C++(18)——适配器概念以及stack、queue、优先队列的模拟实现

       上篇文章中,给出了对于list模拟实现中功能的补全,本篇文章将优先介绍一个新的容器deque之后引入什么是适配器,以及适配器的使用方法,再通过适配器的思想来完成对于Stackqueue、优先级队列(priority_queue)的实现。

目录

1. deque:

1.1 什么是deque:

1.2 deque的大致原理以及其特点:

2. 适配器:

2.1 什么是适配器:

3. Stack的模拟实现:

3.1 功能实现:push、pop:

3.2 功能实现:top,size,empty:

3.3 测试:

4. queue的模拟实现:

4.1 queue的功能实现:

4.2 测试:

​编辑5. priority_queue的模拟实现:

5.1 基本框架:

5.2 插入push以及向上调整函数Adjustup:

5.3 向下调整函数Adjustdown以及删除pop:

5.4 其余功能函数:

5.5 测试:

6. 仿函数:

6.1 仿函数的实现:

6.2 测试:


1. deque:

1.1 什么是deque:

       在对deque的相关实现原理进行介绍前,首先来总结之前介绍的两种容器:vectorlist的优缺点:

       对于vector,在前面对其进行模拟实现的文章中提到,可以将vector看作之前数据结构中的顺序表,其特点是存储空间在物理以及逻辑上的连续性。因此,借由连续性可以得出,vector的优点在于通过下标可以对空间中的内容进行随机访问。并且缓存命中较高对于其缺点,则是头部或者中间进行插入、删除元素时的效率过低,以及一次性开辟较多空间时带来的损耗

     对于list,同样提到,可以将其看作成带哨兵位头结点的双向循环链表,其特点是存储空间在逻辑上连续,但是在物理上不连续。因此,其优点在于任意位置的插入、删除数据时的效率,以及按需申请空间,不会造成浪费。但是由于其在物理上并不连续,因此不能使用下标来对list中的内容进行访问且缓存命中较低

    不难看出,两者的优点几乎可以看作对于对于二者缺点的补充。而本部分介绍的容器deque,则可以看作是对于二者优点的一种结合。

1.2 deque的大致原理以及其特点:

对于deque,其内存管理方式采用了中控的方法,具体原理如下:

    其中,中控所代表的空间是一个指针数组,里面保存了若干个指针,每个指针指向了一块空间,

对于开辟空间的大小,有相同、不同两种方式,这里采用相同进行解释,即每块空间buff均可以存储10个整型数据。对于上述容器,如果需要进行头插,则首先再开辟一块新的空间,这里命名为buff0,然后在buff0中插入数据即可,具体结构如下:

不过需要注意,deque进行头插时,插入数据的顺序并不是从前向后插入数据,而是从后向前依次插入数据,例如先后向deque插入数据1,0。插入效果如下:

在对上述结构进行尾插时,只需要通过指针数组,找到最后一个buff,进行插入数据即可。即:

 在对于deque进行删除数据时,例如进行头插,假设删除一个数据,效果如下:

 如果再删除一个数据,此时buff0中为空,在删除数据后销毁buff0,效果如下:

不难发现,对于deque,虽然其存储空间在物理上仍然保持一定的连续性,但是其头删却不会向vector一样,需要进行挪动覆盖来完成。

对于deque的尾删,只需要找到最后一个数据所处的位置进行删除即可。

        通过上述例子不难发现,对于deque,其头插、头删、尾插、尾删,均有着不错的效率。并且其存储空间的结构则结合了连续空间以及不连续空间。可以说是综合了vector,list的优点,并且对二者的缺点进行了一定程度的互补。

       不过,deque却并不能彻底代替vectorlist。对于vector,其一大优点是可以通过下标来随意访问空间中的内容,对于deque。,虽然也可以实现下标访问,但是其实现方法以及原理相对于 vector过于复杂。下面将对于实现原理进行简单的介绍。

      假设需要利用下标访问第i个位置的内容,则i/10可以算出需要访问的数据在第几块开辟的空间中,再利用i%10就可以计算出,需要访问的内容在空间中的具体位置。但是,如果deque进行过n次头插操作,则计算时,需要先剪掉油茶数据的个数,即利用i-n进行后续的计算。不过需要注意,这种计算方法需要建立在每个buff能存储数据的个数都是相同的。

      不过,在对deque容器中间元素进行删除时,为了保持每个buff的大小都是相同的,并不能直接对于空间进行删除,只能通过逐个挪动数据的方法来完成。这种方法与vector进行头插友删时的弊端一样,效率较低。

     因此,将每个buff的空间保持一样大,可以很好的满足下标访问功能的实现,但是,却不利于实现对于容器中间部分内容的删除以及插入。如果不限制每个存储空间的大小保持一致,有利于实现容器中间部分内容的插入以及删除,但是却不利于实现下标访问。前面矛盾。不过 ,在STL库中,采取的方式是每个存储空间的大小保持一致。具体实现原理过于复杂,本文不再过多叙述。

    总结不难得出,deque的头插,头删,尾插,尾删均有不错的效率,在接下来实现Stack,queue中,将借助deque来完成实现。

