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
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 #else
00764       void
00765       erase(const_iterator __position)
00766       { _M_erase_aux(__position); }
00767 #endif
00768       size_type
00769       erase(const key_type& __x);
00770 
00771 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00772       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00773       // DR 130. Associative erase should return an iterator.
00774       iterator
00775       erase(const_iterator __first, const_iterator __last)
00776       {
00777     _M_erase_aux(__first, __last);
00778     return __last._M_const_cast();
00779       }
00780 #else
00781       void
00782       erase(const_iterator __first, const_iterator __last)
00783       { _M_erase_aux(__first, __last); }
00784 #endif
00785       void
00786       erase(const key_type* __first, const key_type* __last);
00787 
00788       void
00789       clear()
00790       {
00791         _M_erase(_M_begin());
00792         _M_leftmost() = _M_end();
00793         _M_root() = 0;
00794         _M_rightmost() = _M_end();
00795         _M_impl._M_node_count = 0;
00796       }
00797 
00798       // Set operations.
00799       iterator
00800       find(const key_type& __k);
00801 
00802       const_iterator
00803       find(const key_type& __k) const;
00804 
00805       size_type
00806       count(const key_type& __k) const;
00807 
00808       iterator
00809       lower_bound(const key_type& __k)
00810       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00811 
00812       const_iterator
00813       lower_bound(const key_type& __k) const
00814       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00815 
00816       iterator
00817       upper_bound(const key_type& __k)
00818       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00819 
00820       const_iterator
00821       upper_bound(const key_type& __k) const
00822       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00823 
00824       pair<iterator, iterator>
00825       equal_range(const key_type& __k);
00826 
00827       pair<const_iterator, const_iterator>
00828       equal_range(const key_type& __k) const;
00829 
00830       // Debugging.
00831       bool
00832       __rb_verify() const;
00833     };
00834 
00835   template<typename _Key, typename _Val, typename _KeyOfValue,
00836            typename _Compare, typename _Alloc>
00837     inline bool
00838     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00839            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00840     {
00841       return __x.size() == __y.size()
00842          && std::equal(__x.begin(), __x.end(), __y.begin());
00843     }
00844 
00845   template<typename _Key, typename _Val, typename _KeyOfValue,
00846            typename _Compare, typename _Alloc>
00847     inline bool
00848     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00849           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00850     {
00851       return std::lexicographical_compare(__x.begin(), __x.end(), 
00852                       __y.begin(), __y.end());
00853     }
00854 
00855   template<typename _Key, typename _Val, typename _KeyOfValue,
00856            typename _Compare, typename _Alloc>
00857     inline bool
00858     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00859            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00860     { return !(__x == __y); }
00861 
00862   template<typename _Key, typename _Val, typename _KeyOfValue,
00863            typename _Compare, typename _Alloc>
00864     inline bool
00865     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00866           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00867     { return __y < __x; }
00868 
00869   template<typename _Key, typename _Val, typename _KeyOfValue,
00870            typename _Compare, typename _Alloc>
00871     inline bool
00872     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00873            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00874     { return !(__y < __x); }
00875 
00876   template<typename _Key, typename _Val, typename _KeyOfValue,
00877            typename _Compare, typename _Alloc>
00878     inline bool
00879     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00880            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00881     { return !(__x < __y); }
00882 
00883   template<typename _Key, typename _Val, typename _KeyOfValue,
00884            typename _Compare, typename _Alloc>
00885     inline void
00886     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00887      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00888     { __x.swap(__y); }
00889 
00890 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00891   template<typename _Key, typename _Val, typename _KeyOfValue,
00892            typename _Compare, typename _Alloc>
00893     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00894     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
00895     : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
00896     {
00897       if (__x._M_root() != 0)
00898     {
00899       _M_root() = __x._M_root();
00900       _M_leftmost() = __x._M_leftmost();
00901       _M_rightmost() = __x._M_rightmost();
00902       _M_root()->_M_parent = _M_end();
00903 
00904       __x._M_root() = 0;
00905       __x._M_leftmost() = __x._M_end();
00906       __x._M_rightmost() = __x._M_end();
00907 
00908       this->_M_impl._M_node_count = __x._M_impl._M_node_count;
00909       __x._M_impl._M_node_count = 0;
00910     }
00911     }
00912 #endif
00913 
00914   template<typename _Key, typename _Val, typename _KeyOfValue,
00915            typename _Compare, typename _Alloc>
00916     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00917     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00918     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00919     {
00920       if (this != &__x)
00921     {
00922       // Note that _Key may be a constant type.
00923       clear();
00924       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00925       if (__x._M_root() != 0)
00926         {
00927           _M_root() = _M_copy(__x._M_begin(), _M_end());
00928           _M_leftmost() = _S_minimum(_M_root());
00929           _M_rightmost() = _S_maximum(_M_root());
00930           _M_impl._M_node_count = __x._M_impl._M_node_count;
00931         }
00932     }
00933       return *this;
00934     }
00935 
00936   template<typename _Key, typename _Val, typename _KeyOfValue,
00937            typename _Compare, typename _Alloc>
00938 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00939     template<typename _Arg>
00940 #endif
00941     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00942     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00943 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00944     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
00945 #else
00946     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
00947 #endif
00948     {
00949       bool __insert_left = (__x != 0 || __p == _M_end()
00950                 || _M_impl._M_key_compare(_KeyOfValue()(__v), 
00951                               _S_key(__p)));
00952 
00953       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
00954 
00955       _Rb_tree_insert_and_rebalance(__insert_left, __z,
00956                     const_cast<_Base_ptr>(__p),  
00957                     this->_M_impl._M_header);
00958       ++_M_impl._M_node_count;
00959       return iterator(__z);
00960     }
00961 
00962   template<typename _Key, typename _Val, typename _KeyOfValue,
00963            typename _Compare, typename _Alloc>
00964 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00965     template<typename _Arg>
00966 #endif
00967     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00968     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00969 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00970     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
00971 #else
00972     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00973 #endif
00974     {
00975       bool __insert_left = (__x != 0 || __p == _M_end()
00976                 || !_M_impl._M_key_compare(_S_key(__p),
00977                                _KeyOfValue()(__v)));
00978 
00979       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
00980 
00981       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
00982                     this->_M_impl._M_header);
00983       ++_M_impl._M_node_count;
00984       return iterator(__z);
00985     }
00986 
00987   template<typename _Key, typename _Val, typename _KeyOfValue,
00988            typename _Compare, typename _Alloc>
00989 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00990     template<typename _Arg>
00991 #endif
00992     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00993     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00994 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00995     _M_insert_equal_lower(_Arg&& __v)
00996 #else
00997     _M_insert_equal_lower(const _Val& __v)
00998 #endif
00999     {
01000       _Link_type __x = _M_begin();
01001       _Link_type __y = _M_end();
01002       while (__x != 0)
01003     {
01004       __y = __x;
01005       __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
01006             _S_left(__x) : _S_right(__x);
01007     }
01008       return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
01009     }
01010 
01011   template<typename _Key, typename _Val, typename _KoV,
01012            typename _Compare, typename _Alloc>
01013     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01014     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01015     _M_copy(_Const_Link_type __x, _Link_type __p)
01016     {
01017       // Structural copy.  __x and __p must be non-null.
01018       _Link_type __top = _M_clone_node(__x);
01019       __top->_M_parent = __p;
01020 
01021       __try
01022     {
01023       if (__x->_M_right)
01024         __top->_M_right = _M_copy(_S_right(__x), __top);
01025       __p = __top;
01026       __x = _S_left(__x);
01027 
01028       while (__x != 0)
01029         {
01030           _Link_type __y = _M_clone_node(__x);
01031           __p->_M_left = __y;
01032           __y->_M_parent = __p;
01033           if (__x->_M_right)
01034         __y->_M_right = _M_copy(_S_right(__x), __y);
01035           __p = __y;
01036           __x = _S_left(__x);
01037         }
01038     }
01039       __catch(...)
01040     {
01041       _M_erase(__top);
01042       __throw_exception_again;
01043     }
01044       return __top;
01045     }
01046 
01047   template<typename _Key, typename _Val, typename _KeyOfValue,
01048            typename _Compare, typename _Alloc>
01049     void
01050     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01051     _M_erase(_Link_type __x)
01052     {
01053       // Erase without rebalancing.
01054       while (__x != 0)
01055     {
01056       _M_erase(_S_right(__x));
01057       _Link_type __y = _S_left(__x);
01058       _M_destroy_node(__x);
01059       __x = __y;
01060     }
01061     }
01062 
01063   template<typename _Key, typename _Val, typename _KeyOfValue,
01064            typename _Compare, typename _Alloc>
01065     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01066               _Compare, _Alloc>::iterator
01067     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01068     _M_lower_bound(_Link_type __x, _Link_type __y,
01069            const _Key& __k)
01070     {
01071       while (__x != 0)
01072     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01073       __y = __x, __x = _S_left(__x);
01074     else
01075       __x = _S_right(__x);
01076       return iterator(__y);
01077     }
01078 
01079   template<typename _Key, typename _Val, typename _KeyOfValue,
01080            typename _Compare, typename _Alloc>
01081     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01082               _Compare, _Alloc>::const_iterator
01083     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01084     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
01085            const _Key& __k) const
01086     {
01087       while (__x != 0)
01088     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01089       __y = __x, __x = _S_left(__x);
01090     else
01091       __x = _S_right(__x);
01092       return const_iterator(__y);
01093     }
01094 
01095   template<typename _Key, typename _Val, typename _KeyOfValue,
01096            typename _Compare, typename _Alloc>
01097     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01098               _Compare, _Alloc>::iterator
01099     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01100     _M_upper_bound(_Link_type __x, _Link_type __y,
01101            const _Key& __k)
01102     {
01103       while (__x != 0)
01104     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01105       __y = __x, __x = _S_left(__x);
01106     else
01107       __x = _S_right(__x);
01108       return iterator(__y);
01109     }
01110 
01111   template<typename _Key, typename _Val, typename _KeyOfValue,
01112            typename _Compare, typename _Alloc>
01113     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01114               _Compare, _Alloc>::const_iterator
01115     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01116     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
01117            const _Key& __k) const
01118     {
01119       while (__x != 0)
01120     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01121       __y = __x, __x = _S_left(__x);
01122     else
01123       __x = _S_right(__x);
01124       return const_iterator(__y);
01125     }
01126 
01127   template<typename _Key, typename _Val, typename _KeyOfValue,
01128            typename _Compare, typename _Alloc>
01129     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01130                _Compare, _Alloc>::iterator,
01131      typename _Rb_tree<_Key, _Val, _KeyOfValue,
01132                _Compare, _Alloc>::iterator>
01133     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01134     equal_range(const _Key& __k)
01135     {
01136       _Link_type __x = _M_begin();
01137       _Link_type __y = _M_end();
01138       while (__x != 0)
01139     {
01140       if (_M_impl._M_key_compare(_S_key(__x), __k))
01141         __x = _S_right(__x);
01142       else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01143         __y = __x, __x = _S_left(__x);
01144       else
01145         {
01146           _Link_type __xu(__x), __yu(__y);
01147           __y = __x, __x = _S_left(__x);
01148           __xu = _S_right(__xu);
01149           return pair<iterator,
01150                   iterator>(_M_lower_bound(__x, __y, __k),
01151                     _M_upper_bound(__xu, __yu, __k));
01152         }
01153     }
01154       return pair<iterator, iterator>(iterator(__y),
01155                       iterator(__y));
01156     }
01157 
01158   template<typename _Key, typename _Val, typename _KeyOfValue,
01159            typename _Compare, typename _Alloc>
01160     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01161                _Compare, _Alloc>::const_iterator,
01162      typename _Rb_tree<_Key, _Val, _KeyOfValue,
01163                _Compare, _Alloc>::const_iterator>
01164     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01165     equal_range(const _Key& __k) const
01166     {
01167       _Const_Link_type __x = _M_begin();
01168       _Const_Link_type __y = _M_end();
01169       while (__x != 0)
01170     {
01171       if (_M_impl._M_key_compare(_S_key(__x), __k))
01172         __x = _S_right(__x);
01173       else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01174         __y = __x, __x = _S_left(__x);
01175       else
01176         {
01177           _Const_Link_type __xu(__x), __yu(__y);
01178           __y = __x, __x = _S_left(__x);
01179           __xu = _S_right(__xu);
01180           return pair<const_iterator,
01181                   const_iterator>(_M_lower_bound(__x, __y, __k),
01182                       _M_upper_bound(__xu, __yu, __k));
01183         }
01184     }
01185       return pair<const_iterator, const_iterator>(const_iterator(__y),
01186                           const_iterator(__y));
01187     }
01188 
01189   template<typename _Key, typename _Val, typename _KeyOfValue,
01190            typename _Compare, typename _Alloc>
01191     void
01192     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01193     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
01194     {
01195       if (_M_root() == 0)
01196     {
01197       if (__t._M_root() != 0)
01198         {
01199           _M_root() = __t._M_root();
01200           _M_leftmost() = __t._M_leftmost();
01201           _M_rightmost() = __t._M_rightmost();
01202           _M_root()->_M_parent = _M_end();
01203           
01204           __t._M_root() = 0;
01205           __t._M_leftmost() = __t._M_end();
01206           __t._M_rightmost() = __t._M_end();
01207         }
01208     }
01209       else if (__t._M_root() == 0)
01210     {
01211       __t._M_root() = _M_root();
01212       __t._M_leftmost() = _M_leftmost();
01213       __t._M_rightmost() = _M_rightmost();
01214       __t._M_root()->_M_parent = __t._M_end();
01215       
01216       _M_root() = 0;
01217       _M_leftmost() = _M_end();
01218       _M_rightmost() = _M_end();
01219     }
01220       else
01221     {
01222       std::swap(_M_root(),__t._M_root());
01223       std::swap(_M_leftmost(),__t._M_leftmost());
01224       std::swap(_M_rightmost(),__t._M_rightmost());
01225       
01226       _M_root()->_M_parent = _M_end();
01227       __t._M_root()->_M_parent = __t._M_end();
01228     }
01229       // No need to swap header's color as it does not change.
01230       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01231       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01232       
01233       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01234       // 431. Swapping containers with unequal allocators.
01235       std::__alloc_swap<_Node_allocator>::
01236     _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
01237     }
01238 
01239   template<typename _Key, typename _Val, typename _KeyOfValue,
01240            typename _Compare, typename _Alloc>
01241 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01242     template<typename _Arg>
01243 #endif
01244     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01245                _Compare, _Alloc>::iterator, bool>
01246     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01247 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01248     _M_insert_unique(_Arg&& __v)
01249 #else
01250     _M_insert_unique(const _Val& __v)
01251 #endif
01252     {
01253       _Link_type __x = _M_begin();
01254       _Link_type __y = _M_end();
01255       bool __comp = true;
01256       while (__x != 0)
01257     {
01258       __y = __x;
01259       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
01260       __x = __comp ? _S_left(__x) : _S_right(__x);
01261     }
01262       iterator __j = iterator(__y);
01263       if (__comp)
01264     {
01265       if (__j == begin())
01266         return pair<iterator, bool>
01267           (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
01268       else
01269         --__j;
01270     }
01271       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
01272     return pair<iterator, bool>
01273       (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
01274       return pair<iterator, bool>(__j, false);
01275     }
01276 
01277   template<typename _Key, typename _Val, typename _KeyOfValue,
01278            typename _Compare, typename _Alloc>
01279 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01280     template<typename _Arg>
01281 #endif
01282     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01283     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01284 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01285     _M_insert_equal(_Arg&& __v)
01286 #else
01287     _M_insert_equal(const _Val& __v)
01288 #endif
01289     {
01290       _Link_type __x = _M_begin();
01291       _Link_type __y = _M_end();
01292       while (__x != 0)
01293     {
01294       __y = __x;
01295       __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
01296             _S_left(__x) : _S_right(__x);
01297     }
01298       return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
01299     }
01300 
01301   template<typename _Key, typename _Val, typename _KeyOfValue,
01302            typename _Compare, typename _Alloc>
01303 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01304     template<typename _Arg>
01305 #endif
01306     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01307     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01308 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01309     _M_insert_unique_(const_iterator __position, _Arg&& __v)
01310 #else
01311     _M_insert_unique_(const_iterator __position, const _Val& __v)
01312 #endif
01313     {
01314       // end()
01315       if (__position._M_node == _M_end())
01316     {
01317       if (size() > 0
01318           && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
01319                     _KeyOfValue()(__v)))
01320         return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
01321       else
01322         return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
01323     }
01324       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01325                       _S_key(__position._M_node)))
01326     {
01327       // First, try before...
01328       const_iterator __before = __position;
01329       if (__position._M_node == _M_leftmost()) // begin()
01330         return _M_insert_(_M_leftmost(), _M_leftmost(),
01331                   _GLIBCXX_FORWARD(_Arg, __v));
01332       else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
01333                       _KeyOfValue()(__v)))
01334         {
01335           if (_S_right(__before._M_node) == 0)
01336         return _M_insert_(0, __before._M_node,
01337                   _GLIBCXX_FORWARD(_Arg, __v));
01338           else
01339         return _M_insert_(__position._M_node,
01340                   __position._M_node,
01341                   _GLIBCXX_FORWARD(_Arg, __v));
01342         }
01343       else
01344         return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
01345     }
01346       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
01347                       _KeyOfValue()(__v)))
01348     {
01349       // ... then try after.
01350       const_iterator __after = __position;
01351       if (__position._M_node == _M_rightmost())
01352         return _M_insert_(0, _M_rightmost(),
01353                   _GLIBCXX_FORWARD(_Arg, __v));
01354       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01355                       _S_key((++__after)._M_node)))
01356         {
01357           if (_S_right(__position._M_node) == 0)
01358         return _M_insert_(0, __position._M_node,
01359                   _GLIBCXX_FORWARD(_Arg, __v));
01360           else
01361         return _M_insert_(__after._M_node, __after._M_node,
01362                   _GLIBCXX_FORWARD(_Arg, __v));
01363         }
01364       else
01365         return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
01366     }
01367       else
01368     // Equivalent keys.
01369     return __position._M_const_cast();
01370     }
01371 
01372   template<typename _Key, typename _Val, typename _KeyOfValue,
01373            typename _Compare, typename _Alloc>
01374 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01375     template<typename _Arg>
01376 #endif
01377     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01378     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01379 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01380     _M_insert_equal_(const_iterator __position, _Arg&& __v)
01381 #else
01382     _M_insert_equal_(const_iterator __position, const _Val& __v)
01383 #endif
01384     {
01385       // end()
01386       if (__position._M_node == _M_end())
01387     {
01388       if (size() > 0
01389           && !_M_impl._M_key_compare(_KeyOfValue()(__v),
01390                      _S_key(_M_rightmost())))
01391         return _M_insert_(0, _M_rightmost(),
01392                   _GLIBCXX_FORWARD(_Arg, __v));
01393       else
01394         return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
01395     }
01396       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
01397                        _KeyOfValue()(__v)))
01398     {
01399       // First, try before...
01400       const_iterator __before = __position;
01401       if (__position._M_node == _M_leftmost()) // begin()
01402         return _M_insert_(_M_leftmost(), _M_leftmost(),
01403                   _GLIBCXX_FORWARD(_Arg, __v));
01404       else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
01405                        _S_key((--__before)._M_node)))
01406         {
01407           if (_S_right(__before._M_node) == 0)
01408         return _M_insert_(0, __before._M_node,
01409                   _GLIBCXX_FORWARD(_Arg, __v));
01410           else
01411         return _M_insert_(__position._M_node,
01412                   __position._M_node,
01413                   _GLIBCXX_FORWARD(_Arg, __v));
01414         }
01415       else
01416         return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
01417     }
01418       else
01419     {
01420       // ... then try after.  
01421       const_iterator __after = __position;
01422       if (__position._M_node == _M_rightmost())
01423         return _M_insert_(0, _M_rightmost(),
01424                   _GLIBCXX_FORWARD(_Arg, __v));
01425       else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
01426                        _KeyOfValue()(__v)))
01427         {
01428           if (_S_right(__position._M_node) == 0)
01429         return _M_insert_(0, __position._M_node,
01430                   _GLIBCXX_FORWARD(_Arg, __v));
01431           else
01432         return _M_insert_(__after._M_node, __after._M_node,
01433                   _GLIBCXX_FORWARD(_Arg, __v));
01434         }
01435       else
01436         return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
01437     }
01438     }
01439 
01440   template<typename _Key, typename _Val, typename _KoV,
01441            typename _Cmp, typename _Alloc>
01442     template<class _II>
01443       void
01444       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01445       _M_insert_unique(_II __first, _II __last)
01446       {
01447     for (; __first != __last; ++__first)
01448       _M_insert_unique_(end(), *__first);
01449       }
01450 
01451   template<typename _Key, typename _Val, typename _KoV,
01452            typename _Cmp, typename _Alloc>
01453     template<class _II>
01454       void
01455       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01456       _M_insert_equal(_II __first, _II __last)
01457       {
01458     for (; __first != __last; ++__first)
01459       _M_insert_equal_(end(), *__first);
01460       }
01461 
01462   template<typename _Key, typename _Val, typename _KeyOfValue,
01463            typename _Compare, typename _Alloc>
01464     void
01465     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01466     _M_erase_aux(const_iterator __position)
01467     {
01468       _Link_type __y =
01469     static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01470                 (const_cast<_Base_ptr>(__position._M_node),
01471                  this->_M_impl._M_header));
01472       _M_destroy_node(__y);
01473       --_M_impl._M_node_count;
01474     }
01475 
01476   template<typename _Key, typename _Val, typename _KeyOfValue,
01477            typename _Compare, typename _Alloc>
01478     void
01479     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01480     _M_erase_aux(const_iterator __first, const_iterator __last)
01481     {
01482       if (__first == begin() && __last == end())
01483     clear();
01484       else
01485     while (__first != __last)
01486       erase(__first++);
01487     }
01488 
01489   template<typename _Key, typename _Val, typename _KeyOfValue,
01490            typename _Compare, typename _Alloc>
01491     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01492     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01493     erase(const _Key& __x)
01494     {
01495       pair<iterator, iterator> __p = equal_range(__x);
01496       const size_type __old_size = size();
01497       erase(__p.first, __p.second);
01498       return __old_size - size();
01499     }
01500 
01501   template<typename _Key, typename _Val, typename _KeyOfValue,
01502            typename _Compare, typename _Alloc>
01503     void
01504     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01505     erase(const _Key* __first, const _Key* __last)
01506     {
01507       while (__first != __last)
01508     erase(*__first++);
01509     }
01510 
01511   template<typename _Key, typename _Val, typename _KeyOfValue,
01512            typename _Compare, typename _Alloc>
01513     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01514               _Compare, _Alloc>::iterator
01515     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01516     find(const _Key& __k)
01517     {
01518       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01519       return (__j == end()
01520           || _M_impl._M_key_compare(__k,
01521                     _S_key(__j._M_node))) ? end() : __j;
01522     }
01523 
01524   template<typename _Key, typename _Val, typename _KeyOfValue,
01525            typename _Compare, typename _Alloc>
01526     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01527               _Compare, _Alloc>::const_iterator
01528     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01529     find(const _Key& __k) const
01530     {
01531       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01532       return (__j == end()
01533           || _M_impl._M_key_compare(__k, 
01534                     _S_key(__j._M_node))) ? end() : __j;
01535     }
01536 
01537   template<typename _Key, typename _Val, typename _KeyOfValue,
01538            typename _Compare, typename _Alloc>
01539     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01540     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01541     count(const _Key& __k) const
01542     {
01543       pair<const_iterator, const_iterator> __p = equal_range(__k);
01544       const size_type __n = std::distance(__p.first, __p.second);
01545       return __n;
01546     }
01547 
01548   _GLIBCXX_PURE unsigned int
01549   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01550                        const _Rb_tree_node_base* __root) throw ();
01551 
01552   template<typename _Key, typename _Val, typename _KeyOfValue,
01553            typename _Compare, typename _Alloc>
01554     bool
01555     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01556     {
01557       if (_M_impl._M_node_count == 0 || begin() == end())
01558     return _M_impl._M_node_count == 0 && begin() == end()
01559            && this->_M_impl._M_header._M_left == _M_end()
01560            && this->_M_impl._M_header._M_right == _M_end();
01561 
01562       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01563       for (const_iterator __it = begin(); __it != end(); ++__it)
01564     {
01565       _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01566       _Const_Link_type __L = _S_left(__x);
01567       _Const_Link_type __R = _S_right(__x);
01568 
01569       if (__x->_M_color == _S_red)
01570         if ((__L && __L->_M_color == _S_red)
01571         || (__R && __R->_M_color == _S_red))
01572           return false;
01573 
01574       if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01575         return false;
01576       if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01577         return false;
01578 
01579       if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01580         return false;
01581     }
01582 
01583       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01584     return false;
01585       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01586     return false;
01587       return true;
01588     }
01589 
01590 _GLIBCXX_END_NAMESPACE_VERSION
01591 } // namespace
01592 
01593 #endif