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