关于我们 [英] About Vectors growth

问题描述

已经浏览过这本书：
C ++ Primer，第三版
By Stanley B. Lippman，JoséeLajoie

Had been going through the Book: C++ Primer, Third Edition By Stanley B. Lippman, Josée Lajoie

找到1个错误现在。
...在根据第6.3条给出的程序中，一个向量如何增长自己，这个程序错过了一个<在couts！
给出的程序是：

Found 1 mistake until now. ...In the program given under the Article 6.3 How a vector Grows Itself, this Program misses a "<" in the couts!! The program given is:

#include <vector>
#include <iostream>

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。

Now i corrected the problem. Later within that article the book says the following: " 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 是初始容量。
请解释。

---

Hence the initial capacity is increasing with the formula 2^N isn't it??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 invariable 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...

• 尺寸：1容量1 - 元素已复制，副本的每个元素的成本为0.


• size：2 capacity 2 - 当向量的容量增加到2时，必须复制第一个元素。每个元素的平均副本数为0.5


• size：3 capacity 4 - 当向量的容量增加到4时，必须复制前两个元素。每个元素的平均副本数为（2 + 1 + 0）/ 3 = 1。


• size：4 capacity 4 - 每个元素的平均副本数为（2 + 1 + 0 + 0）/ 4 = 3/4 = 0.75。


• size：5 capacity 8 - 每个元素的平均副本数为（3 + 2 + 1 + 1 + 0）/ 5 = 7/5 = 1.4
• 
  
• ...


• size：8 capacity 8 - 每个元素的平均副本数为（3 + 2 + 1 + 1 + 0 + 0 + 0 + 0 ）/ 8 = 7/8 = 0.875


• size：9 capacity 16 - 每个元素的平均副本数为（4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + / 9 = 15/9 = 1.67


• ...


• size 16 capacity 16-每个元素的平均副本数为15/16 = li>
  
• size 17 capacity 32 - 每个元素的平均副本数为31/17 = 1.82

• size: 1 capacity 1 - No elements have been copied, the cost per element for copies is 0.
• size: 2 capacity 2 - When the vector's capacity was increased to 2, the first element had to be copied. Average copies per element is 0.5
• size: 3 capacity 4 - When the vector's capacity was increased to 4, the first two elements had to be copied. Average copies per element is (2 + 1 + 0) / 3 = 1.
• size: 4 capacity 4 - Average copies per element is (2 + 1 + 0 + 0) / 4 = 3 / 4 = 0.75.
• size: 5 capacity 8 - Average copies per element is (3 + 2 + 1 + 1 + 0) / 5 = 7 / 5 = 1.4
• ...
• size: 8 capacity 8 - Average copies per element is (3 + 2 + 1 + 1 + 0 + 0 + 0 + 0) / 8 = 7 / 8 = 0.875
• size: 9 capacity 16 - Average copies per element is (4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0) / 9 = 15 / 9 = 1.67
• ...
• size 16 capacity 16 - Average copies per element is 15 / 16 = 0.938
• size 17 capacity 32 - Average copies per element is 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.

这篇关于关于我们的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！