Почему std :: vector reserve не "удваивает" его емкость, а изменяется размер?

Я только что узнал, что std::vector<T>::resize "удваивает" свою емкость даже при изменении размера до одного элемента выше текущего размера:

std::vector<int> v(50);
v.resize(51);
std::cout << v.capacity() << std::endl;

Эта программа выводит 100 с GCC и Clang и 75 с Visual C++. Однако, когда я переключаюсь с resize для reserve:

std::vector<int> v(50);
v.reserve(51);
std::cout << v.capacity() << std::endl;

Выходной сигнал составляет 51 со всеми тремя компиляторами.

Интересно, почему в реализациях используется другая стратегия расширения для resize и reserve. Это кажется непоследовательным, и я бы ожидал такого же поведения здесь.

Я просто добавляю ссылку на мотивацию для моего вопроса, где сообщается о влиянии на производительность: почему C++ векторы STL на 1000 раз медленнее при выполнении многих резервов?

Добавление цитаты из C+ +1 1 Стандарт для уточнения требований к reserve; §23.3.6.3 (2):

После reserve() capacity() больше или равна аргументу reserve если происходит перераспределение...

Некоторые дополнительные мысли: из C+ +1 1 Стандарт:

Сложность: сложность линейна по количеству вставленных элементов плюс расстояние до конца вектора.

Это, собственно, подразумевает постоянную (амортизированную) сложность для вставки одного элемента в конце. Однако это относится только к векторным модификаторам, таким как push_back или insert (§23.3.6.5).

resize не входит в число модификаторов. Он указан в разделе 23.3.6.3 vector емкости. И нет требований к сложности для resize.

Однако в разделе обзора vector (§23.3.6.1) написано:

он (vector) поддерживает (амортизируется) постоянное время вставки и стирания операций в конце

Вопрос в том, является ли resize(size()+1) "вставкой в конце".

Ответ 1

Насколько я могу судить, ни для resize ни для reserve не требуется продемонстрированное поведение. Тем не менее, оба они допускают такое поведение, хотя оба могут либо выделять точную сумму, и оба могут умножить предыдущее распределение до уровня стандарта.

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

Преимущество подхода, выбранного тестируемыми реализациями, заключается в том, что он позволяет обе стратегии при изменении размера. Чтобы использовать одну стратегию, можно зарезервировать и затем изменить размер. Чтобы использовать другое, просто измените размер. Конечно, нужно знать о неуказанном поведении, чтобы воспользоваться этим. Это преимущество может быть или не быть аргументом в пользу выбора этих реализаций.

Можно было бы подумать, что отказ API-интерфейса API, как указано в стандарте, не позволяет выразить предполагаемое поведение перераспределения (таким образом, что это гарантируется стандартом).

Ответ 2

Когда вы resize больше, чем есть емкость, вы уже "демонстрируете", что не хотите резервировать только нужную емкость. С другой стороны, если вы используете reserve вы явно запрашиваете нужную емкость. Если reserve будет использовать ту же стратегию, что и resize не было бы возможности зарезервировать нужную сумму.

В этом смысле resize без reserve для ленивых или в случае, если вы не знаете точную сумму резерва. Вы называете reserve если знаете, какую мощность вам нужно. Это два разных сценария.

PS: Как отметил StoryTeller, reserve не требуется для резервирования точной суммы, которая запрашивается в соответствии со стандартом. Тем не менее, я думаю, что мой главный аргумент по-прежнему сохраняется: resize (без reserve) и reserve предназначены для разных сценариев, где вы либо даете намек на то, сколько вы хотите зарезервировать или не заботитесь о фактической емкости, и просто хотите, чтобы контейнер размером до того, что вы просите.

Ответ 3

Почему вы ожидаете, что они будут вести себя одинаково? reserve используется для предварительного распределения пространства, которое вы будете использовать позже, с ожиданием того, что пользователь имеет приличную ручку для ожидаемого конечного размера контейнера. resize - это просто нормальное распределение, и поэтому он следует нормальному, быстродействующему, приближающемуся геометрическому увеличению пространства, выделенного контейнером.

Контейнеры увеличиваются в размерах с помощью мультипликативных шагов, чтобы уменьшить количество требуемых ассигнований и тем самым поддерживать скорость и уменьшать фрагментацию памяти. Удвоение является наиболее распространенным, но в некоторых реализациях используются шаги 1,5 (например, MSVC), которые торгуют увеличенными ассигнованиями для более низкого пространства в каждом контейнере.

Но, если пользователь уже сказал библиотеке, насколько большой, по их мнению, контейнер получит - вызывая reserve - нет необходимости выделять лишнее пространство, они могут вместо этого доверять пользователю, чтобы вызвать его с правильным номером. Это reserve который имеет необычное поведение, а не resize.

Ответ 4

resize требуется, чтобы следовать экспоненциальной стратегии перераспределения, чтобы выполнить свою гарантию сложности (линейную по количеству вставленных элементов). Это можно увидеть, учитывая, что для resize(size() + 1) требуется амортизированная постоянная сложность, поэтому он должен следовать экспоненциальному росту по той же причине, что push_back (амортизированная постоянная сложность) должен экспоненциально расти.

Реализации reserve разрешено следовать любой стратегии распределения, которой он нравится, поскольку его единственным требованием сложности является то, что он является линейным по количеству присутствующих элементов. Однако, если бы реализация была, например, округленной до следующей мощности в два, это было бы неэффективным по площади (и неожиданным) в случае, когда пользователь точно знает, сколько памяти требуется, и может усложнить перенос, если пользователь приходит к полагайтесь на это поведение. Широта в Стандарте лучше проявляется в случаях, когда нет неэффективности пространства, например, округляя распределение до размера слова, если распределитель работает с такой детализацией.

Ответ 5

reserve изменяет емкость, а resize изменяет size.

capacity - это количество элементов, на которые в данный момент помещается контейнер.

size - количество элементов в контейнере.

Когда вы выделяете пустой вектор, вы получаете capacity умолчанию (пространство AKA). Размер по-прежнему равен 0, и когда вы добавляете элементы в вектор, его размер увеличивается. Когда размер равен емкости, и вы добавляете больше предметов, емкость должна расти (как правило, сама по себе).

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

Здесь reserve может помочь, если вы знаете максимальные элементы в векторе. Когда вы используете reserve, будет только одно выделение и нет копии памяти, если вы не передадите зарезервированные элементы.

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