This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] First part of 29385
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Cc: gp dot bolton at computer dot org
- Date: Fri, 24 Nov 2006 18:23:58 +0100
- Subject: [Patch] First part of 29385
Hi,
the below is the first part, that is, integration of Gawain Bolton' work
(a few names adjusted to not cause binary level incompatibilities) + a
preliminary clean-up for the second half, introducing the _M_lower_bound
and _M_upper_bound helpers, called by lower_bound, upper_bound and find
(and soon be by equal_range).
Tested x86/x86_64-linux, will commit later today.
Paolo.
////////////////
2006-11-24 Paolo Carlini <pcarlini@suse.de>
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-24 Gawain Bolton <gp.bolton@computer.org>
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.
Index: include/bits/stl_map.h
===================================================================
--- include/bits/stl_map.h (revision 119149)
+++ include/bits/stl_map.h (working copy)
@@ -423,7 +423,7 @@
*/
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.
Index: include/bits/stl_set.h
===================================================================
--- include/bits/stl_set.h (revision 119149)
+++ include/bits/stl_set.h (working copy)
@@ -329,7 +329,7 @@
*/
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.
Index: include/bits/stl_multimap.h
===================================================================
--- include/bits/stl_multimap.h (revision 119149)
+++ include/bits/stl_multimap.h (working copy)
@@ -361,7 +361,7 @@
*/
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.
Index: include/bits/stl_multiset.h
===================================================================
--- include/bits/stl_multiset.h (revision 119149)
+++ include/bits/stl_multiset.h (working copy)
@@ -316,7 +316,7 @@
*/
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.
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h (revision 119149)
+++ include/bits/stl_tree.h (working copy)
@@ -306,14 +306,6 @@
{ 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,
@@ -546,16 +538,16 @@
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 @@
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,23 +662,12 @@
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);
+ _M_insert_unique_(const_iterator __position, const value_type& __x);
iterator
- _M_insert_unique(iterator __position, const value_type& __x);
+ _M_insert_equal_(const_iterator __position, const value_type& __x);
- const_iterator
- _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);
-
template<typename _InputIterator>
void
_M_insert_unique(_InputIterator __first, _InputIterator __last);
@@ -717,31 +706,35 @@
// 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<iterator,iterator>
- equal_range(const key_type& __x);
+ pair<iterator, iterator>
+ equal_range(const key_type& __k);
pair<const_iterator, const_iterator>
- equal_range(const key_type& __x) const;
+ equal_range(const key_type& __k) const;
// Debugging.
bool
@@ -829,7 +822,7 @@
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 @@
_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,59 +857,105 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- 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 _Key, typename _Val, typename _KoV,
+ typename _Compare, typename _Alloc>
+ 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 _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- 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);
+ destroy_node(__x);
+ __x = __y;
}
- return _M_insert(__x, __y, __v);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
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 _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
+ 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<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
void
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
@@ -983,11 +1023,11 @@
iterator __j = iterator(__y);
if (__comp)
if (__j == begin())
- return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
+ return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
else
--__j;
if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
- return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
+ return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
return pair<iterator, bool>(__j, false);
}
@@ -995,64 +1035,24 @@
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())
+ _Link_type __x = _M_begin();
+ _Link_type __y = _M_end();
+ while (__x != 0)
{
- 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;
+ __y = __x;
+ __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
+ _S_left(__x) : _S_right(__x);
}
- 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)))
- {
- // ... 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;
- }
- else
- return __position; // Equivalent keys.
+ return _M_insert_(__x, __y, __v);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- 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 @@
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 @@
// 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 @@
// ... 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 _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
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 @@
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,17 +1127,17 @@
_KeyOfValue()(__v)))
{
// First, try before...
- iterator __before = __position;
+ 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 _M_insert_equal(__v);
@@ -1143,85 +1145,31 @@
else
{
// ... then try after.
- iterator __after = __position;
+ 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 _M_insert_equal_lower(__v);
}
}
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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);
- 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 const_iterator(_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);
- 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 const_iterator(_M_insert_equal_lower(__v));
- }
- }
-
template<typename _Key, typename _Val, typename _KoV,
typename _Cmp, typename _Alloc>
template<class _II>
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<typename _Key, typename _Val, typename _KoV,
@@ -1229,10 +1177,10 @@
template<class _II>
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<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1275,62 +1223,10 @@
return __old_size - size();
}
- template<typename _Key, typename _Val, typename _KoV,
- typename _Compare, typename _Alloc>
- 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<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
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<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- void
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
erase(iterator __first, iterator __last)
{
if (__first == begin() && __last == end())
@@ -1369,16 +1265,7 @@
_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 @@
_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 _Key, typename _Val, typename _KeyOfValue,
@@ -1419,78 +1297,6 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- 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 _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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 _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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 _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- 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<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
inline
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator,