在 priority_queue 内的 pair<int, int> 的情况下决定优先级？

Question

如果我们在priority_queue中插入一个pair<int, int>，那么由哪个元素决定优先级呢？我们可以决定哪个元素决定优先级吗？

Answer 1

是的，您可以使用 priority_queue 的 Compare 模板参数来提供自己的比较器。默认情况下，Compare 默认为 std::less<T>，其中 T 是元素类型，这会导致在对上调用 < 运算符，其特化为：

template <class T1, class T2>
bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y)
{ return x.first < y.first || (!(y.first < x.first) && x.second < y.second) }

以下是如何使用不同比较器的示例：

#include <queue>
#include <utility>
#include <vector>

using namespace std;

struct CompareByFirst {
    constexpr bool operator()(pair<int, int> const & a,
                              pair<int, int> const & b) const noexcept
    { return a.first < b.first; }
};

int main() {
    priority_queue<pair<int, int>,
                   std::vector<pair<int, int> >,
                   CompareByFirst> myQueue;
}

在 priority_queue 内的 pair<int, int> 的情况下决定优先级？

Deciding priority in case of pair<int, int> inside priority_queue?

c++

std

priority-queue