основной вопрос по std :: vector в C ++

Question

C ++ учебники и темы, такие как эти говорят, что векторные элементы физически соприкасаются в памяти.

Но когда мы делаем такие операции, как v.push_back(3.14), я бы предположил, что STL использует оператор new, чтобы получить больше памяти для хранения нового элемента 3.14, только что введенного в вектор.

Теперь допустим, что вектор размера 4 хранится в ячейках памяти компьютера, помеченных 0x7, 0x8, 0x9, 0xA.Если ячейка 0xB содержит некоторые другие несвязанные данные, как 3.14 попадет в эту ячейку?Означает ли это, что ячейка 0xB будет скопирована в другое место, стерта, чтобы освободить место для 3.14?

Answer 1

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

vector< int > vec;
for( int i = 0; i < 100; i++ )
    vec.push_back( i );

cout << vec.size(); // prints "100"
cout << vec.capacity(); // prints some value greater than or equal to 100

Метод capacity() возвращает размер массива, зарезервированного вектором, а метод size() возвращает количество элементов в массиве, которые фактически используются.capacity() всегда будет возвращать число, большее или равное size().Вы можете изменить размер резервного массива, используя метод reserve():

vec.reserve( 400 );
cout << vec.capacity(); // returns "400"

Обратите внимание, что size(), capacity(), reserve() и все связанные методы относятся к отдельным экземплярамТип, что вектор держит.Например, если параметр типа vec T является структурой, которая занимает 10 байтов памяти, то vec.capacity(), возвращая 400, означает, что вектор фактически имеет 4000 байтов зарезервированной памяти (400 x 10 = 4000).

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

if(capacity() < size() + items_added)
{
    size_t sz = capacity();
    while(sz < size() + items_added) 
       sz*=2;
    T* new_data = new T[sz]; 
    for( int i = 0; i < size(); i++ )
        new_data[ i ] = old_data[ i ];
    delete[] old_data;
    old_data = new_data;
}

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

Answer 2

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

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

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

Answer 3

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

Answer 4

Если для добавления нового элемента недостаточно места, будет выделено больше места (как вы правильно указали), и старые данные будут скопированы в новое место.Таким образом, ячейка 0xB будет по-прежнему содержать старое значение (так как оно может иметь указатели на него в других местах, его невозможно переместить, не вызывая хаоса), но весь рассматриваемый вектор будет перемещен в новое местоположение.

Answer 5

Вектор - это массив памяти. Типичная реализация заключается в том, что он захватывает больше памяти, чем требуется. Если этот след необходимо расширить на любую другую память - вся партия копируется. Старый материал освобожден. Векторная память находится в стеке - и это следует отметить. Также полезно сказать, что требуется максимальный размер.

Answer 6

В C ++, который происходит от C, память не «управляется», как вы описываете - содержимое ячейки 0x0B не будет перемещаться.Если вы это сделаете, любые существующие указатели будут недействительными!(Единственный способ сделать это возможным - это если в языке нет указателей и используются только ссылки для аналогичной функциональности.)

std::vector выделяет новый больший буфер и сохраняет значение 3.14 для "конец "буфера.

Обычно, однако, для оптимизированных this->push_back() с std::vector выделяет память примерно вдвое больше, чем this->size().Это гарантирует, что разумное количество памяти будет обменено на производительность.Таким образом, не гарантируется, что 3.14 вызовет this->resize(), и может быть просто помещен в this->buffer[this->size()++] тогда и только тогда, когда this->size() < this->capacity().