当我们push_back元素时，std :: vector何时会自我扩大? [英] When does a std::vector enlarge itself when we push_back elements?
问题描述
根据以下测试，看来 std :: vector< int> 以此方式增加了容量:
According to the following test, it seems that a std::vector<int> increases its capacity in this way:
-
当我们
push_back()并且容量已满时(即v.size()== v.capacity())，就会发生这种情况)，必须注意的是
it happens when we
push_back()and the capacity is already full (i.e.v.size() == v.capacity()), it has to be noted that it doesn't happen a little bit before
容量增加到以前容量的1.5倍
问题:为什么要使用1.5因子?是否依赖于实现?最佳吗?
Question: why this 1.5 factor? Is it implementation-dependent? Is it optimal?
还有，在这段代码中，有没有一种方法可以分析何时发生了真正的重新分配?(有时可以在不移动阵列第一部分的情况下增加容量)
Also, is there a way to analyze, in this code, when exactly a reallocation happens? (sometimes maybe the capacity can be increased without moving the first part of the array)
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
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
Note: I'm using VC++ 2013
推荐答案
Like answer to the linked question What is the ideal growth rate for a dynamically allocated array? shows, always doubling the allocated size has the problem that the free'd memory will always be just too small for the next allocation. The vector will "wander" through the heap, leaving lots of fragments behind.
最大程度地重用的最佳"重新分配大小被证明是黄金比例是1.61803 ...
The "optimal" reallocation size, that maximizes reuse, turns out to be the golden ratio which is 1.61803...
但是， capacity()+ Capacity()/2 可以很容易地计算出1.5，并且在实践中足够接近.这使得它成为现有实现的流行选择.
However, 1.5 is a lot easier to calculate as capacity() + capacity() / 2 and is close enough in practice. That makes it a popular choice for existing implementations.
这篇关于当我们push_back元素时，std :: vector何时会自我扩大?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
