Как реализован C++ std :: vector?

Question

Я много использовал std::vector, и недавно я задал себе этот вопрос: «Как реализовано std::vector?»

У меня было два варианта:

1) Связанный список, а затем сделать API чувствовать себя как случайного доступа (т.е. перегрузка operator[]).

2) Использование new, например. Foo* temp = new Foo[20]: Я считаю, что они делают что-то подобное, но затем возникает еще один вопрос. Всегда ли они выделяют максимальное (uint32_t) хранилище для предоставления произвольного доступа? (Это неэффективно с точки зрения памяти.)

Или есть что-то еще, о чем я должен знать?

Answer 1

Он реализован с использованием базового массива.

Невозможно реализовать std::vector<T> со связанным списком, поскольку стандарт гарантирует, что элементы в списке будут удерживаться в непрерывной памяти.

Answer 2

Существует ни один способ его реализации. Различные реализации могут быть разными, при условии сохранения семантики и удовлетворения требований.

В любой момент времени должен быть примитивный массив из Т, удовлетворяющий требованиям соприкосновения. Однако то, как оно распределяется, вырастает, сокращается и освобождается, зависит от исполнителя.

Вы можете прочитать реализацию самостоятельно, она находится прямо в файле заголовка.

Я могу вам сказать, что no реализация использует связанные списки. Они не соответствуют требованиям стандарта.

Answer 3

Я считаю, что STL использует опцию № 2 (или что-то подобное), потому что гарантируется сохранение std :: vector <> элементов в смежной памяти.

Если вы ищете структуру памяти, которая не требует использования непрерывной памяти, посмотрите на std :: deque.

Answer 4

Они используют динамически выделенный массив, который при необходимости восстанавливается. Необходимо использовать нечто вроде массива, чтобы элементы были непрерывными в памяти, что гарантируется стандартом.

Кстати, одним из распространенных способов восстановления массива является удвоение размера по мере необходимости. Это так, что если вы вставляете n предметов, то самое большее только O(log n) разрастаются разрастания и не более O(n) пространство впустую.

Вы можете прочитать одну реализацию для себя по адресу SGI (где первоначально была задумана STL).

Answer 5

Я считаю, что это третий вариант. Он не может просто использовать new T[n], потому что тогда ему действительно нужно было бы построить столько объектов, сколько они выделяют. Например

std::vector<Foo> v; 
v.reserve(10); 

Если ваша реализация просто в конечном итоге делает new Foo[10] тогда вы просто построили 10 экземпляров Foo.

Вместо этого он использует свой аллокатор выделить и освободить сырую память (без построения объектов), и в случае необходимости (например, когда вы на самом деле push_back объектов) места копирования построенного экземпляров в правильную ячейку памяти в своем резерве с использованием размещения нового и удаляет их с явным вызовом деструктора (что-то, что вы делали бы только в сочетании с размещением нового). Класс Распределитель предоставляет следующие методы для того, что я предполагаю реализации вектора используют

void construct(pointer p, const_reference val); 

    Returns: 
    new((void *)p) T(val) 

    void destroy(pointer p); 

    Returns: 
    ((T*)p)->~T() 

(далее «возвращается», вероятно, следует читать «эффект» или аналогичный.)

Подробнее о placement new

Answer 6

Раздел 23.2. 4, ¶1 стандарта требует, чтобы арифметика на указателях в векторе работала так же, как с указателями в массив.

Элементы вектора хранятся смежно, а это означает, что если v является вектор, где Т представляет некоторый тип кроме BOOL, то он подчиняется тождество & v [N] == & V [ 0] + n для все 0 < = n < v.size().

Это гарантирует, что хранилище находится в массиве. Конечно, если вы измените размер массива на большее, он может быть перемещен в памяти.

Answer 7

Нет никакого реального массива вообще в любой достойной реализации (если есть, вы не можете использовать какой-либо объект в нем без конструктора по умолчанию), а только необработанную память, которая распределяется. Он распределяется так, как обычно, по удвоению каждый раз, когда вам нужно его расширять.

Затем вектор использует распределение по месту, чтобы вызвать конструкторы класса в правильном месте после того, как каждый слот фактически используется фактически.

Когда есть расширение, оно попытается перераспределить на месте (но это немного глупо и обычно не работает, подумайте о сжатии кучи окон 98), но обычно будет создавать совершенно новое распределение и копирование.

Стандартный вектор stl всегда все вместе, но не все реализации работают так (я знаю, написав некоторые из них). Вероятно, ни один из них не является связанным списком.

Answer 8

Из того, что я прочитал в книгах, и из функциональности резерва и требования, чтобы элементы векторов были смежными, это то, что я считаю возможным способом реализации Vector.

1) Элементы векторов должны быть смежными, поддерживая O (1) случайный доступ и векторы должны быть совместимы с массивами C. Это просто означает, что нет связанных списков.

2) Когда вы вызываете резерв, он резервирует дополнительную память. Но резерв не звонит

new T[newSize] 

зарезервировать больше памяти. В противном случае он вызовет конструктор по умолчанию.Поскольку uncleben объяснял, когда резерв называется векторным классом, он просто выделяет больше неинициализированной памяти в свой распределитель (если требуется) и копирует новые объекты в эту память с использованием места размещения new (если больше памяти выделено)

3) Изначально вектор некоторая емкость по умолчанию. для которого выделяется неинициализированная память при создании векторного объекта.

4) copy_back copy создает объект в первом доступном месте. При необходимости требуется дополнительная память, как резерв

Answer 9

Педагогическая (и, следовательно, упрощенная) версия контейнера под названием «Vec» обсуждается в главе 11 замечательной (вводной) книги «Ускоренный C++». То, что они описывают это урезанная версия станд :: вектор, но я думаю, что все еще стоит отметить, что:

1) они реализуют свой шаблонный класс с точки зрения массива,

2) они обсуждают push_back с точки зрения трюка (упомянутого выше) выделения большего объема памяти, чем это необходимо, и возврата для большего количества времени, когда они заканчиваются, и

3) они используют распределитель <T> для управления памятью. В этом контексте новый оператор недостаточно гибкий, так как он выделяет и инициализирует память.

Повторяю, однако, это не означает, что фактические реализации там просты. Но так как «Ускоренный C++» довольно широко распространен, заинтересованные могут найти в соответствующей главе односторонние векторные объекты, которые могут быть созданы, скопированы, назначены и уничтожены.

EDIT: В соответствующей заметке я только что нашел следующее сообщение в блоге Herb Sutter, в котором он комментирует предыдущее сообщение в блоге Andrew Koenig относительно того, следует ли беспокоиться о непрерывности векторных элементов в памяти: Cringe not: Vectors are guaranteed to be contiguous.