Реализация vector

@Harb · Регистрация: 23.03.2014

Author24 — интернет-сервис помощи студентам

Скажите, можно ли где-то посмотреть как примерно реализуются контейнерные классы STL или аналогичных шаблонных библиотек?

Меня, в частности, интересует шаблонный класс vector. Не укладывается в голове как могут быть созданы объекты типа вектор векторов. Ведь если vector - это массив, то каким образом он может содержать элементы разного размера, причем размер каждого элемента может динамически изменяться.

@rikimaru2013 · 18.05.2015, 23:16

так же как в СИ был двухмерный массив, размер элементов которых могу измениться

@Harb · 18.05.2015, 23:28 **[ТС]**

Т.е. объект vector содержит указатель на массив указателей в heap?

MrGluck · 18.05.2015, 23:44

Сообщение от Harb

можно ли где-то посмотреть как примерно реализуются контейнерные классы STL

В хедерах своего компилятора.

http://research.microsoft.com/... ource.html

Добавлено через 2 минуты
Списки, стеки, очереди

@Perfilov · 18.05.2015, 23:57

в векторе содержатся объекты одного размера, но их количество меняется по ходу заполнения вектора.
допустим вектор для объектов типа int, которые в памяти занимают 8 байт. в этом случае внутри вектора
динамически выделяется массив, в который можно было бы уместить скажем 16 таких объектов. т.е. размер массива в байтах: 8*16. внутри вектора есть счетчики, сколько объектов в текущий массив может быть помещено и сколько реально помещено. при очередной операции вставки в вектор код проверяет, а влезет ли новый объект в этот массив. если да, то в нужной мозиции массива инициализируется этот объект. если не влазиет, то внутри вектора создается новый динамический массив который больше предыдущего скажем раза в два. из старого массива в новый копируются все объекты, которые в нем были + в конец втыкается новый объект, из-за которого это перераспределение было затеяно. старый массив удаляется. далее все повторяется. втыкаются новые объекты до тех пор, пока массива хватает. как только перестает хватать - все по новом. создается новый массив еще большего размера ...

Добавлено через 7 минут
по поводу вектора векторов:
статический размер вектора всегда одинаковый и известен во время компиляции. если вектор сделан как я описал выше, то его размер будет складываться из размера его членов данных:

C++

class Vector
{
   Type* pointerToDynamycArray; // указатель на динамический массив
   unsigned arrayCapacity;           // емкость массива
   unsigned objectsCount;            // количество объектов типа Type в массиве
};

sizeof(Vector) >= sizeof(Type*) + sizeof(unsigned) + sizeof(unsigned);
в случае, когда Type - это какой-то вектор, ничего не меняется, т.к. размер указателя на что-то всегда одинаковый и известен во время компиляции.

@Harb 1 / 1 / 0 Регистрация: 23.03.2014 Сообщений: 79
		1
	Реализация vector 18.05.2015, 23:09. Показов 6107. Ответов 4 Метки нет (Все метки) Скажите, можно ли где-то посмотреть как примерно реализуются контейнерные классы STL или аналогичных шаблонных библиотек? Меня, в частности, интересует шаблонный класс vector. Не укладывается в голове как могут быть созданы объекты типа вектор векторов. Ведь если vector - это массив, то каким образом он может содержать элементы разного размера, причем размер каждого элемента может динамически изменяться. 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	18.05.2015, 23:16	2
	так же как в СИ был двухмерный массив, размер элементов которых могу измениться 0

@Harb 1 / 1 / 0 Регистрация: 23.03.2014 Сообщений: 79
	18.05.2015, 23:28 [ТС]	3
	Т.е. объект vector содержит указатель на массив указателей в heap? 0

MrGluck Форумчанин 8216 / 5046 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	18.05.2015, 23:44	4
	Сообщение было отмечено schdub как решение Решение Сообщение от Harb можно ли где-то посмотреть как примерно реализуются контейнерные классы STL В хедерах своего компилятора. http://research.microsoft.com/... ource.html Добавлено через 2 минуты Списки, стеки, очереди 1

	18.05.2015, 23:57

Реализация vector

Решение