[boost] [review] Heaps: size and stability

Subject: [boost] [review] Heaps: size and stability
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-02 11:08:10

Tim,

Do you really need to parametrize the constant-time size property?
C++11 requires constant time size for all containers. I think that
this is also a reasonable requirement for Heaps. I'm not aware of any
applications that use so many heaps that the extra 4-8 bytes required
by a size parameter would make huge difference in memory usage. Also,
for heaps that can be effectively implemented in terms of other
containers, they should guarantee O(1) size.

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.

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.

Andrew