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所必须的头文件

    1. #include <iostream>
    2. #include <unordered_map>

  2. 自定义数据结构，这是一个简单的数据结构，还不具备对应的哈希函数：

    1. struct coord {
    2.     int x;
    3.     int y;
    4. };

  3. 实现哈希函数是为了能让类型作为键存在，这里先实现比较操作函数：

    1. bool operator==(const coord &l, const coord &r)
    2. {
    3.     return l.x == r.x && l.y == r.y;
    4. }

  4. 为了使用STL哈希的能力，我们打开了std命名空间，并且创建了一个特化的std::hash模板。其使用using将特化类型进行别名。

    1. namespace std
    2. {
    3. template <>
    4. struct hash<coord>
    5. {
    6.     using argument_type = coord;
    7.     using result_type = size_t;

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

    1.     result_type operator()(const argument_type &c) const
    2.     {
    3.         return static_cast<result_type>(c.x)
    4.                   + static_cast<result_type>(c.y);
    5.     }
    6. };
    7. }

  6. 我们现在可以创建一个新的std::unordered_map实例，其能结构coord结构体作为键，并且对应任意值。例子中对std::unordered_map使用自定义的类型来说，已经很不错了。让我们基于哈希进行实例化，并填充自定义类型的map表，并打印这个map表：

    1. int main()
    2. {
    3.     std::unordered_map<coord, int> m { 
    4.         { {0, 0}, 1}, 
    5.         { {0, 1}, 2},
    6.         { {2, 1}, 3}
    7.     };
    8.     for (const auto & [key, value] : m) {
    9.         std::cout << "{(" << key.x << ", " << key.y
    10.                  << "): " << value << "} ";
    11.     }
    12.     std::cout << '\n';
    13. }

  7. 编译运行这个例子，就能看到如下的打印信息：

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

How it works…

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

  1. std::unordered_map<key_type, value_type> my_unordered_map;

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

  1. template<
  2.     class Key,
  3.     class T,
  4.     class Hash = std::hash<Key>,
  5.     class KeyEqual = std::equal_to<Key>,
  6.     class Allocator = std::allocator< std::pair<const Key, T> >
  7. > 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，我们可以使用下面的语句来实例化这个类型：

  1. std::unordered_map<coord, value_type, my_hash_type> my_unordered_map;

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