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_node_count(0)
00405       {
00406         this->_M_header._M_color = _S_red;
00407         this->_M_header._M_parent = 0;
00408         this->_M_header._M_left = &this->_M_header;
00409         this->_M_header._M_right = &this->_M_header;
00410       }
00411     };
00412 
00413       // Specialization for _Comparison types that are not capable of
00414       // being base classes / super classes.
00415       template<typename _Key_compare>
00416         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 
00417     {
00418       _Key_compare      _M_key_compare;
00419       _Rb_tree_node_base    _M_header;
00420       size_type         _M_node_count; // Keeps track of size of tree.
00421 
00422       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
00423             const _Key_compare& __comp = _Key_compare())
00424       : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
00425       { 
00426         this->_M_header._M_color = _S_red;
00427         this->_M_header._M_parent = 0;
00428         this->_M_header._M_left = &this->_M_header;
00429         this->_M_header._M_right = &this->_M_header;
00430       }
00431     };
00432 
00433       _Rb_tree_impl<_Compare> _M_impl;
00434 
00435     protected:
00436       _Base_ptr&
00437       _M_root()
00438       { return this->_M_impl._M_header._M_parent; }
00439 
00440       _Const_Base_ptr
00441       _M_root() const
00442       { return this->_M_impl._M_header._M_parent; }
00443 
00444       _Base_ptr&
00445       _M_leftmost()
00446       { return this->_M_impl._M_header._M_left; }
00447 
00448       _Const_Base_ptr
00449       _M_leftmost() const
00450       { return this->_M_impl._M_header._M_left; }
00451 
00452       _Base_ptr&
00453       _M_rightmost()
00454       { return this->_M_impl._M_header._M_right; }
00455 
00456       _Const_Base_ptr
00457       _M_rightmost() const
00458       { return this->_M_impl._M_header._M_right; }
00459 
00460       _Link_type
00461       _M_begin()
00462       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00463 
00464       _Const_Link_type
00465       _M_begin() const
00466       {
00467     return static_cast<_Const_Link_type>
00468       (this->_M_impl._M_header._M_parent);
00469       }
00470 
00471       _Link_type
00472       _M_end()
00473       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00474 
00475       _Const_Link_type
00476       _M_end() const
00477       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00478 
00479       static const_reference
00480       _S_value(_Const_Link_type __x)
00481       { return __x->_M_value_field; }
00482 
00483       static const _Key&
00484       _S_key(_Const_Link_type __x)
00485       { return _KeyOfValue()(_S_value(__x)); }
00486 
00487       static _Link_type
00488       _S_left(_Base_ptr __x)
00489       { return static_cast<_Link_type>(__x->_M_left); }
00490 
00491       static _Const_Link_type
00492       _S_left(_Const_Base_ptr __x)
00493       { return static_cast<_Const_Link_type>(__x->_M_left); }
00494 
00495       static _Link_type
00496       _S_right(_Base_ptr __x)
00497       { return static_cast<_Link_type>(__x->_M_right); }
00498 
00499       static _Const_Link_type
00500       _S_right(_Const_Base_ptr __x)
00501       { return static_cast<_Const_Link_type>(__x->_M_right); }
00502 
00503       static const_reference
00504       _S_value(_Const_Base_ptr __x)
00505       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00506 
00507       static const _Key&
00508       _S_key(_Const_Base_ptr __x)
00509       { return _KeyOfValue()(_S_value(__x)); }
00510 
00511       static _Base_ptr
00512       _S_minimum(_Base_ptr __x)
00513       { return _Rb_tree_node_base::_S_minimum(__x); }
00514 
00515       static _Const_Base_ptr
00516       _S_minimum(_Const_Base_ptr __x)
00517       { return _Rb_tree_node_base::_S_minimum(__x); }
00518 
00519       static _Base_ptr
00520       _S_maximum(_Base_ptr __x)
00521       { return _Rb_tree_node_base::_S_maximum(__x); }
00522 
00523       static _Const_Base_ptr
00524       _S_maximum(_Const_Base_ptr __x)
00525       { return _Rb_tree_node_base::_S_maximum(__x); }
00526 
00527     public:
00528       typedef _Rb_tree_iterator<value_type>       iterator;
00529       typedef _Rb_tree_const_iterator<value_type> const_iterator;
00530 
00531       typedef std::reverse_iterator<iterator>       reverse_iterator;
00532       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00533 
00534     private:
00535       iterator
00536       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00537 
00538       _Link_type
00539       _M_copy(_Const_Link_type __x, _Link_type __p);
00540 
00541       void
00542       _M_erase(_Link_type __x);
00543 
00544     public:
00545       // allocation/deallocation
00546       _Rb_tree()
00547       { }
00548 
00549       _Rb_tree(const _Compare& __comp)
00550       : _M_impl(allocator_type(), __comp)
00551       { }
00552 
00553       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
00554       : _M_impl(__a, __comp)
00555       { }
00556 
00557       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00558       : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
00559       {
00560     if (__x._M_root() != 0)
00561       {
00562         _M_root() = _M_copy(__x._M_begin(), _M_end());
00563         _M_leftmost() = _S_minimum(_M_root());
00564         _M_rightmost() = _S_maximum(_M_root());
00565         _M_impl._M_node_count = __x._M_impl._M_node_count;
00566       }
00567       }
00568 
00569       ~_Rb_tree()
00570       { _M_erase(_M_begin()); }
00571 
00572       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00573       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
00574 
00575       // Accessors.
00576       _Compare
00577       key_comp() const
00578       { return _M_impl._M_key_compare; }
00579 
00580       iterator
00581       begin()
00582       { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
00583 
00584       const_iterator
00585       begin() const
00586       {
00587     return static_cast<_Const_Link_type>
00588       (this->_M_impl._M_header._M_left);
00589       }
00590 
00591       iterator
00592       end()
00593       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00594 
00595       const_iterator
00596       end() const
00597       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00598 
00599       reverse_iterator
00600       rbegin()
00601       { return reverse_iterator(end()); }
00602 
00603       const_reverse_iterator
00604       rbegin() const
00605       { return const_reverse_iterator(end()); }
00606 
00607       reverse_iterator
00608       rend()
00609       { return reverse_iterator(begin()); }
00610 
00611       const_reverse_iterator
00612       rend() const
00613       { return const_reverse_iterator(begin()); }
00614 
00615       bool
00616       empty() const
00617       { return _M_impl._M_node_count == 0; }
00618 
00619       size_type
00620       size() const
00621       { return _M_impl._M_node_count; }
00622 
00623       size_type
00624       max_size() const
00625       { return size_type(-1); }
00626 
00627       void
00628       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
00629 
00630       // Insert/erase.
00631       pair<iterator,bool>
00632       insert_unique(const value_type& __x);
00633 
00634       iterator
00635       insert_equal(const value_type& __x);
00636 
00637       iterator
00638       insert_unique(iterator __position, const value_type& __x);
00639 
00640       iterator
00641       insert_equal(iterator __position, const value_type& __x);
00642 
00643       template<typename _InputIterator>
00644       void
00645       insert_unique(_InputIterator __first, _InputIterator __last);
00646 
00647       template<typename _InputIterator>
00648       void
00649       insert_equal(_InputIterator __first, _InputIterator __last);
00650 
00651       void
00652       erase(iterator __position);
00653 
00654       size_type
00655       erase(const key_type& __x);
00656 
00657       void
00658       erase(iterator __first, iterator __last);
00659 
00660       void
00661       erase(const key_type* __first, const key_type* __last);
00662 
00663       void
00664       clear()
00665       {
00666         _M_erase(_M_begin());
00667         _M_leftmost() = _M_end();
00668         _M_root() = 0;
00669         _M_rightmost() = _M_end();
00670         _M_impl._M_node_count = 0;
00671       }
00672 
00673       // Set operations.
00674       iterator
00675       find(const key_type& __x);
00676 
00677       const_iterator
00678       find(const key_type& __x) const;
00679 
00680       size_type
00681       count(const key_type& __x) const;
00682 
00683       iterator
00684       lower_bound(const key_type& __x);
00685 
00686       const_iterator
00687       lower_bound(const key_type& __x) const;
00688 
00689       iterator
00690       upper_bound(const key_type& __x);
00691 
00692       const_iterator
00693       upper_bound(const key_type& __x) const;
00694 
00695       pair<iterator,iterator>
00696       equal_range(const key_type& __x);
00697 
00698       pair<const_iterator, const_iterator>
00699       equal_range(const key_type& __x) const;
00700 
00701       // Debugging.
00702       bool
00703       __rb_verify() const;
00704     };
00705 
00706   template<typename _Key, typename _Val, typename _KeyOfValue,
00707            typename _Compare, typename _Alloc>
00708     inline bool
00709     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00710            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00711     {
00712       return __x.size() == __y.size()
00713          && std::equal(__x.begin(), __x.end(), __y.begin());
00714     }
00715 
00716   template<typename _Key, typename _Val, typename _KeyOfValue,
00717            typename _Compare, typename _Alloc>
00718     inline bool
00719     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00720           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00721     {
00722       return std::lexicographical_compare(__x.begin(), __x.end(), 
00723                       __y.begin(), __y.end());
00724     }
00725 
00726   template<typename _Key, typename _Val, typename _KeyOfValue,
00727            typename _Compare, typename _Alloc>
00728     inline bool
00729     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00730            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00731     { return !(__x == __y); }
00732 
00733   template<typename _Key, typename _Val, typename _KeyOfValue,
00734            typename _Compare, typename _Alloc>
00735     inline bool
00736     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00737           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00738     { return __y < __x; }
00739 
00740   template<typename _Key, typename _Val, typename _KeyOfValue,
00741            typename _Compare, typename _Alloc>
00742     inline bool
00743     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00744            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00745     { return !(__y < __x); }
00746 
00747   template<typename _Key, typename _Val, typename _KeyOfValue,
00748            typename _Compare, typename _Alloc>
00749     inline bool
00750     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00751            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00752     { return !(__x < __y); }
00753 
00754   template<typename _Key, typename _Val, typename _KeyOfValue,
00755            typename _Compare, typename _Alloc>
00756     inline void
00757     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00758      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00759     { __x.swap(__y); }
00760 
00761   template<typename _Key, typename _Val, typename _KeyOfValue,
00762            typename _Compare, typename _Alloc>
00763     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00764     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00765     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00766     {
00767       if (this != &__x)
00768     {
00769       // Note that _Key may be a constant type.
00770       clear();
00771       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00772       if (__x._M_root() != 0)
00773         {
00774           _M_root() = _M_copy(__x._M_begin(), _M_end());
00775           _M_leftmost() = _S_minimum(_M_root());
00776           _M_rightmost() = _S_maximum(_M_root());
00777           _M_impl._M_node_count = __x._M_impl._M_node_count;
00778         }
00779     }
00780       return *this;
00781     }
00782 
00783   template<typename _Key, typename _Val, typename _KeyOfValue,
00784            typename _Compare, typename _Alloc>
00785     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00786     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00787     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00788     {
00789       bool __insert_left = (__x != 0 || __p == _M_end()
00790                 || _M_impl._M_key_compare(_KeyOfValue()(__v), 
00791                               _S_key(__p)));
00792 
00793       _Link_type __z = _M_create_node(__v);
00794 
00795       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
00796                     this->_M_impl._M_header);
00797       ++_M_impl._M_node_count;
00798       return iterator(__z);
00799     }
00800 
00801   template<typename _Key, typename _Val, typename _KeyOfValue,
00802            typename _Compare, typename _Alloc>
00803     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00804     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00805     insert_equal(const _Val& __v)
00806     {
00807       _Link_type __x = _M_begin();
00808       _Link_type __y = _M_end();
00809       while (__x != 0)
00810     {
00811       __y = __x;
00812       __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
00813             _S_left(__x) : _S_right(__x);
00814     }
00815       return _M_insert(__x, __y, __v);
00816     }
00817 
00818   template<typename _Key, typename _Val, typename _KeyOfValue,
00819            typename _Compare, typename _Alloc>
00820     void
00821     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00822     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
00823     {
00824       if (_M_root() == 0)
00825       {
00826     if (__t._M_root() != 0)
00827     {
00828       _M_root() = __t._M_root();
00829       _M_leftmost() = __t._M_leftmost();
00830       _M_rightmost() = __t._M_rightmost();
00831           _M_root()->_M_parent = _M_end();
00832 
00833       __t._M_root() = 0;
00834       __t._M_leftmost() = __t._M_end();
00835       __t._M_rightmost() = __t._M_end();
00836     }
00837       }
00838       else if (__t._M_root() == 0)
00839       {
00840     __t._M_root() = _M_root();
00841     __t._M_leftmost() = _M_leftmost();
00842     __t._M_rightmost() = _M_rightmost();
00843         __t._M_root()->_M_parent = __t._M_end();
00844 
00845     _M_root() = 0;
00846     _M_leftmost() = _M_end();
00847     _M_rightmost() = _M_end();
00848       }
00849       else
00850       {
00851     std::swap(_M_root(),__t._M_root());
00852     std::swap(_M_leftmost(),__t._M_leftmost());
00853     std::swap(_M_rightmost(),__t._M_rightmost());
00854 
00855     _M_root()->_M_parent = _M_end();
00856     __t._M_root()->_M_parent = __t._M_end();
00857       }
00858       // No need to swap header's color as it does not change.
00859       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
00860       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
00861     }
00862 
00863   template<typename _Key, typename _Val, typename _KeyOfValue,
00864            typename _Compare, typename _Alloc>
00865     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
00866                _Compare, _Alloc>::iterator, bool>
00867     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00868     insert_unique(const _Val& __v)
00869     {
00870       _Link_type __x = _M_begin();
00871       _Link_type __y = _M_end();
00872       bool __comp = true;
00873       while (__x != 0)
00874     {
00875       __y = __x;
00876       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
00877       __x = __comp ? _S_left(__x) : _S_right(__x);
00878     }
00879       iterator __j = iterator(__y);
00880       if (__comp)
00881     if (__j == begin())
00882       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
00883     else
00884       --__j;
00885       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
00886     return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
00887       return pair<iterator, bool>(__j, false);
00888     }
00889 
00890   template<typename _Key, typename _Val, typename _KeyOfValue,
00891            typename _Compare, typename _Alloc>
00892     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00893     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00894     insert_unique(iterator __position, const _Val& __v)
00895     {
00896       // end()
00897       if (__position._M_node == _M_end())
00898     {
00899       if (size() > 0
00900           && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
00901                     _KeyOfValue()(__v)))
00902         return _M_insert(0, _M_rightmost(), __v);
00903       else
00904         return insert_unique(__v).first;
00905     }
00906       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00907                       _S_key(__position._M_node)))
00908     {
00909       // First, try before...
00910       iterator __before = __position;
00911       if (__position._M_node == _M_leftmost()) // begin()
00912         return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00913       else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
00914                       _KeyOfValue()(__v)))
00915         {
00916           if (_S_right(__before._M_node) == 0)
00917         return _M_insert(0, __before._M_node, __v);
00918           else
00919         return _M_insert(__position._M_node,
00920                  __position._M_node, __v);
00921         }
00922       else
00923         return insert_unique(__v).first;
00924     }
00925       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
00926                       _KeyOfValue()(__v)))
00927     {
00928       // ... then try after.
00929       iterator __after = __position;
00930       if (__position._M_node == _M_rightmost())
00931         return _M_insert(0, _M_rightmost(), __v);
00932       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
00933                       _S_key((++__after)._M_node)))
00934         {
00935           if (_S_right(__position._M_node) == 0)
00936         return _M_insert(0, __position._M_node, __v);
00937           else
00938         return _M_insert(__after._M_node, __after._M_node, __v);
00939         }
00940       else
00941         return insert_unique(__v).first;
00942     }
00943       else
00944     return __position; // Equivalent keys.
00945     }
00946 
00947   template<typename _Key, typename _Val, typename _KeyOfValue,
00948            typename _Compare, typename _Alloc>
00949     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00950     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00951     insert_equal(iterator __position, const _Val& __v)
00952     {
00953       // end()
00954       if (__position._M_node == _M_end())
00955     {
00956       if (size() > 0
00957           && !_M_impl._M_key_compare(_KeyOfValue()(__v),
00958                      _S_key(_M_rightmost())))
00959         return _M_insert(0, _M_rightmost(), __v);
00960       else
00961         return insert_equal(__v);
00962     }
00963       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
00964                        _KeyOfValue()(__v)))
00965     {
00966       // First, try before...
00967       iterator __before = __position;
00968       if (__position._M_node == _M_leftmost()) // begin()
00969         return _M_insert(_M_leftmost(), _M_leftmost(), __v);
00970       else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
00971                        _S_key((--__before)._M_node)))
00972         {
00973           if (_S_right(__before._M_node) == 0)
00974         return _M_insert(0, __before._M_node, __v);
00975           else
00976         return _M_insert(__position._M_node,
00977                  __position._M_node, __v);
00978         }
00979       else
00980         return insert_equal(__v);
00981     }
00982       else
00983     {
00984       // ... then try after.  
00985       iterator __after = __position;
00986       if (__position._M_node == _M_rightmost())
00987         return _M_insert(0, _M_rightmost(), __v);
00988       else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
00989                        _KeyOfValue()(__v)))
00990         {
00991           if (_S_right(__position._M_node) == 0)
00992         return _M_insert(0, __position._M_node, __v);
00993           else
00994         return _M_insert(__after._M_node, __after._M_node, __v);
00995         }
00996       else
00997         return insert_equal(__v);
00998     }
00999     }
01000 
01001   template<typename _Key, typename _Val, typename _KoV,
01002            typename _Cmp, typename _Alloc>
01003     template<class _II>
01004       void
01005       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01006       insert_equal(_II __first, _II __last)
01007       {
01008     for (; __first != __last; ++__first)
01009       insert_equal(end(), *__first);
01010       }
01011 
01012   template<typename _Key, typename _Val, typename _KoV,
01013            typename _Cmp, typename _Alloc>
01014     template<class _II>
01015     void
01016     _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01017     insert_unique(_II __first, _II __last)
01018     {
01019       for (; __first != __last; ++__first)
01020     insert_unique(end(), *__first);
01021     }
01022 
01023   template<typename _Key, typename _Val, typename _KeyOfValue,
01024            typename _Compare, typename _Alloc>
01025     inline void
01026     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01027     erase(iterator __position)
01028     {
01029       _Link_type __y =
01030     static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01031                 (__position._M_node,
01032                  this->_M_impl._M_header));
01033       destroy_node(__y);
01034       --_M_impl._M_node_count;
01035     }
01036 
01037   template<typename _Key, typename _Val, typename _KeyOfValue,
01038            typename _Compare, typename _Alloc>
01039     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01040     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01041     erase(const _Key& __x)
01042     {
01043       pair<iterator,iterator> __p = equal_range(__x);
01044       size_type __n = std::distance(__p.first, __p.second);
01045       erase(__p.first, __p.second);
01046       return __n;
01047     }
01048 
01049   template<typename _Key, typename _Val, typename _KoV,
01050            typename _Compare, typename _Alloc>
01051     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01052     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01053     _M_copy(_Const_Link_type __x, _Link_type __p)
01054     {
01055       // Structural copy.  __x and __p must be non-null.
01056       _Link_type __top = _M_clone_node(__x);
01057       __top->_M_parent = __p;
01058 
01059       try
01060     {
01061       if (__x->_M_right)
01062         __top->_M_right = _M_copy(_S_right(__x), __top);
01063       __p = __top;
01064       __x = _S_left(__x);
01065 
01066       while (__x != 0)
01067         {
01068           _Link_type __y = _M_clone_node(__x);
01069           __p->_M_left = __y;
01070           __y->_M_parent = __p;
01071           if (__x->_M_right)
01072         __y->_M_right = _M_copy(_S_right(__x), __y);
01073           __p = __y;
01074           __x = _S_left(__x);
01075         }
01076     }
01077       catch(...)
01078     {
01079       _M_erase(__top);
01080       __throw_exception_again;
01081     }
01082       return __top;
01083     }
01084 
01085   template<typename _Key, typename _Val, typename _KeyOfValue,
01086            typename _Compare, typename _Alloc>
01087     void
01088     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01089     _M_erase(_Link_type __x)
01090     {
01091       // Erase without rebalancing.
01092       while (__x != 0)
01093     {
01094       _M_erase(_S_right(__x));
01095       _Link_type __y = _S_left(__x);
01096       destroy_node(__x);
01097       __x = __y;
01098     }
01099     }
01100 
01101   template<typename _Key, typename _Val, typename _KeyOfValue,
01102            typename _Compare, typename _Alloc>
01103     void
01104     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01105     erase(iterator __first, iterator __last)
01106     {
01107       if (__first == begin() && __last == end())
01108     clear();
01109       else
01110     while (__first != __last)
01111       erase(__first++);
01112     }
01113 
01114   template<typename _Key, typename _Val, typename _KeyOfValue,
01115            typename _Compare, typename _Alloc>
01116     void
01117     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01118     erase(const _Key* __first, const _Key* __last)
01119     {
01120       while (__first != __last)
01121     erase(*__first++);
01122     }
01123 
01124   template<typename _Key, typename _Val, typename _KeyOfValue,
01125            typename _Compare, typename _Alloc>
01126     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01127     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01128     find(const _Key& __k)
01129     {
01130       _Link_type __x = _M_begin(); // Current node.
01131       _Link_type __y = _M_end(); // Last node which is not less than __k.
01132 
01133       while (__x != 0)
01134     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01135       __y = __x, __x = _S_left(__x);
01136     else
01137       __x = _S_right(__x);
01138 
01139       iterator __j = iterator(__y);
01140       return (__j == end()
01141           || _M_impl._M_key_compare(__k,
01142                     _S_key(__j._M_node))) ? end() : __j;
01143     }
01144 
01145   template<typename _Key, typename _Val, typename _KeyOfValue,
01146            typename _Compare, typename _Alloc>
01147     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01148     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01149     find(const _Key& __k) const
01150     {
01151       _Const_Link_type __x = _M_begin(); // Current node.
01152       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
01153 
01154      while (__x != 0)
01155        {
01156      if (!_M_impl._M_key_compare(_S_key(__x), __k))
01157        __y = __x, __x = _S_left(__x);
01158      else
01159        __x = _S_right(__x);
01160        }
01161      const_iterator __j = const_iterator(__y);
01162      return (__j == end()
01163          || _M_impl._M_key_compare(__k, 
01164                        _S_key(__j._M_node))) ? end() : __j;
01165     }
01166 
01167   template<typename _Key, typename _Val, typename _KeyOfValue,
01168            typename _Compare, typename _Alloc>
01169     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01170     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01171     count(const _Key& __k) const
01172     {
01173       pair<const_iterator, const_iterator> __p = equal_range(__k);
01174       const size_type __n = std::distance(__p.first, __p.second);
01175       return __n;
01176     }
01177 
01178   template<typename _Key, typename _Val, typename _KeyOfValue,
01179            typename _Compare, typename _Alloc>
01180     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01181     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01182     lower_bound(const _Key& __k)
01183     {
01184       _Link_type __x = _M_begin(); // Current node.
01185       _Link_type __y = _M_end(); // Last node which is not less than __k.
01186 
01187       while (__x != 0)
01188     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01189       __y = __x, __x = _S_left(__x);
01190     else
01191       __x = _S_right(__x);
01192 
01193       return iterator(__y);
01194     }
01195 
01196   template<typename _Key, typename _Val, typename _KeyOfValue,
01197            typename _Compare, typename _Alloc>
01198     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01199     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01200     lower_bound(const _Key& __k) const
01201     {
01202       _Const_Link_type __x = _M_begin(); // Current node.
01203       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
01204 
01205       while (__x != 0)
01206     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01207       __y = __x, __x = _S_left(__x);
01208     else
01209       __x = _S_right(__x);
01210 
01211       return const_iterator(__y);
01212     }
01213 
01214   template<typename _Key, typename _Val, typename _KeyOfValue,
01215            typename _Compare, typename _Alloc>
01216     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01217     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01218     upper_bound(const _Key& __k)
01219     {
01220       _Link_type __x = _M_begin(); // Current node.
01221       _Link_type __y = _M_end(); // Last node which is greater than __k.
01222 
01223       while (__x != 0)
01224     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01225       __y = __x, __x = _S_left(__x);
01226     else
01227       __x = _S_right(__x);
01228 
01229       return iterator(__y);
01230     }
01231 
01232   template<typename _Key, typename _Val, typename _KeyOfValue,
01233            typename _Compare, typename _Alloc>
01234     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
01235     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01236     upper_bound(const _Key& __k) const
01237     {
01238       _Const_Link_type __x = _M_begin(); // Current node.
01239       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
01240 
01241       while (__x != 0)
01242     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01243       __y = __x, __x = _S_left(__x);
01244     else
01245       __x = _S_right(__x);
01246 
01247       return const_iterator(__y);
01248     }
01249 
01250   template<typename _Key, typename _Val, typename _KeyOfValue,
01251            typename _Compare, typename _Alloc>
01252     inline
01253     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01254                _Compare, _Alloc>::iterator,
01255      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
01256     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01257     equal_range(const _Key& __k)
01258     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
01259 
01260   template<typename _Key, typename _Val, typename _KoV,
01261            typename _Compare, typename _Alloc>
01262     inline
01263     pair<typename _Rb_tree<_Key, _Val, _KoV,
01264                _Compare, _Alloc>::const_iterator,
01265      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
01266     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01267     equal_range(const _Key& __k) const
01268     { return pair<const_iterator, const_iterator>(lower_bound(__k),
01269                           upper_bound(__k)); }
01270 
01271   unsigned int
01272   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01273                        const _Rb_tree_node_base* __root);
01274 
01275   template<typename _Key, typename _Val, typename _KeyOfValue,
01276            typename _Compare, typename _Alloc>
01277     bool
01278     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01279     {
01280       if (_M_impl._M_node_count == 0 || begin() == end())
01281     return _M_impl._M_node_count == 0 && begin() == end()
01282            && this->_M_impl._M_header._M_left == _M_end()
01283            && this->_M_impl._M_header._M_right == _M_end();
01284 
01285       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01286       for (const_iterator __it = begin(); __it != end(); ++__it)
01287     {
01288       _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01289       _Const_Link_type __L = _S_left(__x);
01290       _Const_Link_type __R = _S_right(__x);
01291 
01292       if (__x->_M_color == _S_red)
01293         if ((__L && __L->_M_color == _S_red)
01294         || (__R && __R->_M_color == _S_red))
01295           return false;
01296 
01297       if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01298         return false;
01299       if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01300         return false;
01301 
01302       if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01303         return false;
01304     }
01305 
01306       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01307     return false;
01308       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01309     return false;
01310       return true;
01311     }
01312 } // namespace std
01313 
01314 #endif

Generated on Sat Oct 1 15:08:55 2005 for libstdc++ source by  doxygen 1.4.4