Jump to content
  • Advertisement
Sign in to follow this  
SippyCup

STL priority_queues

This topic is 4871 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does anyone have experience with using reference types in priority queues? Like priority_queue<int &> pqInts? I haven't been able to get this to work, but that's probably because I've never done it and I have no idea what I'm doing.

Share this post


Link to post
Share on other sites
Advertisement
You can't store references in STL containers. Container elements must be copy-constructible and assignable, which references aren't.

Either use pointers (with care!), or smart pointers like boost::shared_ptr or, if you have support for it yet, std::tr1::shared_ptr

Share this post


Link to post
Share on other sites
Yeah, that's what I figured.. My instructor is obviously confused about a great many things. I was going to use pointers, which was suggested to me by Promit, but I don't have a lot of experience with priority_queues, and I don't really know how to pass in a custom predicate. I tried to find some examples, but the ones I found were kind of vague.

Share this post


Link to post
Share on other sites
priority_queue<T> means priority_queue<T,vector<T>,less<T> > which is descending.

priority_queue<int,vector<int>,greater<int> > is ascending.

Share this post


Link to post
Share on other sites
Right, but I can't just say priority_queue<Base*, vector<Base*>, Less<Base*> >, or even operator< <Base*>. I have no clue how to do this. I tried to create a free func called Less that would dereference the Base pointers and work with them, but I still get "Less is invalid as argument #3, type expected." I just need an example to check out, I guess.

I'm pretty sure that using pointers is the only way I can solve this problem. I tried dynamic_cast, but it doesn't work in this situation because the objects in the priority_queue have already been stripped of their derived class data, so it's pointless to try to cast it. I tried using virtual funcs, but once again creating a pointer or a reference to the object doesn't work. If I pass the object into an Event (base) reference, it just executes the useless base function, which is not desirable. It's impossible to create a PQ of reference types, as pointed out above, and so my only option is pointers.

But I don't know how to pass in the overloaded < in my base class.

edit:

Would I have to use the namespace resolution operator :: or something?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You need to make a functor, that is an object with call operator defined.

template<T>
struct Less : std::binary_function<T, T, bool> {
bool operator()(const T& a, const T& b) const { return a < b; }
};


std::binary_function provides some typedefs that some algorithms may or may not use. Or something.

Share this post


Link to post
Share on other sites
Quote:
Original post by SippyCup
Right, but I can't just say priority_queue<Base*, vector<Base*>, Less<Base*> >, or even operator< <Base*>.


Trap was basically saying the default Predicate types used for std::priority_queue is std::less a functional object comes with the standard library. std::less assume the type supports the relational less than operation so in this case the default will compare pointers so as you know you'll need to provide a custom predicate. The custom predicate can be any C++ callable entity, a free-function, a pointer to member function (but not directly), and a functor.


Quote:
Original post by SippyCup
... I have no clue how to do this. I tried to create a free func called Less that would dereference the Base pointers and work with them, but I still get "Less is invalid as argument #3, type expected." I just need an example to check out, I guess.

.....

But I don't know how to pass in the overloaded < in my base class.

edit:

Would I have to use the namespace resolution operator :: or something?


Assuming you have correctly overloaded the relational less than operator then as free function it would be:


#include <queue>

struct base {};

//....

bool compare_base(const base* lhs, const base* rhs) {
return *lhs < *rhs;
}

int main() {

typedef std::priority_queue<base*, std::vector<base*>, bool (*)(const base*, const base*) > my_pqueue;

// notice you must pass the address of a free-function to an instance of a PQ
my_pqueue pq(&compare_base);
}


As a functional object it would be:


struct compare_base {
bool operator()(const base* lhs, const base* rhs) const {
return *lhs < *rhs;
}
};

typedef std::priority_queue<base*, std::vector<base*>, compare_base > my_pqueue;

//nothing more needs to be done just use as normal.

Share this post


Link to post
Share on other sites
Keep in mind if you are using pointers with your own comparison function, if you change the 'value' of anything in the priority queue it will not be updated. If you need to be able to raise or lower the priority of a value you will have to write your own priority queue.

Share this post


Link to post
Share on other sites
Right. Thanks a whole lot to everyone. Lucky for me, I won't be needing to alter the priority of the objects inside the PQ, I only need to process them. Thanks again!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!