[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 12:00:30

-
  How about a sequence container (like a vector) with the advantage of
logarithmic time insertion/removal at any point of the sequence? The
disadvantage is that random access takes logarithmic time too (instead
of the usual constant time random access of a vector).

  Here it is:
    http://sourceforge.net/projects/avl-array

  It is implemented with a tree, but it is _not_ a map. The 'position'
of elements in avl_array are always natural numbers (0, 1, 2... up to
size()-1). When an element is inserted/removed, it changes
automatically the position of all elements after it in the sequence
(in logarithmic time!).

  A simple experiment realized consisted in populating a container by
inserting random numbers in random positions, and then removing
numbers from random positions, showing the value of the last one for
checking. In this test AVL Arrays completely outperform list, vector
and deque. The test code and the results are in sourceforge too.

  Version 1.1 includes a new experimental feature that I call
"Non-Proportional Sequence View". In the normal sequence, every
element occupies a position of size 1. Additionally, elements can be
viewed as a sequence where the 'width' of every element can be changed
(in O(log n) time), being the position of every element the sum of the
widths of all previous elements in the sequence. Negative widths are
forbidden, but zero widths are valid. The type used for the width is a
template parameter, so any class supporting some operators can be
used, not only unsigned or double.

  I've tried to adapt it to the boost requirements, but I'm sure
there's still a lot of things to change. If you are interested, please
take a look at it, and tell me your opinion.

  Regards,

  Martin Knoblauch Revuelta
  Universidad de Alcala