std::vector 的容量如何自动增长?费率是多少? [英] How does the capacity of std::vector grow automatically? What is the rate?

问题描述

我一直在阅读这本书:C++ Primer，第三版 作者:Stanley B. Lippman，Josée Lajoie，在第 6.3 条向量如何自我生长下给出的程序中发现了 1 个错误，该程序遗漏了一个";<<在 couts:

I had been going through the Book: C++ Primer, Third Edition By Stanley B. Lippman, Josée Lajoie, found 1 mistake in the program given under the Article 6.3 How a vector Grows Itself, this program missed a "<" in the couts:

#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."

"Under the Rogue Wave implementation, both the size and the capacity of ivec after its definition are 0. On inserting the first element, however, ivec's capacity is 256 and its size is 1."

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

But, on correcting and running the code i get the following output:

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 是初始容量?请解释.

---

Is the capacity increasing with the formula 2^N where N is the initial capacity? Please explain.

推荐答案

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

The rate at which the capacity of a vector grows is implementation dependent. Implementations almost invariably choose exponential growth, in order to meet the amortized constant time requirement for the push_back operation. What amortized constant time means and how exponential growth achieves this is interesting.

每次增加向量的容量时，都需要复制元素.如果您在向量的整个生命周期内摊销"此成本，结果是如果您以指数因子增加容量，您最终会得到摊销不变的成本.

Every time a vector's capacity is grown the elements need to be copied. If you 'amortize' this cost out over the lifetime of the vector, it turns out that if you increase the capacity by an exponential factor you end up with an amortized constant cost.

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

This probably seems a bit odd, so let me explain to you how this works...

• 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
• size 17 容量 32 - 每个元素的平均副本数为 31/17 = 1.82

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

As you can see, every time the capacity jumps, the number of copies goes up by the previous size of the array. But because the array has to double in size before the capacity jumps again, the number of copies per element always stays less than 2.

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

If you increased the capacity by 1.5 * N instead of by 2 * N, you would end up with a very similar effect, except the upper bound on the copies per element would be higher (I think it would be 3).

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

I suspect an implementation would choose 1.5 over 2 both to save a bit of space, but also because 1.5 is closer to the golden ratio. I have an intuition (that is currently not backed up by any hard data) that a growth rate in line with the golden ratio (because of its relationship to the fibonacci sequence) will prove to be the most efficient growth rate for real-world loads in terms of minimizing both extra space used and time.

这篇关于std::vector 的容量如何自动增长?费率是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！