how are map iterators invalidated when erasing elements?

Question

when and how are iterators invalidated in a map when using the erase method ?

for example :

std :: map < int , int > aMap ;

aMap [ 33 ] = 1 ;
aMap [ 42 ] = 10000 ;
aMap [ 69 ] = 100 ;
aMap [ 666 ] = -1 ;

std :: map < int , int > :: iterator itEnd = aMap.lower_bound ( 50 ) ;

for ( std :: map < int , int > :: iterator it = aMap.begin ( ) ;
      it != itEnd ;
      // no-op
    )
{
   aMap.erase ( it ++ ) ;
}

the erased iterator will surely become invalid (it's incremented while still valid) but what about the others?

if I'm not wrong the standard says that a map has to be a balanced binary tree or a structure with equivalent key-search complexity

in case the map is implemented with a tree, can I assume that not erased iterators remain valid ?

what about other possible ways to implement a map ?

score 8 · Accepted Answer · edited May 23 '17 at 12:34

8

Only the erased iterator is invalid, the rest are guaranteed by the standard to remain valid.

See Iterator invalidation rules

edited May 23 '17 at 12:34

Community

1
1

answered Sep 08 '11 at 14:55

Mark Ransom

299,747
42
398
622

Tony The Lion · Answer 2 · 2011-09-08T15:19:10.570

1

If the map were to be implemented as a balanced tree, after doing erase, the tree might need to be rebalanced, that means that the positions an iterator was pointing to, could now have something else or nothing there, depending on the rebalancing of the tree, so that's why that iterator is invalidated when you remove an element from the map, having erased the element, the iterator now ends up pointing at some memory that is no longer valid, which is Undefined Behaviour.

What if you decide to remove all elements from the map, inside your loop, what are the iterators gonna end pointing at?

edited Sep 08 '11 at 15:19

answered Sep 08 '11 at 14:47

Tony The Lion

61,704
67
242
415

3

`map::erase` only invalidates the iterator that was passed as its argument. All other iterators are guaranteed to remain valid. – Mankarse Sep 08 '11 at 14:54
2

The tree is rebalanced by modifying internal pointers to the nodes; the values themselves don't move, and references and iterators to them remain valid. – Mike Seymour Sep 08 '11 at 14:59
@Mankarse: I amended my answer somewhat, to fit with what you said – Tony The Lion Sep 08 '11 at 15:03
OK (comments deleted) - but you're still saying that the iterator is invalidated because the tree might be rebalanced. That's not the case - it's invalidated because it refers to something that no longer exists. – Mike Seymour Sep 08 '11 at 15:22

how are map iterators invalidated when erasing elements?

2 Answers2

Linked