结构体&优先队列自定义排序

57 阅读 0 评论 38 点赞

我是靠谱客的博主美好大山，最近开发中收集的这篇文章主要介绍结构体&优先队列自定义排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node
{
LL d;//储存距离
int u;//点的标号
bool operator < ( const node& b)const// & 表示的是引用，
{
return d > b.d; // 当定义优先队列的时候 这里的 > 代表的是进如有限队列的顺序，
//
也就是大的先进，所以出来的顺序是小的先出
}
};
//
< 是被重载的运算符，即如果有两个结构体 a ,b
比较的时候必须是 a<b如果结果为真，就说明 a.d > b.d;如果为假，代表着a.d < b.d

这篇文章将的很好：https://www.cnblogs.com/Deribs4/p/5657746.html

有空的话看看什么是仿函数；

好像能仿写priority_queue<Node,vertor<Node>,greater(Node)>里面的greator函数

下面是重点摘抄：

2.3 对于自定义类型，则必须重载operator<或者重写仿函数。

2.3.1 重载operator<的例子：返回true时，说明左边形参的优先级低于右边形参

#include <iostream>
#include <queue>
using namespace std;
struct Node{
int x, y;
Node(int a=0, int b=0):
x(a),y(b){}
};
bool operator<(Node a, Node b){//返回true时，说明a的优先级低于b
//x值较大的Node优先级低（x小的Node排在队前）
//x相等时，y大的优先级低（y小的Node排在队前）
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x;
}
int main(){
priority_queue<Node> q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}

自定义类型重载operator<后，声明对象时就可以只带一个模板参数。

但此时不能像基本类型这样声明priority_queue<Node,vector<Node>,greater<Node> >，原因是greater<Node>没有定义，如果想用这种方法定义则可以重载operator >。

例子：返回的是小顶堆。但不怎么用，习惯是重载operator<。

#include <iostream>
#include <queue>
using namespace std;
struct Node{
int x, y;
Node( int a= 0, int b= 0 ):
x(a), y(b) {}
};
bool operator>( Node a, Node b ){//返回true，a的优先级大于b
//x大的排在队前部；x相同时，y大的排在队前部
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x;
}
int main(){
priority_queue<Node,vector<Node>,greater<Node> > q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}

2.3.2 重写仿函数的例子（返回值排序与2.3.1相同，都是小顶堆。先按x升序，x相等时，再按y升序）：

#include <iostream>
#include <queue>
using namespace std;
struct Node{
int x, y;
Node( int a= 0, int b= 0 ):
x(a), y(b) {}
};
struct cmp{//重写的仿函数
bool operator() ( Node a, Node b ){//默认是less函数
//返回true时，a的优先级低于b的优先级（a排在b的后面）
if( a.x== b.x ) return a.y> b.y;
return a.x> b.x; }
};
int main(){
//仿函数替换默认比较方式
priority_queue<Node, vector<Node>, cmp> q;
for( int i= 0; i< 10; ++i )
q.push( Node( rand(), rand() ) );
while( !q.empty() ){
cout << q.top().x << ' ' << q.top().y << endl;
q.pop();
}
return 0;
}