I''m having some problems with priority_queue... The only docs I can find on this data type deal with simple data like floats and ints, and they leave out the last 2 creation parameters - the latter being the comparison function to use (it defaults to less). How would I go about setting up a priority_queue that stores a list of object pointers (class instances), and lets me define my own comparison function for deciding priority based on data from those objects?

Hi,

maybe this docs will help you

http://www.sgi.com/tech/stl/priority_queue.html

from

http://www.sgi.com/tech/stl/

So the definition is
priority_queue
T is your data type
Sequence is the underlying storage container, default is std::vector
Compare the Compare Function, defaults to std::less

This should work for you:

  your_comp_func(yourclass *x, yourclass *y) {    //determine this comparison on your needs    if(x > y)        return false;    else        return true;}std::priority_queue<yourclass *, std::vector<yourclass *>, your_comp_func>  

Edited by - stk on October 31, 2001 7:00:29 AM

Yeah I've read the SGI STL docs. They're a great guide, but they only have an example of simple float storage/sorting in the priority_queue section. I guess they sorta assume you know the syntax involved with specifying the extra optional creation stuff.

So I've got this:

  priority_queue<MyClass *> myQueue;  

and that works just fine. So I expand that to include the second parameter (just going one arg at a time for now...):

  priority_queue<MyClass *, vector<MyClass *>> myQueue;  

and I get a compile error:

: error C2146: syntax error : missing ',' before identifier 'myQueue'

The only difference (aside from the 3rd param, which is optional anyway) between mine and yours is the std:: scope resolution/namespace thing ahead of some things in there. I just assumed I didn't have to keep specifying that, since when I included my STL headers, I defined the namespace like so:

  #include <queue>#include <vector>using namepsace std;  

So I tried it a few different ways:

  std::priority_queue<MyClass *, vector<MyClass *>> myQueue;priority_queue<MyClass *, std::vector<MyClass *>> myQueue;std::priority_queue<MyClass *, std::vector<MyClass *>> myQueue;  

all of them generate the same error.

What's going wrong?



Edited by - PyroBoy on October 31, 2001 3:15:04 PM

quote:Original post by PyroBoy
priority_queue&ltMyClass *, vector&ltMyClass *>> myQueue;

The compiler is getting confused on your nested angle brackets; it needs a space between them to not consider it a binary shift operator:

                         // note this space|priority_queue&ltMyClass *, vector&ltMyClass *> > myQueue;  

Happy coding!

Edit - forgot about the HTML tag thing.

Edited by - Oluseyi on October 31, 2001 3:22:04 PM

Alternative, you could have a buncg of typedefs:

typedef vector&ltMyClass *> Vec_MyClassPtr;typedef priority_queue&ltMyClass, Vec_MyClassPtr> PQ_MyClass; 

And so on...

Ah! That was silly of me. Yeah I threw a space in there and it worked fine. Good eye! :-)

If I had just gone ahead and used the 3rd paramater it wouldn't have come up. And speaking of the 3rd parameter...

Is there any special function signature you have to use? Is a typdef involved in any way? (I thought I saw something like that being used somewhere...). Do you have to inherit some kind of STL function object class? If the comparison function is a class member function does it need to be static? (it's essentially a callback, so I'd imagine so...)

The docs seem to indicate that the comparison function must be a "Binary Predicate" function. So 2 args and a bool return type - no prob, but the doc page that describes it doesn't give an example of how to declare your own binary predicate function that STL objects will be able to chew.

Anyone had experience doing this?

Edited by - PyroBoy on October 31, 2001 3:59:29 PM

Nevermind... found it! :-)

Just thought I''d post the full solution in case anyone''s found this thread through the forum search (I looked for relevant threads before I posted the question, but there wasn''t anything this complete) and is reading along ''cuz they''re having a similar problem. Here''s how you get an STL prority_queue to custom-sort object instances based on your own comparison function:

First, you declare a comparison function structure:

  struct sortFunc : public binary_function<MyClass *, MyClass *, bool>{	bool operator()(MyClass *arg1, MyClass *arg2);};  

So what you''re doing there is creating a struct (ends up as a class inside c++ anyway, so maybe it''d work with a class instead of a struct. meh.) that inherits the STL binary_function class, so STL knows how to deal with the function. The first 2 template args for the binary_function are the arguments to the function, and the bool is its return type. "sortFunc" is just what I called it. It can be named anything.
Inside the struct, you overload operator() for that struct, which the priority_queue will automatically call to decide which of your objects belongs higher in the sorted queue. So you do it like the above, taking a couple of object pointers as arguments and returning a bool.

For implementation, you have a couple of choices... You could define the function right there in the declaration like so:

  struct sortFunc : public binary_function<MyClass *, MyClass *, bool>{	bool operator()(MyClass *arg1, MyClass *arg2)             {                    //Function goes here             }};  

...or you could define it along with your other source in a .cpp file later on like so:

  //(in the .h file):struct sortFunc : public binary_function<MyClass *, MyClass *, bool>{	bool operator()(MyClass *arg1, MyClass *arg2);};//(in the .cpp file):bool sortFunc::operator()(MyClass *arg1, MyClass *arg2){         //Function goes here}  

In any case, the comparison function should examine the properties of both objects and return true if the first argument is "greater" than the second, and false otherwise. It''s up to you to decide what "greater" means to the objects you''re sorting. Suffice to say, if one object is greater than another, it''ll end up higher in the queue than the other object. Once you''ve got a comparison function object created, you create the priority_queue like this:

  priority_queue<MyClass *, vector<MyClass *>, sortFunc> myQueue;  

The first template argument is the type of data you''re storing, so that''d be a pointer to whatever class you''re sorting.
The second arg is the underlying storage format for the queue. This defaults to a vector of the same type as the first arg, but since we need to get at the 3rd arg, we need to define it. You could use some other storage structure if you want, but vector seems to work pretty well.
The third arg is just the name of your comparison function struct/class.

So that''s it. Add object pointers into the queue, and it''ll call your comparison function automatically until it figures out where that object belongs in the queue. When you pop items off the queue, they''ll be sorted in order from greatest to least. Nifty.

Thanks to everyone who helped me figure this whole mess out! Hope this helps someone else with the same dilema, but hey, if not, explaining something to someone else is a great way to remember that something! :-)