关于vector的扩容机制

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
606
文章
12
评论
2020年1月20日11:16:17 评论

往vector中添加元素时,如果空间不够将会导致扩容。vector有两个属性:size和capacity。size表示已经使用的数据容量,capacity表示数组的实际容量,包含已使用的和未使用的。

vector扩容规则:

  1. 当数组大小不够容纳新增元素时,开辟更大的内存空间,把旧空间上的数据复制过来,然后在新空间中继续增加。
  2. 新的更大的内存空间,一般是当前空间的1.5倍或者2倍,这个1.5或者2被称为扩容因子,不同系统实现扩容因子也不同。

注意,扩容会导致迭代器失效。

在VS2017中,vector的扩容因子是1.5。可以追踪push_back的实现:

函数中先通过_Has_unused_capacity函数判断是否有还有未使用的空间,如果有未使用的空间,直接在未使用的空间上新增。如果没有未使用的空间了,就需要执行_Emplace_reallocate重新扩容:

函数中先判断新长度,然后继续调用_Calculate_growth扩容,这个函数才是真正用来扩容的函数。

忽略过其他判断逻辑,_Calculate_growth的实现为:

新的扩容大小等于当前容量再加上当前容量的一半,即按照1.5倍扩容。

在GCC的实现中,vector扩容是2倍扩容的。

1.5倍扩容和2倍扩容的区别

  1. 扩容因子越大,需要分配的新内存空间越多,越耗时。空闲空间较多,内存利用率低。
  2. 扩容因子越小,需要再分配的可能性就更高,多次扩容耗时。空闲空间较少,内存利用率高。

因此,小规模数组,添加元素不频繁的,建议使用扩容因子更小的。当数据规模越大,插入更频繁,大扩容因子更适合。

示例代码

以上代码通过循环插入了十个元素,并打印出每次插入后vector的容量:

能看出的增长规律为:0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 9 -> 13,而同样的代码通过G++编译后的输出结果为:

马谦马谦马谦
  • 本文由 发表于 2020年1月20日11:16:17
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/code/c-cpp/vector-expansion-mechanism.html
vector中emplace_back方法的用途 C/C++

vector中emplace_back方法的用途

在写代码的过程中,CLion提醒我把push_back方法替换成emplace_back方法: 代码中我的想法是使用vector创建一个二维数组,并提前分配好空间,避免后序频繁扩容增加时间复杂度。 e...
STL中的迭代器失效 C/C++

STL中的迭代器失效

一、迭代器失效 向容器添加或者删除元素可能会导致指向容器的指针、引用或者迭代器失效。使用已经失效的指针、引用或者迭代器将会导致程序出现异常,编码过程中一定要时刻注意迭代器失效的场景。 例如,以vect...
vector中reserve和resize的区别 C/C++

vector中reserve和resize的区别

reserve方法用来给vector预留空间,预留的空间只会改变capacity的大小,不会改变size大小。resize方法表示重新调整数组大小,capacity和size都会改变。 使用reser...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: