Re: [boost] [Container] Priority Deque - Refinement

Subject: Re: [boost] [Container] Priority Deque - Refinement
From: Nathaniel McClatchey (njmcclatchey1990_at_[hidden])
Date: 2013-11-25 23:49:06

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