【C++进阶之路】适配器、反向迭代器、仿函数

文章目录

  • 前言
  • 一、适配器
    • ①模拟实现栈
    • ②模拟实现对列
  • 二、反向迭代器
  • 三、仿函数
  • 总结

前言

我们先来笼统的介绍一下今天的三个内容。

  • 适配器——简单的理解就是复用，用已经实现的轮子，来继续实现某种功能。

  • 反向迭代器——原理很简单，就是对称+复用（已经造好的正向迭代器）

  • 仿函数——与函数用法相同的类，用于排序，比如大堆，小堆，升序，降序。

一、适配器

适配器的功能，在我们模拟实现栈和对列时十分方便！
先用这两个例子感受一下。

①模拟实现栈

	template<class T,class Con = deque<T>>
	class stack
	{
	public:
	
		void push(const T& val)
		{
			st.push_back(val);
		}
		void pop()
		{
			st.pop_back();
		}
		T& top()
		{
			return st[st.size() - 1];
		}
		size_t size()
		{
			return st.size();
		}
		bool empty()
		{
			return st.empty();
		}
	private:
		Con st;
	};

②模拟实现对列

	template<class T, class Con = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			qu.push_back(val);
		}
		void pop()
		{
			qu.pop_front();
		}
		T& front()
		{
			return qu[0];
		}
		size_t size()
		{
			return qu.size();
		}
		bool empty()
		{
			return qu.empty();
		}
	private:
		Con qu;
	};

这里的模板参数：

template<class T, class Con = deque<T>>
				//这就是适配器

看完这两个例子，你可能会明白，并且可能会惊讶于适配器的方便之处。

并且这里也给了模板一个用法——缺省参数。

且如果是全缺省的话，我们示例化还是要给参数列表的。

如下：

stack<> st;

再来谈谈deque，你可能会好奇，这里在栈的第二个缺省参数为啥不给vector<T>, 对列的第二个缺省参数为啥不给list<T>。

要弄清楚原因我们先得了解deque的基本结构：

在这里插入图片描述

我们知道这个中控数组一旦满了，就要考虑扩容的问题，那该如何扩呢？

只需要将中控数组进行扩容，然后将指针拷贝过去即可。

因此相较于vector无需动数据即可完成扩容！—— 提高了扩容的效率。

相较于vector，这种结构也支持随机访问，不过得通过计算，这样高频率的随机访问效率会降低，缓冲命中率也有一定的下降。

相较于list，由于list是单个申请单个释放，因此deque的缓冲命中率较高。

但是相较于list，如果deque要在中间插入数据，那效率就会降低，这一点不如list。

这样：

  1. stack结构，实现尾插尾删功能，如果要考虑扩容的效率，deque的优势更大。
  2. queue结构，实现尾插头删功能，如果要考虑到缓冲命中率，deque的优势更大。

因此库里采用了deque来实现栈和对列！

二、反向迭代器

我们先来看库里的实现方式：

  • vector
    在这里插入图片描述
  • list
    在这里插入图片描述

可以看到，这里呈现对称的方式，但是如何解引用是关键。

库里是这样实现的：

Reverse_iterator operator* ()
{
	Iterator tmp(_it);
	return *--tmp;
}

这里使用了正向迭代器的拷贝构造，然后再减减访问反向迭代器的下一个元素，这样实现了错位，也能刚好利用实现好的正向迭代器。

剩余的就不难实现了：

	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> self;
		//自定义的类型不能被当做类名进行使用
		
	
		Reverse_iterator(const Iterator& it)
		{
			_it = it;
		}
		
		self& operator ++()
		{
			_it--;
			return *this;
		}
		self operator ++(int)
		{
			self tmp(_it);
			_it--;
			return self;
		}
		Ref operator* ()
		{
			Iterator tmp(_it);
	
			return *--tmp;
		}
		Ptr operator->()
		{
			return _it.operator->();
		}
		bool operator!=(const Reverse_iterator&it)const
		{
			return _it != it._it;
	
		}
		bool operator==(const Reverse_iterator& it)const
		{
			return _it == it._it;
		}
		Iterator _it;
	};

然后我们只需在容器里加上下面的代码即可完成复用！

		typedef list_iterator<T,T&,T*> iterator;
		typedef list_iterator<T,const T&,const T*> const_iterator;

		typedef Reverse_iterator<iterator, T, T*> reverse_iterator;
		typedef Reverse_iterator <const_iterator, const T, const T*>\
		 const_reverse_iterator;
		 
		reverse_iterator rbegin()
		{
			return end();
			//这里会调用拷贝构造
		}
		reverse_iterator rend()
		{
			return begin();
		}

