How to remove from a map while iterating it?

Dani picture Dani · Nov 22, 2011 · Viewed 117.7k times · Source

How do I remove from a map while iterating it? like:

std::map<K, V> map;
for(auto i : map)
    if(needs_removing(i))
        // remove it from the map

If I use map.erase it will invalidate the iterators

Answer

Kerrek SB picture Kerrek SB · Nov 22, 2011

The standard associative-container erase idiom:

for (auto it = m.cbegin(); it != m.cend() /* not hoisted */; /* no increment */)
{
  if (must_delete)
  {
    m.erase(it++);    // or "it = m.erase(it)" since C++11
  }
  else
  {
    ++it;
  }
}

Note that we really want an ordinary for loop here, since we are modifying the container itself. The range-based loop should be strictly reserved for situations where we only care about the elements. The syntax for the RBFL makes this clear by not even exposing the container inside the loop body.

Edit. Pre-C++11, you could not erase const-iterators. There you would have to say:

for (std::map<K,V>::iterator it = m.begin(); it != m.end(); ) { /* ... */ }

Erasing an element from a container is not at odds with constness of the element. By analogy, it has always been perfectly legitimate to delete p where p is a pointer-to-constant. Constness does not constrain lifetime; const values in C++ can still stop existing.