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.