C++程序设计：自定义类作为Key的unordered_map编程技法

如何用自定义类型作为unordered_map的key呢？

在上一节，我们讲到：这是自定义类型作为map的Key的编程技法与原理。我们这里先只谈技法，原理下次讲哈希表再去探讨。

分析作为unordered_map的Key的条件

联想标记数组算法，其实标记数组就是一种哈希，只是那是一种以下标（非负整型作为Key）的哈希表。unordered_map的底层实现就是哈希表实现的，这个可以联想类比标记数组！

回顾标记数组的做法！在获得标记下标的时候，也就是知道Key的时候，我们要对数组中同为Key下标的数组元素进行操作。其实哈希表也差不多的，那么大家思考，什么样的类才能满足这个操作呢？

首先，需要到数组中查找是否已经标记了这个元素，如果没有加上标记，如果有就对标记的值（也就是Key-Value的Value）进行访问。那么，我们的类就需要能够支持找到相同Key的方法，也就是“判等”方法，这通过重载运算符==实现！其实和Java的重写equal和hashcode方法差不多。

光有判等方法不够，为了提高效率，我们可以先采用哈希算法，得到对应的哈希值。如果哈希值相同再判等，为什么这样呢？是为了避免哈希碰撞！

实例编程技法

还是上一篇博客的例子：

给定N个学生，用unordered_map存储，并且给学生成绩进行打分。实现的程序是：

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Student {
    friend ostream& operator<<(ostream& out, const Student& res);
private:
    string name;
    int score;
public:
    Student(string name_, int score_) : name(name_), score(score_) {

    }

    bool operator==(const Student& obj) const {
        return name == obj.name && score == obj.score;
    }

    string getName() const {
        return name;
    }

    int getScore() const {
        return score;
    }
};

ostream& operator<<(ostream& out, const Student& res) {
    out << "Name : " << res.name << ",\tscore : " << res.score;
    return out;
}

class hashFunctor {
public:
    size_t operator()(const Student& obj) const {
        return hash<string>()(obj.getName()) ^ hash<int>()(obj.getScore());
    }
};

char getRank(int score) {
    if (score >= 90)
        return ‘A‘;
    else if (score >= 60)
        return ‘B‘;
    else
        return ‘C‘;
}

int main() {
    unordered_map<Student, char, hashFunctor> umpStu;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string curName;
        int curScore;
        cin >> curName >> curScore;
        umpStu[Student(curName, curScore)] = getRank(curScore);
    }
    for (auto it : umpStu) {
        cout << it.first << "\trank : " << it.second << endl;
    }
    return 0;
}

输出结果是：

Name : jiangjy, score : 98      rank : A
Name : zhangwj, score : 67      rank : B
Name : zuozy,   score : 98      rank : A
Name : lifl,    score : 86      rank : B
Name : jiangzl, score : 48      rank : C

大家可以看到，这里是无序的状态了！所以unordered_map又叫无序关联容器。

编程技法总结

（一）自定义类型作为map的Key

需要重载小于运算符

（二）自定义类型作为unordered_map的Key

需要重载==运算符

需要一个仿函数（只重载函数调用运算符() 的类）作为参数构造unordered_map对象