我正在用Js模式编写一个类似STL的容器库js-sdl。
在STL RB-Tree中有一个关于递减函数（迭代器的前向函数）的问题。
当我从小到大插入两个不同的值到树中时，我将得到一个具有以下结构的RB-Tree：
其中，Root节点和Header节点互为父节点和子节点，Header节点的左右节点分别指向插入的两个值，较小的值将成为Root节点，较大的值将成为Root的右子节点。
此时，当指向Root节点的迭代器递减时，将执行以下步骤：
1.判断当前不是Header节点，执行步骤2;
1.判断当前指针的左子节点为空，转步骤3;
1.确定当前节点（Root）是父节点（Header）的左子节点（注意此时Header的LeftMost指向树中最小的节点，也就是Root*），所以将指针移动到父节点（Header），重复步骤3，直到不再满足条件，再转到步骤4;
1.显然，由于Root节点和Header**节点互为父节点和子节点，所以在第3步之后，指针最终指向Root节点。
最后，下面的代码应该会陷入无限循环：
set<int> st { 1, 2 };
for (auto it = st.rbegin(); it != st.rend(); ++it) {
cout << *it <<endl;
}但实际上，上面的代码运行良好，我很困惑，我在STL代码中没有看到任何特殊的处理，我不精通C++，谁能帮我解决这个问题？
感激！
为什么上面的代码工作正常
1条答案
按热度按时间pdsfdshx1#
我想你误解了
std::reverse_iterator的工作原理：当调用重载的operator*时，底层迭代器被递减，然后解引用。更多详情请访问std::reverse_iterator循环应按以下方式解释：
1.在第一次循环中，迭代器（当前为
rbegin()）被解引用，这意味着底层迭代器被递减，然后被解引用。由于迭代器指向sentinel节点（Header），因此递减函数将其移动到其右子节点，即定义的最右侧节点。1.在第二次循环中，更新的迭代器被解引用，这意味着底层迭代器被递减，然后被解引用。由于迭代器指向一个外部节点，它的左子节点为null，然后递减函数将其移动到其父节点（Root）。
1.最后，由于更新后的迭代器现在等于
rend()，即根节点，因此循环中断。实际上，你对
begin()迭代器递减的观察是正确的：如果它被递减，则它再次指向它自己。在我的拙见中，我更喜欢一个更干净的红-黑二叉搜索树的实现，它以另一种方式组织结构，并使用另一种算法进行树遍历，这样哨兵节点既是最左边元素的前一个元素，也是最右边元素的下一个元素（循环迭代）。然而，它不允许对最右边的节点进行恒定时间访问，因此可以理解GCC库和许多其他库决定使用当前的实现：-）