C++容器适配器与stack，queue，priority_queue（优先级队列）的实现以及仿函数（函数对象）与deque的简单介绍

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉 ————————————————

🎉文章简介：

🎉本篇文章将 学习c++容器适配器与stack，queue应用适配器实现 相关知识进行分享！
💕如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加 油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉
——————————————————

一.容器适配器

一.什么是容器适配器

容器适配器是一种设计模式，它通过封装现有的序列容器类，并重定义其成员函数，以提供不同的功能或满足特定的需求。这种适配器类似于电源适配器，它将不兼容的电源（如不同国家的电压标准）转换可用的电源（即适合电器使用的电压），以便用户能够方便地使用各种电器。

在计算机编程中，容器适配器允许程序员使用已经存在的序列容器类（如vector、deque、list等），同时获得预定义的特定功能，如stack实现后进先出（LIFO）存储、queue实现先进先出（FIFO）存储、以及priority_queue实现基于优先级的存储。

容器适配器本质上是容器的一种变体，它利用了其他基础容器模板类中已经实现的成员函数，并在必要时添加或创新自己的成员函数。

如图：
在这里插入图片描述

二.STL中stack，queue在底层中的结构

STL中stack与queue不属于容器，而是容器适配器，他们是基于已经存在的类（容器）上面，对该类（容器）的接口进行了包装，STL中stack和queue默认使用deque；

们可以通过文档发现：
如图：
在这里插入图片描述
在这里插入图片描述

二.相关适配器的介绍及实现

简单的说，这里的适配器的实现，就是在一个类里面，定义一个其他容器的对象A（能支持该适配器B的功能），然后在实现 B 所需要的函数的时候，在函数里面调用 A的成员函数 来实现 B的函数 或则 B函数 的某部分，然而实现B；
可以结合下面的例子看看：

一.stack

一.stack的介绍

stack的文档 link
1. stack是一种容器适配器，具有 后进先出 的特点，是只允许在一端进行删除，插入，提取操作的容器适配器；

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

后进先出特点
在这里插入图片描述

相关函数
在这里插入图片描述

二.实现：
  //这里的Cintainer不确定是什么，默认不传我们给的是deque<int>，和库里面一致
	template<class T, class Container=deque<int>>  //模板参数是传类型
	class stack
	{
	public:
		stack()         //初始化，会去调用对象_con的构造函数
			:_con()     //这里_con默认是deque
		{
		}
		void push(const T& x)    //这里成员函数名可以自己随便修改，这里是为了和库里面的一致
		{
			_con.push_back(x);    //这里调用的函数必须是对象_con的成员函数，并且名字必须相同
		}
		void pop()         
		{
			_con.pop_back();   //下面的调用和上面的都类似
		}
		T& top()
		{
			return _con.back();   //调用_con的取头数据函数
		}
		bool empty()
		{
			return _con.empty();    //调用_con的判空函数
		}
		size_t size()
		{
			return _con.size();    //调用_con的size()函数
		}
	private:     
		Container _con;       //声明一个Container对象
	};

stack的实现完全就是自己什么都不做，全去调用Contaoner的成员函数就可以实现的，下面的queue也是一样；

二.queue

一.queue的介绍

queue文档链接: link

1. 队列是一种容器适配器，专门用于在先进先出（比如现实中取号排队的问题，越早取号的先）中操作，其中从容器一端插入元素，另一端提取元素；

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

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

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

先进先出 特点
在这里插入图片描述
函数使用
在这里插入图片描述

二.实现

与stack的实现一样

