当我们 push_back 元素时，std::vector 什么时候放大？

Question

根据下面的测试，a似乎是通过std::vector<int>这种方式增加了自己的容量：

• 它发生在我们push_back() 和容量已经满时（即v.size() == v.capacity()），必须注意它不会发生在之前

• 容量增加到原来容量的1.5倍

问题：为什么是这个 1.5 因子？它是否依赖于实现？它是最优的吗？

另外，有没有办法在这段代码中分析重新分配的确切时间？（有时也许可以在不移动阵列的第一部分的情况下增加容量）

---

vector<int> v;
int previouscapacity = 0;
for (unsigned int i = 0; i < 1000000; i++)
{
    v.push_back(i);
    if (v.capacity() != previouscapacity)
    {
        wcout << L"new capacity: " << v.capacity() << L" new size: " << v.size() << L" ratio: " << ((float) v.capacity()) / previouscapacity << '\n';
        previouscapacity = v.capacity();
    }
}

新容量：1 新大小：1 比率：1.#INF
新容量：2 新大小：2 比率：2
新容量：3 新大小：3 比率：1.5
新容量：4 新大小：4 比率：1.33333
新容量： 6 新尺寸：5 比例：1.5
新容量：9 新尺寸：7 比例：1.5
新容量：13 新尺寸：10 比例：1.44444
新容量：19 新尺寸：14 比例：1.46154
新容量：28 新尺寸：20 比例：1.47368
新容量：42 新尺寸：29 比例：1.5
新容量：63 新尺寸：43 比例：1.5
新容量：94 新尺寸：64 比例：1.49206
新容量：141 新尺寸：95 比例：1.5
新容量：211新尺寸：142 比例：1.49645
...
新容量：466609 新容量：311074 比率：1.5
新容量：699913 新容量：466610 比率：1.5
新容量：1049869 新容量：699914 比率：1.5

---

注意：我使用的是 VC++ 2013

Answer 1

就像对链接问题的回答一样，动态分配的数组的理想增长率是多少？表演，总是加倍分配的大小有问题的free'd记忆将永远只是太小的下一次分配。该向量将在堆中“徘徊”，留下大量碎片。

最大化重用的“最佳”重新分配大小结果是黄金比例，即 1.61803...

然而，1.5是很多容易计算的capacity() + capacity() / 2，并在实践中是足够接近。这使其成为现有实现的流行选择。