深入浅出C++ ——容器适配器
文章目录
- 一、容器适配器
- 二、deque类简介
- 1. deque的原理
- 2. deque迭代器
- 3. deque的优点和缺陷
- 4. 为什么选择deque作为stack和queue的底层默认容器
一、容器适配器
适配器的概念
适配器是STL六大核心组件之一,它是一种设计模式,该种模式是将一个类的接口转换成客户希望的另外一个接口,通过限制模型的功能以让它满足另一个模型的功能,相当于改变了接口,但实现不变。
设计模式的概念
设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结。
stack和queue
虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和queue只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque。
二、deque类简介
deque中文为双端队列,是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,空间利用率比较高。
1. deque的原理
deque 容器存储数据的空间是由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以位于在内存的不同区域。为了管理这些连续空间,deque 容器用数组map存储着各个连续空间的首地址。也就是说,map 数组中存储的都是指针,指向那些真正用来存储数据的各个连续空间。
通过建立 map 数组,deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说,当 deque 容器需要在头部或尾部增加存储空间时,它会申请一段新的连续空间,同时在 map 数组的开头或结尾添加指向该空间的指针,由此该空间就串接到了 deque 容器的头部或尾部。如果 map 数组满了,再申请一块更大的连续空间供 map 数组使用,将原有数据拷贝到新的 map 数组中,然后释放旧的空间。
2. deque迭代器
deque 容器除了维护先前讲过的 map 数组,还需要维护 start、finish 这 2 个 deque 迭代器。start 迭代器记录着 map 数组中首个连续空间的信息,finish 迭代器记录着 map 数组中最后一个连续空间的信息。另外需要注意的是,和普通 deque 迭代器不同,start 迭代器中的 cur 指针指向的是连续空间中首个元素;而 finish 迭代器中的 cur 指针指向的是连续空间最后一个元素的下一个位置。
3. deque的优点和缺陷
与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
但是deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下。而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。
4. 为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;
queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。
但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:
- stack和queue不需要遍历,只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时,deque比vector的效率高,因为扩容时不需要搬移大量数据;queue中的元素增长时,deque不仅效率高,而且内存使用率高。结合了deque的优点,而完美的避开了其缺陷。
相关文章:

深入浅出C++ ——容器适配器
文章目录一、容器适配器二、deque类简介1. deque的原理2. deque迭代器3. deque的优点和缺陷4. 为什么选择deque作为stack和queue的底层默认容器一、容器适配器 适配器的概念 适配器是STL六大核心组件之一,它是一种设计模式,该种模式是将一个类的接口转换…...

电脑常用知识与工作常用工具
什么是电脑快捷键? 所谓快捷键就是使用键盘上某一个或某几个键的组合完成一条功能命令,从而达到提高操作速度的目的。 键盘布局 主键盘区,数字辅助键盘区、F键功能键盘区、控制键区,对于多功能键盘还增添了快捷键区 一、常用快捷…...

JS的事件循环
文章目录写在前面1.浏览器的进程模型1.1 何为进程1.2 何为线程1.3 浏览器有哪些线程和进程2.渲染主线程是如何工作的任务队列的优先级面试题如何理解JS异步JS中的计时器能做到精确计时吗?为什么?写在前面 此处的文字为自己的理解 1.浏览器的进程模型 1.…...

【阿旭机器学习实战】【31】股票价格预测案例--线性回归
【阿旭机器学习实战】系列文章主要介绍机器学习的各种算法模型及其实战案例,欢迎点赞,关注共同学习交流。 注:本文模型结果不好,仅做学习参考使用,提供思路。了解数据处理思路,训练模型和预测数值的过程。 目录1. 读取数据K线图绘…...

浅谈毫米波技术与应用
浅谈毫米波之技术篇2020年10月GSMA发布的《5G毫米波技术白皮书》预计,在2022年北京冬奥会上,5G毫米波有望大放异彩,为观众、媒体转播者、赛事组织和参与者等提供优质的观赛体验、完备的服务保障,将可提供全景VR、新型信息交互、智…...

给安全平台编写插件模块的思路分享
一、背景 最近在GitHub看到一个新的开源安全工具,可以把工具都集成到一个平台里,觉得挺有意思,但是平台现有的工具不是太全,我想把自己的工具也集成进去,所以研究了一番 蜻蜓安全工作台是一个安全工具集成平台&#x…...

4123版驱动最新支持《霍格沃茨之遗》,英特尔锐炫显卡带你畅游魔法世界
2023年开年最火的3A大作,那一定是近期上架steam平台的《霍格沃茨之遗》,这款游戏在2020年9月份曝光,游戏根据《哈利波特》系列书籍内容改编,作为一款开放式的3A大作,《霍格沃兹之遗》目前在steam上的实时在线人数已经突…...

