为什么优先队列重载运算符必须反着来？

rt，现在有一个结构体：

CPP

const int N=1e6+5;
struct edge{
	int u,v,w;
};

我希望使用 std::priority_queue 对若干个 edge 进行升序排序，于是写出了下面这份代码：

CPP

const int N=1e6+5;
struct edge{
	int u,v,w;
	friend bool operator < (edge a,edge b){
		return a.w<b.w;//注意这行
	}
};

priority_queue<edge,vector<edge>,less<edge> > q;

但经测试，此时优先队列是按降序排序的，更改了运算符重载的内容才能达到预期：

CPP

struct edge{
	int u,v,w;
	friend bool operator < (edge a,edge b){
		return a.w>b.w;//把 < 改成了 >
	}
};

priority_queue<edge,vector<edge>,less<edge> > q;

我寻思升序排序是该写 return a.w<b.w 啊。这是优先队列的某种 feature 吗。

为什么优先队列重载运算符必须反着来？

讨论操作

回复

相关推荐

为什么优先队列重载运算符必须反着来？