1 std::unordered_map中使用结构体或者vector等复杂的数据结构作为Key值

1.1 std::vector作为Key

C++11中引入了unordered_set和unordered_map，其内部数据结构实现没有使用map和set中的红黑树，而是使用的哈希表。如果我们在unordered_set和unordered_map使用比较复杂的数据结构，比如结构体，类，或者类似于std::vector<int>这种作为Key，那么此时我们需要自定义Key的hash值，不然会出现编译错误，比如以下代码

#include <iostream>
#include <unordered_map>
#include <vector>


int main()
{
    std::unordered_map<std::vector<int>, std::string> test;

    return 0;
}

在VS中进行编译会出现以下的编译错误

错误C2280“std::_Uhash_compare<_Kty,_Hasher,_Keyeq>::_Uhash_compare(const std::_Uhash_compare<_Kty,_Hasher,_Keyeq> &)”: 尝试引用已删除的函数 C++BasicTest    C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\unordered_map   50

在上述代码中，我们将std::vector<int>作为std::unorder_map的Key值，而这种复杂的结构体我们需要自定义std::vector<int>这个Key所使用的Hash，我们可以对上述代码进行如下修改

#include <iostream>
#include <unordered_map>
#include <vector>

struct Hash
{
    std::size_t operator()(const std::vector<int>& prefix) const {
        size_t hash_code = 0;

        for (int id : prefix) {
            hash_code = id + 77 * hash_code;
        }
        return hash_code;
    }
};

int main()
{
    std::unordered_map<std::vector<int>, std::string, Hash> test;

    return 0;
}

这个时候再对上述代码进行编译就不会出现编译错误了。

1.2 struct作为Key

同样的，我们也可以将结构体作为std::unorder_map的Key，我们也需要定义strcut的Hash值，一个简单的示例代码如下，

#include <iostream>
#include <unordered_map>
#include <vector>

struct Point {
    int point_id;
    float x;
    float y;
    float z;
};

struct PointHash
{
    std::size_t operator()(const Point& point) const {
        return point.point_id + (int)point.x * 3 + (int)point.y * 5 + (int)point.z * 7;
    }
};

int main()
{
    std::unordered_map<std::vector<int>, std::string, PointHash> test;

    return 0;
}