当前位置： 首页 > article >正文

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍

article 2024/9/29 17:52:12

文章目录

  • 前言
  • 一、优先级队列
  • 二、仿函数
  • 三、 反向迭代器
  • 总结

前言

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍

一、优先级队列

优先级队列本质是一个堆，使用vector容器进一步改进进行实现，优先级队列可以传入比较模板参数，来确定建立大根堆还是小根堆， 比较模板参数本质上是一个仿函数。

namespace hhb
{

	template<class T>
	struct Less
	{
		bool operator()(const T& left, const T& right)
		{
			return (left < right);
		}
	};

	template<class T>
	struct Greater
	{
		bool operator()(const T& left, const T& right)
		{
			return (left > right);
		}
	};

	template <class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
		
	private:
		void AdjustDown(int parent)
		{

			Compare _com;

			// 找到子节点
			int child = parent * 2 + 1;
			// 找字节点中大的一个
			if (child + 1 < _con.size() && _com(_con[child], _con[child + 1]))
			{
				++child;
			}

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


		}

		void AdjustUp(int child)
		{
			Compare _com;
			// 找到父节点
			int parent = (child - 1) / 2;

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

		}
	public:

		priority_queue() {};
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			// 向下调整建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
			
		}

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

			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.front();
		}

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

	private:
		Container _con;
	};
}

测试：

#include <iostream>
#include <vector>

using namespace std;

#include "Priority_queue.h"

void test_priority_queue1()
{
	hhb::priority_queue<int> pq1;
	pq1.push(3);
	pq1.push(1);
	pq1.push(5);
	pq1.push(2);
	pq1.push(4);


	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;


	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(3);
	v.push_back(5);


	hhb::priority_queue<int> pq2(v.begin(), v.end());

	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}

	cout << endl;
}


void test_priority_queue2()
{
	//Less<int> less;
	//cout << less(1, 2) << endl;

	hhb::priority_queue<int, vector<int>, hhb::Less<int>> pq1;
	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	pq1.push(4);
	pq1.push(5);



	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;


	hhb::priority_queue<int, vector<int>, hhb::Greater<int>> pq2;
	pq2.push(5);
	pq2.push(4);
	pq2.push(3);
	pq2.push(2);
	pq2.push(1);


	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	cout << endl;

}

class Date
{
public:
	Date(int year = 1949, int month = 10, int day = 1)
		:_year(year)
		,_month(month)
		,_day(day)
	{}

	Date(const Date& d)
	{
		_year = d._year;
		_month = d._month;
		_day = d._day;
	}

	bool operator<(const Date& d) const
	{
		if (_year < d._year)
		{
			return true;
		}
		else if (_year == d._year && _month < d._month)
		{
			return true;
		}
		else if (_year == d._year && _month == d._month && _day < d._day)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	bool operator>(const Date& d) const
	{
		if (_year > d._year)
		{
			return true;
		}
		else if (_year == d._year && _month > d._month)
		{
			return true;
		}
		else if (_year == d._year && _month == d._month && _day > d._day)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	friend ostream& operator<<(ostream& out, const Date& d);


private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& out, const Date& d)
{
	out << d._year << '-' << d._month << '-' << d._day;
	return out;
}


void test_priority_queue3()
{
	hhb::priority_queue<Date, vector<Date>, hhb::Less<Date>> pq1;

	pq1.push(Date(2024, 9, 23));
	pq1.push(Date(2024, 10, 23));
	pq1.push(Date(2024, 8, 23));

	while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;


	hhb::priority_queue<Date, vector<Date>, hhb::Greater<Date>> pq2;

	pq2.push(Date(2024, 9, 23));
	pq2.push(Date(2024, 10, 23));
	pq2.push(Date(2024, 8, 23));

	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	cout << endl;

}

int main()
{

	//test_priority_queue1();

	//test_priority_queue2();

	 test_priority_queue3();

	return 0;
}

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

二、仿函数

仿函数指的是类的实例化对象可以像函数一样使用，也可以叫函数对象。
本质上，仿函数是在类中进行了()运算符重载。

template<class T>
struct Less
{
	bool operator()(const T& left, const T& right)
	{
		return (left < right);
	}
};


void test_priority_queue4()
{
	Less<int> less; // 类的实例化对象
	cout << less(1, 2) << endl; // 可以像函数一样使用
}

测试：

void test_priority_queue4()
{
	Less<int> less; // 类的实例化对象
	cout << less(1, 2) << endl; // 可以像函数一样使用
}

在这里插入图片描述

有些特殊情况下，必须要使用仿函数， 比如在优先级队列中，比较两个指针

void test_priority_queue5()
{
	hhb::priority_queue<Date*> pq;

	pq.push(new Date(2024, 9, 23));
	pq.push(new Date(2024, 10, 23));
	pq.push(new Date(2024, 8, 23));

	while (!pq.empty())
	{
		cout << *pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

在这里插入图片描述

  • 直接进行指针的比较，是随机的，应该比较指针指向的对象。
struct LessPDate
{
	bool operator()(const Date* left, const Date* right)
	{
		return (*left < *right);
	}
};

void test_priority_queue5()
{
	hhb::priority_queue<Date*, vector<Date*>, LessPDate> pq;

	pq.push(new Date(2024, 9, 23));
	pq.push(new Date(2024, 10, 23));
	pq.push(new Date(2024, 8, 23));

	while (!pq.empty())
	{
		cout << *pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

在这里插入图片描述

三、 反向迭代器

反向迭代器使用的是一种是适配器模式。可以适配所有支持迭代器的容器
反向迭代器与正向迭代器是镜像的，如： 反向迭代器的rbegin是正向迭代器的end();

在这里插入图片描述


namespace hhb
{
	template <class Iterator, class Ref, class Ptr>
	struct ReverseIterator
	{
		typedef ReverseIterator<Iterator, Ref, Ptr> Self;

		ReverseIterator(Iterator it)
			:_it(it)
		{}

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

		Ptr operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}


		Iterator _it;
	};
}

vector：

namespace hhb
{
	template <class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;


		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;



		iterator begin() 
		{
			return _start;
		}

		iterator end() 
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		reverse_iterator rbegin()
		{
			return end();
		}


		reverse_iterator rend()
		{
			return begin();
		}


		const_reverse_iterator rbegin() const
		{
			return end();
		}


		const_reverse_iterator rend() const
		{
			return begin();
		}
	}
}

list:

 template<class T> 
class list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

	typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
	typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

	iterator begin()
	{
		return _head->_next;
	}

	iterator end()
	{
		return _head;
	}

	const_iterator begin() const
	{
		return _head->_next;
	}

	const_iterator end() const
	{
		return _head;
	}


	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}

	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}
}

测试：

#include "vector.h"
#include "list.h"

void test6()
{
	hhb::list<int> lt;

	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);


	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;


	hhb::list<int>::reverse_iterator rit1 = lt.rbegin();
	while (rit1 != lt.rend())
	{
		cout << *rit1 << " ";
		++rit1;
	}
	cout << endl;


	hhb::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;


	hhb::vector<int>::reverse_iterator rit2 = v.rbegin();
	while (rit2 != v.rend())
	{
		cout << *rit2 << " ";
		++rit2;
	}
	cout << endl;

}

在这里插入图片描述

总结

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍


http://www.kler.cn/news/324907.html

相关文章：

  • 再见 ESNI，你好 ECH！—— ECH的前世今生
  • 负载均衡（Load Balancing）是一种计算机技术，用于在网络应用中分配工作负载，以优化资源使用、最大化吞吐量、减少响应时间以及避免过载。
  • Elasticsearch实战应用：构建高效搜索引擎
  • vue 同一个页面第二次跳转路由内容不更新
  • SQL常用数据过滤 - EXISTS运算符
  • 基于SpringBoot校园失物招领系统设计与实现
  • 职业技能大赛-单元测试笔记分享
  • Git GUI操作流程
  • 使用Spring Cloud Config和JCE加密配置文件的实战教程
  • 新版Android Studio Koala 导入github第三方依赖 maven仓库的处理方法 (java版)
  • 云端融合，远程监控：EasyCVR工地无线安防监控系统的云解决方案
  • 故障诊断 | 基于双路神经网络的滚动轴承故障诊断
  • dig和nmap的区别
  • Python 数据分析与可视化：从入门到实践
  • hbase之布隆过滤器
  • Jenkins入门：从搭建到部署第一个Springboot项目(踩坑记录)
  • 微服务-- Gateway服务网关
  • CNN-LSTM预测 | MATLAB实现CNN-LSTM卷积长短期记忆神经网络时间序列预测
  • net Core aspx视图引擎 razor视图引擎
  • java：brew安装rabbitmq以及简单示例
  • 【项目】基于Linux和C++的动态在线视频点播系统设计
  • 自建RustDesk服务器：详细步骤与操作指南
  • [dp+dfs]砝码称重
  • 考研数据结构——C语言实现冒泡排序
  • Brave编译指南2024 MacOS篇-引言与准备工作(一)
  • 题库系统平台开发功能解析
  • leetcode每日一题day17(24.9.27)——每种字符最少取k个
  • 【漏洞复现】Ruoyi框架漏洞复现总结
  • Leetcode 1235. 规划兼职工作
  • uniapp学习（002 常用的内置组件）