为什么STL函数使用节点的颜色来计算std::map节点前驱
Why does STL function use node's color to calculate std::map node predecessor
我正在查看 libstdc++ 的 std::map 实现，并注意到迭代器递增和递减函数并不完全对称。 local_Rb_tree_decrement 函数（又名前身）有一个附加子句检查节点的颜色：
static _Rb_tree_node_base*
local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
{
if (__x->_M_color == _S_red
&& __x->_M_parent->_M_parent == __x)
__x = __x->_M_right;
else if (__x->_M_left != 0)
{
_Rb_tree_node_base* __y = __x->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
__x = __y;
}
else
{
_Rb_tree_node_base* __y = __x->_M_parent;
while (__x == __y->_M_left)
{
__x = __y;
__y = __y->_M_parent;
}
__x = __y;
}
return __x;
}
第一种情况的目的是什么？为什么节点的颜色会以任何方式影响树的遍历？为什么它与 local_Rb_tree_increment 不同？
if (__x->_M_color == _S_red
&& __x->_M_parent->_M_parent == __x)
__x = __x->_M_right;
提前感谢您的评论和解释！
这肯定是为了处理 end() 情况——注意无意义的 self-grandparent 检查和错误的运动方向。而且，毕竟，你不能增量 end()。颜色检查可能是为了（有时）避免比需要更多的内存获取的优化。
经过一些调查，我相信我已经弄明白了。
Header
libstdc++ 对 std::map 的实现在树的最顶端有一个额外的节点。它叫做Header，它的leftchild指向整棵树最左边的叶子，它的right child指向整棵树最右边的叶子，而它的parent其实就是根节点。因此，它有助于获得对树中最小和最大键的恒定时间访问时间（更快的 begin() 和 rbegin() 操作）。 根节点的parent也指向Header节点用这两个节点创建一个 parent 循环。
结束迭代器
正如 Davis Herring 回答的那样，这也用于处理迭代器的 end() 情况。 end 迭代器最天真的实现会简单地包含一个 null 指针。如果我们到达下一个节点 null 的位置，那就是 end。它完美地工作......直到你需要回去。 std::map 的迭代器是 双向的 并且您必须能够递减 end 迭代器并获得树的最右边的元素。
Header作为结尾
这里是Header节点再次提供帮助的地方。在 中序遍历 中搜索下一个节点时，我们最终到达 根节点 的 parent。我们不是从右（也不是左[=78=）来到Header节点 ], 就此而言) child 我们 return 它作为继任者。这样就很自然地有Header作为end迭代器节点。这就是为什么前驱计算的条件会检查 grandparent 等于自身的节点。这就是我们如何检查我们是否在 Header 节点中。这也解释了为什么我们向右child：Header的右边child是树的最右边的节点，这个是前驱中序遍历end的.
等等...但是颜色呢
是的，前一部分有一个重大错误。有 两个 节点的总 parent 等于此节点：Header 和 根。从这个角度来看，它们是无法区分的。我们需要为 Header 节点 设置一个单独的标志。
但是，red-black 树 中的每个节点都已经有一个布尔标志：color。我们还有一棵 red-black 树 的非常好的 属性：Root 总是 黑色.
将它们放在一起，我们可以完全省略额外的标志并为 Header 红色 着色。这将是具有 grandparent 循环的两个节点的区别 属性。
我正在查看 libstdc++ 的 std::map 实现，并注意到迭代器递增和递减函数并不完全对称。 local_Rb_tree_decrement 函数（又名前身）有一个附加子句检查节点的颜色：
static _Rb_tree_node_base*
local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
{
if (__x->_M_color == _S_red
&& __x->_M_parent->_M_parent == __x)
__x = __x->_M_right;
else if (__x->_M_left != 0)
{
_Rb_tree_node_base* __y = __x->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
__x = __y;
}
else
{
_Rb_tree_node_base* __y = __x->_M_parent;
while (__x == __y->_M_left)
{
__x = __y;
__y = __y->_M_parent;
}
__x = __y;
}
return __x;
}
第一种情况的目的是什么？为什么节点的颜色会以任何方式影响树的遍历？为什么它与 local_Rb_tree_increment 不同？
if (__x->_M_color == _S_red
&& __x->_M_parent->_M_parent == __x)
__x = __x->_M_right;
提前感谢您的评论和解释！
这肯定是为了处理 end() 情况——注意无意义的 self-grandparent 检查和错误的运动方向。而且，毕竟，你不能增量 end()。颜色检查可能是为了（有时）避免比需要更多的内存获取的优化。
经过一些调查，我相信我已经弄明白了。
Header
libstdc++ 对 std::map 的实现在树的最顶端有一个额外的节点。它叫做Header，它的leftchild指向整棵树最左边的叶子，它的right child指向整棵树最右边的叶子，而它的parent其实就是根节点。因此，它有助于获得对树中最小和最大键的恒定时间访问时间（更快的 begin() 和 rbegin() 操作）。 根节点的parent也指向Header节点用这两个节点创建一个 parent 循环。
结束迭代器
正如 Davis Herring 回答的那样，这也用于处理迭代器的 end() 情况。 end 迭代器最天真的实现会简单地包含一个 null 指针。如果我们到达下一个节点 null 的位置，那就是 end。它完美地工作......直到你需要回去。 std::map 的迭代器是 双向的 并且您必须能够递减 end 迭代器并获得树的最右边的元素。
Header作为结尾
这里是Header节点再次提供帮助的地方。在 中序遍历 中搜索下一个节点时，我们最终到达 根节点 的 parent。我们不是从右（也不是左[=78=）来到Header节点 ], 就此而言) child 我们 return 它作为继任者。这样就很自然地有Header作为end迭代器节点。这就是为什么前驱计算的条件会检查 grandparent 等于自身的节点。这就是我们如何检查我们是否在 Header 节点中。这也解释了为什么我们向右child：Header的右边child是树的最右边的节点，这个是前驱中序遍历end的.
等等...但是颜色呢
是的，前一部分有一个重大错误。有 两个 节点的总 parent 等于此节点：Header 和 根。从这个角度来看，它们是无法区分的。我们需要为 Header 节点 设置一个单独的标志。
但是，red-black 树 中的每个节点都已经有一个布尔标志：color。我们还有一棵 red-black 树 的非常好的 属性：Root 总是 黑色.
将它们放在一起，我们可以完全省略额外的标志并为 Header 红色 着色。这将是具有 grandparent 循环的两个节点的区别 属性。