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

Question

I have a class called Foo and every Foo object has a method called yVal. What I wanted was a priority queue of Foo objects in ascending order of Foo.yVal()

I overloaded the operator> and operator< in Foo to this:

   bool operator> (const Foo &f){
        return yVal() > f.yVal();
   }

   bool operator< (const Foo &f){
        return yVal() < f.yVal();
   }

And So I have the following code:

priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, greater<unique_ptr<Foo>> > Queue;

But that was not sorting the priority queue in ascending order of Foo.yVal(). Instead it was just sorting them in some unknown random order. I put a cout statement in the operator> and operator< and they weren't even being called. So I tried doing this with a lambda instead:

auto cmp = [](Foo left, Foo right) {return left.xVal() > right.xVal();};
priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, decltype(cmp) > Queue(cmp);

But this gave me the error of "non-static data member declared auto" error.

I would ideally like to get this working with the greater<> and operator overloading. If not can someone please tell me what I am doing wrong with the lambda (not too familiar with lambdas and would like to avoid them if possible).

I have tried using a functor as well, but again, auto on the functor gives me the same "non-static data member declared auto" error.

Answer 1

You got unknown random order because when you have greater<T> the following action is performed

// pseudocode
cmp(T lhs, T rhs) {
  return lhs > rhs;
}

what is T in your code? T is unique_ptr<Foo>, is there operator>(unique_ptr<>,unique_ptr<>) in C++ library? yes, it is see here, and this operator uses unique_ptr::get method while comparing:

// Psuedocode when greater used:
cmp (unique_ptr<Foo>& lhs, unique_ptr<Foo>& rhs)
{
  lhs.get () > rhs.get()
}

What does unique_ptr::get return ? It returns pointer to Foo, so you are comparing pointers to Foo instances. Result is unpredictable. Code compiles and executes but it does not do what you expected.

---

How to fix your lambda:

What objects are stored in your queue ? Foo or unique_ptr<Foo> ? You are storing unique_ptr<Foo> so parameters of your lambda should be declared taking this type.

auto cmp = [](const unique_ptr<Foo>& left, const unique_ptr<Foo>& right) 
{                   ^^^^^^^^^^^^^^^^
    return left->yVal() > right->yVal();
};             ^^
priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, decltype(cmp) > Queue(cmp);

Because instances of unique_ptr cannot be copied you have to pass them by reference. Also use -> operator to access yVal method.

---

EDIT: version with function object.

 // comparator as function object with overloaded operator()
 struct Cmp {
   bool operator()(const std::unique_ptr<Foo>& left, const std::unique_ptr<Foo>& right) const {
     return left->xVal() > right->xVal();
   }
 };

class YourClass {
public:
   std::priority_queue<std::unique_ptr<Foo>, std::vector<std::unique_ptr<Foo>>, Cmp> Queue;