往 vector 中添加元素时,如果空间不够将会导致扩容。 vector 有两个属性:size 和 capacity 。 size 表示已经使用的数据容量,capacity 表示数组的实际容量,包含已使用的和未使用的。
vector 扩容规则:
- 当数组大小不够容纳新增元素时,开辟更大的内存空间,把旧空间上的数据复制过来,然后在新空间中继续增加。
- 新的更大的内存空间,一般是当前空间的 1.5 倍或者 2 倍,这个 1.5 或者 2 被称为扩容因子,不同系统实现扩容因子也不同。
注意,扩容会导致迭代器失效。
在 VS2017 中,vector 的扩容因子是 1.5 。可以追踪 push_back
的实现:
1 2 3 4 5 6 7 8 9 10 |
decltype(auto) emplace_back(_Valty&&... _Val) { // insert by perfectly forwarding into element at end, provide strong guarantee if (_Has_unused_capacity()) { return (_Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...)); } _Ty& _Result = *_Emplace_reallocate(this->_Mylast(), _STD forward<_Valty>(_Val)...); // ... } |
函数中先通过_Has_unused_capacity
函数判断是否有还有未使用的空间,如果有未使用的空间,直接在未使用的空间上新增。如果没有未使用的空间了,就需要执行_Emplace_reallocate
重新扩容:
1 2 3 4 5 6 7 |
pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) { // .. const size_type _Newsize = _Oldsize + 1; const size_type _Newcapacity = _Calculate_growth(_Newsize); // .. } |
函数中先判断新长度,然后继续调用_Calculate_growth
扩容,这个函数才是真正用来扩容的函数。
忽略过其他判断逻辑,_Calculate_growth
的实现为:
1 2 3 4 5 6 |
size_type _Calculate_growth(const size_type _Newsize) const { // ... const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2; // ... } |
新的扩容大小等于当前容量再加上当前容量的一半,即按照 1.5 倍扩容。
在 GCC 的实现中,vector 扩容是 2 倍扩容的。
1.5 倍扩容和 2 倍扩容的区别
- 扩容因子越大,需要分配的新内存空间越多,越耗时。空闲空间较多,内存利用率低。
- 扩容因子越小,需要再分配的可能性就更高,多次扩容耗时。空闲空间较少,内存利用率高。
因此,小规模数组,添加元素不频繁的,建议使用扩容因子更小的。当数据规模越大,插入更频繁,大扩容因子更适合。
示例代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <vector> using namespace std; int main() { int i; vector<int> v; cout << v.capacity() << " "; for (i = 0; i < 10; i++) { v.push_back(1); cout << v.capacity() << " "; } return 0; } |
以上代码通过循环插入了十个元素,并打印出每次插入后 vector 的容量:
1 |
0 1 2 3 4 6 6 9 9 9 13 |
能看出的增长规律为:0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 9 -> 13
,而同样的代码通过 G++编译后的输出结果为:
1 |
0 1 2 4 4 8 8 8 8 16 16 |
评论