|
rom /// __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(); } const_iterator begin() const { return _M_leftmost(); } iterator end() { return _M_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
insert_unique(const value_type& __x); iterator insert_equal(const value_type& __x); iterator insert_unique(iterator __position, const value_type& __x); iterator insert_equal(iterator __position, const value_type& __x); template
void insert_unique(_InputIterator __first, _InputIterator __last); template
void insert_equal(_InputIterator __first, _InputIterator __last); 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
equal_range(const key_type& __x); pair
equal_range(const key_type& __x) const; public: /// Debugging. bool __rb_verify() const; }; template
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
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()); } template
_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; } ///v为要插入的值,x为要插入的位置,y为x的父节点 template
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_no |