当前位置: 首页 > news >正文

【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作为其底层容器,主要原因是:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在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前&#xff0c;我们先讲一讲什…...

Live800:智能客服有哪些未来发展趋势?

智能客服&#xff0c;也称智能问答系统&#xff0c;是一种利用机器学习、自然语言处理等技术实现自主询问、自主应答、自主维护的自动化系统。它们可以通过文字形式&#xff0c;为用户提供个性化、一对一的服务&#xff0c;避免了人工客服的人力成本和等待时间。 未来&#xff…...

【一】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是什么&#xff1f; 1&#xff09;iptables 不是防火墙&#xff0c;是防火墙用户代理。 2&#xff09;用于把用户的安全设置添加到“安全框架”中。 3&#xff09;“安全框架”是防火墙。 4&#xff09;安全框架的名称是netfilter。 5&#xff09;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脚本 有密码&#xff1a; …...

长尾词挖掘,长尾词的优化方法有哪些

我们都知道&#xff0c;长尾词能给我们带来较高的流量和转化率&#xff0c;且优化难度低&#xff0c;成本低。今天就来分享长尾词的优化方法。 首先需要挖掘长尾词&#xff0c;挖掘长尾词的方法以下3种比较实用&#xff1a; 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是一个命令处理器&#xff0c;运行在文本窗口zh哦那个&#xff0c;执行用户输入的命令。 1、bash特性–历史命令 保留用户的历史执行的命令&#xff0c;可以使用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.错误。 版本说明&#xff1a; Hadoop&#xff1a; 3.3.4 Flink&#xff1a;1.17.1 问题…...

玩转css逐帧动画,努力成为更优质的Ikun~

&#x1f389; 一、前言 css3的animation想必大家都知道吧&#xff0c;那 steps 逐帧动画你知道吗&#xff1f;对于我来说&#xff0c;实际工作及练习中也很少用到这种跳跃式变化的动画&#xff0c;而它start和end的解释又比较“不说人话”&#xff0c;以前用到steps动画的时候…...

Linux Capabilities

Linux Capabilities是一种细粒度的权限管理机制,用于将root用户的特权划分为具体的功能集。它允许将部分root特权授予非root进程。 可以在shell中运行: man capabilities将显示capability man page,其中包含有关Linux功能的详细信息。 文章目录 什么是CapabilitiesLinux Cap …...

【自制C++深度学习框架】前言

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

【高危】泛微 e-cology9 存在任意用户登录漏洞

漏洞描述 泛微协同管理应用平台(e-cology)是一套企业大型协同管理平台。 泛微e-cology9部分版本中存在前台任意用户登录漏洞&#xff0c;由于系统默认配置固定密钥进行用户身份验证。 当存在/mobile/plugin/1/ofsLogin.jsp文件时&#xff08;可能通过插件方式安装&#xff0…...

1TB文本的实时全文检索系统搭建

1个T的文本是多大呢&#xff1f;1TB 1000GB&#xff0c;1GB是10亿&#xff0c;1TB就是1万亿字节。如果是英文字符&#xff0c;1TB文本就是1万亿个英文字符&#xff0c;如果是中文字符而且都是UTF8格式&#xff0c;1个中文字符占3个字节&#xff0c;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代…...

毕业生高频常用材料线上签,高校毕业季契约锁电子签章一站式助力

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

.ini配置文件介绍与解析库使用

【前言】 ini 文件是英文"Initialization"的缩写&#xff0c;即初始化文件。它用来配置特定应用软件以实现对程序初始化或进行参数设置。.ini文件由节(section)、键(key)、值(value)三种模块构成。在windows系统/嵌入式软件中有很多XXX.ini文件&#xff0c;例如Syste…...

牛客网Linux错题七

1.如何在命令行查看一台linux机器的CPU、SWAP分区信息、硬盘信息&#xff1f;(ACD) A. cat /proc/cpuinfo B. du C. cat /proc/swaps D. df -Ih 解&#xff1a; cat /proc/cpuinfo查看Linux设备的CPU信息&#xff0c;cat /proc/swaps查看Linux设备的交换分区信息&#xf…...

牛课刷题Day5(编程题)

1.合并数组 arr1 和数组 arr2。不要直接修改数组 arr&#xff0c;结果返回新的数组 正确答案&#xff1a; function concat(arr1, arr2) {let carr1.concat(arr2)return c } 解析&#xff1a; js的Array对象提供了一个叫concat()方法&#xff0c;连接两个或更多的数组&#x…...

javascript基础二十五:说说你对函数式编程的理解?优缺点?

一、是什么 函数式编程是一种"编程范式"&#xff08;programming paradigm&#xff09;&#xff0c;一种编写程序的方法论 主要的编程范式有三种&#xff1a;命令式编程&#xff0c;声明式编程和函数式编程 相比命令式编程&#xff0c;函数式编程更加强调程序执行…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让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求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

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

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...