按相反顺序排列的一对优先级队列

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在队列顶部？

- bqui56

Answer 1

你尝试过这个吗？

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

这将为 pair<int, int> 的正常 operator< 进行反向排序，它将从最小的 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;

- Peter Alexander

---

哎呀，我在看到你的编辑后删除了评论。我问：“有没有办法指定正在进行比较的配对元素？” - bqui56

Answer 2

据我所见，您应该创建自己的域类，而不是在此处使用pair<int, int>。然后，您可以根据需要重载>。

- Hakan Serce