• ＜C++＞ 哈希表模拟实现STL_unordered_set/map

    哈希表模板参数的控制

    首先需要明确的是，unordered_set是K模型的容器，而unordered_map是KV模型的容器。

    要想只用一份哈希表代码同时封装出K模型和KV模型的容器，我们必定要对哈希表的模板参数进行控制。

    为了与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数的名字改为T。

    template<class K, class T>
class HashTable

    • 1
    • 2

    如果上层使用的是unordered_set容器，那么传入哈希表的模板参数就是key和key。

    template<class K>
class unordered_set {
public:
    //...
private:
    HashTable<K, K> _ht;//传入底层哈希表的是K和K
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    但如果上层使用的是unordered_map容器，那么传入哈希表的模板参数就是key以及key和value构成的键值对。

    template<class K, class V>
class unordered_map {
public:
    //...
private:
    HashTable<K, pair<K, V>> _ht;//传入底层哈希表的是K以及K和V构成的键值对
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    也就是说，哈希表中的模板参数T的类型到底是什么，完全却决于上层所使用容器的种类。

    在这里插入图片描述

    而哈希结点的模板参数也应该由原来的K、V变为T：

    • 上层容器是unordered_set时，传入的T是键值，哈希结点中存储的就是键值。
    • 上层容器是unordered_map时，传入的T是键值对，哈希结点中存储的就是键值对。

    更改模板参数后，哈希结点的定义如下：

    template<class T>
struct HashNode {
    HashNode<T> *_next;
    T _data;

    HashNode(const T &data)
        : _data(data), _next(nullptr) {}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    在哈希映射过程中，我们需要获得元素的键值，然后通过哈希函数计算出对应的哈希地址进行映射。

    现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。

    因此，unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。

    template<class K, class V>
class unordered_map {
public:
    struct MapKeyOft {
        const K &operator()(const pair<K, V> &kv) {
            return kv.first;
        }
    };

private:
    HashTable<K, pair<const K, V>, MapKeyOft> _ht;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    而虽然unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。

    template<class K>
class unordered_set {
public:
    struct SetKeyOfT {
        const K &operator()(const K &key) {
            return key;
        }
    };

private:
    HashTable<K, K, SetKeyOfT> _ht;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    因此，底层哈希表的模板参数现在需要增加一个，用于接收上层容器提供的仿函数。

    template<class K, class T, class KeyOfT>
class HashTable

    • 1
    • 2

    string类型无法取模问题

    经过上面的分析后，我们让哈希表增加了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值。

    但是在我们日常编写的代码中，用字符串去做键值key是非常常见的事，比如我们用unordered_map容器统计水果出现的次数时，就需要用各个水果的名字作为键值。

    而字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址。

    但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是4294967295，而众多字符能构成的字符串的种类却是无限的。

    鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已。

    因此，现在我们需要在哈希表的模板参数中再增加一个仿函数，用于将键值key转换成对应的整型。

    template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable

    • 1
    • 2

    若是上层没有传入该仿函数，我们则使用默认的仿函数，该默认仿函数直接返回键值key即可，但是用字符串作为键值key是比较常见的，因此我们可以针对string类型写一个类模板的特化

    template<class K>
struct HashFunc {
    size_t operator()(const K &key) {
        return key;
    }
};

// 特化模板，传string的话，就走这个
template<>
struct HashFunc<string> {
    size_t operator()(const string &s) {
        size_t hash = 0;
        for (auto ch: s) {
            hash += ch;
            hash *= 31;
        }
        return hash;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    哈希表正向迭代器的实现

    哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中都应该存储哈希表的地址。

    代码：

    //前置声明
template<class K, class T, class KeyOft, class Hash = HashFunc<K>>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOft, class Hash>
struct HashIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyOft, Hash> HT;
    //Ref和Ptr可能是T&和T*，也可能是const T&/const T*，需要创建一个支持普通转换为const的迭代器
    typedef HashIterator<K, T, Ref, Ptr, KeyOft, Hash> Self;
    typedef HashIterator<K, T, T &, T *, KeyOft, Hash> iterator;//正向迭代器

    HashIterator(Node *node, HT *ht)
        : _node(node), _ht(ht) {}

    //正向迭代器实现反向迭代器,不能只靠self，如果self传的就是const迭代器，再加上const就有问题了
    HashIterator(const iterator &it)
        : _node(it._node), _ht(it._ht) {}

    Ref operator*() {
        return _node->_data;
    }

    Ptr operator->() {
        return &_node->_data;
    }

    bool operator!=(const Self &s) {
        return _node != s._node;
    }

    bool operator==(const Self &s) {
        return _node == s._node;
    }

    Self &operator++() {
        if (_node->_next != nullptr) {
            _node = _node->_next;
        } else {
            //找下一个不为空的桶
            KeyOft kot;
            Hash hash;
            // 算出我当前的桶位置
            size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
            ++hashi;
            while (hashi < _ht->_tables.size()) {
                if (_ht->_tables[hashi] != nullptr) {
                    _node = _ht->_tables[hashi];
                    break;
                } else {
                    ++hashi;
                }
            }

            //没有找到的话，返回_node为空
            if (hashi == _ht->_tables.size()) {
                _node = nullptr;
            }
            return *this;
        }
        return *this;
    }
    Node *_node;//迭代器指针
    HT *_ht;    //哈希表，用于定位下一个桶
};

