Priority queue in reverse order

Question

This site suggests that if I want to reverse-order my priority queues, the following code is what I should use:

#include <iostream>
#include <queue>
using namespace std;

class mycomparison{
    bool reverse;
  public:
    mycomparison(const bool &revparam=false) {reverse=revparam;}
    bool operator() (const int &lhs, const int &rhs) const {
      if (reverse) return (lhs>rhs);
      else         return (lhs<rhs);
    }
};

int main (){
  int myints[]= {10,60,50,20};

  priority_queue<int, vector<int>, mycomparison(true)> first;

  return 0;
}

This bothers me:

• I have to specify the storage class in my constructor.
• I have created a class whose only purpose is to be passed to the priority queue.

Is there a more elegant or less verbose way of reverse-sorting a priority queue?

Solution 1

You can't avoid specifying the storage container, but you can avoid writing your own functor:

priority_queue<int, vector<int>, std::greater<int> > first;

Solution 2

If you want flexibility without having to define any class, you could use std::function> as the type of your comparator:

#include <functional>

int main ()
{
    int myints[]= {10,60,50,20};

    // Use this is a the type of your comparator
    typedef std::function<bool(int, int)> comp_type;

    // Priority queue using operator < for ordering
    priority_queue<int, vector<int>, comp_type> first(std::less<int>());

    // ...

    // Priority queue using operator > for ordering
    priority_queue<int, vector<int>, comp_type> second(std::greater<int>());

    // ...

    return 0;
}

Comments

[Richard]

So I suppose one should write comparison functions for their custom classes.

[juanchopanza]

@Richard I'm not sure I follow. Whose custom classes? What custom classes?

[Richard]

the question concerned the int type, but my primary interest is in priority queues of custom classes. In which case, one would define comparators for the custom class and then use your code as is.

[Andy Prowl]

@Richard: If by "comparators" you mean overloading operator < and operator >, then yes.

[juanchopanza]

@Richard If the operators < and > make sense for those types, then I would say yes. If your classes don't have a natural ordering, I would favour using your own functors.

[Noein]

Question: What exactly does ordering in priority_queue mean? Doesn't 'greater' imply that the greatest element is the first? Then why is 'lesser' the default?

[juanchopanza]

@Noein It is the opposite. Using std::greater<T> means the smallest element is at the top of the queue. See en.cppreference.com/w/cpp/container/priority_queue

[Caleth]

"You can't avoid specifying the storage container more than once", but you could define an alias template, e.g. namespace my { template<typename T, template<typename> class Comp = std::less> using priority_queue = std::priority_queue<T, std::vector<T>, Comp<T>>; }, and use my::priority_queue<int, std::greater> first;