Hi!↵
↵
##### What is `unordred_map`?↵
↵
It is a data structure like `map` but it is more than 4 times faster than `map`.you can use it in C++11 with including `#include<unordered_map>`.for example:↵
↵
~~~~~↵
#include<unordered_map>↵
using namespace std;↵
int main(){↵
unordered_map<int,int>mp;↵
mp[5]=12;↵
mp[4]=14;↵
cout<<mp[5]<<' '<<mp[4]<<endl;//prints: 12 14↵
}↵
~~~~~↵
↵
Lets explain it more.↵
↵
##### How it works?↵
↵
Focus on `unordered_set` for simplify.You can imagine that it has vector of vector like `vector<vector<type> > mp`. Every time you insert value `V` in that, it calculate its `hash`(I will explain how it works), let `hash(V)=K`; it inserts `V` into `mp[K]` (formally it calls `mp[K].push_back(V)`).When you call `mp.count(V)` it searchs for `V` in `mp[K]`.↵
↵
##### `map` VS `unordered_map` (and `set` VS `unordered_set`)↵
↵
**1-`unordered_map` is more than 4 times faster**↵
↵
Focus on problem [problem:527E], it seems that it is good to use `unordered_map` instead of `map`.↵
↵
My submission with `map`: [submission:14269000] Time:484 MS.↵
↵
My submission with `unordered_map`: [submission:14269381] Time:358 MS.↵
↵
It seems that there isn't big gap between them, but in fact we know that `unordered map` is more that 4 times faster than `map`, I will explain it more later.↵
↵
**2-`unordered_set` (and `unordered_map`) is not sorted**↵
↵
Please note that `set` (and `map`) is sorted, for example *(s.begin()) is always smallest number in the set; but in `unordered_set` it isn't. similarly there isn't `lower_bound` and `upper_bound` in `unordered_set` (and `unordered_map` similarly).↵
↵
##### Creating hash function for structs↵
↵
Now, **one other problem** remains, you can try to compile this code:↵
↵
~~~~~↵
unordered_map<pair<int,int>,int>mp;↵
~~~~~↵
↵
You will get Compilation Error! Why? See [this page](http://www.cplusplus.com/reference/functional/hash) for `unordered_map` supported types. For unsupported types, you have to create your own hash function for use. For example lets see how we can create a hash function for `pair<int,int>`.↵
↵
As you know any `int` value is between -2^31+1 to 2^31-1.so if we create function that for every `pair<int,int>` returns distinct value in type `size_t`(alias of `unsignedlong long int`), it will be done. It is pretty easy: `x.first^(x.second<<32)` is good. but be careful about BUG(OVERFLOW) (It's different from my friend [user:bug-overflow,2015-11-29] :D ). ;for having good hash function we use `hash<long long>`.The code is looks like this:↵
↵
~~~~~↵
struct HASH{↵
size_t operator()(const pair<int,int>&x)const{↵
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));↵
}↵
};↵
unordered_map<pair<int,int>,int,HASH>mp;↵
~~~~~↵
↵
Now you have a `unordered_map` of `pair<int,int>` (it isn't problem what is second member, in example it was `int`).Creating hash function for other structs is same.↵
↵
##### How to test `unordered_map` is faster than `map`?↵
↵
You can test that for N=10^6, `unordered_set`(`unordered_map`) is more than 4 times faster than `set`(`map`) ;with this code:(compile code with command: g++ file.cpp -std=c++11 **-O2**)↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
unordered_set<int>s;//replace it with set for test.↵
int main(){↵
auto T=clock();↵
for(int i=0;i<10000000;i++)↵
s.insert(i);↵
cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';↵
}↵
~~~~~↵
↵
**Note1:** Let your hash function `H(V)`, it is better that H(V) returns distinct value for every distinct `V`, it makes `unordered_map` faster; but if you can't do that(like when you have `pair<long long int,long long int>` as type) **it doesn't problem**. The only problem is that `unordered_map` becomes slower(however it is better than `map`).Here is example hash function for pair<long long int,long long int>:↵
↵
~~~~~↵
struct HASH{↵
size_t operator()(const pair<long long int,long long int>&x)const{↵
return x.first+x.second;↵
}↵
};↵
unordered_map<pair<long long int,long long int>,int,HASH>mp;↵
~~~~~↵
↵
↵
**Note2:** Please be careful about your hash function time complexly! it is fun to use this hash function(WARNING: don't use it!):↵
↵
~~~~~↵
struct HASH{↵
size_t operator()(const pair<int,int>&x)const{↵
size_t ans=0;↵
for(int i=0;i<x.first;i++)↵
ans+=x.second;↵
return ans;↵
}↵
};↵
~~~~~
↵
##### What is `unordred_map`?↵
↵
It is a data structure like `map` but it is more than 4 times faster than `map`.you can use it in C++11 with including `#include<unordered_map>`.for example:↵
↵
~~~~~↵
#include<unordered_map>↵
using namespace std;↵
int main(){↵
unordered_map<int,int>mp;↵
mp[5]=12;↵
mp[4]=14;↵
cout<<mp[5]<<' '<<mp[4]<<endl;//prints: 12 14↵
}↵
~~~~~↵
↵
Lets explain it more.↵
↵
##### How it works?↵
↵
Focus on `unordered_set` for simplify.You can imagine that it has vector of vector like `vector<vector<type> > mp`. Every time you insert value `V` in that, it calculate its `hash`(I will explain how it works), let `hash(V)=K`; it inserts `V` into `mp[K]` (formally it calls `mp[K].push_back(V)`).When you call `mp.count(V)` it searchs for `V` in `mp[K]`.↵
↵
##### `map` VS `unordered_map` (and `set` VS `unordered_set`)↵
↵
**1-`unordered_map` is more than 4 times faster**↵
↵
Focus on problem [problem:527E], it seems that it is good to use `unordered_map` instead of `map`.↵
↵
My submission with `map`: [submission:14269000] Time:484 MS.↵
↵
My submission with `unordered_map`: [submission:14269381] Time:358 MS.↵
↵
It seems that there isn't big gap between them, but in fact we know that `unordered map` is more that 4 times faster than `map`, I will explain it more later.↵
↵
**2-`unordered_set` (and `unordered_map`) is not sorted**↵
↵
Please note that `set` (and `map`) is sorted, for example *(s.begin()) is always smallest number in the set; but in `unordered_set` it isn't. similarly there isn't `lower_bound` and `upper_bound` in `unordered_set` (and `unordered_map` similarly).↵
↵
##### Creating hash function for structs↵
↵
Now, **one other problem** remains, you can try to compile this code:↵
↵
~~~~~↵
unordered_map<pair<int,int>,int>mp;↵
~~~~~↵
↵
You will get Compilation Error! Why? See [this page](http://www.cplusplus.com/reference/functional/hash) for `unordered_map` supported types. For unsupported types, you have to create your own hash function for use. For example lets see how we can create a hash function for `pair<int,int>`.↵
↵
As you know any `int` value is between -2^31+1 to 2^31-1.so if we create function that for every `pair<int,int>` returns distinct value in type `size_t`(alias of `unsigned
↵
~~~~~↵
struct HASH{↵
size_t operator()(const pair<int,int>&x)const{↵
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));↵
}↵
};↵
unordered_map<pair<int,int>,int,HASH>mp;↵
~~~~~↵
↵
Now you have a `unordered_map` of `pair<int,int>` (it isn't problem what is second member, in example it was `int`).Creating hash function for other structs is same.↵
↵
##### How to test `unordered_map` is faster than `map`?↵
↵
You can test that for N=10^6, `unordered_set`(`unordered_map`) is more than 4 times faster than `set`(`map`) ;with this code:(compile code with command: g++ file.cpp -std=c++11 **-O2**)↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
unordered_set<int>s;//replace it with set for test.↵
int main(){↵
auto T=clock();↵
for(int i=0;i<10000000;i++)↵
s.insert(i);↵
cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';↵
}↵
~~~~~↵
↵
**Note1:** Let your hash function `H(V)`, it is better that H(V) returns distinct value for every distinct `V`, it makes `unordered_map` faster; but if you can't do that
↵
~~~~~↵
struct HASH{↵
size_t operator()(const pair<long long int,long long int>&x)const{↵
return x.first+x.second;↵
}↵
};↵
unordered_map<pair<long long int,long long int>,int,HASH>mp;↵
~~~~~↵
↵
**Note2:** Please be careful about your hash function time complexly! it is fun to use this hash function
↵
~~~~~↵
struct HASH{↵
size_t operator()(const pair<int,int>&x)const{↵
size_t ans=0;↵
for(int i=0;i<x.first;i++)↵
ans+=x.second;↵
return ans;↵
}↵
};↵
~~~~~
