hey,
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.
one will have to change the way the stability counters are used: one possibility is to have a list of elements for each key (priority) and look for the maximum stability count for the minimum or maximum side. this is more a node-based approach, which probably does not translate very well to a container adaptor, though ... i had been thinking about the chaining of identical keys when implementing boost.heap ... it has the nice advantage that it slightly simplifies the tree structures
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)).
yes, the handling of the stability count is a bit fragile, though 64bit integers are probably enough to prevent overflows in most applications. a simple way to prevent the overflow could also be to simply subtract the minimum value of all stability counts, which could be done in O(n) by traversing the heap twice. cheers, tim