关于vector增长
已经通过书籍：C ++入门书，第三版由斯坦利·李普曼，何塞·拉霍伊
直到现在发现了一个错误。 …在第6.3节中介绍的程序如何生成一个载体，这个程序错过了一个“<”在couts！ 给出的scheme是：
#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容量的增长速度取决于实现。 实现几乎总是select指数增长，以便满足push_back操作的分期恒定时间要求。 恒定时间摊销意味着什么，指数增长如何实现这一点很有意思。
每当一个向量的容量增长时，这些元素都需要被复制。 如果您在向量的整个生命周期中“摊销”这个成本，事实certificate，如果您通过指数因子增加产能，则最终会得到摊销的固定成本。
这可能看起来有点奇怪，所以让我解释一下这是如何工作的…
- 大小：1个容量1 – 没有元素被复制，每个元素的复制成本是0。
- 大小：2容量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
- …
- 大小16容量16 – 每个元素的平均拷贝数是15/16 = 0.938
- 大小17容量32 – 每个元素的平均份数是31/17 = 1.82
正如你所看到的，每次容量跳跃时，拷贝的数量都会增加上一个数组的大小。 但是，由于在容量再次跳跃之前，数组的大小必须加倍，所以每个元素的拷贝数始终小于2。
如果你的容量增加了1.5 * N而不是2 * N，那么除非每个元素的拷贝上限会更高（我认为它会是3），否则结果会非常相似。
我怀疑一个实现会select1.5或者2以节省一点空间，但是也因为1.5接近黄金比例 。 我有一个直觉（目前没有任何硬数据支持），与黄金比例（因为它与斐波纳契数列的关系）一致的增长率将被certificate是真实世界负荷的最有效的增长率在最大限度地减less额外的空间和时间。
为了能够在std::vector的末尾提供缓冲区的常量插入，实现必须通过一个因子K>1 （*）来增加vector的大小（当需要的时候），这样当试图追加到大小为N的vector满，vector增长为K*N
不同的实现使用不同的常量K来提供不同的好处，特别是大多数实现的K = 2或K = 1.5 。 更高的K会使它更快，因为它需要更less的增长 ，但同时会有更大的记忆效应。 例如，在海湾合作委员会K = 2 ，而在VS（Dinkumware） K = 1.5 。
（*）如果vector增长了一个常量，那么push_back的复杂度将变成线性的，而不是摊销常数 。 例如，如果向量在需要时增加了10个元素，则增长的成本（全部元素复制到新的存储器地址）将是O( N / 10 ) （每10个元素，移动所有东西）或O( N ) 。
你在使用“Rogue Wave”实现吗？
容量如何增长取决于实施。 你用2 ^ N。
vector的容量完全依赖于实现，没有人能说出它是如何增长的。
是的，每超过一次，容量就会翻倍。 这是依赖于实现的。
