Hi Daryle, ________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Daryle Walker [darylew@hotmail.com] Enviado el: jueves, 14 de agosto de 2008 8:08 Para: boost@lists.boost.org 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