C++修炼：unordered_map和unordered_set的利用和封装

        Hello各人好！很高兴我们又见面啦！给生存添点passion，开始今天的编程之路！
  

  我的博客：<但凡.
  我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》
  接待点赞，关注！
          这一期我们来讲解并模拟实现unordered_map和unordered_set。有了前面的铺垫，这一篇就要相对简单很多了。
 
1、unordered_set和unordered_map的利用

        在C++标准模板库(STL)中，unordered_set和unordered_map是两种非常紧张的关联容器，它们基于哈希表实现，提供了高效的查找、插入和删除操作。本文将详细讲解这两种容器的特性、用法、内部实现原理。
      1.1、unordered_set的利用

        unordered_set是一个存储唯一元素的容器，此中每个元素的值同时也是它的键。
        我们把unordered_set的利用快速过一遍。因为在日常利用中，unordered_set的利用和set的利用很相似。接口都是雷同的。

1. #include <unordered_set>
2. #include <iostream>
4. int main() {
5.     // 创建unordered_set
6.     std::unordered_set<int> numbers = {1, 2, 3, 4, 5};
7.    
8.     // 插入元素
9.     numbers.insert(6);
10.     numbers.emplace(7);  // 更高效的插入方式
11.     //下两篇会详细讲解emplace接口
12.    
13.     // 查找元素
14.     if (numbers.find(3) != numbers.end()) {
15.         std::cout << "3 found in the set\n";
16.     }
17.    
18.     // 删除元素
19.     numbers.erase(4);
20.    
21.     // 遍历元素
22.     for (const auto& num : numbers) {
23.         std::cout << num << " ";
24.     }
25.     std::cout << "\n";
26.    
27.     // 获取大小
28.     std::cout << "Size: " << numbers.size() << "\n";
29.    
30.     return 0;
31. }

复制代码

         unordered_set的主要特性：
                唯一性：容器中不允许有重复的元素
                无序性：元素不以任何特定顺序存储
                哈希实现：基于哈希表实现，均匀环境下提供O(1)的查找复杂度
                动态大小：容器可以根据必要动态扩展或收缩
        我们可以把unordered_set理解成不能排序的set，而且unordered_set的插入，删除，查找均匀时间复杂度都是O(1)，效率比set要高。
         1.2、unordered_map的利用

        unordered_map是存储键值对的关联容器，此中每个键都是唯一的。与map不同unordered_map中的元素不以任何特定顺序排序。
        操作我们也不细讲了，因为常用接口和map的接口都差不多。

1. #include <unordered_map>
2. #include <iostream>
3. #include <string>
5. int main() {
6.     // 创建unordered_map
7.     std::unordered_map<std::string, int> word_counts = {
8.         {"apple", 5},
9.         {"banana", 3}
10.     };
11.    
12.     // 插入元素
13.     word_counts.insert({"orange", 2});
14.     word_counts["pear"] = 4;  // 使用下标操作符插入
15.    
16.     // 访问元素
17.     std::cout << "apple count: " << word_counts["apple"] << "\n";
18.    
19.     // 查找元素
20.     auto it = word_counts.find("banana");
21.     if (it != word_counts.end()) {
22.         std::cout << "banana count: " << it->second << "\n";
23.     }
24.    
25.     // 删除元素
26.     word_counts.erase("orange");
27.    
28.     // 遍历元素
29.     for (const auto& pair : word_counts) {
30.         std::cout << pair.first << ": " << pair.second << "\n";
31.     }
32.    
33.     // 获取大小
34.     std::cout << "Size: " << word_counts.size() << "\n";
35.    
36.     return 0;
37. }

复制代码

        unordered_map的主要特性：
                键唯一性：每个键只能在容器中出现一次
                无序性：键值对不以任何特定顺序存储
                哈希实现：基于哈希表实现，均匀环境下提供O(1)的访问复杂度
                快速访问：通过键可以直接访问对应的值
               假如我们想要支持自定义范例的比较和存储，必要让自定义范例支持哈希映射和==的比较。unordered_map和unordered_set同理。

1. #include<iostream>
2. #include<unordered_map>
3. #include<unordered_set>
4. using namespace std;
6. struct node
7. {
8.         int _a;
9.         int _b;
11.         bool operator==(const node& x) const
12.         {
13.                 return (_a == x._a) && (_b == x._b);
14.         }
15. };
17. class A
18. {
19. public:
20.         //需要注意仿函数的重载()一定是public:
21.         size_t operator()(const node& x) const
22.         {
23.                 int ret = x._a;
24.                 ret *= 131;
25.                 ret += x._b;
26.                 ret *= 131;
28.                 return ret;
29.         }
30. };
32. int main()
33. {
34.         unordered_set<node, A> s;
35.         unordered_map<node, string, A> mp;
37.         s.insert({ 1,1 });
38.         s.insert({ 2,2 });
39.         node x = { 1,1 };
40.         mp[{1, 2}] = "11";
41.         node x1 = { 2,3 };
42.         mp.insert({x1, "ss"});//传入pair(key,value)
44.         return 0;
45. }

复制代码

 2、unordered_map和unordered_set的封装

        基于我们上节课实现的哈希表，我们对unordered_set和unordered_map进行封装。必要注意的是我们利用的是链地址法进行封装，因为stl中的unordered_map和unordered_set也是链地址法。
        2.1、KeyOfT

        上期我们的哈希表查找key值，我们是通过直接访问kv.first来实现的。但是由于封装的时间我们想让unordered_set和unordered_map用同一个哈希表，以是我们对哈希表的模板参数中传入KeyOfT，然后在访问key值时利用KeyOfT的方式:

1. template<class K,class T,class KeyOfT,class Hash>

复制代码

        这个KeyOfT是跟着unordered_set和unordered_map的时间写的，以是等我们进一步封装的时间再去实现KeyOfT。 
         2.2、迭代器

        我们对上一次的哈希表进行升级，是他支持迭代器：

1. template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
2. struct HTIterator
3. {
4.         typedef HashNode<T> Node;
5.         typedef HashTable<K, T, KeyOfT, Hash> HT;
6.         typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
8.         Node* _node;
9.         const HT* _pht;
10.         HTIterator(Node* node,const HT* pht)
11.                 :_node(node),
12.                 _pht(pht)
13.         {}
15.         Self& operator++()
16.         {
17.                 if (_node->_next)
18.                 {
19.                         _node = _node->_next;
20.                 }
21.                 else
22.                 {
23.                         //根据哈希表找到下一个下挂节点的地方
24.                         KeyOfT kot;
25.                         Hash hs;
26.                         size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
27.                         hashi++;
28.                         while (hashi < _pht->_tables.size())
29.                         {
30.                                 if (_pht->_tables[hashi])
31.                                 {
32.                                         _node = _pht->_tables[hashi];
33.                                         break;
34.                                 }
35.                                 //这个地方和线性探测不一样，不要让他成环
36.                                 ++hashi;
37.                         }
39.                         if (hashi == _pht->_tables.size())
40.                         {
41.                                 _node = nullptr;
42.                                 //如果跳出循环发现这个位置根本不存在说明没有下一个节点了
43.                         }
45.                         //注意这是前置++
46.                         return *this;
47.                 }
49.         }
50.         Ref operator*()
51.         {
52.                 return _node->_data;
53.         }
55.         Ptr operator->()
56.         {
57.                 return &_node->_data;
58.         }
60.         bool operator!=(const Self& s) const
61.         {
62.                 return  _node != s._node;
63.         }
65.         bool operator==(const Self& s) const
66.         {
67.                 return _node == s._node;//比较地址
68.         }
69. };

复制代码

        我们模板参数有6个，K,T是存储范例不多说了，和我们哈希表的一样，ref是引用，ptr是指针，各人应该也都知道，keyOfT是提取key值，hash是哈希映射函数。
        对于operator++，首先假如这个节点是链中的一个节点，而且他还有下一个节点，那我们直接加加就可以了。假如没有，那么我们就去找下一个链。首先我们通过哈希哈希函数找到当前节点在的链子，记作hashi。然后把hashi加加跳过当前的链子，之后一直往后遍历知道找到下一个链子的位置。
        接下来我们让哈希表支持迭代器。

1.         template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
2.         friend struct HTIterator;
4.         typedef HashNode<T> Node;
5. public:
6.         typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
7.         typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
9.         Iterator Begin()
10.         {
11.                 if (_n == 0)
12.                         return End();
14.                 for (size_t i = 0;i < _tables.size();i++)
15.                 {
16.                         if (_tables[i])
17.                         {
18.                                 return Iterator(_tables[i],this);
19.                         }
20.                 }
21.                 return End();
22.         }
23.         Iterator End()
24.         {
25.                 return Iterator(nullptr,this);
26.         }
28.         ConstIterator Begin() const
29.         {
30.                 if (_n == 0)
31.                         return End();
33.                 for (size_t i = 0;i < _tables.size();i++)
34.                 {
35.                         if (_tables[i])
36.                         {
37.                                 return ConstIterator(_tables[i], this);
38.                         }
39.                 }
40.                 return End();
41.         }
43.         ConstIterator End() const
44.         {
45.                 return ConstIterator(nullptr, this);
46.         }

复制代码

        因为我们在写迭代器类的时间用了hashTable中的私有成员变量，以是要在hashTable中对迭代器类进行友元声明。 
        对于begin来说，我们就通过遍历，找到第一个出现值的位置就行了，假如走到最后了都没出现值，那阐明我们当前哈希表是空的，直接返回end(),而end()现实上是返回一个nullptr构造的迭代器。
      2.3、插入

        我们对插入操作改造升级，使他和源码的返回值雷同：

