Когда std :: vector перераспределяет свой массив памяти?

Question

Я не могу найти ничего, что дает окончательный ответ.Мне было просто любопытно, если std :: vector перераспределяет свой внутренний массив только тогда, когда он абсолютно обязан или будет перераспределяться раньше времени в ожидании (так сказать).

Например:

std::vector<int> myVector;
for (int i = 0; i < 1000; ++i) myVector.push_back(i);

cout << myVector.size() << '\n'      // Gives 1000 as expected
     << myVector.capacity() << endl; // Gives 1024 which makes sense

Если я продолжу добавлять элементы, есть ли вероятность того, что один из следующих 24 элементов, которые я добавлю, изменит емкость или будет перераспределяться только после того, как я добавлю 25-й элемент?

Примечание:

Я выполнил тест с использованием gcc 4.4.3 под Linux, но кажется, что перераспределение выполняется «по требованию», но мне было любопытно, повезло ли мне просто или что-то где-то говорило, что этоожидается поведение.

Answer 1

из стандарта C ++ 23.2.4.2:

size_type capacity() const;

Возвращает: общее количество элементов, которое может содержать вектор без перераспределения.

Также из стандарта

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

Так что да, вы можете быть уверены.

Редактировать: Как заметил @Бо Перссон, есть одна загвоздка. Стандарт ничего не говорит, если мы никогда не позвоним reserve(). Однако на практике это работает хорошо, потому что ни одна из реализаций не помнит, вызвали ли вы резервный или нет. Я считаю, что это ошибка. И, как упомянул @Martin в своем ответе на черновик C ++ 0x, это исправлено.

Answer 2

Из стандарта: n3092: Черновик C ++ 0x

23.3.6.2 векторная емкость [векторная емкость]

резерв пустот (size_type n);
2 Эффекты: Директива, которая сообщает вектору о запланированном изменении размера, чтобы он мог соответствующим образом управлять распределением памяти.После Reserve (), Capacity () больше или равна аргументу резерва, если происходит перераспределение;и равен предыдущему значению емкости () в противном случае. Перераспределение происходит в этой точке тогда и только тогда, когда текущая емкость меньше, чем аргумент резерва () .Если выдается исключение, кроме как с помощью конструктора перемещения типа, отличного от CopyConstructible, эффекты отсутствуют.

23.3.6.4 векторные модификаторы [vector.modifiers]
Примечания: Вызывает перераспределение, если новый размер больше, чем старая емкость .Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются действительными.Если исключение выдается не конструктором копирования, конструктором перемещения, оператором присваивания или оператором присваивания перемещения T или какой-либо операцией InputIterator, никаких эффектов не возникает.Если исключение выдается конструктором перемещения не-CopyConstructible T, эффекты не определены.

Answer 3

Если вы посмотрите документацию для push_back на cplusplus.com , в ней говорится:

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

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

size vs capacity
1020 vs 1024
1021 vs 1024
1022 vs 1024
1023 vs 1024
1024 vs 1024
1025 vs 2048

Answer 4

std :: vector перераспределяет себя с увеличенной емкостью по требованию, т.е. когда превышается текущая емкость (когда size() == capacity()).

Сколько емкости будет добавлено, зависит от реализации: обычно new_capacity = old_capacity * factor, где factor где-то от 1,5 до 2 (теоретический идеал равен Золотое сечение ). Это сделано для того, чтобы возврат новых элементов к вектору амортизировал постоянное время.

Answer 5

С cplusplus.com :

Но векторы также имеют емкость, которая определяет объем выделенного ими пространства памяти и может быть равна или больше, чем фактический размер. Дополнительный объем выделенной памяти не используется, но зарезервирован для вектора, который будет использоваться в случае его увеличения. Таким образом, вектор не должен перераспределять память при каждом его увеличении, но только когда это дополнительное пространство исчерпано и вставлен новый элемент (что должно происходить только в логарифмической последовательности в зависимости от его размера).

Answer 6

Мне показались полезными эти заметки:

http://www.sgi.com/tech/stl/Vector.html#2

http://www.sgi.com/tech/stl/FAQ.html (Почему вектор расширяет свое хранилище в два раза, когда он выполняет перераспределение?)

Однако, это SGI STL, не удалось найти документацию по g ++.

Answer 7

http://www.sgi.com/tech/stl/Vector.html состояния

Память будет перераспределена автоматически, если в вектор будет вставлено больше, чем емкостных () - размер ()Перераспределение не изменяет size () и не изменяет значения любых элементов вектора.Однако он увеличивает емкость () и делает недействительными [5] любые итераторы, указывающие на вектор.

Answer 8

Стандарт гарантирует, что вызовы не делают недействительными итераторы. Технически, std::vector может соответствовать стандарту, только выполняя изменения размера, которые не требуют копирования данных в новое местоположение, то есть, которые не делают недействительными итераторы. Хотя я сомневаюсь, что кто-нибудь знает.

Таким образом, изменение размеров происходит при вызовах reserve() или resize() или любых других вызовах, которые задокументированы как аннулирующие итераторы.