stl_tree.h

Go to the documentation of this file.
00001 // RB tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1996,1997
00033  * Silicon Graphics Computer Systems, Inc.
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Silicon Graphics makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1994
00045  * Hewlett-Packard Company
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Hewlett-Packard Company makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  *
00055  *
00056  */
00057 
00058 /** @file stl_tree.h
00059  *  This is an internal header file, included by other library headers.
00060  *  You should not attempt to use it directly.
00061  */
00062 
00063 #ifndef _TREE_H
00064 #define _TREE_H 1
00065 
00066 #include <bits/stl_algobase.h>
00067 #include <bits/allocator.h>
00068 #include <bits/stl_construct.h>
00069 #include <bits/stl_function.h>
00070 #include <bits/cpp_type_traits.h>
00071 
00072 namespace std
00073 {
00074   // Red-black tree class, designed for use in implementing STL
00075   // associative containers (set, multiset, map, and multimap). The
00076   // insertion and deletion algorithms are based on those in Cormen,
00077   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
00078   // 1990), except that
00079   //
00080   // (1) the header cell is maintained with links not only to the root
00081   // but also to the leftmost node of the tree, to enable constant
00082   // time begin(), and to the rightmost node of the tree, to enable
00083   // linear time performance when used with the generic set algorithms
00084   // (set_union, etc.)
00085   // 
00086   // (2) when a node being deleted has two children its successor node
00087   // is relinked into its place, rather than copied, so that the only
00088   // iterators invalidated are those referring to the deleted node.
00089 
00090   enum _Rb_tree_color { _S_red = false, _S_black = true };
00091 
00092   struct _Rb_tree_node_base
00093   {
00094     typedef _Rb_tree_node_base* _Base_ptr;
00095     typedef const _Rb_tree_node_base* _Const_Base_ptr;
00096 
00097     _Rb_tree_color  _M_color;
00098     _Base_ptr       _M_parent;
00099     _Base_ptr       _M_left;
00100     _Base_ptr       _M_right;
00101 
00102     static _Base_ptr
00103     _S_minimum(_Base_ptr __x)
00104     {
00105       while (__x->_M_left != 0) __x = __x->_M_left;
00106       return __x;
00107     }
00108 
00109     static _Const_Base_ptr
00110     _S_minimum(_Const_Base_ptr __x)
00111     {
00112       while (__x->_M_left != 0) __x = __x->_M_left;
00113       return __x;
00114     }
00115 
00116     static _Base_ptr
00117     _S_maximum(_Base_ptr __x)
00118     {
00119       while (__x->_M_right != 0) __x = __x->_M_right;
00120       return __x;
00121     }
00122 
00123     static _Const_Base_ptr
00124     _S_maximum(_Const_Base_ptr __x)
00125     {
00126       while (__x->_M_right != 0) __x = __x->_M_right;
00127       return __x;
00128     }
00129   };
00130 
00131   template<typename _Val>
00132     struct _Rb_tree_node : public _Rb_tree_node_base
00133     {
00134       typedef _Rb_tree_node<_Val>* _Link_type;
00135       _Val _M_value_field;
00136     };
00137 
00138   _Rb_tree_node_base*
00139   _Rb_tree_increment(_Rb_tree_node_base* __x);
00140 
00141   const _Rb_tree_node_base*
00142   _Rb_tree_increment(const _Rb_tree_node_base* __x);
00143 
00144   _Rb_tree_node_base*
00145   _Rb_tree_decrement(_Rb_tree_node_base* __x);
00146 
00147   const _Rb_tree_node_base*
00148   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
00149 
00150   template<typename _Tp>
00151     struct _Rb_tree_iterator
00152     {
00153       typedef _Tp  value_type;
00154       typedef _Tp& reference;
00155       typedef _Tp* pointer;
00156 
00157       typedef bidirectional_iterator_tag iterator_category;
00158       typedef ptrdiff_t                  difference_type;
00159 
00160       typedef _Rb_tree_iterator<_Tp>        _Self;
00161       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00162       typedef _Rb_tree_node<_Tp>*           _Link_type;
00163 
00164       _Rb_tree_iterator()
00165       : _M_node() { }
00166 
00167       _Rb_tree_iterator(_Link_type __x)
00168       : _M_node(__x) { }
00169 
00170       reference
00171       operator*() const
00172       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00173 
00174       pointer
00175       operator->() const
00176       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00177 
00178       _Self&
00179       operator++()
00180       {
00181     _M_node = _Rb_tree_increment(_M_node);
00182     return *this;
00183       }
00184 
00185       _Self
00186       operator++(int)
00187       {
00188     _Self __tmp = *this;
00189     _M_node = _Rb_tree_increment(_M_node);
00190     return __tmp;
00191       }
00192 
00193       _Self&
00194       operator--()
00195       {
00196     _M_node = _Rb_tree_decrement(_M_node);
00197     return *this;
00198       }
00199 
00200       _Self
00201       operator--(int)
00202       {
00203     _Self __tmp = *this;
00204     _M_node = _Rb_tree_decrement(_M_node);
00205     return __tmp;
00206       }
00207 
00208       bool
00209       operator==(const _Self& __x) const
00210       { return _M_node == __x._M_node; }
00211 
00212       bool
00213       operator!=(const _Self& __x) const
00214       { return _M_node != __x._M_node; }
00215 
00216       _Base_ptr _M_node;
00217   };
00218 
00219   template<typename _Tp>
00220     struct _Rb_tree_const_iterator
00221     {
00222       typedef _Tp        value_type;
00223       typedef const _Tp& reference;
00224       typedef const _Tp* pointer;
00225 
00226       typedef _Rb_tree_iterator<_Tp> iterator;
00227 
00228       typedef bidirectional_iterator_tag iterator_category;
00229       typedef ptrdiff_t                  difference_type;
00230 
00231       typedef _Rb_tree_const_iterator<_Tp>        _Self;
00232       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00233       typedef const _Rb_tree_node<_Tp>*           _Link_type;
00234 
00235       _Rb_tree_const_iterator()
00236       : _M_node() { }
00237 
00238       _Rb_tree_const_iterator(_Link_type __x)
00239       : _M_node(__x) { }
00240 
00241       _Rb_tree_const_iterator(const iterator& __it)
00242       : _M_node(__it._M_node) { }
00243 
00244       reference
00245       operator*() const
00246       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00247 
00248       pointer
00249       operator->() const
00250       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00251 
00252       _Self&
00253       operator++()
00254       {
00255     _M_node = _Rb_tree_increment(_M_node);
00256     return *this;
00257       }
00258 
00259       _Self
00260       operator++(int)
00261       {
00262     _Self __tmp = *this;
00263     _M_node = _Rb_tree_increment(_M_node);
00264     return __tmp;
00265       }
00266 
00267       _Self&
00268       operator--()
00269       {
00270     _M_node = _Rb_tree_decrement(_M_node);
00271     return *this;
00272       }
00273 
00274       _Self
00275       operator--(int)
00276       {
00277     _Self __tmp = *this;
00278     _M_node = _Rb_tree_decrement(_M_node);
00279     return __tmp;
00280       }
00281 
00282       bool
00283       operator==(const _Self& __x) const
00284       { return _M_node == __x._M_node; }
00285 
00286       bool
00287       operator!=(const _Self& __x) const
00288       { return _M_node != __x._M_node; }
00289 
00290       _Base_ptr _M_node;
00291     };
00292 
00293   template<typename _Val>
00294     inline bool
00295     operator==(const _Rb_tree_iterator<_Val>& __x,
00296                const _Rb_tree_const_iterator<_Val>& __y)
00297     { return __x._M_node == __y._M_node; }
00298 
00299   template<typename _Val>
00300     inline bool
00301     operator!=(const _Rb_tree_iterator<_Val>& __x,
00302                const _Rb_tree_const_iterator<_Val>& __y)
00303     { return __x._M_node != __y._M_node; }
00304 
00305   void
00306   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
00307                        _Rb_tree_node_base*& __root);
00308 
00309   void
00310   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
00311                         _Rb_tree_node_base*& __root);
00312 
00313   void
00314   _Rb_tree_insert_and_rebalance(const bool __insert_left,
00315                                 _Rb_tree_node_base* __x,
00316                                 _Rb_tree_node_base* __p,
00317                                 _Rb_tree_node_base& __header);
00318 
00319   _Rb_tree_node_base*
00320   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00321                    _Rb_tree_node_base& __header);
00322 
00323 
00324   template<typename _Key, typename _Val, typename _KeyOfValue,
00325            typename _Compare, typename _Alloc = allocator<_Val> >
00326     class _Rb_tree
00327     {
00328       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00329               _Node_allocator;
00330 
00331     protected:
00332       typedef _Rb_tree_node_base* _Base_ptr;
00333       typedef const _Rb_tree_node_base* _Const_Base_ptr;
00334       typedef _Rb_tree_node<_Val> _Rb_tree_node;
00335 
00336     public:
00337       typedef _Key key_type;
00338       typedef _Val value_type;
00339       typedef value_type* pointer;
00340       typedef const value_type* const_pointer;
00341       typedef value_type& reference;
00342       typedef const value_type& const_reference;
00343       typedef _Rb_tree_node* _Link_type;
00344       typedef const _Rb_tree_node* _Const_Link_type;
00345       typedef size_t size_type;
00346       typedef ptrdiff_t difference_type;
00347       typedef _Alloc allocator_type;
00348 
00349       allocator_type 
00350       get_allocator() const
00351       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00352 
00353     protected:
00354       _Rb_tree_node*
00355       _M_get_node()
00356       { return _M_impl._Node_allocator::allocate(1); }
00357 
00358       void
00359       _M_put_node(_Rb_tree_node* __p)
00360       { _M_impl._Node_allocator::deallocate(__p, 1); }
00361 
00362       _Link_type
00363       _M_create_node(const value_type& __x)
00364       {
00365     _Link_type __tmp = _M_get_node();
00366     try
00367       { get_allocator().construct(&__tmp->_M_value_field, __x); }
00368     catch(...)
00369       {
00370         _M_put_node(__tmp);
00371         __throw_exception_again;
00372       }
00373     return __tmp;
00374       }
00375 
00376       _Link_type
00377       _M_clone_node(_Const_Link_type __x)
00378       {
00379     _Link_type __tmp = _M_create_node(__x->_M_value_field);
00380     __tmp->_M_color = __x->_M_color;
00381     __tmp->_M_left = 0;
00382     __tmp->_M_right = 0;
00383     return __tmp;
00384       }
00385 
00386       void
00387       destroy_node(_Link_type __p)
00388       {
00389     get_allocator().destroy(&__p->_M_value_field);
00390     _M_put_node(__p);
00391       }
00392 
00393     protected:
00394       template<typename _Key_compare, 
00395            bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
00396         struct _Rb_tree_impl : public _Node_allocator
00397         {
00398       _Key_compare      _M_key_compare;
00399       _Rb_tree_node_base    _M_header;
00400       size_type         _M_node_count; // Keeps track of size of tree.
00401 
00402       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00403             const _Key_compare& __comp = _Key_compare())
00404       : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), 
00405         _M_node_count(0)
00406       {
00407         this->_M_header._M_color = _S_red;
00408         this->_M_header._M_parent = 0;
00409         this->_M_header._M_left = &this->_M_header;
00410         this->_M_header._M_right = &this->_M_header;
00411       }
00412     };
00413 
00414       // Specialization for _Comparison types that are not capable of
00415       // being base classes / super classes.
00416       template<typename _Key_compare>
00417         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 
00418     {
00419       _Key_compare      _M_key_compare;
00420       _Rb_tree_node_base    _M_header;
00421       size_type         _M_node_count; // Keeps track of size of tree.
00422 
00423       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00424             const _Key_compare& __comp = _Key_compare())
00425       : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00426       { 
00427         this->_M_header._M_color = _S_red;
00428         this->_M_header._M_parent = 0;
00429         this->_M_header._M_left = &this->_M_header;
00430         this->_M_header._M_right = &this->_M_header;
00431       }
00432     };
00433 
00434       _Rb_tree_impl<_Compare> _M_impl;
00435 
00436     protected:
00437       _Base_ptr&
00438       _M_root()
00439       { return this->_M_impl._M_header._M_parent; }
00440 
00441       _Const_Base_ptr
00442       _M_root() const
00443       { return this->_M_impl._M_header._M_parent; }
00444 
00445       _Base_ptr&
00446       _M_leftmost()
00447       { return this->_M_impl._M_header._M_left; }
00448 
00449       _Const_Base_ptr
00450       _M_leftmost() const
00451       { return this->_M_impl._M_header._M_left; }
00452 
00453       _Base_ptr&
00454       _M_rightmost()
00455       { return this->_M_impl._M_header._M_right; }
00456 
00457       _Const_Base_ptr
00458       _M_rightmost() const
00459       { return this->_M_impl._M_header._M_right; }
00460 
00461       _Link_type
00462       _M_begin()
00463       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00464 
00465       _Const_Link_type
00466       _M_begin() const
00467       {
00468     return static_cast<_Const_Link_type>
00469       (this->_M_impl._M_header._M_parent);
00470       }
00471 
00472       _Link_type
00473       _M_end()
00474       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00475 
00476       _Const_Link_type
00477       _M_end() const
00478       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00479 
00480       static const_reference
00481       _S_value(_Const_Link_type __x)
00482       { return __x->_M_value_field; }
00483 
00484       static const _Key&
00485       _S_key(_Const_Link_type __x)
00486       { return _KeyOfValue()(_S_value(__x)); }
00487 
00488       static _Link_type
00489       _S_left(_Base_ptr __x)
00490       { return static_cast<_Link_type>(__x->_M_left); }
00491 
00492       static _Const_Link_type
00493       _S_left(_Const_Base_ptr __x)
00494       { return static_cast<_Const_Link_type>(__x->_M_left); }
00495 
00496       static _Link_type
00497       _S_right(_Base_ptr __x)
00498       { return static_cast<_Link_type>(__x->_M_right); }
00499 
00500       static _Const_Link_type
00501       _S_right(_Const_Base_ptr __x)
00502       { return static_cast<_Const_Link_type>(__x->_M_right); }
00503 
00504       static const_reference
00505       _S_value(_Const_Base_ptr __x)
00506       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00507 
00508       static const _Key&
00509       _S_key(_Const_Base_ptr __x)
00510       { return _KeyOfValue()(_S_value(__x)); }
00511 
00512       static _Base_ptr
00513       _S_minimum(_Base_ptr __x)
00514       { return _Rb_tree_node_base::_S_minimum(__x); }
00515 
00516       static _Const_Base_ptr
00517       _S_minimum(_Const_Base_ptr __x)
00518       { return _Rb_tree_node_base::_S_minimum(__x); }
00519 
00520       static _Base_ptr
00521       _S_maximum(_Base_ptr __x)
00522       { return _Rb_tree_node_base::_S_maximum(__x); }
00523 
00524       static _Const_Base_ptr
00525       _S_maximum(_Const_Base_ptr __x)
00526       { return _Rb_tree_node_base::_S_maximum(__x); }
00527 
00528     public:
00529       typedef _Rb_tree_iterator<value_type>       iterator;
00530       typedef _Rb_tree_const_iterator<value_type> const_iterator;
00531 
00532       typedef std::reverse_iterator<iterator>       reverse_iterator;
00533       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00534 
00535     private:
00536       iterator
00537       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00538 
00539       _Link_type
00540       _M_copy(_Const_Link_type __x, _Link_type __p);
00541 
00542       void
00543       _M_erase(_Link_type __x);
00544 
00545     public:
00546       // allocation/deallocation
00547       _Rb_tree()
00548       { }
00549 
00550       _Rb_tree(const _Compare& __comp)
00551       : _M_impl(allocator_type(), __comp)
00552       { }
00553 
00554       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00555       : _M_impl(__a, __comp)
00556       { }
00557 
00558       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00559       : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
00560       {
00561     if (__x._M_root() != 0)
00562       {
00563         _M_root() = _M_copy(__x._M_begin(), _M_end());
00564         _M_leftmost() = _S_minimum(_M_root());
00565         _M_rightmost() = _S_maximum(_M_root());
00566         _M_impl._M_node_count = __x._M_impl._M_node_count;
00567       }
00568       }
00569 
00570       ~_Rb_tree()
00571       { _M_erase(_M_begin()); }
00572 
00573       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00574       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
00575 
00576       // Accessors.
00577       _Compare
00578       key_comp() const
00579       { return _M_impl._M_key_compare; }
00580 
00581       iterator
00582       begin()
00583       { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
00584 
00585       const_iterator
00586       begin() const
00587       {
00588     return static_cast<_Const_Link_type>
00589       (this->_M_impl._M_header._M_left);
00590       }
00591 
00592       iterator
00593       end()
00594       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00595 
00596       const_iterator
00597       end() const
00598       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00599 
00600       reverse_iterator
00601       rbegin()
00602       { return reverse_iterator(end()); }
00603 
00604       const_reverse_iterator
00605       rbegin() const
00606       { return const_reverse_iterator(end()); }
00607 
00608       reverse_iterator
00609       rend()
00610       { return reverse_iterator(begin()); }
00611 
00612       const_reverse_iterator
00613       rend() const
00614       { return const_reverse_iterator(begin()); }
00615 
00616       bool
00617       empty() const
00618       { return _M_impl._M_node_count == 0; }
00619 
00620       size_type
00621       size() const
00622       { return _M_impl._M_node_count; }
00623 
00624       size_type
00625       max_size() const
00626       { return size_type(-1); }
00627 
00628       void
00629       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
00630 
00631       // Insert/erase.
00632       pair<iterator,bool>
00633       insert_unique(const value_type& __x);
00634 
00635       iterator
00636       insert_equal(const value_type& __x);
00637 
00638       iterator
00639       insert_unique(iterator __position, const value_type& __x);
00640 
00641       iterator
00642       insert_equal(iterator __position, const value_type& __x);
00643 
00644       template<typename _InputIterator>
00645       void
00646       insert_unique(_InputIterator __first, _InputIterator __last);
00647 
00648       template<typename _InputIterator>
00649       void
00650       insert_equal(_InputIterator __first, _InputIterator __last);
00651 
00652       void
00653       erase(iterator __position);
00654 
00655       size_type
00656       erase(const key_type& __x);
00657 
00658       void
00659       erase(iterator __first, iterator __last);
00660 
00661       void
00662       erase(const key_type* __first, const key_type* __last);
00663 
00664       void
00665       clear()
00666       {
00667         _M_erase(_M_begin());
00668         _M_leftmost() = _M_end();
00669         _M_root() = 0;
00670         _M_rightmost() = _M_end();
00671         _M_impl._M_node_count = 0;
00672       }
00673 
00674       // Set operations.
00675       iterator
00676       find(const key_type& __x);
00677 
00678       const_iterator
00679       find(const key_type& __x) const;
00680 
00681       size_type
00682       count(const key_type& __x) const;
00683 
00684       iterator
00685       lower_bound(const key_type& __x);
00686 
00687       const_iterator
00688       lower_bound(const key_type& __x) const;
00689 
00690       iterator
00691       upper_bound(const key_type& __x);
00692 
00693       const_iterator
00694       upper_bound(const key_type& __x) const;
00695 
00696       pair<iterator,iterator>
00697       equal_range(const key_type& __x);
00698 
00699       pair<const_iterator, const_iterator>
00700       equal_range(const key_type& __x) const;
00701 
00702       // Debugging.
00703       bool
00704       __rb_verify() const;
00705     };
00706 
00707   template<typename _Key, typename _Val, typename _KeyOfValue,
00708            typename _Compare, typename _Alloc>
00709     inline bool
00710     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00711            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00712     {
00713       return __x.size() == __y.size()
00714          && std::equal(__x.begin(), __x.end(), __y.begin());
00715     }
00716 
00717   template<typename _Key, typename _Val, typename _KeyOfValue,
00718            typename _Compare, typename _Alloc>
00719     inline bool
00720     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00721           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00722     {
00723       return std::lexicographical_compare(__x.begin(), __x.end(), 
00724                       __y.begin(), __y.end());
00725     }
00726 
00727   template<typename _Key, typename _Val, typename _KeyOfValue,
00728            typename _Compare, typename _Alloc>
00729     inline bool
00730     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00731            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00732     { return !(__x == __y); }
00733 
00734   template<typename _Key, typename _Val, typename _KeyOfValue,
00735            typename _Compare, typename _Alloc>
00736     inline bool
00737     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00738           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00739     { return __y < __x; }
00740 
00741   template<typename _Key, typename _Val, typename _KeyOfValue,
00742            typename _Compare, typename _Alloc>
00743     inline bool
00744     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00745            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00746     { return !(__y < __x); }
00747 
00748   template<typename _Key, typename _Val, typename _KeyOfValue,
00749            typename _Compare, typename _Alloc>
00750     inline bool
00751     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00752            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00753     { return !(__x < __y); }
00754 
00755   template<typename _Key, typename _Val, typename _KeyOfValue,
00756            typename _Compare, typename _Alloc>
00757     inline void
00758     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00759      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00760     { __x.swap(__y); }
00761 
00762   template<typename _Key, typename _Val, typename _KeyOfValue,
00763            typename _Compare, typename _Alloc>
00764     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00765     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00766     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00767     {
00768       if (this != &__x)
00769     {
00770       // Note that _Key may be a constant type.
00771       clear();
00772       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00773       if (__x._M_root() != 0)
00774         {
00775           _M_root() = _M_copy(__x._M_begin(), _M_end());
00776           _M_leftmost() = _S_minimum(_M_root());
00777           _M_rightmost() = _S_maximum(_M_root());
00778           _M_impl._M_node_count = __x._M_impl._M_node_count;
00779         }
00780     }
00781       return *this;
00782     }
00783 
00784   template<typename _Key, typename _Val, typename _KeyOfValue,
00785            typename _Compare, typename _Alloc>
00786     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00787     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00788     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00789     {
00790       bool __insert_left = (__x != 0 || __p == _M_end()
00791                 || _M_impl._M_key_compare(_KeyOfValue()(__v), 
00792                               _S_key(__p)));
00793 
00794       _Link_type __z = _M_create_node(__v);
00795 
00796       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
00797                     this->_M_impl._M_header);
00798       ++_M_impl._M_node_count;
00799       return iterator(__z);
00800     }
00801 
00802   template<typename _Key, typename _Val, typename _KeyOfValue,
00803            typename _Compare, typename _Alloc>
00804     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00805     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00806     insert_equal(const _Val& __v)
00807     {
00808       _Link_type __x = _M_begin();
00809       _Link_type __y = _M_end();
00810       while (__x != 0)
00811     {
00812       __y = __x;
00813       __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
00814             _S_left(__x) : _S_right(__x);
00815     }
00816       return _M_insert(__x, __y, __v);
00817     }
00818 
00819   template<typename _Key, typename _Val, typename _KeyOfValue,
00820            typename _Compare, typename _Alloc>
00821     void
00822     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00823     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
00824     {
00825       if (_M_root() == 0)
00826       {
00827     if (__t._M_root() != 0)
00828     {
00829       _M_root() = __t._M_root();
00830       _M_leftmost() = __t._M_leftmost();
00831       _M_rightmost() = __t._M_rightmost();
00832           _M_root()->_M_parent = _M_end();
00833 
00834       __t._M_root() = 0;
00835       __t._M_leftmost() = __t._M_end();
00836       __t._M_rightmost() = __t._M_end();
00837     }
00838       }
00839       else if (__t._M_root() == 0)
00840       {
00841     __t._M_root() = _M_root();
00842     __t._M_leftmost() = _M_leftmost();
00843     __t._M_rightmost() = _M_rightmost();
00844         __t._M_root()->_M_parent = __t._M_end();
00845 
00846     _M_root() = 0;
00847     _M_leftmost() = _M_end();
00848     _M_rightmost() = _M_end();
00849       }
00850       else
00851       {
00852     std::swap(_M_root(),__t._M_root());
00853     std::swap(_M_leftmost(),__t._M_leftmost());
00854     std::swap(_M_rightmost(),__t._M_rightmost());
00855 
00856     _M_root()->_M_parent = _M_end();
00857     __t._M_root()->_M_parent = __t._M_end();
00858       }
00859       // No need to swap header's color as it does not change.
00860       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
00861       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
00862     }
00863 
00864   template<typename _Key, typename _Val, typename _KeyOfValue,
00865            typename _Compare, typename _Alloc>
00866     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
00867                _Compare, _Alloc>::iterator, bool>
00868     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00869     insert_unique(const _Val& __v)
00870     {
00871       _Link_type __x = _M_begin();
00872       _Link_type __y = _M_end();
00873       bool __comp = true;
00874       while (__x != 0)
00875     {
00876       __y = __x;
00877       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
00878       __x = __comp ? _S_left(__x) : _S_right(__x);
00879     }
00880       iterator __j = iterator(__y);
00881       if (__comp)
00882     if (__j == begin())
00883       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
00884     else
00885       --__j;
00886       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
00887     return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
00888       return pair<iterator, bool>(__j, false);
00889     }
00890 
00891   template<typename _Key, typename _Val, typename _KeyOfValue,
00892            typename _Compare, typename _Alloc>
00893     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00894     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00895     insert_unique(iterator __position, const _Val& __v)
00896     {
00897       // end()
00898       if (__position._M_node == _M_end())
00899     {
00900       if (size() > 0
00901           && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
00902                     _KeyOfValue()(__v)))
00903         return _M_insert(0, _M_rightmost(), __v);
00904       else
00905         return insert_unique(__v).first;
00906     }
00907       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00908                       _S_key(__position._M_node)))
00909     {
00910       // First, try before...
00911       iterator __before = __position;
00912       if (__position._M_node == _M_leftmost()) // begin()
00913         return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00914       else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
00915                       _KeyOfValue()(__v)))
00916         {
00917           if (_S_right(__before._M_node) == 0)
00918         return _M_insert(0, __before._M_node, __v);
00919           else
00920         return _M_insert(__position._M_node,
00921                  __position._M_node, __v);
00922         }
00923       else
00924         return insert_unique(__v).first;
00925     }
00926       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
00927                       _KeyOfValue()(__v)))
00928     {
00929       // ... then try after.
00930       iterator __after = __position;
00931       if (__position._M_node == _M_rightmost())
00932         return _M_insert(0, _M_rightmost(), __v);
00933       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00934                       _S_key((++__after)._M_node)))
00935         {
00936           if (_S_right(__position._M_node) == 0)
00937         return _M_insert(0, __position._M_node, __v);
00938           else
00939         return _M_insert(__after._M_node, __after._M_node, __v);
00940         }
00941       else
00942         return insert_unique(__v).first;
00943     }
00944       else
00945     return __position; // Equivalent keys.
00946     }
00947 
00948   template<typename _Key, typename _Val, typename _KeyOfValue,
00949            typename _Compare, typename _Alloc>
00950     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00951     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00952     insert_equal(iterator __position, const _Val& __v)
00953     {
00954       // end()
00955       if (__position._M_node == _M_end())
00956     {
00957       if (size() > 0
00958           && !_M_impl._M_key_compare(_KeyOfValue()(__v),
00959                      _S_key(_M_rightmost())))
00960         return _M_insert(0, _M_rightmost(), __v);
00961       else
00962         return insert_equal(__v);
00963     }
00964       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
00965                        _KeyOfValue()(__v)))
00966     {
00967       // First, try before...
00968       iterator __before = __position;
00969       if (__position._M_node == _M_leftmost()) // begin()
00970         return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00971       else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
00972                        _S_key((--__before)._M_node)))
00973         {
00974           if (_S_right(__before._M_node) == 0)
00975         return _M_insert(0, __before._M_node, __v);
00976           else
00977         return _M_insert(__position._M_node,
00978                  __position._M_node, __v);
00979         }
00980       else
00981         return insert_equal(__v);
00982     }
00983       else
00984     {
00985       // ... then try after.  
00986       iterator __after = __position;
00987       if (__position._M_node == _M_rightmost())
00988         return _M_insert(0, _M_rightmost(), __v);
00989       else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
00990                        _KeyOfValue()(__v)))
00991         {
00992           if (_S_right(__position._M_node) == 0)
00993         return _M_insert(0, __position._M_node, __v);
00994           else
00995         return _M_insert(__after._M_node, __after._M_node, __v);
00996         }
00997       else
00998         return insert_equal(__v);
00999     }
01000     }
01001 
01002   template<typename _Key, typename _Val, typename _KoV,
01003            typename _Cmp, typename _Alloc>
01004     template<class _II>
01005       void
01006       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01007       insert_equal(_II __first, _II __last)
01008       {
01009     for (; __first != __last; ++__first)
01010       insert_equal(end(), *__first);
01011       }
01012 
01013   template<typename _Key, typename _Val, typename _KoV,
01014            typename _Cmp, typename _Alloc>
01015     template<class _II>
01016     void
01017     _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01018     insert_unique(_II __first, _II __last)
01019     {
01020       for (; __first != __last; ++__first)
01021     insert_unique(end(), *__first);
01022     }
01023 
01024   template<typename _Key, typename _Val, typename _KeyOfValue,
01025            typename _Compare, typename _Alloc>
01026     inline void
01027     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01028     erase(iterator __position)
01029     {
01030       _Link_type __y =
01031     static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01032                 (__position._M_node,
01033                  this->_M_impl._M_header));
01034       destroy_node(__y);
01035       --_M_impl._M_node_count;
01036     }
01037 
01038   template<typename _Key, typename _Val, typename _KeyOfValue,
01039            typename _Compare, typename _Alloc>
01040     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01041     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01042     erase(const _Key& __x)
01043     {
01044       pair<iterator,iterator> __p = equal_range(__x);
01045       size_type __n = std::distance(__p.first, __p.second);
01046       erase(__p.first, __p.second);
01047       return __n;
01048     }
01049 
01050   template<typename _Key, typename _Val, typename _KoV,
01051            typename _Compare, typename _Alloc>
01052     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01053     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01054     _M_copy(_Const_Link_type __x, _Link_type __p)
01055     {
01056       // Structural copy.  __x and __p must be non-null.
01057       _Link_type __top = _M_clone_node(__x);
01058       __top->_M_parent = __p;
01059 
01060       try
01061     {
01062       if (__x->_M_right)
01063         __top->_M_right = _M_copy(_S_right(__x), __top);
01064       __p = __top;
01065       __x = _S_left(__x);
01066 
01067       while (__x != 0)
01068         {
01069           _Link_type __y = _M_clone_node(__x);
01070           __p->_M_left = __y;
01071           __y->_M_parent = __p;
01072           if (__x->_M_right)
01073         __y->_M_right = _M_copy(_S_right(__x), __y);
01074           __p = __y;
01075           __x = _S_left(__x);
01076         }
01077     }
01078       catch(...)
01079     {
01080       _M_erase(__top);
01081       __throw_exception_again;
01082     }
01083       return __top;
01084     }
01085 
01086   template<typename _Key, typename _Val, typename _KeyOfValue,
01087            typename _Compare, typename _Alloc>
01088     void
01089     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01090     _M_erase(_Link_type __x)
01091     {
01092       // Erase without rebalancing.
01093       while (__x != 0)
01094     {
01095       _M_erase(_S_right(__x));
01096       _Link_type __y = _S_left(__x);
01097       destroy_node(__x);
01098       __x = __y;
01099     }
01100     }
01101 
01102   template<typename _Key, typename _Val, typename _KeyOfValue,
01103            typename _Compare, typename _Alloc>
01104     void
01105     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01106     erase(iterator __first, iterator __last)
01107     {
01108       if (__first == begin() && __last == end())
01109     clear();
01110       else
01111     while (__first != __last)
01112       erase(__first++);
01113     }
01114 
01115   template<typename _Key, typename _Val, typename _KeyOfValue,
01116            typename _Compare, typename _Alloc>
01117     void
01118     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01119     erase(const _Key* __first, const _Key* __last)
01120     {
01121       while (__first != __last)
01122     erase(*__first++);
01123     }
01124 
01125   template<typename _Key, typename _Val, typename _KeyOfValue,
01126            typename _Compare, typename _Alloc>
01127     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01128     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01129     find(const _Key& __k)
01130     {
01131       _Link_type __x = _M_begin(); // Current node.
01132       _Link_type __y = _M_end(); // Last node which is not less than __k.
01133 
01134       while (__x != 0)
01135     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01136       __y = __x, __x = _S_left(__x);
01137     else
01138       __x = _S_right(__x);
01139 
01140       iterator __j = iterator(__y);
01141       return (__j == end()
01142           || _M_impl._M_key_compare(__k,
01143                     _S_key(__j._M_node))) ? end() : __j;
01144     }
01145 
01146   template<typename _Key, typename _Val, typename _KeyOfValue,
01147            typename _Compare, typename _Alloc>
01148     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01149     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01150     find(const _Key& __k) const
01151     {
01152       _Const_Link_type __x = _M_begin(); // Current node.
01153       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
01154 
01155      while (__x != 0)
01156        {
01157      if (!_M_impl._M_key_compare(_S_key(__x), __k))
01158        __y = __x, __x = _S_left(__x);
01159      else
01160        __x = _S_right(__x);
01161        }
01162      const_iterator __j = const_iterator(__y);
01163      return (__j == end()
01164          || _M_impl._M_key_compare(__k, 
01165                        _S_key(__j._M_node))) ? end() : __j;
01166     }
01167 
01168   template<typename _Key, typename _Val, typename _KeyOfValue,
01169            typename _Compare, typename _Alloc>
01170     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01171     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01172     count(const _Key& __k) const
01173     {
01174       pair<const_iterator, const_iterator> __p = equal_range(__k);
01175       const size_type __n = std::distance(__p.first, __p.second);
01176       return __n;
01177     }
01178 
01179   template<typename _Key, typename _Val, typename _KeyOfValue,
01180            typename _Compare, typename _Alloc>
01181     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01182     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01183     lower_bound(const _Key& __k)
01184     {
01185       _Link_type __x = _M_begin(); // Current node.
01186       _Link_type __y = _M_end(); // Last node which is not less than __k.
01187 
01188       while (__x != 0)
01189     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01190       __y = __x, __x = _S_left(__x);
01191     else
01192       __x = _S_right(__x);
01193 
01194       return iterator(__y);
01195     }
01196 
01197   template<typename _Key, typename _Val, typename _KeyOfValue,
01198            typename _Compare, typename _Alloc>
01199     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01200     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01201     lower_bound(const _Key& __k) const
01202     {
01203       _Const_Link_type __x = _M_begin(); // Current node.
01204       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
01205 
01206       while (__x != 0)
01207     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01208       __y = __x, __x = _S_left(__x);
01209     else
01210       __x = _S_right(__x);
01211 
01212       return const_iterator(__y);
01213     }
01214 
01215   template<typename _Key, typename _Val, typename _KeyOfValue,
01216            typename _Compare, typename _Alloc>
01217     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01218     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01219     upper_bound(const _Key& __k)
01220     {
01221       _Link_type __x = _M_begin(); // Current node.
01222       _Link_type __y = _M_end(); // Last node which is greater than __k.
01223 
01224       while (__x != 0)
01225     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01226       __y = __x, __x = _S_left(__x);
01227     else
01228       __x = _S_right(__x);
01229 
01230       return iterator(__y);
01231     }
01232 
01233   template<typename _Key, typename _Val, typename _KeyOfValue,
01234            typename _Compare, typename _Alloc>
01235     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01236     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01237     upper_bound(const _Key& __k) const
01238     {
01239       _Const_Link_type __x = _M_begin(); // Current node.
01240       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
01241 
01242       while (__x != 0)
01243     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01244       __y = __x, __x = _S_left(__x);
01245     else
01246       __x = _S_right(__x);
01247 
01248       return const_iterator(__y);
01249     }
01250 
01251   template<typename _Key, typename _Val, typename _KeyOfValue,
01252            typename _Compare, typename _Alloc>
01253     inline
01254     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01255                _Compare, _Alloc>::iterator,
01256      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
01257     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01258     equal_range(const _Key& __k)
01259     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01260 
01261   template<typename _Key, typename _Val, typename _KoV,
01262            typename _Compare, typename _Alloc>
01263     inline
01264     pair<typename _Rb_tree<_Key, _Val, _KoV,
01265                _Compare, _Alloc>::const_iterator,
01266      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01267     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01268     equal_range(const _Key& __k) const
01269     { return pair<const_iterator, const_iterator>(lower_bound(__k),
01270                           upper_bound(__k)); }
01271 
01272   unsigned int
01273   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01274                        const _Rb_tree_node_base* __root);
01275 
01276   template<typename _Key, typename _Val, typename _KeyOfValue,
01277            typename _Compare, typename _Alloc>
01278     bool
01279     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01280     {
01281       if (_M_impl._M_node_count == 0 || begin() == end())
01282     return _M_impl._M_node_count == 0 && begin() == end()
01283            && this->_M_impl._M_header._M_left == _M_end()
01284            && this->_M_impl._M_header._M_right == _M_end();
01285 
01286       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01287       for (const_iterator __it = begin(); __it != end(); ++__it)
01288     {
01289       _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01290       _Const_Link_type __L = _S_left(__x);
01291       _Const_Link_type __R = _S_right(__x);
01292 
01293       if (__x->_M_color == _S_red)
01294         if ((__L && __L->_M_color == _S_red)
01295         || (__R && __R->_M_color == _S_red))
01296           return false;
01297 
01298       if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01299         return false;
01300       if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01301         return false;
01302 
01303       if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01304         return false;
01305     }
01306 
01307       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01308     return false;
01309       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01310     return false;
01311       return true;
01312     }
01313 } // namespace std
01314 
01315 #endif

Generated on Thu Apr 20 22:15:03 2006 for libstdc++ source by  doxygen 1.4.6