当前位置: 首页 > 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;函数式编程更加强调程序执行…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...