Амортизация в 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.

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


c++ resize vector capacity
person paceholder    schedule 26.10.2017    source источник
comment
Я не понимаю вопроса. Вы уже упоминали, что емкость обычно увеличивается в 2 раза (т.е. удваивается) или в золотом сечении.   -  person 463035818_is_not_a_number    schedule 26.10.2017
comment
@ tobi303 Я думаю, что ОП спрашивает о resize по сравнению с push_back.   -  person Chris Drew    schedule 26.10.2017
comment
@ChrisDrew ах, хорошо, теперь я понимаю вопрос;), хотя я все еще думаю, что его можно улучшить   -  person 463035818_is_not_a_number    schedule 26.10.2017

Ответы (2)


arrow_upward
1
arrow_downward

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

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

будет ли «+1 resize» выделять память так же, как это делается для 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 имеют одинаковую сложность выделения памяти - амортизируемая константа.

person R Sahu    schedule 26.10.2017
comment
ОП спрашивает о resize. - person Chris Drew; 26.10.2017
comment
Поскольку ваше нет только в ответ на удвоение слова, а не в ответ на то, что, как я думаю, является реальным вопросом ОП (имеет ли resize такое же амортизированное постоянное поведение, что и push_back), я бы предложил для пояснения переместить ваше последнее предложение ( где вы объясняете, что возможны другие факторы, кроме 2) рядом с вашим первым. Обратите внимание, что слово удвоилось в кавычках, а ОП уже упомянул другие возможные факторы и использовал слово «амортизация» в своем заголовке. - person Benjamin Lindley; 26.10.2017
comment
@BenjaminLindley, это определенно улучшает ответ. Спасибо за предложение. - person R Sahu; 26.10.2017
comment
Я не зря взял двойное слово в кавычки. И я прямо спросил про +1 ресайз. Смотрите уточненный вопрос. - person paceholder; 26.10.2017
comment
@paceholder, ответ положительный на вопрос об изменении размера +1. Я не уверен, что могу добавить что-то еще к своему ответу, чтобы сделать его более ясным. - person R Sahu; 26.10.2017

arrow_upward
0
arrow_downward

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

и

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

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

person Community    schedule 26.10.2017