 # Weird behaviour of unordered_map and map

There is this problem : Link

Sample Input:
5 2
1 5 3 4 2
Sample Output:
3

Solution 1:

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
int main()
{
ll n,k,a,count=0; cin>>n>>k;
map <ll,ll> record;
for(ll i=0;i<n;i++)
{
cin>>a;
record[a]++;
}
for(auto a:record)
{
ll diff=a.fi-k;
if(record[diff]!=0)
count++;
}
cout<<count;
}
``````

Solution 2:

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
int main()
{
ll n,k,a,count=0; cin>>n>>k;
unordered_map <ll,ll> record;
for(ll i=0;i<n;i++)
{
cin>>a;
record[a]++;
}
for(auto a:record)
{
ll diff=a.fi-k;
if(record[diff]!=0)
count++;
}
cout<<count;
}
``````

Problem: Both the solutions are moreover the same the only difference is i have used unordered map in one and map in other but there is difference in the output of the both Solution one gives the output 1 whereas solution 2 gives the output 0.
(I am using Sublime text as editor with C++17)

Why? Can anybody explain?

This can add an element to `record` while you’re iterating over it.

Since the entries will be processed in a different order for `ordered_map` vs `map`, the effect of doing this will be different.

``````       cout << "a.first: " << a.first << " a.second: " << a.second << endl;

``````

in the `for` loop for a clearer picture of what’s going on Edit:

Actually, more than this: inserting an element into an `unordered_map` can trigger a re-hash (and it does on my machine with your example), which according to the docs:

https://en.cppreference.com/w/cpp/container/unordered_map/insert

so the `unordered_map` case exhibits Undefined Behaviour.

6 Likes

Thankyou so much !!

It cleared a lot of my doubts about the behavior of containers.

1 Like