[Booley]

Sometimes I need to reverse the order in a priority queue to have items sorted smallest to largest. However, I have trouble implementing this for structs since I often need to sort by multiple parameters (e.g. sort property A first, then if tie, sort by B )/>.

I have found that the following works for me. If I have a struct S, I can overload the less<S> operator as such:

#include <queue>
#include <stdio.h>
using namespace std;

struct S
{
    int a, b;

    S(int _a, int _B)/>/>
    {
        a = _a;
        b = _b;
    }

    inline bool operator < (const S& obj) const
    {
        if(a != obj.a)
            return a > obj.a;
        else
            return b > obj.b;
    }
};

int main()
{
    priority_queue<S> pq;
    pq.push(S(1, 10));
    pq.push(S(5, 7));

    S obj = pq.top(); pq.pop();
    printf("%d %d", obj.a, obj.B)/>/>;
}

This code correctly displays (1, 10).

However, I found some help online that says the following method works:

#include <queue>
#include <stdio.h>
using namespace std;

struct S
{
    int a, b;

    S(int _a, int _B)/>/>
    {
        a = _a;
        b = _b;
    }
};

struct compare
{
    inline bool operator () (const S& x, const S& y) const
    {
        if(x.a != y.a)
            return x.a > y.a;
        else
            return x.b > y.b;
    }
};

int main()
{
    priority_queue<S, vector<S>, compare > pq;
    pq.push(S(1, 10));
    pq.push(S(5, 7));

    S obj = pq.top(); pq.pop();
    printf("%d %d", obj.a, obj.B)/>/>;
}

This also produces correct output. Why does the second method work as well? I understand that the "compare" struct is a function object (...right?), but I thought the third template argument for the priority queue involved an operator, not a struct.

Can someone please explain to me either why the second method works or how the priority queue is implemented in regards to how it uses that third template argument? I think if I understand how the operator/function object is used by the queue, I'll be more confidant in my coding.

P.S.: As is obvious, I am a newbie to the C/C++ language. However, I am very fluent in Java, so I'm familiar with concepts that are shared between those languages, but not with others (operator overloading and function objects especially). It might be helpful to have an explanation either using a kind of pseudocode or explaining the C++ code from the perspective of a Java programmer.

[mojo666]

An explanation can be found here

Basically, a priority queue is set up such that you can define a Compare class whose function call operator does the comparison. All the code in the implementation of the priority_queue uses this class in its comparisons. If you don't provide a definition, it defaults the definition to "return a<b" which is why your overload also works.