That's an interesting requirement. It may be the case that some of the more exotic heaps can be used to do something similar. This seems like it would be a good issue to address (and possibly solve) as part of a larger summer project.
Cool! I was thinking the (relatively small) scope and domain (heaps and queues) fits well for a GSoC project. The use cases where I've needed a stable priority queue have been networking related, but I'm sure there's other domains with similar use cases. To reiterate, a stable priority queue maintains insertion order (FIFO) for entries with equal priority (std::priority_queue does not guarantee insertion order). I've needed this to implement priorities for outgoing message queues, where higher priority messages get put at the front of the queue. But it's important that messages with similar priority maintain the insertion order. There's obvious ways to make this work by adding extra data (counter or time stamp), or by creating a different data structure (e.g. hash table of simple queues), but there's drawbacks to each of these approaches. A "native" stable priority queue would not add any memory or data structure overhead, at the cost (I'm assuming) of a slightly more complex internal tree or heap structure / ordering algorithm. This "low memory overhead" is important because of both the "small" and "large" use cases. For example, an embedded system might need a simple stable priority queue that is lean and mean as possible. I'm currently looking at some CAN network related programming, and each device on the network is very limited in memory and processing power (the anticipated price point for the associated product is a few dollars). If I end up writing code for it, I'd love to be able to use Boost facilities as much as possible (I don't know the development environment yet, so don't know if it will be possible). On the other end of the use case scale, an outgoing queue might be in a large scale environment with gigs of memory, but the queue might need to have a large number of entries (e.g. millions). In this case, even a small bit of extra memory (e.g. an integer counter, as I've implemented in the past) has large costs. BTW, I see this container as having the same interface as std::priority_queue, but with the additional ordering guarantee. I would assume a good name is boost::stable_priority_queue, but there may be other people with more experience with this kind of container that can suggest better alternatives. Thanks, Andrew, and any GSoC participants that take this on. Cliff