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< 的相反顺序对于 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;