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-31 07:34:17

On 10/31/06, Martin Knoblauch Revuelta <mkrevuelta_at_[hidden]> wrote:
> The width is based on the same concept as count, but they are not
> related at all. Note that W might be float, for example.
>
> I might deduce m_total_width from m_node_width by recursing through
> the whole subtree every time. Obviously, this would spoil the whole
> thing.

I don't entirely understand the benifit of your 'non-proportional
sequence view'.  What use cases can you think of where this would be
beneficial to client code?  Right now it seems like it adds
unjustified bloat to the library.

> > * I get the impression that there's is way more code than needed to
> > implement this data structure.
>
> I'm trying to refactorize some things, but it's a large interface... ;-)

Large interface == monolithic design.  As much as possible, I would
try to stick to just implementing member functions that are already
member functions of other container types.  Everything else should be
a free function, perhaps in an optional utility header of some kind.

> > * Not sure why you would want the various unsigned/int/long vs size_type
> > variations of methods. Having those extra methods just confuses the
> > interface for users and introduces extra use cases to account for in the
> > implementation.
>
> It helps avoiding ambiguities when T is an unsigned/int/long. This is
> how other container implementations solve it.

What ambiguities?  Implicit conversions exist between built in types,
so if there is no algorithmic difference I don't understand this
justification.

> > and keeping exceptions in mind you do a swap in between :-)
>
> Exceptions? Swap?

He is referring to a pattern where you would create a temporary
<sequence name here> object, build up that object, and then swap the
two sequences (just swap their root pointer values).  This would
ensure that if you can't finish building the tree then the nodes you
added will be released automatically.  Essentially, commit/rollback
without a try/catch.

> > * You have a variety of C style casts, and you happen to be casting
> > "this". That's frowned upon, and truthfully I can't see why you do it.
>
> I'll change them to C++ casts.
>
> With this trick, neither iterators nor tree nodes need to contain a
> pointer to the avl_array object where they "belong", while the
> interface allows working with iterators without requiring references
> to the corresponding avl_array objects.

I would say that slightly more space overhead would be preferable to
tricky and less straight forward code.  Although I'm not sure why
either the nodes or the iterators should be aware of the container
they are a part of to begin with.

>
> > * Algorithms rarely have a place in STL containers. You might want to
> > move the various binary_search, sort, etc. methods to functions.
> > Preferably having them use the same interface as the STD versions.
>
> I'll study this too.

One of the most important features of the stl is that it separates
algorithms from the container types they operate on.  Most of these
algorithms already exist in the stl.  What is your justification that
they need to be overridden for your container in the first place?

>
> > * I would make the value sorted aspect a separate container, possibly as
> > an adaptor to the rank container but possibly also some other form of
> > tree. Sorted ordering is orthogonal to rank statistics.
>
> Why? I wouldn't like to restrict the hybrid use of a container object.
> I mean, using it as a sorted container for a while, then using it as
> unsorted for a while, then sorting it again, maybe with a different
> criterion, and so on... Note that iterators would remain valid through
> the whole process...

Because it desimplifies the interface, causing bloat and making client
code potentially pay for features it doesn't want/need.  I would
prefer a separate container type (perhaps
priority_<sequence_name_here>) which would behave more like a stack or
queue.  It could allow pushing and popping values into sorted order
and forbid arbitrary location inserts by the user.

Supporting both random location inserts by the user and sorted inserts
doesn't make sense.  The container no longer has control over its
invariants.

-Jason