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

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

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

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

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

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

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

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

18

Решение

Имеют ли место аргументы в цитате?

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

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

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

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

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

Хотя вы можете достичь того же самого внешне, этот интерфейс упрощает работу. Эквивалентно shrink_to_fit в C ++ 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 … это, вероятно, не то, что вы хотите писать каждый раз, когда хотите эту операцию.

14

Другие решения

  • Будут ли аргументы верны?

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

  1. Или shrink_to_fit ничего не делает (…)

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

  2. (…) или это дает вам проблемы с локальностью кэша

    В том случае, если shrink_to_fit является не реализован как неактивный, вы должны выделить новый базовый контейнер с емкостью 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, если он не может сжаться на месте, либо оставит память в одиночку (безоперационный случай), либо сделает побитовое копирование (и упустит возможность перенастройки указателей и т. д., которые дали бы надлежащие конструкторы копирования / перемещения C ++).

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

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

  3. и это O (N)

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

  4. обычно дешевле просто оставить слабину в памяти

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

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

Правильный путь еще shrink_to_fit… вам просто не нужно полагаться на это или очень хорошо знать свою реализацию!

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

Нет лучшего способа, но причина существования shrink_to_fit УТВЕРЖДАЕТ, что иногда ваша программа может чувствовать нехватку памяти, и это один из способов лечения. Не очень хороший способ, но все же.

НТН!

14

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

«Трюк обмена» обрезает вектор до требуемого размера (из более эффективного SQL):

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

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

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

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

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

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

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

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

1
Источник
По вопросам рекламы [email protected]
Web-Answers © 2025 Наверх