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