我使用的是这样声明的有序集:
std::set<std::pair<const std::string, const myClass *> > myset;
在对我使用 set 的方式进行一些分析后,
我得出结论,unordered_set
将是一个更明智的选择。但是当我将 std::set
更改为 std::unordered_set
时,我的编译器 (g++ 4.8.1) 收到了大量错误消息,提示一个
invalid use of incomplete type struct std::hash<std::pair<const std::basic_string<char>, const myClass * > >
我发现 std::hash
不知道如何处理 std::pair
类型,尽管事实上这两种类型组成的 对
都是可哈希的。我想error for hash function of pair of ints包含有关 C++11 标准的相关信息,这些信息解释了为什么出现问题。 (对于 g++ 为此发出的坚不可摧的错误文本墙,没有很好的解释。)
在我看来
std::hash<std::pair<T1, T2>> hasher(make_pair(x,y))
= some_func(std::hash<T1>hasher(x), std::hash<T2>hasher(y) )
其中 some_func()
可以像异或一样简单(或者不是;参见 Why is XOR the default way to combine hashes?)
标准是否有充分的理由不要求 std::hash
知道如何为一个对
类型的对象构造哈希值每个都可以哈希吗?
最佳答案
原因很简单,没有加入标准。散列其他结构也是如此,如 tuple
.
事物在足够好时往往会被添加到标准中,而不是在它们完美时,因为完美是好的敌人。更多专业std::hash
不会(经常)破坏代码,因此添加新代码相对无害。
无论如何,为此,我们可以编写自己的哈希扩展器。例如:
namespace hashers {
constexpr size_t hash_combine( size_t, size_t ); // steal from boost, or write your own
constexpr size_t hash_combine( size_t a ) { return a; }
constexpr size_t hash_combine() { return 0; }
template<class...Sizes>
constexpr size_t hash_combine( size_t a, size_t b, Sizes... sizes ) {
return hash_combine( hash_combine(a,b), sizes... );
}
template<class T=void> struct hash;
template<class A, class B>
constexpr size_t custom_hash( std::pair<A,B> const& p ) {
return hash_combine( hash<size_t>{}(2), hash<std::decay_t<A>>{}(p.first), hash<std::decay_t<B>>{}(p.second) );
}
template<class...Ts, size_t...Is>
constexpr size_t custom_hash( std::index_sequence<Is...>, std::tuple<Ts...> const& p ) {
return hash_combine( hash<size_t>{}(sizeof...(Ts)), hash<std::decay_t<Ts>>{}(std::get<Is>(p))... );
}
template<class...Ts>
constexpr size_t custom_hash( std::tuple<Ts...> const& p ) {
return custom_hash( std::index_sequence_for<Ts...>{}, p );
}
template<class T0, class C>
constexpr size_t custom_hash_container( size_t n, C const& c) {
size_t retval = hash<size_t>{}(n);
for( auto&& x : c)
retval = hash_combine( retval, hash<T>{}(x) );
return retval;
}
template<class T0, class C>
constexpr size_t custom_hash_container( C const& c) {
return custom_hash_container( c.size(), c );
}
template<class T, class...Ts>
size_t custom_hash( std::vector<T, Ts...> const& v ) {
return custom_hash_container<T>(v);
}
template<class T, class...Ts>
size_t custom_hash( std::basic_string<T, Ts...> const& v ) {
return custom_hash_container<T>(v);
}
template<class T, size_t n>
constexpr size_t custom_hash( std::array<T, n> const& v ) {
return custom_hash_container<T>(n, v);
}
template<class T, size_t n>
constexpr size_t custom_hash( T (const& v)[n] ) {
return custom_hash_container<T>(n, v);
}
// etc -- list, deque, map, unordered map, whatever you want to support
namespace details {
template<class T, class=void>
struct hash : std::hash<T> {};
using hashers::custom_hash;
template<class T>
struct hash<T,decltype(void(
custom_hash(declval<T const&>())
)) {
constexpr size_t operator()(T const& t)const {
return custom_hash(t);
}
};
}
template<class T>
struct hash : details::hash<T> {};
template<>
struct hash<void> {
template<class T>
constexpr size_t operator()(T const& t)const { return hash<T>{}(t); }
}
}
现在hashers::hash<T>
将递归地使用 ADL 查找 custom_hash
函数,或 std::hash
如果失败,散列 T
及其组件,以及hashers::hash<>
是一个通用的哈希器,它试图对传递给它的任何东西进行哈希处理。
代码可能无法编译,如图所示。
我选择散列所有容器和元组作为它们的长度散列,然后散列它们的内容组合。作为副作用,array<int, 3>
哈希值与 tuple<int,int,int>
相同, 和 tuple<int,int>
哈希值与 pair<int,int>
相同, 和 std::vector<char>{'a','b','c', '\0'}
哈希值与 "abc"
相同,我认为这是一个不错的属性。空数组/元组/vector/等散列像 size_t(0)
.
您可以通过简单地覆盖 custom_hash
来为您自己的类型扩展上述系统。在相关类型的 namespace 中,或专门化 std::hash<X>
或 hashers::hash<X>
做你的自定义散列(我会选择 std::hash
以最小化我自己的原则)。对于高级使用,您可以专门hashers::details::hash<X,void>
与 SFINAE,但我会说为 custom_hash
做相反。
关于c++ - 当 T 是 std::pair<std::hash 也支持的两种更简单的类型> 时,std::hash<T> 应该工作吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27950212/