priority deque

[Antoine Mathys]

Hello,

I'm looking for a free implementation of a priority deque that plays
well with the STL. I have only been able to find a few papers (for
instance
http://www.cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf),
but no code whatsoever.

Just to be clear: a priority deque is like a priority queue but allows
you to remove both the largest and smallest element.

Thanks.

 

[Alf P. Steinbach]

* Antoine Mathys:

Hello,

I'm looking for a free implementation of a priority deque that plays
well with the STL. I have only been able to find a few papers (for
instance
http://www.cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf),
but no code whatsoever.

Just to be clear: a priority deque is like a priority queue but allows
you to remove both the largest and smallest element.

I think perhaps this shows there's a need for access to the underlying
tree data structure (properly abstracted, of course) of std::map.

But if you can go with a little bit of storage overhead, try a std::map.

I think that will be simple, and fairly efficient (log time for
insertion and removal).


Cheers, & hth.,

- Alf