Является ли shrink_to_fit правильным способом уменьшить емкость `std::vector` до его размера?

В С++ 11 shrink_to_fit был введен для дополнения некоторых контейнеров STL (например, std::vector, std::deque, std::string).

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

Кроме того, в предыдущем SO-вопросе OP не поощрялся использовать shrink_to_fit, чтобы уменьшить емкость его std::vector до его размера. Причины этого не приводятся ниже:

shrink_to_fit ничего не делает или дает проблемы с локальностью кэша, а O (n) - выполнить (поскольку вам нужно скопировать каждый элемент в новый, более мелкий дом). Обычно это дешевле оставить в памяти. @Massa

Может ли кто-нибудь быть таким добрым, чтобы ответить на следующие вопросы:

Удерживаются ли аргументы в цитате?
Если да, то какой способ уменьшить емкость контейнера STL до его размера (по крайней мере, для std::vector).
И если есть лучший способ сжать контейнер, какая причина существования shrink_to_fit после всего?

Ответ 1

Удерживаются ли аргументы в цитате?

Измерьте, и вы узнаете. Вы ограничены в памяти? Можете ли вы определить правильный размер спереди? Это будет более эффективно для reserve, чем сжиматься после факта. В общем, я склонен согласиться с предпосылкой, что большинство применений, вероятно, прекрасны с ослаблением.

Если да, то какой способ уменьшить емкость контейнера STL до его размера (по крайней мере, для std::vector).

Комментарий относится не только к shrink_to_fit, но и к любому другому способу сокращения. Учитывая, что вы не можете realloc на месте, это связано с приобретением другого фрагмента памяти и копирования там независимо от того, какой механизм вы используете для сокращения.

И если есть лучший способ сжать контейнер, какая причина существования shrink_to_fit после всего?

Запрос не имеет обязательной силы, но альтернативы не имеют более надежных гарантий. Вопрос в том, имеет ли смысл сокращение, если это так, то имеет смысл предоставить операцию shring_to_fit, которая может воспользоваться тем фактом, что объекты перемещаются в новое место. То есть если тип T имеет конструктор перемещения noexcept(true), он будет выделять новую память и перемещать элементы.

В то время как вы можете добиться того же самого извне, этот интерфейс упрощает работу. Эквивалент shrink_to_fit в С++ 03 был бы следующим:

std::vector<T>(current).swap(current);

Но проблема с этим подходом заключается в том, что когда копия выполняется во временное, она не знает, что current будет заменена, ничего не сообщает библиотеке, что она может перемещать удерживаемые объекты. Обратите внимание: использование std::move(current) не приведет к желаемому эффекту, так как он перемещает весь буфер, поддерживая тот же capacity().

Реализация этого извне будет немного более громоздкой:

{
   std::vector<T> copy;
   if (noexcept(T(std::move(declval<T>())))) {
      copy.assign(std::make_move_iterator(current.begin()),
                  std::make_move_iterator(current.end()));
   } else {
      copy.assign(current.begin(), current.end());
   }
   copy.swap(current);
}

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

Ответ 2

Удерживаются ли аргументы?

Поскольку аргументы изначально мои, не против, если я их защищу, один за другим:

Либо shrink_to_fit ничего не делает (...)

Как уже упоминалось, стандарт говорит (много раз, но в случае vector он раздел 23.3.7.3...), что запрос не имеет обязательной силы, чтобы обеспечить широту реализации для оптимизации. Это означает, что реализация может определить shrink_to_fit как no-op.
(...) или дает вам проблемы с локальностью кэша

В случае, если shrink_to_fit не реализован как no-op, вам необходимо выделить новый базовый контейнер с емкостью size(), скопировать (или, в лучшем случае, переместить), построить все ваши N = size() новые предметы из старых, уничтожают все старые (в случае перемещения это должно быть оптимизировано, но возможно, что это включает цикл снова поверх старого контейнера), а затем разрушает старый контейнер как таковой. Это делается в libstdc++-4.9, как описано Дэвидом Родригесом,
```
      _Tp(__make_move_if_noexcept_iterator(__c.begin()),
          __make_move_if_noexcept_iterator(__c.end()),
          __c.get_allocator()).swap(__c);
```
и в libc++-3.5 с помощью функции из __alloc_traits, которая делает примерно то же самое.

О, и реализация абсолютно не может полагаться на realloc (даже если она использует malloc внутри ::operator new для своих распределений памяти), потому что realloc, если он не может сжиматься на месте, либо покинет память (нет-op case) или сделать побитую копию (и упустить возможность для перенастройки указателей и т.д., которые предоставили бы соответствующие С++ функции копирования/перемещения).

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

В простом случае, когда векторы больше, чем линии кэша, все это движение оказывает давление на кеш.
и это O (n)

Если N = size(), я думаю, что было установлено выше, что, по крайней мере, вам нужно сделать одно n распределение размеров, n копировать или перемещать конструкции, n разрушения и один old_capacity размер освобождения.
обычно дешевле просто оставить память в памяти

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

Если да, то какой способ уменьшить емкость контейнера STL до его размера (по крайней мере, для std::vector).

Правильный способ по-прежнему shrink_to_fit... вам просто нужно либо не полагаться на него, либо хорошо знать вашу реализацию!

И если есть лучший способ сжать контейнер, какая причина существования shrink_to_fit после всего?

Нет лучшего способа, но причиной существования shrink_to_fit является AFAICT, что иногда ваша программа может ощущать давление в памяти и это один из способов ее лечения. Не очень хороший способ, но все же.

НТН!

Ответ 3

Если да, то какой способ уменьшить емкость контейнера STL до его размера (по крайней мере, для std::vector).

"своп-трюк" обрезает вектор до требуемого точного размера (из более эффективного SQL):

vector<Person>(persons).swap(persons);

Особенно полезно, когда вектор пуст, чтобы освободить всю память:

vector<Person>().swap(persons);

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

Вот такой пример, когда мне действительно неинтересно работать (размер или скорость), но я действительно забочусь о точном использовании памяти.

И если есть лучший способ сжать контейнер, какая причина существования shrink_to_fit после всего?

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

Возможно, мы увидим Maybe_sort() в следующей версии.