改造哈希表实现封装unordered_map/unordered_set:通过封装 uset/umap 掌握底层逻辑和细节控制

前面讲过如何手撕红黑树为底层的map/set这次来看看umap/uset。目录1.umap、uset基本框架2.哈希表的调整3.哈希表的迭代器实现核心难点3.1迭代器的思路参考源码3.2迭代器的实现3.3哈希表封装迭代器3.4上层套哈希表的迭代器前置声明报错3.5编译器对模板的按需实例化3.6const迭代器4.InsertEraseFind改造封装4.1下层Find改造4.2下层Insert改造4.3上层封装5.operator[ ] 以及 Key不能修改的问题5.1operator[ ]5.2Key不能修改的问题6.哈希函数Hash缺省值给在上层1.umap、uset基本框架红黑树为底层的map/set那节中讲解过KeyOfT的作用让一个红黑树就能兼容不同数据类型的map和set靠的就是这个KeyOfT仿函数。这里也一样。unordered_set:unordered_map:2.哈希表的调整原本是pair或者是Key的改成T了T是什么由上层决定可以pair也可以是Key。下面是哈希表的模板参数变化以及各种细节的调整1.2.以此类推Find也有类似设计到取Key操作的都一样不列举。3.哈希表的迭代器实现核心难点3.1迭代器的思路参考源码迭代器要怎么实现想一想。begin很好解决就是哈希表中第一个桶的第一个节点。operator 也是就是对桶内的链表curcur-next 类似。但怎么到下一个桶呢遍历哈希表找到下一个桶吗但是迭代器内只有一个节点遍历表要传一个表过去很不划算。传个哈希表指针是否可行还真就这样。早期SGI版本STL实现了哈希表它的迭代器就是这样设计的需要一个哈希表指针那顺便参考源码中如何解决operator大概就是cur当前节点为空进入if语句计算当前节点的哈希值while循环cur bucket ht-buckets.size() 当前节点为空并且 哈希表下一个位置没越界就进入while循环执行更新cur节点更新到下一个哈希表位置。3.2迭代器的实现我们照着它方法写迭代器需要节点和哈希表指针所以Ref和Ptr是让哈希表可以区别const版本。下面返回值需要避免麻烦弄成Self规定end为空。3.3哈希表封装迭代器3.4上层套哈希表的迭代器前置声明报错这样之后一运行就会发现报错了根据经验VS编译器报错出现分号找不到标识符说明编译器不认识这个类型这个类型有问题。如果类型没写错原因就是VS只会向上找声明和定义找不到就报错。哈希表定义在迭代器的后面迭代器声明了哈希表但是在上面找不到。但是把哈希表放在迭代器上面又会报错。因为哈希表也需要声明迭代器。解决办法是前置声明前置声明不需要缺省值3.5编译器对模板的按需实例化测试这个代码的时候又会报错。这是模板的按需实例化。用了什么就实例化什么。低版本的编译器没实例化的地方少个分号可能都检查不出来。高版本的编译器对模板的语法会简单检查大概扫一遍。但是不检查细节语法。解决办法是1.友元声明。2.提供结构get_xxxx函数把数据提出来。1.报错报在迭代器的operator说明迭代器要访问哈希表的私有table那就在哈希表中加上友元声明3.6const迭代器测试const迭代器会报错下面实现const迭代器版本。哈希表内声明加上const版本外层要能使用也需要套上const迭代器。即便这样还是会报错仔细分析会发现const迭代器的End,说的是构造函数类型错误也就是这个。为什么无法构造呢普通迭代器又可以构造原因是迭代器内部是普通指针HT* pht但是const成员函数endconst的this指针是const类型const HT* const 。而迭代器构造那边原本要求的是非const修饰的指针所以会构成权限放大导致报错。4.InsertEraseFind改造封装4.1下层Find改造返回值返回迭代器类型4.2下层Insert改造4.3上层封装5.operator[ ] 以及 Key不能修改的问题5.1operator[ ]operator括号的功能是可以根据它返回值修改value那返回值必然是V然后之前分析它的源码发现需要用到Insert的Iterator返回值下面就是它的实现5.2Key不能修改的问题上层给参数加constusetumap6.哈希函数Hash缺省值给在上层哈希函数Hash缺省值给在上层不然外层想改缺省值都不行。以map举例set一样的然后删除下层哈希表的缺省值就行。另外说明因为套了HashTable头文件所以HashFunc其实是有的不用纠结为什么这里凭空多出。