C++ STL之deque的理解及使用

文章目录

  • 1. 介绍
  • 2. 实现原理（简单理解）
  • 3. deque的优缺点
  • 4. deque类的使用
    • 4.1 deque类对象的构造函数
    • 4.2 deque类对象的容量操作
    • 4.3 deque类对象的修改操作
    • 4.4 deque类对象的访问及遍历操作

1. 介绍

deque(双端队列)：是一种双开口的连续空间的容器，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高，且支持下标访问。

在这里插入图片描述

2. 实现原理（简单理解）

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

在这里插入图片描述

这里如果中控数组满了，扩容的代价是很低的，只需要将指针变量数组扩容即可。

双端队列底层是一段假象的连续空间，实际是分段连续的，所以维护其整体连续以及随机访问的假象的任务就落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

在这里插入图片描述

3. deque的优缺点

  • 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的。
  • 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段，且支持下标访问。

但是，deque 有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。

为什么选择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 没有迭代器），只需要在固定的一端或者两端进行操作，使用deque效率很高。

  2. 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。

所以 stack 和 queue 结合了 deque 的优点，而完美的避开了其缺陷。

4. deque类的使用

4.1 deque类对象的构造函数

(constructor)构造函数代码功能说明
explicit deque (const allocator_type& alloc = allocator_type());（默认构造函数）构造一个空的容器，没有任何元素。
explicit deque (size_type n, const value_type& val = value_type(), onst allocator_type& alloc = allocator_type());（填充构造函数）构造一个包含 n 个元素的容器，每个元素都是 val 的副本。
template <class InputIterator>
deque (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());		（范围构造函数）根据范围[first, last)中的元素构造一个容器，容器中的元素个数与该范围中的元素个数相同，并且顺序相同。
deque (const deque& x);（拷贝构造函数）构造一个容器，其中的每个元素都是 x 中对应元素的副本，顺序相同。

4.2 deque类对象的容量操作

函数名称代码功能说明
sizesize_type size() const;返回 deque 容器中元素个数。
max_sizesize_type max_size() const;返回 deque 容器可以容纳最大元素个数。
resizevoid resize (size_type n, value_type val = value_type());调整容器的大小，使其包含 n 个元素。如果 n 小于当前容器的大小，容器的内容将被减少到前 n 个元素，移除超出范围的元素。如果 n 大于当前容器的大小，容器的内容将通过在末尾插入足够数量的元素来扩展到大小为 n。如果指定了 val，新插入的元素将被初始化为 val 的副本；否则，它们将进行值初始化。
emptybool empty() const;返回 deque 容器是否为空（即其大小是否为 0）。

4.3 deque类对象的修改操作

函数名称代码功能说明
push_backvoid push_back (const value_type& val);在 deque 容器开头插入一个新元素 val。
push_frontvoid push_front (const value_type& val);在 deque 容器开头插入一个新元素 val。
pop_backvoid pop_back();删除最后一个元素。
pop_frontvoid pop_front();删除第一个元素。
insertiterator insert (iterator position, const value_type& val);
void insert (iterator position, size_type n, const value_type& val);
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);		在指定位置 position 之前插入新元素 val、n 个 val或者迭代器区间[first, last)范围的元素。
eraseiterator erase (iterator position);
iterator erase (iterator first, iterator last);		删除 position 位置的元素或者迭代器区间[first, last)范围的元素。
swapvoid swap (deque& x);与另一个相同类型的 deque 容器 x 交换内容。存在一个同名的非成员函数 swap，重载该算法的意义是优化交换时间。
clearvoid clear();从 deque 容器中移除所有元素，使容器的大小变为0。

4.4 deque类对象的访问及遍历操作

