c++ - 以相反顺序排列的对的优先级队列

Question

我想做这样的事情：

priority_queue< pair<int, int>, vector<int>, greater<int> > Q;

如果我要比较的类型是 ，这很好用int，即：

priority_queue< int, vector<int>, greater<int> > Q;

但是，显然对于pair<int, int>，无法将队列中的对与标准 进行比较>。我在想我该怎么办？我将如何实现重载>，或者是否有另一种方法可以创建一个优先级队列，其中最小pair.second的队列位于队列顶部？

Answer 1

你试过这个吗？

typedef pair<int, int> P;
priority_queue< P, vector<P>, greater<P> > Q;

这将给出正常operator<for的相反顺序pair<int, int>，它将从最小的first平局开始，并以最小的second.

如果你想按最小的second第一个和first第二个（！）排序，那么你需要一个新的排序函子：

struct Order
{
    bool operator()(P const& a, P const& b) const
    {
        return a.second < b.second || a.second == b.second && a.first < b.first;
    }
}

然后使用：

priority_queue< P, vector<P>, Order > Q;

Answer 2

据我所知，您应该创建自己的域类而不是pair<int, int>在这里使用。然后你可以随心所欲地超载>。