北京营销型网站建站公司,做公益的网站,免费淘宝客网站模板,免费代理招商网一、封装基本结构
与map和set的封装过程很想#xff0c;unordered_set和unordered_map也需要用MapKeyOfT和SetKeyOfT创建哈希表类型#xff0c;借此获取对应的key值来使用#xff1b;
因此#xff0c;在哈希表中也一样需要用参数class T来替代set中的key和map中的pairunordered_set和unordered_map也需要用MapKeyOfT和SetKeyOfT创建哈希表类型借此获取对应的key值来使用
因此在哈希表中也一样需要用参数class T来替代set中的key和map中的pairkeyvalue
二、迭代器的实现
2.1普通迭代器及其问题
如map和set中一样迭代器中也需要存储一个节点的指针整体结构类似 但若是只存储一个节点的指针在实现operator的过程中会遇到一个问题
如果迭代器此时指向“10”这个节点应该如何找到它的下一个节点呢
只存结点的话会导致此时不知表的存在这个问题是无解的。
因此需要让迭代器中有表的信息有了表的情况后即可通过计算的出当前映射位置进而找到下一个非空的映射位置
解决通过传入迭代器中指针数组或者整个哈希表而这两者之中更方便的是传入哈希表
自此我们的迭代器类中的成员变量设置为
Node* _node;
const HashTableK, T, KeyOfT, Hash* _pht;
其余* 和-的重载以及begin和end的封装过程与map和set中思路相同在实现逻辑方面
begin要去找第一个非空映射位置
end要去构造空迭代器
2.1补在迭代器中传入哈希表会导致两个问题
①在之前要有哈希表的定义而在哈希表中因为要对迭代器进行typedef所以在哈希表定义之前也要有迭代器的定义
可以通过将后定义的声明移到先定义的之前
②在的逻辑中我们需要访问私有成员_tables即哈希表中的指针数组会出现权限问题
其一可以通过在哈希表中实现一个get函数来获取私有成员变量
其二可以设置迭代器类为哈希表的友元类
templateclass K, class T, class KeyOfT, class Ref, class Ptr, class Hash
friend struct HSIterator;
2.2const迭代器
整体的逻辑与set和map封装中一样但是会出现一个权限方面的问题
因为之前在迭代器中传入了一个哈希表作为成员变量所以构造函数的实现中也会出现
HSIterator(Node* node,HashTableK, T, KeyOfT, Hash* pht)
{}
而对应begin中我们进行构造迭代器时传值也是直接传入this指针
但轮到Constbegin的实现我们需要使用const来修饰成员函数Constbegin是在哈希表类中实现的
ConstIterator Begin() const
{}
我们要注意const修饰成员函数的时候this指针会被const修饰
此时我们
ConstIterator(_tables[hashi], this)
的第二个参数实际上传入的是
const HashTableK, T, KeyOfT, Hash*
综上所述
传入的是const修饰的类型但是参数列表中确实普通的类型会导致权限放大的问题
为了解决这一冲突遵顼权限可以缩小但是不可以放大的原则我们需要在参数列表中加const修饰此时参数列表变为
HSIterator(Node* node,const HashTableK, T, KeyOfT, Hash* pht)
{}
2.3普通迭代器也不应该允许修改
对于unordered_set来说若是允许随意修改key的值会导致映射位置错乱影响后续的查找操作
为了实现这一要求我们可以在设置unordered_set的成员变量的时候设为
HashTableK, const K, SetKeyOfT,Hash _hs;
而对于unordered_map来说也是同理只是value的值应该可以随意修改所以其成员变量可以设置为
HashTableK, pairconst K, V, MapKeyOfT,Hash _hs;
三、其他功能的实现
3.1InsertFindErase的实现
如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桶的数量如链表中一样哈希表增加桶的过程会产生不小的消耗
