散列 unordered_map 对<pair<int,int>，对<int,int>>

Question

我定义了以下类型

typedef pair<int,int> point ;
typedef pair<int,int> fraction ; 
typedef pair<fraction,fraction> line ;

使用自定义哈希函数如下 -

struct hash_pair { 
    template <class T1, class T2>
    size_t operator() (const pair<T1, T2> &pair) const
    {
        return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
    }
};

我声明了两张地图如下-

unordered_map<point, int, hash_pair> points ;
unordered_map<line, int, hash_pair> lines ;

我还有两个变量 point p 和 line l 我适当地分配了。当我执行 points.find(p) 时，它正常工作。但是，当我使用 lines.find(l) 时，我会收到如下无穷无尽的错误行 -

solution.cpp: In instantiation of 'size_t hash_pair::operator()(const std::pair<_T1, _T2>&) const [with T1 = std::pair<int, int>; T2 = std::pair<int, int>; size_t = long unsigned int]':
/usr/include/c++/9.2.0/bits/hashtable_policy.h:1384:16:   required from 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = std::pair<std::pair<int, int>, std::pair<int, int> >; _Value = std::pair<const std::pair<std::pair<int, int>, std::pair<int, int> >, int>; _ExtractKey = std::__detail::_Select1st; _H1 = hash_pair; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = long unsigned int]'
/usr/include/c++/9.2.0/bits/hashtable.h:1417:19:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::find(const key_type&) [with _Key = std::pair<std::pair<int, int>, std::pair<int, int> >; _Value = std::pair<const std::pair<std::pair<int, int>, std::pair<int, int> >, int>; _Alloc = std::allocator<std::pair<const std::pair<std::pair<int, int>, std::pair<int, int> >, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<std::pair<int, int>, std::pair<int, int> > >; _H1 = hash_pair; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::iterator = std::__detail::_Node_iterator<std::pair<const std::pair<std::pair<int, int>, std::pair<int, int> >, int>, false, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::key_type = std::pair<std::pair<int, int>, std::pair<int, int> >]'
/usr/include/c++/9.2.0/bits/unordered_map.h:921:29:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Key = std::pair<std::pair<int, int>, std::pair<int, int> >; _Tp = int; _Hash = hash_pair; _Pred = std::equal_to<std::pair<std::pair<int, int>, std::pair<int, int> > >; _Alloc = std::allocator<std::pair<const std::pair<std::pair<int, int>, std::pair<int, int> >, int> >; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator = std::__detail::_Node_iterator<std::pair<const std::pair<std::pair<int, int>, std::pair<int, int> >, int>, false, true>; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type = std::pair<std::pair<int, int>, std::pair<int, int> >]'
solution.cpp:105:30:   required from here
solution.cpp:11:16: error: use of deleted function 'std::hash<std::pair<int, int> >::hash()'
   15 |         return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
      |

在 lines.find(l) 上标记了两个错误，在 return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);

上标记了另一个错误

任何人都可以帮助我如何在 pair<pair<int,int>,pair<int,int>> 上定期使用 unordered_map 吗？谢谢！

Answer 1

处理嵌套对的最简单方法是递归并提供当参数不是对时退出的重载。例如：

struct hash_pair { 
    template <class T1, class T2>
    size_t operator() (const pair<T1, T2> &pair) const
    {
        return (*this)(pair.first) ^ (*this)(pair.second);
    }

    template <class T>
    size_t operator() (const T &v) const
    {
        return hash<T>()(v);
    }
};

（当然，简单的 xor 并不是散列对的好方法。）

散列 unordered_map 对<pair<int,int>，对<int,int>>

Hashing an unordered_map of pair<pair<int,int>,pair<int,int>>

c++

hash

templates

unordered-map