关于STL红黑树迭代器decrement函数的代码运行困惑

背景与疑问 #

我正在开发类STL的JavaScript容器库js-sdsl，对STL红黑树的decrement函数（迭代器的向前操作）存在疑问：

当向树中从小到大插入1、2两个值后，红黑树的结构为：Root节点（值为1）与Header节点互为父子，Header节点的左右指针分别指向树中的最小节点（1）和最大节点（2），Root节点的右子节点是值为2的节点。

按我对decrement函数逻辑的推导，当指向Root节点（值1）的迭代器执行decrement操作时，会发生以下步骤：

• 判断当前节点不是Header，进入下一步；
• 当前节点的左子节点为空，进入下一步；
• 判断当前节点（Root）是父节点（Header）的左子节点，于是将指针移动到父节点（Header），接着重复步骤3——但Header的父节点是Root，这会导致指针在Root和Header之间来回跳转，陷入无限循环。

照此逻辑，以下C++代码应该陷入无限循环，但实际运行完全正常：

set<int> st { 1, 2 };
for (auto it = st.rbegin(); it != st.rend(); ++it) {
    cout << *it << endl;
}

关键原因：对decrement循环终止条件的误解 #

你的推导存在核心错误，问题出在对decrement函数中循环终止条件的判断上，结合反向迭代器的工作逻辑，实际流程不会无限循环：

首先明确反向迭代器的基础逻辑：

• rbegin()返回的反向迭代器，对应正向迭代器end()的前一个位置，也就是树中最大的元素2；
• rend()返回的反向迭代器，对应正向迭代器begin()的前一个位置，也就是Header节点。

遍历的实际执行流程：

1. 初始it = st.rbegin()，指向元素2，第一次执行++it（对应正向迭代器的--，即调用decrement），迭代器从2移动到1；
2. 第二次执行++it，调用decrement处理指向1的迭代器：
   • 节点1的左子节点为空，进入向上查找的逻辑；
   • 检查到节点1是父节点（Header）的左子节点，于是将指针移动到Header；
   • 接下来进入循环判断：当前节点是否是父节点的左子节点——此时Header的父节点是Root（1），但Root的左子节点并不是Header，这个判断条件不成立，循环直接终止；
   • 最终decrement将指针停在Header节点，也就是rend()对应的位置；
3. 此时it != st.rend()的判断结果为false，遍历结束，不会进入无限循环。

gcc实现的decrement函数中，循环的终止条件是「当前节点不是父节点的左子节点」，当指针移动到Header后，下一次判断的条件不满足，循环就会停止，并不会在Root和Header之间来回跳转。

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