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.