支持在std::unordered_set<Key>
和std::unordered_map<Key, Value>
中自定义键类型必须提供operator==(Key, Key)
和哈希函子:
struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }
struct MyHash {
size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};
std::unordered_set<X, MyHash> s;
只写std::unordered_set<X>
会更方便对于X
类型,使用默认散列,比如编译器和库自带的类型。参考
- c++标准草案N3242§20.8.12和§17.6.3.4 [Hash。要求),
- 提振。无序
- g++
includec++4.7.0bitsfunctional_hash.h
- vc10
includexfunctional
- Stack Overflow中的各种相关问题
似乎可以专门化std::hash<X>::operator()
:
namespace std { // argh!
template <>
inline size_t
hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++
// or
// hash<X>::operator()(X x) const { return hash<int>()(x.id); } // works for g++ 4.7, but not for VC10
}
考虑到编译器对c++ 11的支持还处于实验阶段——我没有尝试Clang——,以下是我的问题:
将这样的专门化添加到命名空间
std
是否合法?我对此百感交集。哪个
std::hash<X>::operator()
版本(如果有的话)是符合c++ 11标准的?有便携的方法吗?
明确允许并鼓励您向命名空间std
*添加专门化。添加哈希函数的正确(基本上也是唯一)方法是:
namespace std {
template <> struct hash<Foo>
{
size_t operator()(const Foo & x) const
{
/* your code here, e.g. "return hash<int>()(x.value);" */
}
};
}
(您可能考虑支持的其他流行专门化是std::less
, std::equal_to
和std::swap
。)
*)只要涉及的类型之一是用户定义的,我想。
我打赌是在unordered_map/unorder_set/…的Hash模板参数上。类:
#include <unordered_set>
#include <functional>
struct X
{
int x, y;
std::size_t gethash() const { return (x*39)^y; }
};
typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset;
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2;
int main()
{
auto hashX = [](const X&x) { return x.gethash(); };
Xunset my_set (0, hashX);
Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef
}
当然
- hashX也可以是全局静态函数 在第二种情况下,您可以传递
- 老式函数对象(
struct Xhasher { size_t operator(const X&) const; };
) -
std::hash<X>()
- 任何满足签名的绑定表达式-
- 老式函数对象(
@Kerrek SB已经覆盖了1)和3).
2)尽管g++和VC10用不同的签名声明std::hash<T>::operator()
,但这两个库的实现都是符合标准的。
标准没有指定std::hash<T>
的成员。它只是说,每个这样的专门化必须满足std::unordered_set
的第二个模板参数所需的相同的"哈希"需求,以此类推。即:
- 哈希类型
H
是一个函数对象,至少有一个参数类型Key
。 -
H
是可复制的 -
H
是可破坏的 - 如果
h
是类型为H
或const H
的表达式,并且k
是类型可转换为(可能是const
)Key
的表达式,则h(k)
是类型为size_t
的有效表达式。 - 如果
h
是类型为H
或const H
的表达式,u
是类型为Key
的左值,则h(u)
是类型为size_t
的合法表达式,不修改u
。