如何为基于vector存储桶与链表实现的unordered map自定义迭代器

迭代器核心成员定义 #

迭代器需要内置3个核心状态字段，用来记录遍历进度：

• 底层存储桶的vector的引用/指针，用于访问所有存储桶
• 当前遍历到的存储桶的下标索引
• 当前存储桶链表中，指向当前遍历元素的链表节点指针
• 额外约定：当存储桶下标索引等于vector的总长度时，代表迭代器处于end（末尾）状态，此时节点指针固定为空。

遍历切换核心逻辑 #

迭代器的前进操作（operator++）是实现自动切换桶的核心，逻辑流程如下：

1. 先移动当前链表节点指针到当前节点的next指针指向的位置，如果移动后节点指针不为空，说明当前存储桶还有未遍历元素，直接结束本次前进操作即可。
2. 如果移动后节点指针为空，说明当前存储桶的链表已经全部遍历完成，此时从当前桶下标+1的位置开始，逐个向后检查后续每个存储桶的链表头是否非空：
   • 找到第一个非空的存储桶后，将当前桶下标更新为该桶的下标，同时将当前节点指针设置为该桶的链表头节点，结束本次前进操作。
   • 如果检查到最后一个存储桶都没有找到非空链表，说明所有元素已经全部遍历完成，直接将当前桶下标设置为桶vector的总长度，节点指针设为空，进入end状态即可。

边界初始化逻辑 #

• begin迭代器初始化：从下标为0的存储桶开始查找第一个非空桶，找到后将节点指针设为该桶的链表头即可；如果所有桶都为空，直接初始化为end状态。
• end迭代器初始化：直接将桶下标设为桶vector的总长度，节点指针设为空即可。

小提示：如果你的实现支持存储桶动态扩容，需要遵循标准unordered_map的迭代器失效规则，扩容后原有迭代器全部失效即可，避免访问野指针。

内容的提问来源于stack exchange，提问作者user17005485