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