vector、deque、list相关知识点

vector

• erase返回迭代器指向删除元素后的元素
• insert返回迭代器指插入的元素
• reserve只给容器底层开指定大小内存空间，并不添加新元素

deque

底层数据结构

动态开辟的二维数组，一维数组从2开始，以2倍方式扩容，每次扩容和，原来第二维数组，从新的第一维数组下标oldsize/2开始存放，上下都预留空行，方便deque在首尾添加删除元素

deque适用于首尾进行操作的场景,和vector比，多了push_front和pop_front()

deque底层内存是否是连续的？

不是，分段连续的，每个第二维是连续的

vector、deque、list对比

• vector特点：动态数组，内存是连续的，2倍的方式进行扩容，

• deque特点：动态开辟的二维数组空间，第二维是固定长度的数组空间，扩容的时候（第一维的数组进行2倍扩容）

容器的纵向考察：容器掌握的深度

容器的横向考察：各个相似容器之间的对比

vector和deque的区别

vector底层是动态开辟的一维数组，deque则是动态开辟的二维数组

前中后插入删除元素时间复杂度：中间O(n)和末尾O(1), 首部插入deque O(1),vector则是O(n)

对于内存使用效率：vector需要内存空间必须完全连续，deque只需分段连续

中间进行insert或erase，vector效率更好一点，因为deque分段连续，在边界位置移动需要多余的操作

vector和list区别

vector底层数据结构是数组，list为双向循环链表

数组：增加删除O(n),查询O(n),随机访问O(1)

链表：（考虑搜索时间）增加删除O(1),查询O(n),随机访问O(n)

容器适配器

其实源代码上更接近代理模式

queue和stack底层默认使用deque；priority_queue则使用vector，为什么？

vector初始内存使用效率不如deque，deque一开始就有比较大的第二维连续空间，vector则需要多次的二倍扩容操作。

对于queue需要支持尾插头删，用deque时间复杂度低O(1)

vector需要大片的连续内存，而deque只需要分段的内存，当存储大量数据时，显然deque对于内存的利用率更好一些。

这就是queue和stack底层默认使用deque的理由；

priority_queue堆底层用vector，因为堆是树形结构，底层用vector数组存储更方便随机访问树的节点（下标直接算）。如根节点i，左子节点为$2i+1$,右子节点为$2i+2$

priority_queue默认是大根堆，比较函数对象为less