Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2012-09-24 10:23:40

On Sep 24, 2012, at 9:31 AM, Tim Blechmann <tim_at_[hidden]> wrote:

>>> I am just interested to see the fundamental difference between the
>>> Boost.Graph d_ary_heap and Boost.Heap d_ary_heap. Because the
>>> statement that Graph is optimized for integer values does not seem
>>> correct. I noticed that Graph manages the handles through an array
>>> and Heap through a std::list and considered that there might be
>>> some difference in performance because of that.
>>> 
>>> Probably the difference is minute, but at the same time it is the
>>> only place where I see that Graph makes an assumption (the total
>>> number of values pushed onto the heap is known) that Heap cannot
>>> make.
>> 
>> Locality of reference and a single free store allocation are
>> sufficient reasons for Graph's implementation to be faster. Perhaps a
>> deque would be better than a list for Heap.
> 
> the implementation assumes that std::list iterators are always valid as
> long as the referred object is part of the list. does this property
> apply to deque?

As long as you don't erase from the middle, which I would guess you probably do.