Map iterator behavior after 'erase'ing

Question

I was writing this code below, and found this strange behavior:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
   map<int, string> map1;
   map1[1] = "Hello";
   map1[2] = "Hello1";
   map1[3] = "Hello2";
   map1[4] = "Hello3";
   map1[5] = "Hello4";

   map<int, string>::iterator it;

   for (it = map1.begin(); it != map1.end(); /*it++*/)
   {
      cout << "Enter: " << (int)(it->first) << endl;
      if (it->first == 3)
         map1.erase(it);
      it++;
      cout << "Exit: " << (int)(it->first) << endl;

   }

   return 0;
}

The output was:

Enter: 1
Exit: 2
Enter: 2
Exit: 3
Enter: 3
Exit: 4
Enter: 4
Exit: 5
Enter: 5
Exit: 4

When I increment the iterator it only in the for loop (check the commented iterator), the output is as follows:

Enter: 1
Exit: 1
Enter: 2
Exit: 2
Enter: 3
Exit: 3
Enter: 4
Exit: 4
Enter: 5
Exit: 5

I am confused as to why in the first case, when I increment the iterator, it again points to the previous map element 4?

score 2 · Answer 1 · edited May 23 '17 at 10:24

2

Both versions are undefined behaviour, the latter just appear to work.

In both cases, you increase an iterator that has been invalidated,
See for example iterator invalidation rules
The latter behaves differently, because the 'enter' and 'exit' are printing the
same iterator

This is solved by the "iterate-erase" idiom, that all STL containers support

// C++11
auto iter = container.begin();
while( iter != container.end() )
{
    if( SomeCondition() )
        iter = container.erase(iter);
    else
        ++iter;
}

This is exactly why erase returns an iterator

Note that associative containers, such as std::map
did not support this prior to C++11

edited May 23 '17 at 10:24

Community

1
1

answered Feb 26 '15 at 07:41

sp2danny

7,488
3
31
53

Thanks for the answer. I think an `iter++` is missing after `iter = container.erase(iter);` statement. In C++98, `std::map.erase()` returns void. So, we can have an alternate approach like: `container.erase(iter++);` Am I right? – Upayan Feb 26 '15 at 10:17
there is nothing missing in the given solution, `erase` returns a valid iterator to the item following the erased one (or end). The alternative approach works for containers where `erase` wont invalidate subsequent iterators, so it will work for `map` but not for `vector` – sp2danny Feb 26 '15 at 11:30

RomanK · Accepted Answer · 2015-02-26T08:42:28.423

1

Dereferencing an iterator to map1.end() produces an undefined result, and this is exactly what you do when running it->first in the cout in the last loop iteration.

In the first variant, you run ++it, reaching map1.end(). Conceptually, map1.end() does not point to any element, and dereferencing it can provide any random outcome (including SEGFAULTs). In your case, it probably points to stale memory containing 4.

In the second variant, you never get to dereference map1.end(), as the loop condition exits once you reach the end of the container. You always print out the same element within the loop.

Note also the answer above - erasing an element invalidates the iterator, so both variants are still invalid.

edited Feb 26 '15 at 08:42

answered Feb 26 '15 at 07:13

RomanK

1,258
7
18

Thanks for the answer. Can you please elaborate a little more? On the other hand, why does it work as expected, when I increment the iterator in the for loop itself? – Upayan Feb 26 '15 at 07:31
On the second question - it works, since you never dereference an 'end()' iterator. Presumably, in the second variant, once you re-enable the increment within the loop, you remove the `++it` from the first version. I'll elaborate the original answer. – RomanK Feb 26 '15 at 08:37

Map iterator behavior after 'erase'ing

2 Answers2