对RB-Tree迭代器自减函数的疑问

Question

我正在用Js模式写一个类似STL的容器库js-sdsl。

有一个关于STL RB-Tree中递减函数（迭代器的前向函数）的问题。

当我将两个不同的值从小到大插入树中时，我将得到一个具有以下结构的RB-Tree：

其中，Root节点和Header节点互为父节点，Header节点的左右节点分别指向插入的两个值，较小的值将成为Root节点，较大的值将成为Root的右子节点。

此时，当指向Root节点的迭代器递减时，会进行以下步骤：

1. 判断当前不是Header节点，转步骤2；
2. 判断当前指针的左子节点为空，转步骤3；
3. 判断当前节点（Root）是父节点（Header）的左子节点（注意，此时Header的LeftMost指向树中最小的节点，即Root），所以将指针移动到父节点（Header），重复步骤3，直到不再满足条件，转至步骤4；
4. 显然，因为Root节点和Header节点互为父节点和子节点，所以经过第3步，指针最终指向Root节点。

最终，下面的代码应该陷入无限循环：

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

但实际上，上面的代码工作正常，我很困惑，我在STL代码中没有看到任何特殊处理，我不精通C++，有人可以帮我解决这个问题吗？

感恩！

为什么上面的代码工作正常

Answer 1

我认为您误解了

std::reverse_iterator

的工作原理：当调用重载的

operator*

时，底层迭代器会递减，然后取消引用。更多详细信息可以在 std::reverse_iterator 找到。

循环应按以下方式解释：

1. 在第一个循环中，当前为

   rbegin()

   的迭代器被取消引用，这意味着底层迭代器被递减，然后被取消引用。由于迭代器指向前哨节点（Header），递减函数将其移动到其右子节点，即定义的最右边的节点。
2. 在第二个循环中，更新的迭代器被取消引用，这意味着底层迭代器被递减，然后被取消引用。由于迭代器指向外部节点，因此其左子节点为空，然后递减函数将其移动到其父节点（Root）。
3. 最后，由于更新后的迭代器现在等于

   rend()

   ，即根节点，循环被打破。

实际上，您对

begin()

迭代器递减的观察是正确的：如果它递减，它会再次引用自身。