> For the complete documentation index, see [llms.txt](https://zoupers.gitbook.io/cpp-17-stl-cookbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zoupers.gitbook.io/cpp-17-stl-cookbook/chapter2-0-chinese/chapter2-8-chinese.md).

# std::unordered\_map中使用自定义类型

当我们使用`std::unordered_map`代替`std::map`时，对于键的选择要从另一个角度出发。`std::map`要求键的类型可以排序。因此，元素可以进行排序。不过，当我们使用数学中的向量作为键呢？这样一来就没有判断哪个向量大于另一个向量，比如向量(0, 1)和(1, 0)无法相比较，因为它们指向的方向不同。在`std::unordered_map`中这都不是问题，因为不需要对键的哈希值进行排序。对于我们来说只要为类型实现一个哈希函数和等同`==`操作符的实现，等同操作符的是实现是为了判断两个对象是否完全相同。本节中，我们就来实验一下这个例子。

## How to do it...

本节中，我们要定义一个简单的`coord`数据结构，其没有默认哈希函数，所以我们必须要自行定义一个。然后我们会使用`coord`对象来对应一些值。

1. 包含使用`std::unordered_map`所必须的头文件

   ```cpp
   #include <iostream>
   #include <unordered_map>
   ```
2. 自定义数据结构，这是一个简单的数据结构，还不具备对应的哈希函数：

   ```cpp
   struct coord {
       int x;
       int y;
   };
   ```
3. 实现哈希函数是为了能让类型作为键存在，这里先实现比较操作函数：

   ```cpp
   bool operator==(const coord &l, const coord &r)
   {
       return l.x == r.x && l.y == r.y;
   }
   ```
4. 为了使用STL哈希的能力，我们打开了std命名空间，并且创建了一个特化的`std::hash`模板。其使用`using`将特化类型进行别名。

   ```cpp
   namespace std
   {
   template <>
   struct hash<coord>
   {
       using argument_type = coord;
       using result_type = size_t;
   ```
5. 下面要重载该类型的括号表达式。我们只是为`coord`结构体添加数字，这是一个不太理想的哈希方式，不过这里只是展示如何去实现这个函数。一个好的散列函数会尽可能的将值均匀的分布在整个取值范围内，以减少哈希碰撞。

   ```cpp
       result_type operator()(const argument_type &c) const
       {
           return static_cast<result_type>(c.x)
                     + static_cast<result_type>(c.y);
       }
   };
   }
   ```
6. 我们现在可以创建一个新的`std::unordered_map`实例，其能结构`coord`结构体作为键，并且对应任意值。例子中对`std::unordered_map`使用自定义的类型来说，已经很不错了。让我们基于哈希进行实例化，并填充自定义类型的`map`表，并打印这个`map`表：

   ```cpp
   int main()
   {
       std::unordered_map<coord, int> m { 
           { {0, 0}, 1}, 
           { {0, 1}, 2},
           { {2, 1}, 3}
       };
       for (const auto & [key, value] : m) {
           std::cout << "{(" << key.x << ", " << key.y
                    << "): " << value << "} ";
       }
       std::cout << '\n';
   }
   ```
7. 编译运行这个例子，就能看到如下的打印信息：

   ```
   $ ./custom_type_unordered_map
   {(2, 1): 3} {(0, 1): 2} {(0, 0): 1}
   ```

## How it works...

通常实例化一个基于哈希的map表(比如: `std::unordered_map`)时，我们会这样写：

```cpp
std::unordered_map<key_type, value_type> my_unordered_map;
```

编译器为我们创建特化的`std::unordered_map`时，这句话背后隐藏了大量的操作。所以，让我们来看一下其完整的模板类型声明：

```cpp
template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
```

这里第一个和第二个模板类型，我么填写的是`coord`和`int`。另外的三个模板类型是选填的，其会使用已有的标准模板类。这里前两个参数需要我们给定对应的类型。

对于这个例子，`class Hash`模板参数是最有趣的一个：当我们不显式定义任何东西时，其就指向`std::hash<key_type>`。STL已经具有`std::hash`的多种特化类型，比如`std::hash<std::string>`、`std::hash<int>`、`std::hash<unique_ptr>`等等。这些类型中可以选择最优的一种类型类解决对应的问题。

不过，STL不知道如何计算我们自定义类型`coord`的哈希值。所以我们要使用我们定义的类型对哈希模板进行特化。编译器会从`std::hash`特化列表中，找到我们所实现的类型，也就是将自定义类型作为键的类型。

如果新特化一个`std::hash<coord>`类型，并且将其命名成my\_hash\_type，我们可以使用下面的语句来实例化这个类型：

```cpp
std::unordered_map<coord, value_type, my_hash_type> my_unordered_map;
```

这样命名就很直观，可读性好，而且编译器也能从哈希实现列表中找到与之对应的正确的类型。