<四>vector、deque、list对比

vector和deque之间的区别?
vector：底层动态数组，内存连续，二倍方式扩容
vector vec;默认是没有开辟空间的, 0->1->2->4->8->16 可以用reserve(20) 只开辟空间,没有放置元素

deque:动态开辟的二维数组空间,第二维是固定长度的空间,扩容的时候,是将第一维数组进行二倍扩容,在把二维的数据
空间放到新的第一维的数组空间里

deque：底层存储空间是否连续? 不是, 但是每一个第二维空间是连续的. 所有的二维是分段的.

vector和deque
1:底层数据结构不一样
2:前中后插入删除元素时间复杂度:
中间和末尾的插入和删除的时间复杂度是一样的,末尾(O(1))，中间O(N)
deque前面插入删除O(1), vector前面插入删除O(N)
3:对内存的使用效率: vector 需要的内存空间必须连续
deque 的第二维是连续的,但是每个第二维不需要连续.因此可以分块存储,不需要一大片连续的存储空间.
4:在空间进行insert或者erase,vector和deque 他们的效率那个好一些? 都是O(N) vector由于是连续的空间,移动更高效

vector和list
list:底层是双向双向循环链表
vector 插入,删除,查找 O(N), 随机访问 O(1);
list:链表 插入删除时O(1)但是需要考虑搜索的时间O(N),链表的搜索是比较慢的