2. 适配器:

2.1 什么是适配器:

       适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

       上述给出的关于适配器的概念中提到了,适配器是一种设计模式,这种模式是将一个类的接口转换成另一个接口。例如对于上面给出的容器deque,可以将其看作一个接口,在对于栈和队列这两种结构的实现中,引入deque这种接口,通过deque中的成员函数来完成对于栈和队列的实现。对于deque中的成员函数,大体如下:



 

3. Stack的模拟实现:

上面说到了,可以利用适配器这种设计模式,将deque作为接口,来完成对于Stack的实现,具体原理如下:

namespace violent1
{
	template<class T, class Container = deque<T>>
	class Stack
	{

	private:
		Container _con;
	};
}

在上述代码中,将容器deque作为一种模板引入,在Stack这个类中,通过模板参数来创建成员变量_con此时,_con具有deque的所有性质,因此,此处也不需要编写额外的构造函数来对于成员变量进行初始化。在后面对于Stack功能的实现中,直接调用deque中的成员函数即可

3.1 功能实现:push、pop:
 

直接调用deque的成员函数即可。

void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

3.2 功能实现:top,size,empty:

const T& top()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

3.3 测试:

通过下面的代码对于Stack进行测试:

int main()
{
	violent1::Stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	while (!s.empty())
	{
		cout << s.top() << ' ';
		s.pop();
	}

	return 0;
}

运行结果如下:

4. queue的模拟实现:

       原理与实现Stack所用的方法基本相同,只需要注意栈和队列二者本身的不同的性质即可。具体代码如下:

4.1 queue的功能实现:

namespace violent2
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:

		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.push_front();
		}

		const T& front()
		{
			return _con.front();
		}

		const T& back()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}

4.2 测试:

通过下面的代码对queue的功能进行测试:

void test2()
{
	violent2::queue<int> q;

	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	cout << "功能测试:队列:";
	while (!q.empty())
	{
		cout << q.front() << ' ';
		q.pop();
	}
}

结果如下: 




5. priority_queue的模拟实现:

5.1 基本框架:

对于priority_queue虽然称之为优先级队列,但是在结构上,更贴近于数据结构中的堆

(注:对于堆的介绍可以在一起学数据结构(8)——二叉树中堆的代码实现_子结点与父结交换位置-CSDN博客查看)

这里不再进行过多的叙述,只给出大体流程:

       对于priority_queue的适配器的选择,vector为最佳。在插入结点时,首先插入到堆最后的叶子结点上,再利用向上调整函数Adjustup对于结点的大小关系进行调整。这里默认为实现大堆,即:任意一个父结点都大于子结点。

       对于结点的删除,由于直接删除根结点可能会破坏堆的结构,因此一般选择交换最后一个叶子结点与根结点,删除此时的最后的叶子结点,利用向下调整函数Adjustdown对此时的根结点进行调整。

       大体框架如下:

#include<iostream>
#include<vector>
using namespace std;

namespace violent3
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:


	private:
		Container _con;
	};
}

5.2 插入push以及向上调整函数Adjustup:

void push(const T& x)
		{
			_con.push_back(x);
			Adjustup(_con.size() - 1);
		}

		void Adjustup(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

5.3 向下调整函数Adjustdown以及删除pop:

void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			Adjustdown(0);

		}
void Adjustdown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				{
					child++;
				}

				if (_con[parent] < _con[child])
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

5.4 其余功能函数:

size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

const T& Top()
		{
			return _con[0];
		}

5.5 测试:

利用下面的代码对上述结构进行测试:

void test3()
{
	violent3::priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(6);
	pq.push(2);
	pq.push(3);

	while (!pq.empty())
	{
		cout << pq.Top() << ' ';
		pq.pop();
	}
}

结果如下:


 

6. 仿函数:

6.1 仿函数的实现:

上面所建立的堆是大堆,如果想建立一个小堆,需要改变Adjustup,Adjustdown中的>方向,但是,针对于上方的实现方式,每次更改建立的堆的类型时,都需要对符号进行更改,过于繁琐,为了解决这个问题,引入仿函数:

对于仿函数,其并不是一个函数,而是类,例如:文章中需要用于判断建立大小堆的函数,也就是比较函数,因此,建立两个类,分别命名为less,greater即:

template<class T>
	class less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

