Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Priority queue question (http://www.velocityreviews.com/forums/t609935-priority-queue-question.html)

Kelvin Moss 04-09-2008 10:11 PM

Priority queue question
 
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

acehreli@gmail.com 04-09-2008 11:46 PM

Re: Priority queue question
 
On Apr 9, 3:11 pm, Kelvin Moss <km_jr_use...@yahoo.com> 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::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

acehreli@gmail.com 04-09-2008 11:47 PM

Re: Priority queue question
 
On Apr 9, 4:46 pm, acehr...@gmail.com 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::priority_queue<int,
> std::vector<int>,
> std::greater<int> > MyQueue;


Ali

Kelvin Moss 04-10-2008 11:12 PM

Re: Priority queue question
 
On Apr 9, 4:46 pm, acehr...@gmail.com wrote:
> On Apr 9, 3:11 pm,KelvinMoss <km_jr_use...@yahoo.com> 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::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 ..

Kai-Uwe Bux 04-11-2008 12:10 AM

Re: Priority queue question
 
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


All times are GMT. The time now is 09:40 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.