Как реализовано изменение размера вектора?

Я пытаюсь выяснить, как вектор добавляет больше объектов после того, как он уже «создал» некоторые, я имею в виду: 

int *ptr;
ptr = new int;

Как после этого вы можете добавить больше объектов к этому указателю? (сделайте это массивом)
Спасибо!


c++ add new-operator pointers
person Tal S    schedule 18.01.2011    source источник
comment
возможный дубликат Добавить новые объекты после использования нового   -  person Evan Teran    schedule 18.01.2011
comment
Ответ на этот вопрос в основном содержится в вашем последнем вопросе (который очень похож на этот).   -  person Evan Teran    schedule 18.01.2011

Ответы (6)


arrow_upward
8
arrow_downward

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

person casablanca    schedule 18.01.2011
comment
Верно, что означает, что хранить указатели на объекты, хранящиеся в векторах, небезопасно, если только вы не примете некоторые меры предосторожности (reserve()). - person Kos; 18.01.2011
comment
@Kos Я знаю, что вы имеете в виду, но я думаю, вам следует перефразировать это, чтобы сделать его менее двусмысленным. Похоже, вы говорите не хранить указатели в векторе. - person San Jacinto; 18.01.2011
comment
В более общем случае размер вектора изменяется до размера kN для вектора размера N с константой k > 1, чтобы уменьшить амортизированную сложность вставки до постоянного времени. - person tyree731; 18.01.2011
comment
Для дальнейшего понимания стандарт по существу гарантирует, что std::vector содержит непрерывный блок памяти. (неофициальный) - person Michael Smith; 18.01.2011
comment
Большинство или все (у меня нет возможности это узнать) реализации по умолчанию создают пустой вектор, а не маленький. Потому что нет ничего необычного в том, что вектор не доживет до того, чтобы увидеть какие-либо элементы, вставленные в него, либо потому, что он был заменен местами, либо перемещен и немедленно уничтожен. Кроме того, большинство или все реализации не удваивают размер, оптимальный коэффициент роста составляет около 1,5. - person Gene Bushuyev; 18.01.2011

arrow_upward
4
arrow_downward

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

Он использует новое размещение для создания объектов в памяти.

Для добавления большего количества объектов, когда ему не хватает памяти, он должен выделить больший объем. Если базовым типом является POD, он может просто realloc, но если нет, он должен перемещать их с operator= объекта.

person CashCow    schedule 18.01.2011
comment
Он действительно использует realloc()? Таким образом, malloc() не устарел в С++, а new неизбежен только тогда, когда объект для выделения не является POD. Можете ли вы указать мне хороший документ, в котором объясняется, почему в С++ нет оператора renew? - person Iharob Al Asimi; 05.07.2015
comment
Он может использовать realloc(). Распределитель имеет правила относительно того, что он должен делать, а не как он это делает. Единственная цель, которую я вижу для обновления [], — это изменение размера (и перемещение, если необходимо) чего-то, ранее выделенного с помощью new[]. Однако, поскольку у нас есть вектор, я не вижу в нем необходимости. realloc() с типом, отличным от POD, будет неопределенным поведением, поскольку вы не можете просто запомнить его. - person CashCow; 06.07.2015
comment
Да, я знаю, что std::vector полностью устраняет необходимость, но мне просто любопытно, спасибо за ответ. - person Iharob Al Asimi; 06.07.2015

arrow_upward
3
arrow_downward

Вы не можете сделать его массивом, вы можете указать его только на один.

Итак, когда вы делаете это:

int *ptr;
ptr = new int;

вы указали указатель ptr на вновь созданное целое число. Вы можете удалить его и создать массив и указать ptr на этот массив:

delete ptr;
ptr = new int[5];
person xx77aBs    schedule 18.01.2011

arrow_upward
1
arrow_downward 

1. Build an array.
2. copy *ptr into it.
3. swap ptrs.
4. delete the temp.

Вот и все, теперь вы «изменили размер» вашего указателя мыши.

person Edward Strange    schedule 18.01.2011
comment
Теперь я все понял! Большое всем спасибо! - person Tal S; 18.01.2011

arrow_upward
1
arrow_downward

Вектор отслеживает два бита информации.

  1. Это размер, который представляет собой количество элементов, которые он в данный момент содержит.
  2. Это емкость, или сколько элементов он может содержать до исчерпания памяти.

Если добавление элемента не приводит к превышению его емкости, то проблем нет. Он просто добавляет новый элемент.

Если емкость будет превышена, он рассчитает новую емкость (обычно в 1,5-2 раза больше текущей емкости) и скопирует все элементы в новый массив. Вот почему итераторы становятся недействительными после добавления элемента в вектор. Они могут иметь в виду старый (теперь освобожденный) массив.

person Ferruccio    schedule 18.01.2011

arrow_upward
0
arrow_downward

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

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

person Al Kepp    schedule 18.01.2011
comment
Вы могли сделать это самостоятельно с помощью int* arr = new int[n];, но было бы сложно самостоятельно отслеживать логический размер по сравнению с выделенным размером. - person Dawson; 18.01.2011
comment
@Toolbox: Если вы сделаете это, ваши исходные данные из arr[0] будут потеряны. - person Al Kepp; 18.01.2011
comment
@Аль Кепп: Почему так? Все, что вы можете сделать с классом, вы можете сделать без него, но, как выразился @Toolbox, просто сложно отслеживать все переменные. - person casablanca; 18.01.2011