0

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?

amp1590
  • 43
  • 8
  • 2
    `fatal error: 'bits/stdc++.h' file not found` – 273K Apr 03 '23 at 02:45
  • @273K Are you using MacOSX? I use Windows and CodeBlocks as the IDE. The code successfully runs and gives output. Also, you can run the code in the online GDB to check whether it runs or not - https://www.onlinegdb.com/ . Just select the language as C++ before running. Moreover, you can check out this link for the error you are getting - https://apple.stackexchange.com/questions/148401/file-not-found-error-while-including-bits-stdc-h – amp1590 Apr 03 '23 at 03:11
  • 1
    `std::priority_queue` is different from most other sorted containers in that it keeps elements in descending order, largest (highest priority) first. That's why the output is the exact opposite of what you expected. – Igor Tandetnik Apr 03 '23 at 03:13
  • 2
    Side notes: (1) [#include ](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) (2) [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – wohlstad Apr 03 '23 at 05:46

1 Answers1

0

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
Lemonina
  • 712
  • 2
  • 14
  • Thanks for your answer. But doesn't "p1.second > p2.second" (that you suggested) mean ordering in descending order? Because if the second element of the 1st pair p1 is greater than the second element of the 2nd pair p2, then this return statement is returning true, which means it would be sorted in descending order. Isn't it? Can you please clarify that? I wrote the same comparator function for a vector and it gives me the correct output. Please see the code in the **Update #1** portion of my original post. Thank you. – amp1590 Apr 03 '23 at 20:01