On Sep 24, 2012, at 9:31 AM, Tim Blechmann <tim@klingt.org> 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 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?
As long as you don't erase from the middle, which I would guess you probably do.