C++ priority queue in ascending order by specific method for objects

Question

Lets say I have the a class called MyClass and every MyClass object has a method called xVal. What I want is a priority queue of MyClass objects sorted in ascending order of MyClass.xVal()

So far I have this:

priority_queue<MyClass, vector<MyClass>, greater<MyClass>> queue;

Of course, it doesn't do what I expect.I complies but uses some random ordering for my objects. Would appreciate it if someone can point out what I am doing wrong.

Thanks.

Write your own [functor](https://stackoverflow.com/questions/356950/what-are-c-functors-and-their-uses) or a lambda and replace `greater` with it. — NathanOliver, Nov 01 '18 at 21:26
@NathanOliver How do I write a lambda for this and isn't there a simpler way of doing this? — Alex Smith, Nov 01 '18 at 21:30
What do you mean by 'it doesn't do what I expect'? Does it even compile? — Michaël Roy, Nov 01 '18 at 21:30
@NathanOliver: https://en.cppreference.com/w/cpp/container/priority_queue — Michaël Roy, Nov 01 '18 at 21:30
See [this](https://en.cppreference.com/w/cpp/language/lambda) about lambdas. Unfortunately there isn't a simpler way of doing this. You wither overload your `operator >` to do what you want or you provide your own functor to the `priority_queue` that does what you want. — NathanOliver, Nov 01 '18 at 21:32
@NathanOliver Does it compile? It's difficult to find out what's wrong from an 'It doesn't do what I want', especially if we don't know if it even compiles. The example at cppreference shows how to setup and use a lambda for ordering the queue. — Michaël Roy, Nov 01 '18 at 21:36
@NathanOliver Can you give an example of how to give a functor to a priority queue? — Alex Smith, Nov 01 '18 at 21:37
@AlexSmith There's an example in the [link provided by Michael](https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue). — super, Nov 01 '18 at 21:43
@NathanOliver if I overload the < operator in MyClass will it work? — Alex Smith, Nov 01 '18 at 21:44
If you want greater than you might find `>` more helpful than `<`. — user4581301, Nov 01 '18 at 21:47
@AlexSmith lambdas will make make your life so much easier.... You should get used to them. Reproducing the cppreference example is all you need for now. Overriding operator< will also work, but its logic must be inversed, for what you want to do, which may lead to other issues... I suggest you override operator > instead, and use std::greater, as in your code above. Still, using a lambda is the best way to go, as it makes your intent crystal clear. — Michaël Roy, Nov 06 '18 at 07:49

tangy · Answer 1 · 2018-11-02T23:37:59.163

The CPP Reference link to Priority Queue provides that a priority queue can be defined as:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Here, T=MyClass and Container=std::vector<MyClass>. The only thing that remains is Compare which as has been mentioned above can be implemented using either Lambdas or Functors. I'll show both:

Let's say the class is defined as shown below with xVal() method's return value as the sort key:

struct MyClass{
    int count;
    int key;
    int xVal() { return count; };
};

Using Lambdas

//  Lambda skeleton: [capture preferences](arguments){ body }
auto cmp = [](MyClass left, MyClass right) {return left.xVal() > right.xVal();};
std::priority_queue<MyClass, std::vector<MyClass>, decltype(cmp)> queue(cmp);

Using a Functor

struct CmpFunctor{
    bool operator()(MyClass left, MyClass right) const {
        return left.xVal() > right.xVal();
    }
};
auto cmp = CmpFunctor()
std::priority_queue<MyClass, std::vector<MyClass>, decltype(cmp)> queue(cmp);

Here is a link showing the running code.

Wouldn't it be better to use the `xVal()` method mentioned in the question, rather than invent `count`? — JaMiT, Nov 02 '18 at 23:26

C++ priority queue in ascending order by specific method for objects

1 Answers1

Linked