C++ 面试八股文：list、vector、deque 比较

List 封装了链表, Vector 封装了数组, list 和 vector 得最主要的区别在于 vector 使用连续内存存储的，他支持 [] 运算符，而 list 是以链表形式实现的，不支持 [] 。

Vector对于随机访问的速度很快，但是对于插入尤其是在头部插入元素速度很慢，在尾部插入速度很快。

List对于随机访问速度慢得多，因为可能要遍历整个链表才能做到，但是对于插入就快的多了，不需要拷贝和移动数据，只需要改变指针的指向就可以了。

另外对于新添加的元素，Vector 有一套算法，而 List 可以任意加入。

Map, Set 属于标准关联容器，使用了非常高效的平衡检索二叉树：红黑树，他的插入删除效率比其他序列容器高是因为不需要做内存拷贝和内存移动，而直接替换指向节点的指针即可。

Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在于Set只含有Key，而Map有一个Key和Key所对应的Value两个元素。

Map和Hash_Map的区别是Hash_Map使用了Hash算法来加快查找过程，但是需要更多的内存来存放这些Hash桶元素，因此可以算得上是采用空间来换取时间策略。

vector

向量相当于一个数组，在内存中分配一块连续的内存空间进行存储。支持不指定 vector 大小的存储。

STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy()函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。

通常此默认的内存分配能完成大部分情况下的存储。  

优点：

• 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push_back() pop_back()

• 随机访问方便，即支持[ ]操作符和vector.at()

• 节省空间。  

缺点：

• 在内部进行插入删除操作效率低。              

• 只能在 vector 的最后进行 push 和 pop ，不能在 vector 的头进行 push 和pop。               

• 当动态添加的数据超过 vector 默认分配的大小时要进行整体的重新分配、拷贝与释放 

list 双向链表

每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。

优点：

• 不使用连续内存完成动态操作。              

• 在内部方便的进行插入和删除操作

• 可在两端进行push、pop

缺点：

• 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()

• 相对于verctor占用内存多

deque 双端队列

 deque是在功能上合并了vector和list。

 优点：

• 随机访问方便，即支持[ ]操作符和vector.at()

• 在内部方便的进行插入和删除操作

• 可在两端进行push、pop

缺点：

• 占用内存多

使用区别：    

• 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用 vector 

• 如果你需要大量的插入和删除，而不关心随即存取，则应使用 list 

• 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用 deque

来源：https://cloud.tencent.com/developer/article/1052125

-- END --

推荐：