|
__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); } } template
template
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc> ::insert_equal(_II __first, _II __last) { for ( ; __first != __last; ++__first) insert_equal(*__first); } template
template
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc> ::insert_unique(_II __first, _II __last) { for ( ; __first != __last; ++__first) insert_unique(*__first); } template
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
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) { pair
__p = equal_range(__x); size_type __n = 0; distance(__p.first, __p.second, __n); erase(__p.first, __p.second); return __n; } ///复制以__x作为根节点的子树,得到的树作为__p的子树 template
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; try { if (__x->_M_right) __top->_M_right = _M_copy(_S_right(__x), __top); ///递归复制x的右子树 __p = __top; __x = _S_left(__x); ///直接复制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); ///x指向其左孩子,循环复制其左子树 } } catch(...) { _M_erase(__top); } return __top; } template
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
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
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::erase(const _Key* __first, const _Key* __last) { while (__first != __last) erase(*__first++); } template
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)) ///k <= x的键值时 __y = __x, __x = _S_left(__x); else ///k > x的键值时 __x = _S_right(__x); } ///至此,x为k的可插入点,y为x的直接前驱,如果k存在,则j不可能为end(), ///而且应有j指向结点的键值和k相等 iterator __j = iterator(__y); return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; } template
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; _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); } const_iterator __j = const_iterator(__y); return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; } template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::count(const _Key& __k) const { pair
__p = equal_range(__k); size_type __n = 0; distance(__p.first, __p.second, __n); return __n; } ///返回"最小的"键值和k相同结点 template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterat |