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),链表的搜索是比较慢的