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;

预先感谢您的评论和解释!

最佳答案

这肯定可以解决end()的情况-请注意无意义的祖 parent 祖 parent 检查和错误的运动方向。而且，毕竟，您无法增加end()。颜色检查大概是一种优化，以(有时)避免获取比所需更多的内存。

关于c++ - 为什么STL函数使用节点的颜色来计算std::map节点的前身，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58872546/