unordered_map自定义类重写hash函数对象与比较函数对象_c++ unordered map 自定义哈希函数

在一些无序查找问题中，c++一般采用STL中的unordered_map作为存储结构，底层原理主要是以哈希桶的方式存储数据，使得查找时间复杂度接近常数级，原理不细说，这里主要讲使用unordered_map存储自定义类时，需要我们自定义key的hash函数对象，并自定义比较函数对象。

对于unordered_map官方定义：

template<class Key,
    class T,
    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

其中参数 Key 表示键的类型， T 表示键映射到哈希表中值的类型，Hash 是接受一个参数，且类型与 Key 兼容的函数对象，返回值为 T 类型，Pred 为 接受两个参数，且类型与 Key 兼容的函数对象，返回值为 bool。需要注意的是，这两个函数对象的参数都为 const 引用，函数都是 const 。

举例说明：自定义两个类，article_id 与 article，分别作为键与值

类 article_id

// 类article_id
struct article_id
{
    friend std::ostream & operator<<(std::ostream &os, const article_id &a);
    std::string brand;
    int id;
    article_id(const std::string &b, int id) : brand(b), id(id) { }
};

重载 << 运算符

std::ostream & operator<<(std::ostream &os, const article_id &a)
{
    os << "(" << a.brand << ")" << a.id;
    return os;
}

 类 article

// 类 article
class article
{
    friend std::ostream & operator << (std::ostream &os, const article &a);
public:
    article(const std::string &b, const std::string &m, const std::string &d) : 
        brand(b), model(m), description(d) { }
 
private:
    std::string brand;
    std::string model;
    std::string description;
};

重载 << 运算符

std::ostream & operator << (std::ostream &os, const article &a)
{
    os << "Brand: " << a.brand << "; Model: " << a.model
              << "; Description: " << a.description;
    return os;
}

自定义 hash 函数对象

template <class T>
class article_hash
{
public:
    long operator()(const article_id &x) const
    {
        std::hash<T> z;
        return z(x.brand) * 100 + x.id;
    }
};

自定义比较函数对象

class article_equal_to
{
public:
    bool operator () (const article_id &a, const article_id &b) const
    {
        return a.brand == b.brand && a.id == b.id;
    }
};

函数对象，其实就是重载了operator()的 类，这样的类统称为函数对象类，它的使用形式像函数调用，实际也执行了函数调用。

main函数：

template <class T>
void show(const T & x)
{
    for (auto &i : x)
    {
        std::cout << i.first << "; " << i.second << std::endl;
    }
}
 
int main()
{
    std::unordered_map<article_id, article, article_hash<std::string>, article_equal_to> x;
    x.insert(std::make_pair(article_id("acme", 1), article("acme", "tv", "Acme TV")));
    x.insert(std::make_pair(article_id("foo", 4), article("foo", "phone", "fooPhone")));
    show(x);
    return 0;
}

PS：除了使用自定义函数对象的方法，我们也可以使用直接自定义函数的方式

1. 自定义 hash 函数
2. 自定义比较函数
3. 像unordered_map<>中传入函数指针，可以使用c++11 decltype特性，

   std::unordered_map<article_id, article, decltype(hasher) *, decltype(equal_to) *> x;
   

PS again: 上文中的例子是参考一个大佬的一篇文章，只是找不到网址了，以后找到连接会更新到后面。