Sign in to follow this  
Ahl

priority_queue question...

Recommended Posts

Ahl    170
Just a question about some code I was playing around with. Consider the following:

std::priority_queue<MyClass *> PriQue;

MyClass, obviously, being a class object I'm passing by pointer. priority_queue defaults to sorting by the pointer. Is there a way, when passing objects by pointer, into a priority_queue, to get it to sort the objects by some other factor like a member variable? I'm guessing the answer is no as it ignores overridden operators, but ya never know. There might be some trick I'm missing.

Thanks in advance.

Share this post


Link to post
Share on other sites
inavat    317
You need to specify a custom [i]Compare[/i] template parameter (which should be a BinaryPredicate).

See here: [url="http://www.sgi.com/tech/stl/priority_queue.html"]http://www.sgi.com/t...rity_queue.html[/url]

And [url="http://www.gamedev.net/topic/280363-custom-compare-in-priority_queue/"]see here[/url] for an example.

Actually I'll give you a better example:

[code]
bool LessThanPointers(MyClass* a, MyClass* b)
{
return ( *a < *b);
// or return ( a->someMember() < b->someMember() )
}

std::priority_queue<MyClass*, std::vector<MyClass*>, LessThanPointers> myPriorityQueue;

[/code]

Share this post


Link to post
Share on other sites
frob    44919
[quote name='Ahl' timestamp='1306363075' post='4815802']
Just a question about some code I was playing around with. Consider the following:

std::priority_queue<MyClass *> PriQue;

MyClass, obviously, being a class object I'm passing by pointer. priority_queue defaults to sorting by the pointer. Is there a way, when passing objects by pointer, into a priority_queue, to get it to sort the objects by some other factor like a member variable? I'm guessing the answer is no as it ignores overridden operators, but ya never know. There might be some trick I'm missing.

Thanks in advance.
[/quote]

The full version of the template declaration is:


template < class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

You just happen to use the default container and default comparison.


By storing pointers the default comparison will be a simple sort of the memory address using the less than operator.

To sort differently you will need to specify your own comparison function. Your custom comparison function can do whatever you want, including looking at member variables or look to external sources.

//Edit: since it is a pointer there is no operator< to override. Edited by frob

Share this post


Link to post
Share on other sites
Ahl    170
[quote name='frob' timestamp='1306363627' post='4815807']
[quote name='Ahl' timestamp='1306363075' post='4815802']
Just a question about some code I was playing around with. Consider the following:

std::priority_queue<MyClass *> PriQue;

MyClass, obviously, being a class object I'm passing by pointer. priority_queue defaults to sorting by the pointer. Is there a way, when passing objects by pointer, into a priority_queue, to get it to sort the objects by some other factor like a member variable? I'm guessing the answer is no as it ignores overridden operators, but ya never know. There might be some trick I'm missing.

Thanks in advance.
[/quote]

The full version of the template declaration is:


template < class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

You just happen to use the default container and default comparison.

To sort differently you will need to either override operator<() or specify your own comparison function. Your custom comparison function can do whatever you want, including looking at member variables or look to external sources.
[/quote]

I've tried overloading the < (less than) operator in the class definition but it's ignored. I'll have to look at the other things you mentioned. I hadn't thought about those. Thanks.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this