iterator invalidation in map C++

Question

I have a sample program in which I am trying to see how the iterator invalidates while deleting the elements from a map.

The program is here:

#include <iostream>
#include <map>

using namespace std;

int main(int argc, char *argv[])
{

    map<int, int> myMap;

    myMap.insert(pair<int, int>(0, 2));    
    myMap.insert(pair<int, int>(1, 4));    
    myMap.insert(pair<int, int>(3, 18));    
    myMap.insert(pair<int, int>(2, 20));    

    map<int, int>::iterator it; 

    for(it = myMap.begin(); it != myMap.end(); ++it) 
    {   
        myMap.erase(it);  // erasing the element pointed at by iterator

        cout << it->first << endl; // iterator is invalid here 
    }   
    return 0;
}

The problem is that I am getting output is:

Why the iterator is not invalidating and giving me wrong results. Any help would be highly appreciated.

Documentation of C++ STL maps says that: References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

you're asking why using an invalidated iterator sometimes works? That's a bit like asking why when people jump without a parachute sometimes they survive — UKMonkey, Apr 18 '18 at 09:04
Your iterator is invalidated. You are observing effects of undefined behavior. — Ron, Apr 18 '18 at 09:05
Dereferencing invalid iterator is Undefined Behaviour. It can do everything, including returning (seemingly) correct value. — Yksisarvinen, Apr 18 '18 at 09:05

score 4 · Accepted Answer · answered Apr 18 '18 at 09:13

Using an invalidated iterator is undefined behaviour. In such case, anything could happen.

Why do you see the values? The iterator contains a pointer to some piece of memory, by pure accident, this memory has not yet been returned to the system and has not yet been overwritten. This is why you still can see the already "dead" values.

It does not change anything, it remains undefined behaviour, and the next time you run the program, the memory page the map element resided in could already have been returned to the OS again and you get an access violation (segmentation fault)...

score 2 · Answer 2 · answered Apr 18 '18 at 09:10

Invalidated iterator does not mean that its internal data was erased. Sometimes like in this case the invalidated iterator may hold a valid reference to the next item. However, using it like this is Undefined Behavior and it likely to cause some problems in your application.

score 2 · Answer 3 · answered Apr 18 '18 at 09:10

2

There are no run-time checks for invalid iterators by default.

You can enable the debug checks for invalid iterators with -D_GLIBCXX_DEBUG for GNU C++ standard library. That produces the following run-time error:

iterator "this" @ 0x0x7fff9f3d7060 {
type = N11__gnu_debug14_Safe_iteratorISt17_Rb_tree_iteratorISt4pairIKiiEENSt7__debug3mapIiiSt4lessIiESaIS4_EEEEE (mutable iterator);
  state = singular;
  references sequence with type `NSt7__debug3mapIiiSt4lessIiESaISt4pairIKiiEEEE' @ 0x0x7fff9f3d7150
}

For other standard libraries check the documentation.

answered Apr 18 '18 at 09:10

Maxim Egorushkin

131,725
17
180
271

Note that this is working within the bounds of UB: the standard says "anything can happen" and the implementation then says "throwing an exception conforms to anything" – Caleth Apr 18 '18 at 09:58
@Caleth Following this logic to extreme, it can print this message even without debug iterators, bit it happens so rarely, that it has not been observed yet. To be pedantic, the standard does not require any particular behaviour when UB happens, which is rather different from "anything can happen". – Maxim Egorushkin Apr 18 '18 at 11:53
1

"does not **require** any particular behaviour" yes, but also "does not **forbid** any particular behaviour". In other words "anything can happen" – Caleth Apr 18 '18 at 11:55

iterator invalidation in map C++

3 Answers3

Linked