    • 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
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    注意： 哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实现–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。

    正向迭代器实现后，我们需要在哈希表的实现当中进行如下操作：

    1. 进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。
    2. 由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_table，而_table成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。
    3. 将哈希表中查找函数返回的结点指针，改为返回由结点指针和哈希表地址构成的正向迭代器。
    4. 将哈希表中插入函数的返回值类型，改为由正向迭代器类型和布尔类型所构成的键值对。

    完整的HashTable

    #pragma once
#include 
#include 
#include 
#include 
#include 
using namespace std;

template<class K>
struct HashFunc {
    size_t operator()(const K &key) {
        return key;
    }
};

// 特化模板，传string的话，就走这个
template<>
struct HashFunc<string> {
    size_t operator()(const string &s) {
        size_t hash = 0;
        for (auto ch: s) {
            hash += ch;
            hash *= 31;
        }
        return hash;
    }
};

template<class T>
struct HashNode {
    HashNode<T> *_next;
    T _data;

    HashNode(const T &data)
        : _data(data), _next(nullptr) {}
};


//前置声明
template<class K, class T, class KeyOft, class Hash = HashFunc<K>>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOft, class Hash>
struct HashIterator {
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyOft, Hash> HT;
    //Ref和Ptr可能是T&和T*，也可能是const T&/const T*，需要创建一个支持普通转换为const的迭代器
    typedef HashIterator<K, T, Ref, Ptr, KeyOft, Hash> Self;
    typedef HashIterator<K, T, T &, T *, KeyOft, Hash> iterator;//正向迭代器

    HashIterator(Node *node, HT *ht)
        : _node(node), _ht(ht) {}

    //正向迭代器实现反向迭代器,不能只靠self，如果self传的就是const迭代器，再加上const就有问题了
    HashIterator(const iterator &it)
        : _node(it._node), _ht(it._ht) {}

    Ref operator*() {
        return _node->_data;
    }

    Ptr operator->() {
        return &_node->_data;
    }

    bool operator!=(const Self &s) {
        return _node != s._node;
    }

    bool operator==(const Self &s) {
        return _node == s._node;
    }

    Self &operator++() {
        if (_node->_next != nullptr) {
            _node = _node->_next;
        } else {
            //找下一个不为空的桶
            KeyOft kot;
            Hash hash;
            // 算出我当前的桶位置
            size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
            ++hashi;
            while (hashi < _ht->_tables.size()) {
                if (_ht->_tables[hashi] != nullptr) {
                    _node = _ht->_tables[hashi];
                    break;
                } else {
                    ++hashi;
                }
            }

            //没有找到的话，返回_node为空
            if (hashi == _ht->_tables.size()) {
                _node = nullptr;
            }
            return *this;
        }
        return *this;
    }
    Node *_node;//迭代器指针
    HT *_ht;    //哈希表，用于定位下一个桶
};

template<class K, class T, class KeyOft, class Hash>// Hash用于将key转换成可以取模的类型
class HashTable {
public:
    typedef HashNode<T> Node;
    typedef HashIterator<K, T, T &, T *, KeyOft, Hash> iterator;
    typedef HashIterator<K, T, const T &, const T *, KeyOft, Hash> const_iterator;

    template<class K1, class T1, class Ref1, class Ptr1, class KeyOft1, class Hash1>
    friend struct HashIterator;//用于迭代器访问HashTable中的private成员变量，即_tables、

public:
    ~HashTable() {
        for (auto &cur: this->_tables) {
            while (cur) {
                Node *next = cur->_next;
                delete cur;
                cur = next;
            }
            cur = nullptr;
        }
    }

    iterator begin() {
        Node *cur = nullptr;
        for (size_t i = 0; i < _tables.size(); i++) {
            cur = _tables[i];
            if (cur != nullptr) {
                break;
            }
        }
        return iterator(cur, this);
    }

    iterator end() {
        return iterator(nullptr, this);
    }

    const_iterator begin() const {
        Node *cur = nullptr;
        for (size_t i = 0; i < _tables.size(); i++) {
            cur = _tables[i];
            if (cur != nullptr) {
                break;
            }
        }
        return const_iterator(cur, this);
    }

    const_iterator end() const {
        return const_iterator(nullptr, this);
    }

