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

From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2008-08-14 06:37:21

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)?
>
O(1) access through an always continuous key and O(1) removal anywhere 
are unfortunately mutually exclusive goals. The continuity of the keys 
enforces either O(n) removal, since the keys have to be adjusted 
(shifting elements in the vector, for example), or complex index 
calculation (consulting a list of known holes) that cannot possibly be 
O(1) on access.

If you don't need a continuous key, you can map indices to values in 
some associative container.

Sebastian