CODEWITHSUNDEEP
c++stliteratorstdmap
Pratap Singh
Pratap Singh

Reputation: 55

Erasing while traversing in C++ stl map giving runtime error

Following lines of C++ code gives runtime error but if erase operation mymap.erase(v) is removed it works:

map<int,int> mymap = {{1,0},{2,1},{9,2},{10,3},{11,4}};
for(auto it=mymap.rbegin();it!=mymap.rend();){
    int v=it->first;
    ++it;
    mymap.erase(v);
}

demo

Here iterator it is changed before deleting its value v, so iterator it should remain unaffected I believe.

Upvotes: 5

Views: 397

Answers (2)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122595

Indeed, std::map::erase:

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

But std::reverse_iterator

For a reverse iterator r constructed from an iterator i, the relationship &*r == &*(i-1) is always true (as long as r is dereferenceable); thus a reverse iterator constructed from a one-past-the-end iterator dereferences to the last element in a sequence.

Perhaps it gets more clear when you look at the image on the cppreference page.

image

The crucial part is "Reverse iterator stores an iterator to the next element than the one it actually refers to".

As a consequence (small modification to your code)

auto& element = *it;       // fails in the next iteration, because...
int v = element.first;
++it;                      // now it stores an iterator to element
mymap.erase(v);            // iterators to element are invalidated

You are erasing the element that is used by it in the next iteration.

Upvotes: 5

Remy Lebeau
Remy Lebeau

Reputation: 596673

When you are calling erase(v), you are invalidating the base iterator that the next reverse_iterator (from ++it) is using. So you need to create a new reverse_iterator from the base iterator that precedes the erased value.

Also, rather than erasing the value that the reverse_iterator is referring to, you should erase the base iterator instead, since you already know which element you want to erase. There is no need to make the map go hunting for the value again.

This works for me:

map<int,int> mymap = {{1,0},{2,1},{9,2},{10,3},{11,4}};
for(auto it = mymap.rbegin(); it != mymap.rend(); ){
    auto v = --(it.base());
    v = mymap.erase(v);
    it = map<int,int>::reverse_iterator(v);
}

Demo

On the other hand, this loop is essentially just erase()'ing all elements from mymap, so a better option is to use mymap.clear() instead.

Upvotes: 10

Related Questions