1. pair<Iterator, bool> Insert(const T& data)
2. {
3.         KeyOfT kot;
4.         Iterator it = Find(kot(data));
5.         if (it != End())
6.                 return { it,false };
8.         Hash hs;
10.         if (_n == _tables.size())
11.         {
12.                 //扩容
13.                 //HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1));
15.                  遍历旧表，将旧表的数据全部重新映射到新表
16.                 //for (size_t i = 0; i < _tables.size(); i++)
17.                 //{
18.                 //        Node* cur = _tables[i];
19.                 //        while (cur)
20.                 //        {
21.                 //                newht.Insert(cur->_kv);
22.                 //                cur = cur->_next;
23.                 //        }
24.                 //}
25.                 //_tables.swap(newht._tables);
26.                 //我们不采用上面的方式，因为上面的方式每个节点都得拷贝一次
27.                 vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
29.                 for (size_t i = 0;i < _tables.size();i++)
30.                 {
31.                         Node* cur = _tables[i];
32.                         while (cur)
33.                         {
34.                                 Node* next = cur->_next;
35.                                 size_t hashi = hs(kot(cur->_data)) % newtables.size();
36.                                 cur->_next = newtables[hashi];
37.                                 newtables[hashi] = cur;
39.                                 cur = next;
40.                         }
41.                         _tables[i] = nullptr;
43.                 }
44.                 _tables.swap(newtables);//浅交换
45.         }
47.         size_t hashi = hs(kot(data)) % _tables.size();
49.         Node* newnode = new Node(data);
50.         newnode->_next = _tables[hashi];
51.         _tables[hashi] = newnode;
52.         ++_n;
54.         return { Iterator(newnode,this),true };
55. }

复制代码

        这段内容没什么难点，各人看看就好了。 
         2.4、unordered_map的封装

        现在我们新建一个头文件unordered_map.h，然后写一下unordered_map的类：

1. #include"HashTable.h"
3. template<class K,class V,class hash=HashFunc<K>>
4. class unordered_map
5. {
6.         struct MapKeyOfT
7.         {
8.                 const K& operator()(const pair<K, V>& kv) const //仿函数记得加const
9.                 {
10.                         return kv.first;
11.                 }
12.         };
13. public:
14.         typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, hash>::Iterator iterator;
15.         typedef typename hash_bucket::HashTable< K, pair<const K, V>, MapKeyOfT, hash>::ConstIterator const_iterator;
17.         iterator begin()
18.         {
19.                 return _ht.Begin();
20.         }
21.         iterator end()
22.         {
23.                 return _ht.End();
24.         }
25.         const_iterator begin() const
26.         {
27.                 return _ht.Begin();
28.         }
29.         const_iterator end() const
30.         {
31.                 return _ht.End();
32.         }
34.         pair<iterator, bool> insert(const pair<K, V>& kv)
35.         {
36.                 return _ht.Insert(kv);
37.         }
39.         iterator find(const K& key)
40.         {
41.                 return _ht.Find(key);
42.         }
43.         bool erase(const K& key)
44.         {
45.                 return _ht.Erase(key);
46.         }
48.         V& operator[](const K& key)
49.         {
50.                 pair<iterator, bool> ret = insert({ key,V() });
51.                 return ret.first->second;
52.         }
53. private:
54.         hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, hash> _ht;
55. };

复制代码

        由于我们要包管unordered_map中存储的值的key值不被修改，以是哈希表的私有变量我们第二个传入的模版参数是pair<const K,V>。
        2.5、unordered_set的封装

        说实话这也没啥好说的，各人看看就好。

2. #include"HashTable.h"
3. template<class K,class Hash=HashFunc<K>>
4. class unordered_set
5. {
6.         struct SetKeyOfT
7.         {
8.                 const K& operator()(const K& key)
9.                 {
10.                         return key;
11.                 }
12.         };
13. public:
14.         //注意迭代器都是大类里面封装好的迭代器，不能拿最开始定义的那个类的迭代器
15.         typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
16.         typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
18.         iterator begin()
19.         {
20.                 return _ht.Begin();
21.         }
23.         iterator end()
24.         {
25.                 return _ht.Begin();
26.         }
27.         const_iterator begin() const
28.         {
29.                 return _ht.Begin();
30.         }
31.         const_iterator end() const
32.         {
33.                 return _ht.End();
34.         }
36.         pair<iterator, bool> insert(const K& key)
37.         {
38.                 return _ht.Insert(key);
39.         }
41.         iterator find(const K& key)
42.         {
43.                 return _ht.Find(key);
44.         }
46.         bool erase(const K& key)
47.         {
48.                 return _ht.Erase(key);
49.         }
51. private:
52.         hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
53. };

复制代码

3、总结 

        unordered_set常常用于去重以及存在性检查。unordered_map常用于快速键值查找以及频率统计。在后续做算法题时，常常会用到这两个容器。
特性unordered_setunordered_map存储内容仅 KeyKey-Value 对哈希冲突处理链地址法链地址法时间复杂度均匀 O(1)，最坏 O(n)均匀 O(1)，最坏 O(n)动态扩容必要必要迭代器支持可以自定义可以自定义         好了，今天的内容就分享到这，我们下期再见！