Question

C++ vector和list的区别

Answer 1

主要区别：
1 是否支持随机访问：
vector支持下标直接访问，理论上事件复杂度为O(1)；list无法随机访问中间的元素，只能从两头开始遍历，逐个获取。
2 内存分布：
vector可以看成是内存连续的，list的内存则由指针连接而成；vector每次扩大内存都会开辟额外的内存来“准备新元素插入”；list在两端增删元素的时间复杂度为O(1)，vector为O(n)。从数据结构与算法的角度更细致的对比如下：
时间复杂度： vector list
查找： O(1) O(n)
新增： O(n) O(1)
删除： O(n) O(n)
空间复杂度：
连续内存分配与拷贝 不连续内存分配
适用场景：
对查找要求高的场景 对顺序没有要求的序列
数据不频繁增删 数据频繁增删

Answer 2

你好。
vector和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。
list就是数据结构中的双向链表，因此它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。
如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector；
如果你需要大量的插入和删除，而不关心随即存取，则应使用list。
希望这样解释你可以较好理解。