关于 RB-Tree 迭代器的疑惑

[ZLY201]

您好，我正在编写 Js 模式下的类 STL 容器库 js-sdsl

对于 STL RB-Tree 中的 decrement 函数（迭代器的前移函数）存在一个疑问

当我向 Tree 中从小到大插入两个不同的值后，我会得到以下结构的 RB-Tree:

其中 Root 节点和 Header 节点互为父子，Header 节点的左右节点分别指向插入的两个值，并且小的那个值会成为 Root 节点，大的会成为 Root 的右子节点

此时，当对指向 Root 节点的迭代器进行前移操作（decrement），会经过如下步骤：

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++ 并不精通，请问 @arkingc 您能够帮助我理解这个问题吗？

感激不尽！

[ZLY201]

顺带一提，您的文档对于我的编写起到了很大作用，再次表示感谢！

[arkingc]

不好意思，最近我事情也比较多。当时这块没有分析的这么细，主要是大概了解了一下红黑树的设计思想。没法帮到你抱歉

…

------------------&nbsp;原始邮件&nbsp;------------------ 发件人: "arkingc/note" ***@***.***&gt;; 发送时间:&nbsp;2023年6月15日(星期四) 下午4:14 ***@***.***&gt;; ***@***.******@***.***&gt;; 主题:&nbsp;[arkingc/note] 关于 RB-Tree 迭代器的疑惑 (Issue #9) 您好，我正在编写 Js 模式下的类 STL 容器库 js-sdsl 对于 STL RB-Tree 中的 decrement 函数（迭代器的前移函数）存在一个疑问 当我向 Tree 中从小到大插入两个不同的值后，我会得到以下结构的 RB-Tree: 其中 Root 节点和 Header 节点互为父子，header 节点的左右节点分别指向插入的两个值，并且小的那个值会成为 Root 节点，大的会成为 Root 的右子节点 此时，当对指向 Root 节点的迭代器进行前移操作（decrement），会经过如下步骤： 判断当前不为 Header 节点，进行步骤 2 判断当前指针的左子节点为空，执行步骤 3 判断当前节点（Root）为父节点（Header）的左子节点（注意，此时 Header 的 LeftMost 指向树中最小节点，即 Root），于是将 指针移至父节点（Header），重复步骤 3 直到不满足条件，执行步骤 4 显然由于 Root 节点和 Header 节点互为父子，最终经过步骤 3 指针重新指向 Root 节点 最终如下代码理应陷入死循环： set<int&gt; st { 1, 2 }; for (auto it = st.rbegin(); it != st.rend(); ++it) { cout << *it <<endl; } 但实际上，上述代码能够正常运行，对此我感到很疑惑，我并没有看到 STL 代码中有任何特殊的处理，我对于 C++ 并不精通，请问 @arkingc 您能够帮助我理解这个问题吗？ 感激不尽！ — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: ***@***.***&gt;