unordered_set/unordered_map 自定义类型

c++

使用 std::unordered_set 存储自定义类型，或者使用自定义类型作为 std::unordered_map 的 key 时，报出类似使用已删除的方法的编译错误：

1
use of deleted function 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set() [with _Value = S; _Hash = std::hash<S>; _Pred = std::equal_to<S>; _Alloc = std::allocator<S>]'

一般是因为没有自定义 hash 函数对象导致的。例如 std::unordered_map 定义如下：

1
2
3
4
5
6
7
template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;
    > class unordered_map

可见 unordered_map/unordered_set 需要一个哈希函数对象来计算 key 的 hash 值，因为底层都是基于哈希表的。当使用内置类型的时候，哈希函数对象使用 std::hash, 其支持的类型见 https://en.cppreference.com/w/cpp/utility/hash。当使用自定义类型时没有对应的 std::hash, 就需要自己提供。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cassert>
#include <utility>
#include <unordered_set>
using namespace std;

struct S {
    int a, b;

    bool operator==(const S& s) const {
        return (a == s.a) && (b == s.b);
    }
};

struct hash_s {
    size_t operator()(const S& s) const {
        return hash<int>()(s.a) ^ hash<int>()(s.b);
    }
};

unordered_set<S, hash_s> s;

int main() {
  s.insert({1, 2});
  s.insert({3, 4});
  assert(s.find({1, 2}) != s.end());  
}