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

C++ 浅谈之 STL Deque

C++ 浅谈之 STL Deque

HELLO,各位博友好,我是阿呆 🙈🙈🙈

这里是 C++ 浅谈系列,收录在专栏 C++ 语言中 😜😜😜

本系列阿呆将记录一些 C++ 语言重要的语法特性 🏃🏃🏃

OK,兄弟们,废话不多直接开冲 🌞🌞🌞


一 🏠 概述

简单介绍

Deque 双端队列,在头尾对元素进行删除和插入快,中间插入或删除效率低,支持元素随机访问。它是动态分段连续空间组合而成,无 capacity 概念,可即时增加新空间(不会像 vector 因旧空间不足而重新申请)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JUQ3IwMY-1675954090283)(E:\2022年MD文档\2023 年 MD文档\二月\浅谈系列\C++ 浅谈之 STL Deque.assets\1675951423972.png)]

和 Vector 维护连续线性空间不同,Deque 维护多段连续空间,各段间不一定连续,Deque 用数组(名为 map)存储着各连续空间首地址 👦👦👦

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fJg1VBNk-1675954090285)(E:\2022年MD文档\2023 年 MD文档\二月\浅谈系列\C++ 浅谈之 STL Deque.assets\1675951752739.png)]


迭代器

分段存储提高了两端添加,删除的效率,也使容器迭代器实现更复杂,有如下 2 个问题

① 迭代器遍历时,须确认各连续空间在 map 数组中的位置 👨‍🚀👨‍🚀👨‍🚀

② 迭代器在某个连续空间时,须知道是否处于空间边缘(一旦前进,需要跳到下一个连续空间)

//迭代器内部实现如上,包含 4 个指针
template<class T,...>
struct __deque_iterator{...T* cur; //指向当前正在遍历的元素T* first; //指向当前连续空间的首地址T* last; //指向当前连续空间的末尾地址map_pointer node; //T** 二级指针, 指向 map 数组中存储的指向当前连续空间的指针
}

借助这四个指针和运算符重载,使迭代器可以在分段连续空间遍历 🎅🎅🎅

//当迭代器处于当前连续空间边缘的位置时,如果继续遍历,就需要跳跃到其它的连续空间中,该函数可用来实现此功能
void set_node(map_pointer new_node){node = new_node;//记录新的连续空间在 map 数组中的位置first = *new_node; //更新 first 指针//更新 last 指针,difference_type(buffer_size())表示每段连续空间的长度last = first + difference_type(buffer_size());
}//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}//重载前置 ++ 运算符
self & operator++(){++cur;//处理 cur 处于连续空间边缘的特殊情况if(cur == last){//调用该函数,将迭代器跳跃到下一个连续空间中set_node(node+1);//对 cur 重新赋值cur = first;}return *this;
}//重置前置 -- 运算符
self& operator--(){//如果 cur 位于连续空间边缘,则先将迭代器跳跃到前一个连续空间中if(cur == first){set_node(node-1);cur == last;}--cur;return *this;
}

二 🏠 核心

底层实现

STL Deque 有如下的定义代码 👇👇👇

//_Alloc为内存分配器
template<class _Ty,class _Alloc = allocator<_Ty>>
class deque{...
protected:iterator start; // map 数组中首个连续空间的信息iterator finish; //map 数组中最后一个连续空间的信息map_pointer map;
...
}

内部空间布局,如下图所示 🐳🐳🐳

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gbKUALTy-1675954090286)(E:\2022年MD文档\2023 年 MD文档\二月\浅谈系列\C++ 浅谈之 STL Deque.assets\1675951491835.png)]

三 🏠 结语

身处于这个浮躁的社会,却有耐心看到这里,你一定是个很厉害的人吧 👍👍👍

各位博友觉得文章有帮助的话,别忘了点赞 + 关注哦,你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容,加油吧!技术人! 💪💪💪

相关文章:

C++ 浅谈之 STL Deque

C 浅谈之 STL Deque HELLO&#xff0c;各位博友好&#xff0c;我是阿呆 &#x1f648;&#x1f648;&#x1f648; 这里是 C 浅谈系列&#xff0c;收录在专栏 C 语言中 &#x1f61c;&#x1f61c;&#x1f61c; 本系列阿呆将记录一些 C 语言重要的语法特性 &#x1f3c3;&a…...

