C++ unordered_map using a custom class type as the key

Question

I am trying to use a custom class as key for an unordered_map, like the following:

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector<int> v) {
        sort(v.begin(), v.end());
        a = v[0];       
        b = v[1];       
        c = v[2];       
    }

    bool operator==(Node i) {
        if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    unordered_map<Node, int> m;    

    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(9);
    Node n(v);

    m[n] = 0;

    return 0;
}

However, g++ gives me the following error:

In file included from /usr/include/c++/4.6/string:50:0,
                 from /usr/include/c++/4.6/bits/locale_classes.h:42,
                 from /usr/include/c++/4.6/bits/ios_base.h:43,
                 from /usr/include/c++/4.6/ios:43,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from 3sum.cpp:4:
/usr/include/c++/4.6/bits/stl_function.h: In member function ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]’:
/usr/include/c++/4.6/bits/hashtable_policy.h:768:48:   instantiated from ‘bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type, std::__detail::_Hash_node<_Value, false>*) const [with _Key = Node, _Value = std::pair<const Node, int>, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable.h:897:2:   instantiated from ‘std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node*, const key_type&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = Node, _Value = std::pair<const Node, int>, _Allocator = std::allocator<std::pair<const Node, int> >, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = false, bool __unique_keys = true, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node = std::__detail::_Hash_node<std::pair<const Node, int>, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = Node, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53:   instantiated from ‘std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair<const Node, int>, _Hashtable = std::_Hashtable<Node, std::pair<const Node, int>, std::allocator<std::pair<const Node, int> >, std::_Select1st<std::pair<const Node, int> >, std::equal_to<Node>, std::hash<Node>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>, std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’
3sum.cpp:149:5:   instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:209:23: error: passing ‘const Node’ as ‘this’ argument of ‘bool Node::operator==(Node)’ discards qualifiers [-fpermissive]
make: *** [threeSum] Error 1

I guess, I need the tell C++ how to hash class Node, however, I am not quite sure how to do it. How can I accomplish this tasks?

Answer 1

To be able to use std::unordered_map (or one of the other unordered associative containers) with a user-defined key-type, you need to define two things:

1. A hash function; this must be a class that overrides operator() and calculates the hash value given an object of the key-type. One particularly straight-forward way of doing this is to specialize the std::hash template for your key-type.

2. A comparison function for equality; this is required because the hash cannot rely on the fact that the hash function will always provide a unique hash value for every distinct key (i.e., it needs to be able to deal with collisions), so it needs a way to compare two given keys for an exact match. You can implement this either as a class that overrides operator(), or as a specialization of std::equal, or – easiest of all – by overloading operator==() for your key type (as you did already).

The difficulty with the hash function is that if your key type consists of several members, you will usually have the hash function calculate hash values for the individual members, and then somehow combine them into one hash value for the entire object. For good performance (i.e., few collisions) you should think carefully about how to combine the individual hash values to ensure you avoid getting the same output for different objects too often.

A fairly good starting point for a hash function is one that uses bit shifting and bitwise XOR to combine the individual hash values. For example, assuming a key-type like this:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Here is a simple hash function (adapted from the one used in the cppreference example for user-defined hash functions):

template <>
struct std::hash<Key>
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    // Compute individual hash values for first,
    // second and third and combine them using XOR
    // and bit shifting:

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

With this in place, you can instantiate a std::unordered_map for the key-type:

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

It will automatically use std::hash<Key> as defined above for the hash value calculations, and the operator== defined as member function of Key for equality checks.

If you don't want to specialize template inside the std namespace (although it's perfectly legal in this case), you can define the hash function as a separate class and add it to the template argument list for the map:

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

How to define a better hash function? As said above, defining a good hash function is important to avoid collisions and get good performance. For a real good one you need to take into account the distribution of possible values of all fields and define a hash function that projects that distribution to a space of possible results as wide and evenly distributed as possible.

