vector VS deque

这篇具有很好参考价值的文章主要介绍了vector VS deque。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. vector与deque

vector与动态数组相同,能够在插入或删除元素时自动调整自身大小,其存储由容器自动处理,vector通常占用多于静态数组的空间,因为要分配更多的内存以管理将来的增长,在每次插入元素的时,仅当额外内存耗尽时触发重新分配。

vector VS deque,C++,c++,vector,deque

如上图所示,vector元素放置在连续存储中,以便可以使用迭代器访问和遍历他们。在vector中,末尾插入需要不同的时间,因为有时候需要扩展存储空间。对于删除最后一个元素,因为不涉及存储空间大小的调整,则执行时间是恒定的。对于开头或者中间插入和擦除在时间上是线性的,因为可能要涉及到元素的移动。

deque是具有两端扩缩功能的序列容器。其存储方式与vector相反,deque的元素不是相接存储的,是由一段一段等长的连续空间构成的,各段之间并不一定是连续的。它的典型实现如下图所示,通过单独分配固定尺寸的序列(对应图中的数据区),外加额外的登记(对应图中map映射区),map数组中存储的是每段连续空间的地址,通过映射区来管理这些一段一段等长的连续空间,进而实现“整体连续”的效果。

vector VS deque,C++,c++,vector,deque

deque容器需要在头部或者尾部增加空间的时候,它会申请一段新的连续空间,同时在map数组的开头或者结尾添加指向该空间的指针,由此将deque元素串接起来。在遇到空间不足的时候由于deque可以申请新的连续空间,原数据空间可以保持不变,更新map即可,所以deque在涉及到空间扩展的时候,效率远高于vector

2. 性能比较

2.1 随机访问

vector VS deque,C++,c++,vector,deque

由于vector是连续存储的,deque是分段连续存储,其随机访问需对map数组进行二次指针解引用(可以理解为:deque随机访问需要先去找到待访问元素在哪段连续存储空间,然后再对该空间进行下标访问),而vector只有下标访问一次即可。因此在随机访问性能上,vector略高于deque,但两者复杂度均为常数 O ( 1 ) O(1) O(1)

2.2 末尾插入/删除

vector VS deque,C++,c++,vector,deque

前面我们说过,vector的存储是自动管理的,按需扩张收缩,vector通常占用多于静态数组的空间,因为要分配更多的内存以管理将来的增长,通常情况下vector在尾部插入元素的复杂度为 O ( 1 ) O(1) O(1),但当额外内存耗尽的时候,需要重新分配,此时重新分配,是需要单独再申请一份更大空间,把vector原有的元素重新放到新申请的空间上,再完成尾部插入,此时涉及到了新空间的申请、所有元素的移动和旧空间的释放,这种情况下的插入在性能上是灾难级别的,因此,总的来说对于vector尾部插入的时间复杂度为均摊常数 O ( 1 ) O(1) O(1)

对于deque由于存储空间是分段连续的,当空间不够的时候重新申请新的一段空间即可,不会涉及到旧元素的移动,其复杂度度为常数 O ( 1 ) O(1) O(1)。对于尾部删除,因为不涉及到分配空间申请,因此两者的复杂度均在 O ( 1 ) O(1) O(1)

vector在尾部插入元素的时,新的size()如果大于capacity(),那么所有的迭代器和引用(包括end()迭代器)都会失效,否则只有end()迭代器会失效。而deque除了迭代器会失效,而不会使指向其余元素的指针或引用失效。

2.3 随机插入/删除

vector VS deque,C++,c++,vector,deque

vector在进行随机插入的时候,涉及到插入位置到序列尾部这段元素的移动(可以理解为这段元素需要整体往后移动一位,给新插入元素把位置留出来),随机删除元素同理,因此其随机插入/删除的时间复杂度为插入位置与到vector尾部距离成线性 O ( n ) O(n) O(n)deque的扩展方式是双向的,因此其可以**根据插入位置距离头部或者尾部较近的距离成线性 O ( n ) O(n) O(n),**因此,其性能略胜vector一丢丢。

:对于vector随机插入,如果新size()大于旧的capacity()就会导致重分配,所有的迭代器和引用都会失效,否则,只有在插入点前的迭代器和引用会保持有效。对于deque而言,所有迭代器和引用也会失效,除非插入位置为容器尾部或者头部,引用不会失效。

3. 总结

vectordeque的对比如下表所示:

vector deque
头文件 使用需要包含头文件<vector> 使用需要包含头文件<deque>
存储方式 连续存储元素 包含元素连续存储的内存快列表
随机访问 支持,复杂度为常数 O ( 1 ) O(1) O(1) 支持,复杂度为常数 O ( 1 ) O(1) O(1)
末尾插入/末尾删除元素 均摊常数 O ( 1 ) O(1) O(1) 常数 O ( 1 ) O(1) O(1)
随机插入/随机删除元素 与到vector结尾的距离成线性 O ( n ) O(n) O(n) 线性 O ( n ) O(n) O(n)

vector重分配在性能上是有开销的,如果在使用之前元素的数量已知,那么可以使用rederve()函数来消除重分配。

deque的存储按需自动扩展及收缩,扩展deque比扩张vector更优,因为它不涉及到复制既存元素到新内存位置。但另外一方面,deque典型地拥有较大的最小内存开销,所以当即使保有一个元素的时候,deque也需要为它分配它的整个内部数组。

文章首发公众号:iDoitnow如果喜欢话,可以关注一下文章来源地址https://www.toymoban.com/news/detail-676028.html

到了这里,关于vector VS deque的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++中vector、list和deque的选择:什么时候使用它们?

    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 在C++中,vector、list和deque是STL(标准模板库)提供的三种常见的容器。每种容器都有其特点和适用场景。本文将详

    2024年02月13日
    浏览(39)
  • deque用法深度解析,一篇文章弄懂deque容器各种操作

    🖱 博客主页:在下马农的碎碎念 ✍ 本文由在下马农原创,首发于CSDN 📆 首发时间:2022/01/11 📅 最近更新时间:2022/01/11 🤵 此马非凡马,房星本是星。向前敲瘦骨,犹自带铜声。 📇 系列文章目录: 暂无 🙏作者水平有限,如发现错误,请留言轰炸哦!万分感谢! 🤗码字不

    2023年04月24日
    浏览(51)
  • 【C++】deque的用法

    在了解deque前,我们先讲一讲什么是适配器。 适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结), 该种模式是将一个类的接口转换成客户希望的另外一个接口。 就像我们生活中常见的充电器一样。 在STL中,虽然

    2024年02月08日
    浏览(34)
  • 第十一章:deque类

    deque是一种双开口的“连续空间”的容器。 deque(双端队列):是一种双开口的\\\"连续\\\"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高 。 deque并不是真正连

    2024年02月15日
    浏览(40)
  • deque(简单介绍一下)

    deque的基本情况: 简单的来说deque是一个双头队列。且两边的尺寸可以动态收缩或者扩张。 其底层实现相当复杂,而且效率并不高。大多数时候都不会使用。 deque诞生的原因是vector和list的优缺点不可分割。 正好复习一下vector和list的优缺点。 vector的优点:支持随机访问;尾插

    2024年02月08日
    浏览(55)
  • C++ deque底层原理

    实现双端数组 双向开口的连续线性空间 class deque : protected Deque base _Deque_base._Deque_impl _Deque_iterator _deque buf size 连续空间中能容纳元素的个数 _M_initialize _map 当前连续空间够不够 map 空间够不够 删除最后一个节点,如果当前连续空间没有数据了,则释放该连续空间 推荐一个零声

    2024年02月10日
    浏览(33)
  • Queue,List,Deque联系

    如图所示,可以得出 LinkedList既可以是双向链表也可以是双端队列,Deque接口继承了Queue接口 Queue add(E):boolean 在队尾添加元素,添加成功返回true,如果 队列已满 无法添加则 抛出异常。 offer(E):boolean 在队尾添加元素,添加成功返回true,如果 队列已满 无法添加则 返回false 。

    2024年02月11日
    浏览(37)
  • C++ 学习之Deque容器

    Deque(Double-Ended Queue,双端队列)是C++标准库中的一种容器,允许在两端进行高效地插入和删除操作。Deque与Vector类似,但相比于Vector,Deque在两端插入和删除元素的效率更高。 Deque具有以下特点和概念: 双端操作:Deque支持在头部和尾部进行插入和删除等操作,因此可以被视

    2024年02月19日
    浏览(41)
  • 浅谈deque,queue,stack

    deque 和 queue 都是常用于存储元素的容器,但它们在数据结构和应用场景上有一些区别。 queue 是队列的一种实现,它只能从队首插入元素,而只能从队尾获取并移除元素。即,queue 满足 FIFO(先进先出)的特性。queue 通常用于实现任务队列、消息队列等场景。 deque 则是双端队

    2024年02月07日
    浏览(39)
  • 双端队列deque(C++)

    栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。 该数据结构形如长条形。 一开始该容器为空,有以下七种操作。 1 a从前面插入元素a 2 从前面删除一个元素 3 a从后面插入一个元素 4 从后面删除一个元素 5 将整个容器头尾翻转 6 输出个数和所有元素 7 对所有

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包