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

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...