Re: [boost] [proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)

From: Jason Hise (0xchaos_at_[hidden])
Date: 2006-10-26 15:52:09

> >>From the beginning, I designed the avl_array with the clear intention
> > of hiding the tree nature of the implementation to the user's eyes. In
> > this concrete case, I can't think of any benefit coming out of
> > exposing the tree hierarchy. In part because of the banlance
> > operations.
>
> That would be one big difference, which has been brought up before in
> the same context. I don't see a harm to have access to the tree. If you
> really want to limit such access you can make a separate adaptor.

Would there be any benefit to accessing the data structure as a tree
in client code?  If so, shouldn't std::map do the same?

My opinion is that this is a sequence container that gives certain
complexity guarantees, and over-specifying the public interface
restricts potential future implementations.  The fact that the
sequence uses a tree internally is an implementation detail.  And
actually, given that, I think it should be renamed to something that
reflects the strengths of the container, rather than after the
implementation structure.  (Not sure what a good name would be, but
something to think about).

Just my $0.02.