Hi Cliff,
One container I've needed in the recent past is a stable priority queue. This is a priority queue that maintains insertion order (FIFO) for entries with equal priority (std::priority_queue does not guarantee stable insertion order). It's pretty easy to adapt std::priority_queue for a "home grown" container (e.g. add a counter to every entry), but all of the obvious and easy ways to adapt the container have a cost or drawback (more memory, integer count overflow, etc).
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. Andrew Sutton andrew.n.sutton@gmail.com