一直在读这本书:
C++ Primer，第三版
斯坦利·利普曼(Stanley B. Lippman)，何塞·拉乔(JoséeLajoie)
到现在为止发现1个错误。
...在根据第6.3条给出的程序自身如何增长的程序中，该程序错过了提示中的“给出的程序是:
#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。”
但是，在更正和运行代码后，我得到以下输出:
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 是初始容量。
请解释。
最佳答案
vector 容量增长的速度取决于实现方式。实现几乎总是选择指数增长，以满足push_back操作的摊销不变时间要求。固定时间摊销意味着什么，以及指数增长如何实现这一点很有趣。
每当 vector 容量增加时，都需要复制元素。如果您在 vector 的整个生命周期中“摊销”此成本，那么事实证明，如果将容量增加一个指数因数，最终将得到摊销的恒定成本。
这似乎有点奇怪，所以让我向您解释这是如何工作的...
如您所见，每当容量增加时，副本数就会增加以前的阵列大小。但是，由于阵列必须在容量再次翻倍之前将其大小加倍，因此每个元素的副本数始终保持小于2。
如果将容量增加1.5 * N而不是2 * N，则会得到非常相似的效果，只是每个元素的副本上限更高(我认为应该是3)。
我怀疑一个实现会选择1.5而不是2来节省一些空间，而且还因为1.5更接近golden ratio。我有一个直觉(目前还没有任何硬数据支持)，与黄金比率一致的增长率(由于其与斐波那契数列的关系)将被证明是现实负载中最有效的增长率在最大限度地减少使用的额外空间和时间方面。
关于c++ - 关于媒介增长，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5232198/