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

From: JOAQUIN M. LOPEZ MUÑOZ (joaquin_at_[hidden])
Date: 2008-08-14 10:12:19

Hi Daryle,

________________________________________
De: boost-bounces_at_[hidden] [boost-bounces_at_[hidden]] En nombre de Daryle Walker [darylew_at_[hidden]]
Enviado el: jueves, 14 de agosto de 2008 8:08
Para: boost_at_[hidden]
Asunto: [boost] Can multi-index do this?
>
> 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)?

As Sebastian has already pointed out, it does not seem possible
to have O(1) lookup and O(1) insertion/removal simultaneously.
That said, Boost.MultiIndex has so-called random-access indices:

http://www.boost.org/libs/multi_index/doc/tutorial/indices.html#rnd_indices

which have O(1) lookup and very fast removal: although erasing
an element is O(n), it does not actually incur any element shifting,
as it is only an internal vector of pointers that gets adjusted. This
can be much faster than std::vector removal when the elements
are of moderate size (though, still, it is not O(1)).

A drawback of random indices in comparison with std::vector is
that elements of multi_index_containers are immutable. Incidentally,
I happen to have recently implemented a *stable* vector, a
container that mimics the interface of std::vector with the differences
that element contiguity is not observed and, in exchange, the container
is stable, i.e. iterators and references to the elements remain valid
regarldess of the insertions/removals being performed. This
container, again, has O(n) removal but no element shifting. If this
is of your interest I plan to publish this little work in my
blog (http://bannalia.blogspot.com ) during September.

HTH,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo