C++ - erase from a map/set in a loop

A nice property of a C++ Standard Template Library (STL) map, multimap, set or multiset is that you can insert or erase elements without invalidating existing iterators. This is especially useful if you are looping through a container and in the loop body decide if you want to erase the element currently processed. This article describes the pattern I prefer to write such a loop in the correct way.

If you search for this problem you'll find lots of other styles to write such a loop (for example on stackoverflow), but I don't like all answers I've found for three reasons:

1. Some use the non-standard version of iterator erase(iterator&) which returns an iterator to the next element following the erased element. While this is elegant, not all STL implementations have this function (for example the libstdc++ from g++).
2. They often use pre- and post-increment operators on the iterator inside the loop body, depending if the iterator/element should be erased or not. I find it often confusing as to which increment operator to use and choosing the wrong one will lead to incorrect code.
3. They often use a while loop, which requires the iterator to be declared outside the while loop. Thus the scope of the iterator is greater than the while loop body in which is is mainly used. I like to narrow variable scope as much as possible, so that I can re-use variable names safely and that I can not use variables outside their intended area of use.

Basic version

My pattern to write such a loop avoids all three issues and in additions looks almost like any other loop which iterates over a STL container using a for loop. The trick is to use a second iterator which is always positioned on the following element. This way it is safe inside the loop body to work with the main iterator (it) in any way you want and you don't need to worry about advancing it inside the loop's body. Look at the following template:

std::container c;
for(std::container::iterator it=c.begin(), it_next=it; it!=c.end(); it=it_next) {
  ++it_next;
  ...
}

We are iterating over a container c using the container's iterator from begin() to end() using the iterator it. We are also creating our secondary iterator it_next which is initialized to it (and thus c.begin()). Then at the beginning of the loop we advance it_next to the next element. Now it is safe to use it in any way inside the for loop body. You can call c.erase(it), but then make sure to not use it after this call. At the end of the loop body, when the third argument of the for expression is evaluated, it is set to it_next, which was already advanced.

Note that erasing from a container while iterating over it, only work reliable with forward iterators!

Now for a fully working example. I'll use a std::map of integers and populate it with number 0 to 9. Then in my first loop I erase all odd elements. In the second loop I erase all remaining elements.

#include <cassert>
#include <iostream>
#include <map>
using namespace std;
int main() {
  typedef std::map<int,int> m_t;
  m_t m;
  m[0]=0; m[1]=1; m[2]=2; m[3]=3; m[4]=4;
  m[5]=5; m[6]=6; m[7]=7; m[8]=8; m[9]=9;

  for(m_t::iterator it=m.begin(), it_next=it; it!=m.end(); it=it_next) {
    ++it_next;

    cout << it->first << ' ' << it->second << endl;
    if(it->first & 1)
      m.erase(it);
  }
  cout << endl;
  assert(m.size() == 5);

  for(m_t::iterator it=m.begin(), it_next=it; it!=m.end(); it=it_next) {
    ++it_next;

    cout << it->first << ' ' << it->second << endl;
    m.erase(it);
  }
  assert(m.empty());

  return 0;
}

The expected output of this program is:

[doj@cubicle /tmp]$ c++ test.cpp && ./a.out
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9

0 0
2 2
4 4
6 6
8 8

Improving the basic version

The basic version can be improved, by using a third iterator to store the value of c.end() to avoid calling this method for every loop iteration. It will then look like:

std::container c;
for(std::container::iterator it=c.begin(), it_next=it, it_end=c.end();
    it != it_end;
    it = it_next)
{
  ++it_next;
  ...
}

But what we still don't like is the ++it_next code which needs to be placed as the first statement inside the loop body. But with a slightly redesigned logic in the for loop we can make sure, that it_next is either positioned after it or it points to c.end().

std::container c;
for(m_t::iterator it_end=c.end(), it_next=c.begin(),
                  it = (it_next==it_end)?it_next:it_next++;
    it != it_next;
    it = (it_next==it_end)?it_next:it_next++)
{
  ...
}

Because that is a lot of code to type every time you need such a loop, you can use a define for convenience. In your own code you can also use my foreach.hpp header file, which contains the foreach_e macro shown below and also foreach and foreach_r for a simple container iteration in forward or reverse direction.

/** a for loop to iterate over a container. You can call erase() on i
    if the erase() function does not invalidate iterators different
    from i. This is true for STL map, multimap, set, multiset.
    @param c (STL) container, has to support begin() and end() methods.
    @param i name of iterator which is available in loop body
*/
#define foreach_e(c,i) for(auto end##i = (c).end(), next##i = (c).begin(), \
                                i = (next##i==end##i)?next##i:next##i++; \
			   i != next##i; \
			   it = (next##i==end##i)?next##i:next##i++)

If you use g++ you need at version 4.4 or later to use auto-typed variables. Use the -std=c++0x compile option to enable support for C++0x features. See foreach.hpp how to use the GNU extension typeof if you are using g++ < 4.4.
Microsoft C++ supports auto with version 16 or later (Visual Studio 2010). For earlier versions you can use Boost.Typeof.

The first loop of the test program would then look like:

foreach_e(m, it) {
  cout << it->first << ' ' << it->second << endl;
  if(it->first & 1)
    m.erase(it);
}
cout << endl;
assert(m.size() == 5);

Contact

For questions and comments about this pattern write to Dirk Jagdmann <doj@cubic.org>.