C++中的unordered_set和unordered_map的模拟实现

一、封装基本结构

与map和set的封装过程很想，unordered_set和unordered_map也需要用MapKeyOfT和SetKeyOfT创建哈希表类型，借此获取对应的key值来使用；

因此，在哈希表中也一样需要用参数class T来替代set中的key和map中的pair<key，value>

二、迭代器的实现

2.1普通迭代器及其问题

如map和set中一样，迭代器中也需要存储一个节点的指针，整体结构类似

但若是只存储一个节点的指针，在实现operator++的过程中会遇到一个问题：

如果迭代器此时指向“10”这个节点，应该如何找到它的下一个节点呢？

只存结点的话，会导致此时不知表的存在，这个问题是无解的。

因此需要让迭代器中有表的信息，有了表的情况后即可通过计算的出当前映射位置，进而找到下一个非空的映射位置

解决：通过传入迭代器中指针数组或者整个哈希表，而这两者之中，更方便的是传入哈希表

自此我们的迭代器类中的成员变量设置为

Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;

其余*  和->的重载以及begin和end的封装过程与map和set中思路相同，在实现逻辑方面：

begin要去找第一个非空映射位置

end要去构造空迭代器

2.1补：在迭代器中传入哈希表会导致两个问题

①在之前要有哈希表的定义；而在哈希表中因为要对迭代器进行typedef，所以在哈希表定义之前也要有迭代器的定义

可以通过将后定义的声明移到先定义的之前

②在++的逻辑中，我们需要访问私有成员_tables（即哈希表中的指针数组），会出现权限问题

其一，可以通过在哈希表中实现一个get函数来获取私有成员变量

其二，可以设置迭代器类为哈希表的友元类

template<class K, class T, class KeyOfT, class Ref, class Ptr, class Hash>
friend struct HSIterator;

2.2const迭代器

整体的逻辑与set和map封装中一样，但是会出现一个权限方面的问题：

因为之前在迭代器中传入了一个哈希表作为成员变量，所以构造函数的实现中也会出现

HSIterator(Node* node,HashTable<K, T, KeyOfT, Hash>* pht)
{}

而对应begin中我们进行构造迭代器时传值也是直接传入this指针，

但轮到Constbegin的实现，我们需要使用const来修饰成员函数（Constbegin是在哈希表类中实现的）

ConstIterator Begin() const
{}

我们要注意，const修饰成员函数的时候，this指针会被const修饰

此时我们

ConstIterator(_tables[hashi], this)

的第二个参数实际上传入的是

const HashTable<K, T, KeyOfT, Hash>*

综上所述：

传入的是const修饰的类型，但是参数列表中确实普通的类型，会导致权限放大的问题

为了解决这一冲突，遵顼权限可以缩小但是不可以放大的原则，我们需要在参数列表中加const修饰，此时参数列表变为

HSIterator(Node* node,const HashTable<K, T, KeyOfT, Hash>* pht)
{}

2.3普通迭代器也不应该允许修改

对于unordered_set来说，若是允许随意修改key的值会导致映射位置错乱，影响后续的查找操作

为了实现这一要求，我们可以在设置unordered_set的成员变量的时候设为

HashTable<K, const K, SetKeyOfT,Hash> _hs;

而对于unordered_map来说也是同理，只是value的值应该可以随意修改，所以其成员变量可以设置为

HashTable<K, pair<const K, V>, MapKeyOfT,Hash> _hs;

三、其他功能的实现

3.1Insert，Find，Erase的实现

如set和map中一样，主要逻辑在哈希表中实现，而unordered_set和unordered_map中只要套一层壳调用即可

3.2operator[]的实现

这是unordered_map特有的，要在对应类中单独实现，思路与map中完全一致

3.3让unordered_set和unordered_map支持自定义类型的映射

底层为哈希表，那么传入自定义类型的时候无法转换为size_t就是一个需要解决的问题

因为日常使用nordered_set和unordered_map是无法直接为哈希表的模板参数传参的，所以我们需要把哈希函数上移一层到unordered_set和unordered_map中，如

四、库中关于unordered_set和unordered_map的其他接口

4.1统计当前桶的总数

size_type bucket_count() const noexcept;

4.2获取第n个桶的长度

size_type bucket_size ( size_type n ) const;

4.3获取当前负载因子

float load_factor() const noexcept;

4.4设置桶的数量

void reserve ( size_type n );

4.5unordered_set和unordered_map使用的其他问题

①要计算平均桶的长度，我们只算有数据的桶才有意义，否则就是算负载因子大小

②如果已知数据量，可以提前reserve桶的数量，如链表中一样，哈希表增加桶的过程会产生不小的消耗