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桶的数量，如链表中一样，哈希表增加桶的过程会产生不小的消耗
原文地址：https://blog.csdn.net/tianxhiliangtadi/article/details/145167383
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！