Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to use lambda function as hash function in unordered_map?

Tags:

c++

c++11

I wonder if it is possible to use lambda function as custom hash function for unordered_map in C++11? If so, what is the syntax?

like image 399
HanXu Avatar asked Mar 30 '13 13:03

HanXu


People also ask

Which hash function is used in Unordered_map?

The unordered_map::hash_function() is a built in function in C++ STL which is used to get the hash function. This hash function is a unary function which takes a single argument only and returns a unique value of type size_t based on it.

Is Unordered_map a hash map?

Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1).

Is Unordered_map a hash table?

Unordered_map IS a hash table actually. You may want to use a better example as, as is the second insert will fail since it has the same key.

Can pair be used as key in Unordered_map?

Unordered Map does not contain a hash function for a pair like it has for int, string, etc, So if we want to hash a pair then we have to explicitly provide it with a hash function that can hash a pair. unordered_map can takes upto 5 arguments: Key : Type of key values. Value : Type of value to be stored against the key.


1 Answers

#include<unordered_map> #include<string>  int main() {     auto my_hash = [](std::string const& foo) {         return std::hash<std::string>()(foo);     };      std::unordered_map<std::string, int, decltype(my_hash)> my_map(10, my_hash);  } 

You need to pass lambda object to unordered_map constructor, since lambda types are not default constructible.

As @mmocny suggested in comment, it's also possible to define make function to enable type deduction if you really want to get rid of decltype:

#include<unordered_map> #include<string>  template<         class Key,         class T,         class Hash = std::hash<Key>         // skipped EqualTo and Allocator for simplicity > std::unordered_map<Key, T, Hash> make_unordered_map(         typename std::unordered_map<Key, T, Hash>::size_type bucket_count = 10,         const Hash& hash = Hash()) {     return std::unordered_map<Key, T, Hash>(bucket_count, hash); }  int main() {     auto my_map = make_unordered_map<std::string, int>(10,             [](std::string const& foo) {                 return std::hash<std::string>()(foo);             }); } 
like image 152
zch Avatar answered Oct 14 '22 09:10

zch