How NOT to erase elements while iterating

Erasing elements of the container while iterating over them can be hazardous and hard to debug. We need to be very careful about it.

Consider the following C++ code.

Example Problem 1

When we run this code, it fails with Segmentation Fault. Why?

Let’s look at what the standard says about erasing an iterator.

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

Look at lines from 13 to 15 in the above code. The following sequence of events happens along those lines.

Line #13: For-loop starts with iterator it pointing at s.begin().
Line #14: The first element of the set is 0. That’s why *it is 0 and if-condition satisfies.
Line #15: s.erase(it) erases the iterator, and hence also the element pointing by it, from the set s.
Line #13: it++ happens. Here’s the problem. If we look at the standard, it says that after erasing the iterator, the iterator and the element it points becomes invalidated. And hence, iterator it just after erase (Line #15) is invalidated. Because of this, when it++ happens, it is undefined behaviour and leads to the error.

From the above example, we learned that we should always avoid accessing the iterator just after erasing it.

Then, how to correct the above code?

Solution 1

This solution is simple. Store the current iterator in another variable, and increment the iterating iterator one step ahead. So that even if we erase the current iterator, stored in another variable, the iterating iterator will always point to the next position. Look at lines from 12 to 16 in the below code to understand this.

Solution 1

Solution 2

From C++11, erase function returns an iterator to the element that follows the last element removed (or set::end, if the last element was removed).

Look at lines from 12 to 17 in the below code to understand how we’re fixing the problem using the above fact.

Solution 2

With the knowledge we learned so far, let’s try to answer the AlgoTwister 9.

AlgoTwiser 9

The only difference between the code we’ve seen at the beginning of the discussion, and AlgoTwister’s code is that in the AlgoTwister they used the Range-based for-loop.

So in order to understand this fully, we first need to understand how Range-based for-loop is translated into traditional for-loop.

The range-based for-loop statement

for ( range-declaration : range-expression ) loop-statement

is equivalent to

{
   auto && __range = range-expression ;
   auto __begin = begin_expr ;
   auto __end = end_expr ;
   for ( ; __begin != __end; ++__begin) {
       range-declaration = *__begin;
       loop-statement
   }
}

That means the range-based for-loop in the AlgoTwister’s code is translated to the traditional for-loop as:

{
    auto && __range = s;
    auto __begin = begin(__range);
    auto __end = end(__range);
    for ( ; __begin != __end; ++__begin) {
        int u = *__begin;

        if (u % 2 == 0) {
            s.erase(u);
        }
    }
}

If you look carefully, this looks similar to what we’ve seen at the start of the discussion.

As we erase the element and the iterator is currently pointing to, the iterator gets invalidated and is incremented afterwards, which is undefined behaviour.

And therefore, AlgoTwister’s code throws the Segmentation fault.

Note that whatever we have seen so far holds true for other STL containers as well like multiset, vector, map, multimap, and so on.

We hope this discussion helps you to understand the details of the erasure of iterators in C++.

References

1. https://en.cppreference.com/w/cpp/container/set/erase
2. https://en.cppreference.com/w/cpp/language/range-for
3. https://stackoverflow.com/questions/2874441/deleting-elements-from-stdset-while-iterating
4. https://stackoverflow.com/questions/263945/what-happens-if-you-call-erase-on-a-map-element-while-iterating-from-begin-to/263958#263958
5. https://stackoverflow.com/questions/51744166/removing-an-element-from-a-stdset-while-iterating-over-it-in-c17