CODEWITHSUNDEEP
c++priority-queue
Daniel
Daniel

Reputation: 7724

Make priority_queue sort by minimum

Lets say I have some struct like this:

struct point{
    int x, y;
    //constructor
};

Then my comparison method:

bool operator < (point a, point b){
    if(a.x < b.x) return true;
    if(a.x == b.x) return a.y < b.y;
    return false;
}

When I create:

priority_queue<point> Q;

It sorts maximum-based (the top element will the one with greatest x, etc).

How can I sort by minimum without change my comparison method? (Obviously I could do something like this:

bool operator < (point a, point b){
    bool b;
    if(a.x < b.x) b = true;
    else if(a.x == b.x) b = a.y < b.y;
    else b = false;
    return !b;
}

But what I'm looking for is keep the comparison as it is (cos is better for me to understand), and just change the priority_queue constructor, like this:

priority_queue<point, reverse> Q;

How can I achieve this?

Upvotes: 0

Views: 102

Answers (1)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

First you should make an operator> for your struct, if it makes sense to check if one point is less than another, then it makes sense to check if one is greater than another. You can implement it in terms of operator< by simply reversing the arguments.

bool operator>(point a, point b)
{
    return b < a;
}

Once you have that, you can make a reversed priority queue using std::greater, from the <functional> header.

std::priority_queue<point, std::vector<point>, std::greater<point>> Q;

If you require this sort of thing often, it might be worth it to define a template alias:

template<typename T, typename C = std::vector<T>>
using reverse_priority_queue = std::priority_queue<T, C, std::greater<T>>;

reverse_priority_queue<point> Q;

Upvotes: 1

Related Questions