    //查找Key也是K类型
    iterator Find(const K &key) {
        if (this->_tables.size() == 0) {
            return iterator(nullptr, this);
        }

        KeyOft kot;//模板参数，用来区分是kv，还是v由上层map、set传模板参数过来(通过仿函数实现)
        Hash hash;
        size_t hashi = hash(key) % this->_tables.size();
        Node *cur = this->_tables[hashi];
        while (cur) {
            if (kot(cur->_data) == key) {
                return iterator(cur, this);
            }
            cur = cur->_next;
        }
        return iterator(nullptr, this);
    }

    //删除的值key为K类型
    bool Erase(const K &key) {
        Hash hash;
        KeyOft kot;
        size_t hashi = hash(key) % this->_tables.size();
        Node *prev = nullptr;
        Node *cur = this->_tables[hashi];
        while (cur) {
            if (kot(cur->_data) == key) {
                if (prev == nullptr) {
                    this->_tables[hashi] = cur->_next;
                } else {
                    prev->_next = cur->_next;
                }
                delete cur;
                return true;
            } else {
                prev = cur;
                cur = cur->_next;
            }
        }
        return false;
    }

    // 扩容优化，使用素数扩容
    size_t GetNextPrime(size_t prime) {
        // SGI
        static const int _stl_num_primes = 28;
        static const uint64_t _stl_prime_list[_stl_num_primes] = {
                53, 97, 193, 389, 769, 1543,
                3079, 6151, 12289, 24593, 49157, 98317,
                196613, 393241, 786433, 1572869, 3145739, 6291469,
                12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
                805306457, 1610612741, 3221225473, 4294967291};

        size_t i = 0;
        for (; i < _stl_num_primes; ++i) {
            if (_stl_prime_list[i] > prime)
                return _stl_prime_list[i];
        }

        return _stl_prime_list[_stl_num_primes - 1];
    }

    //插入的类型是T类型，可能是K可能是pair 通过模板参数传过来
    pair<iterator, bool> Insert(const T &data) {
        Hash hash;// 仿函数用于不能取模的值
        KeyOft kot;
        // 已经有这个数，就不用插入了
        iterator it = Find(kot(data));
        //如果it不是end()，说明找到了数，就不用插入，返回迭代器和false
        if (it != end()) {
            return make_pair(it, false);
        }


        // 负载因子 == 1时扩容
        if (this->n == this->_tables.size()) {
            // size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            size_t newsize = this->GetNextPrime(_tables.size());
            vector<Node *> newtables(newsize, nullptr);
            for (auto &cur: this->_tables) {// cur是Node*
                while (cur) {
                    // 保存下一个
                    Node *next = cur->_next;
                    // 头插到新表
                    size_t hashi = hash(kot(cur->_data)) % newtables.size();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;

                    cur = next;
                }
            }
            _tables.swap(newtables);
        }

        size_t hashi = hash(kot(data)) % this->_tables.size();
        // 头插
        Node *newnode = new Node(data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        this->n++;

        //插入成功返回，通过newnode，和this构造迭代器，返回true。
        return make_pair(iterator(newnode, this), true);
    }

    // 获取哈希表索引最大长度(哈希桶长度)
    size_t MaxBucketSize() {
        size_t max = 0;
        for (int i = 0; i < _tables.size(); ++i) {
            auto cur = _tables[i];
            size_t size = 0;
            while (cur) {
                ++size;
                cur = cur->_next;
            }

            printf("[%d]->%d\n", i, size);

            if (size > max) {
                max = size;
            }
            if (max == 5121) {
                printf("%d", i);
                break;
            }
        }

        return max;
    }

private:
    vector<Node *> _tables;
    size_t n = 0;// 存储有效数据的个数
};

    • 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
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291

    封装unordered_set的代码

    #pragma once
#include "HashTable.h"

template<class K, class Hash = HashFunc<K>>
class unordered_set {
public:
    struct SetKeyOfT {
        const K &operator()(const K &key) {
            return key;
        }
    };

public:
    typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
    typedef typename HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;


    iterator begin() {
        return _ht.begin();
    }

    iterator end() {
        return _ht.end();
    }

    const_iterator begin() const {
        return _ht.begin();
    }

    const_iterator end() const {
        return _ht.end();
    }

    //这里的pair中的iterator是const类型的，而Insert返回的是普通迭代器
    pair<iterator, bool> insert(const K &key) {
        return _ht.Insert(key);
    }

    iterator find(const K &key) {
        return _ht.Find(key);
    }

    bool erase(const K &key) {
        return _ht.Erase(key);
    }

private:
    HashTable<K, K, SetKeyOfT, Hash> _ht;
};

    • 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
    • 45
    • 46
    • 47
    • 48
    • 49

    封装unordered_map的代码

