From the docs on stable priority queue:
"If a priority queue is configured to be stable, an integer timestamp is associated with each node, specifying the time ..." I was one of the people discussing priority queue use cases, probably a year ago, and specifically was wanting a stable priority queue. I also said that adding a time stamp or counter to each entry was a naïve approach (and one that I had done myself in about an hour, adapting a std::priority_queue). I asked for a true, "native" implementation of a stable priority queue, because adding a time stamp to each entry has a couple of drawbacks: 1) It adds storage to each element - while for many (most?) applications this extra storage is negligible, in some cases it is not negligible (embedded systems with large queues) 2) It can fail - if a true time stamp is used, what happens when times are adjusted? If a counter is used, what happens when the counter overflows? While the failures are edge cases, there's no need to have any failures. I can dig out the e-mail, if more details of the discussion are needed. I'm a bit perplexed that either this discussion was completely missed, or somehow "read but misremembered, with the opposite of the desired result". There must be heap data structures for priority queues that preserve order (with no extra memory) at the cost of being slightly slower (but still with the same big-O complexity). This is what I expect of a Boost library - finding and implementing the best, not something naïve and easily thrown together. So this gives me very little confidence for a robust, world-class implementation of heap structures. Please read this as encouragement to do the hard work, not just the minimum necessary for a review, at least for the case mentioned in this e-mail. Cliff