c++ - 使 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;
}

但我正在寻找的是保持比较原样(cos 对我来说更好理解)，并且只需更改 priority_queue 构造函数，如下所示:

priority_queue<point, reverse> Q;

我怎样才能做到这一点？

Answer 1

首先你应该制作一个operator>对于您的结构，如果检查一个点是否小于另一个点是有意义的，那么检查一个点是否大于另一个点也是有意义的。您可以根据 operator< 来实现它通过简单地颠倒论点。

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

一旦你有了它，你就可以使用 std::greater 创建一个反向优先级队列, 来自 <functional>标题。

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;