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

From: Stephen Dolan (stedolan_at_[hidden])
Date: 2006-07-29 13:54:17

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