C++vector和list区别及应用

一、平时做项目时vector和list都是经常用到的但是他们具体有什么区别呢底层实现又是什么原理呢下面做详细介绍。
二、概念
1Vector 的底层结构是动态顺序表在内存中是一段连续的空间。
连续存储的容器动态数组在堆上分配空间。
底层实现数组
两倍容量增长
vector 增加插入新元素时如果未超过当时的容量则还有剩余空间那么直接添加到最后插入指定位置然后调整迭代器。如果没有剩余空间了则会重新配置原有元素个数的两倍空间然后将原空间元素通过复制的方式初始化新空间再向新空间增加元素最后析构并释放原空间之前的迭代器会失效。
访问vector支持随机访问可以利用下标精准定位到一个元素上。
插入和删除vector任意位置插入和删除的效率低因为它每插入一个元素尾插除外都需要搬移数据而且插入还有可能要增容这样一来还要开辟新空间拷贝元素是旧空间效率会更低。
插入在最后插入空间够很快
在最后插入空间不够需要内存申请和释放以及对之前数据进行拷贝。
在中间插入空间够内存拷贝
在中间插入空间不够需要内存申请和释放以及对之前数据进行拷贝。
删除在最后删除很快
在中间删除内存拷贝
空间利用率vector由于底层是动态顺序表在内存中是一段连续的空间所以不容易造成内存碎片空寂爱你利用率高缓存利用率高。
适用场景经常随机访问且不经常对非尾节点进行插入删除。
2List 的底层结构是带头节点的双向循环链表在内存中不是一段连续的空间。
动态链表在堆上分配空间每插入一个元数都会分配空间每删除一个元素都会释放空间。
底层双向链表
访问list不支持随机访问要想访问list中的某个元素只能是从前向后或从后向前依次遍历。
插入和删除list任意位置插入和删除的效率高他不需要搬移元素只需要改变插入或删除位置的前后两个节点的指向即可。
插入很快一般是常数开销
删除很快一般是常数开销
空间利用率list的底层节点动态开辟空间小结点容易造成内存碎片空间利用率低缓存利用率低。
适用场景经常插入删除大量数据
三、区别
1vector底层实现是数组list是双向 链表。
2vector支持随机访问list不支持。
3vector是顺序内存list不是。
4vector在中间节点进行插入删除会导致内存拷贝list不会。
5vector一次性分配好内存不够时才进行2倍扩容list每次插入新节点都会进行内存申请。
6vector随机访问性能好插入删除性能差list随机访问性能差插入删除性能好。
四、应用
vector拥有一段连续的内存空间因此支持随机访问如果需要高效的随即访问和数据存储而不在乎插入和删除的效率使用vector。
list拥有一段不连续的内存空间如果需要高效且大量的插入和删除而不关心随机访问则应使用list。
五、备注
昨天同事做dll封装时函数原型的形参是引用类型的vector par_vecvoid func(&par_vec)函数实现代码会给par_vec赋值。上位机调用的时候先声明了一个vector变量x_vec然后调用函数func并把X_vec传递给func。发现x_vec是返回的乱码的东西然而dll的函数并没有报错。deug调试进入dll源代码发现也没有报错并且正常赋值了par_vec。这是什么原因呢同事在vector变量赋值的时候直接采用的=的形式par_vec = temp_vec。我让他修改了代码改成
par_vec .assign(temp_vec.begin(), temp_vec.end());就解决了这个问题。原来par_vec .assign会先清空par_vec然后再把temp_vec的数据拷贝给par_vec。后面我让他测试先par_vec.clear();然后par_vec = temp_vec也解决了他的问题。看来=号不能随便使用如果传进的实参是需要被完全覆盖的一定要先清空该实参的内存数据。