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?

Maniemanifest

The third template argument is the hash function you need to supply. – Coauthor

cppreference has a simple and practical example of how to do this: en.cppreference.com/w/cpp/container/unordered_map/unordered_map – Lens

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
        // https://mcmap.net/q/23169/-quick-and-simple-hash-code-combinations
        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;
    }
};

Lens

Can you please explain why it is necessary to shift the bits in KeyHasher ? – Ciccia

If you didn't shift the bits and two strings were the same, the xor would cause them to cancel each other out. So hash("a","a",1) would be the same as hash("b","b",1). Also order wouldn't matter, so hash("a","b",1) would be the same as hash("b","a",1). – Fiona

I am just learning C++ and one thing I always struggle with is: Where to put the code? I have written a specialize std::hash method for my key as you have done. I put this at the bottom of my Key.cpp file but I am getting the following error: Error 57 error C2440: 'type cast' : cannot convert from 'const Key' to 'size_t' c:\program files (x86)\microsoft visual studio 10.0\vc\include\xfunctional. I am guessing that the compiler is not finding my hash method? Should I be adding anything to my Key.h file? – Gandhi

When I put my specialize std::hash method in to the Key.h file my program compiles fine, but it seems wrong to put implementation into a header file. – Gandhi

@Gandhi Putting it into the .h file is correct. std::hash is not actually a struct, but a template (specialization) for a struct. So it isn't an implementation -- it will be turned into an implementation when the compiler needs it. Templates should always go into header files. See also #495521 – Lens

@jogojapan: Thank you for the explaination. I was wondering how would I use the find function? If I do find(key), I would get the string here right? i.e if I say find({"John", "Doe", 12}) the iterator returned would be pointing to "example" or to the location of key? I am confused – Hubbell

@nightfury find() returns an iterator, and that iterator points to an "entry" of the map. An entry is a std::pair consisting of key and value. So if you do auto iter = m6.find({"John","Doe",12});, you'll get the key in iter->first and the value (i.e. the string "example") in iter->second. If you want the string directly, you can either use m6.at({"John","Doe",12}) (that will throw an exception if the key doesn't exits), or m6[{"John","Doe",12}] (that will create an empty value if the key doesn't exist). – Lens

Can you please tell where you got documentation original documentation for the top part of your answer? – Audriaaudrie

BTW, I was trying to define my operator== in terms of the template's hash function, which, by your explanation, is wrong! – Audriaaudrie

@Audriaaudrie It follows from various sections of the C++ Standard. Are you interested in which sections those are? Or are you looking for a text book chapter that describes this? – Lens

On whatever documentation you used to know it yourself :) – Audriaaudrie

@jogojapan, I wonder if it is ok to concatenate 2 strings and convert int to string and then calculate hash function for that string because hash function is already specialized for std::string. Is it just not that efficient or there are any other drawbacks? Because that was first that came to my mind, though I'm not an expert in this. – Lammers

@Lammers Yes, one concern would be efficiency -- but depending on your situation that may not be important for you. Another concern is that fact that the hash function for string has been designed under the assumption that the strings it is applied to may contain all kinds of characters, not only the characters for numerical digits. Since the strings you will be building will all consist of digits only, the resulting hash values may not uniformly exhaust the space of possible hash values. (Then again, it's not a big problem. What you propose would definitely work in principle.) – Lens

Would it be possible / easy to reuse the hash function of std::tuple? I guess not by deriving from std::tuple, since that has various flaws, but by using tuple through composition? (Or ideally, by reusing the hash implementation from tuple, without even adding a tuple data member - I doubt it's possible though?) – Machinist

uhhh. wait... there's no std::hash pre-defined for a tuple? Am I missing something?.. If not, then my previous question is moot. – Machinist

Why instead of ^ (hash<int>()(k.third) << 1) that would be xor one size_t type; one not use just ^k.third. because sizeof(size_t)>=sizeof(int) why use hash function for one obj size less than size_t? – Woodbine

The last hash function is really interesting. What is the basis of this algorithm? – Flournoy

Fantastic answer! Just to add that operator() override should be specified as noexcept, at least according to ReSharper suggestion. – Mchugh

@Lens The specialization has to be declared in the header, but the implementation doesn't have to live in the header. – Villein

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.

Winser

where did the 8 come from and what does it mean? – Funambulist

@WhalalalalalalaCHen: Please take a look at the documentation of the unordered_map constructor. The 8 represents the so-called "bucket count". A bucket is a slot in the container's internal hash table, see e.g. unordered_map::bucket_count for more information. – Winser

@WhalalalalalalaCHen: I picked 8 at random. Depending on the content you want to store in your unordered_map, the bucket count can affect the performance of the container. – Winser

Answer 3

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;
}

Polemic

How do you do this without supplying the third argument for the unordered_map? – Mutualism

Answer 4

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_;

Hypoderma

This is exactly what I was looking for!!! Thanks a lot Jiaqi Ju! – Bamford

Answer 5

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.

Timothea

Answer 6

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)

Headship

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.

Makkah

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

Behalf

I definetely don't agree with the third option. 31 is just too tiny. 31 is chosen because of it being a power of 2 but one less. 63, 127, 255, etc. would be better though because they are larger. It's best if it can be specialized, for example, if your values are guarenteed to be under 40,000, you can use return a*(1 << 16) + b. – Shaft

Third option is reduced fourth option (number of collisions are the same). But Forth option is most popular answer in this thread. – Szechwan