This can be difficult; the XOR/bit-shifting method above is probably not a bad start. For a slightly better start, you may use the hash_value and hash_combine function template from the Boost library. The former acts in a similar way as std::hash for standard types (recently also including tuples and other useful standard types); the latter helps you combine individual hash values into one. Here is a rewrite of the hash function that uses the Boost helper functions:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

And here’s a rewrite that doesn’t use boost, yet uses good method of combining the hashes:

template <>
struct std::hash<Key>
{
    std::size_t operator()( const Key& k ) const
    {
        // Compute individual hash values for first, second and third
        // http://stackoverflow.com/a/1646913/126995
        std::size_t res = 17;
        res = res * 31 + hash<string>()( k.first );
        res = res * 31 + hash<string>()( k.second );
        res = res * 31 + hash<int>()( k.third );
        return res;
    }
};

Answer 2

I think, jogojapan gave an very good and exhaustive answer. You definitively should take a look at it before reading my post. However, I'd like to add the following:

1. You can define a comparison function for an unordered_map separately, instead of using the equality comparison operator (operator==). This might be helpful, for example, if you want to use the latter for comparing all members of two Node objects to each other, but only some specific members as key of an unordered_map.
2. You can also use lambda expressions instead of defining the hash and comparison functions.

All in all, for your Node class, the code could be written as follows:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

Notes:

• I just reused the hashing method at the end of jogojapan's answer, but you can find the idea for a more general solution here (if you don't want to use Boost).
• My code is maybe a bit too minified. For a slightly more readable version, please see this code on Ideone.

Answer 3

For enum type, I think this is a suitable way, and the difference between class is how to calculate hash value.

template <typename T>
struct EnumTypeHash {
  std::size_t operator()(const T& type) const {
    return static_cast<std::size_t>(type);
  }
};

enum MyEnum {};
class MyValue {};

std::unordered_map<MyEnum, MyValue, EnumTypeHash<MyEnum>> map_;

Answer 4

Most basic possible copy/paste complete runnable example of using a custom class as the key for an unordered_map (basic implementation of a sparse matrix):

// UnorderedMapObjectAsKey.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

struct Pos
{
  int row;
  int col;

  Pos() { }
  Pos(int row, int col)
  {
    this->row = row;
    this->col = col;
  }

  bool operator==(const Pos& otherPos) const
  {
    if (this->row == otherPos.row && this->col == otherPos.col) return true;
    else return false;
  }

  struct HashFunction
  {
    size_t operator()(const Pos& pos) const
    {
      size_t rowHash = std::hash<int>()(pos.row);
      size_t colHash = std::hash<int>()(pos.col) << 1;
      return rowHash ^ colHash;
    }
  };
};

int main(void)
{
  std::unordered_map<Pos, int, Pos::HashFunction> umap;

  // at row 1, col 2, set value to 5
  umap[Pos(1, 2)] = 5;

  // at row 3, col 4, set value to 10
  umap[Pos(3, 4)] = 10;

  // print the umap
  std::cout << "\n";
  for (auto& element : umap)
  {
    std::cout << "( " << element.first.row << ", " << element.first.col << " ) = " << element.second << "\n";
  }
  std::cout << "\n";

  return 0;
}

Answer 5

check the following link https://www.geeksforgeeks.org/how-to-create-an-unordered_map-of-user-defined-class-in-cpp/ for more details.

• the custom class must implement the == operator
• must create a hash function for the class (for primitive types like int and also types like string the hash function is predefined)

Answer 6

STL Does not provide hash function for pairs. You need to implement it yourself and either specify as template parameter or put into namespace std, from where it will be automatically picked up. Following https://github.com/HowardHinnant/hash_append/blob/master/n3876.h is very useful for implementing custom hash functions for structutres. More details are well explained in the other answers to this question, so I won't repeat that. There is also similar thing (hash_combine) in the Boost.

Answer 7