Koa2-项目中的基本应用

文章目录安装配置koa2配置nodemon,热更新我们的项目中间件什么是中间件&#x1f47b;洋葱模型路由中间件连接数据库 - mysql后端允许跨域处理请求getpostputdelete后续会继续更新安装配置koa2 &#x1f47b;安装 koa2 npm i koa2 -s&#x1f47b;在package.json 配置,当然是在…...

Flask入门(2):配置

目录2.Flask配置2.1 直接写入主脚本2.2 系统环境变量2.3 单独的配置文件2.4 多个配置类2.5 Flask内置配置2.Flask配置 我们都知道&#xff0c;Flask应用程序肯定是需要各种各样的配置。来满足我们不同的需求的&#xff0c;这样可以使我们的应用程序更加灵活。比如可以根据需要…...

Linux--fork

一、fork入门知识 fork&#xff08;&#xff09;函数通过系统调用创建一个与原来进程几乎完全相同的进程&#xff0c;也就是两个进程可以做完全相同的事&#xff0c;但如果初始参数或者传入的变量不同&#xff0c;两个进程也可以做不同的事。可以简单地说fork()的作用就是创建一…...

计算机组成原理(一)

1.了解计算机硬件的发展和软件的发展历程&#xff1b; 硬件&#xff1a;   电子管时代&#xff08;1946-1959&#xff09;&#xff1a;电子管、声汞延迟线、磁鼓   晶体管时代&#xff08;1959-1964&#xff09;&#xff1a;晶体管、磁芯   中、小规模集成电路时代&#…...

【SpringBoot】实现Async异步任务

1. 环境准备 在 Spring Boot 入口类上配置 EnableAsync 注解开启异步处理。 创建任务抽象类 AbstractTask&#xff0c;并分别配置三个任务方法 doTaskOne()&#xff0c;doTaskTwo()&#xff0c;doTaskThree()。 public abstract class AbstractTask {private static Random r…...

Node =>Express学习

1.Express 能做什么 能快速构建web网站的服务器 或 Api接口的服务期 Web网站服务器&#xff0c;专门对外提供Web网页资源的服务器Api接口服务器&#xff1a;专门对外提供API接口的服务器 2.安装 在项目所处的目录中&#xff0c;运行以下命令&#xff0c;简装到项目中了 npm …...

QT基础入门【布局篇】消除控件之间的间隔

一、相关参数 layoutLeftMargin: layout内的布局距离边框左端的距离。 layoutTopMargin: layout内的布局距离边框顶端的距离。 layoutRightMargin: layout内的布局距离边框右端的距离。 layoutBottomMargin: layout内的布局距离边框底端的距离。 layoutHorizontalSpacing: layo…...

vue脚手架 element-ui spring boot 实现图片上传阿里云 并保存到数据库

一.阿里云 注册登陆就不讲了&#xff0c;登陆进去后如下操作 1. 进入对象存储OSS 创建一个新的Bucket 随后点击新建的bucket 2.去访问RAM 前往RAM控制台 3.去创建用户 4.创建密匙 5.随后返回RAM控制台 给用户增加权限&#xff0c;文件上传所需权限&#xff0c;需要带含有…...

【FPGA】Verilog:组合电路 | 3—8译码器 | 编码器 | 74LS148

前言&#xff1a;本章内容主要是演示Vivado下利用Verilog语言进行电路设计、仿真、综合和下载 示例&#xff1a;编码/译码器的应用 ​ 功能特性&#xff1a; 采用 Xilinx Artix-7 XC7A35T芯片 配置方式&#xff1a;USB-JTAG/SPI Flash 高达100MHz 的内部时钟速度 存储器&…...

GLP-1类药物研发进展-销售数据-上市药品前景分析

据一项2021 年的报告发现&#xff0c;当 GLP-1 类似物用于治疗 2 型糖尿病时&#xff0c;全因死亡率降低了 12%&#xff0c;它们不仅降糖效果显著&#xff0c;同时还兼具减重、降压、改善血脂谱等作用。近几年&#xff0c;随着GLP-1R激动剂类药物市场规模不断增长&#xff0c;美…...

