Re: [boost] [review] Heaps: size and stability

Subject: Re: [boost] [review] Heaps: size and stability
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-02 13:27:56

hi,

> Do you really need to parametrize the constant-time size property?

the design to customize the data structure is directly related to 
boost.intrusive ... and basically it does not hurt to be able to customize it, 
even if the effect may be marginal ...

> The stability issue relates to a previous discussion from a couple
> months ago (brought up by Cliff Green,
> http://article.gmane.org/gmane.comp.lib.boost.devel/219330). Cliff was
> concerned that the implementation of stability added overhead to the
> normally unstable heaps (i.e., an extra size_t, I think) from the
> implementation. I worry that the use of a policy parameter to specify
> stability will result in "accidental overhead" in cases where users
> don't fully understand the impact of their configuration choices.

it is not possible to write every heap algorithm as `stable' heap. i do not 
recall the exact point that will break stability if one just orders the nodes in 
the tree, but there was a non-trivial issue (possibly related to mutable heaps). 
iac the node versioning seems to be the usual approach for implementing stable 
heaps. the type of the version should be exposed to the interface, though, so 
one can specify arbitrary-sized integer types to avoid overflows ...

> Would it be better (would it be possible?) to write stable_heap as a
> heap adaptor? I think that this approach (if possible) has two
> benefits. First it encapsulates the strategy for implementing
> stability. It also provides a single point of reference for describing
> the impact of using that configuration.

what do you mean by `heap adaptor'? at the moment, i am using the same 
implementation, but customize the node type ...

tim