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?

Solution 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.

Solution 2

for(MyMap::iterator it = mymap.begin(); it!=mymap.end(); ) {
  if(mycondition(it))
    it = mymap.erase(it);
  else
    it++;
}

edit: seems that this works in MSVC only

edit2: in c++0x this works for associative containers too

Solution 3

This is one simple way:

    int value_to_delete( 2 );
    for( std::map<int, int>::iterator i = mm.begin(); i != mm.end(); ) {
        if( i->second != value_to_delete ) {
            mm.erase( i++ ); // advance before iterator become invalid
        }
        else {
            ++i;
        }
    }

Comments

[templatetypedef]

This will work for sequence containers like std::vector, but not for associative containers like std::map. The difference is that in sequence containers erase() returns an iterator to the next element, whereas in associative containers it returns void.

[Admin]

so if I had a vector like this: 10, 11, 12, 13, and the iterator deleted 11 while incrementing, it wouldn't skip over 12?... if that makes sense. because I am wondering if when I delete 11, 12 will move into the 11's spot, and I will miss 12...

[Admin]

I think you just answered it in a comment on @Timo's answer, but if you could clarify, that would be great.

[templatetypedef]

For the vector case the logic is different (See Timo's example below); after you erase() something, all iterators at or after the erase point are invalidated. To know where to pick up, you can therefore capture the value of the erase() function. With a map, the only invalidated iterators from an erasure are iterators to the element that got deleted.

[Timo]

@templatetypedef: hmmm, that's funny because the associative containers in MSVC work differently: msdn.microsoft.com/en-us/library/z2f3cb7h.aspx I guess it's non-standard then.

[templatetypedef]

Just confirmed from Table 69 of the ISO spec that it should return void. I guess the MSVC version is nonstandard... I never knew that!

[Tamas Demjen]

It works now in C++11. However, still there are many compilers not ready for C++11. So mymap.erase(it++) is more portable.

[Avrdan]

This is a great answer. The only thing missing is comparing this with the std::vector behavior and contrasting it, but I suppose that would go a bit into a different topic.