Re: [boost] Can multi-index do this?

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2008-08-18 21:05:18

If you allow random-access to take O(log n) time, then you can have:
    - search and insertion-by-value in O(log n) time
    - insertion at iterator (when you know where to insert) in O(log  
n) time, and O(1) amortized time if insertion is in order
    - erase at iterator in O(log n) time
    - random-access by index in O(log n) time.
That, is, the same as std::map/set, with a small overhead in the O 
(log n) and additional random-access (which isn't possible with  
std::set/map).

The data structure is called an augmented red-black tree (i.e., r/b  
tree with an additional field at the node, which you can compact with  
the r/b color in no overhead to the footprint for most  
implementations).  You'll find it in any data structure textbook.   
It's fairly easy to adapt/augment, e.g., the SGI STL map  
implementation. In practice the cost of insertion should be a bit  
higher (e.g., 20%) for manipulation, and identical for search and  
navigation (e.g., iteration).  Random access would be fast but  
definitely not as fast as vector.
--
Hervé Brönnimann
hervebronnimann_at_[hidden]
On Aug 14, 2008, at 2:08 AM, Daryle Walker wrote:
> Is it possible for Boost.Multi-index, or anything else in Boost, to  
> make a container that is generally random-access (like vector or  
> deque) but efficiently allows removals anywhere (like list)?
>
> -- 
> Daryle Walker
> Mac, Internet, and Video Game Junkie
> darylew AT hotmail DOT com
>
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/ 
> listinfo.cgi/boost