C ++ unordered_map使用自定义类类型作为键 [英] C++ unordered_map using a custom class type as the key
问题描述
我尝试使用自定义类作为unordered_map的键，如下所示：
#include< iostream>
#include< algorithm>
#include< unordered_map>
//＃include< map>
using namespace std;
类节点;
class解决方案;
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& & ic == 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 ++如何哈希类Node，我不太确定如何做到。
以下是g ++的错误：
在/usr/include/c++/4.6/string:50:0中包含的文件中，
来自/usr/include/c++/4.6/bits/locale_classes.h:42,
来自/usr/include/c++/4.6/bits/ios_base.h:43，
来自/usr/include/c++/4.6/ios:43，
来自/ usr / include / c ++ / 4.6 / ostream：40，
从/usr/include/c++/4.6/iostream:40，
从3sum.cpp：4：
/usr/include/c++/4.6/bits/ stl_function.h：在成员函数'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：实例化从'bool std :: __ detail :: _ Hash_code_base< _Key，_Value，_ExtractKey，_Equal，_H1，_H2，std :: __ detail :: _ Default_ranged_hash，false> 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<节点>中_H1 =的std ::散列<节点>中_H2 =的std :: __细节:: _ Mod_range_hashing，性病:: __细节:: _ 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：从'std： ：_Hashtable< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2，_hash，_RehashPolicy，__cache_hash_code，__constant_iterators，__unique_keys> :: _节点*的std :: _哈希表< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2， _hash，_RehashPolicy，__cache_hash_code，__constant_iterators，__unique_keys> :: _ M_find_node（STD :: _哈希表< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2，_hash，_RehashPolicy，__cache_hash_code，__constant_iterators，__unique_keys> :: _节点*，常量为key_type&放;，类型名的std :: _哈希表< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2，_hash，_RehashPolicy，__cache_hash_code，__constant_iterators，__unique_keys> :: _ Hash_code_type）常量[与_key =节点，_Value =的std ::对< const Node，int> _Allocator = std :: allocator< std :: pair< const Node，int> >，_ExtractKey = std :: _ Select1st< std :: pair< const Node，int> >中_Equal =的std :: equal_to<节点>中_H1 =的std ::散列<节点>中_H2 =的std :: __细节:: _ Mod_range_hashing，_hash =的std :: __细节:: _ Default_ranged_hash，_RehashPolicy =的std :: __细节： ：_Prime_rehash_policy，布尔__cache_hash_code =假，布尔__constant_iterators =假，布尔__unique_keys = TRUE，性病:: _哈希表< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2，_hash，_RehashPolicy，__cache_hash_code，__constant_iterators，__unique_keys> :: _节点=的std :: __细节:: _ Hash_node<的std ::对<常量节点，INT>中假> ;,的std :: _哈希表< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2，_hash，_RehashPolicy，__cache_hash_code，__constant_iterators， __unique_keys> ::为key_type =节点，类型名称的std :: _哈希表< _key，_Value，_Allocator，_ExtractKey，_Equal，_H1，_H2，_hash，_RehashPolicy，__cache_hash_code，__constant_iterators，__unique_keys> :: _ Hash_code_type =长期无符号整型]'
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53：从'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& 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， std :: __ detail :: _ Map_base< _Key，_Pair，std :: _ Select1st< _Pair> ;, true，_Hashtable> :: mapped_type = int]'
3sum.cpp：149：5：从这里实例化
/usr/include/c++/4.6/bits/stl_function.h:209:23：错误：将'const Node'作为'bool Node :: operator ==（Node）'的'this'参数传递丢弃限定符[-fpermissive]
make：*** [threeSum]错误1
为了能够使用用户定义的键类型使用 std :: unordered_map （或其他无序关联容器之一），您需要定义两个东西：
-
哈希函数;这必须是覆盖
operator（）并计算给定键类型对象的哈希值的类。一个特别直接的方法是为你的键类型专门化std :: hash模板。 -
等于的比较函数;这是必需的，因为散列不能依赖于散列函数将总是为每个不同的密钥提供唯一的散列值（即，它需要能够处理冲突）的事实，因此它需要一种方式来比较两个给定的密钥完全匹配。您可以将此实现为覆盖
operator（）或作为std :: equal的特殊化的类，或–最简单的 b
哈希函数的难点是，如果你的键类型由几个成员组成，你通常会使用哈希函数为每个成员计算哈希值，然后以某种方式将它们组合成一个哈希值整个对象。对于良好的性能（即几乎没有冲突），你应该仔细考虑如何组合单个散列值，以确保避免过多地为不同的对象获得相同的输出。
散列函数的相当好的起点是使用比特移位和按位异或来组合各个散列值的。例如，假设这样的键类型：
struct Key
{
std :: string第一;
std :: string second;
int third;
bool operator ==（const Key& other）const
{return（first == other.first
&& second == other.second
&& third == other.third）;
}
};
这里是一个简单的哈希函数（改编自用户定义的哈希函数的参考示例）：
namespace std {
template<>
struct hash< Key>
{
std :: size_t operator（）（const Key& k）const
{
using std :: size_t;
using std :: hash;
using std :: string;
//计算第一个散列值，
//第二个和第三个，并使用XOR
//和位移组合它们：
return （hash< string>（）（k.first）
^（hash< string>（）（k.second）< 1））> 1）
^ ; int>（）（k.third）<<< 1）;
}
};
}
这样就可以实例化一个
std :: unordered_map的键类型：int main $ b {
std :: unordered_map< Key，std :: string> m6 = {
{{John，Doe，12}，example}，
{{Mary，Sue，21}，another}
};
}
它会自动使用
std :: hash< Key> ;定义为键运算符==如果你不想在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）<<<
}
};
int main（）
{
std :: unordered_map< Key，std :: string，KeyHasher> m6 = {
{{John，Doe，12}，example}，
{{Mary，Sue，21}，another}
};
}
如何定义更好的哈希函数？如上所述，定义好的哈希函数对于避免冲突和获得良好的性能是重要的。对于一个真正好的，你需要考虑所有字段的可能值的分布，并定义一个哈希函数，将该分布预测到尽可能广泛和均匀分布的可能结果的空间。
这可能很困难;上面的XOR /位移位方法可能不是一个坏的开始。为了稍好一些，您可以使用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;
//以哈希值0开始。
std :: size_t seed = 0;
//通过XOR和位移位在
中修改'种子'//另一个之后的Key的一个成员：
hash_combine（seed，hash_value（k.first ））;
hash_combine（seed，hash_value（k.second））;
hash_combine（seed，hash_value（k.third））;
//返回结果。
return seed;
}
};
下面是一个不使用boost的重写， / p>
namespace std
{
template<>
struct hash< Key>
{
size_t operator（）（const Key& k）const
{
//计算第一，第二和第三个哈希值
// 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;
}
};
}
I am trying to use a custom class as key for unordered_map, like the following,
#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 ( 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; }I guess I need the tell C++ how to hash class Node, however, I am not quite sure how to do it. Is there any example for this kind of tasks?
The following is the error from 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解决方案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: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 thestd::hashtemplate for your key-type.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 ofstd::equal, or – easiest of all – by overloadingoperator==()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):
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: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 theoperator==defined as member function ofKeyfor equality checks.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: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_valueandhash_combinefunction template from the Boost library. The former acts in a similar way asstd::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:#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:
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; } }; }这篇关于C ++ unordered_map使用自定义类类型作为键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
