20
// erasing from map
#include <iostream>
#include <map>
using namespace std;

int main ()
{
  map<char,int> mymap;
  map<char,int>::iterator it(mymap.begin());

  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;

  it=mymap.find('a');
  mymap.erase (it);                   // erasing by iterator

  // show content:
  for (; it != mymap.end(); it++ )
    cout << (*it).first << " => " << (*it).second << endl;
  return 0;
}

Why does this give an output like 

a => 10
b => 20
c => 30
d => 40
e => 50
f => 60

shouldn't "a => 10" be deleted anyways, but if I declare it = mymap.begin() in the for loop, everything is perfect. why?

program adapted from : http://www.cplusplus.com/reference/stl/map/erase/

moinudin
  • 134,091
  • 45
  • 190
  • 216
0x0
  • 2,915
  • 5
  • 40
  • 67

5 Answers5

48

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.

sth
  • 222,467
  • 53
  • 283
  • 367
  • Similar to: http://stackoverflow.com/questions/1038708/erase-remove-contents-from-the-map-or-any-other-stl-container-while-iterating/1038761#1038761 – karlphillip Jan 12 '11 at 16:02
  • Not working with G++: http://codepad.org/D2lApTLL . Problem is that the `erase()` method was originally in 1998 defined to return `void`. Afaik C++03 changed that, but still not supported by g++. – Notinlist May 15 '12 at 14:03
  • Shouldn't your first code snippet read `mymap.erase(++it)` (pre-increment) instead as a no-no? – OlivierD Jun 06 '12 at 19:45
  • @OlivierD: That would delete not the current element but the following item. And then it would leave the iterator pointing at that deleted item, so it would have the same problem as the code in the question. – sth Jun 06 '12 at 22:34
  • 2
    I'm confused by the sentence. You say "You shouldn't reuse that iterator (_OK_), or advance the iterator to the next element before the deletion takes place (_pre-increment_), for example like this" and then present an example with post-increment which is then repeated as an example of good code. I would expect an example of bad code following that sentence. – OlivierD Jun 07 '12 at 17:32
  • What about just incrementing iterator after erase. I found a bug in my own code where I do 'xxx_map.erase(it)';++it;' and it proved to be working on multiple platforms. So, I am wondering is it actually a bug? – uuu777 Apr 05 '17 at 11:11
  • Seems like the example at cppreference,com is wrong? see: https://en.cppreference.com/w/cpp/container/map/erase – slashmais Jun 11 '18 at 13:44
  • @slashmais: It's different, but not wrong. They don't reuse the (invalid) iterator for the deleted element, instead they use the new (valid) iterator that is returned by `erase()`. `erase()` returns that iterator exactly for this purpose, so it's a good solution. – sth Jun 11 '18 at 17:38
  • thx for responding. I use flag std=c++14 with gcc(v6.3.0): if you look at my last question - now deleted but should be in my history & you do have the rep to access it - I used the 'Since C++11'-type code and the app crashes, but changing to `erase(it++)` worked (that was what prompted the question, but it got shot down poisonously quick). Which way is the current correct way? or do I take pot-luck on what works? – slashmais Jun 12 '18 at 04:26
  • @slashmais I could access it if I had a link, but deleted posts don't show up in profiles. Both the C++11 variant and the "classic" variant of erasing are correct (just in old compilers the C++11 variant wouldn't compile). In your crashing app I can only guess there is some other problem that causes the error, like the iterator already being invalid before the `erase` or the map you are iterating over being deleted/... – sth Jun 12 '18 at 08:56
3

Calling erase() invalidates the iterator. In this case, what's happening is the iterator points to the residual value left behind in memory (but don't rely on this undefined behaviour!). Reset the iterator with it=mymap.begin() before the loop for the desired results.

http://codepad.org/zVFRtoV5

This answer shows how to erase elements while iterating over an std::map:

for(map<T, S*>::iterator it = T2pS.begin(); it != T2pS.end(); T2pS.erase(it++)) {
    // wilhelmtell in the comments is right: no need to check for NULL. 
    // delete of a NULL pointer is a no-op.
    if(it->second != NULL) {
        delete it->second;
            it->second = NULL;
    }
}
Community
  • 1
  • 1
moinudin
  • 134,091
  • 45
  • 190
  • 216
  • So is it not possible to use the iterator inside a for loop and delete elements based on some condition or in other words if I have 1000 elements in a map and I want to delete elements that satisfy a certain user defined condition, then each time I delete an element should I break the loop and start all over again ? – 0x0 Jan 08 '11 at 21:26
  • 2
    @Sunil With `std::map`, the answer unfortunately is yes. Deleting an element restructures the tree to maintain its balance, so you can't even rely on everything to the right of the deleted element being in its original location as with some other std containers such as `std::list`. – moinudin Jan 08 '11 at 21:30
  • 2
    @Sunil See sth's post; if you post-increment the iterator when you call erase, your iterator remains valid. Just make sure that in your for loop, you don't accidentally increment the iterator twice. @marcog That's not exactly correct. While the nodes may be re-balanced, their actual addresses in memory don't change; it's only their left/right/parent pointers (at least for red-black trees). sth's answer works. – Dawson Jan 08 '11 at 21:31
  • @toolbox: Incrementing it twice is the problem, don't you think. because when I do that, the next time in the for loop it checks for a condition and again increments the iterator. This means every time I delete an item I skip an item next to it. – 0x0 Jan 08 '11 at 21:37
  • 2
    @Sunil See [this answer](http://stackoverflow.com/questions/433164/what-happens-to-an-stl-iterator-after-erasing-it-in-vs-unix-linux/433207#433207) for the correct way to iterate through an `std::map` and erase elements at the same time. – moinudin Jan 08 '11 at 21:41
  • @Sunil You have to change the loop for that to work. Make it a while loop where you either 1) erase(it++) or 2) ++it. @marcog I ran your code and got the same output - but what's wrong with it? You erased 'b', then reset the iterator to begin() and got the expected result. As to that thread, it++ avoids that issue by copying it, incrementing the original, then passing the copy to erase. That avoids invalidation. – Dawson Jan 08 '11 at 21:44
1

This has to do with how the map is implemented. Let's say it's a tree of some sort, like:

class map_node {
    char key;
    int  value;
    map_node* next;
    ...
};

When you erase() the iterator, you remove the node from the tree and deallocate its space. But until that memory location is overwritten, the node's contents are still in memory. That's why you can get not only the value, but also the next element in the tree. Thus, your result is completely expected.

chrisaycock
  • 36,470
  • 14
  • 88
  • 125
1

it is no longer valid after mymap.erase(it). This means, it can do whatever it wants.

Oswald
  • 31,254
  • 3
  • 43
  • 68
0

"it" still points at the same location, erase does not update the iterator by itself, you have to do it, by resetting the iterator. In effect, "it" points to the old location which has been erased from the vector but still contains the old data.

Akhil
  • 2,269
  • 6
  • 32
  • 39