使用自定义类类型作为键的 C++ unordered_map

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

提问by Alfred Zhong

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

我正在尝试使用自定义类作为 的键unordered_map，如下所示：

#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:

但是，g++ 给了我以下错误：

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?

我想，我需要告诉 C++ 如何散列 class Node，但是，我不太确定该怎么做。我怎样才能完成这个任务？

回答by jogojapan

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:

为了能够将std::unordered_map（或其他无序关联容器之一）与用户定义的键类型一起使用，您需要定义两件事：

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::hashtemplate 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).

1. 一个哈希函数；这必须是一个类，它可以覆盖operator()并计算给定键类型对象的哈希值。一种特别直接的方法是std::hash为您的键类型专门化模板。

2. 相等的比较函数；这是必需的，因为散列不能依赖这样一个事实，即散列函数将始终为每个不同的键提供唯一的散列值（即，它需要能够处理冲突），因此它需要一种方法来比较两个给定的键精确匹配。您可以将其实现为覆盖 的类operator()，或者作为 的特化std::equal，或者 - 最简单的 - 通过重载operator==()您的键类型（就像您已经做过的那样）。

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):

这是一个简单的哈希函数（改编自cppreference 示例中用于用户定义的哈希函数的函数）：

namespace std {

  template <>
  struct 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_mapfor the key-type:

有了这个，您可以std::unordered_map为键类型实例化 a ：

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 Keyfor equality checks.

它将自动使用std::hash<Key>如上定义的哈希值计算，以及operator==定义Key为等式检查的成员函数。

If you don't want to specialize template inside the stdnamespace (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:

如果您不想在std命名空间内专门化模板（尽管在这种情况下它是完全合法的），您可以将哈希函数定义为一个单独的类并将其添加到映射的模板参数列表中：

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_valueand hash_combinefunction template from the Boost library. The former acts in a similar way as std::hashfor 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:

这可能很困难；上面的异或/位移方法可能不是一个糟糕的开始。为了更好地开始，您可以使用Boost 库中的hash_value和hash_combine函数模板。前者的行为方式与std::hash标准类型类似（最近还包括元组和其他有用的标准类型）；后者可帮助您将单个哈希值合并为一个。这是使用 Boost 辅助函数的哈希函数的重写：

#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:

这是一个不使用 boost 的重写，但使用了组合散列的好方法：

namespace std
{
    template <>
    struct hash<Key>
    {
        size_t operator()( const Key& k ) const
        {
            // Compute individual hash values for first, second and third
            // http://stackoverflow.com/a/1646913/126995
            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;
        }
    };
}

回答by honk

I think, jogojapangave 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:

我认为，jogojapan给出了一个非常好的和详尽的答案。在阅读我的帖子之前，您绝对应该先看看它。但是，我想添加以下内容：

1. You can define a comparison function for an unordered_mapseparately, 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 Nodeobjects to each other, but only some specific members as key of an unordered_map.
2. You can also use lambda expressionsinstead of defining the hash and comparison functions.

1. 您可以为unordered_map单独定义一个比较函数，而不是使用相等比较运算符 ( operator==)。这可能会有所帮助，例如，如果您想使用后者将两个Node对象的所有成员相互比较，但只有某些特定成员作为unordered_map.
2. 您还可以使用lambda 表达式而不是定义散列和比较函数。

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

总而言之，对于你的Node类，代码可以写成如下：

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.

• 我只是在 jogojapan 的答案末尾重用了哈希方法，但是您可以在此处找到更通用的解决方案的想法（如果您不想使用 Boost）。
• 我的代码可能有点过于缩小了。有关可读性稍强的版本，请参阅Ideone 上的此代码。