I'm interested in submitting a proposal for this years Google Summer of Code for the Heaps and Queues project ...
You might want to look at the heaps and queue data structures in boost/pending. These are used AFAIK in a few BGL algorithms. Also, you should here:
https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/
There' s a lot of unfinished work on these data structures.
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). A "native" stable priority queue would be great (I.e. where the internal data structure preserves insertion order, without adding extra "cruft" to each element). Searches on the web have found lots of discussion and approaches similar to the one I've used (add a counter to each element), and lots of tree and heap structures that probably do the job, but no ready-made "native" implementations. I'm pretty sure in the various heap and tree structures that there's something obvious and straightforward that results in a good internal data structure for a stable priority queue. It could be there's already one in Boost somewhere - in the containers mentioned above, or somewhere else in the sandbox or a "pending" container, but I didn't have success with a quick perusal. Thanks! Cliff