...

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

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