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

Subject: Re: [boost] [Container] Priority Deque - Refinement
From: Tim Blechmann (tim_at_[hidden])
Date: 2013-12-19 04:14:50

hey,

sry for the delay, this got lost in my inbox :/

> Now that I have more thoroughly examined Boost.Heap, I can conclude that
> implementing the following concepts and interfaces would impractical when
> mimicking the STL priority_queue interface, which allows the user to
> specify the type of underlying container:
> - Template options. These would require that I depart from the interface of
> std::priority_queue.

std::priority_queue provides a very limited interface. extending or
using a different interface is not necessarily a disadvantage ;)

> - Stability. Adding a stability counter would require modifying the type
> stored in the underlying container and would (slightly) decrease
> performance.

boost.heap follows the principle that you only pay for what you use: if
you don't configure the data structure to have a stable heap order, you
won't have any performance overhead.

> - Mutability. I'd need to implement handles, which have the same objections
> as stability. I have provided a more limited version of Boost.Heap's
> mutability, which modifies at an iterator.

see above: you only pay for what you use. for d-ary heaps (which keep
the tree in an array) mutability requires an indirection: the values are
stored in std::list and the actual heap only contains list iterators.
side note: this indirection may actually be a performance benefit if
copying a value is (much) more expensive than copying an interator.

the reason or choosing an opaque handle instead of using iterators is
that handles are never invalidated, while iterators can be.

> - Ordered Iterators. I can think of at least one way to add these, even
> without departing from STL's interface, but it is not truly practical
> because it would require O(n) additional memory.

the idea behind boost.heap is to provide ordered iterators, no matter if
their implementation is efficient or not. in some cases (check
ordered_iterator_adaptor.hpp) they need to keep track of the unvisited
nodes.
however there are use cases for traversing all elements in heap order.

>> in theory, yes ... though i doubt this is an issue in the real world ...
>> especially one can do quite a lot of work before a 64bit counter
>> overflows and if this really turns out to be a problem ... just use a
>> larger counter ;)
> 
> Yes, it's true that a 64-bit counter does effectively solve the problem.
> However, using a large counter may decrease performance (especially if it
> increases the likelihood of a page fault), and increase required memory.
> Thus it may be worthwhile to have the failsafe fix all problems, if for no
> reason other than permitting safe use of smaller counters on mobile or
> low-memory devices.

does the space overhead really matter on these devices? iac, i do have a
prototype for re-assigning the stability counter if an overflow will
occur ... but this requires ordered iterators ;)

cheers, tim