Why is map faster than unordered_map in this situation?

Question

C++ / C#

There is a challenge: https://codeforces.com/contest/1283/problem/D
and 2 solutions
1-e with unordered_map (>2000ms):

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define double long double
#define sqr(x) (x)*(x)
#define pb push_back
#define ams(a) for (auto&c:a) cout<<c<<" ";
#define pf push_front
int32_t main() {
  IOS;
  int n, m;
  cin >> n >> m;
  queue<int>q;
  unordered_map<int, int>len;
  for (int i = 0; i < n; i++) {
    int x; cin >> x; len[x] = 0;
    q.push(x + 1); q.push(x - 1);
  }
  vector<int>ans;
  int sum = 0;
  while (1) {
    if (ans.size() == m) break;
    int cur = q.front(); q.pop();
    if (!len.count(cur)) {
      int r1 = 1e18; int r2 = 1e18;
      if (len.count(cur - 1)) r1 = len[cur - 1];
      if (len.count(cur + 1)) r2 = len[cur + 1];
      if (min(r1, r2) == 1e18) continue;
      sum += min(r1, r2) + 1; len[cur] = min(r1, r2) + 1;
      q.push(cur - 1); q.push(cur + 1); ans.pb(cur);
    }
  }
  cout << sum << "\n";
  ams(ans);
}

2nd with map (607ms):

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define double long double
#define sqr(x) (x)*(x)
#define pb push_back
#define ams(a) for (auto&c:a) cout<<c<<" ";
#define pf push_front
int32_t main() {
  IOS;
  int n, m;
  cin >> n >> m;
  queue<int>q;
  map<int, int>len;
  for (int i = 0; i < n; i++) {
    int x; cin >> x; len[x] = 0;
    q.push(x + 1); q.push(x - 1);
  }
  vector<int>ans;
  int sum = 0;
  while (1) {
    if (ans.size() == m) break;
    int cur = q.front(); q.pop();
    if (!len.count(cur)) {
      int r1 = 1e18; int r2 = 1e18;
      if (len.count(cur - 1)) r1 = len[cur - 1];
      if (len.count(cur + 1)) r2 = len[cur + 1];
      if (min(r1, r2) == 1e18) continue;
      sum += min(r1, r2) + 1; len[cur] = min(r1, r2) + 1;
      q.push(cur - 1); q.push(cur + 1); ans.pb(cur);
    }
  }
  cout << sum << "\n";
  ams(ans);
}

Why is map faster in this situation? (my only option: because of the cache, but I'm not sure)
Thanks for the answers

Answer 1

unordered_map can run for a line in the worst case. This is if there are many collisions. The standard implementation is also wildly slow, works through linked lists and often uses trivial hashes (literally, the int value is taken as the hash value). Finding a deadly test for such a hash is not at all difficult. Enter i*8192 tree coordinates as input to your program - if I understand correctly, unordered_map will take a very long time to work.
You can get rid of such trivial collisions if you implement your own hash function. And then you can even return it. And that will be better. Also, to get rid of constant rehashing, you can add this:(x * 239017l) % (1<<31)

len.reserve(1048576);
len.max_load_factor(0.25);

They say that if you reserve space in advance and specify a smaller load_factor, then unordered_map will be 10 times faster.
Plus, the constant for unorderd_map is higher - because it is necessary to count hashes and rehash the entire table if there are a lot of numbers. Maybe it would be faster for a million numbers, and not 100000, like you have there.