Re: [Boost-users] Need example of substitution of priority queue

Subject: Re: [Boost-users] Need example of substitution of priority queue
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-05-22 14:08:58

On Fri, 21 May 2010, Eric Fowler wrote:

> Thank you. I can now compile with an std::vector<> as my queue, and
> the default color map.

Named parameters should also allow you to use the built-in color map 
generation; you weren't using them before so that's why I told you to just 
add that argument explicitly.

> In looking at the Dijkstra example, I see it is using a
> boost::mutable_queue<>, which has the primary feature of being able to
> dynamically change the sorting criterion. This is exciting but not
> something I need.

It's not dynamically changing, or are you referring to update()?  That 
just lets you update the sort key of an element without removing and 
reinserting it.

> Turning my attention to boost::queue<>, I am trying to see how to
> place my own sorting criteria. It looks like I need to define a class
> encapsulating my data (or deriving from the class that holds my data),
> and to define the usual ordering operators (<,>,==, etc) within that
> class. I would then declare an object of type boost::queue<MyClass>
> and go from there.
>
> Is that the "cheapest" way to get a priority queue with a custom sort order?

boost::queue<> is unsorted, so you cannot use a sort order with it.  Are 
you sure your problem is not just shortest paths with custom compare 
and/or combine operators?  That is the easiest way: 
dijkstra_shortest_paths sets up the queue, color map, and such for you. 
Otherwise, look at the code in dijkstra_shortest_paths that I pointed out 
and use one of the queues instantiated there.  Note that Dijkstra's 
algorithm does use a custom < operator in its priority queue in the 
mutable_queue variant (in order to use indirect_cmp and the user's 
comparison operator which is not necessarily < either).

-- Jeremiah Willcock