Priority queue of pairs in reverse order
Solution 1
Have you tried this?
typedef pair<int, int> P;
priority_queue< P, vector<P>, greater<P> > Q;
This will give the reverse ordering of the normal operator<
for pair<int, int>
, which will start with the smallest first
tie-broken with smallest second
.
If you want to sort by smallest second
first and first
second (!) then you'll need a new sorting functor:
struct Order
{
bool operator()(P const& a, P const& b) const
{
return a.second < b.second || a.second == b.second && a.first < b.first;
}
}
Then use:
priority_queue< P, vector<P>, Order > Q;
Solution 2
You should create your own domain class rather than using pair<int, int>
here, as far as I can see. Then you can overload >
as you like.
Related videos on Youtube
bqui56
Updated on September 15, 2022Comments
-
bqui56 over 1 year
I'm wanting to do something like this:
priority_queue< pair<int, int>, vector<int>, greater<int> > Q;
This works fine if the type I'm comparing is
int
, i.e.:priority_queue< int, vector<int>, greater<int> > Q;
however, obviously with the
pair<int, int>
, there is no way of comparing the pairs in the queue with the standard>
. I was wondering what I should do? How would I implement an overloaded>
or is there another way I can create a priority queue of pairs with the smallestpair.second
being at the top of the queue? -
bqui56 almost 12 yearsoops deleted comment after I saw your edit. I asked: "Is there a way to specify which pair element is being compared?".