Что происходит под капотом вектора :: push_back памяти? - PullRequest
13 голосов
/ 26 октября 2011

Мой вопрос касается эффекта vector::push_back, я знаю, что он добавляет элемент в конец вектора, но что происходит под капотом?

Объекты памяти IIRC распределяются последовательно, поэтомумой вопрос заключается в том, просто ли vector::push_back выделяет больше памяти сразу после вектора, и если да, что происходит, если в этом месте недостаточно свободной памяти?Или, возможно, в конце указатель добавлен, чтобы вектор «перепрыгнул» в место, где он продолжается?Или он просто перераспределяется путем копирования его в другое место, где достаточно места, а старая копия отбрасывается?Или может быть что-то еще?

Ответы [ 7 ]

20 голосов
/ 26 октября 2011

Если уже выделено достаточно места, объект является копией, созданной из аргумента на месте. Когда памяти недостаточно, вектор будет увеличивать свой внутренний буфер данных в соответствии с некоторой геометрической прогрессией (каждый раз новый размер будет k*old_size с k > 1 [1] ) и все объекты, присутствующие в исходный буфер будет затем перемещен в новый буфер. После завершения операции старый буфер будет выпущен в систему.

В предыдущем предложении Move не используется в техническом Move-конструкторе / Move-Assignment смысле, они могут быть Move или скопировано или любая эквивалентная операция.

[1] Увеличение с коэффициентом k > 1 обеспечивает постоянную амортизированную стоимость push_back. Фактическая константа варьируется от одной реализации к другой (Dinkumware использует 1,5, gcc использует 2). Амортизированная стоимость означает, что даже если очень часто один push_back будет очень дорогим (O(N) от размера вектора в то время), эти случаи случаются достаточно редко, чтобы стоимость всех операций по всему набору вставок является линейным по количеству вставок, и, таким образом, каждая вставка в среднем постоянных затрат)

3 голосов
/ 26 октября 2011

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

Решение о том, как это реализовать, зависит от распределителя.

Однако вектор решает,сколько места можно зарезервировать: стандарт гарантирует, что емкость вектора будет увеличиваться как минимум в 1,5 1 геометрически (см. комментарий), что предотвращает ужасную производительность из-за многократных «малых»'allocations.

При физическом перемещении / копировании элементов:

  • c ++ 11 соответствующих реализаций будет перемещать элементов, если они поддерживают назначение и конструкцию перемещения
  • большинство известных мне реализаций (особенно g ++) просто используют std :: copy для типов POD;специализация алгоритма для типов POD обеспечивает компиляцию в (по существу) операцию memcpy.Это, в свою очередь, компилируется в любую быструю инструкцию процессора в вашей системе (например, инструкции SSE2)

1 Я попытался найти справочную цитату для этого из стандартного черновика документа n3242,но я не смог найти его в это время

2 голосов
/ 26 октября 2011

Вектор гарантирует, что все элементы являются сомнительными в памяти.

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

start:     Points at the beginning of the allocated block.
final:     Points one past the last element in the vector.
           If the vector is empty then start == final 
capacity:  Points one past the end of allocated memory.
           If final == capacity there is no room left.

Когда выpush back.

  1. Если final меньше емкости:
    • , новый элемент копируется в место, на которое указывает final
    • final увеличивается на следующую позицию.
  2. Если final равен емкости, вектор заполнен
    • должна быть выделена новая память.
    • Компилятор выделит X*(capacity - start)*sizeof(t) bytes.
    • где X обычно значение между 1,5 и 2.
    • Затем он копирует все значения из старого буфера памяти в новый буфер памяти.
    • в буфер добавлено новое значение.
    • Передает указатели начала / финала / емкости.
    • Освобождает старый буфер
2 голосов
/ 26 октября 2011

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

Чтобы избежать чрезмерного количества выделений и сохранить среднее время push_back() на O(1), для перераспределения требуется, чтобы размер был увеличен по крайней мере на постоянный коэффициент.(1,5 и 2 являются общими)

0 голосов
/ 23 марта 2012

Если у вас есть представление о том, каким будет конечный размер вашего массива, попробуйте сначала vector::reserve память.Обратите внимание, что reserve отличается от vector::resizereserve vector::size() вашего массива не изменяется

0 голосов
/ 26 октября 2011

std :: vector overallocates - обычно он выделяет больше памяти, чем необходимо автоматически.На size это не влияет, но вы можете контролировать это через capacity.

std :: vector скопирует все , если дополнительной емкости недостаточно.

Память, выделенная std :: vector, является необработанной, конструкторы не вызываются по требованию с использованием размещения new.

Итак, push_back делает:

  • если емкостьнедостаточно для нового элемента, он
    • выделит новый блок
    • скопирует все существующие элементы (обычно используя конструктор копирования)
  • увеличитсяпо размеру
  • скопировать новый элемент в новое место
0 голосов
/ 26 октября 2011

При вызове vector::push_back указатель end сравнивается с указателем емкость .Если для нового объекта достаточно места, вызывается placement new для создания объекта в доступном пространстве, а указатель end увеличивается.

Если места недостаточно, vector вызывает свой allocator , чтобы выделить достаточно непрерывного пространства, по крайней мере, для существующих элементов плюс новый элемент (другая реализация может увеличить выделенную память различными умножителями).Затем все существующие элементы плюс новый будут скопированы во вновь выделенное пространство.

...