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

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Tim Blechmann (tim_at_[hidden])
Date: 2012-09-24 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?