
Boost : 
Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex HagenZanker (ahh34_at_[hidden])
Date: 20120924 11:27:59
On 24/09/2012 14:25, Rob Stewart wrote:
> On Sep 24, 2012, at 7:07 AM, Alex HagenZanker <ahh34_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 single free store allocation does make a difference of course. I
don't really understand how locality of reference plays a role. Are both
options not equally local?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk