Почему std :: vector резерв не «двойной» его емкость, а изменение размера делает?
Я только что узнал, что 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 ++ 11 Standard для уточнения требований к reserve; §23.3.6.3 (2):
После
reserve(),capacity()является больше или равно к аргументуreserveесли произойдет перераспределение …
Некоторые дополнительные мысли: из C ++ 11 Standard:
Сложность: Сложность линейна по количеству вставленных элементов плюс расстояние до конца вектора.
Что, по сути, подразумевает постоянную (амортизированную) сложность для вставки одного элемента в конце. Однако это относится только к векторные модификаторы, такие как push_back или же insert (§23.3.6.5).
resize не указан среди модификаторов. Это перечислено в §23.3.6.3 vector Емкость раздела. И нет никаких требований к сложности для resize,
Однако в vector В разделе обзора (§23.3.6.1) написано:
Это (
vector) поддерживает (амортизируется) операции вставки и удаления с постоянным временем в конце
Вопрос в том, resize(size()+1) считается «вставка в конце».
Решение
Насколько я могу сказать, ни resize ни reserve требуется иметь продемонстрированное поведение. Тем не менее, обоим разрешено такое поведение, хотя оба могут либо распределить точную сумму, и оба могут умножить предыдущее распределение в том, что касается стандарта.
У каждой стратегии распределения есть свои преимущества. Преимущество распределения точного количества состоит в том, что у него нет никаких накладных расходов памяти, когда максимальное выделение известно заранее. Преимущество умножения состоит в том, что оно сохраняет постоянное амортизированное свойство при смешивании с операциями вставки в конце.
Подход, выбранный протестированными реализациями, имеет то преимущество, что он позволяет использовать обе стратегии при изменении размера. Чтобы использовать одну стратегию, можно зарезервировать, а затем изменить размер. Чтобы использовать другой, просто измените размер. Конечно, нужно знать о неопределенном поведении, чтобы воспользоваться этим. Это преимущество может или не может быть причиной выбора этих реализаций.
Можно было бы считать это отказом векторного API, как указано в стандарте, что выражение предполагаемого поведения перераспределения невозможно (таким образом, который гарантируется стандартом).
Другие решения
Когда ты resize больше, чем есть емкость, вы уже «демонстрируете», что не хотите резервировать только нужную емкость. С другой стороны, если вы используете reserve Вы явно просите правильную емкость. Если reserve будет использовать ту же стратегию, что и resize не было бы никакого способа зарезервировать только правильную сумму.
В этом смысле resize без reserve для ленивых или в случае, если вы не знаете точную сумму, чтобы зарезервировать. Ты звонишь reserve если вы знаете, какая емкость вам нужна. Это два разных сценария.
PS: как указывал StoryTeller, reserve не требуется резервировать точную сумму, которая запрашивается согласно стандарту. Тем не менее я думаю, что мой главный аргумент все еще остается в силе: resize (без reserve) а также reserve предназначены для разных сценариев, где вы либо даете подсказку о том, сколько вы хотите зарезервировать, либо не заботитесь о фактической емкости и просто хотите, чтобы размер контейнера соответствовал тому, что вы просите.
Почему вы ожидаете, что они будут вести себя одинаково? reserve используется для предварительного распределения пространства, которое вы будете использовать позже, в расчете на то, что у пользователя есть приличный дескриптор ожидаемого конечного размера контейнера. resize это просто нормальное распределение, и поэтому оно следует нормальному, эффективному по скорости подходу геометрического увеличения выделенного пространства контейнера.
Контейнеры увеличиваются в размерах с помощью мультипликативных шагов, чтобы уменьшить количество необходимых распределений и, таким образом, поддерживать скорость и уменьшить фрагментацию памяти. Удвоение является наиболее распространенным, но в некоторых реализациях используются этапы 1,5 (например, MSVC), которые обменивают увеличенные выделения для более неиспользуемого пространства в каждом контейнере.
Но, если пользователь уже сказал библиотеке, насколько большой, по его мнению, контейнер станет — вызывая reserve — нет необходимости выделять лишнее пространство, вместо этого они могут доверять пользователю, который вызвал его с правильным номером. это reserve что имеет необычное поведение, а не resize,
resize требуется следовать экспоненциальной стратегии перераспределения, чтобы выполнить ее гарантию сложности (линейный по количеству элементов вставленный). Это можно увидеть, если учесть, что resize(size() + 1) требуется амортизировать постоянную сложность, поэтому должен следовать экспоненциальный рост по той же причине, что push_back (амортизируемая постоянная сложность) должна расти в геометрической прогрессии.
Реализация reserve разрешено следовать любой стратегии распределения, которая ему нравится, поскольку ее единственное требование к сложности состоит в том, чтобы она была линейной по числу элементов подарок. Однако, если реализация была, например, чтобы округлить до следующей степени двух, это было бы неэффективно (и удивительно) в случае, когда пользователь точно знает, сколько памяти требуется, и могло бы усложнить портирование, если пользователь полагается на это поведение. Широта в стандарте проявляется лучше в тех случаях, когда нет неэффективности пространства, например округляя выделения до размера слова, если распределитель работает с такой гранулярностью.
reserve меняет емкость, в то время как resize изменяет size,
capacity это количество элементов, для которых контейнер выделил место.
size количество элементов в контейнере
Когда вы выделяете пустой вектор, вы получаете значение по умолчанию capacity (Ака пространство). Размер по-прежнему равен 0, а при добавлении элементов в вектор его размер увеличивается. Когда размер равен емкости, и вы добавляете больше предметов, емкость должна увеличиваться (обычно удваивается).
Проблема с вектором заключается в том, что он обеспечивает последовательную память, а это означает, что при каждом новом увеличении выделения также будет требоваться копия предыдущего выделения новому, в случае, если в старой выделенной области памяти не было места для нового размера выделения.
Здесь reserve может помочь, если вы знаете максимум элементов в векторе. Когда вы используете reserve, будет только одно выделение и нет копии памяти, если вы не передадите зарезервированные элементы.
Когда вы указываете точное зарезервированное количество, вы получаете именно ту память, которую вы просили. Когда вы просто добавляете элементы (даже с изменением размера, вы не говорите, что не добавите больше элементов).