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

Subject: Re: [boost] [Container] Priority Deque - Refinement
From: tim (tim_at_[hidden])
Date: 2013-11-26 02:14:44

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