Consistency when removing items from boost multi-index using an iterator

Question

I know that the following code is not correct, for std::vectors and more generally all STL containers:

std::vector<something>::iterator it = array.begin();
for(; it != array.end(); it++) {
   ...
   array.erase(it);
   ...
}

because the iterator needs to be updated after erasing and element.

I was wondering if it's the same for a boost multi-index, e.g would something like the following be correct or not:

my_index::iterator it = index.get<0>().begin();
for(; it != index.get<0>().end(); it++) {
   ...
   index.erase(it);
   ...
}

I'd like to be sure to understand well the following paragraph of the documentation: http://www.boost.org/doc/libs/1_51_0/libs/multi_index/doc/tutorial/indices.html#guarantees which seems to state that I can erase without invalidating the iterator. However I'm not sure if because I delete an element, another element that I would be supposed to visit during the iteration could be moved before the current iterator's position and never be visited (in other words, by erasing some elements during the iteration, am I still sure to go through all the elements?).

Thanks!

ecatmur · Accepted Answer · 2012-10-22T09:16:55.977

The paragraph you linked only applies to hashed (unordered) indices. It states that when inserting new elements, hashed index iterators remain valid.

When erasing, for ordered indices you can always guarantee complete iteration by using the return value from erase:

for (; it != index.get<0>().end(); ) {
    if (...) it = index.erase(it);
    else ++it;
}

This will also work for hashed (unordered) indices, as the iteration order is stable over erasing elements.

score 3 · Answer 2 · edited Jun 20 '20 at 09:12

No, your action is not valid in a boost index. Iterators erased from a collection never remain valid, what can remain valid is other iterators within the collection, should you be storing them somewhere.

The actual text is:

Guarantees on iterator validity and exception safety

Due to the internal constraints imposed by the Boost.MultiIndex framework, hashed indices provide guarantees on iterator validity and exception safety that are actually stronger than required by the C++ Standard Library Technical Report (TR1) with respect to unordered associative containers:

Iterator validity is preserved in any case during insertion or rehashing: TR1 allows for iterator invalidation when a rehash (implicit or explicit) is performed. Erasing an element or range of elements via iterators does not throw ever, as the internal hash function and equality predicate objects are not actually invoked. rehash provides the strong exception safety guarantee unconditionally.

TR1 only warrants it if the internal hash function and equality predicate objects do not throw. The somewhat surprising consequence is that a TR1-compliant unordered associative container might erase elements if an exception is thrown during rehashing! In general, these stronger guarantees play in favor of the user's convenience, specially that which refers to iterator stability. A (hopefully minimal) degradation in performance might result in exchange for these commodities, though.

Does this mean that if I create a copy of the original iterator, this copy remains valid? Like if I do iterator it2 = it; index.erase(it); it = it2; it would work? — sunmat, Oct 22 '12 at 10:05
No, you are "erasing" a copy anyway, you can assume erase takes its parameter by value. You should use remove_if algorithms which are always guaranteed to work. — CashCow, Oct 22 '12 at 10:10

Consistency when removing items from boost multi-index using an iterator

2 Answers2

Linked