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

From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2006-10-25 22:38:55

Rene Rivera wrote:
> Martin Knoblauch Revuelta wrote:
> >   How about a sequence container [..].
>
> I was wondering how long it would take this to make it from the usenet
> groups to here :-)
>
> I've mentioned this type of container here in the past, under the name
> of "rank_tree". Very soon now I will have the version I wrote, and use,
> ported to the framework that Bernhard produced for the SoC tree project.
> You can look at the draft TR
> <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/libs/tree/doc/html/d2102.html?format=raw>
> that mentions it, and other trees.
>
> I don't have time to look at your implementation right now. But perhaps
> you could comment on how you think your implementation might fit within
> the above. And of course if there's something we haven't thought about.

Well, maybe the most important thing is the experimental feature NPSV
that I added in version 1.1. I described it briefly in my message, but
there's a detailed description in the notes for version 1.1 of
stlavlarray.h. The example program in npsvexample.cpp shows it's
behaviour.

Example where NPSV would be useful: a simple avl_array (or rank_tree)
would waste a lot of memory when used for small contained types. This
can be solved with NPSV, by storing more than one contained type
element in every tree node. The 'width' of the node would be the
number of occupied elements in the node, which would contain a
circular buffer.

Additionally, avl_array has the next characteristics (use it as a check list):
* On iterators, ++ and -- are O(1)
* begin(), end(), rbegin() and rend() are all O(1)
* Copy constructor, assignment operator and destructor are O(n)
* Other constructors, where the number of elements is known, are O(n)
* Comparison operators are all O(n)
* reverse(), merge(), and unique are O(n)
* avl_array swap is O(1)
* element swap is O(1) unless when NPSV is used _and_ the elements'
widths don't match (then it is O(log n))
* element swap also works between two different avl_arrays
* resize, range-insert and range-erase take O(m log n) when m is
small, but O(n) when m is reasonably significant compared to n. (m:
number of elements to insert/erase; n: size of the array)
* move() is O(log n) unless it is a single-position move, in which
case it is done with a swap
* both sort() and stable_sort() are provided with O(n log n)
* search tree methods are provided
* insert_anywhere() inserts without rotations favouring balance
(though still O(log n))
* Iterators follow their referenced elements, even when theese are
moved from an avl_array to another one

Can all this be done with generic trees while keeping them simple,
efficient and usable for other purposes where the hierarchy is visible
to the user?

Regards,

Martin Knoblauch Revuelta