13

我想做这样的事情:

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

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

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

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

4

2 回答 2

25

你试过这个吗?

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;
于 2012-05-26T10:54:45.260 回答
1

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

于 2012-05-26T10:54:21.660 回答