UPD: Tricks to make unordered_map faster added.
Hi!
What is unordered_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 527E - Data Center Drama, it seems that it is good to use unordered_map instead of map.
My submission with map: 14269000 Time:484 MS.
My submission with unordered_map: 14269381 Time:358 MS.
Another good sample to show how fast is unordered_map is problem 178C3 - Smart Beaver and Resolving Collisions:
My submission with map: 15781810 Time limit exceeded on test 36 .
My submission with unordered_map: 15774685 Accepted (Time:966 MS).
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 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 int), it will be done. It is pretty easy: x.first^(x.second<<32) is good. but be careful about overflow ;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();
s.reserve(32768); //updated !
s.max_load_factor(0.25); //updated !
for(int i=0;i<1000000;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 it doesn't problem. The only problem is that unordered_map becomes slower(however it is better than map).
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;
}
};
UPD I will explain hash<type> in my next post.
UPD It seems that sometimes unordered_map becames so slow.but it can improve with this two lines of code:
unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);
With this two lines unordered_map become about 10 times faster. You can replace 1024 with another suitable power of two.(it depends on number of insert s you will do).
