My Personal Blog
0%

unordered_map使用自定义键类型

Posted on Edited on

unordered_map定义(C++11)

参考博客

1
2
3
4
5
6
7
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;

Key代表键值（key），T是根据哈希函数得到的值（value），Hash是哈希函数的函数对象，KeyEqual是等比函数的函数对象，通过"=="来判断两个key是否相等。
想实现自定义的键类型，必须实现hash函数和等比函数。

实现

  • 法一：利用std::function中的默认hash函数std::hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <functional>
#include <unordered_map>

class mypair
{
public:
    char first;
    char second;

    mypair(char a, char b)
    {
        if( a < b)
        {
            first = a;
            second = b;
        }
        else
        {
            first = b;
            second = a;
        }
    }

    bool operator==(const mypair& rhs)
    {
    return rhs.first == this->first && rhs.second == this->second;
    }
};

static size_t mypair_hash(const mypair& tmp)
{
    return hash<char>()(tmp.first) ^ hash<char>()(tmp.second);
}

int main()
{
    //ERRO: unordered_map<mypair, int, decltype(&mypair_hash)> ids;
    //ERRO: unordered_map<mypair, int, mypair_hash> ids(100, mypair_hash );
    //OK: unordered_map<mypair, int, decltype(&mypair_hash)> ids(100, mypair_hash );
    unordered_map<mypair, int, decltype(&mypair_hash)> memo(20/*, mypair_hash*/);  //在这里decltype后面必须要使用引用
    /*
     * code
     */
}

Note:

1) decltype(exp)推导的内容如果是一个左值，那么 decltype(exp) 的类型就是 exp 的引用。在这里mypair_hash是一个函数，如果是自动推导得到的是函数的返回值，不是引用类型，运行时编译器会报错，在hashtable_policy.h中：
field 'std::__detail::_Hashtable_ebo_helper<1, long long unsigned int(const mypair&), false>::_M_tp' invalidly declared function type

2) 参考的博客中说memo初始化时必须传入mypair_hash构造函数，但是我尝试不传入发现也是可以编译通过和运行的。

  • 法二：重载operator()类，打包哈希函数变成函数对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class mypair
{
public:
    char first;
    char second;

    mypair(const char& a, const char& b)
    {
        first = a;
        second = b;
    }

    bool operator==(const mypair& rhs) const
    {
    return rhs.first == first && rhs.second == second;
    }

};

struct hashname
{
    size_t operator()(const mypair& tmp) const
    {
        return (hash<char>()(tmp.first)) ^ (hash<char>()(tmp.second));
    }
};

int main()
{
    unordered_map<mypair, int, hashname> memo(20);
    /*
     * code
     */
}

可以直接运行通过，没有什么坑。