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

C++ : STL容器(适配器)之stack、queue剖析

在这里插入图片描述

STL容器适配器之stack、queue剖析

  • 一、stack、queue的接口
    • (一)stack 接口说明
    • (二)queue 接口说明
  • 二、stack、queue的模拟实现
    • (一)stack、queue是容器适配器
      • stack、queue底层默认容器--deque
        • 1、deque概念及原理
        • 2、stl中deque迭代器的实现(部分)
    • (二)stack的模拟实现
    • (三)queue的模拟实现
  • 三、优先队列
    • (一)优先队列的概念
    • (二)优先队列的接口说明
    • (三)优先队列的模拟实现
  • 四、结束语

一、stack、queue的接口

(一)stack 接口说明

  • stack()
    • 构造空的栈
  • empty()
    • 检测stack是否为空
  • size()
    • 返回stack中元素的个数
  • top()
    • 返回栈顶元素的引用
  • push()
    • 将元素val压入stack中
  • pop()
    • 将stack中尾部的元素弹出

(二)queue 接口说明

  • empty:
    • 检测队列是否为空
  • size:
    • 返回队列中有效元素的个数
  • front:
    • 返回队头元素的引用
  • back:
    • 返回队尾元素的引用
  • push_back:
    • 在队列尾部入队列
  • pop_front:
    • 在队列头部出队列

二、stack、queue的模拟实现

(一)stack、queue是容器适配器

虽然stackqueue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stackqueue只是对其他容器的接口进行了包装,STL中stackqueue默认使用deque.

stack、queue底层默认容器–deque

1、deque概念及原理

deque(双端队列):可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个
动态的二维数组,其底层结构如下图所示:
在这里插入图片描述

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问
的假象,落在了deque的迭代器身上

2、stl中deque迭代器的实现(部分)

在这里插入图片描述
在stl源码实现中,下面截取了迭代器的部分,有很多知识值得学习。

1、普通迭代器和const迭代器实现技巧

我们知道const对象的实现就是不能修改值,因此只需要在实现迭代器时针对一下->*的返回值即可,源码库中使用两个模板参数巧妙的解决这个问题。

2、非类型模板参数

在模板进阶中我们会讲到非类型模板参数的使用,使用size_t作为参数相当于一个宏的使用。
template <class T, class Ref, class Ptr, size_t BufSiz>

3、重载的复用

先实现重载符号 += 接着的 +、-、-=都采用了复用的方式,使得代码更简洁。
在实现++、–时,先实现前置++,前置–,再实现后置++,后置–,这里也可以复用

#pragma once
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef T** map_pointer;typedef ptrdiff_t difference_type;typedef __deque_iterator self;//构造函数//有参构造__deque_iterator(T* x, map_pointer y): cur(x), first(*y), last(*y + buffer_size()), node(y) {}//默认构造__deque_iterator() : cur(0), first(0), last(0), node(0) {}//拷贝构造__deque_iterator(const iterator& x): cur(x.cur), first(x.first), last(x.last), node(x.node) {}//更新结点信息void set_node(map_pointer new_node) {node = new_node;first = *new_node;last = first + difference_type(buffer_size());}//运算符重载reference operator*() const { return *cur; }pointer operator->() const { return &(operator*()); }self& operator++() {++cur;if (cur == last) {set_node(node + 1);cur = first;}return *this;}self operator++(int) {self tmp = *this;++*this;return tmp;}self& operator--() {if (cur == first) {set_node(node - 1);cur = last;}--cur;return *this;}self operator--(int) {self tmp = *this;--*this;return tmp;}self& operator+=(difference_type n) {difference_type offset = n + (cur - first);if (offset >= 0 && offset < difference_type(buffer_size()))cur += n;else {difference_type node_offset =offset > 0 ? offset / difference_type(buffer_size()): -difference_type((-offset - 1) / buffer_size()) - 1;set_node(node + node_offset);cur = first + (offset - node_offset * difference_type(buffer_size()));}return *this;}self operator+(difference_type n) const {self tmp = *this;return tmp += n;}self& operator-=(difference_type n) { return *this += -n; }self operator-(difference_type n) const {self tmp = *this;return tmp -= n;}reference operator[](difference_type n) const { return *(*this + n); }bool operator==(const self& x) const { return cur == x.cur; }bool operator!=(const self& x) const { return !(*this == x); }bool operator<(const self& x) const {return (node == x.node) ? (cur < x.cur) : (node < x.node);}//成员变量
private:T* cur;T* first;T* last;map_pointer node;
};

(二)stack的模拟实现

通过stack的实现可以看出,stack的实现是基于deque栈的实现就是将双端队列进行包装,这个过程就像是deque是交流电,而stack就是这个插头,为用户提供需要的接口。

