# 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.

## 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 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 on other sites
Sort of what I thought. Thanks for the answer.

##### 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 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 on other sites
Quote:
 Original post by loufoquestd::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 on other sites
Quote:
 Original post by vs322So 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 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.