Priority Queue Not Comparing Correctly C++

Question

I am trying to create a priority queue consisting of pairs of int, char that gives me the pair with the greater int, but my code is not working properly. What am I doing wrong?

This is my comparator class:

class Compare
{
public:
    bool operator() (pair<int, char>a, pair<int, char>b)
    {
        return a.first > b.first;
    }
};

And this is my priority queue:

priority_queue<pair<int, char>, vector<pair<int, char>>, Compare> party;

But if I execute the code:

party.push(make_pair(2, 'A'));
party.push(make_pair(3, 'B'));
cout<<party.top().first;

It returns 2, instead of 3. How do I fix my implementation of the priority queue?

Sam Varshavchik Sam Varshavchik · Accepted Answer · 2016-12-28T20:17:14

The same fix that Geordi La Forge would use: reverse the polarity:

bool operator() (const pair<int, char> &a, const pair<int, char> &b) const
{
    return a.first < b.first;
}

The comparison function always implements strict weak ordering, a.k.a. the logical < operation. But priority_queue, by definition, gives you the largest value in the priority queue, first:

... provides constant time lookup of the largest (by default) element,

But the comparison function is still strict weak ordering:

A Compare type providing a strict weak ordering.

Slightly counter-intuitive, but after a while, it does make sense...

P.S.: The comparison function should be a const function, and take const parameters, for efficiency, as shown in my example; but that's an additional detail.

Priority Queue Not Comparing Correctly C++

2 Answers