Priority queue question

K

Kelvin Moss

Hi all,

By default Priority Queues use the less<> function object. This causes
the highest element to be retrieved first. To get the least element
one should use the greater<> function object. Can someone explain how
this works? I ask this to know that how should I write my custom
function object if I want the least element from my custom class.

Thanks ..
P.S. - I am getting confused with the notion of defining great and
less as defined in the priority queue
 
A

acehreli

Hi all,

By default Priority Queues use the less<> function object. This causes
the highest element to be retrieved first. To get the least element
one should use the greater<> function object. Can someone explain how
this works?

You need to provide the comparison object type as a template
parameter. This is easy though, because the comparison type is the
third template parameter which necessitates to also specify the
implementation type even though one may not know or do not care. :)

vector should work for a priority queue implementation that uses the
heap data structure (g++'s implementation uses vector anyway):

#include <queue>
#include <functional>
#include <vector>
#include <assert.h>

typedef std::priority_queue<int,
std::vector<int>,
std::greater<int> > MyQueue;
int main()
{
MyQueue q;
q.push(2);
q.push(1);

assert(q.top() == 1);
}

Ali
 
A

acehreli

This is easy though, because the comparison type is the
third template parameter which necessitates to also specify the
implementation type even though one may not know or do not care.

I meant "This is *not* easy ... ".
typedef std::priority_queue<int,
std::vector<int>,
std::greater<int> > MyQueue;

Ali
 
K

Kelvin Moss

You need to provide the comparison object type as a template
parameter. This is easy though, because the comparison type is the
third template parameter which necessitates to also specify the
implementation type even though one may not know or do not care. :)

vector should work for apriorityqueueimplementation that uses the
heap data structure (g++'s implementation uses vector anyway):

#include <queue>
#include <functional>
#include <vector>
#include <assert.h>

typedef std::priority_queue<int,
std::vector<int>,
std::greater<int> > MyQueue;
int main()
{
MyQueue q;
q.push(2);
q.push(1);

assert(q.top() == 1);

}

Ali

Perhaps I was not clear in my question. I meant to know that why does
the greatest element get picked with the less <> function object?
Won't it have been more intuitive to return the least element with
less<> function object? Or may be I am missing something?

Thanks ..
 
K

Kai-Uwe Bux

Kelvin Moss wrote:

[snip]
Perhaps I was not clear in my question. I meant to know that why does
the greatest element get picked with the less <> function object?
Won't it have been more intuitive to return the least element with
less<> function object? Or may be I am missing something?

Intuitively, a priority queue is supposed to retrieve elements starting from
highest down to lowest priority. On the other hand, the standard uses
std::less<> by default to define the order relation on a type. Therefore,
the priority queue uses std::less<> to figure out the element with the top
priority.


Best

Kai-Uwe Bux
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

priority queue 2
Priority Queue - very slow 4
priority queue question 1
Priority queue help 4
Priority Queue - Remove 2
how to use priority queue with multiprocessing 2
my priority queue 0
priority queue wrapper 1

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top