daydayup daydayup - 3 months ago 11
C++ Question

How to intuitively understand larger than/less than operator in comparator of C++ priority queue container

I am always confused with defining the comparator for a priority queue container and don't know how to understand it.
For example, I have a

vector
of
pair<int,int>
, where I want sort the pairs descendingly by its second field value.

So the codes looks like this:

struct Compare
{
bool operator()(pair<int,int> const &p1, pair<int,int> const &p2) const
{
return p1.second < p2.second;
}
};



priority_queue<pair<int,int>,vector<pair<int,int> >, Compare> pqueue;


How to understand the operator
"<"
here because I thought it should be
">"
the first time and had to change it based on the result. Why is it
"<"
for descending order instead of
">"
? I just want to get it right at the first shot next time when I use
priority_queue
. Thank you.

Answer

Priority queue returns the top element based on the comparison operator, meaning that when you retrieve items one by one, you get them in descending order.

The meaning of the comparison operator always stays "less than", meaning that when compare(A, B) is true, B has higher priority than A, and would be returned earlier from the priority queue.

Inverting the comparison function inverts the order in which you get the items from your priority queue. Specifically, using > in place of < reverses the order to ascending.

Comments