使 priority_queue 按最小值排序

Question

假设我有这样的结构：

struct point{
    int x, y;
    //constructor
};

然后我的比较方法：

bool operator < (point a, point b){
    if(a.x < b.x) return true;
    if(a.x == b.x) return a.y < b.y;
    return false;
}

当我创建时：

priority_queue<point> Q;

它基于最大值排序（顶部元素将是具有最大 x 的元素，依此类推）。

如何在不更改比较方法的情况下按最小值排序？（显然我可以这样做：

bool operator < (point a, point b){
    bool b;
    if(a.x < b.x) b = true;
    else if(a.x == b.x) b = a.y < b.y;
    else b = false;
    return !b;
}

但我正在寻找的是保持比较原样（因为我更容易理解），只需更改 priority_queue 构造函数，如下所示：

priority_queue<point, reverse> Q;

我怎样才能做到这一点？

Answer 1

首先你应该为你的结构创建一个operator>，如果检查一个点是否小于另一个点是有意义的，那么检查一个点是否大于另一个点也是有意义的。您可以通过简单地反转参数来根据 operator< 实现它。

bool operator>(point a, point b)
{
    return b < a;
}

一旦你有了它，你可以使用 std::greater，从 <functional> header.

中获得相反的优先级 queue

std::priority_queue<point, std::vector<point>, std::greater<point>> Q;

如果您经常需要这种东西，定义一个模板别名可能是值得的：

template<typename T, typename C = std::vector<T>>
using reverse_priority_queue = std::priority_queue<T, C, std::greater<T>>;

reverse_priority_queue<point> Q;

使 priority_queue 按最小值排序

Make priority_queue sort by minimum

c++

priority-queue