C++ Map iterator stucks in infinite for loop

Question

I am iterating a map in C++ using a for loop but it is stucking in an infinite loop. I have searched for other similar questions and the closest one is this question, but answer to that question doesn't answer my query because in that question the author is making changes to the map object but I am not making any changes to the map object during the for loop.

My code is follows (I tried commenting different lines and figured out that infinite loop is caused by 11th line (else statement) but I couldn't figure out the exact problem ):

int main(){
    map<int,int> dic; //dic is the relevant map object
    dic[0]=1; dic[1]=1; dic[2]=1; dic[3]=1; //dic = {0:1, 1:1, 2:1, 3:1}

    int k=1;
    int sol=0;

    for(map<int,int>::iterator iter=dic.begin(); iter!=dic.end(); iter++){
        int a=iter->first; int b=iter->second;
        if(k==0) sol+=b*(b-1)/2;
        else sol+=b*dic[a+k]; //after some trials, I found that problem is in this line but I couldn't figure out the problem
    }
    return sol;
}

[Prefer](https://stackoverflow.com/questions/1303899/performance-difference-between-iterator-and-iterator) `++iter` to `iter++`. — Evg, Apr 22 '20 at 13:33
It won't affect the correctness of the code, that's why it's just a comment. — Evg, Apr 22 '20 at 13:35
Okay. what's the reason for preferring `++iter` over `iter++`? — ATK, Apr 22 '20 at 13:36
I think a little `cout << a << endl;` would have gone a long way towards solving the mystery. — molbdnilo, Apr 22 '20 at 13:44
I used `cout` and it was printing all added values in each loop with pair value of 0 but I didn't know that C++ would automatically add those keys. I was expecting an error in that case (python gives error in that case) :) — ATK, Apr 22 '20 at 13:47
When the behaviour is surprising, [look up](https://en.cppreference.com/w/cpp/container/map/operator_at) what it's supposed to do and compare that to your assumptions. In this case, among the first things you see is "[...] performing an insertion if such key does not already exist." — molbdnilo, Apr 22 '20 at 13:50

cigien · Accepted Answer · 2020-04-22T13:48:27.777

6

This line:

sol+=b*dic[a+k];

does add a new element to the map if the key a+k doesn't exist.

a here is a key, so dic[a] would work fine. However, when k is not 0, you run the risk of accessing an element of the map that doesn't exist.

Use map::find if you want to check whether a particular key exists.

Also, your observation that this code results in an infinite loop, is valid, but technically incorrect. There are only a finite number of values that the key type can have, so eventually the loop will terminate. It might take quite a while though. This assumes that you are only ever using keys that don't overflow an int.

edited Apr 22 '20 at 13:48

answered Apr 22 '20 at 13:32

cigien

57,834
11
73
112

`a` is the key, but the same applies: at some point `a+k == 3 + 1 == 4` so `dic[4]` will be created, iteration continues, `dic[5]` will be created, and so on and on. – Roel Schroeven Apr 22 '20 at 13:36
@RoelSchroeven That's right, I missed that bit, thanks. – cigien Apr 22 '20 at 13:38
It should be clarified that the for loop won't result in an infinite loop since `a+k` can take a maximum of `2^32-1` unique values. – srt1104 Apr 22 '20 at 13:46
@lucieon Wouldn't it be `2^32`? Eventually the key will overflow, but this code isn't going to stop because of that. It will continue until the computed key wraps around and works its way back up to 0. – cdhowie Apr 22 '20 at 13:47
@cdhowie you're right, it's `2^32`. I was thinking of the maximum value it can take while making that comment. But how will it overflow? Whatever be the result of `a+k`, it'll be one of those `2^32` values. And since it's there is a limit to it, `iter` will finally reach `dic.end()`. – srt1104 Apr 22 '20 at 13:59
@lucieon Right, not claiming that it will loop forever. However, I believe it's not actually `2^32` iterations either, since `std::map` is ordered. I think the loop will run a maximum of `2^31-1` times (note the exponent is different than in your comment) because once iteration reaches the maximum key, iteration will stop there since we're iterating an ordered set. (While a negative key will get added during that iteration, we won't advance to it.) – cdhowie Apr 22 '20 at 16:02

C++ Map iterator stucks in infinite for loop

1 Answers1