我试图使用自定义类作为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 ( 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;
}
我想我需要告诉C如何散列类Node,但是,我不太清楚如何做到这一点 . 这种任务有什么例子吗?
以下是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
1 回答
为了能够将
std::unordered_map
(或其他无序关联容器之一)与用户定义的键类型一起使用,您需要定义两件事:A hash function ;这必须是一个覆盖
operator()
的类,并计算给定键类型对象的哈希值 . 一种特别直接的方法是将std::hash
模板专门用于您的密钥类型 .A comparison function for equality ;这是必需的,因为哈希不能依赖于哈希函数将始终为每个不同的键提供唯一哈希值的事实(即,它需要能够处理冲突),因此需要一种方法来比较两个给定的键完全匹配 . 您可以将此实现为覆盖
operator()
的类,或者作为std::equal
的特化,或者最简单的方法 - 通过为您的密钥类型重载operator==()
(就像您已经这样) .散列函数的难点在于,如果您的键类型由多个成员组成,您通常会使用散列函数计算各个成员的散列值,然后以某种方式将它们组合成整个对象的一个散列值 . 为了获得良好的性能(即碰撞很少),您应该仔细考虑如何组合各个哈希值,以确保避免过于频繁地为不同的对象获取相同的输出 .
散列函数的一个相当好的起点是使用位移和按位异或来组合各个散列值的起点 . 例如,假设键类型如下:
这是一个简单的哈希函数(改编自_727786中使用的哈希函数):
有了这个,您可以为密钥类型实例化
std::unordered_map
:它将自动使用上面定义的
std::hash<Key>
进行哈希值计算,并将operator==
定义为Key
的成员函数进行相等性检查 .如果您不想在
std
命名空间内专门化模板(尽管在这种情况下它是完全合法的),您可以将哈希函数定义为单独的类并将其添加到 Map 的模板参数列表中:如何定义更好的哈希函数?如上所述,定义良好的散列函数对于避免冲突和获得良好性能非常重要 . 对于一个真正的好的,您需要考虑所有字段的可能值的分布,并定义一个散列函数,该散列函数将该分布投影到尽可能宽且均匀分布的可能结果的空间 .
这可能很困难;上面的XOR /位移方法可能不是一个糟糕的开始 . 为了更好的开始,您可以使用Boost库中的
hash_value
和hash_combine
函数模板 . 对于标准类型(最近还包括元组和其他有用的标准类型),前者的行为与std::hash
类似;后者可以帮助您将各个哈希值合并为一个 . 这是重写使用Boost辅助函数的哈希函数:这里是一个不使用boost的重写,但使用了很好的方法来组合哈希: