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