函数名称代码功能说明
operator[]reference operator[] (size_type n);
const_reference operator[] (size_type n) const;		返回 deque 容器中位置 n 处的元素的引用。
at reference at (size_type n);
const_reference at (size_type n) const;		返回 deque 容器中位置 n 处的元素的引用。该函数会自动检查 n 是否在 deque 容器的有效元素范围内，如果不在范围内（即 n 大于或等于向量的大小），则抛出 out_of_range 异常。这与成员运算符 operator[] 不同，后者不进行边界检查。
frontreference front();
const_reference front() const;		返回 deque 容器中第一个元素的引用。
backreference back();
const_reference back() const;		返回 deque 容器中最后一个元素的引用。

遍历操作

遍历操作

#include <iostream>
#include <deque>

int main()
{
	std::deque<int> dq(10, 100);
	// 1.普通下标遍历
	for (size_t i = 0; i < dq.size(); ++i)
		std::cout << dq[i] << " ";
	std::cout << '\n';

	// 2.迭代器遍历
	for (std::deque<int>::iterator it = dq.begin(); it != dq.end(); ++it)
		std::cout << *it << " ";
	std::cout << '\n';

	// 3.范围for遍历
	for (auto e : dq)
		std::cout << e << " ";
	std::cout << '\n';

	return 0;
}

输出结果

在这里插入图片描述

说明

  1. 普通下标遍历：
    在此代码段中，通过使用普通的下标操作符 []，从索引 0 开始，逐个访问 deque 容器dq 中的元素，并将其打印出来。循环变量 i 从 0 递增到 dq.size()-1，并使用 dq[i] 访问每个元素。最后，打印一个换行符。
  2. 迭代器遍历：
    在此代码段中，使用迭代器进行遍历。首先，通过 dq.begin() 获取 deque 容器 dq 的起始迭代器，通过 dq.end() 获取 deque 容器 dq 的结束迭代器。然后，通过迭代器 it 遍历从起始迭代器到结束迭代器之间的所有元素，并使用 *it 打印每个元素的值。最后，打印一个换行符。
  3. 范围for循环遍历：
    在此代码段中，使用范围for循环对 deque 容器 dq 进行遍历。对于 deque 容器 dq 中的每个元素，将其依次赋值给循环变量 e，然后打印出 e 的值。此方法不需要显式地使用迭代器或下标来访问向量的元素，因为范围for循环会自动处理迭代过程，并在每次迭代中将元素赋值给循环变量。最后，打印一个换行符。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/346125.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

UCAS-AOD遥感旋转目标检测数据集——基于YOLOv8obb，map50已达96.7%

UCAS-AOD遥感旋转目标检测数据集——基于YOLOv8obb，map50已达96.7%

1.UCAS-AOD简介 1.1数据说明 遥感图像&#xff0c;又名高分辨率遥感图像。遥感图像的分类依据是根据成像的介质不同来进行分类的。UCAS-AOD (Zhu et al.&#xff0c;2015)用于飞机和汽车的检测&#xff0c;包含飞机与汽车2类样本以及一定数量的反例样本&#xff08;背景&…
阅读更多...
第4章 面向对象（下）

第4章 面向对象（下）

4.1 继承 4.1.1 继承的概念 在现实生活中&#xff0c;继承一般指的是子女继承父辈的财产。在程序中&#xff0c;继承描述的是事物之间的所属关系&#xff0c;通过继承可以使多种事物之间形成一种关系体系。例如&#xff0c;猫和狗都属于动物&#xff0c;程序中便可以描述为猫…
阅读更多...
2017年认证杯SPSSPRO杯数学建模C题(第二阶段)移动端考研产品的春天真的到来了吗全过程文档及程序

2017年认证杯SPSSPRO杯数学建模C题(第二阶段)移动端考研产品的春天真的到来了吗全过程文档及程序

2017年认证杯SPSSPRO杯数学建模 C题 移动端考研产品的春天真的到来了吗 原题再现&#xff1a; 2017 年的全国硕士研究生招生考试共有 201 万人报名参加&#xff0c;比去年增加了 24 万名考生&#xff0c;增加 13.56%。看起来新一轮的考研热潮即将到来&#xff0c;而考研教学和…
阅读更多...
JAVA工程中引用本地jar的3种常用方式，你用过哪种?