#pragma once
#include<vector>
#include<list>
#include<deque>
using namespace std;namespace wgm {template<class T, class Container = deque<T>>class stack {public:void push(const T& val) {_con.push_back(val);}void pop() {_con.pop_back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T& top()  const{return _con.back();}private:Container _con;};
}

(三)queue的模拟实现

stack类似,在它的参数列表中也有一个参数类型Container(容器),它也存在默认参数deque。这里的参数不能传入vector,因为vector不支持头部出元素的pop_front操作。

#pragma once
#include<vector>
#include<list>
#include<deque>
using namespace std;namespace wgm {template<class T, class Container = deque<T>>class queue {public:void push(const T& val) {_con.push_back(val);}void pop() {_con.pop_front();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T& front() const{return _con.front();}const T& back() const{return _con.back();}private:Container _con;};
}

三、优先队列

(一)优先队列的概念

优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大(小)的。实际上,这就和之前学过的数据结构堆的性质一样。

(二)优先队列的接口说明

  • empty():
    • 检测容器是否为空
  • size():
    • 返回容器中有效元素个数
  • front():
    • 返回容器中第一个元素的引用
  • push_back():
    • 在容器尾部插入元素
  • pop_back():
    • 删除容器尾部元素

(三)优先队列的模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;namespace wgm {template <class T>struct less{bool operator() (const T& x, const T& y) const{return x < y;}};template <class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T , class Container = vector<T>, class Compare = less<T>>class priority_queue {public:
#define FATHER(i) (((i) - 1) / 2)
#define LEFT(i) (((i) * 2) + 1)
#define RIGHT(i) (((i) * 2) + 2)void AdjustUp(int i){Compare cmp;while (FATHER(i) >= 0 && Compare()(_con[FATHER(i)], _con[i])) {swap(_con[i], _con[FATHER(i)]);i = FATHER(i);}}void AdjustDown(int i){while (LEFT(i) < _con.size()) {int l = LEFT(i), r = RIGHT(i), ind = i;Compare cmp;if (cmp(_con[ind], _con[LEFT(i)])) ind = LEFT(i);if (RIGHT(i) < _con.size() && cmp(_con[ind], _con[RIGHT(i)])) ind = RIGHT(i);if (ind == i) break;swap(_con[i], _con[ind]);i = ind;}}void push(const T& val){_con.push_back(val);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}

四、结束语

这个部分相对于之前学的容器要简单,只不过这个双端队列的实现源码还是挺有意思的,可以尝时着实现实现。

相关文章:

C++ : STL容器(适配器)之stack、queue剖析

STL容器适配器之stack、queue剖析 一、stack、queue的接口&#xff08;一&#xff09;stack 接口说明&#xff08;二&#xff09;queue 接口说明 二、stack、queue的模拟实现&#xff08;一&#xff09;stack、queue是容器适配器stack、queue底层默认容器--deque1、deque概念及…...

nuxt3安装pinia报错500[vite-node] [ERR_LOAD_URL]问题解决

按照pinia官网步骤安装运送服务会报一个500[vite-node] [ERR_LOAD_URL]问题,查阅各个网站资料没有找到有用信息. 最后解决:在package.json中把pinia的版本给降回0.5.5版本之后就正常了 "dependencies": {"element-plus/icons-vue": "^2.3.1",&q…...

青少年编程能力等级测评CPA试卷(2)Python编程(一级)

青少年编程能力等级测评CPA试卷&#xff08;2&#xff09; Python编程(一级) &#xff08;考试时间90分钟&#xff0c;满分100分&#xff09; 一、单项选择题&#xff08;共20题&#xff0c;每题3.5分&#xff0c;共70分&#xff09; 下列语句的输出结果是&#xff08; &am…...

wordpress判断page页与非page页

在WordPress中&#xff0c;你可以使用is_page()函数来判断当前页面是否为page类型。以下是如何使用这个函数的示例&#xff1a; <?php if (is_page()) {// 当前页面是page类型echo 这是一个Page页面; } else {// 当前页面不是page类型echo 这不是一个Page页面; } ?> …...

JavaScript 库-qs的使用

meta.query qs.parse(query)语句解析&#xff1a;qs.parse(query) qs 是一个常用的 JavaScript 库&#xff08;全称为 query-string 或 qs&#xff09;&#xff0c;它用于处理 URL 查询字符串。qs.parse(query) 会将查询字符串解析成一个对象。举个例子&#xff1a; 假设有一…...

Leetcode 两数之和 Ⅱ - 输入有序数组

这段代码实现了在一个非递减排序的数组中找到两个数&#xff0c;使它们的和等于目标值的算法。算法使用了双指针技术&#xff0c;具体思想如下&#xff1a; 算法思想&#xff1a; 初始化指针&#xff1a;定义两个指针 left 和 right&#xff0c;分别指向数组的起始位置和末尾位…...

多处理器一致协议(MSI)协议详细介绍

多处理器一致协议 MSI 协议详细介绍 #mermaid-svg-2lc6AxM2mRiND4C0 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-2lc6AxM2mRiND4C0 .error-icon{fill:#552222;}#mermaid-svg-2lc6AxM2mRiND4C0 .error-text{fill:…...

SSH实验5密钥登录Linuxroot用户(免密登录)

当用户尝试通过SSH连接到远程服务器时&#xff0c;客户端会生成一对密钥&#xff1a;公钥和私钥。公钥被发送到远程服务器&#xff0c;并存储在服务器的~/.ssh/authorized_keys文件中。而私钥则由客户端保管&#xff0c;不会传输给服务器。 在连接过程中&#xff0c;客户端使用…...

2024 网鼎杯 - 青龙组 Web WP

2024 网鼎杯 - 青龙组 WEB - 02 打开容器一个登录界面&#xff0c;随便输入账号密码可以进到漏洞界面 这里有一个发送给boss的功能&#xff0c;一眼xss 有三个接口&#xff1a;/flag 、/update 、/submit /flag &#xff1a;要求boss才能访问&#xff0c;/update &#xf…...

ORACLE 闪回技术简介

闪回技术是若干技术的集合 包含对数据库整体的闪回 对表的闪回 对事务的闪回 经典面试题面试题&#xff1a;简述Oracle数据库闪回技术&#xff1f; 1.闪回Oracle数据库 2.闪回表 3.闪回事务 数据库闪回 要想实现数据库闪回 1.必须配置数据库的恢复区 SQL> show parameter …...

【笔记】LLC电路工作频点选择 2-2 开关管与滤波压力

LLC谐振变换器稳态工作波形分析 - 知乎&#xff0c;上面这篇文的结论相较MPS那篇文章的结论更严格。我们分析一下它的频点选择为什么会更窄&#xff1a; 1. LLC电路模型 电流滞后的特性就是电路呈感性注意这里也是开关管ZVS开通。 2.工作循环的波形 iLm的波形&#xff0c;最终…...

【CUDA】认识CUDA

目录 一、CUDA编程 二、第一个CUDA程序 三、CUDA关键字 四、device管理 4.1 初始化 4.2 Runtime API查询GPU信息 4.3 决定最佳GPU CUDA C 编程指南CUDA C在线文档&#xff1a;CUDA C 编程指南 CUDA是并行计算的平台和类C编程模型&#xff0c;能很容易的实现并行算法。只…...

Linux(CentOS)yum update -y 事故

CentOS版本&#xff1a;CentOS 7 事情经过&#xff1a; 1、安装好CentOS 7&#xff0c;系统自带JDK8&#xff0c;版本为&#xff1a;1.8.0_181 2、安装好JDK17&#xff0c;版本为&#xff1a;17.0.13 3、为了安装MySQL执行了 yum update -y&#xff08;这个时候不知道该命令的…...

AI绘画赚钱秘籍!掌握ai绘画赚钱技巧,开启副业新篇章,ai绘画赚钱实战指南!

AI绘画赚钱&#xff1a;方法与策略 一、引言 ​ 随着人工智能技术的日益发展&#xff0c;AI绘画作为新兴领域&#xff0c;正逐渐成为赚钱的新途径。本文将从多个角度探讨AI绘画赚钱的完整策略&#xff0c;帮助读者深入了解并把握这一领域的商机。 二、AI绘画赚钱的主要方式…...

HCIP-HarmonyOS Application Developer V1.0 笔记(四)

平板/折叠屏设计 自适应动态布局&#xff1a;相对拉伸、相对缩放、延伸布局 响应式动态布局&#xff1a;挪移布局、重复布局、瀑布布局 Sketch 插件 设计系统&#xff1a;提供了 HarmonyOS 设计语言中定义的视觉参数和设计资源文件。 控件库&#xff1a;按类别组织控件&…...

【前端】Svelte:组件封装与使用

在 Svelte 中&#xff0c;组件化是开发的核心理念。将页面的不同部分封装成独立组件&#xff0c;不仅可以提升代码的复用性&#xff0c;还能让项目的结构更加清晰。在本文中&#xff0c;我们将介绍如何创建、封装、引入和使用 Svelte 组件&#xff0c;帮助你快速上手 Svelte 的…...

STM32标准库-待机模式

1.1 STM32待机模式简介 STM32单片机具有低功耗模式&#xff0c;包括睡眠、停止和待机三种。 运行状态下&#xff0c;HCLK为CPU提供时钟。HCLK由AHB预分频器分频后直接输出得到。 低功耗模式选择需考虑电源消耗、启动时间和唤醒源。 睡眠模式停CPU不停外设时钟&#xff1b; 停止…...

【论文笔记】The Power of Scale for Parameter-Efficient Prompt Tuning

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: The Power of Scale for P…...

几个docker可用的镜像源

几个docker可用的镜像源 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; sudo rm -rf /etc/docker/daemon.json sudo mkdir -p /etc/dockersudo tee /etc/docker/daemon.json <<-EOF {"registry-mirrors": ["https://d…...

Spring学习笔记_27——@EnableLoadTimeWeaving

EnableLoadTimeWeaving 1. 介绍 在Spring框架中&#xff0c;EnableLoadTimeWeaving 是一个注解&#xff0c;它用于启用加载时织入&#xff08;Load-Time Weaving, LTW&#xff09; LWT[Spring学习笔记_26——LWT-CSDN博客] 2. 场景 AOP&#xff1a;在Spring框架中&#xf…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...