vector和deque之间的区别?
vector:底层动态数组,内存连续,二倍方式扩容
vector
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),链表的搜索是比较慢的
原文链接: https://www.cnblogs.com/erichome/p/16982183.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/4915
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!