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