【C++】deque的用法
目录
- 一、容器适配器
- 二、deque的介绍
- 三、deque的使用及缺陷
- 1、deque的构造函数
- 2、deque的元素访问接口
- 3、deque的 iterator的使用
- 4、deque的增删查改
- 4、deque的缺陷
- 5、为什么选择deque作为stack和queue的底层默认容器
一、容器适配器
在了解deque前,我们先讲一讲什么是适配器。
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 就像我们生活中常见的充电器一样。
在STL中,虽然stack、queue和priority_dueue中也可以存放元素,但是并没有将其划分在容器的行列中去,而是将其称为容器适配器,这就是因为stack、queue和priority_dueue中只是对其他容器的接口进行了包装。并且,在STL中stack和queue默认使用的是deque,priority_dueue默认使用的是vector。
二、deque的介绍
deque:即双端队列,是一种双开口的连续空间的数据结构。可以在头尾两端进行插入和删除操作。并且,时间复杂度为O(1),与vector比较,头插效率高,不需要移动元素;与list比较,空间利用率比较高。
但是,deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下:
双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:
那deque又是如何借助其迭代器维护其假想连续的结构呢?
三、deque的使用及缺陷
1、deque的构造函数
函数名称 | 功能说明 |
---|---|
deque() | 无参构造 |
deque(size_type n, const value_type& val = value_type()) | 构造并初始化n个val |
deque (InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
deque (const deque& x) | 拷贝构造 |
代码演示:
#include <iostream>
#include <deque>
using namespace std;
int main()
{int i;deque<int> d1; deque<int> d2(4, 50); deque<int> d3(d2.begin(), d2.end()); deque<int> d4(d3); for (auto e : d4){cout << e << " ";//结果:50 50 50 50}cout << endl;int arr[] = { 16,2,77,29 };deque<int> d5(arr, arr + sizeof(arr) / sizeof(int));deque<int>::iterator it = d5.begin();while (it != d5.end()){cout << *it << ' ';//结果:16 2 77 29++it;}cout << endl;return 0;
}
2、deque的元素访问接口
函数声明 | 说明 |
---|---|
size() | 获取数据个数 |
empty() | 判断是否为空 |
resize() | 更该容器大小 |
front() | 访问第一个元素 |
back() | 访问最后一个元素 |
3、deque的 iterator的使用
函数声明 | 说明 |
---|---|
begin() + end() | 获取第一个数据位置的iterator/const_iterator + 获取最后一个数据的下一个位置的iterator/const_iterator |
rbegin() + rend() | 获取最后一个数据位置的reverse_iterator + 获取第一个数据前一个位置的reverse_iterator |
与vector一样是一个随机访问迭代器,而list是一个双向迭代器
4、deque的增删查改
函数名称 | 功能说明 |
---|---|
push_back() | 在末尾添加元素 |
push_front() | 在开头插入元素 |
pop_back() | 删除最后一个元素 |
pop_front() | 删除第一个元素 |
insert() | 插入元素 |
erase() | 删除元素 |
swap() | 交换元素 |
clear() | 清空有效元素 |
operator[] | 访问元素 |
insert / erase 代码演示:
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
void PrintList(const deque<int>& d)
{for (deque<int>::const_iterator it = d.begin(); it != d.end(); ++it){cout << *it << " "; }cout << endl;
}
int main()
{deque<int> d1;for (int i = 1; i < 6; i++){d1.push_back(i); // 1 2 3 4 5}deque<int>::iterator it = d1.begin();++it;it = d1.insert(it, 10); PrintList(d1); // 结果:1 10 2 3 4 5d1.insert(it, 2, 20); PrintList(d1);// 结果:1 20 20 10 2 3 4 5it = d1.begin() + 2;vector<int> v(2, 30);d1.insert(it, v.begin(), v.end()); PrintList(d1);// 结果:1 20 30 30 20 10 2 3 4 5deque<int> d2;for (int i = 1; i <= 10; i++){d2.push_back(i); // 1 2 3 4 5 6 7 8 9 10}d2.erase(d2.begin() + 5);PrintList(d2); //结果:1 2 3 4 5 7 8 9 10d2.erase(d2.begin(), d2.begin() + 3);PrintList(d2); //结果:4 5 7 8 9 10return 0;
}
运行结果:
由上述接口中,可以看出deque是vector和list的结合体,但是实际使用中并不常见,而目前能看到的一个应用就是在STL中用其作为stack和queue的底层数据结构,为什么呢?
4、deque的缺陷
优势
- 与vector比较,deque头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是比vector高的。
- 与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
缺陷:
- deque并不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多。所以目前能看到的一个应用就是在STL中用其作为stack和queue的底层数据结构。
5、为什么选择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和queue没有迭代器),只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。
综上所述,stack和queue结合了deque的优点,而完美避开了其缺陷。
相关文章:

【C++】deque的用法
目录 一、容器适配器二、deque的介绍三、deque的使用及缺陷1、deque的构造函数2、deque的元素访问接口3、deque的 iterator的使用4、deque的增删查改4、deque的缺陷5、为什么选择deque作为stack和queue的底层默认容器 一、容器适配器 在了解deque前,我们先讲一讲什…...

Live800:智能客服有哪些未来发展趋势?
智能客服,也称智能问答系统,是一种利用机器学习、自然语言处理等技术实现自主询问、自主应答、自主维护的自动化系统。它们可以通过文字形式,为用户提供个性化、一对一的服务,避免了人工客服的人力成本和等待时间。 未来ÿ…...
【一】Java SE 基础
文章目录 一、初始Java1.1 什么是Java1.2 Java的特点1.3 第一个Java程序 二、数据类型与变量2.1 基本数据类型2.2 基本数据类型对应的包装类2.3 变量2.4 类型转换2.5 字符串类型及其与数字之间的转换 三、运算符3.1 算术运算符3.2 赋值运算符3.3 关系运算符3.4 逻辑运算符3.5 位…...
Linux防火墙学习笔记2
iptables是什么? 1)iptables 不是防火墙,是防火墙用户代理。 2)用于把用户的安全设置添加到“安全框架”中。 3)“安全框架”是防火墙。 4)安全框架的名称是netfilter。 5)netfilter位于内…...
Linux下MongDB定时备份方案
1. 安装crontabs 首先安装crontabs yum install crontabs 2. 创建备份目录 [rootlocalhost data]# mkdir -p /data/backup/mongo/mongodb_bak_tmp [rootlocalhost data]# mkdir -p /data/backup/mongo/mongodb_bak_path 3. 创建MongoDB备份shell脚本 有密码: …...

