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?

I guess it should be `priority_queue, mycomparison> first(true)`; — Andy Prowl, Mar 26 '13 at 20:54
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. — Richard, Mar 26 '13 at 21:03
I'm curious. What is the usage case for reverse-ordering a priority queue? — Martin James, Mar 26 '13 at 21:06
@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? — Richard, Mar 26 '13 at 21:24

juanchopanza · Accepted Answer · 2020-01-02T20:00:58.973

30

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;

edited Jan 02 '20 at 20:00

answered Mar 26 '13 at 20:55

juanchopanza

223,364
34
402
480

So I suppose one should write comparison functions for their custom classes. – Richard Mar 26 '13 at 21:01
@Richard I'm not sure I follow. Whose custom classes? What custom classes? – juanchopanza Mar 26 '13 at 21:12
1

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. – Richard Mar 26 '13 at 21:36
@Richard: If by "comparators" you mean overloading `operator <` and `operator >`, then yes. – Andy Prowl Mar 26 '13 at 21:42
@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. – juanchopanza Mar 26 '13 at 21:45
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? – Noein May 12 '15 at 19:15
@Noein It is the opposite. Using `std::greater` means the smallest element is at the top of the queue. See http://en.cppreference.com/w/cpp/container/priority_queue – juanchopanza May 12 '15 at 19:30
1

"You can't avoid specifying the storage container *more than once*", but you could define an alias template, e.g. `namespace my { template class Comp = std::less> using priority_queue = std::priority_queue, Comp>; }`, and use `my::priority_queue first;` – Caleth Jan 02 '20 at 13:42

score 1 · Answer 2 · answered Mar 26 '13 at 21:01

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

score 0 · Answer 3 · answered Nov 03 '20 at 09:43

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

Priority queue in reverse order

3 Answers3