Амортизация в std :: vector :: resize и std :: vector :: push_back

Question

Амортизация в std :: vector :: resize и std :: vector :: push_back

Мы знаем, что механизм перераспределения заботится о выделении большего объема памяти, который нам действительно нужен при вызове std::vector::push_back(),
Обычно емкость увеличивается с множителем 2х или с золотым коэффициентом ~ 1,618 …

Предположим, мы добавляем элементы следующим образом:

std::vector<int> v;
for(unsigned i = 0; i < 100000; ++i)
{
v.resize(v.size() + 1);
}

Гарантируется ли, что емкость вектора «удвоится», если произойдет перераспределение?
Другими словами: будет ли «+1 изменить размер» выделять память так же, как это делается для push_back,

Или это чисто зависящая от реализации вещь?

3

c++capacity resize vector

Решение

Другие решения

Вектор — это контейнер последовательности, который поддерживает (амортизированную) константу
время вставки и удаления операций в конце; [Vector.overview]

а также

Если размер () < sz, добавляет sz — size () вставленные по умолчанию элементы к
последовательность.

для изменения размера. ИМХО это означает, что да, гарантируется, что емкость вектора «удвоится», если произойдет перераспределение

0

Источник

Accepted Answer

Гарантируется ли, что емкость вектора «удвоится», если произойдет перераспределение?

Нет. Сложность перераспределения памяти постоянна. То, будет ли емкость объекта удваиваться при необходимости или увеличено другим фактором, зависит от реализации.

будет ли «+1 изменить размер» выделять память так же, как это делается для push_back

Да.

std::vector::resize(size_type sz) присоединяет sz - size() инициализированные значением элементы в последовательности, когда sz больше, чем size(), Это эквивалентно:

 insert(end(), sz-size(), <value initialized object>);

std::vector::insert, std::vector::emplace, а также std::vector::push_back имеют одинаковую сложность для выделения памяти — амортизируемая постоянная.

1