[C++历练之路]优先级队列||反向迭代器的模拟实现

这篇具有很好参考价值的文章主要介绍了[C++历练之路]优先级队列||反向迭代器的模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络

W...Y的主页 😊 

代码仓库分享💕

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络


🍔前言:
在C++的宇宙中,优先队列似乎是一座巨大的宝库,藏匿着算法的珍宝。而就在这片代码的天空下,我们不仅可以探索优先队列的神奇,还能够揭开反向迭代器的神秘面纱。让我们一同踏入这个编程的探险之旅,在这里,我们将用C++语言创造出一个能按照优先级排列元素的神奇容器,并且探索反向迭代器的魅力,仿佛是在编码的星空下追逐着闪烁的代码流星。准备好了吗?让我们迈出第一步,开启这段惊险又充满奇迹的模拟之旅。

目录

了解priority_queue

模拟实现priority_queue

构建基本框架

仿函数的介绍以及第三个参数添加

反向迭代器的模板实现


了解priority_queue

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素

op_back():删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

 优先队列其实就是数据结构中的堆,而我们想要进行其实现必须掌握其模板。

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络

默认情况下,priority_queue是大堆,而第一个模板参数class T就是其对应的数据类型,第二个模板参数是其数据结构的类型,缺省值为vector,所以其默认的结构类型就是数组,不是链式结构类型的堆,如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。第三个模板类型就是一种仿函数,其可以操控其创建的是大堆还是小堆。

所以我们要用堆的思想来模拟实现优先队列!

模拟实现priority_queue

构建基本框架

首先我们可以照猫画虎,仿照其参数模板进行仿写:

#pragma once
#include<vector>
#include<iostream>
#include<vector>
#include<deque>
#include<stdbool.h>
using namespace std;
namespace why
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

我们将基本函数框架打好,将优先队列的基本函数接口完善,这些都是我们复用的vector、list、deque等接口,可以直接从STL中直接调用。 

注意:这里我们在函数模板中未加入第三个参数进行参数,这里我们在最后实现。原模板接口的缺省默认参数为less<T>,是构建大堆的,所以我们模拟中是先建立大堆。、

往vector中push数据时就要建立大堆进行排序,pop数据得使用向下调整对堆中的数据重新排序成为大堆,所以建立大堆就是使用数据结构中的向上调整函数进行操作,而pop数据是用向下调整的方法进行。

如果对堆这一块的不太了解,可以一下文章:

堆的基本实现——数据结构https://blog.csdn.net/m0_74755811/article/details/132794715?spm=1001.2014.3001.5502向上调整:

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

向下调整:

void adjust_down(size_t parent)
{
	//Compare com;
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		if (child + 1 < _con.size() && _con[child] < _con[child + 1])
		//if(child + 1 < _con.size() && com(_con[child], _con[child + 1]))
		{
			child++;
		}
		if(_con[child] > _con[parent])
		//if (com(_con[parent], _con[child]))
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

仿函数的介绍以及第三个参数添加

在C++中,仿函数(Functor)是一种重载了函数调用操作符 operator() 的对象。它实际上是一个类或者结构体,通过重载 operator(),使得该对象可以像函数一样被调用。仿函数可以像函数一样接受参数,并返回结果,同时可以包含状态信息,因此它们在C++中被广泛用于实现函数对象,作为算法的参数传递,或者用于定义自定义的操作。

通过仿函数,可以实现自定义的比较、排序、转换或者其他操作,这些操作可以被算法直接使用,例如在标准库中的排序算法 std::sort、查找算法 std::find,或者容器类中的自定义排序规则等。使用仿函数可以提供更大的灵活性,使得算法能够适应不同的需求。

下面是一个简单的示例,展示了一个自定义的仿函数用于比较两个整数的大小:

#include <iostream>

// 定义一个比较器仿函数
struct Compare {
    bool operator()(int a, int b) const {
        return a < b; // 自定义的比较规则:a < b
    }
};

int main() {
    Compare cmp; // 创建比较器对象

    int x = 5, y = 10;
    if (cmp(x, y)) {
        std::cout << "x is less than y." << std::endl;
    } else {
        std::cout << "x is greater than or equal to y." << std::endl;
    }

    return 0;
}

在这个示例中,Compare 结构体重载了 operator(),定义了一个比较规则,判断第一个参数是否小于第二个参数。然后在 main 函数中,创建了一个 Compare 类型的对象 cmp,并使用它进行比较操作。

因此,仿函数是C++中的一种强大机制,可以扩展函数的行为,提供更灵活的功能,并允许开发者以更抽象的方式定义特定操作。

所以我们可以使用仿函数针对第三个参数。

priority_queue函数的第三个默认缺省参数为less<T>,如果我们传greater<T>才可以创建小堆。而我们模拟的函数中创建大小堆只不过是将其比较符号进行转换即可。所以我们就可以使用仿函数创建两个不同类型的进行调用。

#pragma once
#include<vector>
#include<iostream>
#include<vector>
#include<deque>
#include<stdbool.h>
using namespace std;
namespace why
{
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child] > _con[parent])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if(child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child++;
				}
				//if(_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

