34

我一直在浏览 Book: C++ Primer, Third Edition By Stanley B. Lippman, Josée Lajoie,在 s 下给出的程序中发现 1 个错误,该Article 6.3 How a vector Grows Itself程序在 s 中遗漏了一个“<” 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请解释。

4

6 回答 6

89

向量容量增长的速度取决于实现。实现几乎总是选择指数增长,以满足操作的摊销常数时间要求push_back摊销恒定时间意味着什么以及指数增长如何实现这一点很有趣。

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

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

  • size: 1 capacity 1 - 没有元素被复制,每个元素的复制成本为 0。
  • size: 2 capacity 2 - 当向量的容量增加到 2 时,必须复制第一个元素。每个元素的平均副本数为 0.5
  • size: 3 capacity 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
  • ...
  • 大小 16 容量 16 - 每个元素的平均副本数为 15 / 16 = 0.938
  • 大小 17 容量 32 - 每个元素的平均副本数为 31 / 17 = 1.82

如您所见,每次容量跳跃时,副本数都会增加先前的数组大小。但是由于数组在容量再次跳跃之前必须翻倍,因此每个元素的副本数始终保持小于 2。

如果你将容量增加 1.5 * N 而不是 2 * N,你最终会得到非常相似的效果,除了每个元素的副本上限会更高(我认为它会是 3)。

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

于 2011-03-08T12:19:15.340 回答
13

为了能够在 的末尾提供分摊的常数时间std::vector插入,实现必须将向量的大小(在需要时)增加一个因子K>1(*),以便在尝试附加到一个大小N为已满的向量时,向量增长为K*N

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

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

于 2011-03-08T12:30:56.150 回答
2

只是为了在 上添加一些时间复杂度的数学证明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 是有原因的,请参见此T(n)当在 2 左右时达到最小值K,使用更大的 并没有太大的好处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)

如我们所见,它是班轮

于 2019-04-04T20:56:04.633 回答
1

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

于 2011-03-08T12:09:25.233 回答
1

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

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

于 2011-03-08T12:09:52.117 回答
0

是的,每次超过容量都会翻倍。这取决于实现。

于 2011-03-08T12:09:54.693 回答