Как реализован 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

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

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

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

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

 void construct(pointer p, const_reference val);

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

  void destroy(pointer p);

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

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

Подробнее о размещении новых

Answer 3

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

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

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

Answer 4

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

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

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

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

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

РЕДАКТИРОВАТЬ: В связанной заметке я только что нашел следующее сообщение в блоге Херба Саттера, в котором он комментирует более раннее сообщение в блоге Эндрю Кенига о том, следует ли беспокоиться о соприкосновении векторных элементов в памяти: 1012 * Не передайте: векторы гарантированно будут смежными .

Answer 5

Раздел 23.2.4, of1 стандарта требует, чтобы арифметика для указателей на вектор работала так же, как с указателями на массив.

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

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

Answer 6

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

Answer 9

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

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

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

new T[newSize]

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

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

4) копия push_back создает объект в первом доступном месте.Если требуется, необходимо выделить больше памяти аналогично резервному

.