STL——容器适配器、deque
一、容器适配器
1.适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人所知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。
2.STL标准库中stack和queue的底层结构
stack和queue也可以存放元素,但是STL并没有将其划分在容器的行列,而是将其称为容器适配器。这是因为stack和queue只是对其他容器的接口进行了包装,STL中stack和queue底层容器默认使用的是deque。
二、deque简介
1. deque的原理
1.1 deque(双端队列)
是一种双开口“连续”空间的数据结构。双开口是指:可以在头尾两端进行插入和删除操作,且时间复杂度位O(1)。与vector相比,头插效率高,不需要搬移元素;与list相比,空间利用率比较高。
1.2 deque的空间
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成,实际deque类似于一个动态的二维数组,其底层结构图如下所示:

若头插(尾插),但是缓冲区已满,则会再开辟一块空间记录到中控器中的前一个(后一个)位置中,然后往新的缓冲区中插入元素。
若map(中控器满载),则会重新申请一块更大的map,并记录原先map对应位置所记录的缓冲区即可(即将原先map中记录的地址拷贝到新map中),不需要改变原先的缓冲区。
1.3 deque的迭代器
双端队列表面上是一段连续的空间,然而其底层实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,那么其实现就落到了其迭代器上,因此deque的迭代器设计就比较复杂:
first:指向当前缓冲区的起始;
last:指向当前缓冲区的末尾;
cur:指向当前所访问的元素;
node:指向当前所访问的缓冲区的地址在map中的存储位置。
在遍历元素时,当cur与last(first)相同时,则对node进行++(--),然后重新赋值first、last、cur,让其分别指向node指向的新缓冲区的起始、末尾、第一个元素。
2. deque的缺陷
优势:
(1)与vector相比,deque的优势是头部插入和删除时,不需要搬移元素,效率高,而且在扩容时,也不需要搬移大量的元素。因此其效率比vector高。
(2)与list相比,其底层空间是“连续”空间,空间利用率比较高,不需要存储额外字段。
缺陷:
不适合遍历:因为在遍历时,迭代器的每一次++(--)前,都会先对cur进行检测是否已经到达某段缓冲区的边界,频繁的检测导致效率低下。而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多情况下优先考虑vector和list,deque的应用并不多。
3.为什么选择deque作为stack和queue的底层默认容器
stack是一种先进后出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以。
queue是先进先出的特殊线性数据结构,只要具有push_back()和pop_front()操作的线性结构,都可以作为queue的底层容器,比如list。
采用deque作为默认底层容器的原因:
(1)stack和queue不需要遍历,只需要在固定一端或两端进行操作;
(2)在stack中元素增长时,deque扩容时不需要搬移大量数据,效率比vector高;queue中元素增长时,deque不仅效率高,而且内存利用率高。
stack和queue的特性,集合了deque的优点,且完美避开了deque的缺陷。
相关文章:
STL——容器适配器、deque
一、容器适配器 1.适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人所知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 2.STL标准库中stack和queue的底层结构 stack…...
VBA数组和Excel工作表数据传递
本文介绍如何利用 VBA 的数组(Array) 来提高 Excel 单元格和外部数据传输的性能。如果数量比较大,通过 Array 来传输数据比直接操作单元格要快若干倍。 将 Range 的数据写入 VBA Array 将 Range 数据写入 VBA 的数组非常简单。下面的例子演示了用法&am…...
PyQt5保姆级入门教程——从安装到使用
目录 Part1:安装PyQt5 Part 2:PyCharm配置PyQt5 Part 3:PyQt5设计界面介绍 Part 4:PyQt5设计UI 今天看了多个大佬的教程,总算是把PyQt5开发弄好了,每个部分都要看几个人的十分不方便,我十分…...
1.6 epoll实战使用
文章目录1、连接池2、epoll两种工作模式2.1、LT模式2.2、ET模式3、后端开发面试题4、epoll验证1、连接池 将每一个套接字和一块内存进行绑定,连接池就是一个结构体数组,通过链表来维护一个空闲连接。 1、ngx_get_connection(int fd)从空闲链表取一个空闲…...
JDK定时、Spring定时、时间轮定时小结
Timer使用一个线程,一个小根堆。线程执行根上的任务,小根堆会根据执行时间戳重新调整,根上的任务是下一个执行的任务。 DelayedQueue维护一个优先级队列,本质也是一个数组方式的堆。任务生成时也有时间戳,只提供存储。…...
关于cFosSpeed如何配置
cFosSpeed配置一、检查Calibration Done情况二、优化Ping时间和线路校准三、测网速四、cFosSpeed控制台五、配置参数一、检查Calibration Done情况 安装完毕,激活成功后。 右键------>选项------>设置, 打开适配器信息,查看Calibra…...
YOLOV5输出的txt里面有什么猫腻(用于图像分类竞赛中提升图像信息密度)
背景概括: kaggle最近举办了一场医学乳腺癌检测的比赛(图像分类) 比赛官网地址 给的数据是dcm的专业的医学格式,自己通过DICOM库转为png后,发现该图像胸部不同的患者乳腺大小不一,简言之乳腺的CT有效图在…...
vue+axios常用操作
vueaxios常用操作vue2axios请求拦截依赖项http.jsvue2axios设置请求头依赖项http.js获取并设置请求头api.jsa.vuevue2axios请求拦截 依赖项 “vue”: “^2.6.11” “axios”: “^0.21.0” “element-ui”: “^2.13.2”(做弹窗提示,可以不用) http.js // 引入axi…...
Xshell连接阿里云服务器搭建网站
一、建设一个网站的基本要求 申请一个独立的域名申请一台云服务器ECS在服务器上安装网站环境,如:Apache发布网站内容至云服务器将第一步注册的域解析至云服务器的外网IP地址进行ICP备案 二、用户访问网站的过程 在浏览器上输入域名浏览器自动调用DNS&…...
嵌入式ARM设计编程(三) 处理器工作模式
文章和代码已归档至【Github仓库:hardware-tutorial】,需要的朋友们自取。或者公众号【AIShareLab】回复 嵌入式 也可获取。 一、实验目的 (1) 通过实验掌握学会使用msr/mrs 指令实现ARM 处理器工作模式的切换,观察不…...
jenkins构建报错:.java:16: error: package javafx.util does not exist
1、报错 jenkins构建报错 package javafx.util does not exist2、报错原因 代码发现使用了javafx类,该类仅存在OracleJDK中,OpenJDK中没有该类。 jenkins服务器安装的是openjdk 3、卸载OpenJDK 具体不概述了 4、离线安装OracleJDK 1)…...
【第三天】策略模式
前言 策略模式是针对不同算法给出不同实现的方式,解耦代码,减少代码中if.....else代码书写量。 一、策略模式UNL类图 对象角色Context 上下文对象,依赖Strategy接口,一般像Context传入Strategy实现对象,执行策略方法…...
以应用为导向,看声纹识别中的音频伪造问题
声纹识别,又称说话人识别,是根据语音信号中的声纹特征来识别话者身份的过程,也是一种重要的生物认证手段。历经几十年的研究,当前声纹识别系统已取得了令人满意的性能表现,并在安防、司法、金融、家居等诸多领域中完成…...
RocketMQ源码分析之CommitLog消息存储机制
1、消息存储分析 1.1 DefaultMessageStore 概要 其核心属性如下: messageStoreConfig 存储相关的配置,例如存储路径、commitLog文件大小,刷盘频次等等。CommitLog commitLog comitLog 的核心处理类,消息存储在 commitlog 文件中…...
亿级高并发电商项目-- 实战篇 --万达商城项目 九(广告服务、安装Redis优化用户缓存、广告服务实现类等开发)
专栏:高并发---分布式项目 亿级高并发电商项目-- 实战篇 --万达商城项目搭建 一 (商家端与用户端功能介绍、项目技术架构、数据库表结构等设计) 亿级高并发电商项目-- 实战篇 --万达商城项目搭建 一 (商家端与用户端功能介绍、项…...
FreeMarker生成word文档,固定word模板
该方法也就是通过freemarker生成固定的word文档,动态的word模板布局不能用该方法。 也就是必须有一个固定的模板文档是.ftl类型 如果初始文件为 需要手动改为: 也就是所有需要替换的地方,都需要有${XX}替换。 主要步骤为: 将 w…...
前端必学的CSS制作Switch动画开关按钮演示
目录 前言 CSS 制作的 Switch 动画开关按钮 1.Html构建 2.CSS编写 3.完整代码 index.html文件 style.css文件 总结 前言 随着前端技术的不断发展与进步,界面交互的样式要求和美感也越来越高,很多网页的交互都加上了css动画,这里作者给大家分享一…...
C语言运算符(左值右值,基本运算符)
一.数据对象,左值,右值,运算符 数据对象:用于存储值的数据存储区域统称,而使用变量名是标识对象的一种方法(还有指针,后面会教的) 左值:用于标识特定数据对象的名称或表…...
【自学Python】一文读懂Python字符串是否是数字
Python字符串是否是数字 Python字符串是否是数字教程 在开发过程中,有时候我们需要判断一个 字符串 是否是 数字 形式,在 Python 中,判断字符串是否只由数字组成的函数为 isnumeric() 。 isnumeric() 函数只能判断 unicode 字符串…...
【PTA Advanced】1146 Topological Order(C++)
目录 题目 Input Specification: Output Specification: Sample Input: Sample Output: 思路 C 知识UP 代码 题目 This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given dire…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果。…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
