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?

Vitrine

I guess it should be priority_queue<int, vector<int>, mycomparison> first(true); – Palimpsest

I think you are implying, @sftrabbit, that this is a homework-related question. Not the case. I've been using the std priority queue for some time now and this aspect of its use has always bothered me. I'm refactoring some code now and taking a hard look at that comparison class; it doesn't please me. – Vitrine

I'm curious. What is the usage case for reverse-ordering a priority queue? – Meritorious

@MartinJames, the standard priority queue behavior is to return the greatest element first. So the reverse order will return the least. (I state that for the listeners, I'm sure you already know it.) In my case, I am simulating water rising around an island of terrain. The water should flood the lowest pieces of land first, working its way toward higher elevations. But it is also useful in event scheduling simulations where you skip forward through time to the next soonest event in the future. Did that answer your question? – Vitrine

@Vitrine - heh, devs do some weird jobs:) – Meritorious

Answer 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;

Luckin

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

@Vitrine I'm not sure I follow. Whose custom classes? What custom classes? – Luckin

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. – Vitrine

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

@Vitrine 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. – Luckin

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? – Sabol

@Sabol 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 – Luckin

"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; – Durno

Answer 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;
}

Palimpsest

Answer 3

I have found much more simple solution while I was reversing a priority queue of struct. I hame modified solution from there: stl priority_queue of C++ with struct

struct leaf
{
int symbol;
double probability;
bool operator < (const leaf &o) const 
    {
        return probability > o.probability; // here just reversed the operator
    }
};

priority_queue <leaf> leafs_queue; //queue already reversed

Gravely