template<class T,class Container=deque<int>>   //库里面一致，默认是deque<int>
class quque
{
public:
	quque()
		:_con()
	{}
	void push(const T& x)
	{
		_con.push_back(x);    //调用_con的成员函数
	}
	void pop()
	{
		_con.pop_front();
	}
	T& top()
	{
		return _con.front();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

三.priority_queue

一.priority_queue的介绍

priority_queue文档链接: link

1. 优先队列是一种容器适配器，类似于堆，默认情况下是大堆，即堆顶的元素总是它所包含的元素中最大的；

2. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

3. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。因为vector支持下标随机访问

4.需要支持随机访问迭代器，以便始终在内部保持堆结构；
支持以下操作：

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

函数使用
在这里插入图片描述

.实现

仿函数的简单介绍

仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了；
有了仿函数类过后，再结合模板使用，就可以使一些需要重复使用的代码独立出来，以便下次复用，这样有利于资源的管理（这点可能是它相对于函数最显著的优点了）。

就比如下面我们所需要实现的优先队列，默认的是大堆（如图，库里面是反着的，less是大堆，greater是小堆），当我们想要小堆的时候，就需要用仿函数，这样只需要我们再使用优先级队列时改变传的模板参数即可；
在这里插入图片描述

向上调整与向下调整思想及图解链接: link

template<class T>
class lesser               //定义一个类
{
public:
	bool operator()(const T& x, const T& y)   //重载operator()
	{
		return x < y;                  //小于的比较逻辑
	}
};
template<class T>                 //定义一个类
class greater
{
public:
	bool operator()(const T& x, const T& y)     //重载operator()
	{
		return x > y;              //大于的比较逻辑
	}
};
namespace P
{                         
	template<class T, class Container=vector<int>,class Compare= less<int> >
	class priority_quque
	{
	public:
		priority_quque()
			:_con()
		{}
		void AdjustUp(int child)
		{
			Compare _com;
			int parent = (child - 1) / 2;
			while (parent >= 0)
			{
				if(_com(_con[child],_con[parent]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(int parent)
		{
			Compare _com;
			int child = parent * 2 + 1;

			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _com(_con[child+1] , _con[child]))
				{
					++child;
				}
				//如果父亲比孩子小，交换
				if(_com(_con[child],_con[parent]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;                           //向下走
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);    //尾插一个数据
			AdjustUp(size() - 1);  //然后向上调整
		}
		void pop()
		{
			std::swap(_con[0], _con[size() - 1]);   //堆顶与最后一个元素交换，然后删除最后一个元素，然后从堆顶开始，向下调整
			_con.pop_back();
			AdjustDown(0);     //向下调整
		}
		T& top()
		{
			return _con.front();
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

}

三.deque的介绍

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

所说的来连续，并不是说都是连续的，在底层，deque是一段一段的数组，数组中存储的数据，然后有一个指针数组存储每一个数组的地址，这样，与vector比较，头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

在这里插入图片描述

但是有一个致命的缺陷是：中间插入和删除效率与下标随机访问的效率不高，这个缺陷是底层物理结构所导致的；

为什么选择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不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。

请添加图片描述

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

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

相关文章

centos云服务器安装cs（cobaltstrike4.0）教程

centos云服务器安装cs（cobaltstrike4.0）教程

1、先安装JAVA环境 mkdir download #创建download目录 cd download #进入download目录 mkdir java1.8 #在download目录下再创建java1.8目录 cd java1.8 #进入java1.8目录 wget https://repo.huaweicloud.com/java/jdk/8u201-b09/jdk-8u201-linux-x64.tar.gz #下载jdk压缩包 tar…
阅读更多...
积分法卷径计算(CODESYS ST完整源代码)

积分法卷径计算(CODESYS ST完整源代码)

在学习积分法卷径计算课程之前大家需要属性下PLC的数值积分器运算。 1、博途PLC积分法卷径计算完整源代码 https://rxxw-control.blog.csdn.net/article/details/136719982https://rxxw-control.blog.csdn.net/article/details/1367199822、转动圈数累积功能块 https://rxxw…
阅读更多...
代码随想录算法训练营三刷day27 | 回溯之 39. 组合总和 40.组合总和II 131.分割回文串

代码随想录算法训练营三刷day27 | 回溯之 39. 组合总和 40.组合总和II 131.分割回文串

三刷day27 39. 组合总和回溯三部曲剪枝优化 40.组合总和II回溯三部曲 131.分割回文串回溯三部曲判断回文子串 39. 组合总和 题目链接 解题思路&#xff1a; 本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本…
阅读更多...
组件化开发

组件化开发

一、引言 Vue.js 的组件化开发是其核心特性之一&#xff0c;它允许开发者将复杂的界面拆分为可复用的、独立的、小的组件&#xff0c;从而提高开发效率和代码的可维护性。 二、关键点 1.组件的定义 在components下创建.vue文件timecard.vue用来编辑内容。 文件创建完毕后&am…
阅读更多...
我的导航学习笔记仓库大改版，欢迎关注！！

我的导航学习笔记仓库大改版，欢迎关注！！

链接&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 我的导航学习笔记&#xff0c;内容涵盖导航定位开源程序的源码解读 ( 包括&#xff1a;RTKLIB、GAMP、SoftGNSS、KF-GINS、ORB-SLAM3 等)、各种导航设备的使用方式、书籍讲义、博客翻译、开源项目梳理、…
阅读更多...
python爬取微博话题、关键词下方的所有帖子

python爬取微博话题、关键词下方的所有帖子

文章目录 github repository项目介绍输出安装必备库获取cookiegithub repository 网址：https://github.com/dataabc/weibo-search 在GitHub获取到的非常成熟的微博话题、关键词等微博帖子的获取方案，并且可以指定一个或多个关键词，指定获取微博类型，指定获取日期等等。 项…
阅读更多...
文件处理（二）

文件处理（二）

CSV文件的读取和写入 CSV文件的操作 csv是逗号分隔符文本格式&#xff0c;常用于数据交换、Excel文件和数据库数据的导入和导出。 与Excel文件不同&#xff0c;CSV文件中&#xff1a; 值没有类型&#xff0c;所有值都是字符串不能指定字体颜色等样式不能指定单元格的宽高&…
阅读更多...
全网最全100个AI工具导航网站合集

全网最全100个AI工具导航网站合集

随着ChatGPT年前的爆火&#xff0c;人工智能也变成当今最热门的领域之一&#xff0c;它正在改变着我们的生活和工作方式。无论你是想要学习人工智能的基础知识&#xff0c;还是想要利用人工智能来提升你的业务效率和创新能力&#xff0c;都需要找到合适的AI工具来帮助你实现目标…
阅读更多...
VS Code安装Live Server插件搭建web网页结合内网穿透实现公网访问

VS Code安装Live Server插件搭建web网页结合内网穿透实现公网访问

文章目录 前言1. 编写MENJA小游戏2. 安装cpolar内网穿透3. 配置MENJA小游戏公网访问地址4. 实现公网访问MENJA小游戏5. 固定MENJA小游戏公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&…
阅读更多...
数仓建模简介

数仓建模简介

1 建模的意义 如果把数据看作图书馆里的书&#xff0c;我们希望看到它们在书架上分门别类地放置&#xff1b;如果把数据看作城市的建筑&#xff0c;我们希望城市规划布局合理&#xff1b;如果把数据看作电脑文件和文件夹&#xff0c;我们希望按照自己的习惯有很好的文件夹组织方…
阅读更多...
docker小白第十二天

docker小白第十二天

docker小白第十二天 docker network简介 docker不启动时默认的网络情况。 # 停止docker服务 systemctl stop docker.socket systemctl stop docker # 查看docker镜像 docker images输入查看docker镜像命令后&#xff0c;显示未连接到docker服务器 docker启动时网络情况 sy…
阅读更多...
async与defer的区别

async与defer的区别

原文解释 async vs defer attributes - Growing with the Web
阅读更多...
【OpenCV • c++】图像平滑处理（1） —— 线性滤波

【OpenCV • c++】图像平滑处理（1） —— 线性滤波

文章目录 一、平滑处理二、图像滤波三、邻域算子与线性邻域滤波四、方框滤波代码演示 一、平滑处理 平滑处理也称为模糊处理&#xff0c;是一种简单且使用频率很高的图像处理方法&#xff0c;平滑处理的用途有很多&#xff0c;最常见的是用来减少图像上的噪点或者失真。在涉及到…
阅读更多...
资深老鸟，性能测试-TPS上不去分析+电商系统TPS计算（详细）

资深老鸟，性能测试-TPS上不去分析+电商系统TPS计算（详细）

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、性能测试-TPS上…
阅读更多...
YOLOv9详解

YOLOv9详解

1.概述 在逐层进行特征提取和空间转换的过程中&#xff0c;会损失大量信息&#xff0c;例如图中的马在建模过程中逐渐变得模糊&#xff0c;从而影响到最终的性能。YOLOv9尝试使用可编程梯度信息PGI解决这一问题。 具体来说&#xff0c; PGI包含三个部分&#xff0c;&#xff0…
阅读更多...
C语言例：表达式 45-35+1^2 的值

C语言例：表达式 45-35+1^2 的值

代码如下&#xff1a; #include<stdio.h> int main(void) {int a;a 4&5-3&&51^2;printf("4&5-3&&51^2 %d\n",a);return 0; } 结果如下&#xff1a;
阅读更多...
保姆级教学！微信小程序设计全攻略！

保姆级教学！微信小程序设计全攻略！

微信小程序开启了互联网软件的新使用模式。在各种微信小程序争相抢占流量的同时&#xff0c;如何设计微信小程序&#xff1f;让用户感到舒适是设计师在产品设计初期应该考虑的问题。那么如何做好微信小程序的设计呢&#xff1f;即时设计总结了以下设计指南&#xff0c;希望对准…
阅读更多...
win10 使用 IIS 搭建 FTP

win10 使用 IIS 搭建 FTP

0. 背景 首先描述一下需求&#xff0c;大概情况就是&#xff0c;视频文件是存储在笔记本电脑里面&#xff0c;然后偶尔需要投屏到电视上。之前考虑过是否可以通过U盘拷贝的方式&#xff0c;后来发现不行&#xff0c;这样太局限了&#xff0c;需要先明确可能用到的教程&#xf…
阅读更多...
探秘atoi与atof的模拟之路：从原理到实践的全能指南！

探秘atoi与atof的模拟之路：从原理到实践的全能指南！

目录 ​编辑 一.atoi及atof库函数的工作原理 1.1atoi 1.2atof 1.3使用时的注意事项 注意事项 1. 检查输入字符串是否为 NULL 2. 检查字符串是否仅包含有效的数字字符 3. 检查转换结果是否在预期范围内 4. 使用更健壮的替代函数 二. 模拟实现atoi和atof 2.1模拟 atoi…
阅读更多...
服务器相关知识点总结

服务器相关知识点总结

一、服务器概述 1.服务器的定义 服务器是计算机的一种&#xff0c;是网络中为客户端计算机提供各种服务的高性能的计算机。服务器在网络操作系统的控制下&#xff0c;将与其连接的硬盘、磁带、打印机以及昂贵的专用通讯设备提供给网络上的客户站点共享&#xff0c;也能为网络用…
阅读更多...
最新文章

Copyright @ 2022~2023