priority_queue的类前,将上面的类作为一个模板参数,假设在没有明确要求的情况下,默认建立大堆,则模板参数如下:

template<class T, class Container = vector<T>, class compare = greater<T>>

在类中,将模板参数compare实例化出一个对象,这里命名为com,在需要对于父、子结点进行比较时,直接将这两个结点放入到com中,具体代码如下:

void Adjustup(int child)
		{
			int parent = (child - 1) / 2;
			compare com;
			while (child > 0)
			{
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void Adjustdown(int parent)
		{
			size_t child = parent * 2 + 1;
			compare com;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child+1],_con[child]))
				{
					child++;
				}

				if (com(_con[child],_con[parent]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

6.2 测试:

利用下面的代码测试仿函数建立大堆小堆:

大堆:

void test3()
{
	/*violent3::priority_queue<int,deque<int>,greater<int>> pq;*/
	violent3::priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(6);
	pq.push(2);
	pq.push(3);

	while (!pq.empty())
	{
		cout << pq.Top() << ' ';
		pq.pop();
	}
}

效果如下:


小堆:

void test3()
{
	violent3::priority_queue<int,deque<int>,less<int>> pq;
	/*violent3::priority_queue<int> pq;*/
	pq.push(1);
	pq.push(2);
	pq.push(6);
	pq.push(2);
	pq.push(3);

	while (!pq.empty())
	{
		cout << pq.Top() << ' ';
		pq.pop();
	}
}

效果如下:

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

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

相关文章

ASP.NET-实现图形验证码

ASP.NET 实现图形验证码能够增强网站安全性&#xff0c;防止机器人攻击。通过生成随机验证码并将其绘制成图像&#xff0c;用户在输入验证码时增加了人机交互的难度。本文介绍了如何使用 C# 和 ASP.NET 创建一个简单而有效的图形验证码系统&#xff0c;包括生成随机验证码、绘制…

树莓派4B傻瓜式安装系统配置(无显示器)

一、前言&#xff1a; 本教程详细描述树莓派如何装系统&#xff0c;如何连接电脑显示屏&#xff0c;有详细安装包&#xff0c;有需要的可以点击链接下载&#xff0c;没有会员的宝宝可以关注后私信我。 &#xff08;树莓派4B傻瓜式安装系统配置&#xff08;无显示器&#xff0…

onlyoffice基础环境搭建+部署+demo可直接运行 最简单的入门

office这个体系分为四个大教程 1、【document server文档服务器基础搭建】 2、【连接器(connector)或者jsApi调用操作office】-进阶 3、【document builder文档构造器使用】-进阶 4、【Conversion API(文档转化服务)】-进阶 如果需要连接器&#xff0c;可以查看&#xff1a;onl…

Fiddler如何比较两个接口请求?

进行APP测试时&#xff0c;往往会出现Android和iOS端同一请求&#xff0c;但执行结果不同&#xff0c;这通常是接口请求内容差异所致。 我习惯于用Fiddler抓包&#xff0c;那此时应该如何定位问题呢&#xff1f; 分别把Android和iOS的接口请求另存为TXT文件&#xff0c;然后用…

leetcode hot100零钱兑换Ⅱ

本题可以看出也是背包问题&#xff0c;但区别于之前的01背包问题&#xff0c;这个是完全背包问题的变形形式。 下面介绍01背包和完全背包的区别与联系&#xff1a; 01背包是背包中的物品只能用一次&#xff0c;不可以重复使用&#xff0c;而完全背包则是可以重复使用。01/完全…

体验一下UE5.3的Skeletal Editor

UE5.3中增加了蒙皮网格骨架编辑工具&#xff0c;用户无需导出Fbx就可以直接编辑蒙皮网格&#xff0c;支持修改绑定姿势的骨骼位置、修改蒙皮权重、对已蒙皮多边形进行编辑以及对蒙皮网格减免等操作&#xff0c;就来体验一下。 1.加载插件 要使用Skeletal Editor功能&#xff…

使用系统调用实现shell命令之【ls -l】

时间获取: 1.time time_t time(time_t *tloc); 功能: 返回1970-1-1到现在的秒数&#xff08;格林威治时间&#xff09; 参数: tloc:存放秒数空间首地址 返回值: 成功返回秒数 失败返回-1 2.localtime stru…

Stable Diffusion——基础模型、VAE、LORA、Embedding各个模型的介绍与使用方法

前言 Stable Diffusion&#xff08;稳定扩散&#xff09;是一种生成模型&#xff0c;基于扩散过程来生成高质量的图像。它通过一个渐进过程&#xff0c;从一个简单的噪声开始&#xff0c;逐步转变成目标图像&#xff0c;生成高保真度的图像。这个模型的基础版本是基于扩散过程…

ESMFold conda安装、使用及与AlphaFold的简单比较

文章目录 前言一、ESMFold是什么&#xff1f;二、安装步骤1. 确认安装环境&#xff1a;cuda toolkit版本2. 创建ESMFold conda环境并安装Step 1&#xff1a;创建conda环境&#xff0c;下载需要的包Step 2&#xff1a;激活conda环境&#xff0c;继续pip安装 3. 运行结构预测 三、…

pom.xml常见依赖及其作用

1.org.mybatis.spring.boot下的mybatis-spring-boot-starter&#xff1a;这个依赖是mybatis和springboot的集成库&#xff0c;简化了springboot项目中使用mybatis进行持久化操作的配置和管理 2.org.projectlombok下的lombok&#xff1a;常用注解Data、NoArgsConstructor、AllA…

【Vuforia+Unity】AR02-长方体物体识别

1.创建模型 选择多维长方体图&#xff0c;这个长方体是生活中的真实物体的拍摄图&#xff0c;提前把6个面拍摄好并裁剪干净。 官网创建模型https://developer.vuforia.com/targetmanager/project/targets?projectId0ddbb5c17e7f4bf090834650bbea4995&avfalse 设置长宽高…

Rabbitmq入门与应用(六)-rabbitmq的消息确认机制

rabbitmq的消息确认机制 确认消息是否发送给交换机 配置 server:port: 11111 spring:rabbitmq:port: 5672host: 192.168.201.81username: adminpassword: 123publisher-confirm-type: correlated编码RabbitTemplate.ConfirmCallback ConfirmCallback 是一个回调接口&#xf…

突出最强算法模型——回归算法 !!

文章目录 1、特征工程的重要性 2、缺失值和异常值的处理 &#xff08;1&#xff09;处理缺失值 &#xff08;2&#xff09;处理异常值 3、回归模型的诊断 &#xff08;1&#xff09;残差分析 &#xff08;2&#xff09;检查回归假设 &#xff08;3&#xff09;Cooks 距离 4、学…

汽车电子论文学习---电动汽车用高功率密度碳化硅电机控制器研究

关键重点&#xff1a; sic的特点&#xff1a;耐压高、开关速度快、开关损耗小&#xff1b;采用sic的控制器&#xff0c;损耗降低70%&#xff0c;续航里程提高5%。sic的模块并联设计难度高于IGBT模块&#xff1b;多芯片并联导致热耦合问题、温升不均&#xff0c;导致部分芯片率…

合纵连横 – 以 Flink 和 Amazon MSK 构建 Amazon DocumentDB 之间的实时数据同步

在大数据时代&#xff0c;实时数据同步已经有很多地方应用&#xff0c;包括从在线数据库构建实时数据仓库&#xff0c;跨区域数据复制。行业落地场景众多&#xff0c;例如&#xff0c;电商 GMV 数据实时统计&#xff0c;用户行为分析&#xff0c;广告投放效果实时追踪&#xff…

【git】提交信息写错了,使用 amend 或者 reset 修改最近一次的提交信息 ,修改上上次/以前的提交信息

如果你的提交信息写错了&#xff0c;比如下面&#xff0c;你想修改【初始化项目】这5个字 修改最近一次的提交新的两个办法 &#xff08;1&#xff09;使用 reset 把这个提交重置&#xff0c;然后重新提交&#xff0c;reset 的使用方法请参考这篇文章。但是 reset 这种方法只能…

计算机设计大赛 深度学习人体跌倒检测 -yolo 机器视觉 opencv python

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习的人体跌倒检测算法研究与实现 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f947;学长这里给一个题目综合评分(每项满…

消息队列-RabbitMQ:发布确认—发布确认逻辑和发布确认的策略

九、发布确认 1、发布确认逻辑 生产者将信道设置成 confirm 模式&#xff0c;一旦信道进入 confirm 模式&#xff0c;所有在该信道上面发布的消息都将会被指派一个唯一的 ID (从 1 开始)&#xff0c;一旦消息被投递到所有匹配的队列之后&#xff0c;broker 就会发送一个确认给…

设计模式二:代理模式

1、什么是动态代理 可能很多小伙伴首次接触动态代理这个名词的时候&#xff0c;或者是在面试过程中被问到动态代理的时候&#xff0c;不能很好的描述出来&#xff0c;动态代理到底是个什么高大上的技术。不方&#xff0c;其实动态代理的使用非常广泛&#xff0c;例如我们平常使…

华为配置直连三层组网直接转发示例

华为配置直连三层组网直接转发示例 组网图形 图1 配置直连三层组网直接转发示例组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件扩展阅读 业务需求 企业用户接入WLAN网络&#xff0c;以满足移动办公的最基本需求。且在覆盖区域内移动发生漫游时&#xff…