Re: [Boost-users] [multi_index] Couple of questions on multi-index containers

Subject: Re: [Boost-users] [multi_index] Couple of questions on multi-index containers
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2014-09-28 09:36:00

Aaron Levy <aaron.levy <at> yandex.com> writes:

> If I erase elements in a multi_index_container, how are iterators
> invalidated?
> 1. For other than random_access index, only iterators to the deleted
> element?
> 2. For random_access index, potentially any iterator?

For all indices, on every ocassion, only the iterators to the deleted
element are invalidated.

> What are the data structures used internally for this container and its
> indexes.

The general structure (how index structures are combined) is explained at:

http://stackoverflow.com/a/4208349/213114

As for the index-specific structures:

* ordered indices use rb trees, just as any std::set in the world.
* sequenced indices are simple bidirectional lists.
* hashed indices use a structure departing from other implementations
  of unordered associative containers:
    
    http://bannalia.blogspot.com/2014/01/a-better-hash-table.html

* random-access indices use this:

    http://bannalia.blogspot.com/2008/08/stable-vectors.html

  This structure is also used to implement the standalone stable_vector
  in Boost.Container:

    http://www.boost.org/doc/html/boost/container/stable_vector.html

HTH

Joaquín M López Muñoz
Telefónica