Removing elements from a C++ map through a for-loop

Question

My STL is a bit rusty, so forgive me for asking a possibly trivial question. Consider the following piece of code:

map<int,int> m;
...
for (auto itr = m.begin(); itr != m.end(); ++itr) {
    if (itr->second == 0) {
        m.erase(itr);
    }
}

The question is: Is it safe to erase elements while looping over the map?

Solution 1

I think that you shouldn't use removed iterator at all - in case of lists this causes serious problems, shouldn't be different for maps.

EDIT by Matthieu M: this code is well-formed in C++0x and allowed as an extension by MSVC.

map<int,int> m;
...
auto itr = m.begin();
while (itr != m.end())
{
    if (itr->second == 0) {
        itr = m.erase(itr);
    }
    else 
    {
        itr++;
    }
}

Solution 2

Yes, but not the way you do it. You're invalidating itr when you erase, then incrementing the invalid iterator.

auto itr = m.begin();
while (itr != m.end()) {
  if (itr->first == 0) {
    m.erase(itr++);
  } else {
    ++itr;
  }
}

Solution 3

For the example given, It would actually be easier to use the erase overload that takes a key as an argument. This function erases all elements in the map with the given key (for a map, this is always either zero or one element)

map<int,int> m; 
// ...
m.erase(0); // erase all elements with key equivalent to 0

Comments

[Jagannath]

auto tmp = ++itr; m.erase(iter); itr = tmp; // This would be more understable ( IMO ).

[Erik]

It'd also be wrong, you're incrementing before you erase... Did you perhaps intend e.g. auto tmp=itr; ++itr; m.erase(tmp); ?

[Erik]

Standard c++ map::erase does not return a new iterator, that's a MSVC extension.

[decltype]

This code is ill-formed. There is no version of the erase function that returns an iterator. The Visual C++ standard library implementation provides such a return type, but specifically notes that it doesn't conform to the C++ Standard

[Matthieu M.]

@Ben, @Erik: A warning, there are two kinds of erase methods in the standard, for node-based containers (list, map, set, ...) use this method, for containers whose erase method returns an iterator (like vector), the erase line should read itr = m.erase(itr). This signature quirk effectively throw a damp on the whole "interchangeability" thing... and so is corrected in C++0x so that all erase that did not return anything now return an iterator to the next element :)

[Matthieu M.]

@Xader: I've reverted your edit and added a disclaimer, this code is well-formed in C++0x and is the canonical way of removing elements in a container, so the best answer given. (The disclaimer is so that people who don't understand that auto means C++0x don't get confused). Standard reference for the nay-sayers: n3225 23.5.1.2 element access.

[decltype]

@Matthieu: I agree. Since the OP wrote "C++" in his question, I assumed that auto was simply being used in the sense "this type is painfully long to write out in C++03, so I'll borrow the C++0x type specifier auto, but the example should otherwise be considered C++03," or some such ;)

[dlanod]

For my own understanding since I use this pattern quite often, can you confirm that this means the m.erase(itr++); line can become itr = m.erase(itr++); for all containers in C++0x?

[Petter]

Thanks, I am using C++0x (as the auto keyword and the c++0x tag suggests) so looks like a good solution.

[rubenvb]

@dlanod lose the ++: itr = m.erase(itr); is what it should be, see e.g. en.cppreference.com/w/cpp/container/map/erase