std::vector 的容量如何自动增长？费率是多少？

Question

我一直在读这本书： C++ Primer，第三版 作者：Stanley B. Lippman、Josée Lajoie，在第 6.3 条向量如何自行增长给出的程序中发现了 1 个错误，该程序错过了“ <”在 cout 中：

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> ivec;
    cout < "ivec: size: " < ivec.size() < " capacity: "  < ivec.capacity() < endl;
    
    for (int ix = 0; ix < 24; ++ix) {
        ivec.push_back(ix);
        cout < "ivec: size: " < ivec.size()
        < " capacity: "  < ivec.capacity() < endl;
    }    
}

在那篇文章的后面：

“在 Rogue Wave 实施下，尺寸和容量 定义后的 ivec 均为 0。插入第一个元素时， 然而，ivec 的容量为 256，大小为 1。"

但是，在更正和运行代码时，我得到以下输出：

---

ivec: size: 0 capacity: 0
ivec[0]=0 ivec: size: 1 capacity: 1
ivec[1]=1 ivec: size: 2 capacity: 2
ivec[2]=2 ivec: size: 3 capacity: 4
ivec[3]=3 ivec: size: 4 capacity: 4
ivec[4]=4 ivec: size: 5 capacity: 8
ivec[5]=5 ivec: size: 6 capacity: 8
ivec[6]=6 ivec: size: 7 capacity: 8
ivec[7]=7 ivec: size: 8 capacity: 8
ivec[8]=8 ivec: size: 9 capacity: 16
ivec[9]=9 ivec: size: 10 capacity: 16
ivec[10]=10 ivec: size: 11 capacity: 16
ivec[11]=11 ivec: size: 12 capacity: 16
ivec[12]=12 ivec: size: 13 capacity: 16
ivec[13]=13 ivec: size: 14 capacity: 16
ivec[14]=14 ivec: size: 15 capacity: 16
ivec[15]=15 ivec: size: 16 capacity: 16
ivec[16]=16 ivec: size: 17 capacity: 32
ivec[17]=17 ivec: size: 18 capacity: 32
ivec[18]=18 ivec: size: 19 capacity: 32
ivec[19]=19 ivec: size: 20 capacity: 32
ivec[20]=20 ivec: size: 21 capacity: 32
ivec[21]=21 ivec: size: 22 capacity: 32
ivec[22]=22 ivec: size: 23 capacity: 32
ivec[23]=23 ivec: size: 24 capacity: 32

---

容量是否随着公式 2^N 增加，其中 N< /code> 是初始容量吗？请解释一下。

Answer 1

标准要求向量容量增长的速率是指数级的（恕我直言，这是过度规范的）。标准指定这一点是为了满足 push_back 操作的摊销恒定时间要求。 摊销恒定时间意味着什么以及指数增长如何实现这一点很有趣。

每次向量容量增加时，都需要复制元素。如果您在向量的生命周期内“摊销”此成本，那么事实证明，如果您以指数因子增加容量，则最终会得到摊销的恒定成本。

这可能看起来有点奇怪，所以让我向您解释一下这是如何工作的...

• size: 1capacity 1 - 没有复制任何元素，每个元素的副本成本为 0。
• size: 2capacity 2 - 当向量的容量如果增加到 2，则必须复制第一个元素。每个元素的平均副本数为 0.5
• 大小：3 容量 4 - 当向量的容量增加到 4 时，必须复制前两个元素。每个元素的平均副本为 (2 + 1 + 0) / 3 = 1。
• 大小：4 容量 4 - 每个元素的平均副本为 (2 + 1 + 0 + 0) / 4 = 3 / 4 = 0.75。
• 大小：5 容量 8 - 每个元素的平均副本数为 (3 + 2 + 1 + 1 + 0) / 5 = 7 / 5 = 1.4
• ...
• 大小：8 容量 8 - 每个元素的平均副本数为 (3 + 2 + 1 + 1 + 0 + 0 + 0 + 0) / 8 = 7 / 8 = 0.875
• 大小：9 容量 16 - 每个元素的平均副本为 (4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0) / 9 = 15 / 9 = 1.67
• ...
• size 16 容量 16 - 每个元素的平均副本数为 15 / 16 = 0.938
• size 17 容量 32 - 每个元素的平均副本数为 31 / 17 = 1.82

