Any thing about unordered_map
Difference between en5 and en6, changed 448 character(s)
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 `unsigned 
long 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<1000000
0;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;↵
  }↵
};↵
~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English Arpa 2017-02-24 19:05:47 18 post name updated
en14 English Arpa 2016-02-07 21:16:53 71
en13 English Arpa 2016-02-07 21:11:47 162
en12 English Arpa 2016-02-07 21:09:22 74
en11 English Arpa 2016-02-07 21:06:53 4 Tiny change: '____**UPD:** T' -> '**UPD:** T'
en10 English Arpa 2016-02-07 21:06:17 331
en9 English Arpa 2016-02-07 20:54:44 438
en8 English Arpa 2015-12-03 15:07:16 56 Tiny change: 'n};\n~~~~~' -> 'n};\n~~~~~\n\n**UPD** I will explain `hash<type>` in my next post.'
en7 English Arpa 2015-11-30 22:21:36 2 Tiny change: ' `map`).\n**Note2:' -> ' `map`).\n\n**Note2:'
en6 English Arpa 2015-11-30 22:07:16 448
en5 English Arpa 2015-11-29 22:40:15 820
en4 English Arpa 2015-11-29 19:18:52 4 Tiny change: 'red_map>`.example:\n' -> 'red_map>`.for example:\n'
en3 English Arpa 2015-11-29 18:46:44 337
en2 English Arpa 2015-11-29 17:21:04 349
en1 English Arpa 2015-11-29 15:19:01 2957 Initial revision (published)