daydayup daydayup - 1 year ago 62
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

, 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
. Thank you.

Answer Source

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.