C++远程监控系统接收端- RevPlayMDIChildWnd.cpp

void CRevPlayWnd::InitMultiSock() { int RevBuf; int status; BOOL bFlag; CString ErrMsg; SOCKADDR_IN stLocalAddr; SOCKADDR_IN stDestAddr; SOCKET hNewSock; int RevLensizeof(RevBuf); //创建一个IP组播套接字 MultiSock W…...

QT之OpenGL深度测试

QT之OpenGL深度测试1. 深度测试概述1. 1 提前深度测试1.2 深度测试相关函数2. 深度测试精度2.1 深度冲突3. Demo4. 参考1. 深度测试概述 在OpenGL中深度测试(Depth Testing)是关闭的&#xff0c;此时在渲染图形时会产生一种现象后渲染的会把最先渲染的遮挡住。而在启用深度测试…...

用LCR测试仪测试无线充电系统中的线圈

宽阻抗范围用来表征电感和质量因数– 高精度 DCR 测量– 制造环节快速测量– 大量夹具可供选择智能终端上不断增加新功能&#xff0c;电池寿命成为用户最头痛的问题之一。相比便携式电源和电缆供电而言&#xff0c;无线充电技术因其方便性和多功能性获得了很大的关注&#xff0…...

华为、南卡和漫步者蓝牙耳机怎么选?国产高性价比蓝牙耳机推荐

随着蓝牙耳机的快速发展&#xff0c;现如今使用蓝牙耳机的人也越来越多。其中&#xff0c;日益增多的国产蓝牙耳机品牌也逐渐被大众认识、认可。目前一些热销的国产蓝牙耳机&#xff0c;如华为、南卡和漫步者等都是大家比较熟知的品牌。那么&#xff0c;这三个品牌哪个性价比高…...

MySQl学习(从入门到精通12)

MySQl学习&#xff08;从入门到精通12&#xff09;第 15 章_存储过程与函数1. 存储过程概述1. 1 理解1. 2 分类2. 创建存储过程2. 1 语法分析2. 2 代码举例3. 调用存储过程3. 1 调用格式3. 2 代码举例3. 3 如何调试4. 存储函数的使用4. 1 语法分析4. 2 调用存储函数4. 3 代码举…...

08讲 | 基于STM32单片机NBIOT定位实战项目

前言 绘制基于 STM32 单片机的 NBIOT 实战开发板。 文章目录前言一、原理图1、绘制1&#xff09;电源供电a、USB 转 TTL 电路b、锂电池充电管理电路c、3.3V电压转换电路d、一键开关机电路2&#xff09;单片机最小系统3&#xff09;ADC电压转换电路4&#xff09;NBIOT 模组串口电…...

提取接近竖直物体(粗定位)

由于项目的需要提取图像之中的一个接近于竖直的物体&#xff0c;一般的方法是进行图像分割&#xff0c;分割方式使用什么OTSU方式以及hsv方法等等。但是项目中使用的相机是黑白相机&#xff0c;会受到一定的限制。因此想到的是使用线条提取方式。线条提取方式之中最好的方法是使…...

程序环境和预处理

目录一、程序的翻译环境和执行环境二、编译链接2.1 翻译环境2.2 编译2.2.1 预处理2.2.2 编译2.2.3 汇编2.3 链接2.4 结果三、运行环境四、预处理详解4.1 #define4.1.1 #define定义标识符4.1.2 #define定义宏4.1.3 #define 替换规则4.1.4 #和##4.1.5 带副作用的宏参数4.1.6 宏和…...

财报解读:业务复苏迹象明显,中国中免能否重写增长神话?

2月3日&#xff0c;中国中免披露2022年度业绩快报&#xff0c;2022年总营收为544.63亿元&#xff0c;同比下降19.52%&#xff1b;实现归属于上市公司股东的净利润50.25亿元&#xff0c;同比下降47.95%。来源&#xff1a;中国中免2022年度业绩快报业绩近乎腰斩&#xff0c;但从长…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

网站指纹识别

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

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...