CODEWITHSUNDEEP
c++hashmapunordered-map
Franky Yeung
Franky Yeung

Reputation: 29

c++ unordered_map iterator stop after erasing element within

I am trying to make a function to calculate polynomial derivative with the polynomial storing in a hashmap, but i am not sure why the iterator stop while i am erasing element through the iteration. The code are as follow, the iterator will stop if map.erase(i.first); put in place

the hash key contains the exponent degree, the bucket contains the assoicated coefficient. The input polynomial is 3x^6 + 4x^4 + 6x^2 + 2

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map <int,int> derivative (unordered_map<int, int>& map) {
unordered_map <int, int> answer;
    map.erase(0);   // drop the constant in the polynomial

    for (auto i: map) {
        answer [i.first-1] = i.first * i.second;    //take the derivative
       // map.erase(i.first);     // erase the element after taking the derivative

    }
    return answer;
}

int main() {
    unordered_map <int,int> map = {{6,3},{4,4},{2,6},{0,2}};

    unordered_map<int,int> result = derivative(map);

    for (auto i: result)
        cout << i.second << "X^" << i.first << endl;

    return 0;
}

Upvotes: 0

Views: 1381

Answers (2)

wally
wally

Reputation: 11002

The following

for(auto i : map) {
    answer[i.first - 1] = i.first * i.second;    //take the derivative
    map.erase(i.first);     // erase the element after taking the derivative
}

is iterating over the elements. If you erase one of the elements with map.erase(i.first); while iterating then you get undefined behavior.

If you are using a c++14 compliant compiler you could explicitly use the iterator and update it with erase's return value. That way elements can be erased while iterating through the container.

So you could do:

for (auto it = map.begin(); it != map.end; ) {
    answer[it->first-1] = it->first * it->second;    //take the derivative
    it = map.erase(it);
}

Upvotes: 2

Slava
Slava

Reputation: 44238

You cannot erase current element from std::map or std::unordered_map while iterating with range loop, use iterators instead:

for( auto it = map.begin(); it != map.end(); ) {
     if( condition ) map.erase( it++ );
     else ++it;
}

in your particular case it could be simplified to:

for (auto it = map.begin(); it != map.end; ) {
    answer[it->first-1] = it->first * it->second;    //take the derivative
    map.erase(it++);
}

Upvotes: 4

Related Questions