长尾词挖掘,长尾词的优化方法有哪些
我们都知道,长尾词能给我们带来较高的流量和转化率,且优化难度低,成本低。今天就来分享长尾词的优化方法。 首先需要挖掘长尾词,挖掘长尾词的方法以下3种比较实用: 1、使用长尾词挖掘工具 可以通过第三方工…...
JUC基础-0601
6 多线程锁 6.1 锁的八个问题演示 class Phone {public static synchronized void sendSMS() throws Exception {//停留4秒TimeUnit.SECONDS.sleep(4);System.out.println("------sendSMS");}public synchronized void sendEmail() throws Exception {System.out.p…...
bash特性
bash bash是一个命令处理器,运行在文本窗口zh哦那个,执行用户输入的命令。 1、bash特性–历史命令 保留用户的历史执行的命令,可以使用history查看之前执行过的命令 #通过$HISTORY查看保存的命令条数 echo $HISTORY #存放用户执行的历史…...

[Flink] Flink On Yarn(yarn-session.sh)启动错误
在Flink上启动 yarn-session.sh时出现 The number of requested virtual cores for application master 1 exceeds the maximum number of virtual cores 0 available in the Yarn Cluster.错误。 版本说明: Hadoop: 3.3.4 Flink:1.17.1 问题…...
玩转css逐帧动画,努力成为更优质的Ikun~
🎉 一、前言 css3的animation想必大家都知道吧,那 steps 逐帧动画你知道吗?对于我来说,实际工作及练习中也很少用到这种跳跃式变化的动画,而它start和end的解释又比较“不说人话”,以前用到steps动画的时候…...
Linux Capabilities
Linux Capabilities是一种细粒度的权限管理机制,用于将root用户的特权划分为具体的功能集。它允许将部分root特权授予非root进程。 可以在shell中运行: man capabilities将显示capability man page,其中包含有关Linux功能的详细信息。 文章目录 什么是CapabilitiesLinux Cap …...

【自制C++深度学习框架】前言
KuiperCourse 介绍 此GitHub项目是一个初学者的深度学习框架,使用C编写,旨在为用户提供一种简单、易于理解的深度学习实现方式。以下是本项目的主要特点和功能: 计算图:使用计算图来描述深度学习模型的计算过程,利用计…...

【高危】泛微 e-cology9 存在任意用户登录漏洞
漏洞描述 泛微协同管理应用平台(e-cology)是一套企业大型协同管理平台。 泛微e-cology9部分版本中存在前台任意用户登录漏洞,由于系统默认配置固定密钥进行用户身份验证。 当存在/mobile/plugin/1/ofsLogin.jsp文件时(可能通过插件方式安装࿰…...
1TB文本的实时全文检索系统搭建
1个T的文本是多大呢?1TB 1000GB,1GB是10亿,1TB就是1万亿字节。如果是英文字符,1TB文本就是1万亿个英文字符,如果是中文字符而且都是UTF8格式,1个中文字符占3个字节,1TB文本是3333亿中文字符&am…...
RHCA---DO477---变量实验
实验目的如下: 1. 环境准备: 使用命令lab inventory-variables start初始化环境 2. 进入/home/student/git-repos目录克隆下载http://git.lab.example.com:8081/git/inventory-variables.git 3. 将目录下yaml文件内容以group_vars形式修改 4. 部署并将修改后ansible-playbook代…...

毕业生高频常用材料线上签,高校毕业季契约锁电子签章一站式助力
据人社部消息,2023年全国高校毕业生总规模将达1158万人!毕业季开启,全国各地高校普遍面临三方协议、成绩单、证书、证明等毕业生高频常用材料签署量激增的现状。学生、教职工、学校常常疲于应对机械化的材料盖章工作。 #毕业季高频常用材料清…...

.ini配置文件介绍与解析库使用
【前言】 ini 文件是英文"Initialization"的缩写,即初始化文件。它用来配置特定应用软件以实现对程序初始化或进行参数设置。.ini文件由节(section)、键(key)、值(value)三种模块构成。在windows系统/嵌入式软件中有很多XXX.ini文件,例如Syste…...
牛客网Linux错题七
1.如何在命令行查看一台linux机器的CPU、SWAP分区信息、硬盘信息?(ACD) A. cat /proc/cpuinfo B. du C. cat /proc/swaps D. df -Ih 解: cat /proc/cpuinfo查看Linux设备的CPU信息,cat /proc/swaps查看Linux设备的交换分区信息…...
牛课刷题Day5(编程题)
1.合并数组 arr1 和数组 arr2。不要直接修改数组 arr,结果返回新的数组 正确答案: function concat(arr1, arr2) {let carr1.concat(arr2)return c } 解析: js的Array对象提供了一个叫concat()方法,连接两个或更多的数组&#x…...

javascript基础二十五:说说你对函数式编程的理解?优缺点?
一、是什么 函数式编程是一种"编程范式"(programming paradigm),一种编写程序的方法论 主要的编程范式有三种:命令式编程,声明式编程和函数式编程 相比命令式编程,函数式编程更加强调程序执行…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...