这个问题的本质还是在问顺序表和链表的区别
底层结构不同
| vector容器 |
list容器 |
| 一段连续的空间 |
带头结点的双向循环链表 |
元素访问方式
| vector容器 |
list容器 |
| 支持随机访问—O(1) |
不支持随机访问—O(N) |
| 需要扩容 |
不需要扩容 |
| 任意位置插入元素----O(N)–搬移元素 |
O(1) |
迭代器不同
| vector容器 |
list容器 |
| 类型:原生态的指针 |
对原生态指针进行封装 |
| 失效的场景:导致底层空间改变操作 |
当前迭代器对应的结点没有了 |
| erase(it) |
erase(it) |
空间
| vector容器 |
list容器 |
| 需要扩容 |
不需要扩容 |
| 不扩容的话空间利用率高，扩容不一定 |
不扩容的话空间利用率低，扩容不一定 |
| vector如果不new是在栈上的 |
list结点是new出来的，频繁向系统申请小的内存块，可能会存在内存碎片。new的底层是malloc，可能会有额外空间的浪费 |
缓存利用率
| vector容器 |
list容器 |
| 比如上面的图，cpu加载1时有可能把12345全部加载到缓存中，这样效率更高，底层连续 |
而list加载时，一次性加载可能就一两个元素，底层不连续 |
应用场景
| vector容器 |
list容器 |
| 高效存储—访问 |
任意位置插入和删除操作比较多 |
接口不同
vector没有push_front,和pop_front，因为它头插和头删的效率比较低
