第十一章:deque类

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

系列文章目录



前言

deque是一种双开口的“连续空间”的容器。


deque的介绍

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

第十一章:deque类,# C++语言基础,c++,stl

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下图所示:

第十一章:deque类,# C++语言基础,c++,stl

SGI版本选择用固定大小的缓冲区,缓冲区是否是固定大小会影响中间插入删除数据和随机访问的效率

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:
第十一章:deque类,# C++语言基础,c++,stl

第十一章:deque类,# C++语言基础,c++,stl

cur:当前指向数据位置
first和last:buff数组开始和结束
node:反向指向中控数组

deque的使用

第十一章:deque类,# C++语言基础,c++,stl

deque的缺陷

与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。

与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。

但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

而且deque中间插入删除很难搞,效率比vector高,比list低。如果想中间插入删除数据高会影响随机访问效率变低,如果想让删除数据的效率变高会影响中间插入删除数据效率变低。

综上所述,没有vector和list优点极致。

deque的应用

选择deque作为stack和queue的底层默认容器。

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。

结合了deque的优点,而完美的避开了其缺陷。


总结

deque结合了list和vector的优点,但并没有任意一个极致。
只有经历地狱般的磨练,才能炼出创造天堂的力量。文章来源地址https://www.toymoban.com/news/detail-615394.html

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

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

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

相关文章

  • 简易计算器-课后程序(JAVA基础案例教程-黑马程序员编著-第十一章-课后作业)

    【案例11-2】 简易计算器 【案例介绍】 1. 案例描述 本案例要求利用Java Swing 图形组件开发一个可以进行简单的四则运算的图形化计算器。 2. 运行结果 运行结果   【案例分析】 要制作一个计算器,首先要知道它由哪些部分组成,如下图所示: 一个简单的图形化界面计算器,

    2024年02月03日
    浏览(45)
  • Spark大数据分析与实战笔记(第一章 Scala语言基础-2)

    Spark是专为大规模数据处理而设计的快速通用的计算引擎,它是由Scala语言开发实现的,关于大数据技术,本身就是计算数据,而Scala既有面向对象组织项目工程的能力,又具备计算数据的功能,同时Spark和Scala的紧密集成,本书将采用Scala语言开发Spark程序,所以学好Scala将有助

    2024年02月11日
    浏览(59)
  • Spark大数据分析与实战笔记(第一章 Scala语言基础-1)

    Spark是专为大规模数据处理而设计的快速通用的计算引擎,它是由Scala语言开发实现的,关于大数据技术,本身就是计算数据,而Scala既有面向对象组织项目工程的能力,又具备计算数据的功能,同时Spark和Scala的紧密集成,本书将采用Scala语言开发Spark程序,所以学好Scala将有助

    2024年02月11日
    浏览(62)
  • Spark大数据分析与实战笔记(第一章 Scala语言基础-3)

    对于每一门编程语言来说,数组(Array)都是重要的数据结构之一,主要用来存储数据类型相同的元素。Scala中的数组分为定长数组和变长数组,定义定长数组,需要使用new,而定义变长数组时,则需要导包 import scala.collection.mutable.ArrayBuffer 。 数组(Array)主要用来存储

    2024年02月10日
    浏览(60)
  • [ XJTUSE ]JAVA语言基础知识——第一章 面向对象程序设计思想

    类描述了一组有相同 特性 (属性)和相同 行为 (方法)的对象,类和对象是面向对象思想的两个核心概念 · 人类是一种类,每一个具体的人则是这个类的对象 用面向对象程序来模拟真实世界 发现并创建类 发现类的特征 发现类的行为 在面向对象程序中,对象的特征由各种

    2023年04月13日
    浏览(82)
  • 前端新手Vue3+Vite+Ts+Pinia+Sass项目指北系列文章 —— 第十一章 基础界面开发 (组件封装和使用)

    Vue 是前端开发中非常常见的一种框架,它的易用性和灵活性使得它成为了很多开发者的首选。而在 Vue2 版本中,组件的开发也变得非常简单,但随着 Vue3 版本的发布,组件开发有了更多的特性和优化,为我们的业务开发带来了更多便利。本文将介绍如何使用 Vue3 开发业务组件

    2024年02月19日
    浏览(83)
  • 【蓝桥杯备赛Java组】第一章·语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月19日
    浏览(72)
  • shell 第十一章

    1.写一个库函数,用定时任务调用这个库函数,每月1号执行 1.sh:  1.1.sh:   2.以免交互的方式实现 ssh 远程登录,密码错误也直接退出,不用人干预 3.以免交互的方式,实现磁盘分区、格式化、挂载

    2024年02月08日
    浏览(59)
  • 第十一章 请求响应

    将前端发送的请求封装为HttpServletRequest对象 在通过HttpServletResponse 在前后端分离开发中,后端每开发完一个功能,就想要对这个接口功能进行测试 由于是前后端分离开发,所以没有前端页面 我们一般是在浏览器中直接输入地址,来访问我们所开发的web应用 但是浏览器发起的

    2024年01月21日
    浏览(60)
  • Linux 第十一章

    🐶博主主页: @ᰔᩚ. 一怀明月ꦿ  ❤️‍🔥 专栏系列: 线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C++,linux 🔥 座右铭:“不要等到什么都没有了,才下定决心去做” 🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀 目录

    2024年04月28日
    浏览(70)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包