Boost logo

Boost :

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,

> 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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at