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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk