如何实现优先级队列的自定义运算符重载
最编程
2024-07-19 21:52:54
...
引言
首先我们先来介绍一下sort的自定义比较方式
最经典的题就是noip2007的奖学金
第一种就是用比较器函数
struct node{ int x,y; }a[105]; bool cmp1(node a, node b)//降序 { return a.x>b.x; } bool cmp2(node a, node b)//升序 { return a.x<b.x; }
我们在写sort时只需要
sort(a+1, a+n+1, cmp1)
关于return后的内容:我们可以简单理解为:
a为前一个对象,b为后一个对象。当a>b时返回true,意味着要求a>b。那么得到一个降序序列
第二种方法就先留一个悬念
大家都知道,STL的优先队列是个好东西
但它怎么如同sort一样
自定义比较方式呢
这里就献上几种
重载运算符的方法
First
如果对象是int
STL默认是大根堆
只需要
把 priority<int> Q
换成priority<int, vector<int>, greater<int> > Q
它就能摇身变为小根堆
Secondly
重点是结构体的重载运算符
隆重推出
operator
给出四种方法吧。它们是等价的,只是写法不同。功能都是重载运算符<
而这四种方法同时也就是前文sort的第二种方法(sort默认是升序,所以在结构体里添加一个如下的operator,就相当于以x为比较对象降序)
对于优先队列而言,如下的operator,就相当于以x为比较对象的小根堆
struct node{ int x; int y; friend bool operator<(const node a,const node b) { return a.x>b.x; } }; priority_queue<node> Q;
struct node{ int x; int y; bool operator<(const node &a) const { return x>a.x; } }; priority_queue<node> Q;
struct node{ int x; int y; }point; bool operator<(const node &a,const node &b) { return a.x>b.x; } priority_queue<node> Q;
struct node{ int x; int y; }; struct cmp{ bool operator()(node a,node b){ return a.x>b.x; } }; priority_queue<node,vector<node>,cmp> Q;
如果我们需要一个以x为比较对象的大根堆,只需要将return后的内容改为 a.x<b.x;
推荐阅读
-
C++编程:实战教程 - 实现栈与队列(Deque) 容器适配器,探讨Stack和Queue的实现及Queueue(Deque)的问题。深入理解:如何模拟实现Priority Queue (优先级队列) - 实例与练习。续集:仿函数在C++中的二次探索
-
详解优先级队列(priority_queue):大小根堆实现与自定义操作符重载
-
C++中的优先级队列(Priority Queue)及其运算符重载
-
如何实现优先级队列的自定义运算符重载
-
在Dart中如何实现优先级队列的步骤详解
-
C++编程:实战教程 - 实现栈与队列(Deque) 容器适配器,探讨Stack和Queue的实现及Queueue(Deque)的问题。深入理解:如何模拟实现Priority Queue (优先级队列) - 实例与解题,以及仿射函数入门(第一部分)