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

Question

Каким образом добавление и удаление элементов «масштабирует» данные?Как рассчитывается размер вектора (я считаю, что он отслеживается)?Будем благодарны за любые другие дополнительные ресурсы, чтобы узнать о векторах.

Answer 1

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

.size() isколичество элементов, содержащихся в векторе, тогда как .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.

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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

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

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

Answer 4

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