c++ - 当我们 push_back 元素时 std::vector 什么时候扩大自己？

Question

根据下面的测试，似乎是一个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();
    }
}

new capacity: 1 new size: 1 ratio: 1.#INF
new capacity: 2 new size: 2 ratio: 2
new capacity: 3 new size: 3 ratio: 1.5
new capacity: 4 new size: 4 ratio: 1.33333
new capacity: 6 new size: 5 ratio: 1.5
new capacity: 9 new size: 7 ratio: 1.5
new capacity: 13 new size: 10 ratio: 1.44444
new capacity: 19 new size: 14 ratio: 1.46154
new capacity: 28 new size: 20 ratio: 1.47368
new capacity: 42 new size: 29 ratio: 1.5
new capacity: 63 new size: 43 ratio: 1.5
new capacity: 94 new size: 64 ratio: 1.49206
new capacity: 141 new size: 95 ratio: 1.5
new capacity: 211 new size: 142 ratio: 1.49645
...
new capacity: 466609 new size: 311074 ratio: 1.5
new capacity: 699913 new size: 466610 ratio: 1.5
new capacity: 1049869 new size: 699914 ratio: 1.5

---

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

Answer 1

喜欢链接问题的答案What is the ideal growth rate for a dynamically allocated array?显示，总是将分配的大小加倍会导致释放的内存总是只是对于下一次分配来说太小了。 vector 将在堆中“游荡”，留下许多碎片。

最大化重用的“最佳”重新分配大小结果是 golden ratio这是 1.61803...

但是，1.5 很多更容易计算为 capacity() + capacity()/2 并且在实践中足够接近。这使其成为现有实现​​的热门选择。