Use struct as key to std::unordered_map in C++
This post will discuss how to use struct as key to std::unordered_map in C++.
To use struct as a key to std::unordered_map, you need to do two things:
1. Define operator== to compare keys in case of a hash collision
In the previous post, we have seen that the ordered associative containers use a strict weak order to identify their keys. That means two keys x and y are considered to be equal if !(x < y) && !(y < x) is true, i.e., neither x is smaller than y, nor y is smaller than x. So less-than operator is used to detect equality and there is no need to define operator==.
On the other hand, std::unordered_map expects you to define the operator== for your class. This is because the fourth template parameter of std::unordered_map requires a comparison function object that returns true if the keys passed as arguments are equal. It defaults to std::equal_to and implementation of std::equal_to delegates the call to operator==.
2. Create specialized hash function for keys of std::unordered_map function
The unordered associative containers are implemented as a hash table. The third template parameter of std::unordered_map is a hashing function object which defaults to std::hash. Since there is no specialization of std::hash for std::pair in the C++ standard library, you have to define our own specialization for std::hash or use boost::hash from Boost.Functional that works with std::pair.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <unordered_map> template<typename T1, typename T2> struct Node { T1 x; T2 y; // constructor Node(T1 x, T2 y) { this->x = x; this->y = y; } // `operator==` is required to compare keys in case of a hash collision bool operator==(const Node &p) const { return x == p.x && y == p.y; } }; // The specialized hash function for `unordered_map` keys struct hash_fn { template <class T1, class T2> std::size_t operator() (const Node<T1, T2> &node) const { std::size_t h1 = std::hash<T1>()(node.x); std::size_t h2 = std::hash<T2>()(node.y); return h1 ^ h2; } }; int main() { std::unordered_map<Node<std::string, std::string>, int, hash_fn> u_map = { {{"C", "C99"}, 1999}, {{"C", "C11"}, 2011}, {{"C++", "C++14"}, 2014}, {{"C++", "C++17"}, 2017}, {{"Java", "Java SE 8"}, 2014}, {{"Java", "Java SE 9"}, 2017} }; for (const auto &entry: u_map) { std::cout << "{" << entry.first.x << "," << entry.first.y << "}: " << entry.second << std::endl; } return 0; } |
Output:
{Java,Java SE 9}: 2017
{Java,Java SE 8}: 2014
{C++,C++17}: 2017
{C++,C++14}: 2014
{C,C11}: 2011
{C,C99}: 1999
Please note that using XOR as a hash combination function can be dangerous. This is because XOR maps identical values to 0, which would end up with far too many collisions in the real world. We should shift/rotate one of the hashes before XORing.
That’s all about using struct as key to std::unordered_map in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)