Амортизация в 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,
Или это чисто зависящая от реализации вещь?
Решение
Гарантируется ли, что емкость вектора «удвоится», если произойдет перераспределение?
Нет. Сложность перераспределения памяти постоянна. То, будет ли емкость объекта удваиваться при необходимости или увеличено другим фактором, зависит от реализации.
будет ли «+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 имеют одинаковую сложность для выделения памяти — амортизируемая постоянная.
Другие решения
Вектор — это контейнер последовательности, который поддерживает (амортизированную) константу
время вставки и удаления операций в конце; [Vector.overview]
а также
Если размер () < sz, добавляет sz — size () вставленные по умолчанию элементы к
последовательность.
для изменения размера. ИМХО это означает, что да, гарантируется, что емкость вектора «удвоится», если произойдет перераспределение