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

Ответ 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() в следующей версии.