# stl_tree.h

Go to the documentation of this file.

    00001 // RB tree implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004 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
    00166       _Rb_tree_iterator(_Link_type __x)
    00167       : _M_node(__x) { }
    00168
    00169       reference
    00170       operator*() const
    00171       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
    00172
    00173       pointer
    00174       operator->() const
    00175       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
    00176
    00177       _Self&
    00178       operator++()
    00179       {
    00180     _M_node = _Rb_tree_increment(_M_node);
    00181     return *this;
    00182       }
    00183
    00184       _Self
    00185       operator++(int)
    00186       {
    00187     _Self __tmp = *this;
    00188     _M_node = _Rb_tree_increment(_M_node);
    00189     return __tmp;
    00190       }
    00191
    00192       _Self&
    00193       operator--()
    00194       {
    00195     _M_node = _Rb_tree_decrement(_M_node);
    00196     return *this;
    00197       }
    00198
    00199       _Self
    00200       operator--(int)
    00201       {
    00202     _Self __tmp = *this;
    00203     _M_node = _Rb_tree_decrement(_M_node);
    00204     return __tmp;
    00205       }
    00206
    00207       bool
    00208       operator==(const _Self& __x) const
    00209       { return _M_node == __x._M_node; }
    00210
    00211       bool
    00212       operator!=(const _Self& __x) const
    00213       { return _M_node != __x._M_node; }
    00214
    00215       _Base_ptr _M_node;
    00216   };
    00217
    00218   template<typename _Tp>
    00219     struct _Rb_tree_const_iterator
    00220     {
    00221       typedef _Tp        value_type;
    00222       typedef const _Tp& reference;
    00223       typedef const _Tp* pointer;
    00224
    00225       typedef _Rb_tree_iterator<_Tp> iterator;
    00226
    00227       typedef bidirectional_iterator_tag iterator_category;
    00228       typedef ptrdiff_t                  difference_type;
    00229
    00230       typedef _Rb_tree_const_iterator<_Tp>        _Self;
    00231       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
    00232       typedef const _Rb_tree_node<_Tp>*           _Link_type;
    00233
    00234       _Rb_tree_const_iterator() { }
    00235
    00236       _Rb_tree_const_iterator(_Link_type __x)
    00237       : _M_node(__x) { }
    00238
    00239       _Rb_tree_const_iterator(const iterator& __it)
    00240       : _M_node(__it._M_node) { }
    00241
    00242       reference
    00243       operator*() const
    00244       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
    00245
    00246       pointer
    00247       operator->() const
    00248       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
    00249
    00250       _Self&
    00251       operator++()
    00252       {
    00253     _M_node = _Rb_tree_increment(_M_node);
    00254     return *this;
    00255       }
    00256
    00257       _Self
    00258       operator++(int)
    00259       {
    00260     _Self __tmp = *this;
    00261     _M_node = _Rb_tree_increment(_M_node);
    00262     return __tmp;
    00263       }
    00264
    00265       _Self&
    00266       operator--()
    00267       {
    00268     _M_node = _Rb_tree_decrement(_M_node);
    00269     return *this;
    00270       }
    00271
    00272       _Self
    00273       operator--(int)
    00274       {
    00275     _Self __tmp = *this;
    00276     _M_node = _Rb_tree_decrement(_M_node);
    00277     return __tmp;
    00278       }
    00279
    00280       bool
    00281       operator==(const _Self& __x) const
    00282       { return _M_node == __x._M_node; }
    00283
    00284       bool
    00285       operator!=(const _Self& __x) const
    00286       { return _M_node != __x._M_node; }
    00287
    00288       _Base_ptr _M_node;
    00289     };
    00290
    00291   template<typename _Val>
    00292     inline bool
    00293     operator==(const _Rb_tree_iterator<_Val>& __x,
    00294                const _Rb_tree_const_iterator<_Val>& __y)
    00295     { return __x._M_node == __y._M_node; }
    00296
    00297   template<typename _Val>
    00298     inline bool
    00299     operator!=(const _Rb_tree_iterator<_Val>& __x,
    00300                const _Rb_tree_const_iterator<_Val>& __y)
    00301     { return __x._M_node != __y._M_node; }
    00302
    00303   void
    00304   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
    00305                        _Rb_tree_node_base*& __root);
    00306
    00307   void
    00308   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
    00309                         _Rb_tree_node_base*& __root);
    00310
    00311   void
    00312   _Rb_tree_insert_and_rebalance(const bool __insert_left,
    00313                                 _Rb_tree_node_base* __x,
    00314                                 _Rb_tree_node_base* __p,
    00315                                 _Rb_tree_node_base& __header);
    00316
    00317   _Rb_tree_node_base*
    00318   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
    00319                    _Rb_tree_node_base& __header);
    00320
    00321
    00322   template<typename _Key, typename _Val, typename _KeyOfValue,
    00323            typename _Compare, typename _Alloc = allocator<_Val> >
    00324     class _Rb_tree
    00325     {
    00326       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
    00327               _Node_allocator;
    00328
    00329     protected:
    00330       typedef _Rb_tree_node_base* _Base_ptr;
    00331       typedef const _Rb_tree_node_base* _Const_Base_ptr;
    00332       typedef _Rb_tree_node<_Val> _Rb_tree_node;
    00333
    00334     public:
    00335       typedef _Key key_type;
    00336       typedef _Val value_type;
    00337       typedef value_type* pointer;
    00338       typedef const value_type* const_pointer;
    00339       typedef value_type& reference;
    00340       typedef const value_type& const_reference;
    00341       typedef _Rb_tree_node* _Link_type;
    00342       typedef const _Rb_tree_node* _Const_Link_type;
    00343       typedef size_t size_type;
    00344       typedef ptrdiff_t difference_type;
    00345       typedef _Alloc allocator_type;
    00346
    00347       allocator_type
    00348       get_allocator() const
    00349       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
    00350
    00351     protected:
    00352       _Rb_tree_node*
    00353       _M_get_node()
    00354       { return _M_impl._Node_allocator::allocate(1); }
    00355
    00356       void
    00357       _M_put_node(_Rb_tree_node* __p)
    00358       { _M_impl._Node_allocator::deallocate(__p, 1); }
    00359
    00360       _Link_type
    00361       _M_create_node(const value_type& __x)
    00362       {
    00363     _Link_type __tmp = _M_get_node();
    00364     try
    00365       { std::_Construct(&__tmp->_M_value_field, __x); }
    00366     catch(...)
    00367       {
    00368         _M_put_node(__tmp);
    00369         __throw_exception_again;
    00370       }
    00371     return __tmp;
    00372       }
    00373
    00374       _Link_type
    00375       _M_clone_node(_Const_Link_type __x)
    00376       {
    00377     _Link_type __tmp = _M_create_node(__x->_M_value_field);
    00378     __tmp->_M_color = __x->_M_color;
    00379     __tmp->_M_left = 0;
    00380     __tmp->_M_right = 0;
    00381     return __tmp;
    00382       }
    00383
    00384       void
    00385       destroy_node(_Link_type __p)
    00386       {
    00387     std::_Destroy(&__p->_M_value_field);
    00388     _M_put_node(__p);
    00389       }
    00390
    00391     protected:
    00392       template<typename _Key_compare,
    00393            bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
    00394         struct _Rb_tree_impl : public _Node_allocator
    00395         {
    00396       _Key_compare      _M_key_compare;
    00397       _Rb_tree_node_base    _M_header;
    00398       size_type         _M_node_count; // Keeps track of size of tree.
    00399
    00400       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
    00401             const _Key_compare& __comp = _Key_compare())
    00402       : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
    00403       {
    00404         this->_M_header._M_color = _S_red;
    00405         this->_M_header._M_parent = 0;
    00406         this->_M_header._M_left = &this->_M_header;
    00407         this->_M_header._M_right = &this->_M_header;
    00408       }
    00409     };
    00410
    00411       // Specialization for _Comparison types that are not capable of
    00412       // being base classes / super classes.
    00413       template<typename _Key_compare>
    00414         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
    00415     {
    00416       _Key_compare      _M_key_compare;
    00417       _Rb_tree_node_base    _M_header;
    00418       size_type         _M_node_count; // Keeps track of size of tree.
    00419
    00420       _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
    00421             const _Key_compare& __comp = _Key_compare())
    00422       : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
    00423       {
    00424         this->_M_header._M_color = _S_red;
    00425         this->_M_header._M_parent = 0;
    00426         this->_M_header._M_left = &this->_M_header;
    00427         this->_M_header._M_right = &this->_M_header;
    00428       }
    00429     };
    00430
    00431       _Rb_tree_impl<_Compare> _M_impl;
    00432
    00433     protected:
    00434       _Base_ptr&
    00435       _M_root()
    00436       { return this->_M_impl._M_header._M_parent; }
    00437
    00438       _Const_Base_ptr
    00439       _M_root() const
    00440       { return this->_M_impl._M_header._M_parent; }
    00441
    00442       _Base_ptr&
    00443       _M_leftmost()
    00444       { return this->_M_impl._M_header._M_left; }
    00445
    00446       _Const_Base_ptr
    00447       _M_leftmost() const
    00448       { return this->_M_impl._M_header._M_left; }
    00449
    00450       _Base_ptr&
    00451       _M_rightmost()
    00452       { return this->_M_impl._M_header._M_right; }
    00453
    00454       _Const_Base_ptr
    00455       _M_rightmost() const
    00456       { return this->_M_impl._M_header._M_right; }
    00457
    00458       _Link_type
    00459       _M_begin()
    00460       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
    00461
    00462       _Const_Link_type
    00463       _M_begin() const
    00464       { return static_cast<
    00465       _Const_Link_type>(this->_M_impl._M_header._M_parent); }
    00466
    00467       _Link_type
    00468       _M_end()
    00469       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
    00470
    00471       _Const_Link_type
    00472       _M_end() const
    00473       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
    00474
    00475       static const_reference
    00476       _S_value(_Const_Link_type __x)
    00477       { return __x->_M_value_field; }
    00478
    00479       static const _Key&
    00480       _S_key(_Const_Link_type __x)
    00481       { return _KeyOfValue()(_S_value(__x)); }
    00482
    00483       static _Link_type
    00484       _S_left(_Base_ptr __x)
    00485       { return static_cast<_Link_type>(__x->_M_left); }
    00486
    00487       static _Const_Link_type
    00488       _S_left(_Const_Base_ptr __x)
    00489       { return static_cast<_Const_Link_type>(__x->_M_left); }
    00490
    00491       static _Link_type
    00492       _S_right(_Base_ptr __x)
    00493       { return static_cast<_Link_type>(__x->_M_right); }
    00494
    00495       static _Const_Link_type
    00496       _S_right(_Const_Base_ptr __x)
    00497       { return static_cast<_Const_Link_type>(__x->_M_right); }
    00498
    00499       static const_reference
    00500       _S_value(_Const_Base_ptr __x)
    00501       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
    00502
    00503       static const _Key&
    00504       _S_key(_Const_Base_ptr __x)
    00505       { return _KeyOfValue()(_S_value(__x)); }
    00506
    00507       static _Base_ptr
    00508       _S_minimum(_Base_ptr __x)
    00509       { return _Rb_tree_node_base::_S_minimum(__x); }
    00510
    00511       static _Const_Base_ptr
    00512       _S_minimum(_Const_Base_ptr __x)
    00513       { return _Rb_tree_node_base::_S_minimum(__x); }
    00514
    00515       static _Base_ptr
    00516       _S_maximum(_Base_ptr __x)
    00517       { return _Rb_tree_node_base::_S_maximum(__x); }
    00518
    00519       static _Const_Base_ptr
    00520       _S_maximum(_Const_Base_ptr __x)
    00521       { return _Rb_tree_node_base::_S_maximum(__x); }
    00522
    00523     public:
    00524       typedef _Rb_tree_iterator<value_type>       iterator;
    00525       typedef _Rb_tree_const_iterator<value_type> const_iterator;
    00526
    00527       typedef std::reverse_iterator<iterator>       reverse_iterator;
    00528       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00529
    00530     private:
    00531       iterator
    00532       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
    00533
    00534       _Link_type
    00535       _M_copy(_Const_Link_type __x, _Link_type __p);
    00536
    00537       void
    00538       _M_erase(_Link_type __x);
    00539
    00540     public:
    00541       // allocation/deallocation
    00542       _Rb_tree()
    00543       { }
    00544
    00545       _Rb_tree(const _Compare& __comp)
    00546       : _M_impl(allocator_type(), __comp)
    00547       { }
    00548
    00549       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
    00550       : _M_impl(__a, __comp)
    00551       { }
    00552
    00553       _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
    00554       : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
    00555       {
    00556     if (__x._M_root() != 0)
    00557       {
    00558         _M_root() = _M_copy(__x._M_begin(), _M_end());
    00559         _M_leftmost() = _S_minimum(_M_root());
    00560         _M_rightmost() = _S_maximum(_M_root());
    00561         _M_impl._M_node_count = __x._M_impl._M_node_count;
    00562       }
    00563       }
    00564
    00565       ~_Rb_tree()
    00566       { _M_erase(_M_begin()); }
    00567
    00568       _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
    00569       operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
    00570
    00571       // Accessors.
    00572       _Compare
    00573       key_comp() const
    00574       { return _M_impl._M_key_compare; }
    00575
    00576       iterator
    00577       begin()
    00578       { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
    00579
    00580       const_iterator
    00581       begin() const
    00582       { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
    00583
    00584       iterator
    00585       end()
    00586       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
    00587
    00588       const_iterator
    00589       end() const
    00590       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
    00591
    00592       reverse_iterator
    00593       rbegin()
    00594       { return reverse_iterator(end()); }
    00595
    00596       const_reverse_iterator
    00597       rbegin() const
    00598       { return const_reverse_iterator(end()); }
    00599
    00600       reverse_iterator
    00601       rend()
    00602       { return reverse_iterator(begin()); }
    00603
    00604       const_reverse_iterator
    00605       rend() const
    00606       { return const_reverse_iterator(begin()); }
    00607
    00608       bool
    00609       empty() const
    00610       { return _M_impl._M_node_count == 0; }
    00611
    00612       size_type
    00613       size() const
    00614       { return _M_impl._M_node_count; }
    00615
    00616       size_type
    00617       max_size() const
    00618       { return size_type(-1); }
    00619
    00620       void
    00621       swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
    00622
    00623       // Insert/erase.
    00624       pair<iterator,bool>
    00625       insert_unique(const value_type& __x);
    00626
    00627       iterator
    00628       insert_equal(const value_type& __x);
    00629
    00630       iterator
    00631       insert_unique(iterator __position, const value_type& __x);
    00632
    00633       iterator
    00634       insert_equal(iterator __position, const value_type& __x);
    00635
    00636       template<typename _InputIterator>
    00637       void
    00638       insert_unique(_InputIterator __first, _InputIterator __last);
    00639
    00640       template<typename _InputIterator>
    00641       void
    00642       insert_equal(_InputIterator __first, _InputIterator __last);
    00643
    00644       void
    00645       erase(iterator __position);
    00646
    00647       size_type
    00648       erase(const key_type& __x);
    00649
    00650       void
    00651       erase(iterator __first, iterator __last);
    00652
    00653       void
    00654       erase(const key_type* __first, const key_type* __last);
    00655
    00656       void
    00657       clear()
    00658       {
    00659         _M_erase(_M_begin());
    00660         _M_leftmost() = _M_end();
    00661         _M_root() = 0;
    00662         _M_rightmost() = _M_end();
    00663         _M_impl._M_node_count = 0;
    00664       }
    00665
    00666       // Set operations.
    00667       iterator
    00668       find(const key_type& __x);
    00669
    00670       const_iterator
    00671       find(const key_type& __x) const;
    00672
    00673       size_type
    00674       count(const key_type& __x) const;
    00675
    00676       iterator
    00677       lower_bound(const key_type& __x);
    00678
    00679       const_iterator
    00680       lower_bound(const key_type& __x) const;
    00681
    00682       iterator
    00683       upper_bound(const key_type& __x);
    00684
    00685       const_iterator
    00686       upper_bound(const key_type& __x) const;
    00687
    00688       pair<iterator,iterator>
    00689       equal_range(const key_type& __x);
    00690
    00691       pair<const_iterator, const_iterator>
    00692       equal_range(const key_type& __x) const;
    00693
    00694       // Debugging.
    00695       bool
    00696       __rb_verify() const;
    00697     };
    00698
    00699   template<typename _Key, typename _Val, typename _KeyOfValue,
    00700            typename _Compare, typename _Alloc>
    00701     inline bool
    00702     operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
    00703            const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    00704     {
    00705       return __x.size() == __y.size()
    00706          && equal(__x.begin(), __x.end(), __y.begin());
    00707     }
    00708
    00709   template<typename _Key, typename _Val, typename _KeyOfValue,
    00710            typename _Compare, typename _Alloc>
    00711     inline bool
    00712     operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
    00713           const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    00714     {
    00715       return lexicographical_compare(__x.begin(), __x.end(),
    00716                      __y.begin(), __y.end());
    00717     }
    00718
    00719   template<typename _Key, typename _Val, typename _KeyOfValue,
    00720            typename _Compare, typename _Alloc>
    00721     inline bool
    00722     operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
    00723            const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    00724     { return !(__x == __y); }
    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 __y < __x; }
    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 !(__x < __y); }
    00746
    00747   template<typename _Key, typename _Val, typename _KeyOfValue,
    00748            typename _Compare, typename _Alloc>
    00749     inline void
    00750     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
    00751      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    00752     { __x.swap(__y); }
    00753
    00754   template<typename _Key, typename _Val, typename _KeyOfValue,
    00755            typename _Compare, typename _Alloc>
    00756     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
    00757     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    00758     operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
    00759     {
    00760       if (this != &__x)
    00761     {
    00762       // Note that _Key may be a constant type.
    00763       clear();
    00764       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
    00765       if (__x._M_root() != 0)
    00766         {
    00767           _M_root() = _M_copy(__x._M_begin(), _M_end());
    00768           _M_leftmost() = _S_minimum(_M_root());
    00769           _M_rightmost() = _S_maximum(_M_root());
    00770           _M_impl._M_node_count = __x._M_impl._M_node_count;
    00771         }
    00772     }
    00773       return *this;
    00774     }
    00775
    00776   template<typename _Key, typename _Val, typename _KeyOfValue,
    00777            typename _Compare, typename _Alloc>
    00778     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    00779     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    00780     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
    00781     {
    00782       _Link_type __z = _M_create_node(__v);
    00783       bool __insert_left;
    00784
    00785       __insert_left = __x != 0 || __p == _M_end()
    00786                   || _M_impl._M_key_compare(_KeyOfValue()(__v),
    00787                         _S_key(__p));
    00788
    00789       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
    00790                     this->_M_impl._M_header);
    00791       ++_M_impl._M_node_count;
    00792       return iterator(__z);
    00793     }
    00794
    00795   template<typename _Key, typename _Val, typename _KeyOfValue,
    00796            typename _Compare, typename _Alloc>
    00797     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    00798     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    00799     insert_equal(const _Val& __v)
    00800     {
    00801       _Link_type __x = _M_begin();
    00802       _Link_type __y = _M_end();
    00803       while (__x != 0)
    00804     {
    00805       __y = __x;
    00806       __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
    00807             _S_left(__x) : _S_right(__x);
    00808     }
    00809       return _M_insert(__x, __y, __v);
    00810     }
    00811
    00812   template<typename _Key, typename _Val, typename _KeyOfValue,
    00813            typename _Compare, typename _Alloc>
    00814     void
    00815     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    00816     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
    00817     {
    00818       if (_M_root() == 0)
    00819       {
    00820     if (__t._M_root() != 0)
    00821     {
    00822       _M_root() = __t._M_root();
    00823       _M_leftmost() = __t._M_leftmost();
    00824       _M_rightmost() = __t._M_rightmost();
    00825           _M_root()->_M_parent = _M_end();
    00826
    00827       __t._M_root() = 0;
    00828       __t._M_leftmost() = __t._M_end();
    00829       __t._M_rightmost() = __t._M_end();
    00830     }
    00831       }
    00832       else if (__t._M_root() == 0)
    00833       {
    00834     __t._M_root() = _M_root();
    00835     __t._M_leftmost() = _M_leftmost();
    00836     __t._M_rightmost() = _M_rightmost();
    00837         __t._M_root()->_M_parent = __t._M_end();
    00838
    00839     _M_root() = 0;
    00840     _M_leftmost() = _M_end();
    00841     _M_rightmost() = _M_end();
    00842       }
    00843       else
    00844       {
    00845     std::swap(_M_root(),__t._M_root());
    00846     std::swap(_M_leftmost(),__t._M_leftmost());
    00847     std::swap(_M_rightmost(),__t._M_rightmost());
    00848
    00849     _M_root()->_M_parent = _M_end();
    00850     __t._M_root()->_M_parent = __t._M_end();
    00851       }
    00852       // No need to swap header's color as it does not change.
    00853       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
    00854       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
    00855     }
    00856
    00857   template<typename _Key, typename _Val, typename _KeyOfValue,
    00858            typename _Compare, typename _Alloc>
    00859     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
    00860     bool>
    00861     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    00862     insert_unique(const _Val& __v)
    00863     {
    00864       _Link_type __x = _M_begin();
    00865       _Link_type __y = _M_end();
    00866       bool __comp = true;
    00867       while (__x != 0)
    00868     {
    00869       __y = __x;
    00870       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
    00871       __x = __comp ? _S_left(__x) : _S_right(__x);
    00872     }
    00873       iterator __j = iterator(__y);
    00874       if (__comp)
    00875     if (__j == begin())
    00876       return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
    00877     else
    00878       --__j;
    00879       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
    00880     return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
    00881       return pair<iterator,bool>(__j, false);
    00882     }
    00883
    00884   template<typename _Key, typename _Val, typename _KeyOfValue,
    00885            typename _Compare, typename _Alloc>
    00886     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    00887     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    00888     insert_unique(iterator __position, const _Val& __v)
    00889     {
    00890       if (__position._M_node == _M_leftmost())
    00891     {
    00892       // begin()
    00893       if (size() > 0
    00894           && _M_impl._M_key_compare(_KeyOfValue()(__v),
    00895                     _S_key(__position._M_node)))
    00896         return _M_insert(__position._M_node, __position._M_node, __v);
    00897       // First argument just needs to be non-null.
    00898       else
    00899         return insert_unique(__v).first;
    00900     }
    00901       else if (__position._M_node == _M_end())
    00902     {
    00903       // end()
    00904       if (_M_impl._M_key_compare(_S_key(_M_rightmost()),
    00905                      _KeyOfValue()(__v)))
    00906         return _M_insert(0, _M_rightmost(), __v);
    00907       else
    00908         return insert_unique(__v).first;
    00909     }
    00910       else
    00911     {
    00912       iterator __before = __position;
    00913       --__before;
    00914       if (_M_impl._M_key_compare(_S_key(__before._M_node),
    00915                      _KeyOfValue()(__v))
    00916           && _M_impl._M_key_compare(_KeyOfValue()(__v),
    00917                     _S_key(__position._M_node)))
    00918         {
    00919           if (_S_right(__before._M_node) == 0)
    00920         return _M_insert(0, __before._M_node, __v);
    00921           else
    00922         return _M_insert(__position._M_node, __position._M_node, __v);
    00923           // First argument just needs to be non-null.
    00924         }
    00925       else
    00926         return insert_unique(__v).first;
    00927     }
    00928     }
    00929
    00930   template<typename _Key, typename _Val, typename _KeyOfValue,
    00931            typename _Compare, typename _Alloc>
    00932     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    00933     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    00934     insert_equal(iterator __position, const _Val& __v)
    00935     {
    00936       if (__position._M_node == _M_leftmost())
    00937     {
    00938       // begin()
    00939       if (size() > 0
    00940           && !_M_impl._M_key_compare(_S_key(__position._M_node),
    00941                      _KeyOfValue()(__v)))
    00942         return _M_insert(__position._M_node, __position._M_node, __v);
    00943       // first argument just needs to be non-null
    00944       else
    00945         return insert_equal(__v);
    00946     }
    00947       else if (__position._M_node == _M_end())
    00948     {
    00949       // end()
    00950       if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
    00951                       _S_key(_M_rightmost())))
    00952         return _M_insert(0, _M_rightmost(), __v);
    00953       else
    00954         return insert_equal(__v);
    00955     }
    00956       else
    00957     {
    00958       iterator __before = __position;
    00959       --__before;
    00960       if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
    00961                       _S_key(__before._M_node))
    00962           && !_M_impl._M_key_compare(_S_key(__position._M_node),
    00963                      _KeyOfValue()(__v)))
    00964         {
    00965           if (_S_right(__before._M_node) == 0)
    00966         return _M_insert(0, __before._M_node, __v);
    00967           else
    00968         return _M_insert(__position._M_node, __position._M_node, __v);
    00969           // First argument just needs to be non-null.
    00970         }
    00971       else
    00972         return insert_equal(__v);
    00973     }
    00974     }
    00975
    00976   template<typename _Key, typename _Val, typename _KoV,
    00977            typename _Cmp, typename _Alloc>
    00978     template<class _II>
    00979       void
    00980       _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
    00981       insert_equal(_II __first, _II __last)
    00982       {
    00983     for ( ; __first != __last; ++__first)
    00984       insert_equal(*__first);
    00985       }
    00986
    00987   template<typename _Key, typename _Val, typename _KoV,
    00988            typename _Cmp, typename _Alloc>
    00989     template<class _II>
    00990     void
    00991     _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
    00992     insert_unique(_II __first, _II __last)
    00993     {
    00994       for ( ; __first != __last; ++__first)
    00995     insert_unique(*__first);
    00996     }
    00997
    00998   template<typename _Key, typename _Val, typename _KeyOfValue,
    00999            typename _Compare, typename _Alloc>
    01000     inline void
    01001     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
    01002     {
    01003       _Link_type __y = static_cast<
    01004     _Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
    01005                          this->_M_impl._M_header));
    01006       destroy_node(__y);
    01007       --_M_impl._M_node_count;
    01008     }
    01009
    01010   template<typename _Key, typename _Val, typename _KeyOfValue,
    01011            typename _Compare, typename _Alloc>
    01012     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
    01013     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
    01014     {
    01015       pair<iterator,iterator> __p = equal_range(__x);
    01016       size_type __n = std::distance(__p.first, __p.second);
    01017       erase(__p.first, __p.second);
    01018       return __n;
    01019     }
    01020
    01021   template<typename _Key, typename _Val, typename _KoV,
    01022            typename _Compare, typename _Alloc>
    01023     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
    01024     _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
    01025     _M_copy(_Const_Link_type __x, _Link_type __p)
    01026     {
    01027       // Structural copy.  __x and __p must be non-null.
    01028       _Link_type __top = _M_clone_node(__x);
    01029       __top->_M_parent = __p;
    01030
    01031       try
    01032     {
    01033       if (__x->_M_right)
    01034         __top->_M_right = _M_copy(_S_right(__x), __top);
    01035       __p = __top;
    01036       __x = _S_left(__x);
    01037
    01038       while (__x != 0)
    01039         {
    01040           _Link_type __y = _M_clone_node(__x);
    01041           __p->_M_left = __y;
    01042           __y->_M_parent = __p;
    01043           if (__x->_M_right)
    01044         __y->_M_right = _M_copy(_S_right(__x), __y);
    01045           __p = __y;
    01046           __x = _S_left(__x);
    01047         }
    01048     }
    01049       catch(...)
    01050     {
    01051       _M_erase(__top);
    01052       __throw_exception_again;
    01053     }
    01054       return __top;
    01055     }
    01056
    01057   template<typename _Key, typename _Val, typename _KeyOfValue,
    01058            typename _Compare, typename _Alloc>
    01059     void
    01060     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
    01061     {
    01062       // Erase without rebalancing.
    01063       while (__x != 0)
    01064     {
    01065       _M_erase(_S_right(__x));
    01066       _Link_type __y = _S_left(__x);
    01067       destroy_node(__x);
    01068       __x = __y;
    01069     }
    01070     }
    01071
    01072   template<typename _Key, typename _Val, typename _KeyOfValue,
    01073            typename _Compare, typename _Alloc>
    01074     void
    01075     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01076     erase(iterator __first, iterator __last)
    01077     {
    01078       if (__first == begin() && __last == end())
    01079     clear();
    01080       else
    01081     while (__first != __last) erase(__first++);
    01082     }
    01083
    01084   template<typename _Key, typename _Val, typename _KeyOfValue,
    01085            typename _Compare, typename _Alloc>
    01086     void
    01087     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01088     erase(const _Key* __first, const _Key* __last)
    01089     {
    01090       while (__first != __last)
    01091     erase(*__first++);
    01092     }
    01093
    01094   template<typename _Key, typename _Val, typename _KeyOfValue,
    01095            typename _Compare, typename _Alloc>
    01096     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    01097     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
    01098     {
    01099       _Link_type __x = _M_begin(); // Current node.
    01100       _Link_type __y = _M_end(); // Last node which is not less than __k.
    01101
    01102       while (__x != 0)
    01103     if (!_M_impl._M_key_compare(_S_key(__x), __k))
    01104       __y = __x, __x = _S_left(__x);
    01105     else
    01106       __x = _S_right(__x);
    01107
    01108       iterator __j = iterator(__y);
    01109       return (__j == end()
    01110       || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
    01111     }
    01112
    01113   template<typename _Key, typename _Val, typename _KeyOfValue,
    01114            typename _Compare, typename _Alloc>
    01115     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
    01116     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01117     find(const _Key& __k) const
    01118     {
    01119       _Const_Link_type __x = _M_begin(); // Current node.
    01120       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
    01121
    01122      while (__x != 0)
    01123        {
    01124      if (!_M_impl._M_key_compare(_S_key(__x), __k))
    01125        __y = __x, __x = _S_left(__x);
    01126      else
    01127        __x = _S_right(__x);
    01128        }
    01129      const_iterator __j = const_iterator(__y);
    01130      return (__j == end()
    01131       || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
    01132     }
    01133
    01134   template<typename _Key, typename _Val, typename _KeyOfValue,
    01135            typename _Compare, typename _Alloc>
    01136     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
    01137     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01138     count(const _Key& __k) const
    01139     {
    01140       pair<const_iterator, const_iterator> __p = equal_range(__k);
    01141       const size_type __n = std::distance(__p.first, __p.second);
    01142       return __n;
    01143     }
    01144
    01145   template<typename _Key, typename _Val, typename _KeyOfValue,
    01146            typename _Compare, typename _Alloc>
    01147     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    01148     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01149     lower_bound(const _Key& __k)
    01150     {
    01151       _Link_type __x = _M_begin(); // Current node.
    01152       _Link_type __y = _M_end(); // Last node which is not less than __k.
    01153
    01154       while (__x != 0)
    01155     if (!_M_impl._M_key_compare(_S_key(__x), __k))
    01156       __y = __x, __x = _S_left(__x);
    01157     else
    01158       __x = _S_right(__x);
    01159
    01160       return iterator(__y);
    01161     }
    01162
    01163   template<typename _Key, typename _Val, typename _KeyOfValue,
    01164            typename _Compare, typename _Alloc>
    01165     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
    01166     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01167     lower_bound(const _Key& __k) const
    01168     {
    01169       _Const_Link_type __x = _M_begin(); // Current node.
    01170       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
    01171
    01172       while (__x != 0)
    01173     if (!_M_impl._M_key_compare(_S_key(__x), __k))
    01174       __y = __x, __x = _S_left(__x);
    01175     else
    01176       __x = _S_right(__x);
    01177
    01178       return const_iterator(__y);
    01179     }
    01180
    01181   template<typename _Key, typename _Val, typename _KeyOfValue,
    01182            typename _Compare, typename _Alloc>
    01183     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    01184     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01185     upper_bound(const _Key& __k)
    01186     {
    01187       _Link_type __x = _M_begin(); // Current node.
    01188       _Link_type __y = _M_end(); // Last node which is greater than __k.
    01189
    01190       while (__x != 0)
    01191     if (_M_impl._M_key_compare(__k, _S_key(__x)))
    01192       __y = __x, __x = _S_left(__x);
    01193     else
    01194       __x = _S_right(__x);
    01195
    01196       return iterator(__y);
    01197     }
    01198
    01199   template<typename _Key, typename _Val, typename _KeyOfValue,
    01200            typename _Compare, typename _Alloc>
    01201     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
    01202     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01203     upper_bound(const _Key& __k) const
    01204     {
    01205       _Const_Link_type __x = _M_begin(); // Current node.
    01206       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
    01207
    01208       while (__x != 0)
    01209     if (_M_impl._M_key_compare(__k, _S_key(__x)))
    01210       __y = __x, __x = _S_left(__x);
    01211     else
    01212       __x = _S_right(__x);
    01213
    01214       return const_iterator(__y);
    01215     }
    01216
    01217   template<typename _Key, typename _Val, typename _KeyOfValue,
    01218            typename _Compare, typename _Alloc>
    01219     inline
    01220     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,
    01221                _Compare,_Alloc>::iterator,
    01222      typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
    01223     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    01224     equal_range(const _Key& __k)
    01225     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
    01226
    01227   template<typename _Key, typename _Val, typename _KoV,
    01228            typename _Compare, typename _Alloc>
    01229     inline
    01230     pair<typename _Rb_tree<_Key, _Val, _KoV,
    01231                _Compare, _Alloc>::const_iterator,
    01232      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
    01233     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    01234     equal_range(const _Key& __k) const
    01235     { return pair<const_iterator, const_iterator>(lower_bound(__k),
    01236                           upper_bound(__k)); }
    01237
    01238   unsigned int
    01239   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
    01240                        const _Rb_tree_node_base* __root);
    01241
    01242   template<typename _Key, typename _Val, typename _KeyOfValue,
    01243            typename _Compare, typename _Alloc>
    01244     bool
    01245     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
    01246     {
    01247       if (_M_impl._M_node_count == 0 || begin() == end())
    01248     return _M_impl._M_node_count == 0 && begin() == end()
    01249            && this->_M_impl._M_header._M_left == _M_end()
    01250            && this->_M_impl._M_header._M_right == _M_end();
    01251
    01252       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
    01253       for (const_iterator __it = begin(); __it != end(); ++__it)
    01254     {
    01255       _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
    01256       _Const_Link_type __L = _S_left(__x);
    01257       _Const_Link_type __R = _S_right(__x);
    01258
    01259       if (__x->_M_color == _S_red)
    01260         if ((__L && __L->_M_color == _S_red)
    01261         || (__R && __R->_M_color == _S_red))
    01262           return false;
    01263
    01264       if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
    01265         return false;
    01266       if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
    01267         return false;
    01268
    01269       if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
    01270         return false;
    01271     }
    01272
    01273       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
    01274     return false;
    01275       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
    01276     return false;
    01277       return true;
    01278     }
    01279 } // namespace std
    01280
    01281 #endif