# stl_tree.h

Go to the documentation of this file.

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