лучший способ сделать Std :: Vector Capacity> = N и размер = 0?

Question

Учитывая std::vector, чей размер и емкость могут быть произвольными, каков наилучший способ изменить его размер на 0 и емкость по крайней мере на N (данное число)?

Моя прямая идея:

void f(vector<int> &t, int N)
{
    t.clear();
    t.reserve(N);
}

но я заметил, что

Перераспределение не гарантируется, а емкость вектора не гарантируется изменение (когда вызывается std :: vector :: clear ).

Так что мне интересно, как избежать перераспределения, когда емкость источника больше, чем заданное N?

Answer 1

Примечание. Этот ответ отвечает на вопросы:

лучший способ сделать std :: vectoracity = N и size = 0?

и

Как лучше всего менять его размер на 0 и емкость на N (заданное число)?

После публикации этого ответа было добавлено изменение "> = N" и добавлено требование избегать перераспределения.

---

Стандарт не предлагает гарантированного способа для достижения этой цели. Но ваш лучший шанс:

 t.clear();
 t.shrink_to_fit();
 t.reserve(N);

Второй вызов рекомендуется , чтобы уменьшить емкость, чтобы соответствовать текущему размеру (который будет 0 в этой точке).

Альтернатива, которая может работать или не работать, опять же на усмотрение реализации, это:

t.swap( std::vector<int>{} );
t.reserve(N);

Answer 2

Лучший способ - это, вероятно, ваш текущий код.

К сожалению, стандарт позволяет реализации иметь контейнеры, емкость которых может только расти. В этом случае ваш код будет гарантировать только то, что емкость составляет по крайней мере N. Перераспределение произойдет, если начальная емкость меньше N, и ничего не произойдет, если емкость больше N. Эти баллы гарантированы стандарт, потому что проект 4659 для C ++ 17 говорит в [vector.capacity] (подчеркните мой):

void reserve(size_type n);
...
3 Эффекты: директива, которая информирует вектор о запланированном изменении размера, чтобы он мог управлять хранилищем распределение соответственно. После резерва (), емкость () больше или равна аргументу резерва, если происходит перераспределение; и равен предыдущему значению емкости () в противном случае . Перераспределение происходит в этот момент, если и только если текущая емкость меньше, чем аргумент резерва ().

и

void shrink_to_fit();
...
8 Эффекты: shrink_to_fit - это необязательный запрос на уменьшение емкости () до размера (). [Примечание: запрос не является обязательным, чтобы разрешить широту для специфических для реализации оптимизаций. - Конец примечания] Это не увеличить емкость (), но может уменьшить емкость (), вызвав перераспределение.

У вас нет способа гарантировать, что емкость будет точно равна N. Вместо этого ваш код гарантирует, что если начальная емкость больше, чем N in, не изменится и перераспределение не произойдет.

Редактировать: это поведение стабильно, по крайней мере, с C ++ 11 (черновик n3337)

Answer 3

Каков наилучший способ изменить его размер на 0 и емкость на N (заданное число)? Моя прямая идея: ...

Ваша прямая идея верна, и самый простой вариант. Хотя, чтобы быть педантичным, reserve меняет емкость на больше или , равную данному числу; не гарантированно будет равным (но все протестированные мной реализации действительно выделяют именно ту сумму, если предыдущая емкость была меньше).

Так что мне интересно, как избежать перераспределения, когда емкость источника больше, чем заданное N?

Используя стандартную реализацию библиотеки, которая решила не освобождать память при вызове clear (т. Е. Любая стандартная соответствующая реализация, как указано ответом здесь ).

---

Другой подход к гарантии (хотя, как представляется, это не является необходимым, поскольку вышеприведенное должно быть гарантировано, несмотря на слабую формулировку на cplusplus.com) отсутствие перераспределения (в случае N > t.capacity()): поскольку вектор содержит простые целые числа и вы, кажется, знаете, сколько будет элементов (как вы знаете, чтобы зарезервировать), вы можете просто позвонить t.resize(N) (чтобы удалить дополнительные элементы в случае, если размер был больше), не очищая вектор, а затем перейти к перезаписи существующих элементы, а не выдвигать новые.

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

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