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

原文链接: https://www.cnblogs.com/erichome/p/16982183.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    <四>vector、deque、list对比

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/4915

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月4日 下午7:08
下一篇 2023年2月4日 下午7:09

相关推荐