JAVA工程中引用本地jar的3种常用方式，你用过哪种?

文章目录 前言1. 第1种方式2. 第2种方式3. 第3种方式 前言 实际项目过程中咱们经常会碰到需要本地引用jar包到java工程中的场景&#xff0c;本文就介绍一下遇到此场景时如何在IDEA中导入本地jar包到工程中的3种方式&#xff0c;简单却很常用。 1. 第1种方式 IDEA -> File …
阅读更多...
MySQL函数—流程函数

MySQL函数—流程函数

MySQL函数—流程函数&#xff1a;用于实现条件筛选&#xff0c;从而题搞语句的效率。 MySQL函数—流程函数 函数功能IF(value,t,f)如果value为true&#xff0c;则返回t&#xff0c;否则返回fIFNULL(value1,value2)如果value1不为空&#xff0c;返回value1&#xff0c;否则返回v…
阅读更多...
单点登陆（SSO）基于CAS实现前后端分离的SSO系统开发「IDP发起」

单点登陆（SSO）基于CAS实现前后端分离的SSO系统开发「IDP发起」

关于其他前端常见登录实现单点登录方案&#xff0c;请见「前端常见登录实现方案 单点登录方案 」 前沿 单点登录&#xff08;SSO&#xff09;&#xff0c;英文全称为 Single Sign On。 SSO 是指在多个应用系统中&#xff0c;用户只需要登录一次&#xff0c;就可以访问所有相互…
阅读更多...
分布变化下的Test-Time adaption 综述

分布变化下的Test-Time adaption 综述

论文 https://arxiv.org/abs/2303.15361 代码 https://github.com/tim-learn/awesome-test-time-adaptation &#xff08;其实这是相关领域代码和论文合集之类的东西&#xff09; Abstract 机器学习方法努力在训练过程中获得一个鲁棒模型&#xff0c;即使在分布变化的情况下…
阅读更多...
RDMA vs InfiniBand 网卡接口如何区分？

RDMA vs InfiniBand 网卡接口如何区分？

(该架构图来源于参考文献) 高性能计算网络&#xff0c;RoCE vs. InfiniBand该怎么选&#xff1f; 新 RoCEv2 标准可实现 RDMA 路由在第三层以太网网络中的传输。RoCEv2 规范将用以太网链路层上的 IP 报头和 UDP 报头替代 InfiniBand 网络层。这样&#xff0c;就可以在基于 IP…
阅读更多...
向日葵远程控制Mac版权限设置教程解决远程无法控制问题

向日葵远程控制Mac版权限设置教程解决远程无法控制问题

很多Mac新手安装向日葵远程控制Mac版后&#xff0c;根据提示设置了权限后发现无法远程控制&#xff0c;其实主要是你只勾选了中文的“向日葵权限选项“&#xff0c;而忘记了勾选了向日葵另外一个英文选项权限。 判断是否完全开启控制权限 打开向日葵访问权限设置面板&#xf…
阅读更多...
gitlab runner 安装、注册、配置、使用

gitlab runner 安装、注册、配置、使用

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…
阅读更多...
Unity Mask合批情况验证

Unity Mask合批情况验证

1.首先是两个Mask完全重合的情况下 每张图片使用的image都来自同一个图集 发现彼此之间是没有合批的&#xff0c;但是每个Mask内部是实现了合批的 经过计算此种情况的visiableList&#xff1a;mask1&#xff0c;IM1&#xff0c;IM2&#xff0c;mask2&#xff0c;IM3&#xf…
阅读更多...
实时渲染 -- 光追（Ray Tracing)

实时渲染 -- 光追（Ray Tracing)

光栅化 Or 光线追踪 传统的光栅化方式主要是将每个物体进行光栅化后形成若干个像素&#xff0c;然后每个像素需要计算光源直接照射到自己并反射回眼睛而形成的颜色。这种算法方式是极快的&#xff0c;但是只能表示直接光照&#xff0c;图像质量较低。 Bling-Phong 模型是一个常…
阅读更多...
Java 集合List相关面试题

