std::vector 的容量会减少吗？

Question

C++14 final working draft 对 std::vector 发表以下评论：

Storage management is handled automatically, though hints can be given to improve efficiency.

The storage of the vector is handled automatically, being expanded and contracted as needed.

C++'s std::vector and Rust's std::vec::Vec are implementations of dynamic arrays

所以我认为当一个向量的容量远大于它的大小时，它应该自动减少它的容量。我写了下面的代码来检查我的假设：

#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

如果您的实施中的 std::vector::shrink_to_fit() 没有达到您想要实现的目标（因为它只是提出 非绑定 减少矢量容量的请求），你可以考虑在你的向量上应用 swap-to-fit idiom 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().

，则可能会出现这种情况

Answer 2

取决于在什么操作下。如果你包括所有这些，那么是的。

参见 [vector.capacity]p9 (shrink_to_fit):

Remarks: shrink_to_fit is a non-binding request to reduce capacity() to size(). [ Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note ] ...

和[vector.capacity]p10 (swap):

Effects: Exchanges the contents and capacity() of *this with that of x.

换句话说，shrink_to_fit()，你可能会减少容量。使用 swap()，只要您能够用更少的 capacity() 创建另一个 vector，您一定会减少您的 capacity() 如果你 swap() 它们（但请注意 "original" 容量，即现在另一个对象的容量，本身并没有减少）。

关于以下方面的快速说明：

So I think that a vector should reduce its capacity when its capacity is much larger than its size. I wrote the following code to check my assumption:

为了减少 capacity()，实现需要（通常）分配内存（和 move/copy 元素并释放原始存储），这是一个非常昂贵的操作，没有人想要擦除元素时。

最重要的是，如果您的程序再次到达其新的 capacity()（这很可能，因为您之前已经这样做过），则必须再次重复该过程。

Answer 3

So I think that a vector should reduce its capacity when its capacity is much larger than its size.

首先，该标准必须指定 "capacity is much larger than its size" 的含义。这将限制当前实现对重新分配策略的选择。

其次，如果减少容量需要重新分配并移动所有剩余的元素。这意味着所有迭代器可能会因擦除而失效，这限制了安全使用。

目前，擦除状态

Invalidates iterators and references at or after the point of the erase, including the end() iterator.

第三，向量再次达到其高容量水位线的可能性与它长时间保持较小容量的可能性一样。

对于一些有效的场景，您可能会使使用情况变得更糟，因为释放大量分配的可疑好处。现代虚拟内存系统可以很好地处理旧分配，这些分配的保留时间严格长于 neccecary。

So are there some conditions to trigger the reduction of its capacity?

是的，shrink_to_fit 是明确要求 做你想做的事。如果您确实希望它重新分配到更小的尺寸，您可以提出要求。其他会受到 shinks 伤害的用法不受影响。

std::vector 的容量会减少吗？

Will a std::vector's capacity ever be reduced?

c++

vector

std

stdvector

c++-standard-library