From 0447af6cf0fa465bb5e0c15a3939dad0c1b3f564 Mon Sep 17 00:00:00 2001 From: paolo Date: Sat, 25 Nov 2006 10:35:52 +0000 Subject: [PATCH] 2006-11-25 Paolo Carlini PR libstdc++/29385 (partial) * include/bits/stl_tree.h (_Rb_tree<>::destroy_node): Uglify. (_M_erase, erase(iterator), erase(const_iterator)): Adjust 2006-11-25 Paolo Carlini PR libstdc++/29385 (partial) * include/bits/stl_tree.h (_Rb_tree<>::_M_lower_bound(_Const_Link_type, _Const_Link_type, const _Key&), _M_upper_bound(_Const_Link_type, _Const_Link_type, const _Key&)): Add. (lower_bound(const key_type&), upper_bound(const key_type&), find(const key_type&)): Call the latter. 2006-11-25 Gawain Bolton PR libstdc++/29385 (partial) * include/bits/stl_tree.h (_Rb_tree_rotate_left, _Rb_tree_rotate_right): Do not declare. (_Rb_tree<>::_M_insert(_Base_ptr, _Base_ptr, const value_type&), _M_insert(_Const_Base_ptr, _Const_Base_ptr, const value_type&), _M_insert_unique(iterator, const value_type&), _M_insert_unique(const_iterator, const value_type&), _M_insert_equal(iterator, const value_type&), _M_insert_equal(const_iterator, const value_type&)): Remove. (_Rb_tree<>::_M_insert_(_Const_Base_ptr, _Const_Base_ptr, const value_type&), _M_insert_unique_(const_iterator, const value_type&), _M_insert_equal_(const_iterator, const value_type&)): Add, adjust all callers. * include/bits/stl_map.h (map<>::insert(iterator, const value_type&)): Adjust. * include/bits/stl_set.h (set<>::insert(iterator, const value_type&)): Likewise. * include/bits/stl_multimap.h (multimap<>::insert(iterator, const value_type&)): Likewise. * include/bits/stl_multiset.h (multiset<>::insert(iterator, const value_type&)): Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@119190 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 40 +++ libstdc++-v3/include/bits/stl_map.h | 2 +- libstdc++-v3/include/bits/stl_multimap.h | 2 +- libstdc++-v3/include/bits/stl_multiset.h | 2 +- libstdc++-v3/include/bits/stl_set.h | 2 +- libstdc++-v3/include/bits/stl_tree.h | 504 ++++++++++--------------------- 6 files changed, 199 insertions(+), 353 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index dde783a..2566535 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,43 @@ +2006-11-25 Paolo Carlini + + PR libstdc++/29385 (partial) + * include/bits/stl_tree.h (_Rb_tree<>::destroy_node): Uglify. + (_M_erase, erase(iterator), erase(const_iterator)): Adjust + +2006-11-25 Paolo Carlini + + PR libstdc++/29385 (partial) + * include/bits/stl_tree.h (_Rb_tree<>::_M_lower_bound(_Const_Link_type, + _Const_Link_type, const _Key&), _M_upper_bound(_Const_Link_type, + _Const_Link_type, const _Key&)): Add. + (lower_bound(const key_type&), upper_bound(const key_type&), + find(const key_type&)): Call the latter. + +2006-11-25 Gawain Bolton + + PR libstdc++/29385 (partial) + * include/bits/stl_tree.h (_Rb_tree_rotate_left, + _Rb_tree_rotate_right): Do not declare. + (_Rb_tree<>::_M_insert(_Base_ptr, _Base_ptr, const value_type&), + _M_insert(_Const_Base_ptr, _Const_Base_ptr, const value_type&), + _M_insert_unique(iterator, const value_type&), + _M_insert_unique(const_iterator, const value_type&), + _M_insert_equal(iterator, const value_type&), + _M_insert_equal(const_iterator, const value_type&)): + Remove. + (_Rb_tree<>::_M_insert_(_Const_Base_ptr, _Const_Base_ptr, + const value_type&), _M_insert_unique_(const_iterator, + const value_type&), _M_insert_equal_(const_iterator, + const value_type&)): Add, adjust all callers. + * include/bits/stl_map.h (map<>::insert(iterator, const value_type&)): + Adjust. + * include/bits/stl_set.h (set<>::insert(iterator, const value_type&)): + Likewise. + * include/bits/stl_multimap.h (multimap<>::insert(iterator, + const value_type&)): Likewise. + * include/bits/stl_multiset.h (multiset<>::insert(iterator, + const value_type&)): Likewise. + 2006-11-22 Antony King J"orn Rennecke diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index 6dc53e9..d04b376 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -423,7 +423,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) */ iterator insert(iterator position, const value_type& __x) - { return _M_t._M_insert_unique(position, __x); } + { return _M_t._M_insert_unique_(position, __x); } /** * @brief Template function that attemps to insert a range of elements. diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index b11b6e4..554035a 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -361,7 +361,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) */ iterator insert(iterator __position, const value_type& __x) - { return _M_t._M_insert_equal(__position, __x); } + { return _M_t._M_insert_equal_(__position, __x); } /** * @brief A template function that attemps to insert a range of elements. diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index 8c499c3..3979cd6 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -316,7 +316,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) */ iterator insert(iterator __position, const value_type& __x) - { return _M_t._M_insert_equal(__position, __x); } + { return _M_t._M_insert_equal_(__position, __x); } /** * @brief A template function that attemps to insert a range of elements. diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index b61106a..6ee8526 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -329,7 +329,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) */ iterator insert(iterator __position, const value_type& __x) - { return _M_t._M_insert_unique(__position, __x); } + { return _M_t._M_insert_unique_(__position, __x); } /** * @brief A template function that attemps to insert a range of elements. diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 96b7a52..c4dba4f 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -306,14 +306,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { return __x._M_node != __y._M_node; } void - _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, - _Rb_tree_node_base*& __root); - - void - _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, - _Rb_tree_node_base*& __root); - - void _Rb_tree_insert_and_rebalance(const bool __insert_left, _Rb_tree_node_base* __x, _Rb_tree_node_base* __p, @@ -395,7 +387,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } void - destroy_node(_Link_type __p) + _M_destroy_node(_Link_type __p) { get_allocator().destroy(&__p->_M_value_field); _M_put_node(__p); @@ -546,16 +538,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std) private: iterator - _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); + _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, + const value_type& __v); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 233. Insertion hints in associative containers. iterator _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); - const_iterator - _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y, - const value_type& __v); + iterator + _M_insert_equal_lower(const value_type& __x); _Link_type _M_copy(_Const_Link_type __x, _Link_type __p); @@ -563,6 +555,14 @@ _GLIBCXX_BEGIN_NAMESPACE(std) void _M_erase(_Link_type __x); + iterator + _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, + const _Key& __k) const; + + iterator + _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, + const _Key& __k) const; + public: // allocation/deallocation _Rb_tree() @@ -662,22 +662,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) iterator _M_insert_equal(const value_type& __x); - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 233. Insertion hints in associative containers. - iterator - _M_insert_equal_lower(const value_type& __x); - iterator - _M_insert_unique(iterator __position, const value_type& __x); - - const_iterator - _M_insert_unique(const_iterator __position, const value_type& __x); + _M_insert_unique_(const_iterator __position, const value_type& __x); iterator - _M_insert_equal(iterator __position, const value_type& __x); - - const_iterator - _M_insert_equal(const_iterator __position, const value_type& __x); + _M_insert_equal_(const_iterator __position, const value_type& __x); template void @@ -717,31 +706,35 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // Set operations. iterator - find(const key_type& __x); + find(const key_type& __k); const_iterator - find(const key_type& __x) const; + find(const key_type& __k) const; size_type - count(const key_type& __x) const; + count(const key_type& __k) const; iterator - lower_bound(const key_type& __x); + lower_bound(const key_type& __k) + { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); } const_iterator - lower_bound(const key_type& __x) const; + lower_bound(const key_type& __k) const + { return const_iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); } iterator - upper_bound(const key_type& __x); + upper_bound(const key_type& __k) + { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); } const_iterator - upper_bound(const key_type& __x) const; + upper_bound(const key_type& __k) const + { return const_iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); } - pair - equal_range(const key_type& __x); + pair + equal_range(const key_type& __k); pair - equal_range(const key_type& __x) const; + equal_range(const key_type& __k) const; // Debugging. bool @@ -829,7 +822,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename _Compare, typename _Alloc> typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) + _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) { bool __insert_left = (__x != 0 || __p == _M_end() || _M_impl._M_key_compare(_KeyOfValue()(__v), @@ -837,7 +830,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _Link_type __z = _M_create_node(__v); - _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + _Rb_tree_insert_and_rebalance(__insert_left, __z, + const_cast<_Base_ptr>(__p), this->_M_impl._M_header); ++_M_impl._M_node_count; return iterator(__z); @@ -863,55 +857,101 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) + _M_insert_equal_lower(const _Val& __v) { - bool __insert_left = (__x != 0 || __p == _M_end() - || _M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(__p))); + _Link_type __x = _M_begin(); + _Link_type __y = _M_end(); + while (__x != 0) + { + __y = __x; + __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? + _S_left(__x) : _S_right(__x); + } + return _M_insert_lower(__x, __y, __v); + } - _Link_type __z = _M_create_node(__v); + template + typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type + _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: + _M_copy(_Const_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; - _Rb_tree_insert_and_rebalance(__insert_left, __z, - const_cast<_Base_ptr>(__p), - this->_M_impl._M_header); - ++_M_impl._M_node_count; - return const_iterator(__z); + 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); + } + } + catch(...) + { + _M_erase(__top); + __throw_exception_again; + } + return __top; } template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + void _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert_equal(const _Val& __v) + _M_erase(_Link_type __x) { - _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); + // Erase without rebalancing. while (__x != 0) { - __y = __x; - __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? - _S_left(__x) : _S_right(__x); + _M_erase(_S_right(__x)); + _Link_type __y = _S_left(__x); + _M_destroy_node(__x); + __x = __y; } - return _M_insert(__x, __y, __v); } template typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert_equal_lower(const _Val& __v) + _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, + const _Key& __k) const { - _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); while (__x != 0) - { - __y = __x; - __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? - _S_left(__x) : _S_right(__x); - } - return _M_insert_lower(__x, __y, __v); + if (!_M_impl._M_key_compare(_S_key(__x), __k)) + __y = __x, __x = _S_left(__x); + else + __x = _S_right(__x); + return iterator(const_cast<_Link_type>(__y)); + } + + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, + const _Key& __k) const + { + while (__x != 0) + if (_M_impl._M_key_compare(__k, _S_key(__x))) + __y = __x, __x = _S_left(__x); + else + __x = _S_right(__x); + return iterator(const_cast<_Link_type>(__y)); } template(_M_insert(__x, __y, __v), true); + return pair(_M_insert_(__x, __y, __v), true); else --__j; if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) - return pair(_M_insert(__x, __y, __v), true); + return pair(_M_insert_(__x, __y, __v), true); return pair(__j, false); } @@ -995,64 +1035,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename _Compare, typename _Alloc> typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert_unique(iterator __position, const _Val& __v) + _M_insert_equal(const _Val& __v) { - // end() - if (__position._M_node == _M_end()) - { - if (size() > 0 - && _M_impl._M_key_compare(_S_key(_M_rightmost()), - _KeyOfValue()(__v))) - return _M_insert(0, _M_rightmost(), __v); - else - return _M_insert_unique(__v).first; - } - else if (_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(__position._M_node))) - { - // First, try before... - iterator __before = __position; - if (__position._M_node == _M_leftmost()) // begin() - return _M_insert(_M_leftmost(), _M_leftmost(), __v); - else if (_M_impl._M_key_compare(_S_key((--__before)._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); - } - else - return _M_insert_unique(__v).first; - } - else if (_M_impl._M_key_compare(_S_key(__position._M_node), - _KeyOfValue()(__v))) + _Link_type __x = _M_begin(); + _Link_type __y = _M_end(); + while (__x != 0) { - // ... then try after. - iterator __after = __position; - if (__position._M_node == _M_rightmost()) - return _M_insert(0, _M_rightmost(), __v); - else if (_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key((++__after)._M_node))) - { - if (_S_right(__position._M_node) == 0) - return _M_insert(0, __position._M_node, __v); - else - return _M_insert(__after._M_node, __after._M_node, __v); - } - else - return _M_insert_unique(__v).first; + __y = __x; + __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? + _S_left(__x) : _S_right(__x); } - else - return __position; // Equivalent keys. + return _M_insert_(__x, __y, __v); } template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert_unique(const_iterator __position, const _Val& __v) + _M_insert_unique_(const_iterator __position, const _Val& __v) { // end() if (__position._M_node == _M_end()) @@ -1060,9 +1060,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (size() > 0 && _M_impl._M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) - return _M_insert(0, _M_rightmost(), __v); + return _M_insert_(0, _M_rightmost(), __v); else - return const_iterator(_M_insert_unique(__v).first); + return _M_insert_unique(__v).first; } else if (_M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) @@ -1070,18 +1070,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // First, try before... const_iterator __before = __position; if (__position._M_node == _M_leftmost()) // begin() - return _M_insert(_M_leftmost(), _M_leftmost(), __v); + return _M_insert_(_M_leftmost(), _M_leftmost(), __v); else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), _KeyOfValue()(__v))) { if (_S_right(__before._M_node) == 0) - return _M_insert(0, __before._M_node, __v); + return _M_insert_(0, __before._M_node, __v); else - return _M_insert(__position._M_node, - __position._M_node, __v); + return _M_insert_(__position._M_node, + __position._M_node, __v); } else - return const_iterator(_M_insert_unique(__v).first); + return _M_insert_unique(__v).first; } else if (_M_impl._M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) @@ -1089,27 +1089,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // ... then try after. const_iterator __after = __position; if (__position._M_node == _M_rightmost()) - return _M_insert(0, _M_rightmost(), __v); + return _M_insert_(0, _M_rightmost(), __v); else if (_M_impl._M_key_compare(_KeyOfValue()(__v), _S_key((++__after)._M_node))) { if (_S_right(__position._M_node) == 0) - return _M_insert(0, __position._M_node, __v); + return _M_insert_(0, __position._M_node, __v); else - return _M_insert(__after._M_node, __after._M_node, __v); + return _M_insert_(__after._M_node, __after._M_node, __v); } else - return const_iterator(_M_insert_unique(__v).first); + return _M_insert_unique(__v).first; } else - return __position; // Equivalent keys. + // Equivalent keys. + return iterator(static_cast<_Link_type> + (const_cast<_Base_ptr>(__position._M_node))); } template typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert_equal(iterator __position, const _Val& __v) + _M_insert_equal_(const_iterator __position, const _Val& __v) { // end() if (__position._M_node == _M_end()) @@ -1117,7 +1119,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (size() > 0 && !_M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) - return _M_insert(0, _M_rightmost(), __v); + return _M_insert_(0, _M_rightmost(), __v); else return _M_insert_equal(__v); } @@ -1125,91 +1127,37 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _KeyOfValue()(__v))) { // First, try before... - iterator __before = __position; - if (__position._M_node == _M_leftmost()) // begin() - return _M_insert(_M_leftmost(), _M_leftmost(), __v); - else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key((--__before)._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); - } - else - return _M_insert_equal(__v); - } - else - { - // ... then try after. - iterator __after = __position; - if (__position._M_node == _M_rightmost()) - return _M_insert(0, _M_rightmost(), __v); - else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), - _KeyOfValue()(__v))) - { - if (_S_right(__position._M_node) == 0) - return _M_insert(0, __position._M_node, __v); - else - return _M_insert(__after._M_node, __after._M_node, __v); - } - else - return _M_insert_equal_lower(__v); - } - } - - template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_insert_equal(const_iterator __position, const _Val& __v) - { - // end() - if (__position._M_node == _M_end()) - { - if (size() > 0 - && !_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(_M_rightmost()))) - return _M_insert(0, _M_rightmost(), __v); - else - return const_iterator(_M_insert_equal(__v)); - } - else if (!_M_impl._M_key_compare(_S_key(__position._M_node), - _KeyOfValue()(__v))) - { - // First, try before... const_iterator __before = __position; if (__position._M_node == _M_leftmost()) // begin() - return _M_insert(_M_leftmost(), _M_leftmost(), __v); + return _M_insert_(_M_leftmost(), _M_leftmost(), __v); else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), _S_key((--__before)._M_node))) { if (_S_right(__before._M_node) == 0) - return _M_insert(0, __before._M_node, __v); + return _M_insert_(0, __before._M_node, __v); else - return _M_insert(__position._M_node, - __position._M_node, __v); + return _M_insert_(__position._M_node, + __position._M_node, __v); } else - return const_iterator(_M_insert_equal(__v)); + return _M_insert_equal(__v); } else { // ... then try after. const_iterator __after = __position; if (__position._M_node == _M_rightmost()) - return _M_insert(0, _M_rightmost(), __v); + return _M_insert_(0, _M_rightmost(), __v); else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), _KeyOfValue()(__v))) { if (_S_right(__position._M_node) == 0) - return _M_insert(0, __position._M_node, __v); + return _M_insert_(0, __position._M_node, __v); else - return _M_insert(__after._M_node, __after._M_node, __v); + return _M_insert_(__after._M_node, __after._M_node, __v); } else - return const_iterator(_M_insert_equal_lower(__v)); + return _M_insert_equal_lower(__v); } } @@ -1218,10 +1166,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template void _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: - _M_insert_equal(_II __first, _II __last) + _M_insert_unique(_II __first, _II __last) { for (; __first != __last; ++__first) - _M_insert_equal(end(), *__first); + _M_insert_unique_(end(), *__first); } template void _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: - _M_insert_unique(_II __first, _II __last) + _M_insert_equal(_II __first, _II __last) { for (; __first != __last; ++__first) - _M_insert_unique(end(), *__first); + _M_insert_equal_(end(), *__first); } template(_Rb_tree_rebalance_for_erase (__position._M_node, this->_M_impl._M_header)); - destroy_node(__y); + _M_destroy_node(__y); --_M_impl._M_node_count; } @@ -1259,7 +1207,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) static_cast<_Link_type>(_Rb_tree_rebalance_for_erase (const_cast<_Base_ptr>(__position._M_node), this->_M_impl._M_header)); - destroy_node(__y); + _M_destroy_node(__y); --_M_impl._M_node_count; } @@ -1275,58 +1223,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __old_size - size(); } - template - typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type - _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: - _M_copy(_Const_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); - __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); - } - } - catch(...) - { - _M_erase(__top); - __throw_exception_again; - } - return __top; - } - - template - void - _Rb_tree<_Key, _Val, _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 @@ -1369,16 +1265,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: find(const _Key& __k) { - _Link_type __x = _M_begin(); // Current node. - _Link_type __y = _M_end(); // Last node which is not less than __k. - - while (__x != 0) - if (!_M_impl._M_key_compare(_S_key(__x), __k)) - __y = __x, __x = _S_left(__x); - else - __x = _S_right(__x); - - iterator __j = iterator(__y); + iterator __j = iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); return (__j == end() || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; @@ -1390,20 +1277,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: find(const _Key& __k) const { - _Const_Link_type __x = _M_begin(); // Current node. - _Const_Link_type __y = _M_end(); // Last node which is not less than __k. - - while (__x != 0) - { - if (!_M_impl._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_impl._M_key_compare(__k, - _S_key(__j._M_node))) ? end() : __j; + const_iterator __j = const_iterator(_M_lower_bound(_M_begin(), + _M_end(), __k)); + return (__j == end() + || _M_impl._M_key_compare(__k, + _S_key(__j._M_node))) ? end() : __j; } template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - lower_bound(const _Key& __k) - { - _Link_type __x = _M_begin(); // Current node. - _Link_type __y = _M_end(); // Last node which is not less than __k. - - while (__x != 0) - if (!_M_impl._M_key_compare(_S_key(__x), __k)) - __y = __x, __x = _S_left(__x); - else - __x = _S_right(__x); - - return iterator(__y); - } - - template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - lower_bound(const _Key& __k) const - { - _Const_Link_type __x = _M_begin(); // Current node. - _Const_Link_type __y = _M_end(); // Last node which is not less than __k. - - while (__x != 0) - if (!_M_impl._M_key_compare(_S_key(__x), __k)) - __y = __x, __x = _S_left(__x); - else - __x = _S_right(__x); - - return const_iterator(__y); - } - - template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - upper_bound(const _Key& __k) - { - _Link_type __x = _M_begin(); // Current node. - _Link_type __y = _M_end(); // Last node which is greater than __k. - - while (__x != 0) - if (_M_impl._M_key_compare(__k, _S_key(__x))) - __y = __x, __x = _S_left(__x); - else - __x = _S_right(__x); - - return iterator(__y); - } - - template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator - _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - upper_bound(const _Key& __k) const - { - _Const_Link_type __x = _M_begin(); // Current node. - _Const_Link_type __y = _M_end(); // Last node which is greater than __k. - - while (__x != 0) - if (_M_impl._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, -- 2.7.4