What happens if you call erase() on a map element while iterating from begin to end?

Question

In the following code I loop through a map and test if an element needs to be erased. Is it safe to erase the element and keep iterating or do I need to collect the keys in another container and do a second loop to call the erase()?

map<string, SerialdMsg::SerialFunction_t>::iterator pm_it;
for (pm_it = port_map.begin(); pm_it != port_map.end(); pm_it++)
{
    if (pm_it->second == delete_this_id) {
        port_map.erase(pm_it->first);
    }
}

UPDATE: Of course, I then read this question which I didn't think would be related but answers my question.

Please note in question that `std::remove_if` does not work with `std:map` — socketpair, Nov 04 '15 at 13:16

score 190 · Accepted Answer · edited May 23 '17 at 11:54

190

C++11

This has been fixed in C++11 (or erase has been improved/made consistent across all container types).
The erase method now returns the next iterator.

auto pm_it = port_map.begin();
while(pm_it != port_map.end())
{
    if (pm_it->second == delete_this_id)
    {
        pm_it = port_map.erase(pm_it);
    }
    else
    {
        ++pm_it;
    }
}

C++03

Erasing elements in a map does not invalidate any iterators.
(apart from iterators on the element that was deleted)

Actually inserting or deleting does not invalidate any of the iterators:

Also see this answer:
Mark Ransom Technique

But you do need to update your code:
In your code you increment pm_it after calling erase. At this point it is too late and is already invalidated.

map<string, SerialdMsg::SerialFunction_t>::iterator pm_it = port_map.begin();
while(pm_it != port_map.end())
{
    if (pm_it->second == delete_this_id)
    {
        port_map.erase(pm_it++);  // Use iterator.
                                  // Note the post increment.
                                  // Increments the iterator but returns the
                                  // original value for use by erase 
    }
    else
    {
        ++pm_it;           // Can use pre-increment in this case
                           // To make sure you have the efficient version
    }
}

edited May 23 '17 at 11:54

Community

1
1

answered Nov 05 '08 at 00:09

Martin York

257,169
86
333
562

Is the order of evaluation of the increment in the postfix expression `pm_it++` guaranteed to be executed before the function is entered? – David Rodríguez - dribeas Mar 03 '11 at 20:56
4

@David Rodríguez - dribeas: Yes. The standard guarantees that all argument expressions will be fully evaluated before the function is called. It is the result of the post increment that is passed to the erase function(). So yes the post increment of pm_it will be done before erase() is called. – Martin York Mar 03 '11 at 21:19
NOTE: Almost line for line matches the associative container example in Scott Meyer's "Effective STL" Item 9. – Ogre Psalm33 May 09 '12 at 15:33
for (auto pm_t = port_map.begin(); pm_it != port_map.end(); ) { ... } – Andrii Syrokomskyi Sep 25 '13 at 09:42
Not positive about this, but it seems like this will fail if `delete_this_id` refers to the last element. Would it not be better to use `pm_it = port_map.erase(pm_it)`? – iboisver Aug 28 '14 at 23:43
@iboisver: `delete_this_id` is an `id` not an iterator. The loop is not entered for the `end()` iterator so that does not apply. If you mean `delete_this_id` refers to the last valid element in the map. Then it will still work. `pm_it++` is called before the `erase()` is called. Incrementing the iterator from the last element to `end()` is perfectly valid. The result of the `operator++()` returns the original value (before the increment) and thus is a valid value to be passed to `erase()`. – Martin York Aug 28 '14 at 23:47
@LokiAstari: you are right, the code is fine for a `map`. My testing indicates it will fail if the last element is erased and if the container is a `vector` because a side effect of `erase` is that the value returned by `end()` changes. Incrementing the iterator in `erase(...)`, as opposed to using `pm_it = port_map.erase(pm_it)` causes the iterator to be invalid. Sorry for the confusion. – iboisver Aug 29 '14 at 17:30
4

@iboisver: On the vector. The use of erase() invalidates all iterators of the array after the erase point (not just the end), this is a property of `Sequence` containers. The special property of `Associative` containers is that iterators are not invalidated by erase or insert (unless they point at element that was erased). Vector and erase usign iterators is covered in detail in the appropriate question http://stackoverflow.com/a/3938847/14065 – Martin York Aug 29 '14 at 17:35
If you are using C++11 then you can use `pm_it = port_map.erase(pm_it);` as this ensures that pm_it becomes the next valid iterator or port_map::end if the last element is erased. But in the code above by @LokiAstari once you perform `port_map.erase(pm_it)` pm_it becomes a invalid pointer and the operations thereafter may cause the program to terminate. – sabertooth1990 Dec 08 '14 at 23:43
@sabertooth1990: That is why there is no: `port_map.erase(pm_it)` in the above code. We have do the extra: `port_map.erase(pm_it++)` to make it work. – Martin York Dec 08 '14 at 23:48

score 12 · Answer 2 · answered May 05 '09 at 14:13

Here's how I do that ...

typedef map<string, string>   StringsMap;
typedef StringsMap::iterator  StrinsMapIterator;

StringsMap m_TheMap; // Your map, fill it up with data    

bool IsTheOneToDelete(string str)
{
     return true; // Add your deletion criteria logic here
}

void SelectiveDelete()
{
     StringsMapIter itBegin = m_TheMap.begin();
     StringsMapIter itEnd   = m_TheMap.end();
     StringsMapIter itTemp;

     while (itBegin != itEnd)
     {
          if (IsTheOneToDelete(itBegin->second)) // Criteria checking here
          {
               itTemp = itBegin;          // Keep a reference to the iter
               ++itBegin;                 // Advance in the map
               m_TheMap.erase(itTemp);    // Erase it !!!
          }
          else
               ++itBegin;                 // Just move on ...
     }
}

If you delete the end of the vector as well (itEnd), then the last check (the while condition) will be against an invalidated iterator (itEnd). Not good. — Agostino, Feb 28 '15 at 23:03

score 1 · Answer 3 · answered Nov 05 '08 at 00:18

This is how I would do it, approximately:

bool is_remove( pair<string, SerialdMsg::SerialFunction_t> val )
{
    return val.second == delete_this_id;
}

map<string, SerialdMsg::SerialFunction_t>::iterator new_end = 
    remove_if (port_map.begin( ), port_map.end( ), is_remove );

port_map.erase (new_end, port_map.end( ) );

There is something odd about

val.second == delete_this_id

but I just copied it from your example code.

What happens if you call erase() on a map element while iterating from begin to end?

3 Answers3

C++11

C++03

Linked

Related