The answers here were quite helpful, but I still struggled mightily trying to figure this out, so perhaps my lessons learned will be beneficial. I had a bit of a unique situation compared to the OP; my key was a custom UUID class that I didn't own. In what I consider a bug/oversight, this class did not define a hash function, or overload for operator() (it did define the operator==, so I was set there). Yes, I had the source, but it was widely distributed and controlled, so modifying it was a non-starter. I wanted to use this UUID as key in a std::unordered_map member, like

std::unordered_map<UUID, MyObject> mapOfObjs_;

In Visual Studio, I did eventually settle on this solution:

// file MyClass.h

namespace myNamespace
{
   static auto staticUuidHashFunc = [](const UUID& n)
   {
      // XORed the most and least significant bits, not important
   }
   ... 
   class MyClass
   {
      ...
   private:
      std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> mapOfObjs_;
   };
}

This worked great in Windows. However, when I finally took my code to gcc in linux, I got the warning (paraphrasing)

'MyClass' has a field 'mapOfObjs_' whose type uses the anonymous namespace

I even got this warning with all warnings disabled, so gcc must consider it quite serious. I googled around and found this answer, which suggested I needed to move the hash function code to the .cpp file.

At this point, I also tried deriving from the UUID class:

// file MyClass.h

namespace myNamespace
{
   struct myUuid : public UUID
   {
      // overload the operator()
   };
   ...
   // and change my map to use this type
   std::unordered_map<myUuid, std::unique_ptr<MyObject>> mapOfObjs_;
}

However, this brought its own set of problems. Namely, all parts of code that used the (now parent) UUID class were incompatible with my map, like:

void MyClass::FindUuid(const UUID& id)
{
   // doesn't work, can't convert `id` to a `myUuid` type
   auto it = mapOfObjs_.find(id);
   ...
}

was now broken. I didn't want to change all that code, so I punted on that and was back to the "put the code in the .cpp file" solution. However, stubbornly, I still tried a few things to keep the hash function in the .h file. What I was really trying to avoid was dropping the auto from the hash function definition, since I didn't know and didn't want to have to figure out what the type was. So I tried:

class MyClass
{
   ...
private:
   static auto staticUuidHashFunc = [](const UUID& n)
   {
      // my hash function
   }
};

But this (or variations of this) came back with errors, like "can't have static initializers in class", "cant use auto here", etc (I had a hard C++11 requirement). So I finally accepted I needed to treat this like a static variable, declare it in the header, and initialize it in .cpp file. Once I figured out its type, it was straight forward:

// MyClass.h
namespace myNamespace
{
   class MyClass
   {
      ...
   private:
      static std::function<unsigned long long(const UUID&)> staticUuidHashFunc;

      std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> mapOfObjs_;
   };
}

And finally in the .cpp file:

// MyClass.cpp

namespace myNamespace
{
   std::function<unsigned long long(const UUID&)> MyClass::staticUuidHashFunc = [](const UUID& n)
    {
        // the hash function
    };

    MyClass::MyClass()
       : mapOfObjs_{ std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> (MyClass::NUMBER_OF_MAP_BUCKETS, staticUuidHashFunc)}
    {  }

   ...
}

Defining the static hash function in the .cpp file was the key. After that, both Visual Studio and gcc were happy.

Answer 8

We need to do two points:

1. minimize collisions
2. hash(a,b)!=hash(b,a)

I suggest such way:

numerically we have such algorithm:

a = hash1
b = hash2
p = a+b
result_hash = p*(p+1)/2+b

but if we reduce algorithm, this will not affect collisions:

a = hash1
b = hash2
p = a+b
result_hash = p*p+b

we can check this (in python):

N=256 # number of different values of hash
d = {}
for a in range(N):
  for b in range(N):
    p = a+b
    x = (p*p+b)%N
    if x in d:
      d[x]+=1
    else:
      d[x]=1
    #print(format(x,'04b'),end='\t')
  #print()
print(max(v for k,v in d.items()))

So finally we have such methods:

p = a+b
return p*p+b

return (a<<1)^b

return a*31+b

return (17*31+a)*31+b