Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Priority queue question

Reply
Thread Tools

Priority queue question

 
 
Kelvin Moss
Guest
Posts: n/a
 
      04-09-2008
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
 
Reply With Quote
 
 
 
 
acehreli@gmail.com
Guest
Posts: n/a
 
      04-09-2008
On Apr 9, 3:11 pm, Kelvin Moss <(E-Mail Removed)> wrote:
> 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:riority_queue<int,
std::vector<int>,
std::greater<int> > MyQueue;
int main()
{
MyQueue q;
q.push(2);
q.push(1);

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

Ali
 
Reply With Quote
 
 
 
 
acehreli@gmail.com
Guest
Posts: n/a
 
      04-09-2008
On Apr 9, 4:46 pm, (E-Mail Removed) wrote:
> 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:riority_queue<int,
> std::vector<int>,
> std::greater<int> > MyQueue;


Ali
 
Reply With Quote
 
Kelvin Moss
Guest
Posts: n/a
 
      04-10-2008
On Apr 9, 4:46 pm, (E-Mail Removed) wrote:
> On Apr 9, 3:11 pm,KelvinMoss <(E-Mail Removed)> wrote:
>
> > Hi all,

>
> > By defaultPriorityQueues 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 apriorityqueueimplementation that uses the
> heap data structure (g++'s implementation uses vector anyway):
>
> #include <queue>
> #include <functional>
> #include <vector>
> #include <assert.h>
>
> typedef std:riority_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 ..
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      04-11-2008
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
efficient priority queue for a few descrete priority levels Marcel Müller C++ 3 04-27-2009 03:22 PM
Shutter Priority Vs. Aperture Priority Question mutefan@yahoo.com Digital Photography 13 09-14-2006 03:51 PM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM
Question about Aperture priority and Shutter Priority John Edwards Digital Photography 8 01-05-2005 04:58 PM



Advertisments