67

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

Flow
  • 23,572
  • 15
  • 99
  • 156
  • 1
    Can you give us an example of what your map contains and what criteria you want to use? A typical approach is to iterate through the contents of the map and call map.erase(iterator); – wkl Jan 05 '11 at 03:30
  • @birryree it doesn't even have to be map... it could be a vector or something else that an iterator can be used on. I'm just looking for a generic answer like @templatetypedef's. –  Jan 05 '11 at 03:34
  • 1
    possible duplicate of [What happens if you call erase() on a map element while iterating from begin to end?](http://stackoverflow.com/questions/263945/what-happens-if-you-call-erase-on-a-map-element-while-iterating-from-begin-to-e) – Martin York Jan 05 '11 at 05:40
  • @MartinYork similiar, but I asked how to do the loop, while he just wanted to know if his loop would work. –  Jan 05 '11 at 22:07

3 Answers3

116

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    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... –  Jan 05 '11 at 03:40
  • I think you just answered it in a comment on @Timo's answer, but if you could clarify, that would be great. –  Jan 05 '11 at 03:43
  • 3
    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. – templatetypedef Jan 05 '11 at 03:43
  • 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. – Avrdan Jan 22 '20 at 15:22
11
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

Timo
  • 5,125
  • 3
  • 23
  • 29
  • 5
    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. – templatetypedef Jan 05 '11 at 03:39
  • @templatetypedef: hmmm, that's funny because the associative containers in MSVC work differently: http://msdn.microsoft.com/en-us/library/z2f3cb7h.aspx I guess it's non-standard then. – Timo Jan 05 '11 at 03:50
  • 1
    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! – templatetypedef Jan 05 '11 at 03:52
  • 1
    It works now in C++11. However, still there are many compilers not ready for C++11. So `mymap.erase(it++)` is more portable. – Tamas Demjen Dec 31 '13 at 01:15
8


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;
        }
    }
roxrook
  • 13,511
  • 40
  • 107
  • 156