Будет ли когда-нибудь уменьшена емкость std :: vector?

Question

C ++ 14 окончательный рабочий проект дает следующий комментарий о std::vector:

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

cppreference говорит:

Хранение вектора обрабатывается автоматически, расширяется и сокращается по мере необходимости.

И Запись в Википедии для динамического массива говорит:

C ++ std::vector и Rust std::vec::Vec являются реализациями динамических массивов

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> v = {};

  cout << "initialization" << endl;
  cout << "  capacity: " << v.capacity() << endl;
  cout << "  size: " << v.size() << endl;

  for (int i = 1; i <= 10000; i++) 
    v.push_back(i);

  cout << "after inserting a lot of elements" << endl;
  cout << "  capacity: " << v.capacity() << endl;
  cout << "  size: " << v.size() << endl;

  v.erase(v.begin() + 1, v.begin() + 10000);
  cout << "after erasing a lot of elements" << endl;
  cout << "  capacity: " << v.capacity() << endl;
  cout << "  size: " << v.size() << endl;

  v.push_back(9);

  cout << "after inserting another element" << endl;
  cout << "  capacity: " << v.capacity() << endl;
  cout << "  size: " << v.size() << endl;
}

Я использовал g++ -std=c++14 code.cc для компиляции кода.И выполнение приведенного a.out дает следующий вывод.Я использую macOS Mojave.

initialization
  capacity: 0
  size: 0
after inserting a lot of elements
  capacity: 16384
  size: 10000
after erasing a lot of elements
  capacity: 16384
  size: 1
after inserting another element
  capacity: 16384
  size: 2

Так что, похоже, std::vector не уменьшает свою емкость, даже если его емкость намного больше его размера.

Будет std::vectorкогда-нибудь уменьшать его емкость?
Так есть ли какие-то условия, чтобы вызвать снижение его емкости?

Answer 1

Зависит от того, под какими операциями.Если вы включите все из них, тогда да.

См. [Vector.capacity] p9 (shrink_to_fit):

Примечания : shrink_to_fit isнеобязательный запрос на уменьшение capacity() до size().[ Примечание : запрос не является обязательным для разрешения широты для оптимизаций, специфичных для реализации.- конечная нота ] ...

и [vector.capacity] p10 (swap):

Эффекты : Заменяет содержимое и capacity() из *this на x.

Другими словами, с shrink_to_fit() вы можете уменьшить емкость.С swap(), пока вы можете создать еще один vector с меньшим capacity(), вы гарантированно уменьшите ваш capacity(), если вы swap() их (но учтите, что«оригинальная» емкость, т. е. та, которая сейчас равна емкости другого объекта, сама по себе не уменьшается).

---

Краткое примечание относительно:

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

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

Кроме того, если ваша программа затем снова достигает своего нового capacity() (что, вероятно, потому что вы уже делали это раньше), процессдолжен быть повторен снова.

Answer 2

Так что я думаю, что вектор должен уменьшать свою емкость, когда его емкость намного больше, чем его размер.

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

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

В настоящее время состояния стирания

Делает недействительными итераторы и ссылки на или послеточка стирания, включая итератор end().

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

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

Так есть ли условия для запуска уменьшения его емкости?

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

Answer 3

Если std::vector::shrink_to_fit() в вашей реализации не делает того, чего вы хотите достичь (поскольку он просто делает необязательный запрос на уменьшение емкости вектора), вы можете рассмотреть возможность применения поменяйте местами идиома на вашем векторе v:

std::vector<int> v;

// ...

{
   std::vector<int> tmp(v); // create a copy of vector v
   tmp.swap(v);
   // vector tmp goes out of scope --> tmp is destroyed
}

Или просто как однострочный:

std::vector<int>(v).swap(v);

Эта идиомасостоит из создания временного векторного объекта, который состоит из элементов исходного вектора v, а затем замены , в результате чего получается временный исходный вектор v.

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