
Boost : 
Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Gordon Woodhull (gordon_at_[hidden])
Date: 20120924 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk