时间戳

首页 > 解决方案 > 为什么 STL 函数使用节点的颜色来计算 std::map 节点前任

c++ - 为什么 STL 函数使用节点的颜色来计算 std::map 节点前任

问题描述

我正在查看 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;

提前感谢您的评论和解释！

标签： c++gccstllibstdc++red-black-tree

解决方案

这肯定是为了处理这个end()案子——注意荒谬的自我祖父母检查和错误的运动方向。而且，毕竟，你不能递增 end(). 颜色检查可能是（有时）避免比需要更多的内存获取的优化。

推荐阅读