STL源码解析(1)-红黑树
STL容器之红黑树实现
C++中map和set都是基于红黑树的实现, 其迭代器也是红黑树提供的; 所以直接来分析stl_tree中的代码。
二叉排序树
1.左结点小于或等于根结点的值。
2.右结点大于或等于根结点的值。
3.左、右子树也分别为二叉排序树。
可以用于排序, 快速的插入和删除; 相比于链表和数组, 根据值继续查找的速度降低到了O(logn)
红黑树
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
6.具有二叉排序树的特点
对于二叉排序树而言, 如果左子树和右子树相差太大的话其效率会迅速降低; 红黑树就是为了避免这个问题的.
基础结构
struct _Rb_tree_node_base
{
typedef _Rb_tree_Color_type _Color_type;
typedef _Rb_tree_node_base* _Base_ptr;
_Color_type _M_color; // 节点颜色，非红即黑
_Base_ptr _M_parent; // 父节点
_Base_ptr _M_left; // 左节点
_Base_ptr _M_right; // 右节点
...
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Value>* _Link_type;
_Value _M_value_field; // 节点值
};
/*初始化header节点,该节点是用于辅助计算的*/
void _M_empty_initialize() {
_S_color(_M_header) = _S_rb_tree_red; // used to distinguish header from __root, in iterator.operator++
_M_root() = 0;
_M_leftmost() = _M_header;
_M_rightmost() = _M_header;
}
- 使用的是链表来实现, 相比于普通的二叉搜索树多了一个父节点以及颜色的记录;
- 初始化时会额外创建一个header节点, 用于辅助计算: header节点为末尾的节点、header左节点是开头
insert_unique实现插入一个不相同的值
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
bool>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_unique(const _Value& __v)
{
_Link_type __y = _M_header; //header节点
_Link_type __x = _M_root(); //根节点
bool __comp = true;
while (__x != 0) {
__y = __x;
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); //keyOfValue默认提供的就是取pair的第二个值:_Select1st
__x = __comp ? _S_left(__x) : _S_right(__x);
}
//二叉搜索树的查找方式, 比较然后往左往右进行移动; 区别在于叶子节点是黑色的NIL节点, __x是会找到叶子节点
iterator __j = iterator(__y); //查找到的是底层的一个节点其左右节点应该都是NIL;
if (__comp)
if (__j == begin())
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
else
--__j;
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
return pair<iterator,bool>(__j, false);
/* 假设找到了__y这个节点, 将要把节点插入于其左或者右节点
如果 x<y成立, 那么还需要判断 --y<x 才可以插入
如果 x<y不成立, 那么还需要判断 x<y才可以插入
因为默认cop给出的是less函数, 只可以比较小于的情况, 如果>=时需要排除==的情况
*/
}
这里的实现算是比较简单的, 相比于简单的二叉排序树: 由于叶子节点都是NIL节点, 所以找到的插入的父节点都是最后一级(左右节点都是NIL), 同时对==的情况做了排序比较.
_M_insert接口
// RB-tree 插入一个元素
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
{
_Link_type __x = (_Link_type) __x_;
_Link_type __y = (_Link_type) __y_;
_Link_type __z;
if (__y == _M_header || __x != 0 ||
_M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
__z = _M_create_node(__v); //如果是根节点,或者值小于其父节点, 那么放在父节点的左侧
_S_left(__y) = __z; // also makes _M_leftmost() = __z
// when __y == _M_header
if (__y == _M_header) {
_M_root() = __z;
_M_rightmost() = __z; //如果插入的是第一个节点,那么更新根节点和末尾节点
}
else if (__y == _M_leftmost()) //如果父节点是最小节点(第一个节点),新插入左节点需要更新为最小节点
_M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
}
else { //插入为父节点的右节点
__z = _M_create_node(__v);
_S_right(__y) = __z;
if (__y == _M_rightmost())
_M_rightmost() = __z; // maintain _M_rightmost() pointing to max node
}
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0; //新插入的总是叶子节点
_Rb_tree_rebalance(__z, _M_header->_M_parent); //reblance
++_M_node_count; //计数+1
return iterator(__z);
}
根据大小判断插入一个新的叶子节点, 然后重新进行平衡操作; RBtree的核心也就是进行平衡
红黑树的旋转操作
红黑树为了保持平衡插入玩数据后需要进行变色和旋转的操作以保持红黑树自平衡
左旋操作
父节点被其右孩子取代
右旋操作
该节点被其左孩子取代, 具体的为什么要使用左旋和右旋, 我们来看红黑树的实现
右旋
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_left; //X的左节点, 该节点将会取代X节点
__x->_M_left = __y->_M_right; //X节点右旋, 其左节点原本是Y; 现在取代于Y的右节点
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x; //Y的右节点变成了X的左节点, 更新parent
__y->_M_parent = __x->_M_parent; //Y取代X, 所以更新X的节点
if (__x == __root) //更新根节点
__root = __y;
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;
else
__x->_M_parent->_M_left = __y; //更新X的父节点于X的关联
__y->_M_right = __x; //X变为Y的右节点
__x->_M_parent = __y; //Y变为X的父节点
}
左旋操作
inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
/*X的右节点为Y, Y将会取代X的位置; Y的左节点将会变为X的右节点, X*/
{
_Rb_tree_node_base* __y = __x->_M_right; //Y是X的右节点
__x->_M_right = __y->_M_left; //X的右节点变为Y的左节点
if (__y->_M_left !=0) //更新Y的左节点的父节点
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent; //Y的父节点更新
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;
else
__x->_M_parent->_M_right = __y; //X的父节点更新数据
__y->_M_left = __x;
__x->_M_parent = __y; //X的父节点变为Y
}
红黑树插入分析
-
插入的节点都是叶子节点, 且是红色
-
如果插入节点的父节点是黑色, 那么符合要求不需要做任何操作
-
如果插入节点的父节点是红色, 不满足要求; 操作包括旋转和变色
新节点
-
新插入的节点是红色的
-
新插入的节点的是叶子节点
为什么插入的节点一定可以是叶子节点?
// 供 operator--() 调用
void _M_decrement()
{ // 红色节点，父节点的父节点等于自己?
if (_M_node->_M_color == _S_rb_tree_red &&
_M_node->_M_parent->_M_parent == _M_node)
_M_node = _M_node->_M_right;
else if (_M_node->_M_left != 0) { // 如果存在左孩子, 那么其前一个节点就是左孩子的最大值
_Base_ptr __y = _M_node->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right; //找到最下面一个右孩子
_M_node = __y;
}
else { //如果没有左孩子
_Base_ptr __y = _M_node->_M_parent;
while (_M_node == __y->_M_left) { //如果该节点为其父节点的左节点, 就一致往上找父节点
_M_node = __y;
__y = __y->_M_parent;
}
_M_node = __y;
}
}
插入的 可能性:
-
假设一个节点非叶子节点存在左孩子, 那么其前一个节点是其左孩子的最右孩子; 也就是说插入到该节点前面的话, 其位置将会是一个节点的右孩子 -> 叶子节点
-
假设一个节点不存在左孩子的话, 那么如果需要插入到该节点前的话: 其可以直接成为该节点的左孩子
无论什么情况, 均可以作为叶子节点插入到这颗树上
插入分析
把正在分析的节点称为关注节点, 其父节点的兄弟节点称为叔叔节点, 父节点的父节点称为祖父节点; 需要分析的情况初始情况是关注节点是红色的, 父节点也是红色的
叔叔节点也是红色节点
情况
操作:
-
父节点和叔叔节点变为黑色, 祖父节点变为红色
-
关注节点变为祖父节点
这样, 从祖父节点到关注节点这之中的数据符合规则; 但是祖父节点和其父节点还可能存在问题, 所以下一步考虑考虑祖父节点
之后的变换是不需要考虑该节点的孩子的
如果其叔叔节点是黑色, 关注节点是父节点的右节点
图片
- 关注节点变为红色的父节点, 之后对关注节点进行左旋
那么情况变为: 叔叔节点是黑色节点, 关注节点是父节点的左节点
如果叔叔节点是黑色, 关注节点是父节点的左节点
图片
-
关注节点的祖父节点右旋
-
父节点和祖父节点颜色呼唤
从图中可以看出, 黑色节点的计数未发生改变; 但是相邻的红色节点被分开了
注意
-
这是一个迭代判断的问题, 不仅仅是一次就完结了
-
每一种变换都不会影响黑色节点的计数, 考虑的问题仅仅是红色节点的相邻问题
-
变换过程中不需要考虑高一级或者低一级的问题, 因为不改变黑节点的计数
_Rb_tree_rebalance函数
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
/*参数一个是新插入的节点, 一个是根节点*/
{
__x->_M_color = _S_rb_tree_red;
//新插入的节点在最底层, 默认为红色; 如果其父节点为黑色, 那么不需要调整其规则不会被破坏
//如果其父节点也被是红色, 违反了连续的红节点以及红节点的子节点不能为黑
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) { //如果该节点的父节点是更高层节点的左节点
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; //叔叔节点
if (__y && __y->_M_color == _S_rb_tree_red) {
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
} //第一种情况, 变换祖父节点/父节点+叔叔节点的颜色; 关注节点变为祖父节点
//如果没有叔叔节点, 那么不需要考虑叔叔节点; 视作黑色节点
else {
if (__x == __x->_M_parent->_M_right) {
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
} //第二种情况, 关注节点变为父节点, 左旋
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
//第三种情况, 父节点和祖父节点颜色变换; 然后右旋
}
}
else {
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; //叔叔节点
if (__y && __y->_M_color == _S_rb_tree_red)
{
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
//第一种情况,
}
else
{
if (__x == __x->_M_parent->_M_left)
{
__x = __x->_M_parent;
_Rb_tree_rotate_right(__x, __root);
}
//第二种情况的镜像, 关注节点变为父节点, 进行右旋
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
//第三种情况的镜像, 颜色变换然后左旋
}
}
}
__root->_M_color = _S_rb_tree_black;
}
- 注意: 根节点实现为黑色是很有必要的, 否则在插入第二个点的时候就需要考虑调整的问题了
删除操作
删除操作包含两步调整:
初步调整满足, 每个节点到其任何叶子节点都包含相同的黑色节点
第二部调整为, 满足没有相邻的红色节点
-
case1: 节点仅有一个孩子
- 根据红色树条件4和5, 那么其本身必然为黑色, 并且其孩子必然是红色
- 使用它的孩子替换它, 并且将颜色改为黑色即可
- 不需要二次调整, 因为黑色计数没有改变
-
case2: 删除节点
a有两个孩子, 其后继节点是b, b仅有一个孩子- 使用
b代替a的位置, 并覆盖颜色; 情况2则变成了情况1
- 使用
-
case3: 删除节点是叶子节点: 主要分析的情况也就是这种情况
- 如果是红色节点, 则直接就可以结束了, 如果是黑色考虑的情况就变多了
下面图也是这里弄来的, 主要了自己学习分析一边
case3各种情况分析
父节点是红色, 兄弟节点是黑色, 两个侄子都是黑色(case1)
图片
- 将父节点和兄弟节点的颜色对换即可
父节点也是黑色节点, 兄弟节点是黑色节点, 两个侄子也是黑色节点(case2)
图片
-
将兄弟节点变为红色, 父节点变为关注节点(父节点需要进行黑色-1)的操作
-
这一步主要是平均了左右子树, 还需要进入第二步操作(父节点需要进行黑色+1操作)
-
原本关注节点是删除节点, 现在变为父节点; 情况其实是一致的, 都是需要补充缺少的黑色
兄弟节点是黑色节点, 左侄子为红色(case3)
图片
-
对兄弟节点进行右旋, 然后交换兄弟节点与其左孩子的颜色
-
这样就将情况变为了: 兄弟节点是黑色, 其右侄子是红色
兄弟节点是黑色节点, 右侄子是红色(case4)
图片
-
兄弟节点左旋, 并且颜色替换为父节点
-
父节点+兄弟节点的右孩子 变为黑色; 这样就弥补了左子树缺少的黑色
父节点是黑色节点, 兄弟节点是红色, 并且侄子节点必然有黑色(case5)
图片
-
对兄弟节点进行一次左旋操作, 并且和父节点交换颜色
-
那么就会进入上面的情况
STL删除代码实现
// 删除一个节点后调整
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
{
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
//考虑仅有一个子节点的情况
if (__y->_M_left == 0)
__x = __y->_M_right; // __x might be null.
else if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
__x = __y->_M_left; // __x is not null.
else { // __z has two non-null children. Set __y to
__y = __y->_M_right; // __z's successor. __x might be null.
while (__y->_M_left != 0)
__y = __y->_M_left; //__y是删除节点的后继节点;
__x = __y->_M_right; //后继节点的右孩子
}
/* __y是将要用于替换的节点, __x是删除节点的孩子 */
if (__y != __z)
/* 删除节点存在两个孩子, 使用__y替换__z节点 */
{
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
/* __z的左孩子和__y互相指向 */
if (__y != __z->_M_right) {
/* __y不是删除节点的右孩子, __x需要解题__x */
__x_parent = __y->_M_parent;
if (__x)
__x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x;
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else //后继节点就是删除节点的右孩子
__x_parent = __y;
//__x_parent保存的是替换位置后的x的父节点
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent; //__y指向__z的父节点
__STD::swap(__y->_M_color, __z->_M_color); //更新颜色
__y = __z; //__y指向将要被删除的节点
}
else
/* 仅有1个或者没有孩子的情况 */
{
__x_parent = __y->_M_parent;
if (__x)
__x->_M_parent = __y->_M_parent; /* 如果有孩子__x, 将__x的父节点改为删除节点的父节点 */
if (__root == __z)
__root = __x;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x; /* 删除节点__z的父节点改为指向__x */
if (__leftmost == __z)
if (__z->_M_right == 0) // __z->_M_left must be null also
__leftmost = __z->_M_parent;
// makes __leftmost == _M_header if __z == __root
else
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
if (__z->_M_left == 0) // __z->_M_right must be null also
__rightmost = __z->_M_parent;
// makes __rightmost == _M_header if __z == __root
else // __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
/* 删除节点有可能是一些特殊的节点, 更新数据 */
}
if (__y->_M_color != _S_rb_tree_red)
/* 如果删除节点是红色, 那么删除不会影响黑节点计数, 不需要进一步考虑 */
{
/*(__x == 0 || __x->_M_color == _S_rb_tree_black) 表达式的意思是:
如果删除节点没有孩子的情况, 以及需要黑色计数+1的节点不是红色的情况 */
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left) {
_Rb_tree_node_base* __w = __x_parent->_M_right; //兄弟节点
/* case5 兄弟节点是红色, 左旋操作交换颜色 */
if (__w->_M_color == _S_rb_tree_red)
{
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
if ((__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) &&
(__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
/* case1 这里没有改变父节点的元素, 因为可以在循环推出后改变 */
}
else
{
if (__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) {
if (__w->_M_left)
__w->_M_left->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
/* case3, 左孩子是红色, 进入case4 */
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_right)
__w->_M_right->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_left(__x_parent, __root);
/* case4 */
break;
}
}
else /* 镜像操作 */
{ // same as above, with _M_right <-> _M_left.
_Rb_tree_node_base* __w = __x_parent->_M_left;
if (__w->_M_color == _S_rb_tree_red) {
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent->_M_left;
}
if ((__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) &&
(__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else
{
if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) {
if (__w->_M_right)
__w->_M_right->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__w, __root);
__w = __x_parent->_M_left;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_left)
__w->_M_left->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_right(__x_parent, __root);
break;
}
}
if (__x)
__x->_M_color = _S_rb_tree_black;
}
return __y;
}
这里带上SGI STL的红黑树实现代码, 是一个比较老的版本, 但是很容易读
/*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_TREE_H
#define __SGI_STL_INTERNAL_TREE_H
/*
Red-black tree class, designed for use in implementing STL
associative containers (set, multiset, map, and multimap). The
insertion and deletion algorithms are based on those in Cormen,
Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
except that
(1) the header cell is maintained with links not only to the root
but also to the leftmost node of the tree, to enable constant time
begin(), and to the rightmost node of the tree, to enable linear time
performance when used with the generic set algorithms (set_union,
etc.);
(2) when a node being deleted has two children its successor node is
relinked into its place, rather than copied, so that the only
iterators invalidated are those referring to the deleted node.
*/
// 红黑树内部实现
#include <stl_algobase.h>
#include <stl_alloc.h>
#include <stl_construct.h>
#include <stl_function.h>
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1375
#endif
typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false; // 红色为 0
const _Rb_tree_Color_type _S_rb_tree_black = true; // 黑色为 1
// RB-tree 节点-基类
struct _Rb_tree_node_base
{
typedef _Rb_tree_Color_type _Color_type;
typedef _Rb_tree_node_base* _Base_ptr;
_Color_type _M_color; // 节点颜色，非红即黑
_Base_ptr _M_parent; // 父节点
_Base_ptr _M_left; // 左节点
_Base_ptr _M_right; // 右节点
// 找到 RB-tree 的最小值节点
static _Base_ptr _S_minimum(_Base_ptr __x)
{
while (__x->_M_left != 0) __x = __x->_M_left;
return __x;
}
// 找到 RB-tree 的最大值节点
static _Base_ptr _S_maximum(_Base_ptr __x)
{
while (__x->_M_right != 0) __x = __x->_M_right;
return __x;
}
};
// RB-tree 节点; 额外多了一项用于值的存储
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Value>* _Link_type;
_Value _M_value_field; // 节点值
};
// RB-tree 的迭代器-基类
struct _Rb_tree_base_iterator
{
typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
typedef bidirectional_iterator_tag iterator_category; // 双向迭代器
typedef ptrdiff_t difference_type;
_Base_ptr _M_node; // 它用来与容器之间产生一个连接关系
// 供 operator++() 调用
void _M_increment()
{
if (_M_node->_M_right != 0) { // 如果有右子节点，就向右走
_M_node = _M_node->_M_right;
while (_M_node->_M_left != 0) // 然后一直往左子树走到底
_M_node = _M_node->_M_left;
}
else {
_Base_ptr __y = _M_node->_M_parent; // 没有右子节点，找其父节点
while (_M_node == __y->_M_right) { // 当该节点为其父节点的右子节点，就一直向上找父节点
_M_node = __y;
__y = __y->_M_parent;
}
if (_M_node->_M_right != __y) //如果是这个父节点的左节点, 那么该父节点就是++的值
_M_node = __y;
}
}
// 供 operator--() 调用
void _M_decrement()
{ // 红色节点，父节点的父节点等于自己?
if (_M_node->_M_color == _S_rb_tree_red &&
_M_node->_M_parent->_M_parent == _M_node)
_M_node = _M_node->_M_right;
else if (_M_node->_M_left != 0) { // 如果存在左孩子, 那么其前一个节点就是左孩子的最大值
_Base_ptr __y = _M_node->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right; //找到最下面一个右孩子
_M_node = __y;
}
else { //如果没有左孩子
_Base_ptr __y = _M_node->_M_parent;
while (_M_node == __y->_M_left) { //如果该节点为其父节点的左节点, 就一致往上找父节点
_M_node = __y;
__y = __y->_M_parent;
}
_M_node = __y;
}
}
};
// RB-tree 的迭代器
template <class _Value, class _Ref, class _Ptr>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{
typedef _Value value_type;
typedef _Ref reference;
typedef _Ptr pointer;
typedef _Rb_tree_iterator<_Value, _Value&, _Value*>
iterator;
typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*>
const_iterator;
typedef _Rb_tree_iterator<_Value, _Ref, _Ptr>
_Self;
typedef _Rb_tree_node<_Value>* _Link_type;
_Rb_tree_iterator() {}
_Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
_Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
// RB-tree 迭代器 ++，-- 操作
_Self& operator++() { _M_increment(); return *this; }
_Self operator++(int) {
_Self __tmp = *this;
_M_increment();
return __tmp;
}
_Self& operator--() { _M_decrement(); return *this; }
_Self operator--(int) {
_Self __tmp = *this;
_M_decrement();
return __tmp;
}
};
inline bool operator==(const _Rb_tree_base_iterator& __x,
const _Rb_tree_base_iterator& __y) {
return __x._M_node == __y._M_node;
}
inline bool operator!=(const _Rb_tree_base_iterator& __x,
const _Rb_tree_base_iterator& __y) {
return __x._M_node != __y._M_node;
}
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
inline bidirectional_iterator_tag
iterator_category(const _Rb_tree_base_iterator&) {
return bidirectional_iterator_tag();
}
inline _Rb_tree_base_iterator::difference_type*
distance_type(const _Rb_tree_base_iterator&) {
return (_Rb_tree_base_iterator::difference_type*) 0;
}
template <class _Value, class _Ref, class _Ptr>
inline _Value* value_type(const _Rb_tree_iterator<_Value, _Ref, _Ptr>&) {
return (_Value*) 0;
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// 左旋转
inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
/*X的右节点为Y, Y将会取代X的位置; Y的左节点将会变为X的右节点, X*/
{
_Rb_tree_node_base* __y = __x->_M_right; //Y是X的右节点
__x->_M_right = __y->_M_left; //X的右节点变为Y的左节点
if (__y->_M_left !=0) //更新Y的左节点的父节点
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent; //Y的父节点更新
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;
else
__x->_M_parent->_M_right = __y; //X的父节点更新数据
__y->_M_left = __x;
__x->_M_parent = __y; //X的父节点变为Y
}
// 右旋转
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_left; //X的左节点, 该节点将会取代X节点
__x->_M_left = __y->_M_right; //X节点右旋, 其左节点原本是Y; 现在取代于Y的右节点
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x; //Y的右节点变成了X的左节点, 更新parent
__y->_M_parent = __x->_M_parent; //Y取代X, 所以更新X的节点
if (__x == __root) //更新根节点
__root = __y;
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;
else
__x->_M_parent->_M_left = __y; //更新X的父节点于X的关联
__y->_M_right = __x; //X变为Y的右节点
__x->_M_parent = __y; //Y变为X的父节点
}
// RB-tree 平衡调整
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
/*参数一个是新插入的节点, 一个是根节点*/
{
__x->_M_color = _S_rb_tree_red;
//新插入的节点在最底层, 默认为红色; 如果其父节点为黑色, 那么不需要调整其规则不会被破坏
//如果其父节点也被是红色, 违反了连续的红节点以及红节点的子节点不能为黑
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) { //如果该节点的父节点是更高层节点的左节点
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
if (__y && __y->_M_color == _S_rb_tree_red) {
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
}
else {
if (__x == __x->_M_parent->_M_right) {
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
}
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
}
}
else {
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
if (__y && __y->_M_color == _S_rb_tree_red)
{
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
}
else
{
if (__x == __x->_M_parent->_M_left)
{
__x = __x->_M_parent;
_Rb_tree_rotate_right(__x, __root);
}
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
}
}
}
__root->_M_color = _S_rb_tree_black;
}
// 删除一个节点后调整
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
{
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
__x = __y->_M_right; // __x might be null.
else
if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
__x = __y->_M_left; // __x is not null.
else { // __z has two non-null children. Set __y to
__y = __y->_M_right; // __z's successor. __x might be null.
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
if (__y != __z) { // relink y in place of z. y is z's successor
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
if (__y != __z->_M_right) {
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; // __y must be a child of _M_left
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else
__x_parent = __y;
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent;
__STD::swap(__y->_M_color, __z->_M_color);
__y = __z;
// __y now points to node to be actually deleted
}
else { // __y == __z
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
if (__root == __z)
__root = __x;
else
if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x;
if (__leftmost == __z)
if (__z->_M_right == 0) // __z->_M_left must be null also
__leftmost = __z->_M_parent;
// makes __leftmost == _M_header if __z == __root
else
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
if (__z->_M_left == 0) // __z->_M_right must be null also
__rightmost = __z->_M_parent;
// makes __rightmost == _M_header if __z == __root
else // __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
}
if (__y->_M_color != _S_rb_tree_red) {
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left) {
_Rb_tree_node_base* __w = __x_parent->_M_right;
if (__w->_M_color == _S_rb_tree_red) {
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
if ((__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black) &&
(__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
if (__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) {
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_left(__x_parent, __root);
break;
}
} else { // same as above, with _M_right <-> _M_left.
_Rb_tree_node_base* __w = __x_parent->_M_left;
if (__w->_M_color == _S_rb_tree_red) {
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent->_M_left;
}
if ((__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) &&
(__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
if (__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black) {
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__w, __root);
__w = __x_parent->_M_left;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_right(__x_parent, __root);
break;
}
}
if (__x) __x->_M_color = _S_rb_tree_black;
}
return __y;
}
// Base class to encapsulate the differences between old SGI-style
// allocators and standard-conforming allocators. In order to avoid
// having an empty base class, we arbitrarily move one of rb_tree's
// data members into the base class.
#ifdef __STL_USE_STD_ALLOCATORS
// RB-tree 的构造与内存分配-基类
// _Base for general standard-conforming allocators.
template <class _Tp, class _Alloc, bool _S_instanceless>
class _Rb_tree_alloc_base {
public:
typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return _M_node_allocator; }
_Rb_tree_alloc_base(const allocator_type& __a)
: _M_node_allocator(__a), _M_header(0) {}
protected:
typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
_M_node_allocator;
_Rb_tree_node<_Tp>* _M_header;
_Rb_tree_node<_Tp>* _M_get_node()
{ return _M_node_allocator.allocate(1); }
void _M_put_node(_Rb_tree_node<_Tp>* __p)
{ _M_node_allocator.deallocate(__p, 1); }
};
// Specialization for instanceless allocators.
template <class _Tp, class _Alloc>
class _Rb_tree_alloc_base<_Tp, _Alloc, true> {
public:
typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}
protected:
_Rb_tree_node<_Tp>* _M_header;
typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
_Alloc_type;
_Rb_tree_node<_Tp>* _M_get_node() // 配置空间
{ return _Alloc_type::allocate(1); }
void _M_put_node(_Rb_tree_node<_Tp>* __p) // 释放空间
{ _Alloc_type::deallocate(__p, 1); }
};
// _Rb_tree 的基类
template <class _Tp, class _Alloc>
struct _Rb_tree_base
: public _Rb_tree_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
typedef _Rb_tree_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
_Base;
typedef typename _Base::allocator_type allocator_type;
_Rb_tree_base(const allocator_type& __a)
: _Base(__a) { _M_header = _M_get_node(); }
~_Rb_tree_base() { _M_put_node(_M_header); }
};
#else /* __STL_USE_STD_ALLOCATORS */
template <class _Tp, class _Alloc>
struct _Rb_tree_base
{
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Rb_tree_base(const allocator_type&)
: _M_header(0) { _M_header = _M_get_node(); }
~_Rb_tree_base() { _M_put_node(_M_header); }
protected:
_Rb_tree_node<_Tp>* _M_header;
typedef simple_alloc<_Rb_tree_node<_Tp>, _Alloc> _Alloc_type;
_Rb_tree_node<_Tp>* _M_get_node()
{ return _Alloc_type::allocate(1); }
void _M_put_node(_Rb_tree_node<_Tp>* __p)
{ _Alloc_type::deallocate(__p, 1); }
};
#endif /* __STL_USE_STD_ALLOCATORS */
// _Rb_tree 数据结构
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> {
typedef _Rb_tree_base<_Value, _Alloc> _Base;
protected:
typedef _Rb_tree_node_base* _Base_ptr;
typedef _Rb_tree_node<_Value> _Rb_tree_node;
typedef _Rb_tree_Color_type _Color_type;
public:
typedef _Key key_type;
typedef _Value value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef _Rb_tree_node* _Link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
protected:
#ifdef __STL_USE_NAMESPACES
using _Base::_M_get_node;
using _Base::_M_put_node;
using _Base::_M_header; // header，实现上的技巧
#endif /* __STL_USE_NAMESPACES */
protected:
// 创建一个节点
_Link_type _M_create_node(const value_type& __x)
{
_Link_type __tmp = _M_get_node(); // 配置空间
__STL_TRY {
construct(&__tmp->_M_value_field, __x); // 构造内容
}
__STL_UNWIND(_M_put_node(__tmp));
return __tmp;
}
// 复制一个节点，注意节点的数据结构
_Link_type _M_clone_node(_Link_type __x)
{
_Link_type __tmp = _M_create_node(__x->_M_value_field);
__tmp->_M_color = __x->_M_color;
__tmp->_M_left = 0;
__tmp->_M_right = 0;
return __tmp;
}
// 删除一个节点
void destroy_node(_Link_type __p)
{
destroy(&__p->_M_value_field); // 析构内容
_M_put_node(__p); // 释放空间
}
protected:
size_type _M_node_count; // keeps track of size of tree 节点数量
_Compare _M_key_compare; // 节点间的键值大小比较准则
// 利用 header 快速找到 RB-tree 最小值，最大值，根节点
_Link_type& _M_root() const
{ return (_Link_type&) _M_header->_M_parent; }
_Link_type& _M_leftmost() const
{ return (_Link_type&) _M_header->_M_left; }
_Link_type& _M_rightmost() const
{ return (_Link_type&) _M_header->_M_right; }
// 获取 __x 的成员
static _Link_type& _S_left(_Link_type __x)
{ return (_Link_type&)(__x->_M_left); }
static _Link_type& _S_right(_Link_type __x)
{ return (_Link_type&)(__x->_M_right); }
static _Link_type& _S_parent(_Link_type __x)
{ return (_Link_type&)(__x->_M_parent); }
static reference _S_value(_Link_type __x)
{ return __x->_M_value_field; }
static const _Key& _S_key(_Link_type __x)
{ return _KeyOfValue()(_S_value(__x)); }
static _Color_type& _S_color(_Link_type __x)
{ return (_Color_type&)(__x->_M_color); }
static _Link_type& _S_left(_Base_ptr __x)
{ return (_Link_type&)(__x->_M_left); }
static _Link_type& _S_right(_Base_ptr __x)
{ return (_Link_type&)(__x->_M_right); }
static _Link_type& _S_parent(_Base_ptr __x)
{ return (_Link_type&)(__x->_M_parent); }
static reference _S_value(_Base_ptr __x)
{ return ((_Link_type)__x)->_M_value_field; }
static const _Key& _S_key(_Base_ptr __x)
{ return _KeyOfValue()(_S_value(_Link_type(__x)));}
static _Color_type& _S_color(_Base_ptr __x)
{ return (_Color_type&)(_Link_type(__x)->_M_color); }
// 求最小值和最大值
static _Link_type _S_minimum(_Link_type __x)
{ return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); }
static _Link_type _S_maximum(_Link_type __x)
{ return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
public:
typedef _Rb_tree_iterator<value_type, reference, pointer> iterator; // RB-tree 迭代器
typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
const_iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_bidirectional_iterator<iterator, value_type, reference,
difference_type>
reverse_iterator;
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type>
const_reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
private:
iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
_Link_type _M_copy(_Link_type __x, _Link_type __p);
void _M_erase(_Link_type __x);
public:
// allocation/deallocation
_Rb_tree()
: _Base(allocator_type()), _M_node_count(0), _M_key_compare()
{ _M_empty_initialize(); }
_Rb_tree(const _Compare& __comp)
: _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
{ _M_empty_initialize(); }
_Rb_tree(const _Compare& __comp, const allocator_type& __a)
: _Base(__a), _M_node_count(0), _M_key_compare(__comp)
{ _M_empty_initialize(); }
// 初始化
_Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
: _Base(__x.get_allocator()),
_M_node_count(0), _M_key_compare(__x._M_key_compare)
{
if (__x._M_root() == 0)
_M_empty_initialize();
else {
_S_color(_M_header) = _S_rb_tree_red;
_M_root() = _M_copy(__x._M_root(), _M_header);
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
}
_M_node_count = __x._M_node_count;
}
~_Rb_tree() { clear(); }
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
private:
/*初始化header节点,该节点是用于辅助计算的*/
void _M_empty_initialize() {
_S_color(_M_header) = _S_rb_tree_red; // used to distinguish header from __root, in iterator.operator++
_M_root() = 0;
_M_leftmost() = _M_header;
_M_rightmost() = _M_header;
}
public:
// accessors:
_Compare key_comp() const { return _M_key_compare; }
iterator begin() { return _M_leftmost(); } // RB-tree 的起点为最左节点处
const_iterator begin() const { return _M_leftmost(); }
iterator end() { return _M_header; } // RB-tree 的终点为 header 所指处
const_iterator end() const { return _M_header; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return const_reverse_iterator(begin());
}
bool empty() const { return _M_node_count == 0; }
size_type size() const { return _M_node_count; }
size_type max_size() const { return size_type(-1); }
void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
__STD::swap(_M_header, __t._M_header);
__STD::swap(_M_node_count, __t._M_node_count);
__STD::swap(_M_key_compare, __t._M_key_compare);
}
public:
// insert/erase
pair<iterator,bool> insert_unique(const value_type& __x);
iterator insert_equal(const value_type& __x);
iterator insert_unique(iterator __position, const value_type& __x); // 将 __x 插入到 RB-tree 唯一
iterator insert_equal(iterator __position, const value_type& __x); // 将 __x 插入到 RB-tree，允许重复
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert_unique(_InputIterator __first, _InputIterator __last);
template <class _InputIterator>
void insert_equal(_InputIterator __first, _InputIterator __last);
#else /* __STL_MEMBER_TEMPLATES */
void insert_unique(const_iterator __first, const_iterator __last);
void insert_unique(const value_type* __first, const value_type* __last);
void insert_equal(const_iterator __first, const_iterator __last);
void insert_equal(const value_type* __first, const value_type* __last);
#endif /* __STL_MEMBER_TEMPLATES */
void erase(iterator __position);
size_type erase(const key_type& __x);
void erase(iterator __first, iterator __last);
void erase(const key_type* __first, const key_type* __last);
void clear() {
if (_M_node_count != 0) {
_M_erase(_M_root());
_M_leftmost() = _M_header;
_M_root() = 0;
_M_rightmost() = _M_header;
_M_node_count = 0;
}
}
public:
// set operations:
iterator find(const key_type& __x);
const_iterator find(const key_type& __x) const;
size_type count(const key_type& __x) const;
iterator lower_bound(const key_type& __x);
const_iterator lower_bound(const key_type& __x) const;
iterator upper_bound(const key_type& __x);
const_iterator upper_bound(const key_type& __x) const;
pair<iterator,iterator> equal_range(const key_type& __x);
pair<const_iterator, const_iterator> equal_range(const key_type& __x) const;
public:
// Debugging.
bool __rb_verify() const;
};
// 比较操作
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return !(__x == __y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return __y < __x;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return !(__y < __x);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return !(__x < __y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline void
swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
__x.swap(__y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
// 赋值操作符
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
{
if (this != &__x) {
// Note that _Key may be a constant type.
clear();
_M_node_count = 0;
_M_key_compare = __x._M_key_compare;
if (__x._M_root() == 0) {
_M_root() = 0;
_M_leftmost() = _M_header;
_M_rightmost() = _M_header;
}
else {
_M_root() = _M_copy(__x._M_root(), _M_header);
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_node_count = __x._M_node_count;
}
}
return *this;
}
// RB-tree 插入一个元素
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
{
_Link_type __x = (_Link_type) __x_;
_Link_type __y = (_Link_type) __y_;
_Link_type __z;
if (__y == _M_header || __x != 0 ||
_M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
__z = _M_create_node(__v); //如果是根节点,或者值小于其父节点, 那么放在父节点的左侧
_S_left(__y) = __z; // also makes _M_leftmost() = __z
// when __y == _M_header
if (__y == _M_header) {
_M_root() = __z;
_M_rightmost() = __z; //如果插入的是第一个节点,那么更新根节点和末尾节点
}
else if (__y == _M_leftmost()) //如果父节点是最小节点(第一个节点),新插入左节点需要更新为最小节点
_M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
}
else { //插入为父节点的右节点
__z = _M_create_node(__v);
_S_right(__y) = __z;
if (__y == _M_rightmost())
_M_rightmost() = __z; // maintain _M_rightmost() pointing to max node
}
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0; //新插入的总是叶子节点
_Rb_tree_rebalance(__z, _M_header->_M_parent); //reblance
++_M_node_count; //计数+1
return iterator(__z);
}
// 插入新值，节点键值允许重复
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_equal(const _Value& __v)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root(); // 从根节点开始
while (__x != 0) {
__y = __x;
// 当插入值大于当前节点的值，向右，否则反之
__x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert(__x, __y, __v); // __x 为插入节点，__y 为插入节点的父节点， __v 为插入节点的值
}
// 插入值, 不允许重复
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
bool>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_unique(const _Value& __v)
{
_Link_type __y = _M_header; //header节点
_Link_type __x = _M_root(); //根节点
bool __comp = true;
while (__x != 0) {
__y = __x;
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); //keyOfValue默认提供的就是取pair的第二个值:_Select1st
__x = __comp ? _S_left(__x) : _S_right(__x);
}
//二叉搜索树的查找方式, 比较然后往左往右进行移动; 区别在于叶子节点是黑色的NIL节点, __x是会找到叶子节点
iterator __j = iterator(__y); //查找到的是底层的一个节点其左右节点应该都是NIL;
if (__comp) //如果插入的值小于__y的值
if (__j == begin()) //如果__y是首节点, 那么可以直接插入
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
else //如果不是首届点, 那么找到__y的左节点
--__j;
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
return pair<iterator,bool>(__j, false);
//假设找到了__y这个节点, 1, v<y=comp=false, 所以还需要判断==的情况
//2, v<y=comp=true, 那么还需要判断 y--<x的情况, 排除==的情况
}
template <class _Key, class _Val, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>
::insert_unique(iterator __position, const _Val& __v)
{
if (__position._M_node == _M_header->_M_left) { // begin()
if (size() > 0 &&
_M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
else
return insert_unique(__v).first;
} else if (__position._M_node == _M_header) { // end()
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_unique(__v).first;
} else {
iterator __before = __position;
--__before;
if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
&& _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) {
if (_S_right(__before._M_node) == 0)
return _M_insert(0, __before._M_node, __v);
else
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
} else
return insert_unique(__v).first;
}
}
template <class _Key, class _Val, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>
::insert_equal(iterator __position, const _Val& __v)
{
if (__position._M_node == _M_header->_M_left) { // begin()
if (size() > 0 &&
!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
else
return insert_equal(__v);
} else if (__position._M_node == _M_header) {// end()
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_equal(__v);
} else {
iterator __before = __position;
--__before;
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
&& !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) {
if (_S_right(__before._M_node) == 0)
return _M_insert(0, __before._M_node, __v);
else
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
} else
return insert_equal(__v);
}
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(_II __first, _II __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(_II __first, _II __last) {
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
#else /* __STL_MEMBER_TEMPLATES */
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void
_Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(const _Val* __first, const _Val* __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void
_Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(const_iterator __first, const_iterator __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void
_Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(const _Val* __first, const _Val* __last)
{
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(const_iterator __first, const_iterator __last)
{
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(iterator __position)
{
_Link_type __y =
(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
_M_header->_M_parent,
_M_header->_M_left,
_M_header->_M_right);
destroy_node(__y);
--_M_node_count;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
{
pair<iterator,iterator> __p = equal_range(__x);
size_type __n = 0;
distance(__p.first, __p.second, __n);
erase(__p.first, __p.second);
return __n;
}
template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc>
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
_Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>
::_M_copy(_Link_type __x, _Link_type __p)
{
// structural copy. __x and __p must be non-null.
_Link_type __top = _M_clone_node(__x);
__top->_M_parent = __p;
__STL_TRY {
if (__x->_M_right)
__top->_M_right = _M_copy(_S_right(__x), __top);
__p = __top;
__x = _S_left(__x);
while (__x != 0) {
_Link_type __y = _M_clone_node(__x);
__p->_M_left = __y;
__y->_M_parent = __p;
if (__x->_M_right)
__y->_M_right = _M_copy(_S_right(__x), __y);
__p = __y;
__x = _S_left(__x);
}
}
__STL_UNWIND(_M_erase(__top));
return __top;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::_M_erase(_Link_type __x)
{
// erase without rebalancing
while (__x != 0) {
_M_erase(_S_right(__x));
_Link_type __y = _S_left(__x);
destroy_node(__x);
__x = __y;
}
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(iterator __first, iterator __last)
{
if (__first == begin() && __last == end())
clear();
else
while (__first != __last) erase(__first++);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(const _Key* __first, const _Key* __last)
{
while (__first != __last) erase(*__first++);
}
// find 查找
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
{
_Link_type __y = _M_header; // Last node which is not less than __k.
_Link_type __x = _M_root(); // Current node.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
iterator __j = iterator(__y);
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const
{
_Link_type __y = _M_header; /* Last node which is not less than __k. */
_Link_type __x = _M_root(); /* Current node. */
while (__x != 0) {
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
}
const_iterator __j = const_iterator(__y);
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::count(const _Key& __k) const
{
pair<const_iterator, const_iterator> __p = equal_range(__k);
size_type __n = 0;
distance(__p.first, __p.second, __n);
return __n;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::lower_bound(const _Key& __k)
{
_Link_type __y = _M_header; /* Last node which is not less than __k. */
_Link_type __x = _M_root(); /* Current node. */
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::lower_bound(const _Key& __k) const
{
_Link_type __y = _M_header; /* Last node which is not less than __k. */
_Link_type __x = _M_root(); /* Current node. */
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return const_iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::upper_bound(const _Key& __k)
{
_Link_type __y = _M_header; /* Last node which is greater than __k. */
_Link_type __x = _M_root(); /* Current node. */
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::upper_bound(const _Key& __k) const
{
_Link_type __y = _M_header; /* Last node which is greater than __k. */
_Link_type __x = _M_root(); /* Current node. */
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return const_iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::equal_range(const _Key& __k)
{
return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
}
template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc>
inline
pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator,
typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator>
_Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>
::equal_range(const _Key& __k) const
{
return pair<const_iterator,const_iterator>(lower_bound(__k),
upper_bound(__k));
}
inline int
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
{
if (__node == 0)
return 0;
else {
int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
if (__node == __root)
return __bc;
else
return __bc + __black_count(__node->_M_parent, __root);
}
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
_M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
int __len = __black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it) {
_Link_type __x = (_Link_type) __it._M_node;
_Link_type __L = _S_left(__x);
_Link_type __R = _S_right(__x);
if (__x->_M_color == _S_rb_tree_red)
if ((__L && __L->_M_color == _S_rb_tree_red) ||
(__R && __R->_M_color == _S_rb_tree_red))
return false;
if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
return false;
if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
if (!__L && !__R && __black_count(__x, _M_root()) != __len)
return false;
}
if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
return false;
if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
return false;
return true;
}
// Class rb_tree is not part of the C++ standard. It is provided for
// compatibility with the HP STL.
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
{
typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
typedef typename _Base::allocator_type allocator_type;
rb_tree(const _Compare& __comp = _Compare(),
const allocator_type& __a = allocator_type())
: _Base(__comp, __a) {}
~rb_tree() {}
};
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1375
#endif
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_TREE_H */
// Local Variables:
// mode:C++
// End:
网友评论