hey, sry for the delay, this got lost in my inbox :/
Now that I have more thoroughly examined Boost.Heap, I can conclude that implementing the following concepts and interfaces would impractical when mimicking the STL priority_queue interface, which allows the user to specify the type of underlying container: - Template options. These would require that I depart from the interface of std::priority_queue.
std::priority_queue provides a very limited interface. extending or using a different interface is not necessarily a disadvantage ;)
- Stability. Adding a stability counter would require modifying the type stored in the underlying container and would (slightly) decrease performance.
boost.heap follows the principle that you only pay for what you use: if you don't configure the data structure to have a stable heap order, you won't have any performance overhead.
- Mutability. I'd need to implement handles, which have the same objections as stability. I have provided a more limited version of Boost.Heap's mutability, which modifies at an iterator.
see above: you only pay for what you use. for d-ary heaps (which keep the tree in an array) mutability requires an indirection: the values are stored in std::list and the actual heap only contains list iterators. side note: this indirection may actually be a performance benefit if copying a value is (much) more expensive than copying an interator. the reason or choosing an opaque handle instead of using iterators is that handles are never invalidated, while iterators can be.
- Ordered Iterators. I can think of at least one way to add these, even without departing from STL's interface, but it is not truly practical because it would require O(n) additional memory.
the idea behind boost.heap is to provide ordered iterators, no matter if their implementation is efficient or not. in some cases (check ordered_iterator_adaptor.hpp) they need to keep track of the unvisited nodes. however there are use cases for traversing all elements in heap order.
in theory, yes ... though i doubt this is an issue in the real world ... especially one can do quite a lot of work before a 64bit counter overflows and if this really turns out to be a problem ... just use a larger counter ;)
Yes, it's true that a 64-bit counter does effectively solve the problem. However, using a large counter may decrease performance (especially if it increases the likelihood of a page fault), and increase required memory. Thus it may be worthwhile to have the failsafe fix all problems, if for no reason other than permitting safe use of smaller counters on mobile or low-memory devices.
does the space overhead really matter on these devices? iac, i do have a prototype for re-assigning the stability counter if an overflow will occur ... but this requires ordered iterators ;) cheers, tim