Re: [boost] Can multi-index do this?

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-08-14 12:50:52

Daryle Walker wrote:
> Is it possible for Boost.Multi-index, or anything else in Boost, to  
> make a container that is generally random-access (like vector or  
> deque) but efficiently allows removals anywhere (like list)?

I think that the best you can do is a tree of contiguous fragments, 
i.e. a std::map<size_t, std::vector<T>>.  (Are ropes implemented like 
this?)  Random access involves an O(log #fragments) tree search to find 
the right fragment followed by an O(1) lookup to find the right element 
in the fragment.  Insertions and deletions involve splitting a fragment 
in two (hmm, some memory-allocation magic is needed to make that 
possible without copying one half).  This is efficient if the number of 
fragments is kept small, and this means merging fragments from time to 
time.  It would be great if there were a merge strategy that would give 
amortised O(1) operations, but I doubt it's possible.

Phil.