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

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.

                              HTH,
                              Cromwell D. Enage

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com