这样我们只需要在模拟函数中创建一个模板变量即可在函数中进行调用。

反向迭代器的模板实现

在STL中的所有容器里都有迭代器与反向迭代器,而在每个容器的模拟实现中我们也将其进行复现。string、vector中的迭代器都可以类似与指针,因为其底层的存储物理空间是连续的,我们可以很好的进行重定义使用。但是list却不行,因为空间是不连续的,所以我们得重新定义封装出一个类迭代器的重定义,将其运算符进行重载成合理的进行使用。

而反向迭代器中我们可以将list中封装的迭代器进行复制粘贴修改,就可以正确使用。

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络

rend指向头节点,而rbegin指向_head->_prev节点,也就是尾节点即可。 

template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{
	typedef list_node<T> node;
	typedef __list_reverse_iterator<T, Ref, Ptr> self;
	node* _node;

	__list_reverse_iterator(node* n)
		:_node(n)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	self& operator++()
	{
		_node = _node->_prev;

		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_prev;

		return tmp;
	}

	self& operator--()
	{
		_node = _node->_next;

		return *this;
	}

	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_next;

		return tmp;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

我们只需要将++、--运算符进行重载即可。将++指向当前节点的_prev节点,而--指向当前节点的_next节点。

那我们看一下STL-list中的反向迭代器是怎么写的:

class reverse_bidirectional_iterator {
  typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp, 
                                         _Reference, _Distance>  _Self;
protected:
  _BidirectionalIterator current;
public:
  typedef bidirectional_iterator_tag iterator_category;
  typedef _Tp                        value_type;
  typedef _Distance                  difference_type;
  typedef _Tp*                       pointer;
  typedef _Reference                 reference;

  reverse_bidirectional_iterator() {}
  explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
    : current(__x) {}
  _BidirectionalIterator base() const { return current; }
  _Reference operator*() const {
    _BidirectionalIterator __tmp = current;
    return *--__tmp;
  }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
  _Self& operator++() {
    --current;
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    --current;
    return __tmp;
  }
  _Self& operator--() {
    ++current;
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    ++current;
    return __tmp;
  }
};

STL中的反向迭代器是封装了正向迭代器,构造一个反向迭代器了。正向迭代器的++就是反向迭代器的--,而正向迭代器的--就是反向迭代器的++。

注意:STL源码中的复用代码rbegin()与rend()的源码为:
[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络

直接返回的是其正向迭代器的begin()与end(),所以其解引用的内容就要发生变化:

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络

其结构就不同:

[C++历练之路]优先级队列||反向迭代器的模拟实现,C++,c++,开发语言,人工智能,java,网络

与原来的结构是不同的。

我们可以自己封装一个类进行使用:

#pragma once
namespace why
{
	template<class Iterator, class Ref>
	struct ReverseIterator
	{
		typedef ReverseIterator<Iterator, Ref> Self;
		Iterator _cur;

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

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

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

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

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

 但是这样复用正向迭代器与刚才的写法所表达的写法是一样的,为什么还要这样单独创建一个类呢?因为list的正向迭代器就是进行封装的,可以复用。但是string、vector的正向迭代器就是指针就不能进行此操作了,所以我们必须复用。


总结:

在这段代码的奇妙旅程中,我们成功地创造了一个C++中的优先队列,仿佛编织了一个可以按照优先级排序元素的魔法网。这个队列不仅仅是一段代码,更是算法的交响乐,奏响着排序、插入、删除的优美旋律。而更加令人惊叹的是,我们在这个编码的仙境中,还揭开了反向迭代器的神秘面纱,为我们的容器增添了一抹独特的色彩。

通过这个模拟实现,我们深入理解了C++中优先队列的本质,并感受到了反向迭代器的便利之处。这不仅是一次代码之旅,更是对数据结构和算法的深刻思考,是对编程艺术的一次追求和探索。

或许,在未来的编程征途中,你会在实际项目中运用这些知识,创造出更为强大、高效的代码。无论何时何地,优先队列和反向迭代器的魔法都将伴随着你,成为解决问题的得力工具。

让我们怀着对编码奇迹的敬畏之心,结束这段代码的冒险。愿你的代码之路充满创造与探索,愿你的算法之舞永远翩翩起舞。编码的世界里,冒险永不止步,期待着你下一次的代码奇迹。文章来源地址https://www.toymoban.com/news/detail-755976.html

到了这里,关于[C++历练之路]优先级队列||反向迭代器的模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【AHB接口协议】固定优先级和轮询仲裁器的Verilog实现

    目录 一、 实验目的 1 二、 实验工具及环境 1 三、 实验内容及步骤 1 1、 实验2.1:16位可参数化仲裁器的设计 1 (1)补码相与法 1 (2)可变参数设计 1 2、 实验2.2:AHB总线仲裁器的设计 2 (1)设计目标 2 (2)状态机实现 3 ①状态定义 3 ②增量控制寄存器cnt 4 ③轮询数计数器

    2024年02月10日
    浏览(47)
  • 【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列

    前言: 大家好,我是 良辰 丫💞💞⛽,我们又见面了,前面我们讲了用链表实现的二叉树,今天我们来接触 堆 的概念,堆是一种特殊的二叉树,只不过咱们的对底层原理是数组,堆也是我们在做题中经常见到的,那么,接下来我们就慢慢的去接触堆, 认识堆,理解堆,掌

    2024年02月02日
    浏览(46)
  • Linux_进程的优先级&&环境变量&&上下文切换&&优先级队列

    什么是优先级? 指定一个进程获取某种资源的先后顺序 本质是进程获取cpu资源的优先顺序 为什么要有优先级 进程访问的资源(CPU)是有限的 操作系统关于调度和优先级的原则:分时操作系统,基本的公平,如果进程因为长时间不被调整,就造成了饥饿问题 Linux的优先级特

    2024年04月09日
    浏览(53)
  • 优先级队列

    目录  前言: 1、PriorityQueue的特性 .2 PriorityQueue常用接口介绍 Ⅰ、PriorityQueue常见的构造方法  Ⅱ、常用的方法 Ⅲ、PriorityQueue的扩容方式:  3、应用 普通的队列是一种 先进先出 的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元

    2024年02月02日
    浏览(53)
  • 优先级队列【C++】

    优先队列(priority_queue)也是队列的一种,priority_queue的接口是和queue的接口是相同的。所以两者的使用语法也是相同的。我们直接看优先队列(priority——queue)的底层实现原理。 默认情况下priority_queue是大堆。 priority_queue的底层实际上就是堆,模拟实现priority_queue之前,需要

    2024年02月10日
    浏览(42)
  • 「数据结构」优先级队列

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! 优先级队列底层是用堆实现的 ,关于堆的实现,之前的文章已经详细介绍过了,文章链接:二叉树1:堆的实现 方法 功能 PriorityQueue() 创建一个空的优先级队列,默认容量是11 PriorityQueue(int i

    2024年02月20日
    浏览(42)
  • rabbitmq的优先级队列

    在我们系统中有一个 订单催付 的场景,我们的客户在天猫下的订单 , 淘宝会及时将订单推送给我们,如果在用户设定的时间内未付款那么就会给用户推送一条短信提醒,很简单的一个功能对吧,但是,tianmao商家对我们来说,肯定是要分大客户和小客户的对吧,比如像苹果,

    2024年02月11日
    浏览(43)
  • Java优先级队列-堆

    大家好,我是晓星航。今天为大家带来的是 Java优先级队列(堆) 的讲解!😀 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。 这种方式的主要用法就是堆的表示。 已知双亲(parent)的下

    2023年04月16日
    浏览(36)
  • 【JAVA】优先级队列(堆)

    羡慕别人就让自己变得更好! 优先级队列(堆)可用于topK问题 有大小根堆 注意堆的模拟实现 坚持真的很难但是真的很酷! 队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。 此时,数据结

    2024年02月15日
    浏览(48)
  • 【Java】PriorityQueue--优先级队列

    目录  一、优先级队列  (1)概念 二、优先级队列的模拟实现 (1)堆的概念  (2)堆的存储方式   (3)堆的创建 堆向下调整 (4)堆的插入与删除 堆的插入  堆的删除 三、常用接口介绍 1、PriorityQueue的特性 2、PriorityQueue常用接口介绍   (1)优先级队列的构造 (2)插入

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包