vector扩容原理说明_yangshiziping的博客-CSDN博客_vector扩容
扩容原理概述
- 新增元素:Vector通过一个连续的数组存放元素,如果集合已满,在新增数据的时候,就要分配一块更大的内存,将原来的数据复制过来,释放之前的内存,在插入新增的元素;
- 对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了 ;
- 初始时刻vector的capacity为0,塞入第一个元素后capacity增加为1;
- 不同的编译器实现的扩容方式不一样,VS2015中以1.5倍扩容,GCC以2倍扩容。
总结
vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度,相对于增长指定大小的O(n)时间复杂度更好。
为了防止申请内存的浪费,现在使用较多的有2倍与1.5倍的增长方式,而1.5倍的增长方式可以更好的实现对内存的重复利用。
参考
另外要注意:vector 容器的容量(用 capacity 表示),指的是在不分配更多内存的情况下,容器可以保存的最多元素个数;而 vector 容器的大小(用 size 表示),指的是它实际所包含的元素个数。
原文链接: https://www.cnblogs.com/nntzhc/p/14072437.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/205643
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!