Boost logo

Boost :

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

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.

Any interest?

Stephen Dolan

Boost list run by bdawes at, gregod at, cpdaniel at, john at