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

From: me22 (me22.ca_at_[hidden])
Date: 2006-07-29 14:16:36

On 7/29/06, Stephen Dolan <stedolan_at_[hidden]> wrote:
> The STL contains vector, which has O(1) lookup and O(n) insertion. It
> also has list, which has O(n) lookup and O(1) insertion. There is also
> a third type of container, which doesn't exist in the STL, which has
> O(log n) lookup and O(log n) insertion. (For those who have read
> Knuth's TAOCP, it's a balanced tree with the RANK field). AFAIK, there
> is no well-known name for this structure, but a linear list with both
> operations fairly fast seems a useful item to have.
>
Sounds much like a map< size_t, T > to me...