Как работает С++ std::vector?

Ответ 1

В терминах калибровки есть два значения, представляющие интерес для std::vector: size и capacity (доступ через .size() и .capacity()).

.size() - количество элементов, содержащихся в векторе, тогда как .capacity() - количество элементов, которые могут быть добавлены к вектору, прежде чем память будет перераспределена.

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

Вы можете зарезервировать емкость, используя .reserve. Например:

std::vector<int> A;
A.reserve(1);        // A: size:0, capacity:1  {[],x}
A.push_back(0);      // A: size:1, capacity:1  {[0]}
A.push_back(1);      // A: size:2, capacity:2  {[0,1]}
A.push_back(2);      // A: size:3, capacity:4  {[0,1,2],x}
A.push_back(3);      // A: size:4, capacity:4  {[0,1,2,3]}
A.push_back(4);      // A: size:5, capacity:8  {[0,1,2,3,4],x,x,x}

Перераспределение памяти будет происходить в строках 4, 5 и 7.

Ответ 2

Обычно вектор имеет три указателя. Если вектор никогда не использовался, все они равны 0 или NULL.

• Один для первого элемента вектора. (это итератор begin())
• Один из последних элементов вектора + 1. (это итератор end())
• И еще один до последнего выделенного, но неиспользуемого элемента + 1. (этот минус begin() - это емкость)

Когда элемент вставлен, вектор выделяет некоторое хранилище и устанавливает его указатели. Он может выделить 1 элемент, или он может выделить 4 элемента. Или 50.

Затем он вставляет элемент и увеличивает указатель последнего элемента.

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

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

Ответ 3

Реализация std::vector слегка изменилась с помощью С++ 0x и более поздних версий с введением семантики перемещения (см. Что такое семантика перемещения? для введения).

При добавлении элемента в std::vector, который уже заполнен, изменяется размер vector, который включает в себя процедуру выделения новой более крупной области памяти, перемещение существующих данных в новый vector, удаление старого vector, а затем добавление нового элемента.

std::vector - это класс коллекции в стандартной библиотеке шаблонов. Ввод объектов в vector, их удаление или vector, выполняющий изменение размера при добавлении элемента в полный vector, требует, чтобы класс объекта поддерживал оператор присваивания, конструктор копирования и перемещался семантика. (См. требования типа для std::vector, а std::vector работает с классами, которые по умолчанию не конструктивны? для деталей.)

Один из способов думать о std::vector - это стиль C array смежных элементов типа, указанного при определении vector, который имеет некоторые дополнительные функции для его интеграции в предложения стандартной библиотеки шаблонов. Что выделяет vector из стандартного array, так это то, что a vector будет динамически расти по мере добавления элементов. (См. std::vector и c-style массивы, а также Когда вы будете использовать массив, а не вектор/строку? для некоторого обсуждения различий.)

Использование std::vector позволяет использовать другие компоненты стандартной библиотеки шаблонов, такие как алгоритмы, поэтому использование std::vector имеет довольно много преимуществ по сравнению с стилем C array, поскольку вы можете использовать уже существующие функции.

Вы можете указать начальный размер, если максимум известен заранее. (См. Установите оба элемента и начальную емкость std::vector, а также Выбор между vector:: resize() и vector:: reserve())

Основы физического представления std::vector представляют собой набор указателей, использующих память, выделенную из кучи. Эти указатели позволяют выполнять фактические операции доступа к элементам, хранящимся в vector, удаляя элементы из vector, итерируя по vector, определяя количество элементов, определяя его размер и т.д.

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

С современной семантикой перемещения С++ накладные расходы std::vector были уменьшены, так что он обычно является контейнером по умолчанию, который будет использоваться для большинства приложений, как рекомендовал Бьярн Страуструп в своей книге "Язык программирования С++ 4th Edition", в которой обсуждается С++ 11.

Ответ 4

Я написал вектор в С++ год назад. Это массив с заданным размером (например, 16 символов), который при необходимости увеличивается на эту сумму. То есть, если размер по умолчанию составляет 16 символов, и вам нужно сохранить Hi my name is Bobby, тогда он удвоит размер массива до 32 символов, а затем сохранит массив char.