[multi_index] Couple of questions on multi-index containers
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? What are the data structures used internally for this container and its indexes. -- Aaron Levy aaron.levy@yandex.com
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
28.09.2014, 19:06, "Joaquin M Lopez Munoz" <joaquin@tid.es>:
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.
* random-access indices use this:
Aah! Random access and stable, I should have guessed stable_vectors. And the pointers to the implementation are impressive. Thanks.
Hello Joaquin, I just came up with a slightly different question in more or less same direction. Can I safely erase data from the index view in a range based for loop. The index container contains only ordered indices (no random access). I saw a suggestion that an iterator is being invalidated and therefore pre-incrementing it for the next step is fine. But what happens if an element erased via its key itself in a range-based for-loop? Would the next increment work fine? Many thanks, Ovanes On Sun, Sep 28, 2014 at 4:03 PM, Aaron Levy <aaron.levy@yandex.com> wrote:
28.09.2014, 19:06, "Joaquin M Lopez Munoz" <joaquin@tid.es>:
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.
* random-access indices use this:
Aah! Random access and stable, I should have guessed stable_vectors.
And the pointers to the implementation are impressive.
Thanks. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, Sep 29, 2014 at 7:25 PM, Ovanes Markarian <om_boost@keywallet.com> wrote:
Can I safely erase data from the index view in a range based for loop. The index container contains only ordered indices (no random access).
Looks like it is undefined behaviour with std::containers at least. I assume with mi it'd be the same...
Ovanes Markarian <om_boost <at> keywallet.com> writes:
Hello Joaquin, I just came up with a slightly different question in more or less same direction. Can I safely erase data from the index view in a range based for loop. The index container contains only ordered indices (no random access).
No: the definition of range-based for given in [stmt.ranged] actually *guarantees* that you'd produce undefined behavior (the iterator is post-incremented). Joaquín M López Muñoz Telefónica
participants (4)
-
Aaron Levy -
Joaquin M Lopez Munoz -
Joaquín M Lopez Munoz
-
Ovanes Markarian