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 06:44:20

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

tim