Erasing nodes of a std::map within a range-based "for" loop

Question

I need to check data of a std::map, and remove some of them. I'm using a range-based "for" loop, like this:

std::map<int, string> data { { 1, "name1" }, { 2, "name2" }, { 3, "name3" }, };

for( auto&[id, name] : data )
  if( id == 2 )
    data.erase( id );

Is this method correct? Would it crash the loop or result incorrect loop times?

Answer 1

No, this method is not correct. The range-for loop uses iterators internally to drive the loop. If you modify data by erasing an element, this will invalidate existing iterators and lead to undefined behavior. You cannot do it this way.

Your particular example is a bit too trivial -- there's no point in even having a loop, because you can just do data.erase(2); without searching the entire map. That's also more efficient.

Let's go over some options, and abstract your logic for determining whether to erase an element:

bool should_erase(int id, const string& name)
{
    return id == 2;
}

If you do need to erase elements while looping, the documentation for std::map::erase contains an example detailing how that should be done. That would be:

for (auto it = data.begin(); it != data.end(); )
{
    if (should_erase(it->first, it->second)) {
        it = data.erase(it);
    } else {
        ++it;
    }
}

If you're really set on using the range-for, then you'll need to separately store the keys you want to erase and then do that in a second step. The downside is this requires extra storage.

std::deque<int> to_erase;
for (auto& [id, name] : data)
{
    if (should_erase(id, name)) {
        to_erase.push_back(id);
    }
}

for (int id : to_erase)
{
    data.erase(id);
}

Or, you can even build a new map and std::move the data that you wish to keep into it, provided you don't modify the topology of the original map. Again, this needs extra storage and in addition it's not very efficient, and probably the worst of all the ideas I could suggest. But if you expect to erase more values than you keep, it might be appropriate:

std::map<int, string> new_data;
for (auto& [id, name] : data)
{
    if (should_erase(id, name)) {
        new_data.insert(make_pair(id, move(name)));
    }
}
data = move(new_data);

As another user commented, another option is std::erase_if -- that would be the best solution if the only purpose of your loop is to validate stuff. In that case, you could ditch the loop and use erase_if to validate -- it's equivalent to the example using iterators, but a bit cleaner.

erase_if(data,
         [](const auto& item) {
             return should_erase(item.first, item.second);
         });

Answer 2

No, that's not the right way. The pattern you want to learn is:

std::map<int, string> data { { 1, "name1" }, { 2, "name2" }, { 3, "name3" }, };

for(auto it = data.begin(); it != data.end(); )
{
    if( it->first == 2 )
    {
        it = data.erase( it );
    }
    else
    {
        it++;
    }
}
return 0;

Notice the lack of iterator increment in the loop statement. Rather, we update it after deleting, or otherwise, increment it.