Re: [boost] Interest in O(log n) linear list?

From: Stephen Dolan (stedolan_at_[hidden])
Date: 2006-07-29 14:25:02

Ok, here's an example.
map<int, char> list;
list[0] = 'a';
list[1] = 'b';
list[2] = 'c';
list[3] = 'd';

So, the nth element of the list is list[n].

How do I insert an element into the middle of the list?
I have to move all the other elements out of the way.
e.g. if I make 'x' list[2], then I want list[3] == 'c' and list[4] == 'd'
Using std::map, you have to change them all giving O(n) performance.

There is another data structure, *not in the STL*, which can emulate
linear lists using a binary tree, thus giving log n performance for
all operations. It is *not* an associative structure like set or map,
but a *linear list* like list or vector. It's semantics are exactly
the same as the semantics of list or vector, but with different
complexities.

HTH,
Stephen Dolan