Boost logo

Boost :

From: Cromwell Enage (sponage_at_[hidden])
Date: 2006-07-29 13:46:29

--- Stephen Dolan wrote:
> 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.

The STL treats trees as either sets or maps. In your
case, you might want to look at std::set first; it
should have the time complexities you're looking for,
in addition to linear iteration through the elements.

                              Cromwell D. Enage

Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around

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