• Advertisement
Sign in to follow this  

std::priority_queue questions

This topic is 3413 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

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
Advertisement
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
Sign in to follow this  

  • Advertisement