vector, deque, list之间的对比
-
vector的特点：
- 动态数组
- 内存是完全连续的
- 扩容：2倍形式扩容，扩容时要开辟新的内存空间，并将数据拷贝
-
list的特点：
- 双向循环链表
- 内存是不连续的
- 没有扩容需求
-
deque的特点：
- 参考
- 动态开辟的二维数组空间
- 内存分段连续
- 第二维是固定长度的数组空间，扩容的时候第一维2倍扩容
-
vector和deque的区别
- 底层数据结构不同
- 前面插入元素的复杂度：vector为O(n)，deque为O(1)
- 中间插入元素的复杂度：均为O(n)
- 最后插入元素的复杂度：均为O(1)
- 内存的使用效率：vector要求内存空间必须是连续的，deque可以分块数据存储，不必内存连续，使用效率更高。
- 对中间进行insert或者erase，vector的效率相对更好些，因为其底层内存连续。
-
vector和list的区别
- 底层数据结构不同
- vector适合随机访问
- list适合增删