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

On 7/29/06, Stephen Dolan <stedolan@gmail.com> 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...