OSI模型和网络协议简介
文章目录一、OSI七层模型1.1什么是OSI七层模型?1.2这个网络模型究竟是干什么呢?二、TCP/IP协议三、常见协议四、物联网通信协议以及MQTT4.1 物联网七大通信协议4.2 MQTT特性一、OSI七层模型 1.1什么是OSI七层模型? 我们需要了解互联网的本质…...

传感器原理及应用期末复习汇总(附某高校期末真题试卷)
文章目录一、选择题二、填空题三、简答题四、计算题五、期末真题一、选择题 1.下列哪一项是金属式应变计的主要缺点(A) A、非线性明显 B、灵敏度低 C、准确度低 D、响应时间慢 2.属于传感器动态特性指标的是(D) A、重复性 B、线…...

【亲测2022年】网络工程师被问最多的面试笔试题
嗨罗~大家好久不见,主要是薄荷呢主业还是比较繁忙的啦,之前发了一个面试题大家都很喜欢,非常感谢各位大佬对薄荷的喜爱,嘻嘻然后呢~薄荷调研了身边的朋友和同事,发现我们之前去面试,写的面试题有很多共同的…...

Web前端:全栈开发人员的责任
多年来,关于全栈开发人员有很多说法,全栈开发人员是一位精通应用程序全栈开发过程的专业人士。这包括数据库、API、前端技术、后端开发语言和控制系统版本。你一定遇到过前端和后端开发人员。前端开发人员将构建接口,而后端开发人员将开发、更…...

C语言之通讯录的实现
通讯录实现所需头文件和源文件 Contact.h的功能 声明函数和创建结构体变量 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #define MAX 1000 #define MAX_NAME 20 #define MAX…...

手把手教大家在 gRPC 中使用 JWT 完成身份校验
文章目录1. JWT 介绍1.1 无状态登录1.1.1 什么是有状态1.1.2 什么是无状态1.2 如何实现无状态1.3 JWT1.3.1 简介1.3.2 JWT数据格式1.3.3 JWT 交互流程1.3.4 JWT 存在的问题2. 实践2.1 项目创建2.2 grpc_api2.3 grpc_server2.4 grpc_client3. 小结上篇文章松哥和小伙伴们聊了在 …...

VSCode远程连接服务器
工作使用服务器的jupyter,直到有一天服务器挂了,然而,代码还没有来得及备份。o(╥﹏╥)o VScode远程连接服务器,使用服务器的资源,代码可以存在本地,可以解决上述困境。 1.官网下载VSCode.网址https://cod…...

【C++】-- 异常
目录 C语言传统的处理错误的方式 C异常概念 异常的使用 异常的抛出和捕获 自定义异常体系 异常的重新抛出 异常安全 异常规范(C期望) C标准库的异常体系 异常的优缺点 C异常的优点 C异常的缺点 总结 C语言传统的处理错误的方式 传统的错误…...

Java中的Stack与Queue
文章目录一、栈的概念及使用1.1 概念1.2 栈的使用1.3 栈的模拟实现二、队列的概念及使用2.1 概念2.2 队列的使用2.3 双端队列(Deque)三、相关OJ题3.1 用队列实现栈。3.2 用栈实现队列。总结一、栈的概念及使用 1.1 概念 栈:一种特殊的线性表,其只允许在…...

xilinx FPGA在线调试方法总结(vivado+ila+vio)
本文主要介绍xilinx FPGA开发过程中常用的调试方法,包括ILA、VIO和TCL命令等等,详细介绍了如何使用。一、FPGA调试基本原则根据实际的输出结果表现,来推测可能的原因,再在模块中加ILA信号,设置抓信号条件,逐…...

自动化测试——css元素定位
文章目录一、css定位场景二、css相对定位的优点三、css的调试方法1、表达式中含有字符串:表达式中的引号一定和外面字符串的引号相反四、css基础语法1、标签定位2、class定位特别注意:当class类型的属性值包含多个分割值,$(.s_tab s_tab_1z9n…...
ChatGPT可能马上取代你,这是它能做的十个工作
ChatGPT 的横空出世,在业界掀起了惊涛骇浪。专家表示,ChatGPT 和相关人工智能技术可能会威胁到一些工作岗位,尤其是白领工作。 自去年11月发布以来,新型聊天机器人模型 ChatGPT 已经被用于各种各样的工作:撰写求职信、编写儿童读物,甚至帮助学生在论文中作弊。谷歌公司发…...

ubuntu转储coredump
方法一: 输入以下命令即可,其中${USER}为自己电脑的用户名: ulimit -c unlimited echo "/home/${USER}/core.%p" > /proc/sys/kernel/core_pattern 方法二: Disable apport : sudo systemctl stop apport.servicesudo system…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...