Problem with Std::Map::Iterator After Calling Erase()

Problem with std::map::iterator after calling erase()

Erasing an element of a map invalidates iterators pointing to that element (after all that element has been deleted). You shouldn't reuse that iterator.

Since C++11 erase() returns a new iterator pointing to the next element, which can be used to continue iterating:

it = mymap.begin();
while (it != mymap.end()) {
   if (something)
      it = mymap.erase(it);
   else
      it++;
}

Before C++11 you would have to manually advance the iterator to the next element before the deletion takes place, for example like this:

mymap.erase(it++);

This works because the post-increment side-effect of it++ happens before erase() deletes the element. Since this is maybe not immediately obvious, the C++11 variant above should be preferred.

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

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
    }
}

Does C++ map erase elements in loop invalidates iterator? (C++03)

As @sam answered, std::map::erase will invalidate the iterator to the erased element. After that the invalid iterator is used for increment operation in for loop, which is undefined behavior.

References and iterators to the erased elements are invalidated.

To solve it, since C++11 you could use the return value of erase, which is the iterator following the removed element. But for C++03, you have to do that manually. e.g.

class Table
{
public:
  ...    
  void
  Purge ()
  {
    for (Iterator_t it = m_map.begin (); it != m_map.end (); )
      {
        if (it->second.length () <= 4)
          {
            Erase (it++, "Erase entry ");
          }
        else
          {
            ++it;
          }
      }
  }
};

The point of the above code is that the increment is performed before erase happens (while it is still a valid iterator). And we take advantage of the fact that it++ will return the original value of it. Thus the evaluation order would be: (1) it is incremented; (2) the original value of it is passed to erase; (3) the element is erased.

Does inserting/erasing an element from a std::map modify the iteration sequence?

In a std::map the elements will be visited in order.

If you store an iterator that refers to an element that is not deleted, and hence not invalidated, the iterator will still refer to that same element. (If it was the end iterator, it remains the end iterator, as it is not invalidated).

When you advance that iterator, it will advance to the next element in order after the element you refer to.

For your particular example, yes, every element will be visited exactly once, because all deletion of elements was elements that are before the current iterator state of your loop.

If you insert elements ahead of whatever iterator you are using to iterate, then you'll eventually reach them as you iterate forward with your iterator. If you delete elements ahead of whatever iterator you are using to iterate, then they are no longer part of the future elements you'll reach if you iterate with that iterator.

If you insert or delete elements that are before the current location of the iterator, unless you start calling -- or similar functions, your current iteration will continue without noticing that they went away.

This is because ++ on a valid iterator in an ordered container is guaranteed to return the next element in the order, and operations on other iterators that do not invalidate an iterator don't change that iterator's invariants (like what element they refer to).

Does std::map::erase(it++) maintain a valid iterator pointing to the next element in the map?

From the online documentation:

"Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity."

So maybe this:

for(auto it = myMap.begin(); it != myMap.end();)
{
    auto itPrev = it;
    ++it;

    if(shouldBeDeleted(*itPrev))
       myMap.erase(itPrev);
}

Edit: The erase(it++) idea you mention is actually ok, because the increment occurs (and returns a copy of the old, pre-increment value) before erase() is called. It's in effect the equivalent of:

template<typename IteratorT>
IteratorT PostIncrement(IteratorT& it)
{
   auto copy = it;
   ++it;
   return copy;
}

for(auto it = myMap.begin(); it != myMap.end();)
   myMap.erase(PostIncrement(it));

which amounts to the same thing as the other example. Incidentally, this is why you should normally use the prefix ++ with iterators; that copy operation is extra overhead, and you usually don't need it.

What happens with `map::iterator` when i remove entry from map?

In case of std::map iterators and references to the erased elements are invalidated [23.1.2/8]. Your code uses the iterator after it has been invalidated, this results in an Undefined Behavior. In order to avoid this Undefined behavior the iterator needs to be incremented before it gets invalidated in the erase() call.

You need to use:

for(it = m.begin(); it != m.end(); ) {
    if( condition )
        m.erase(it++);
    else
        ++it;
}

Note that here it++ increments it so that it refers to the next element but yields a copy of its original value. Thus, it doesn't refer to the element that is removed when erase() is called.

map .erase doesn't delete the element

If all you want to do is erase the map element whose value is the highest then:

map<string, int> test;

void sort_print()
{
    int biggestNum = 0;
    string word;

    for (auto it = test.begin(); it != test.end(); it++)
    {
        if (it->second > biggestNum)
        {
            word = it->first;
        }
    }
    cout << word + ": " << biggestNum << endl;
    test.erase(word);
}

No need for two loops, and no need for:

biggestNum = it->second;

---

Related Topics