正如你所看到的，每次容量跳跃时，副本数量增加了数组先前的大小。但由于在容量再次跳跃之前数组的大小必须加倍，因此每个元素的副本数始终小于 2。

如果将容量增加 1.5 * N 而不是 2 * N，则最终会得到一个非常大的值。类似的效果，除了每个元素的副本上限会更高（我认为是 3）。

我怀疑实现会选择 1.5 而不是 2，这既是为了节省一点空间，也是因为 1.5 更接近 黄金比例。我有一个直觉（目前没有任何硬数据支持），符合黄金比例的增长率（因为它与斐波那契数列的关系）将被证明是现实世界负载最有效的增长率最大限度地减少使用的额外空间和时间。

Answer 2

为了能够在 std::vector 末尾提供摊销常数时间插入，实现必须将向量的大小（需要时）增加一个因子 < code>K>1 (*)，这样当尝试附加到已满的大小为 N 的向量时，向量将增长为 K*N >。

不同的实现使用不同的常量K来提供不同的好处，特别是大多数实现都采用K = 2或K = 1.5。较高的 K 会使其速度更快，因为它需要的增长更少，但同时也会对内存产生更大的影响。例如，在 gcc K = 2 中，而在 VS (Dinkumware) K = 1.5 中。

(*) 如果向量以恒定量增长，则 push_back 的复杂度将变为线性，而不是摊销常量。例如，如果向量在需要时增长 10 个元素，则增长成本（将所有元素复制到新的内存地址）将为 O( N / 10 ) （每 10 个元素，移动所有元素）或O(N)。

Answer 3

只是为了在 vector::push_back 上添加一些时间复杂度的数学证明，假设向量的大小为 n，我们在这里关心的是发生的副本数量，所以到目前为止，说y，请注意每次增长向量时都会发生复制。

增长因子 K

  y = K^1 + K^2 + K^3 ... K^log(K, n)
K*y =     + K^2 + K^3 ... K^log(K, n) + K*K^log(K, n)

K*y-y = K*K^log(K, n) - K
y = K(n-1)/(K-1) = (K/(K-1))(n-1)

T(n) = y/n = (K/(K-1)) * (n-1)/n < K/(K-1) = O(1)

K/(K-1) 是一个常数，看看最常见的情况：

• K=2, T( n) = 2/(2-1) = 2
• K=1.5, T(n) = 1.5/(1.5-1) = 3

实际上在不同的实现中选择 K 为 1.5 或 2 是有原因的，请参见此< a href="https://www.desmos.com/calculator/brtkj6myfk" rel="nofollow noreferrer">图表：当 T(n) 达到最小值时K 约为 2，使用较大的 K 并没有多大好处，但代价是分配更多内存

按恒定数量增长 C

y = C + 2*C + 3*C + 4*C +  ... (n/C) * C
  = C(1+2+3+...+n/C), say m = n/C
  = C*(m*(m-1)/2)
  = n(m-1)/2

T(n) = y/n = (n(m-1)/2)/n = (m-1)/2 = n/2C - 1/2 = O(n)

正如我们所看到的，它是班轮

Answer 4

vector 的容量完全依赖于实现，没有人能知道它是如何增长的。

Answer 5

您正在使用“Rogue Wave”实施吗？

容量如何增长取决于实施。你的使用 2^N。

Answer 6

是的，每次超出时容量都会增加一倍。这是依赖于实现的。

Answer 7

在推回元素之前，向量检查大小是否大于其容量，如下所示，

我将用保留函数解释它：

void    push_back(const value_type &val)   //push_back actual prototype
{
   if (size_type < 10)
        reserve(size_type + 1);
   else if (size_type > (_capacity / 4 * 3))
        reserve(_capacity + (this->_capacity / 4));
   //then the vector get filled with value
}

size_type ：向量大小。

_capacity：向量_capacity。