priority_queue of pairs of integers in c++ where first elements: descending order, the second elements: ascending order if first elements are equal

Question

I am trying to build a priority queue of pairs of integers in C++ with a custom comparator, where the first elements will be sorted in descending order, but if the first elements of the two pairs are the same, then the second elements will be sorted in the ascending order. So according to my understanding, the following code should have produced the desired output.

#include <bits/stdc++.h>

using namespace std;

// Custom comparator function for pairs of integers
struct Comp
{
    bool operator()(pair<int, int> const& p1, pair<int, int> const& p2)
    {
        if (p1.first == p2.first)
        {
            // If the first elements are the same, sort in ascending order of the second elements
            return p1.second < p2.second;
        }
        else
        {
            // If the first elements are different, sort in descending order
            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;
}

The above code's desired output was supposed to be:

3 2
3 5
2 2
2 4
1 6

But the above code is producing just the opposite output:

1 6
2 4
2 2
3 5
3 2

That is, the output is - the first elements are being sorted in ascending order, and if the first elements of the pairs are the same, then the second elements are being sorted in ascending order - which is just the opposite of my desired output.

I am bewildered by this and have no idea where I am going wrong. I would appreciate any comment or logic behind this and would appreciate other solutions to this problem. Thanks!

Update #1: I get that just flipping the operators of my comparator will solve the issue. But doesn't "p1.second > p2.second" means ordering in descending order? I did the same thing for a vector of pairs of integers and it is giving me the correct output.

#include <bits/stdc++.h>

using namespace std;

// Custom comparator function for pairs of integers
bool comp (pair<int, int> const& p1, pair<int, int> const& p2)
{
        if (p1.first == p2.first)
        {
            // If the first elements are the same, sort in ascending order of the second elements
            return p1.second < p2.second;
        }
        else
        {
            // If the first elements are different, sort in descending order
            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;
}

It is giving me the following output which is correct according to the logic.

3 2
3 5
2 2
2 4
1 6

So in spite of having the same comparator function logic(except one is inside a struct, another one is a direct function), why the vector one is giving the correct output while in the case of the priority queue, it's working in opposite meaning?

Answer 1

I think that the issue is that the comparator is defined such that the first elements are sorted in ascending order when they are the same + second elements are sorted in ascending order always.

Try

struct Comp
{
    bool operator()(pair<int, int> const& p1, pair<int, int> const& p2)
    {
        if (p1.first == p2.first)
        {
            // If the first elements are the same, sort in ascending order of the second elements
            return p1.second > p2.second; // Change this line
        }
        else
        {
            // If the first elements are different, sort in descending order
            return p1.first < p2.first; // Change this line
        }
    }
};

• in the first case where the first elements are the same -- we sort the pairs in ascending order of the second elements by returning p1.second > p2.second + in the second case where the first elements are different -- sort the pairs in descending order of the first elements by returning p1.first < p2.first