How can I delete elements of a std::map with an iterator?

Question

I would like to loop through an std::map and delete items based on their contents. How best would this be done?

Answer 1

If you have a C++11-compliant compiler, here's an easy way to do this:

std::map<K, V>::iterator itr = myMap.begin();
while (itr != myMap.end()) {
    if (ShouldDelete(*itr)) {
       itr = myMap.erase(itr);
    } else {
       ++itr;
    }
}

The idea is to walk the iterator forward from the start of the container to the end, checking at each step whether the current key/value pair should be deleted. If so, we remove the element iterated over using the erase member function, which then returns an iterator to the next element in the map. Otherwise, we advance the iterator forward normally.

If you do not have a C++11-compliant compiler, or you're working with an older codebase, things are a bit trickier. Before C++11, the erase member function would not return an iterator to the next element in the map. This meant that in order to remove an element while iterating, you'd need to use a three-part dance:

1. Copy the current iterator.
2. Advance the current iterator to the next element.
3. Call erase on the copy of the old iterator.

This is shown here:

std::map<K, V>::iterator itr = myMap.begin();
while (itr != myMap.end()) {
    if (ShouldDelete(*itr)) {
       std::map<K, V>::iterator toErase = itr;
       ++itr;
       myMap.erase(toErase);
    } else {
       ++itr;
    }
}

This process was required because if you just called erase on the iterator, you'd invalidate it, meaning that operations like increment and decrement would lead to undefined behavior. The above code gets around this by setting up a copy of the iterator, advancing itr so that it's at the next element, then erasing the temporary copy of the iterator.

Using some Clever Trickiness, it's possible to shrink this code down at the expense of readability. The following pattern is common in older C++ code, but isn't necessary in C++11:

std::map<K, V>::iterator itr = myMap.begin();
while (itr != myMap.end()) {
    if (ShouldDelete(*itr)) {
       myMap.erase(itr++);  // <--- Note the post-increment!
    } else {
       ++itr;
    }
}

The use of the post-increment operator here is a clever way of making a copy of the old iterator (remember that a postfix ++ operator returns a copy of the original iterator value) while also advancing the older iterator.