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?

Thanks in advance !

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.

Add:

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

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

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