为何unordered_set不支持pair<int,int>与vector<int>类型？

问题现象 #

下面两段代码会触发编译错误：

unordered_set<pair<int,int>> vis;
unordered_set<vector<int>> vis;

但将容器换成set后就能正常编译：

set<vector<int>> vis;
set<pair<int,int>> vis;

测试代码示例：

int test()
{
        unordered_set<pair<int,int>> vis;
        return 0;
}

对应的编译错误信息：

error: call to implicitly-deleted default constructor of 'unordered_set<pair<int, int>>'
        unordered_set<pair<int,int>> vis;
                                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/unordered_set.h:135:7: note: explicitly defaulted function was implicitly deleted here
      unordered_set() = default;
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/unordered_set.h:100:18: note: default constructor of 'unordered_set<std::pair<int, int>, std::hash<std::pair<int, int>>, std::equal_to<std::pair<int, int>>, std::allocator<std::pair<int, int>>>' is implicitly deleted because field '_M_h' has a deleted default constructor
      _Hashtable _M_h;
                 ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable.h:414:7: note: explicitly defaulted function was implicitly deleted here
      _Hashtable() = default;
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable.h:174:7: note: default constructor of '_Hashtable<std::pair<int, int>, std::pair<int, int>, std::allocator<std::pair<int, int>>, std::__detail::_Identity, std::equal_to<std::pair<int, int>>, std::hash<std::pair<int, int>>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true>>' is implicitly deleted because base class '__detail::_Hashtable_base<pair<int, int>, pair<int, int>, _Identity, equal_to<pair<int, int>>, hash<pair<int, int>>, _Mod_range_hashing, _Default_ranged_hash, _Hashtable_traits<true, true, true>>' has a deleted default constructor
    : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:1822:5: note: explicitly defaulted function was implicitly deleted here
    _Hashtable_base() = default;
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:1771:5: note: default constructor of '_Hashtable_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::equal_to<std::pair<int, int>>, std::hash<std::pair<int, int>>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true>>' is implicitly deleted because base class '_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int>>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, _Hashtable_traits<true, true, true>::__hash_cached::value>' has a deleted default constructor
  : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
    ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:1373:7: note: explicitly defaulted function was implicitly deleted here
      _Hash_code_base() = default;
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:1349:7: note: default constructor of '_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int>>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>' is implicitly deleted because base class '_Hashtable_ebo_helper<1, std::hash<std::pair<int, int>>>' has a deleted default constructor
      private _Hashtable_ebo_helper<1, _H1>,
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:1096:7: note: explicitly defaulted function was implicitly deleted here
      _Hashtable_ebo_helper() = default;
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:1094:7: note: default constructor of '_Hashtable_ebo_helper<1, std::hash<std::pair<int, int>>, true>' is implicitly deleted because base class 'std::hash<std::pair<int, int>>' has a deleted default constructor
    : private _Tp
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/functional_hash.h:101:19: note: default constructor of 'hash<std::pair<int, int>>' is implicitly deleted because base class '__hash_enum<std::pair<int, int>>' has no default constructor
    struct hash : __hash_enum<_Tp>
                  ^
1 error generated.

差异原因 #

这两个容器的底层实现逻辑完全不同，对存储元素的要求也不一样：

• set的要求：set是基于红黑树的有序容器，它只需要元素支持小于比较运算符<。C++标准库已经默认给pair和vector实现了<运算符重载，所以set<pair<int,int>>和set<vector<int>>能正常编译。
• unordered_set的要求：unordered_set是哈希表实现的无序容器，它需要元素满足两个条件：一是支持相等比较运算符==，二是要有对应的哈希函数（即std::hash的特化版本）。虽然标准库给pair和vector提供了==重载，但没有默认提供std::hash<pair<T1,T2>>和std::hash<vector<T>>的特化。

编译错误的根源就在于：当你声明unordered_set<pair<int,int>>时，编译器会自动尝试使用默认的std::hash<pair<int,int>>，但这个特化不存在，导致哈希表的底层结构无法初始化，最终触发了默认构造函数被删除的错误。

解决办法（如果要使用unordered_set存储这类元素） #

你需要自定义哈希函数，并在声明unordered_set时指定它。比如针对pair<int,int>：

// 自定义哈希函数
struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        // 组合两个int的哈希值，避免碰撞可以用更复杂的方式
        size_t h1 = std::hash<int>()(p.first);
        size_t h2 = std::hash<int>()(p.second);
        return h1 ^ (h2 << 1);
    }
};

// 使用自定义哈希的unordered_set
unordered_set<pair<int,int>, PairHash> vis;

内容的提问来源于stack exchange，提问作者Ryan