三、仿函数

我们这里先实现一个优先级对列——大堆。

	template<class T,class Container = vector<T>>
	class priority_queue
	{
		//建大堆
		void AdjustDown(int parent)
		{
			//假设左孩子较大
			size_t child = parent * 2 + 1;
			//因为是往下比较，所以child应在范围内
			while (child < con.size())
			{
				//先选出来较大的孩子，当然前提得存在。
				if (child + 1 < con.size() && con[child] < con[child + 1])
				{
					child = child + 1;
				}
				//再跟父节点进行比较，如果孩子大就换
				if (con[parent]< con[child])
				{
					swap(con[parent], con[child]);
					//因为是向下比较的，所以要看parent是不是还比下面的孩子大。
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		//建大堆
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (parent >= 0)
			{
				if (con[parent] < con[child])
				{
					swap(con[parent], con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
	public:

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			InputIterator it = first;
			while (it != last)
			{
				con.push_back(*it);
				it++;
			}
			//进行调堆
			//从最后一个叶子结点的父节点开始。

			//时间复杂度O(N)
			for (int i = ((con.size() - 1) - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}
		void pop()
		{
			swap(con[0], con[con.size() - 1]);
			con.pop_back();
			AdjustDown(0);
		}
		void push(const T& val)
		{
			con.push_back(val);
			AdjustUp(con.size() - 1);
		}
		size_t size()
		{
			return con.size();
		}
		bool empty()
		{
			return con.empty();
		}
		T top()const
		{
			return con[0];
		}
		
		priority_queue()
		{}
	private:
		Container con;
	};

这里的大堆算是实现了，借助这二叉树的一点点知识。

  • 那如果我们还要实现小堆呢？

用不用cv一份，再改呢？其实不用，只需要写一个仿函数即可。

	template<class T>
	struct Less
	{
		bool operator()(const T &x1 ,const T& x2)
		{
			return x1 < x2;
		}
	};
	template<class T>
	struct Greater
	{
		bool operator()(const T& x1, const T& x2)
		{
			return x1 > x2;
		}
	};

如何使用呢？用类模板+重载函数的掉用。

template<class T,class Container = vector<T>,class Compare = Less<T>>
class priority_queue
{
	//建大堆
	void AdjustDown(int parent)
	{
		//假设左孩子较大
		size_t child = parent * 2 + 1;
		//因为是往下比较，所以child应在范围内
		while (child < con.size())
		{
			//先选出来较大的孩子，当然前提得存在。
			if (child + 1 < con.size() && com(con[child] , con[child + 1]))
			{
				child = child + 1;
			}
			//再跟父节点进行比较，如果孩子大就换
			if (com(con[parent], con[child]))
			{
				swap(con[parent], con[child]);
				//因为是向下比较的，所以要看parent是不是还比下面的孩子大。
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
	//建大堆
	void AdjustUp(int child)
	{
		int parent = (child - 1) / 2;
		while (parent >= 0)
		{
			if (com(con[parent] , con[child]))
			{
				std::swap(con[parent], con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
public:

	template<class InputIterator>
	priority_queue(InputIterator first, InputIterator last)
	{
		InputIterator it = first;
		while (it != last)
		{
			con.push_back(*it);
			it++;
		}
		//进行调堆
		//从最后一个叶子结点的父节点开始。

		//时间复杂度O(N)
		for (int i = ((con.size() - 1) - 1) / 2; i >= 0; i--)
		{
			AdjustDown(i);
		}
	}
	void pop()
	{
		swap(con[0], con[con.size() - 1]);
		con.pop_back();
		AdjustDown(0);
	}
	void push(const T& val)
	{
		con.push_back(val);
		AdjustUp(con.size() - 1);
	}
	size_t size()
	{
		return con.size();
	}
	bool empty()
	{
		return con.empty();
	}
	T top()const
	{
		return con[0];
	}
	priority_queue()
	{}
private:
	Container con;
	Compare com;
};

这样既可以当做大堆使用，也可以当做小堆使用。

总结

 今天的分享就到这里了，如果觉得文章不错，点个赞鼓励一下吧！我们下篇文章再见！

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

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

相关文章

Maven发布中央仓库始终报403

Maven发布中央仓库始终报403

把域名 oss.sonatype.org 全部替换为&#xff1a;s01.oss.sonatype.org
阅读更多...
Chatgpt Web API 创建对话，免费，不计token数量，模仿网页提交对话

Chatgpt Web API 创建对话，免费，不计token数量，模仿网页提交对话

Chatgpt API 是收费的&#xff0c;按token使用量计费 Chatgpt Web API 免费的&#xff0c;只要有账号就可以使用。 curl https://chat.openai.com/backend-api/conversation \-H authority: chat.openai.com \-H accept: text/event-stream \-H accept-language: zh-CN,zh;q…
阅读更多...
52.弱集合 WeakSet

52.弱集合 WeakSet

WeakSet与Set相似&#xff0c;Set的方法在WeakSet中基本都能使用 WeakSet只能放对象 WeakSet不能被遍历 目录 1 创建WeakSet 2 弱集合的指向问题 1 创建WeakSet 直接在创建的时候把对象放进去是不行的 你需要用add()方法才可以放进去 2 弱集合的指向问题 当你把obj加…
阅读更多...
前后端分离windows本地nginx解决跨域

前后端分离windows本地nginx解决跨域

下载 http://nginx.org/en/download.html 命令 启动Nginx&#xff1a; nginx.exe start 快速停止或关闭Nginx&#xff1a; nginx.exe -s stop 正常停止或关闭Nginx&#xff1a; nginx.exe -s quit 配置文件修改重装载命令&#xff1a; nginx.exe -s reload 强制停用…
阅读更多...
Java基本数据类型

Java基本数据类型

Java基本数据类型 字面常量数据类型变量整形变量长整形变量短整型变量字节型变量思考浮点型变量双精度浮点型单精度浮点型 字符型布尔型变量 类型转换类型提升 字面常量 字符串常量&#xff1a;由""括起来的&#xff0c;比如“12345”、“hello”、“你好”。整形常量…
阅读更多...
机器学习---经验误差与过拟合、方差与偏差、性能度量、比较检验

机器学习---经验误差与过拟合、方差与偏差、性能度量、比较检验

1. 经验误差与过拟合 第三张图建立的模型&#xff0c;在训练集中通过x可以很好的预测y&#xff0c;然而我们不能预期该模型能够很好的预 测集外的数据&#xff0c;换句话说&#xff0c;这个模型没有很好的泛化能力。 第一张图建立了一个线性模型&#xff0c;但是该模型并没有…
阅读更多...
Nginx 301 https跳转后出现跨域和混合内容问题 —— 筑梦之路

Nginx 301 https跳转后出现跨域和混合内容问题 —— 筑梦之路

问题 在浏览器地址栏敲入url访问静态资源目录时&#xff0c;发现默认跳转到了http协议的地址 如上图所示&#xff0c;客户端https请求先到达API网关&#xff0c;然后网关将请求通过http协议转发到静态资源服务器。 调出浏览器发现客户端发送的https请求收到了一个301状态码的响…
阅读更多...
nodejs+vue+elementui学习交流和学习笔记分享系统

nodejs+vue+elementui学习交流和学习笔记分享系统

Node.js 是一个基于 Chrome JavaScript 运行时建立的一个平台。 前端技术&#xff1a;nodejsvueelementui,视图层其实质就是vue页面&#xff0c;通过编写vue页面从而展示在浏览器中&#xff0c;编写完成的vue页面要能够和控制器类进行交互&#xff0c;从而使得用户在点击网页进…
阅读更多...
Kotlin 协程 CoroutineScope

Kotlin 协程 CoroutineScope

协程定义&#xff1a; 19年官方是这样说的&#xff1a;协程是轻量级的线程&#xff0c;协程就是 Kotlin 提供的一套线程封装的 API&#xff1b; 现在官方是这样说的&#xff1a;协程是一种并发设计模式&#xff1b; 协程作用&#xff1a; 1.处理耗时任务&#xff1b; 2.保…
阅读更多...
Kotlin 新版本 1.9.0重要更新预览

Kotlin 新版本 1.9.0重要更新预览

释放 Kotlin 新版本 1.9.0 的强大功能 1. Kotlin K2编译器用于多平台 对K2编译器进行了进一步的改进&#xff0c;使其更加稳定。K2编译器针对JVM目标现已进入Beta版本&#xff0c;并且也可以在多平台项目中使用。 您可以通过将K2配置添加到项目的gradle.properties中&#x…
阅读更多...
win 11 ping ip ping通了，ping域名不通

win 11 ping ip ping通了，ping域名不通

开始-》设置 手动换成自动
阅读更多...
九、数据结构——顺序队列中的循环队列

九、数据结构——顺序队列中的循环队列

目录 一、循环队列的定义 二、循环队列的实现 三、循环队列的基本操作 ①初始化 ②判空 ③判满 ④入队 ⑤出队 ⑥获取长度 ⑦打印 四、循环队列的应用 五、全部代码 数据结构中的循环队列 在数据结构中&#xff0c;队列&#xff08;Queue&#xff09;是一种常见的线性数据结…
阅读更多...
pytest+allure运行出现乱码的解决方法

pytest+allure运行出现乱码的解决方法

pytestallure运行出现乱码的解决方法 报错截图&#xff1a; 这里的截图摘自 悟翠人生 小伙伴的https://blog.csdn.net/weixin_45435918/article/details/107601721一文。 这是因为没有安装allure运行环境或者没有配置allure的环境变量导致&#xff0c;解决方案&#xff1a; 1…
阅读更多...
Vue移动端项目--瑞幸咖啡重构优化

Vue移动端项目--瑞幸咖啡重构优化

来了客官&#xff0c;好久不见&#xff01; 从年初开始&#xff0c;就有个想法&#xff0c;想着把之前做过的项目重新整理一下。毕竟今时不同往日&#xff0c;从现在的角度去看曾经做过的项目&#xff0c;倒是觉得有很多稚嫩的地方。毕竟无论做什么都是熟能生巧&#xff0c;由浅…
阅读更多...
深度学习推理和训练

深度学习推理和训练

优化和泛化 深度学习的根本问题是优化和泛化之间的对立。 • 优化&#xff08;optimization&#xff09;是指调节模型以在 训练数据 上得到最佳性能&#xff08;即机器学习中的学习&#xff09;。 • 泛化&#xff08;generalization&#xff09;是指训练好的模型在 前所未…
阅读更多...
2023JAVA 架构师面试 130 题含答案：JVM+spring+ 分布式 + 并发编程》...

2023JAVA 架构师面试 130 题含答案：JVM+spring+ 分布式 + 并发编程》...

此文包含 Java 面试的各个方面&#xff0c;史上最全&#xff0c;苦心整理最全 Java 面试题目整理包括基JVM算法数据库优化算法数据结构分布式并发编程缓存等&#xff0c;使用层面广&#xff0c;知识量大&#xff0c;涉及你的知识盲点。要想在面试者中出类拔萃就要比人付出更多的…
阅读更多...
nginx怎么做负载均衡

nginx怎么做负载均衡

Nginx怎么做负载均衡 Nginx 是一个高性能的开源反向代理服务器&#xff0c;可以用于实现负载均衡。负载均衡指的是将用户请求平均分配给多个服务器&#xff0c;以提高整体系统性能和可靠性。下面是一个详细介绍如何使用 Nginx 实现负载均衡的步骤&#xff1a; 步骤 1&#xf…
阅读更多...
【Nodejs】Node.js简介

【Nodejs】Node.js简介

1.前言 Node 的重要性已经不言而喻&#xff0c;很多互联网公司都已经有大量的高性能系统运行在 Node 之上。Node 凭借其单线程、异步等举措实现了极高的性能基准。此外&#xff0c;目前最为流行的 Web 开发模式是前后端分离的形式&#xff0c;即前端开发者与后端开发者在自己喜…
阅读更多...
提升Web3安全性和用户体验：元事务和加密技术的应用

提升Web3安全性和用户体验：元事务和加密技术的应用

在Web3中&#xff0c;去中心化应用程序&#xff08;DApps&#xff09;是一种基于区块链技术的应用程序&#xff0c;它们通过智能合约实现透明、安全、去中心化的业务逻辑。然而&#xff0c;DApps的使用门槛比传统的中心化应用程序更高&#xff0c;需要用户具备一定的技术知识&a…
阅读更多...
工厂能耗管理系统解决方案

工厂能耗管理系统解决方案

1、概述 随着碳达峰、碳中和成为政府工作主要任务&#xff0c;工厂作为能耗密集&#xff0c;用能情况较为复杂的大型建筑&#xff0c;有效的降低能源消耗&#xff0c;减少能源成本&#xff0c;避免用能过程中的“跑冒滴漏”现象&#xff0c;实施能效综合考评是个非常必要的管理…
阅读更多...
最新文章

Copyright @ 2022~2023