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