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

Nope, not the same. Sorry, maybe I wasn't clear enough. A set or map is an associative container which supports lookup *by key* and insertion (deletion, etc) *by key*. A "linear list" is any data structure which supports lookup *by position* and insertion,etc *by position*. A map<int, foo> is not a linear list because if I insert another element into the map, the existing elements aren't "pushed right". I can, using std::map, insert an element in log time, but to find the n-th element takes linear time. It is possible to implement a data structure supporting both the operations "insert in position n" and "find element in position n" in log time, I was wondering if there was any interest for it. Sorry about the confusion, Stephen Dolan