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?