Re: [boost] Heaps and Queues for GSoC - stable priority queue?

Subject: Re: [boost] Heaps and Queues for GSoC - stable priority queue?
From: Cliff Green (cliffg_at_[hidden])
Date: 2010-03-19 12:56:37

>> 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