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

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-10-25 15:22:20

Martin Knoblauch Revuelta wrote:
>   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).

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.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo