This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch]: Separate classes for constant iterators and miscellaneousoptimizations
- From: Gawain Bolton <gbolton at free dot fr>
- To: libstdc++ at gcc dot gnu dot org
- Date: Mon, 04 Aug 2003 01:13:15 +0200
- Subject: [Patch]: Separate classes for constant iterators and miscellaneousoptimizations
- Reply-to: gp dot bolton at computer dot org
This patch introduces new classes for constant iterators for std::list
and the _Rb_tree class which is used to implement the
std::{multi}*{map|set} containers.
The reasons for doing this are:
* code clarity/simplicity
* eliminate need for const_casts
* a single template argument is required for the iterator classes.
o this results in less debug info and clearer error messages
* eliminates need for global comparison functions to compare iterators
o less pollution in std namespace and the code is more readable
The only drawbacks are that there is slightly more code in the header
files and the new const_iterator classes are basically clones of the
iterator class. However, I do not think this is a problem since the
functions are simple one-liners and the code in question is within the
same header file, thus this will not be a maintenance problem.
Here's an example of an error message when erasing using a constant
iterator as provided by the patch:
test.cc: In member function `void test_erase()':
test.cc:375: error: no matching function for call to `std::map<Fred,
unsigned int, std::less<Fred>, std::allocator<std::pair<const Fred,
unsigned
int> > >::erase(std::_Rb_tree_const_iterator<std::pair<const Fred,
unsigned
int> >&)'
Here's the equivalent error message currently given without an explicit
const iterator class:
test.cc: In member function `void test_erase()':
test.cc:375: error: no matching function for call to `std::map<Fred,
unsigned int, std::less<Fred>, std::allocator<std::pair<const Fred,
unsigned
int> > >::erase(std::_Rb_tree_iterator<std::pair<const Fred, unsigned
int>,
const std::pair<const Fred, unsigned int>&, const std::pair<const Fred,
unsigned int>*>&)'
Other changes made by this patch include:
* std:list
o Only erase contents in destructor.
o Eliminated static_casts where possible.
* _Rb_tree class:
o Only erase contents in destructor.
o Eliminate unnecessary initialization in assignment operator.
o Optimize for the nominal case by not checking whether
container is empty in clear().
o Re-order test in _M_insert() to improve performance.
o Move initialization of new node's left & right pointers to
src/stl_tree.cc to where new node's colour is initialized
and to reduce the amount of inline code.
o Use _M_leftmost() and _M_end() to improve readability where
appropriate.
This patch has been tested on i686-pc-linux-gnu. Performance tests were
done using Bjarne Stroustrup's Standard Container Benchmark as found here:
http://groups.google.fr/groups?q=standard+container+benchmark+group:comp.lang.c%2B%2B.moderated&hl=en&lr=lang_en|lang_fr&ie=UTF-8&group=comp.lang.c%2B%2B.moderated&selm=HFnqCB.6Js%40research.att.com&rnum=1
No changes were made to the benchmark code. It was compiled with -O2
and executed several times with and without the patch as the numbers do
vary a bit from one run to the next. The data sets reported are neither
the best nor worst obtained in either case.
Only the performance of list, set and multiset is changed by this patch
so only the last three columns of information are of interest concerning
this patch.
Here are the numbers using mainline CVS:
size array vector(1) vector(2) deque list set multiset
10 3.06 3.19 3.25 5.85 13.63 5.69 10.04
100 1.89 1.89 1.94 3.54 7.26 3.97 6.14
1000 1.82 1.78 1.94 3.14 6.38 3.55 5.62
10000 1.86 1.90 2.06 3.17 7.43 4.20 6.75
100000 2.12 2.21 2.26 3.23 9.19 6.44 8.88
(1) with pointers
(2) with iterators
Here are the numbers using the patch:
size array vector(1) vector(2) deque list set multiset
10 3.15 3.16 3.31 5.64 10.42 5.73 9.84
100 1.85 1.87 1.95 3.48 5.13 3.90 6.07
1000 1.79 1.78 1.97 3.21 4.68 3.41 5.41
10000 1.86 1.85 2.04 3.20 5.44 3.96 6.24
100000 2.05 2.04 2.17 3.23 7.53 5.83 8.40
(1) with pointers
(2) with iterators
Cheers,
Gawain
--
Gawain Bolton
Coignieres, France
PGP Info: Key server: http://wwwkeys.pgp.net
Key id: 6EBEDEA6
Fingerprint: 65C0 0030 21D1 7A01 546A E7DB D60F 47E0 6EBE DEA6
Index: include/bits/list.tcc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/list.tcc,v
retrieving revision 1.7
diff -c -3 -p -r1.7 list.tcc
*** include/bits/list.tcc 6 Jul 2003 00:58:52 -0000 1.7
--- include/bits/list.tcc 3 Aug 2003 20:16:16 -0000
*************** namespace std
*** 77,84 ****
std::_Destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
- this->_M_node._M_next = &this->_M_node;
- this->_M_node._M_prev = &this->_M_node;
}
template<typename _Tp, typename _Alloc>
--- 77,82 ----
Index: include/bits/stl_list.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_list.h,v
retrieving revision 1.30
diff -c -3 -p -r1.30 stl_list.h
*** include/bits/stl_list.h 15 Jul 2003 06:15:57 -0000 1.30
--- include/bits/stl_list.h 3 Aug 2003 20:16:17 -0000
*************** namespace std
*** 86,167 ****
/**
! * @if maint
! * @brief Common part of a list::iterator.
*
! * A simple type to walk a doubly-linked list. All operations here should
! * be self-explanatory after taking any decent introductory data structures
! * course.
* @endif
*/
! struct _List_iterator_base
{
! typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef bidirectional_iterator_tag iterator_category;
! /// The only member points to the %list element.
! _List_node_base* _M_node;
!
! _List_iterator_base(_List_node_base* __x)
: _M_node(__x)
{ }
! _List_iterator_base()
! { }
! /// Walk the %list forward.
! void
! _M_incr()
! { _M_node = _M_node->_M_next; }
! /// Walk the %list backward.
! void
! _M_decr()
! { _M_node = _M_node->_M_prev; }
bool
! operator==(const _List_iterator_base& __x) const
{ return _M_node == __x._M_node; }
!
bool
! operator!=(const _List_iterator_base& __x) const
{ return _M_node != __x._M_node; }
};
/**
! * @brief A list::iterator.
! *
! * In addition to being used externally, a list holds one of these
! * internally, pointing to the sequence of data.
*
* @if maint
* All the functions are op overloads.
* @endif
*/
! template<typename _Tp, typename _Ref, typename _Ptr>
! struct _List_iterator : public _List_iterator_base
{
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
! typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
!
! typedef _Tp value_type;
! typedef _Ptr pointer;
! typedef _Ref reference;
! typedef _List_node<_Tp> _Node;
! _List_iterator(_Node* __x)
! : _List_iterator_base(__x)
! { }
! _List_iterator()
{ }
!
! _List_iterator(const iterator& __x)
! : _List_iterator_base(__x._M_node)
{ }
!
reference
operator*() const
{ return static_cast<_Node*>(_M_node)->_M_data; }
--- 86,199 ----
/**
! * @brief A list::iterator.
*
! * @if maint
! * All the functions are op overloads.
* @endif
*/
! template<typename _Tp>
! struct _List_iterator
{
! typedef _List_iterator<_Tp> _Self;
! typedef _List_node<_Tp> _Node;
!
typedef ptrdiff_t difference_type;
typedef bidirectional_iterator_tag iterator_category;
+ typedef _Tp value_type;
+ typedef _Tp* pointer;
+ typedef _Tp& reference;
! _List_iterator()
! { }
!
! _List_iterator(_List_node_base* __x)
: _M_node(__x)
{ }
+
+ reference
+ operator*() const
+ { return static_cast<_Node*>(_M_node)->_M_data; }
+ // Must downcast from List_node_base to _List_node to get to _M_data.
! pointer
! operator->() const
! { return &static_cast<_Node*>(_M_node)->_M_data; }
! _Self&
! operator++()
! {
! _M_node = _M_node->_M_next;
! return *this;
! }
! _Self
! operator++(int)
! {
! _Self __tmp = *this;
! _M_node = _M_node->_M_next;
! return __tmp;
! }
!
! _Self&
! operator--()
! {
! _M_node = _M_node->_M_prev;
! return *this;
! }
+ _Self
+ operator--(int)
+ {
+ _Self __tmp = *this;
+ _M_node = _M_node->_M_prev;
+ return __tmp;
+ }
+
bool
! operator==(const _Self& __x) const
{ return _M_node == __x._M_node; }
!
bool
! operator!=(const _Self& __x) const
{ return _M_node != __x._M_node; }
+
+ // The only member points to the %list element.
+ _List_node_base* _M_node;
};
+
/**
! * @brief A list::const_iterator.
*
* @if maint
* All the functions are op overloads.
* @endif
*/
! template<typename _Tp>
! struct _List_const_iterator
{
! typedef _List_const_iterator<_Tp> _Self;
! typedef const _List_node<_Tp> _Node;
! typedef _List_iterator<_Tp> iterator;
! typedef ptrdiff_t difference_type;
! typedef bidirectional_iterator_tag iterator_category;
! typedef _Tp value_type;
! typedef const _Tp* pointer;
! typedef const _Tp& reference;
! _List_const_iterator()
{ }
!
! _List_const_iterator(const _List_node_base* __x)
! : _M_node(__x)
{ }
!
! _List_const_iterator(const iterator& __x)
! : _M_node(__x._M_node)
! { }
!
reference
operator*() const
{ return static_cast<_Node*>(_M_node)->_M_data; }
*************** namespace std
*** 169,180 ****
pointer
operator->() const
! { return &(operator*()); }
_Self&
operator++()
{
! this->_M_incr();
return *this;
}
--- 201,212 ----
pointer
operator->() const
! { return &static_cast<_Node*>(_M_node)->_M_data; }
_Self&
operator++()
{
! _M_node = _M_node->_M_next;
return *this;
}
*************** namespace std
*** 182,195 ****
operator++(int)
{
_Self __tmp = *this;
! this->_M_incr();
return __tmp;
}
_Self&
operator--()
{
! this->_M_decr();
return *this;
}
--- 214,227 ----
operator++(int)
{
_Self __tmp = *this;
! _M_node = _M_node->_M_next;
return __tmp;
}
_Self&
operator--()
{
! _M_node = _M_node->_M_prev;
return *this;
}
*************** namespace std
*** 197,208 ****
operator--(int)
{
_Self __tmp = *this;
! this->_M_decr();
return __tmp;
}
};
!
!
/// @if maint Primary default version. @endif
/**
* @if maint
--- 229,251 ----
operator--(int)
{
_Self __tmp = *this;
! _M_node = _M_node->_M_prev;
return __tmp;
}
+
+ bool
+ operator==(const _Self& __x) const
+ { return _M_node == __x._M_node; }
+
+ bool
+ operator!=(const _Self& __x) const
+ { return _M_node != __x._M_node; }
+
+ // The only member points to the %list element.
+ const _List_node_base* _M_node;
};
!
!
/// @if maint Primary default version. @endif
/**
* @if maint
*************** namespace std
*** 301,308 ****
_List_base(const allocator_type& __a)
: _Base(__a)
{
! this->_M_node._M_next = &this->_M_node;
! this->_M_node._M_prev = &this->_M_node;
}
// This is what actually destroys the list.
--- 344,350 ----
_List_base(const allocator_type& __a)
: _Base(__a)
{
! __init();
}
// This is what actually destroys the list.
*************** namespace std
*** 313,318 ****
--- 355,367 ----
void
__clear();
+
+ void
+ __init()
+ {
+ this->_M_node._M_next = &this->_M_node;
+ this->_M_node._M_prev = &this->_M_node;
+ }
};
*************** namespace std
*** 372,379 ****
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef value_type& reference;
--- 421,428 ----
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
! typedef _List_iterator<_Tp> iterator;
! typedef _List_const_iterator<_Tp> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef value_type& reference;
*************** namespace std
*** 565,592 ****
* %list. Iteration is done in ordinary element order.
*/
iterator
! begin() { return static_cast<_Node*>(this->_M_node._M_next); }
/**
* Returns a read-only (constant) iterator that points to the first element
* in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! begin() const { return static_cast<_Node*>(this->_M_node._M_next); }
/**
* Returns a read/write iterator that points one past the last element in
* the %list. Iteration is done in ordinary element order.
*/
iterator
! end() { return static_cast<_Node*>(&this->_M_node); }
/**
* Returns a read-only (constant) iterator that points one past the last
* element in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! end() const { return const_cast<_Node *>(static_cast<const _Node*>(&this->_M_node)); }
/**
* Returns a read/write reverse iterator that points to the last element in
--- 614,641 ----
* %list. Iteration is done in ordinary element order.
*/
iterator
! begin() { return this->_M_node._M_next; }
/**
* Returns a read-only (constant) iterator that points to the first element
* in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! begin() const { return this->_M_node._M_next; }
/**
* Returns a read/write iterator that points one past the last element in
* the %list. Iteration is done in ordinary element order.
*/
iterator
! end() { return &this->_M_node; }
/**
* Returns a read-only (constant) iterator that points one past the last
* element in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! end() const { return &this->_M_node; }
/**
* Returns a read/write reverse iterator that points to the last element in
*************** namespace std
*** 861,867 ****
* the user's responsibilty.
*/
void
! clear() { _Base::__clear(); }
// [23.2.2.4] list operations
/**
--- 910,920 ----
* the user's responsibilty.
*/
void
! clear()
! {
! _Base::__clear();
! _Base::__init();
! }
// [23.2.2.4] list operations
/**
Index: include/bits/stl_tree.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.28
diff -c -3 -p -r1.28 stl_tree.h
*** include/bits/stl_tree.h 30 Jul 2003 15:01:58 -0000 1.28
--- include/bits/stl_tree.h 3 Aug 2003 20:16:17 -0000
*************** namespace std
*** 141,176 ****
_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x);
_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x);
! template<typename _Val, typename _Ref, typename _Ptr>
struct _Rb_tree_iterator
{
! typedef _Val value_type;
! typedef _Ref reference;
! typedef _Ptr pointer;
! typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator;
! typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*>
! const_iterator;
! typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
typedef bidirectional_iterator_tag iterator_category;
! typedef ptrdiff_t difference_type;
! typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self;
! typedef _Rb_tree_node<_Val>* _Link_type;
! typedef const _Rb_tree_node<_Val>* _Const_Link_type;
_Rb_tree_iterator() {}
_Rb_tree_iterator(_Link_type __x)
: _M_node(__x) {}
- _Rb_tree_iterator(_Const_Link_type __x)
- : _M_node(const_cast<_Link_type>(__x)) {}
-
- _Rb_tree_iterator(const iterator& __it)
- : _M_node(__it._M_node) {}
-
reference
operator*() const
{ return static_cast<_Link_type>(_M_node)->_M_value_field; }
--- 141,174 ----
_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x);
+ const _Rb_tree_node_base*
+ _Rb_tree_increment(const _Rb_tree_node_base* __x);
+
_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x);
! const _Rb_tree_node_base*
! _Rb_tree_decrement(const _Rb_tree_node_base* __x);
!
! template<typename _Tp>
struct _Rb_tree_iterator
{
! typedef _Tp value_type;
! typedef _Tp& reference;
! typedef _Tp* pointer;
!
typedef bidirectional_iterator_tag iterator_category;
! typedef ptrdiff_t difference_type;
!
! typedef _Rb_tree_iterator<_Tp> _Self;
! typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
! typedef _Rb_tree_node<_Tp>* _Link_type;
_Rb_tree_iterator() {}
_Rb_tree_iterator(_Link_type __x)
: _M_node(__x) {}
reference
operator*() const
{ return static_cast<_Link_type>(_M_node)->_M_value_field; }
*************** namespace std
*** 209,252 ****
return __tmp;
}
_Base_ptr _M_node;
};
! template<typename _Val, typename _Ref, typename _Ptr>
! inline bool
! operator==(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
! const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y)
! { return __x._M_node == __y._M_node; }
! template<typename _Val>
! inline bool
! operator==(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
! const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y)
! { return __x._M_node == __y._M_node; }
! template<typename _Val>
! inline bool
! operator==(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
! const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y)
! { return __x._M_node == __y._M_node; }
! template<typename _Val, typename _Ref, typename _Ptr>
! inline bool
! operator!=(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
! const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y)
! { return __x._M_node != __y._M_node; }
! template<typename _Val>
! inline bool
! operator!=(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
! const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y)
! { return __x._M_node != __y._M_node; }
! template<typename _Val>
! inline bool
! operator!=(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
! const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y)
! { return __x._M_node != __y._M_node; }
void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x, _Rb_tree_node_base*& __root);
--- 207,295 ----
return __tmp;
}
+ bool
+ operator==(const _Self& __x) const
+ { return _M_node == __x._M_node; }
+
+ bool
+ operator!=(const _Self& __x) const
+ { return _M_node != __x._M_node; }
+
_Base_ptr _M_node;
};
! template<typename _Tp>
! struct _Rb_tree_const_iterator
! {
! typedef _Tp value_type;
! typedef const _Tp& reference;
! typedef const _Tp* pointer;
! typedef _Rb_tree_iterator<_Tp> iterator;
! typedef bidirectional_iterator_tag iterator_category;
! typedef ptrdiff_t difference_type;
! typedef _Rb_tree_const_iterator<_Tp> _Self;
! typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
! typedef const _Rb_tree_node<_Tp>* _Link_type;
!
! _Rb_tree_const_iterator() {}
! _Rb_tree_const_iterator(_Link_type __x)
! : _M_node(__x) {}
! _Rb_tree_const_iterator(const iterator& __it)
! : _M_node(__it._M_node) {}
!
! reference
! operator*() const
! { return static_cast<_Link_type>(_M_node)->_M_value_field; }
!
! pointer
! operator->() const
! { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
!
! _Self&
! operator++()
! {
! _M_node = _Rb_tree_increment(_M_node);
! return *this;
! }
!
! _Self
! operator++(int)
! {
! _Self __tmp = *this;
! _M_node = _Rb_tree_increment(_M_node);
! return __tmp;
! }
!
! _Self&
! operator--()
! {
! _M_node = _Rb_tree_decrement(_M_node);
! return *this;
! }
!
! _Self
! operator--(int)
! {
! _Self __tmp = *this;
! _M_node = _Rb_tree_decrement(_M_node);
! return __tmp;
! }
!
! bool
! operator==(const _Self& __x) const
! { return _M_node == __x._M_node; }
!
! bool
! operator!=(const _Self& __x) const
! { return _M_node != __x._M_node; }
!
! _Base_ptr _M_node;
! };
void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x, _Rb_tree_node_base*& __root);
*************** namespace std
*** 465,476 ****
{ return _Rb_tree_node_base::_S_maximum(__x); }
public:
! typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
! typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
! const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator;
private:
iterator
--- 508,518 ----
{ return _Rb_tree_node_base::_S_maximum(__x); }
public:
! typedef _Rb_tree_iterator<value_type> iterator;
! typedef _Rb_tree_const_iterator<value_type> const_iterator;
+ typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
private:
iterator
*************** namespace std
*** 512,518 ****
_M_node_count = __x._M_node_count;
}
! ~_Rb_tree() { clear(); }
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
--- 554,560 ----
_M_node_count = __x._M_node_count;
}
! ~_Rb_tree() { _M_erase(_M_begin()); }
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
*************** namespace std
*** 601,618 ****
void
erase(const key_type* __first, const key_type* __last);
! void
! clear()
{
! if (_M_node_count != 0)
! {
! _M_erase(_M_begin());
! _M_leftmost() = _M_end();
! _M_root() = 0;
! _M_rightmost() = _M_end();
! _M_node_count = 0;
! }
! }
// Set operations.
iterator
--- 643,657 ----
void
erase(const key_type* __first, const key_type* __last);
! void
! clear()
{
! _M_erase(_M_begin());
! _M_leftmost() = _M_end();
! _M_root() = 0;
! _M_rightmost() = _M_end();
! _M_node_count = 0;
! }
// Set operations.
iterator
*************** namespace std
*** 712,726 ****
{
// 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_end();
! _M_rightmost() = _M_end();
! }
! else
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
--- 751,758 ----
{
// Note that _Key may be a constant type.
clear();
_M_key_compare = __x._M_key_compare;
! if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
*************** namespace std
*** 739,753 ****
{
_Link_type __x = static_cast<_Link_type>(__x_);
_Link_type __y = static_cast<_Link_type>(__y_);
! _Link_type __z;
! if (__y == &this->_M_header || __x != 0 ||
! _M_key_compare(_KeyOfValue()(__v), _S_key(__y)))
{
- __z = _M_create_node(__v);
__y->_M_left = __z; // also makes _M_leftmost() = __z
// when __y == &_M_header
! if (__y == &this->_M_header)
{
_M_root() = __z;
_M_rightmost() = __z;
--- 771,784 ----
{
_Link_type __x = static_cast<_Link_type>(__x_);
_Link_type __y = static_cast<_Link_type>(__y_);
! _Link_type __z = _M_create_node(__v);
! if (__x != 0 || _M_key_compare(_KeyOfValue()(__v), _S_key(__y)) ||
! __y == _M_end())
{
__y->_M_left = __z; // also makes _M_leftmost() = __z
// when __y == &_M_header
! if (__y == _M_end())
{
_M_root() = __z;
_M_rightmost() = __z;
*************** namespace std
*** 757,772 ****
}
else
{
- __z = _M_create_node(__v);
__y->_M_right = __z;
// Maintain _M_rightmost() pointing to max node.
if (__y == _M_rightmost())
_M_rightmost() = __z;
}
__z->_M_parent = __y;
! __z->_M_left = 0;
! __z->_M_right = 0;
! _Rb_tree_rebalance(__z, this->_M_header._M_parent);
++_M_node_count;
return iterator(__z);
}
--- 788,800 ----
}
else
{
__y->_M_right = __z;
// Maintain _M_rightmost() pointing to max node.
if (__y == _M_rightmost())
_M_rightmost() = __z;
}
__z->_M_parent = __y;
! _Rb_tree_rebalance(__z, _M_root());
++_M_node_count;
return iterator(__z);
}
*************** namespace std
*** 867,873 ****
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (__position._M_node == this->_M_header._M_left)
{
// begin()
if (size() > 0 &&
--- 895,901 ----
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_leftmost())
{
// begin()
if (size() > 0 &&
*************** namespace std
*** 877,883 ****
else
return insert_unique(__v).first;
}
! else if (__position._M_node == &this->_M_header)
{
// end()
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
--- 905,911 ----
else
return insert_unique(__v).first;
}
! else if (__position._M_node == _M_end())
{
// end()
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
*************** namespace std
*** 909,915 ****
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (__position._M_node == this->_M_header._M_left)
{
// begin()
if (size() > 0 &&
--- 937,943 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_leftmost())
{
// begin()
if (size() > 0 &&
*************** namespace std
*** 919,925 ****
else
return insert_equal(__v);
}
! else if (__position._M_node == &this->_M_header)
{
// end()
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
--- 947,953 ----
else
return insert_equal(__v);
}
! else if (__position._M_node == _M_end())
{
// end()
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
*************** namespace std
*** 1219,1226 ****
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
! this->_M_header._M_left == &this->_M_header &&
! this->_M_header._M_right == &this->_M_header;
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
--- 1247,1254 ----
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
! this->_M_header._M_left == _M_end() &&
! this->_M_header._M_right == _M_end();
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
Index: src/stl_tree.cc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/src/stl_tree.cc,v
retrieving revision 1.2
diff -c -3 -p -r1.2 stl_tree.cc
*** src/stl_tree.cc 30 Jul 2003 15:01:58 -0000 1.2
--- src/stl_tree.cc 3 Aug 2003 20:16:17 -0000
*************** namespace std
*** 82,87 ****
--- 82,93 ----
return __x;
}
+ const _Rb_tree_node_base*
+ _Rb_tree_increment(const _Rb_tree_node_base* __x)
+ {
+ return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
+ }
+
_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x)
{
*************** namespace std
*** 108,113 ****
--- 114,125 ----
return __x;
}
+ const _Rb_tree_node_base*
+ _Rb_tree_decrement(const _Rb_tree_node_base* __x)
+ {
+ return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
+ }
+
void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root)
*************** namespace std
*** 153,158 ****
--- 165,172 ----
void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
+ __x->_M_left = 0;
+ __x->_M_right = 0;
__x->_M_color = _S_red;
while (__x != __root