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.