Java 集合List相关面试题

&#x1f4d5;作者简介&#xff1a; 过去日记&#xff0c;致力于Java、GoLang,Rust等多种编程语言&#xff0c;热爱技术&#xff0c;喜欢游戏的博主。 &#x1f4d7;本文收录于java面试题系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏Rust初阶教程、go语言基…
阅读更多...
IDEA插件(MyBatis Log Free)

IDEA插件(MyBatis Log Free)

引言 在Java开发中&#xff0c;MyBatis 是一款广泛使用的持久层框架&#xff0c;它简化了SQL映射并提供了强大的数据访问能力。为了更好地调试和优化MyBatis应用中的SQL语句执行&#xff0c;一款名为 MyBatis Log Free 的 IntelliJ IDEA 插件应运而生。这款插件旨在帮助开发者…
阅读更多...
2023-2024年重庆职业院校技能大赛“信息安全管理与评估”比赛样题

2023-2024年重庆职业院校技能大赛“信息安全管理与评估”比赛样题

2023 年重庆职业院校技能大赛&#xff08;高等职业教育&#xff09; “信息安全管理与评估”样题任务书 第一阶段&#xff1a;任务 1 网络平台搭建&#xff08;50 分&#xff09;任务 2 网络安全设备配置与防护&#xff08;250 分&#xff09; 第二阶段&#xff1a;第一部分 网…
阅读更多...
C语言王道练习题第七周两题

C语言王道练习题第七周两题

第一题 Description 输入一个学生的学号&#xff0c;姓名&#xff0c;性别&#xff0c;用结构体存储&#xff0c;通过 scanf 读取后&#xff0c;然后再 通过 printf 打印输出 Input 学号&#xff0c;姓名&#xff0c;性别&#xff0c;例如输入 101 xiongda m Output 输出…
阅读更多...
Linux系统Shell脚本编程之条件语句

Linux系统Shell脚本编程之条件语句

一、条件测试 Shell 环境根据命令执行后的返回状态值 " $? " 来判断是否执行成功&#xff0c;当返回值为0时表示成功&#xff0c;否则表示失败或异常&#xff08;非0值&#xff09;。使用专门的测试工具 test 命令&#xff0c;可以对特定条件进行测试&#xff0c;并…
阅读更多...
【Vue3】组件通信

【Vue3】组件通信

Vue3组件通信和Vue2的区别&#xff1a; 移出事件总线&#xff0c;使用mitt代替。vuex换成了pinia。把.sync优化到了v-model里面了。把$listeners所有的东西&#xff0c;合并到$attrs中了。$children被砍掉了。 1. props 若 父传子&#xff1a;属性值是非函数。若 子传父&…
阅读更多...
网络协议与攻击模拟_08DHCP协议

网络协议与攻击模拟_08DHCP协议

技术学习要了解某项技术能干什么&#xff1f;它的详细内容&#xff1f;发展走向&#xff1f; 一、DHCP协议 1、DHCP基本概念 dhcp动态主机配置协议&#xff0c;广泛应用于局域网内部 主要是为客户机提供TCP/IP 参数&#xff08;IP地址、子网掩码、网关、DNS等&#xff09;…
阅读更多...
【AI】深度学习与图像描述生成——看图说话（1）

【AI】深度学习与图像描述生成——看图说话（1）

还记得我闲来无事&#xff0c;用大模型来“洗图”吗&#xff0c;就是想抄袭别人的图&#xff0c;但是又要装作原创的样子。因为洗稿大家都熟悉&#xff0c;洗图其实也是一样的。 【AIGC】今天想用AI“洗个图”&#xff0c;失败了&#xff0c;进来看我怎么做的-CSDN博客 【AIG…
阅读更多...
最新文章

Copyright @ 2022~2023