C++ pair<int,int>优先队列自定义比较器异常及与vector差异问题

问题场景 #

想要实现一个存储pair<int,int>的priority_queue，规则是：首元素降序，首元素相同时次元素升序。编写的代码如下：

#include <bits/stdc++.h>

using namespace std;

struct Comp
{
    bool operator()(pair<int, int> const& p1, pair<int, int> const& p2)
    {
        if (p1.first == p2.first)
        {
            return p1.second < p2.second;
        }
        else
        {
            return p1.first > p2.first;
        }
    }
};

int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;

    pq.push(make_pair(3, 5));
    pq.push(make_pair(2, 4));
    pq.push(make_pair(1, 6));
    pq.push(make_pair(3, 2));
    pq.push(make_pair(2, 2));

    while (!pq.empty())
    {
        pair<int, int> p = pq.top();
        cout << p.first << " " << p.second << endl;
        pq.pop();
    }

    return 0;
}

预期输出：

3 2
3 5
2 2
2 4
1 6

实际输出却完全相反：

1 6
2 4
2 2
3 5
3 2

但将相同逻辑的比较器用于vector的sort函数时，却能得到正确结果：

#include <bits/stdc++.h>

using namespace std;

bool comp (pair<int, int> const& p1, pair<int, int> const& p2)
{
        if (p1.first == p2.first)
        {
            return p1.second < p2.second;
        }
        else
        {
            return p1.first > p2.first;
        }
}

int main()
{
    vector<pair<int,int> > v;

    v.push_back(make_pair(3, 5));
    v.push_back(make_pair(2, 4));
    v.push_back(make_pair(1, 6));
    v.push_back(make_pair(3, 2));
    v.push_back(make_pair(2, 2));

    sort(v.begin(), v.end(), comp);

    for(int i=0; i<v.size(); i++)
    {
        cout << v[i].first << " " << v[i].second << endl;
    }
    return 0;
}

输出结果符合预期：

3 2
3 5
2 2
2 4
1 6

核心原因 #

两者的比较器逻辑定义本质完全不同：

• sort的比较器：返回true时，表示p1应该排在p2的前面，直接定义元素的顺序优先级。
• priority_queue的比较器：返回true时，表示p1的优先级低于p2，会被放在堆的下层（即p2会被优先弹出）。它本质是定义堆的弱序关系，用来判断元素是否需要"下沉"。

直白来说：sort的比较器是判断"谁该在前"，priority_queue的比较器是判断"谁该被压下去"。你写的比较器逻辑在sort里是让大的首元素在前，但在priority_queue里，这个逻辑会让大的首元素被判定为优先级更低，被压到堆底，最终弹出顺序就完全反过来了。

解决方案 #

翻转priority_queue比较器里的判断逻辑，让它符合堆的弱序规则即可：

#include <bits/stdc++.h>

using namespace std;

struct Comp
{
    bool operator()(pair<int, int> const& p1, pair<int, int> const& p2)
    {
        if (p1.first == p2.first)
        {
            // 首元素相同时，次元素大的优先级更低，应该被压下去
            return p1.second > p2.second;
        }
        else
        {
            // 首元素小的优先级更低，应该被压下去
            return p1.first < p2.first;
        }
    }
};

int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;

    pq.push(make_pair(3, 5));
    pq.push(make_pair(2, 4));
    pq.push(make_pair(1, 6));
    pq.push(make_pair(3, 2));
    pq.push(make_pair(2, 2));

    while (!pq.empty())
    {
        pair<int, int> p = pq.top();
        cout << p.first << " " << p.second << endl;
        pq.pop();
    }

    return 0;
}

运行后输出符合预期：

3 2
3 5
2 2
2 4
1 6

内容的提问来源于stack exchange，提问作者amp1590