Sign in to follow this  
vs322

std::priority_queue questions

Recommended Posts

Is there some way to alter the sorting value of a non-top element of the stl's priority_queue without causing an invalid heap? Or perhaps a way to remove a non top element? Or should I implement my own class that is capable of re-ordering itself? (thanks for your time, and sorry for the noobish question)

Share this post


Link to post
Share on other sites
Not really.
The only reason to use a std::priority_queue is to make it explicitly clear that you're not fiddling with the heap invariant which is exactly what your desired operations would do. If you need to do such things then you can either 1) Keep a sorted vector 2) Keep a vector maintained using the {make|push|pop|is}_heap functions 3) Use a std::set or std::map.

FYI, the priority_queue uses option 2 but doesn't give you access to the underlying heap (hence the benefit of doing it yourself).

The best solution for you depends on what exactly it is you're doing, but they would all work regardless.

Share this post


Link to post
Share on other sites
So I have implemented a vector based Q that can be reorded. Here are the interesting bits:

void MapPath_NodeQ::push(MapPath_Node* ndIn)
{
if (empty())
NodeQ.push_back(ndIn);
else
{
if(NodeQ.back()->fCost <= ndIn->fCost)
NodeQ.push_back(ndIn);
else
{
bool bBreak = true;
NodeVec::iterator iTor = NodeQ.begin();
while(bBreak)
{
if((*iTor)->fCost >= ndIn->fCost)
{
bBreak = false;
NodeQ.insert(iTor,ndIn);
}
else
++iTor;
}
}
}
}
void MapPath_NodeQ::ReOrder(MapPath_Node* NodeToReOrder)
{
bool bBreak = true;
for(NodeVec::iterator iTor = NodeQ.begin(); bBreak && (iTor != NodeQ.end()); )
{
if((*iTor) == NodeToReOrder)
{
NodeQ.erase(iTor);
bBreak = false;
}
else
++iTor;
}
if(!bBreak)
push(NodeToReOrder);
}



I'm wondering if my ReOrder function is a total waste of cycles and there is a simpler way to do it.
BTW: NodeQ is a vector<MapPath_Node*> if it wasn't obvious.

Share this post


Link to post
Share on other sites
std::priority_queue fails hard.
libstdc++ (the standard library of C++) provides a much more advanced priority queue framework (one that is actually useful)

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
std::priority_queue fails hard.
libstdc++ (the standard library of C++) provides a much more advanced priority queue framework (one that is actually useful)


er... std is the standard C++ lib. Or are you talking about something else?

Share this post


Link to post
Share on other sites
Quote:
Original post by vs322
So I have implemented a vector based Q that can be reorded. Here are the interesting bits:
*** Source Snippet Removed ***

I'm wondering if my ReOrder function is a total waste of cycles and there is a simpler way to do it.
BTW: NodeQ is a vector<MapPath_Node*> if it wasn't obvious.
Yes there is a simpler (and more efficient) way, use std::lower_bound to find the insertion point.
However might I point out that you seem to be simply reimplementing assoc_vector from the Loki library. You could simply download and use that instead.

Other than that I'd suggest simply using a std::set.

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