Tom Lachecki

Keeping it low-key this week, let's re-iterate (lol) the conventional map-erase idiom in C++.

Iterating through the elements of a std::map is easy enough, but complication arises when you want to delete a few elements as you go.

The first naive approach might look a little like this:

#include <map></p> <p>int main() { typedef std::map<int, int> M; typedef M::iterator I; M m; /<em> (populate m..) </em>/</p> <pre><code>for (I it = m.begin(), end = m.end(); it != end; ++it) { if (it->first == 3) m.erase(it); // remove elements whose key is '3' }</code></pre> <p>}

Unfortunately, after you've erased the element from the map, the iterator pointing to it is invalidated. When the loop goes to run ++it ready for the next iteration, this invokes UB… meaning you should never do it. It's invalid.

So what to do? If you do ++it before performing the erase, then it's safe, but then you don't have the iterator to erase any more. You can use a copy:

for (I it = m.begin(), end = m.end(); it != end; ) { if (it->first == 3) { M::iterator copy = it; ++it; // increment ready for the next iteration m.erase(copy); // remove via original iterator } else { ++it; // just increment } }

Note the important change to the for declaration. The increment on each loop is replaced by the conditional increment in the body.

A shorter version of the same thing is:

for (I it = m.begin(), end = m.end(); it != end; ) { if (it->first == 3) m.erase(it++); else ++it; }

This works because it++ inherently makes a copy, performing the increment after the original value is sent to erase, but before the erase actually occurs.

Coming soon…

Other standard containers make this a lot easier; the next C++ standard, due for completion this year (or possibly in 2012), will fix this omission for std::map by allowing m.erase to return the next iterator automatically:

for (I it = m.begin(), end = m.end(); it != end; ) { if (it->first == 3) it = m.erase(it); else ++it; }