    #pragma once

#include "HashTable.h"
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
public:
    struct MapKeyOft {
        const K &operator()(const pair<K, V> &kv) {
            return kv.first;
        }
    };

    //typename 告诉编译器引入的是一个类型，而不是成员
    typedef typename HashTable<K, pair<const K, V>, MapKeyOft, Hash>::iterator iterator;
    typedef typename HashTable<K, pair<const K, V>, MapKeyOft, Hash>::const_iterator const_iterator;

    iterator begin() {
        return _ht.begin();
    }

    iterator end() {
        return _ht.end();
    }

    const_iterator begin() const {
        return _ht.begin();
    }

    const_iterator end() const {
        return _ht.end();
    }

    pair<iterator, bool> insert(const pair<K, V> kv) {
        return _ht.Insert(kv);
    }

    V &operator[](const K &key) {
        pair<iterator, bool> ret = insert(make_pair(key, V()));
        return ret.first->second;
    }

    iterator find(const K &key) {
        return _ht.Find(key);
    }

    bool erase(const K &key) {
        return _ht.Erase(key);
    }

private:
    HashTable<K, pair<const K, V>, MapKeyOft, Hash> _ht;
};

    • 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
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    测试

    #include "unordered_map.h"
#include "unordered_set.h"
#include 
class Date {
    friend struct HashDate;

public:
    Date(int year = 1900, int month = 1, int day = 1)
        : _year(year), _month(month), _day(day) {}

    bool operator<(const Date &d) const {
        return (_year < d._year) ||
               (_year == d._year && _month < d._month) ||
               (_year == d._year && _month == d._month && _day < d._day);
    }

    bool operator>(const Date &d) const {
        return (_year > d._year) ||
               (_year == d._year && _month > d._month) ||
               (_year == d._year && _month == d._month && _day > d._day);
    }

    bool operator==(const Date &d) const {
        return _year == d._year && _month == d._month && _day == d._day;
    }

    friend ostream &operator<<(ostream &_cout, const Date &d);

private:
    int _year;
    int _month;
    int _day;
};

ostream &operator<<(ostream &_cout, const Date &d) {
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}

//自定义Hash，模板最后一个参数，传自定义类型的话，需要自己写
struct HashDate {
    size_t operator()(const Date &d) {
        size_t hash = 0;
        hash += d._year;
        hash *= 31;

        hash += d._month;
        hash *= 31;

        hash += d._day;
        hash *= 31;

        return hash;
    }
};

struct unordered_map_Test {
    static void unordered_map_Test1() {
        unordered_map<int, int> mp;
        mp.insert(make_pair(1, 1));
        mp.insert(make_pair(2, 2));
        mp.insert(make_pair(3, 3));

        unordered_map<int, int>::iterator it = mp.begin();
        while (it != mp.end()) {
            cout << it->first << " " << it->second << endl;
            ++it;
        }
        cout << endl;
    }

    static void unordered_map_Test2() {
        string arr[] = {"西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨"};
        unordered_map<string, int> countMap;
        for (auto &e: arr) {
            countMap[e]++;
        }

        for (auto &kv: countMap) {
            cout << kv.first << "" << kv.second << endl;
        }
    }

    static void unordered_map_Test3() {
        Date d1(2023, 3, 13);
        Date d2(2023, 3, 13);
        Date d3(2023, 3, 12);
        Date d4(2023, 3, 11);
        Date d5(2023, 3, 12);
        Date d6(2023, 3, 13);

        Date a[] = {d1, d2, d3, d4, d5, d6};

        unordered_map<Date, int, HashDate> countMap;
        for (auto e: a) {
            countMap[e]++;
        }

        for (auto &kv: countMap) {
            cout << kv.first << ":" << kv.second << endl;
        }
    }
};

struct unordered_set_Test {
    static void unordered_set_Test1() {
        unordered_set<int> s;
        s.insert(1);
        s.insert(3);
        s.insert(2);
        s.insert(7);
        s.insert(8);

        unordered_set<int>::iterator it = s.begin();
        while (it != s.end()) {
            cout << *it << " ";
            //(*it) = 1;
            ++it;
        }
        cout << endl;
    }
};

int main() {
    unordered_set_Test::unordered_set_Test1();
    unordered_map_Test::unordered_map_Test1();
    unordered_map_Test::unordered_map_Test2();
    unordered_map_Test::unordered_map_Test3();
    return 0;
}

    • 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
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
  • 相关阅读:
    笛卡尔积现象
    力扣 1662. 检查两个字符串数组是否相等
    设计模式 - 代理模式
    UDP 协议详解
    Kibana--配置大全
    react脚手架创建命令教程
    SpringBoot配置文件
    【JavaScript复习七】内置对象string截取字符串及其他方法
    Python算法图解——递归（一）：打印从1循环到10
    图的深度优先遍历
  • 原文地址：https://blog.csdn.net/ikun66666/article/details/133472155