0

I have this 2 codes,

Code 1

#include<bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<int,int>m;

    int nums[]={1,1,3,4,5};

    for(auto x:nums)
    {
        m[x]++;
    }

    for(auto x:m)
    {
        cout<<x.first<<" "<<m[x.first]<<endl;
    }

return 0;

}

Code 2

#include<bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<int,int>m;

    int nums[]={1,1,3,4,5}; int k=2;

    for(auto x:nums)
    {
        m[x]++;
    }

    for(auto x:m)
    {
        cout<<x.first<<" "<<m[x.first+k]<<endl;
    }

return 0;

}

The output of the first code is

5 1
4 1
1 2
3 1

But the output of the second code is

5 0
4 0
5 0
7 0

I am not getting why the output of the 2nd code is like this, shouldn't it be like

5 0  //5 is the index and m[5+2]=0 hence 0
4 0  
1 1  //since m[1+2]=1 
3 1

......................................................................................................................................................................................................................

Turing101
  • 347
  • 3
  • 15
  • 4
    The second code likely has UB because you're modifying the map (potentially invalidating the iterators) while iterating. – Holt Oct 07 '21 at 12:42
  • @mch giving the expected result, and being valid are two different things. The second code will result in undefined behavior in case of rehashing, so showing a compiler version of it that generates the expected result does not help much. – t.niese Oct 07 '21 at 13:09
  • See [Why should I not #include ?](https://stackoverflow.com/q/31816095) and [Why using namespace std is bad practice](https://stackoverflow.com/questions/1452721). – prapin Oct 07 '21 at 18:21

2 Answers2

3

When you do m[x.first + k], you're modifying m when x.first + k is not already in m. According to en.cppreference.com:

If an insertion occurs and results in a rehashing of the container, all iterators are invalidated. [...]

If this occurs, you're invalidating iterators while iterating the map since for (auto x: m) is just a hidden way of iterating using iterators. Thus, your code has undefined behavior (you're using invalidated iterators), hence what you are seeing (and also why other people might see something different).

Holt
  • 36,600
  • 7
  • 92
  • 139
1

operator[], on a map or unordered_map, has the potential to change the container, because (as you're relying on) when you call it with a key which isn't already present, it immediately adds it with a default-constructed value. As such, it's not safe to evaluate m[foo] while looping over m unless you're certain that foo is already present.

I'm not sure what this code is trying to do, but assuming it's just trying to print 0 when the value for the shifted key isn't present, you could do unordered_map::find directly on that shifted key and check whether the returned iterator is valid, and if not, print 0 instead.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • It’s undefined behaviour therefore saying it “won’t crash” is wrong. See other answer. – Mike Vine Oct 07 '21 at 12:51
  • `As such, it's not safe to evaluate m[foo] while looping over m unless you're certain that foo is already present.` I know that this is true for `unordered_map` because there an insert could invalidate all iterates if rehashing occurs. But you also mention `map`, but is it the case there too? – t.niese Oct 07 '21 at 13:02
  • 1
    @t.niese Inserting into a `std::map` (via `insert`, `emplace` or `operator[]`) does not invalidate iterators. – Holt Oct 07 '21 at 14:04
  • @t.niese For `map` there's no UB, but you're likely to end up skipping later elements or revisiting earlier elements. – Sneftel Oct 07 '21 at 14:39