Here is a tentative implementation of priority_deque as a thin wrapper around STL-like interval heap functions (provided in interval_heap.hpp): https://github.com/nmcclatchey/Priority-Deque/tree/Thin-Wrapper The function interfaces in interval_heap.hpp are likely to change as I more thoroughly examine the heaps in STL and Boost.Heap.
having fifo/max lifo/min would be quite reasonable. a fifo of both min and max sides could probably be achieved by using use stability
An implementation using a single stability counter modifies the comparison (which must be a strict weak ordering) to break ties according to the order in which the elements were added. For a priority queue, newer objects are considered "less" than older objects. For a priority deque, breaking ties in favor of one direction precludes breaking of ties in the other. Thus, simultaneous FIFO max and LIFO min is trivial (use the same stability counter as used for the priority queue), but that particular method cannot be used efficiently for simultaneous FIFO max and FIFO min. I don't believe that using two stability counters would help, but if you've got ideas or (preferably) details about how it could be accomplished, I would be happy to read them. While I'm on the subject of stability counters, I believe I can improve on the method used in Boost.Heap's stable priority queue. In particular, the Boost.Heap queue does not handle integer overflow except by throwing an exception. A better way to handle overflow would, I believe, be to sort the underlying container according to its counters (O(n^2), O(n log n), or O(n), depending on sort used). Follow this by editing the counters to be consecutive from the minimum possible value (O(n)), and by re-building the heap (O(n)).