|
de(__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); ++_M_node_count; return iterator(__z); } template
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) ///寻找合适的插入点(一定为0),同时记录插入点的父节点 { __y = __x; __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? _S_left(__x) : _S_right(__x); } return _M_insert(__x, __y, __v); } template
pair
::iterator, bool> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_unique(const _Value& __v) ///键值不可重复插入,插入可能失败 { _Link_type __y = _M_header; _Link_type __x = _M_root(); bool __comp = true; while (__x != 0) ///寻找可能的插入位置 { __y = __x; __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); ///v小于x的键值时向左子树移动,否则向右子树移动,因此,如果已有重复 ///键值存在,x最终一定位于重复键值所在节点的右子树 __x = __comp ? _S_left(__x) : _S_right(__x); } ///检查是否可以插入(键值是否有重复) iterator __j = iterator(__y); if (__comp) ///插入点是其父节点的左孩子 if (__j == begin()) { ///最左端结点,不可能位于某个节点的右子树,因此可判定无重复键值,可插入 return pair
(_M_insert(__x, __y, __v), true); } else { --__j; ///得到其父节点的直接前驱结点,若插入x,即成为x的直接前驱结点 } ///此时,j为若插入x后x的直接前驱结点. if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) return pair
(_M_insert(__x, __y, __v), true); return pair
(__j, false); } ///不可重复插入,先在指定位置插入,若指定位置插入不合法, ///再试图寻找合法位置插入 template
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))) { /// first argument just needs to be non-null return _M_insert(__position._M_node, __position._M_node, __v); } 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
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 = |