使用pair创建priority_queue,使得当第一个元素相等时,第一个元素的排序为"<",第二个元素的排序为">"

Question

我有一个基本的疑问,因为我试图弄清楚priority_queueSTL在C++中的多功能性.

我知道默认情况下优先级队列实际上是max_heap.我也知道可以通过以下方式修改它来创建min_heap:

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

我想要实现的目标是,我想要创建一个priority_queue <pair <int,int> pq,这样堆就是该对中第一个元素的max_heap,并且它是该对中第二个元素的min_heap.例如,在插入以下对时:

(2,4) (1,5) (1,6)

显示元素时的输出如下:

(2,4)
(1,5)
(1,6)

默认情况下,输出将是:

(2,4)
(1,6)
(1,5)

可能吗？如果是,那怎么样？

先感谢您.

Answer 1

您可以编写一个自定义比较,比较第一个元素operator<和第二个元素operator>.

struct less_then_greater {
    template<typename T, typename U>
    bool operator()(T const& lhs, U const& rhs) const {
        if (lhs.first < rhs.first) return true;
        if (rhs.first < lhs.first) return false;
        return lhs.second > lhs.second;
    }
};

std::priority_queue<std::pair<int, int>,
                    std::vector<std::pair<int, int>>,
                    less_then_greater
                   > pq;

请注意,这不会为一个创建最小堆,而为另一个创建最大堆.但根据你描述的输出,我不认为那是你真正要求的.