能否在不引用底层映射的情况下实现std::unordered_map::iterator？

之前我在一个没有标准库的环境里移植了一些C++标准库容器，连续存储和基于节点的容器的迭代器都很容易搞定，但轮到unordered_map的迭代器时我犯难了——我不想让迭代器存储对映射本身的引用，也不想存end迭代器，这该怎么实现呢？

最头疼的就是operator++操作，它得跳过空的桶，同时还不能越界到底层缓冲区外面去。

嘿，这个问题我太有共鸣了！其实完全能实现，我给你唠唠可行的思路：

首先，不用揪着“不能引用整个map”这个点死磕，换个思路——只要让迭代器知道什么时候该停下就行。不少实际的unordered_map实现里，都会在底层桶数组的末尾加一个「哨兵桶」，这个桶永远是空的，而且是桶数组的最后一个元素。有了这个哨兵，迭代器根本不需要依赖map本身来判断边界。

具体到operator++的实现，步骤大概是这样：

• 先看当前桶里的链表（如果是链式桶结构的话），有没有下一个节点——有的话直接移动到这个节点就行
• 如果当前桶已经遍历完了，就开始往后找下一个桶：
  • 从当前桶的下一个位置开始，逐个检查桶是否非空
  • 直到找到第一个非空的桶，或者碰到那个哨兵桶
• 要是碰到哨兵桶了，就把迭代器置为end状态，这时候就代表遍历结束了

还有个细节要注意：如果你的unordered_map支持重哈希（rehash），那迭代器肯定会失效，这和标准库的行为完全一致，完全符合预期，不用额外处理。

另外，你也可以让每个节点里记录自己所在的桶索引，这样迭代器在移动的时候，就能明确当前桶的位置，然后逐个往后找非空桶。但核心还是那个哨兵桶，它是判断边界的关键——没有它的话，迭代器确实不知道什么时候该停下，总不能一直遍历到内存里的垃圾区域吧？

总结下来，核心就是用哨兵桶代替对map的引用和end迭代器的存储，这样迭代器就能独立完成遍历、跳过空桶的操作啦！

备注：内容来源于stack exchange，提问作者Dominik Kaszewski