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

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-09-24 07:07:46

On 24/09/2012 11:44, Tim Blechmann wrote:
>>>>>> Boost heap uses a std::list, where the handle is an iterator
>>>>>> to an element in the list and the value is stored in the
>>>>>> list. This makes sense because for Boost.Heap the number of
>>>>>> values may be infinite, and an array for all values would
>>>>>> explode.
>>>>>>
>>>>>> However, it also seems that a list provides more
>>>>>> functionality and overhead than necessary as it keeps its
>>>>>> values sorted. I would therefore expect that using an
>>>>>> unordered list instead of a std::list would improve
>>>>>> performance of boost.heap without sacrificing generality.
>>>> Are you thinking of set/map versus unordered_set/map? list isn't
>>>> sorted by default.
>> It is not sorted, but it is ordered. The iterators go through the
>> elements in the same order that they are added to the list. For the
>> sole purpose of handle fetching and retrieving that is not a
>> necessary requirement. So there are is potential for some gains to be
>> made (probably minute). In particular the insert() and erase()
>> functions can be simpler.
> std::list is only used as dumb container for implementing mutable d-ary
> heaps. it is neither ordered,

http://www.cplusplus.com/reference/stl/list/

> nor does it use insert()

Heap does not use insert() but push_front(), it does use erase().

> , it is basically
> a way to achieve mutability by managing a heap of std::list iterators.
> or what are you referring to?
>
> tim
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.