＜＜哈希表迭代器函数＞＞

哈希表迭代器是手写哈希表的核心模块依托KeyOfT取键仿函数实现通用适配同时打通unordered_map / unordered_set遍历逻辑是容器实现迭代遍历、范围for循环的底层支撑。哈希表迭代器不同于链表、数组迭代器需要适配哈希桶数组单链表的双层结构。1 迭代器核心原理哈希表底层结构为数组哈希桶 每个桶挂载一条单链表。迭代器的核心工作逻辑记录当前遍历的节点指针当前链表节点记录当前遍历的桶下标定位当前遍历的数组桶重载运算符实现跨桶、同桶遍历切换依托KeyOfT适配map/set不同数据类型实现通用遍历核心特点哈希表迭代器是单向迭代器仅支持前置/后置不支持 -- 反向遍历和STL标准unordered容器迭代器特性一致。2 迭代器完整源码实现通用模板迭代器封装为模板类和哈希表、KeyOfT联动完美适配map、set两种场景无代码冗余。// 前置声明哈希表模板类 templateclass K, class T, class KeyOfT, class HashFunc class HashTable; // 哈希表迭代器类 templateclass K, class T, class KeyOfT, class HashFunc struct HashIterator { // 别名定义简化代码 typedef HashNodeT Node; typedef HashIteratorK, T, KeyOfT, HashFunc Self; Node* _pNode; // 当前迭代器指向的节点 size_t _bucketIndex; // 当前所在桶的下标 HashTableK, T, KeyOfT, HashFunc* _ht; // 哈希表本体指针 // 构造函数 HashIterator(Node* node, size_t index, HashTableK, T, KeyOfT, HashFunc* ht) :_pNode(node) , _bucketIndex(index) , _ht(ht) {} // 重载解引用返回节点存储的数据 T operator*() { return _pNode-_data; } // 重载箭头支持 - 访问数据成员 T* operator-() { return _pNode-_data; } // 重载前置核心遍历逻辑 Self operator() { // 1. 当前桶还有后续节点直接往后走 if (_pNode-_next ! nullptr) { _pNode _pNode-_next; } // 2. 当前桶遍历完毕寻找下一个非空桶 else { _bucketIndex; // 遍历后续所有桶找到第一个非空桶的头节点 while (_bucketIndex _ht-_table.size()) { if (_ht-_table[_bucketIndex] ! nullptr) { _pNode _ht-_table[_bucketIndex]; break; } _bucketIndex; } // 所有桶遍历完毕迭代器置空尾后迭代器 if (_bucketIndex _ht-_table.size()) { _pNode nullptr; } } return *this; } // 重载后置 Self operator(int) { Self tmp *this; (*this); return tmp; } // 重载相等判断 bool operator!(const Self it) { return _pNode ! it._pNode; } // 重载不等判断 bool operator(const Self it) { return _pNode it._pNode; } };3 哈希表配套迭代器接口在哈希表类中实现begin()和end()接口对外提供遍历入口适配范围for循环。// 哈希表类内接口 // 找到第一个非空桶的首节点返回起始迭代器 iterator begin() { for (size_t i 0; i _table.size(); i) { if (_table[i] ! nullptr) { return iterator(_table[i], i, this); } } return end(); } // 尾后迭代器节点为空 iterator end() { return iterator(nullptr, -1, this); }4 迭代器与 KeyOfT 的联动关系迭代器本身不直接处理键值提取而是通过对外暴露数据结合KeyOfT实现通用遍历匹配完美承接前文知识点遍历set迭代器取出T即K直接取值使用遍历map迭代器取出TpairK,V通过KeyOfT提取first键完成查找、比对逻辑核心逻辑迭代器负责遍历节点KeyOfT负责解析数据二者分工明确共同实现一套代码适配两种容器。5 迭代器核心特性单向遍历仅支持不支持--属于单向迭代器契合STL unordered容器特性跨桶遍历自动识别当前桶是否遍历完毕无缝切换下一个非空桶零开销模板编译期确定类型无运行时多态开销通用性强依托模板KeyOfT同时适配map、set自定义类型遍历6 迭代器常见易错点遍历顺序无序哈希表迭代器遍历顺序并非插入顺序是哈希桶存储顺序和STL unordered容器一致扩容迭代器失效哈希表扩容后底层数组重构原有迭代器全部失效不可继续使用不支持反向遍历未重载--运算符强行调用会编译报错尾后迭代器禁止解引用end()迭代器节点为空解引用会触发空指针访问崩溃7 面试高频考点1、哈希表迭代器为什么不支持反向遍历哈希表每个桶是单向链表仅保存next后继指针无前驱指针无法向前遍历且桶与桶之间无关联不支持反向迭代。2、迭代器和KeyOfT的协作逻辑是什么迭代器负责遍历所有存储节点取出原始数据TKeyOfT负责从T中提取哈希键K实现遍历过程中的查重、比对、匹配逻辑是遍历功能通用化的核心。3、哈希表迭代器失效场景主要为扩容场景插入元素触发扩容后底层哈希桶数组重新开辟空间所有节点迁移至新数组原有迭代器的节点指针、桶下标全部失效。