or _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::lower_bound(const _Key& __k) { _Link_type __y = _M_header; _Link_type __x = _M_root(); while (__x != 0) { ///当__x的键值 == k时,寻找"更小的" 键值等于k的__x if (!_M_key_compare(_S_key(__x), __k)) __y = __x, __x = _S_left(__x); else /// x的键值 < k __x = _S_right(__x); } return iterator(__y); } template
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; _Link_type __x = _M_root(); 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); } ///返回"最大的"键值和k相同结点的直接后继 template
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; _Link_type __x = _M_root(); while (__x != 0) { if (_M_key_compare(__k, _S_key(__x))) ///k小于x的键值 __y = __x, __x = _S_left(__x); else ///当__x的键值 == k时,寻找"更大的" __x __x = _S_right(__x); } return iterator(__y); } template
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; _Link_type __x = _M_root(); 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
inline pair
::iterator, typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::equal_range(const _Key& __k) { return pair
(lower_bound(__k), upper_bound(__k)); } template
inline pair
::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
(lower_bound(__k), upper_bound(__k)); } ///计算[__node,__root]之间黑色结点的个数,采用递归上溯法 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
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; }
|