使用自定义类types作为键的C ++ unordered_map
我正在尝试使用自定义类作为unordered_map的关键字，如下所示，
#include <iostream> #include <algorithm> #include <unordered_map> //#include <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 ( ia==this->a && ib==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; } 我想我需要告诉C ++如何散列类节点，但是，我不太确定如何做到这一点。 这种任务有没有例子？
以下是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
为了能够使用std::unordered_map （或其他无序的关联容器之一）和用户定义的键types，需要定义两件事情：
-
散列函数 ; 这必须是一个覆盖
operator()的类，并且计算给定keytypes的对象的哈希值。 这样做的一个特别直接的方法是专门为你的密钥types使用std::hash模板。 -
比较function的平等 ; 这是必需的，因为散列不能依赖于散列函数总是为每个不同的密钥提供唯一散列值的事实（即，它需要能够处理冲突），所以它需要一种方法来比较两个给定的密钥完全匹配。 你可以通过重载
operator==()来重载operator()，或者作为std::equal的特殊化，或者最简单的方法来实现这个operator()（就像你已经做过的那样）。
散列函数的难点在于，如果你的键types由多个成员组成，你通常会使用散列函数为各个成员计算散列值，然后以某种方式将它们合并为一个整个对象的散列值。 为了获得良好的性能（即，很less发生冲突），您应该仔细考虑如何组合各个散列值，以确保避免经常为不同对象获取相同的输出。
散列函数的一个相当好的起点是使用位移和按位异或来组合单个散列值的散列函数。 例如，假设一个这样的密钥types：
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); } };
这里是一个简单的哈希函数（根据用户定义哈希函数的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); } }; }
有了这个，你可以为key-type实例化一个std::unordered_map ：
int main() { std::unordered_map<Key,std::string> m6 = { { {"John", "Doe", 12}, "example"}, { {"Mary", "Sue", 21}, "another"} }; }
它将自动使用上面定义的std::hash<Key>作为散列值计算，而operator==定义为Key成员函数，用于相等性检查。
如果您不想在std名称空间内专门化模板（尽pipe在这种情况下它完全合法），您可以将散列函数定义为单独的类，并将其添加到地图的模板参数列表中：
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"} }; }
如何定义一个更好的散列函数？ 如上所述，定义一个好的散列函数对于避免冲突并获得良好的性能非常重要。 对于一个真正的好的，你需要考虑所有字段的可能值的分布，并定义一个散列函数，将散布投影到尽可能广泛和均匀分布的可能结果空间中。
这可能是困难的; 上面的XOR /位移方法可能不是一个糟糕的开始。 为了稍微好一点，可以使用Boost库中的hash_combine和hash_combine函数模板。 前者的行为与标准types的std::hash类似（最近也包括元组和其他有用的标准types）; 后者可以帮助您将各个散列值合并为一个。 下面是使用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; } };
这里是一个不使用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; } }; }
