Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net