libstdc++
stl_tree.h
Go to the documentation of this file.
00001 // RB tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 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 #pragma GCC system_header
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 #include <ext/alloc_traits.h>
00068 #if __cplusplus >= 201103L
00069 #include <ext/aligned_buffer.h>
00070 #endif
00071 
00072 namespace std _GLIBCXX_VISIBILITY(default)
00073 {
00074 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00075 
00076 #if __cplusplus > 201103L
00077 # define __cpp_lib_generic_associative_lookup 201304
00078 #endif
00079 
00080   // Red-black tree class, designed for use in implementing STL
00081   // associative containers (set, multiset, map, and multimap). The
00082   // insertion and deletion algorithms are based on those in Cormen,
00083   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
00084   // 1990), except that
00085   //
00086   // (1) the header cell is maintained with links not only to the root
00087   // but also to the leftmost node of the tree, to enable constant
00088   // time begin(), and to the rightmost node of the tree, to enable
00089   // linear time performance when used with the generic set algorithms
00090   // (set_union, etc.)
00091   // 
00092   // (2) when a node being deleted has two children its successor node
00093   // is relinked into its place, rather than copied, so that the only
00094   // iterators invalidated are those referring to the deleted node.
00095 
00096   enum _Rb_tree_color { _S_red = false, _S_black = true };
00097 
00098   struct _Rb_tree_node_base
00099   {
00100     typedef _Rb_tree_node_base* _Base_ptr;
00101     typedef const _Rb_tree_node_base* _Const_Base_ptr;
00102 
00103     _Rb_tree_color      _M_color;
00104     _Base_ptr           _M_parent;
00105     _Base_ptr           _M_left;
00106     _Base_ptr           _M_right;
00107 
00108     static _Base_ptr
00109     _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00110     {
00111       while (__x->_M_left != 0) __x = __x->_M_left;
00112       return __x;
00113     }
00114 
00115     static _Const_Base_ptr
00116     _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00117     {
00118       while (__x->_M_left != 0) __x = __x->_M_left;
00119       return __x;
00120     }
00121 
00122     static _Base_ptr
00123     _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00124     {
00125       while (__x->_M_right != 0) __x = __x->_M_right;
00126       return __x;
00127     }
00128 
00129     static _Const_Base_ptr
00130     _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00131     {
00132       while (__x->_M_right != 0) __x = __x->_M_right;
00133       return __x;
00134     }
00135   };
00136 
00137   template<typename _Val>
00138     struct _Rb_tree_node : public _Rb_tree_node_base
00139     {
00140       typedef _Rb_tree_node<_Val>* _Link_type;
00141 
00142 #if __cplusplus < 201103L
00143       _Val _M_value_field;
00144 
00145       _Val*
00146       _M_valptr()
00147       { return std::__addressof(_M_value_field); }
00148 
00149       const _Val*
00150       _M_valptr() const
00151       { return std::__addressof(_M_value_field); }
00152 #else
00153       __gnu_cxx::__aligned_membuf<_Val> _M_storage;
00154 
00155       _Val*
00156       _M_valptr()
00157       { return _M_storage._M_ptr(); }
00158 
00159       const _Val*
00160       _M_valptr() const
00161       { return _M_storage._M_ptr(); }
00162 #endif
00163     };
00164 
00165   _GLIBCXX_PURE _Rb_tree_node_base*
00166   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
00167 
00168   _GLIBCXX_PURE const _Rb_tree_node_base*
00169   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
00170 
00171   _GLIBCXX_PURE _Rb_tree_node_base*
00172   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
00173 
00174   _GLIBCXX_PURE const _Rb_tree_node_base*
00175   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
00176 
00177   template<typename _Tp>
00178     struct _Rb_tree_iterator
00179     {
00180       typedef _Tp  value_type;
00181       typedef _Tp& reference;
00182       typedef _Tp* pointer;
00183 
00184       typedef bidirectional_iterator_tag iterator_category;
00185       typedef ptrdiff_t                  difference_type;
00186 
00187       typedef _Rb_tree_iterator<_Tp>        _Self;
00188       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00189       typedef _Rb_tree_node<_Tp>*           _Link_type;
00190 
00191       _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
00192       : _M_node() { }
00193 
00194       explicit
00195       _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00196       : _M_node(__x) { }
00197 
00198       reference
00199       operator*() const _GLIBCXX_NOEXCEPT
00200       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
00201 
00202       pointer
00203       operator->() const _GLIBCXX_NOEXCEPT
00204       { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
00205 
00206       _Self&
00207       operator++() _GLIBCXX_NOEXCEPT
00208       {
00209         _M_node = _Rb_tree_increment(_M_node);
00210         return *this;
00211       }
00212 
00213       _Self
00214       operator++(int) _GLIBCXX_NOEXCEPT
00215       {
00216         _Self __tmp = *this;
00217         _M_node = _Rb_tree_increment(_M_node);
00218         return __tmp;
00219       }
00220 
00221       _Self&
00222       operator--() _GLIBCXX_NOEXCEPT
00223       {
00224         _M_node = _Rb_tree_decrement(_M_node);
00225         return *this;
00226       }
00227 
00228       _Self
00229       operator--(int) _GLIBCXX_NOEXCEPT
00230       {
00231         _Self __tmp = *this;
00232         _M_node = _Rb_tree_decrement(_M_node);
00233         return __tmp;
00234       }
00235 
00236       bool
00237       operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
00238       { return _M_node == __x._M_node; }
00239 
00240       bool
00241       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
00242       { return _M_node != __x._M_node; }
00243 
00244       _Base_ptr _M_node;
00245   };
00246 
00247   template<typename _Tp>
00248     struct _Rb_tree_const_iterator
00249     {
00250       typedef _Tp        value_type;
00251       typedef const _Tp& reference;
00252       typedef const _Tp* pointer;
00253 
00254       typedef _Rb_tree_iterator<_Tp> iterator;
00255 
00256       typedef bidirectional_iterator_tag iterator_category;
00257       typedef ptrdiff_t                  difference_type;
00258 
00259       typedef _Rb_tree_const_iterator<_Tp>        _Self;
00260       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00261       typedef const _Rb_tree_node<_Tp>*           _Link_type;
00262 
00263       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
00264       : _M_node() { }
00265 
00266       explicit
00267       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00268       : _M_node(__x) { }
00269 
00270       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
00271       : _M_node(__it._M_node) { }
00272 
00273       iterator
00274       _M_const_cast() const _GLIBCXX_NOEXCEPT
00275       { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
00276 
00277       reference
00278       operator*() const _GLIBCXX_NOEXCEPT
00279       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
00280 
00281       pointer
00282       operator->() const _GLIBCXX_NOEXCEPT
00283       { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
00284 
00285       _Self&
00286       operator++() _GLIBCXX_NOEXCEPT
00287       {
00288         _M_node = _Rb_tree_increment(_M_node);
00289         return *this;
00290       }
00291 
00292       _Self
00293       operator++(int) _GLIBCXX_NOEXCEPT
00294       {
00295         _Self __tmp = *this;
00296         _M_node = _Rb_tree_increment(_M_node);
00297         return __tmp;
00298       }
00299 
00300       _Self&
00301       operator--() _GLIBCXX_NOEXCEPT
00302       {
00303         _M_node = _Rb_tree_decrement(_M_node);
00304         return *this;
00305       }
00306 
00307       _Self
00308       operator--(int) _GLIBCXX_NOEXCEPT
00309       {
00310         _Self __tmp = *this;
00311         _M_node = _Rb_tree_decrement(_M_node);
00312         return __tmp;
00313       }
00314 
00315       bool
00316       operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
00317       { return _M_node == __x._M_node; }
00318 
00319       bool
00320       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
00321       { return _M_node != __x._M_node; }
00322 
00323       _Base_ptr _M_node;
00324     };
00325 
00326   template<typename _Val>
00327     inline bool
00328     operator==(const _Rb_tree_iterator<_Val>& __x,
00329                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
00330     { return __x._M_node == __y._M_node; }
00331 
00332   template<typename _Val>
00333     inline bool
00334     operator!=(const _Rb_tree_iterator<_Val>& __x,
00335                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
00336     { return __x._M_node != __y._M_node; }
00337 
00338   void
00339   _Rb_tree_insert_and_rebalance(const bool __insert_left,
00340                                 _Rb_tree_node_base* __x,
00341                                 _Rb_tree_node_base* __p,
00342                                 _Rb_tree_node_base& __header) throw ();
00343 
00344   _Rb_tree_node_base*
00345   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00346                                _Rb_tree_node_base& __header) throw ();
00347 
00348 #if __cplusplus > 201103L
00349   template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
00350     struct __has_is_transparent
00351     { };
00352 
00353   template<typename _Cmp, typename _SfinaeType>
00354     struct __has_is_transparent<_Cmp, _SfinaeType,
00355                                 __void_t<typename _Cmp::is_transparent>>
00356     { typedef void type; };
00357 #endif
00358 
00359   template<typename _Key, typename _Val, typename _KeyOfValue,
00360            typename _Compare, typename _Alloc = allocator<_Val> >
00361     class _Rb_tree
00362     {
00363       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
00364         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
00365 
00366       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
00367 
00368     protected:
00369       typedef _Rb_tree_node_base*               _Base_ptr;
00370       typedef const _Rb_tree_node_base*         _Const_Base_ptr;
00371       typedef _Rb_tree_node<_Val>*              _Link_type;
00372       typedef const _Rb_tree_node<_Val>*        _Const_Link_type;
00373 
00374     private:
00375       // Functor recycling a pool of nodes and using allocation once the pool
00376       // is empty.
00377       struct _Reuse_or_alloc_node
00378       {
00379         _Reuse_or_alloc_node(_Rb_tree& __t)
00380           : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
00381         {
00382           if (_M_root)
00383             {
00384               _M_root->_M_parent = 0;
00385 
00386               if (_M_nodes->_M_left)
00387                 _M_nodes = _M_nodes->_M_left;
00388             }
00389           else
00390             _M_nodes = 0;
00391         }
00392 
00393 #if __cplusplus >= 201103L
00394         _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
00395 #endif
00396 
00397         ~_Reuse_or_alloc_node()
00398         { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
00399 
00400         template<typename _Arg>
00401           _Link_type
00402 #if __cplusplus < 201103L
00403           operator()(const _Arg& __arg)
00404 #else
00405           operator()(_Arg&& __arg)
00406 #endif
00407           {
00408             _Link_type __node = static_cast<_Link_type>(_M_extract());
00409             if (__node)
00410               {
00411                 _M_t._M_destroy_node(__node);
00412                 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
00413                 return __node;
00414               }
00415 
00416             return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
00417           }
00418 
00419       private:
00420         _Base_ptr
00421         _M_extract()
00422         {
00423           if (!_M_nodes)
00424             return _M_nodes;
00425 
00426           _Base_ptr __node = _M_nodes;
00427           _M_nodes = _M_nodes->_M_parent;
00428           if (_M_nodes)
00429             {
00430               if (_M_nodes->_M_right == __node)
00431                 {
00432                   _M_nodes->_M_right = 0;
00433 
00434                   if (_M_nodes->_M_left)
00435                     {
00436                       _M_nodes = _M_nodes->_M_left;
00437 
00438                       while (_M_nodes->_M_right)
00439                         _M_nodes = _M_nodes->_M_right;
00440 
00441                       if (_M_nodes->_M_left)
00442                         _M_nodes = _M_nodes->_M_left;
00443                     }
00444                 }
00445               else // __node is on the left.
00446                 _M_nodes->_M_left = 0;
00447             }
00448           else
00449             _M_root = 0;
00450 
00451           return __node;
00452         }
00453 
00454         _Base_ptr _M_root;
00455         _Base_ptr _M_nodes;
00456         _Rb_tree& _M_t;
00457       };
00458 
00459       // Functor similar to the previous one but without any pool of nodes to
00460       // recycle.
00461       struct _Alloc_node
00462       {
00463         _Alloc_node(_Rb_tree& __t)
00464           : _M_t(__t) { }
00465 
00466         template<typename _Arg>
00467           _Link_type
00468 #if __cplusplus < 201103L
00469           operator()(const _Arg& __arg) const
00470 #else
00471           operator()(_Arg&& __arg) const
00472 #endif
00473           { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
00474 
00475       private:
00476         _Rb_tree& _M_t;
00477       };
00478 
00479     public:
00480       typedef _Key                              key_type;
00481       typedef _Val                              value_type;
00482       typedef value_type*                       pointer;
00483       typedef const value_type*                 const_pointer;
00484       typedef value_type&                       reference;
00485       typedef const value_type&                 const_reference;
00486       typedef size_t                            size_type;
00487       typedef ptrdiff_t                         difference_type;
00488       typedef _Alloc                            allocator_type;
00489 
00490       _Node_allocator&
00491       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
00492       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
00493       
00494       const _Node_allocator&
00495       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
00496       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00497 
00498       allocator_type
00499       get_allocator() const _GLIBCXX_NOEXCEPT
00500       { return allocator_type(_M_get_Node_allocator()); }
00501 
00502     protected:
00503       _Link_type
00504       _M_get_node()
00505       { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
00506 
00507       void
00508       _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
00509       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
00510 
00511 #if __cplusplus < 201103L
00512       void
00513       _M_construct_node(_Link_type __node, const value_type& __x)
00514       {
00515         __try
00516           { get_allocator().construct(__node->_M_valptr(), __x); }
00517         __catch(...)
00518           {
00519             _M_put_node(__node);
00520             __throw_exception_again;
00521           }
00522       }
00523 
00524       _Link_type
00525       _M_create_node(const value_type& __x)
00526       {
00527         _Link_type __tmp = _M_get_node();
00528         _M_construct_node(__tmp, __x);
00529         return __tmp;
00530       }
00531 
00532       void
00533       _M_destroy_node(_Link_type __p)
00534       { get_allocator().destroy(__p->_M_valptr()); }
00535 #else
00536       template<typename... _Args>
00537         void
00538         _M_construct_node(_Link_type __node, _Args&&... __args)
00539         {
00540           __try
00541             {
00542               ::new(__node) _Rb_tree_node<_Val>;
00543               _Alloc_traits::construct(_M_get_Node_allocator(),
00544                                        __node->_M_valptr(),
00545                                        std::forward<_Args>(__args)...);
00546             }
00547           __catch(...)
00548             {
00549               __node->~_Rb_tree_node<_Val>();
00550               _M_put_node(__node);
00551               __throw_exception_again;
00552             }
00553         }
00554 
00555       template<typename... _Args>
00556         _Link_type
00557         _M_create_node(_Args&&... __args)
00558         {
00559           _Link_type __tmp = _M_get_node();
00560           _M_construct_node(__tmp, std::forward<_Args>(__args)...);
00561           return __tmp;
00562         }
00563 
00564       void
00565       _M_destroy_node(_Link_type __p) noexcept
00566       {
00567         _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
00568         __p->~_Rb_tree_node<_Val>();
00569       }
00570 #endif
00571 
00572       void
00573       _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
00574       {
00575         _M_destroy_node(__p);
00576         _M_put_node(__p);
00577       }
00578 
00579       template<typename _NodeGen>
00580         _Link_type
00581         _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
00582         {
00583           _Link_type __tmp = __node_gen(*__x->_M_valptr());
00584           __tmp->_M_color = __x->_M_color;
00585           __tmp->_M_left = 0;
00586           __tmp->_M_right = 0;
00587           return __tmp;
00588         }
00589 
00590     protected:
00591       // Unused _Is_pod_comparator is kept as it is part of mangled name.
00592       template<typename _Key_compare,
00593                bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
00594         struct _Rb_tree_impl : public _Node_allocator
00595         {
00596           _Key_compare          _M_key_compare;
00597           _Rb_tree_node_base    _M_header;
00598           size_type             _M_node_count; // Keeps track of size of tree.
00599 
00600           _Rb_tree_impl()
00601           : _Node_allocator(), _M_key_compare(), _M_header(),
00602             _M_node_count(0)
00603           { _M_initialize(); }
00604 
00605           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
00606           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
00607             _M_node_count(0)
00608           { _M_initialize(); }
00609 
00610 #if __cplusplus >= 201103L
00611           _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
00612           : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
00613             _M_header(), _M_node_count(0)
00614           { _M_initialize(); }
00615 #endif
00616 
00617           void
00618           _M_reset()
00619           {
00620             this->_M_header._M_parent = 0;
00621             this->_M_header._M_left = &this->_M_header;
00622             this->_M_header._M_right = &this->_M_header;
00623             this->_M_node_count = 0;
00624           }
00625 
00626         private:
00627           void
00628           _M_initialize()
00629           {
00630             this->_M_header._M_color = _S_red;
00631             this->_M_header._M_parent = 0;
00632             this->_M_header._M_left = &this->_M_header;
00633             this->_M_header._M_right = &this->_M_header;
00634           }         
00635         };
00636 
00637       _Rb_tree_impl<_Compare> _M_impl;
00638 
00639     protected:
00640       _Base_ptr&
00641       _M_root() _GLIBCXX_NOEXCEPT
00642       { return this->_M_impl._M_header._M_parent; }
00643 
00644       _Const_Base_ptr
00645       _M_root() const _GLIBCXX_NOEXCEPT
00646       { return this->_M_impl._M_header._M_parent; }
00647 
00648       _Base_ptr&
00649       _M_leftmost() _GLIBCXX_NOEXCEPT
00650       { return this->_M_impl._M_header._M_left; }
00651 
00652       _Const_Base_ptr
00653       _M_leftmost() const _GLIBCXX_NOEXCEPT
00654       { return this->_M_impl._M_header._M_left; }
00655 
00656       _Base_ptr&
00657       _M_rightmost() _GLIBCXX_NOEXCEPT
00658       { return this->_M_impl._M_header._M_right; }
00659 
00660       _Const_Base_ptr
00661       _M_rightmost() const _GLIBCXX_NOEXCEPT
00662       { return this->_M_impl._M_header._M_right; }
00663 
00664       _Link_type
00665       _M_begin() _GLIBCXX_NOEXCEPT
00666       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00667 
00668       _Const_Link_type
00669       _M_begin() const _GLIBCXX_NOEXCEPT
00670       {
00671         return static_cast<_Const_Link_type>
00672           (this->_M_impl._M_header._M_parent);
00673       }
00674 
00675       _Base_ptr
00676       _M_end() _GLIBCXX_NOEXCEPT
00677       { return &this->_M_impl._M_header; }
00678 
00679       _Const_Base_ptr
00680       _M_end() const _GLIBCXX_NOEXCEPT
00681       { return &this->_M_impl._M_header; }
00682 
00683       static const_reference
00684       _S_value(_Const_Link_type __x)
00685       { return *__x->_M_valptr(); }
00686 
00687       static const _Key&
00688       _S_key(_Const_Link_type __x)
00689       { return _KeyOfValue()(_S_value(__x)); }
00690 
00691       static _Link_type
00692       _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00693       { return static_cast<_Link_type>(__x->_M_left); }
00694 
00695       static _Const_Link_type
00696       _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00697       { return static_cast<_Const_Link_type>(__x->_M_left); }
00698 
00699       static _Link_type
00700       _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00701       { return static_cast<_Link_type>(__x->_M_right); }
00702 
00703       static _Const_Link_type
00704       _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00705       { return static_cast<_Const_Link_type>(__x->_M_right); }
00706 
00707       static const_reference
00708       _S_value(_Const_Base_ptr __x)
00709       { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
00710 
00711       static const _Key&
00712       _S_key(_Const_Base_ptr __x)
00713       { return _KeyOfValue()(_S_value(__x)); }
00714 
00715       static _Base_ptr
00716       _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00717       { return _Rb_tree_node_base::_S_minimum(__x); }
00718 
00719       static _Const_Base_ptr
00720       _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00721       { return _Rb_tree_node_base::_S_minimum(__x); }
00722 
00723       static _Base_ptr
00724       _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00725       { return _Rb_tree_node_base::_S_maximum(__x); }
00726 
00727       static _Const_Base_ptr
00728       _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00729       { return _Rb_tree_node_base::_S_maximum(__x); }
00730 
00731     public:
00732       typedef _Rb_tree_iterator<value_type>       iterator;
00733       typedef _Rb_tree_const_iterator<value_type> const_iterator;
00734 
00735       typedef std::reverse_iterator<iterator>       reverse_iterator;
00736       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00737 
00738       pair<_Base_ptr, _Base_ptr>
00739       _M_get_insert_unique_pos(const key_type& __k);
00740 
00741       pair<_Base_ptr, _Base_ptr>
00742       _M_get_insert_equal_pos(const key_type& __k);
00743 
00744       pair<_Base_ptr, _Base_ptr>
00745       _M_get_insert_hint_unique_pos(const_iterator __pos,
00746                                     const key_type& __k);
00747 
00748       pair<_Base_ptr, _Base_ptr>
00749       _M_get_insert_hint_equal_pos(const_iterator __pos,
00750                                    const key_type& __k);
00751 
00752     private:
00753 #if __cplusplus >= 201103L
00754       template<typename _Arg, typename _NodeGen>
00755         iterator
00756         _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
00757 
00758       iterator
00759       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
00760 
00761       template<typename _Arg>
00762         iterator
00763         _M_insert_lower(_Base_ptr __y, _Arg&& __v);
00764 
00765       template<typename _Arg>
00766         iterator
00767         _M_insert_equal_lower(_Arg&& __x);
00768 
00769       iterator
00770       _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
00771 
00772       iterator
00773       _M_insert_equal_lower_node(_Link_type __z);
00774 #else
00775       template<typename _NodeGen>
00776         iterator
00777         _M_insert_(_Base_ptr __x, _Base_ptr __y,
00778                    const value_type& __v, _NodeGen&);
00779 
00780       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00781       // 233. Insertion hints in associative containers.
00782       iterator
00783       _M_insert_lower(_Base_ptr __y, const value_type& __v);
00784 
00785       iterator
00786       _M_insert_equal_lower(const value_type& __x);
00787 #endif
00788 
00789       template<typename _NodeGen>
00790         _Link_type
00791         _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
00792 
00793       _Link_type
00794       _M_copy(_Const_Link_type __x, _Base_ptr __p)
00795       {
00796         _Alloc_node __an(*this);
00797         return _M_copy(__x, __p, __an);
00798       }
00799 
00800       void
00801       _M_erase(_Link_type __x);
00802 
00803       iterator
00804       _M_lower_bound(_Link_type __x, _Base_ptr __y,
00805                      const _Key& __k);
00806 
00807       const_iterator
00808       _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
00809                      const _Key& __k) const;
00810 
00811       iterator
00812       _M_upper_bound(_Link_type __x, _Base_ptr __y,
00813                      const _Key& __k);
00814 
00815       const_iterator
00816       _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
00817                      const _Key& __k) const;
00818 
00819     public:
00820       // allocation/deallocation
00821       _Rb_tree() { }
00822 
00823       _Rb_tree(const _Compare& __comp,
00824                const allocator_type& __a = allocator_type())
00825       : _M_impl(__comp, _Node_allocator(__a)) { }
00826 
00827       _Rb_tree(const _Rb_tree& __x)
00828       : _M_impl(__x._M_impl._M_key_compare,
00829                 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
00830       {
00831         if (__x._M_root() != 0)
00832           {
00833             _M_root() = _M_copy(__x._M_begin(), _M_end());
00834             _M_leftmost() = _S_minimum(_M_root());
00835             _M_rightmost() = _S_maximum(_M_root());
00836             _M_impl._M_node_count = __x._M_impl._M_node_count;
00837           }
00838       }
00839 
00840 #if __cplusplus >= 201103L
00841       _Rb_tree(const allocator_type& __a)
00842       : _M_impl(_Compare(), _Node_allocator(__a))
00843       { }
00844 
00845       _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
00846       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
00847       {
00848         if (__x._M_root() != nullptr)
00849           {
00850             _M_root() = _M_copy(__x._M_begin(), _M_end());
00851             _M_leftmost() = _S_minimum(_M_root());
00852             _M_rightmost() = _S_maximum(_M_root());
00853             _M_impl._M_node_count = __x._M_impl._M_node_count;
00854           }
00855       }
00856 
00857       _Rb_tree(_Rb_tree&& __x)
00858       : _M_impl(__x._M_impl._M_key_compare,
00859                 std::move(__x._M_get_Node_allocator()))
00860       {
00861         if (__x._M_root() != 0)
00862           _M_move_data(__x, std::true_type());
00863       }
00864 
00865       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
00866       : _Rb_tree(std::move(__x), _Node_allocator(__a))
00867       { }
00868 
00869       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
00870 #endif
00871 
00872       ~_Rb_tree() _GLIBCXX_NOEXCEPT
00873       { _M_erase(_M_begin()); }
00874 
00875       _Rb_tree&
00876       operator=(const _Rb_tree& __x);
00877 
00878       // Accessors.
00879       _Compare
00880       key_comp() const
00881       { return _M_impl._M_key_compare; }
00882 
00883       iterator
00884       begin() _GLIBCXX_NOEXCEPT
00885       { return iterator(this->_M_impl._M_header._M_left); }
00886 
00887       const_iterator
00888       begin() const _GLIBCXX_NOEXCEPT
00889       { return const_iterator(this->_M_impl._M_header._M_left); }
00890 
00891       iterator
00892       end() _GLIBCXX_NOEXCEPT
00893       { return iterator(&this->_M_impl._M_header); }
00894 
00895       const_iterator
00896       end() const _GLIBCXX_NOEXCEPT
00897       { return const_iterator(&this->_M_impl._M_header); }
00898 
00899       reverse_iterator
00900       rbegin() _GLIBCXX_NOEXCEPT
00901       { return reverse_iterator(end()); }
00902 
00903       const_reverse_iterator
00904       rbegin() const _GLIBCXX_NOEXCEPT
00905       { return const_reverse_iterator(end()); }
00906 
00907       reverse_iterator
00908       rend() _GLIBCXX_NOEXCEPT
00909       { return reverse_iterator(begin()); }
00910 
00911       const_reverse_iterator
00912       rend() const _GLIBCXX_NOEXCEPT
00913       { return const_reverse_iterator(begin()); }
00914 
00915       bool
00916       empty() const _GLIBCXX_NOEXCEPT
00917       { return _M_impl._M_node_count == 0; }
00918 
00919       size_type
00920       size() const _GLIBCXX_NOEXCEPT 
00921       { return _M_impl._M_node_count; }
00922 
00923       size_type
00924       max_size() const _GLIBCXX_NOEXCEPT
00925       { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
00926 
00927       void
00928       swap(_Rb_tree& __t)
00929       _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
00930 
00931       // Insert/erase.
00932 #if __cplusplus >= 201103L
00933       template<typename _Arg>
00934         pair<iterator, bool>
00935         _M_insert_unique(_Arg&& __x);
00936 
00937       template<typename _Arg>
00938         iterator
00939         _M_insert_equal(_Arg&& __x);
00940 
00941       template<typename _Arg, typename _NodeGen>
00942         iterator
00943         _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
00944 
00945       template<typename _Arg>
00946         iterator
00947         _M_insert_unique_(const_iterator __pos, _Arg&& __x)
00948         {
00949           _Alloc_node __an(*this);
00950           return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
00951         }
00952 
00953       template<typename _Arg, typename _NodeGen>
00954         iterator
00955         _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
00956 
00957       template<typename _Arg>
00958         iterator
00959         _M_insert_equal_(const_iterator __pos, _Arg&& __x)
00960         {
00961           _Alloc_node __an(*this);
00962           return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
00963         }
00964 
00965       template<typename... _Args>
00966         pair<iterator, bool>
00967         _M_emplace_unique(_Args&&... __args);
00968 
00969       template<typename... _Args>
00970         iterator
00971         _M_emplace_equal(_Args&&... __args);
00972 
00973       template<typename... _Args>
00974         iterator
00975         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
00976 
00977       template<typename... _Args>
00978         iterator
00979         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
00980 #else
00981       pair<iterator, bool>
00982       _M_insert_unique(const value_type& __x);
00983 
00984       iterator
00985       _M_insert_equal(const value_type& __x);
00986 
00987       template<typename _NodeGen>
00988         iterator
00989         _M_insert_unique_(const_iterator __pos, const value_type& __x,
00990                           _NodeGen&);
00991 
00992       iterator
00993       _M_insert_unique_(const_iterator __pos, const value_type& __x)
00994       {
00995         _Alloc_node __an(*this);
00996         return _M_insert_unique_(__pos, __x, __an);
00997       }
00998 
00999       template<typename _NodeGen>
01000         iterator
01001         _M_insert_equal_(const_iterator __pos, const value_type& __x,
01002                          _NodeGen&);
01003       iterator
01004       _M_insert_equal_(const_iterator __pos, const value_type& __x)
01005       {
01006         _Alloc_node __an(*this);
01007         return _M_insert_equal_(__pos, __x, __an);
01008       }
01009 #endif
01010 
01011       template<typename _InputIterator>
01012         void
01013         _M_insert_unique(_InputIterator __first, _InputIterator __last);
01014 
01015       template<typename _InputIterator>
01016         void
01017         _M_insert_equal(_InputIterator __first, _InputIterator __last);
01018 
01019     private:
01020       void
01021       _M_erase_aux(const_iterator __position);
01022 
01023       void
01024       _M_erase_aux(const_iterator __first, const_iterator __last);
01025 
01026     public:
01027 #if __cplusplus >= 201103L
01028       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01029       // DR 130. Associative erase should return an iterator.
01030       _GLIBCXX_ABI_TAG_CXX11
01031       iterator
01032       erase(const_iterator __position)
01033       {
01034         const_iterator __result = __position;
01035         ++__result;
01036         _M_erase_aux(__position);
01037         return __result._M_const_cast();
01038       }
01039 
01040       // LWG 2059.
01041       _GLIBCXX_ABI_TAG_CXX11
01042       iterator
01043       erase(iterator __position)
01044       {
01045         iterator __result = __position;
01046         ++__result;
01047         _M_erase_aux(__position);
01048         return __result;
01049       }
01050 #else
01051       void
01052       erase(iterator __position)
01053       { _M_erase_aux(__position); }
01054 
01055       void
01056       erase(const_iterator __position)
01057       { _M_erase_aux(__position); }
01058 #endif
01059       size_type
01060       erase(const key_type& __x);
01061 
01062 #if __cplusplus >= 201103L
01063       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01064       // DR 130. Associative erase should return an iterator.
01065       _GLIBCXX_ABI_TAG_CXX11
01066       iterator
01067       erase(const_iterator __first, const_iterator __last)
01068       {
01069         _M_erase_aux(__first, __last);
01070         return __last._M_const_cast();
01071       }
01072 #else
01073       void
01074       erase(iterator __first, iterator __last)
01075       { _M_erase_aux(__first, __last); }
01076 
01077       void
01078       erase(const_iterator __first, const_iterator __last)
01079       { _M_erase_aux(__first, __last); }
01080 #endif
01081       void
01082       erase(const key_type* __first, const key_type* __last);
01083 
01084       void
01085       clear() _GLIBCXX_NOEXCEPT
01086       {
01087         _M_erase(_M_begin());
01088         _M_impl._M_reset();
01089       }
01090 
01091       // Set operations.
01092       iterator
01093       find(const key_type& __k);
01094 
01095       const_iterator
01096       find(const key_type& __k) const;
01097 
01098       size_type
01099       count(const key_type& __k) const;
01100 
01101       iterator
01102       lower_bound(const key_type& __k)
01103       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
01104 
01105       const_iterator
01106       lower_bound(const key_type& __k) const
01107       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
01108 
01109       iterator
01110       upper_bound(const key_type& __k)
01111       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
01112 
01113       const_iterator
01114       upper_bound(const key_type& __k) const
01115       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
01116 
01117       pair<iterator, iterator>
01118       equal_range(const key_type& __k);
01119 
01120       pair<const_iterator, const_iterator>
01121       equal_range(const key_type& __k) const;
01122 
01123 #if __cplusplus > 201103L
01124       template<typename _Kt,
01125                typename _Req =
01126                  typename __has_is_transparent<_Compare, _Kt>::type>
01127         iterator
01128         _M_find_tr(const _Kt& __k)
01129         {
01130           const _Rb_tree* __const_this = this;
01131           return __const_this->_M_find_tr(__k)._M_const_cast();
01132         }
01133 
01134       template<typename _Kt,
01135                typename _Req =
01136                  typename __has_is_transparent<_Compare, _Kt>::type>
01137         const_iterator
01138         _M_find_tr(const _Kt& __k) const
01139         {
01140           auto __j = _M_lower_bound_tr(__k);
01141           if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
01142             __j = end();
01143           return __j;
01144         }
01145 
01146       template<typename _Kt,
01147                typename _Req =
01148                  typename __has_is_transparent<_Compare, _Kt>::type>
01149         size_type
01150         _M_count_tr(const _Kt& __k) const
01151         {
01152           auto __p = _M_equal_range_tr(__k);
01153           return std::distance(__p.first, __p.second);
01154         }
01155 
01156       template<typename _Kt,
01157                typename _Req =
01158                  typename __has_is_transparent<_Compare, _Kt>::type>
01159         iterator
01160         _M_lower_bound_tr(const _Kt& __k)
01161         {
01162           const _Rb_tree* __const_this = this;
01163           return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
01164         }
01165 
01166       template<typename _Kt,
01167                typename _Req =
01168                  typename __has_is_transparent<_Compare, _Kt>::type>
01169         const_iterator
01170         _M_lower_bound_tr(const _Kt& __k) const
01171         {
01172           auto __x = _M_begin();
01173           auto __y = _M_end();
01174           while (__x != 0)
01175             if (!_M_impl._M_key_compare(_S_key(__x), __k))
01176               {
01177                 __y = __x;
01178                 __x = _S_left(__x);
01179               }
01180             else
01181               __x = _S_right(__x);
01182           return const_iterator(__y);
01183         }
01184 
01185       template<typename _Kt,
01186                typename _Req =
01187                  typename __has_is_transparent<_Compare, _Kt>::type>
01188         iterator
01189         _M_upper_bound_tr(const _Kt& __k)
01190         {
01191           const _Rb_tree* __const_this = this;
01192           return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
01193         }
01194 
01195       template<typename _Kt,
01196                typename _Req =
01197                  typename __has_is_transparent<_Compare, _Kt>::type>
01198         const_iterator
01199         _M_upper_bound_tr(const _Kt& __k) const
01200         {
01201           auto __x = _M_begin();
01202           auto __y = _M_end();
01203           while (__x != 0)
01204             if (_M_impl._M_key_compare(__k, _S_key(__x)))
01205               {
01206                 __y = __x;
01207                 __x = _S_left(__x);
01208               }
01209             else
01210               __x = _S_right(__x);
01211           return const_iterator(__y);
01212         }
01213 
01214       template<typename _Kt,
01215                typename _Req =
01216                  typename __has_is_transparent<_Compare, _Kt>::type>
01217         pair<iterator, iterator>
01218         _M_equal_range_tr(const _Kt& __k)
01219         {
01220           const _Rb_tree* __const_this = this;
01221           auto __ret = __const_this->_M_equal_range_tr(__k);
01222           return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
01223         }
01224 
01225       template<typename _Kt,
01226                typename _Req =
01227                  typename __has_is_transparent<_Compare, _Kt>::type>
01228         pair<const_iterator, const_iterator>
01229         _M_equal_range_tr(const _Kt& __k) const
01230         {
01231           auto __low = _M_lower_bound_tr(__k);
01232           auto __high = __low;
01233           auto& __cmp = _M_impl._M_key_compare;
01234           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
01235             ++__high;
01236           return { __low, __high };
01237         }
01238 #endif
01239 
01240       // Debugging.
01241       bool
01242       __rb_verify() const;
01243 
01244 #if __cplusplus >= 201103L
01245       _Rb_tree&
01246       operator=(_Rb_tree&&)
01247       noexcept(_Alloc_traits::_S_nothrow_move()
01248                && is_nothrow_move_assignable<_Compare>::value);
01249 
01250       template<typename _Iterator>
01251         void
01252         _M_assign_unique(_Iterator, _Iterator);
01253 
01254       template<typename _Iterator>
01255         void
01256         _M_assign_equal(_Iterator, _Iterator);
01257 
01258     private:
01259       // Move elements from container with equal allocator.
01260       void
01261       _M_move_data(_Rb_tree&, std::true_type);
01262 
01263       // Move elements from container with possibly non-equal allocator,
01264       // which might result in a copy not a move.
01265       void
01266       _M_move_data(_Rb_tree&, std::false_type);
01267 #endif
01268     };
01269 
01270   template<typename _Key, typename _Val, typename _KeyOfValue,
01271            typename _Compare, typename _Alloc>
01272     inline bool
01273     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01274                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01275     {
01276       return __x.size() == __y.size()
01277              && std::equal(__x.begin(), __x.end(), __y.begin());
01278     }
01279 
01280   template<typename _Key, typename _Val, typename _KeyOfValue,
01281            typename _Compare, typename _Alloc>
01282     inline bool
01283     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01284               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01285     {
01286       return std::lexicographical_compare(__x.begin(), __x.end(), 
01287                                           __y.begin(), __y.end());
01288     }
01289 
01290   template<typename _Key, typename _Val, typename _KeyOfValue,
01291            typename _Compare, typename _Alloc>
01292     inline bool
01293     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01294                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01295     { return !(__x == __y); }
01296 
01297   template<typename _Key, typename _Val, typename _KeyOfValue,
01298            typename _Compare, typename _Alloc>
01299     inline bool
01300     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01301               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01302     { return __y < __x; }
01303 
01304   template<typename _Key, typename _Val, typename _KeyOfValue,
01305            typename _Compare, typename _Alloc>
01306     inline bool
01307     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01308                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01309     { return !(__y < __x); }
01310 
01311   template<typename _Key, typename _Val, typename _KeyOfValue,
01312            typename _Compare, typename _Alloc>
01313     inline bool
01314     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01315                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01316     { return !(__x < __y); }
01317 
01318   template<typename _Key, typename _Val, typename _KeyOfValue,
01319            typename _Compare, typename _Alloc>
01320     inline void
01321     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01322          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01323     { __x.swap(__y); }
01324 
01325 #if __cplusplus >= 201103L
01326   template<typename _Key, typename _Val, typename _KeyOfValue,
01327            typename _Compare, typename _Alloc>
01328     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01329     _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
01330     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
01331     {
01332       using __eq = typename _Alloc_traits::is_always_equal;
01333       if (__x._M_root() != nullptr)
01334         _M_move_data(__x, __eq());
01335     }
01336 
01337   template<typename _Key, typename _Val, typename _KeyOfValue,
01338            typename _Compare, typename _Alloc>
01339     void
01340     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01341     _M_move_data(_Rb_tree& __x, std::true_type)
01342     {
01343       _M_root() = __x._M_root();
01344       _M_leftmost() = __x._M_leftmost();
01345       _M_rightmost() = __x._M_rightmost();
01346       _M_root()->_M_parent = _M_end();
01347 
01348       __x._M_root() = 0;
01349       __x._M_leftmost() = __x._M_end();
01350       __x._M_rightmost() = __x._M_end();
01351 
01352       this->_M_impl._M_node_count = __x._M_impl._M_node_count;
01353       __x._M_impl._M_node_count = 0;
01354     }
01355 
01356   template<typename _Key, typename _Val, typename _KeyOfValue,
01357            typename _Compare, typename _Alloc>
01358     void
01359     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01360     _M_move_data(_Rb_tree& __x, std::false_type)
01361     {
01362       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
01363           _M_move_data(__x, std::true_type());
01364       else
01365         {
01366           _Alloc_node __an(*this);
01367           auto __lbd =
01368             [&__an](const value_type& __cval)
01369             {
01370               auto& __val = const_cast<value_type&>(__cval);
01371               return __an(std::move_if_noexcept(__val));
01372             };
01373           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
01374           _M_leftmost() = _S_minimum(_M_root());
01375           _M_rightmost() = _S_maximum(_M_root());
01376           _M_impl._M_node_count = __x._M_impl._M_node_count;
01377         }
01378     }
01379 
01380   template<typename _Key, typename _Val, typename _KeyOfValue,
01381            typename _Compare, typename _Alloc>
01382     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
01383     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01384     operator=(_Rb_tree&& __x)
01385     noexcept(_Alloc_traits::_S_nothrow_move()
01386              && is_nothrow_move_assignable<_Compare>::value)
01387     {
01388       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
01389       if (_Alloc_traits::_S_propagate_on_move_assign()
01390           || _Alloc_traits::_S_always_equal()
01391           || _M_get_Node_allocator() == __x._M_get_Node_allocator())
01392         {
01393           clear();
01394           if (__x._M_root() != nullptr)
01395             _M_move_data(__x, std::true_type());
01396           std::__alloc_on_move(_M_get_Node_allocator(),
01397                                __x._M_get_Node_allocator());
01398           return *this;
01399         }
01400 
01401       // Try to move each node reusing existing nodes and copying __x nodes
01402       // structure.
01403       _Reuse_or_alloc_node __roan(*this);
01404       _M_impl._M_reset();
01405       if (__x._M_root() != nullptr)
01406         {
01407           auto __lbd =
01408             [&__roan](const value_type& __cval)
01409             {
01410               auto& __val = const_cast<value_type&>(__cval);
01411               return __roan(std::move_if_noexcept(__val));
01412             };
01413           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
01414           _M_leftmost() = _S_minimum(_M_root());
01415           _M_rightmost() = _S_maximum(_M_root());
01416           _M_impl._M_node_count = __x._M_impl._M_node_count;
01417           __x.clear();
01418         }
01419       return *this;
01420     }
01421 
01422   template<typename _Key, typename _Val, typename _KeyOfValue,
01423            typename _Compare, typename _Alloc>
01424     template<typename _Iterator>
01425       void
01426       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01427       _M_assign_unique(_Iterator __first, _Iterator __last)
01428       {
01429         _Reuse_or_alloc_node __roan(*this);
01430         _M_impl._M_reset();
01431         for (; __first != __last; ++__first)
01432           _M_insert_unique_(end(), *__first, __roan);
01433       }
01434 
01435   template<typename _Key, typename _Val, typename _KeyOfValue,
01436            typename _Compare, typename _Alloc>
01437     template<typename _Iterator>
01438       void
01439       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01440       _M_assign_equal(_Iterator __first, _Iterator __last)
01441       {
01442         _Reuse_or_alloc_node __roan(*this);
01443         _M_impl._M_reset();
01444         for (; __first != __last; ++__first)
01445           _M_insert_equal_(end(), *__first, __roan);
01446       }
01447 #endif
01448 
01449   template<typename _Key, typename _Val, typename _KeyOfValue,
01450            typename _Compare, typename _Alloc>
01451     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
01452     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01453     operator=(const _Rb_tree& __x)
01454     {
01455       if (this != &__x)
01456         {
01457           // Note that _Key may be a constant type.
01458 #if __cplusplus >= 201103L
01459           if (_Alloc_traits::_S_propagate_on_copy_assign())
01460             {
01461               auto& __this_alloc = this->_M_get_Node_allocator();
01462               auto& __that_alloc = __x._M_get_Node_allocator();
01463               if (!_Alloc_traits::_S_always_equal()
01464                   && __this_alloc != __that_alloc)
01465                 {
01466                   // Replacement allocator cannot free existing storage, we need
01467                   // to erase nodes first.
01468                   clear();
01469                   std::__alloc_on_copy(__this_alloc, __that_alloc);
01470                 }
01471             }
01472 #endif
01473 
01474           _Reuse_or_alloc_node __roan(*this);
01475           _M_impl._M_reset();
01476           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
01477           if (__x._M_root() != 0)
01478             {
01479               _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
01480               _M_leftmost() = _S_minimum(_M_root());
01481               _M_rightmost() = _S_maximum(_M_root());
01482               _M_impl._M_node_count = __x._M_impl._M_node_count;
01483             }
01484         }
01485 
01486       return *this;
01487     }
01488 
01489   template<typename _Key, typename _Val, typename _KeyOfValue,
01490            typename _Compare, typename _Alloc>
01491 #if __cplusplus >= 201103L
01492     template<typename _Arg, typename _NodeGen>
01493 #else
01494     template<typename _NodeGen>
01495 #endif
01496       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01497       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01498       _M_insert_(_Base_ptr __x, _Base_ptr __p,
01499 #if __cplusplus >= 201103L
01500                  _Arg&& __v,
01501 #else
01502                  const _Val& __v,
01503 #endif
01504                  _NodeGen& __node_gen)
01505       {
01506         bool __insert_left = (__x != 0 || __p == _M_end()
01507                               || _M_impl._M_key_compare(_KeyOfValue()(__v),
01508                                                         _S_key(__p)));
01509 
01510         _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
01511 
01512         _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
01513                                       this->_M_impl._M_header);
01514         ++_M_impl._M_node_count;
01515         return iterator(__z);
01516       }
01517 
01518   template<typename _Key, typename _Val, typename _KeyOfValue,
01519            typename _Compare, typename _Alloc>
01520 #if __cplusplus >= 201103L
01521     template<typename _Arg>
01522 #endif
01523     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01524     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01525 #if __cplusplus >= 201103L
01526     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
01527 #else
01528     _M_insert_lower(_Base_ptr __p, const _Val& __v)
01529 #endif
01530     {
01531       bool __insert_left = (__p == _M_end()
01532                             || !_M_impl._M_key_compare(_S_key(__p),
01533                                                        _KeyOfValue()(__v)));
01534 
01535       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
01536 
01537       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
01538                                     this->_M_impl._M_header);
01539       ++_M_impl._M_node_count;
01540       return iterator(__z);
01541     }
01542 
01543   template<typename _Key, typename _Val, typename _KeyOfValue,
01544            typename _Compare, typename _Alloc>
01545 #if __cplusplus >= 201103L
01546     template<typename _Arg>
01547 #endif
01548     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01549     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01550 #if __cplusplus >= 201103L
01551     _M_insert_equal_lower(_Arg&& __v)
01552 #else
01553     _M_insert_equal_lower(const _Val& __v)
01554 #endif
01555     {
01556       _Link_type __x = _M_begin();
01557       _Base_ptr __y = _M_end();
01558       while (__x != 0)
01559         {
01560           __y = __x;
01561           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
01562                 _S_left(__x) : _S_right(__x);
01563         }
01564       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
01565     }
01566 
01567   template<typename _Key, typename _Val, typename _KoV,
01568            typename _Compare, typename _Alloc>
01569     template<typename _NodeGen>
01570       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01571       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01572       _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
01573       {
01574         // Structural copy. __x and __p must be non-null.
01575         _Link_type __top = _M_clone_node(__x, __node_gen);
01576         __top->_M_parent = __p;
01577 
01578         __try
01579           {
01580             if (__x->_M_right)
01581               __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
01582             __p = __top;
01583             __x = _S_left(__x);
01584 
01585             while (__x != 0)
01586               {
01587                 _Link_type __y = _M_clone_node(__x, __node_gen);
01588                 __p->_M_left = __y;
01589                 __y->_M_parent = __p;
01590                 if (__x->_M_right)
01591                   __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
01592                 __p = __y;
01593                 __x = _S_left(__x);
01594               }
01595           }
01596         __catch(...)
01597           {
01598             _M_erase(__top);
01599             __throw_exception_again;
01600           }
01601         return __top;
01602       }
01603 
01604   template<typename _Key, typename _Val, typename _KeyOfValue,
01605            typename _Compare, typename _Alloc>
01606     void
01607     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01608     _M_erase(_Link_type __x)
01609     {
01610       // Erase without rebalancing.
01611       while (__x != 0)
01612         {
01613           _M_erase(_S_right(__x));
01614           _Link_type __y = _S_left(__x);
01615           _M_drop_node(__x);
01616           __x = __y;
01617         }
01618     }
01619 
01620   template<typename _Key, typename _Val, typename _KeyOfValue,
01621            typename _Compare, typename _Alloc>
01622     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01623                       _Compare, _Alloc>::iterator
01624     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01625     _M_lower_bound(_Link_type __x, _Base_ptr __y,
01626                    const _Key& __k)
01627     {
01628       while (__x != 0)
01629         if (!_M_impl._M_key_compare(_S_key(__x), __k))
01630           __y = __x, __x = _S_left(__x);
01631         else
01632           __x = _S_right(__x);
01633       return iterator(__y);
01634     }
01635 
01636   template<typename _Key, typename _Val, typename _KeyOfValue,
01637            typename _Compare, typename _Alloc>
01638     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01639                       _Compare, _Alloc>::const_iterator
01640     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01641     _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
01642                    const _Key& __k) const
01643     {
01644       while (__x != 0)
01645         if (!_M_impl._M_key_compare(_S_key(__x), __k))
01646           __y = __x, __x = _S_left(__x);
01647         else
01648           __x = _S_right(__x);
01649       return const_iterator(__y);
01650     }
01651 
01652   template<typename _Key, typename _Val, typename _KeyOfValue,
01653            typename _Compare, typename _Alloc>
01654     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01655                       _Compare, _Alloc>::iterator
01656     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01657     _M_upper_bound(_Link_type __x, _Base_ptr __y,
01658                    const _Key& __k)
01659     {
01660       while (__x != 0)
01661         if (_M_impl._M_key_compare(__k, _S_key(__x)))
01662           __y = __x, __x = _S_left(__x);
01663         else
01664           __x = _S_right(__x);
01665       return iterator(__y);
01666     }
01667 
01668   template<typename _Key, typename _Val, typename _KeyOfValue,
01669            typename _Compare, typename _Alloc>
01670     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01671                       _Compare, _Alloc>::const_iterator
01672     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01673     _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
01674                    const _Key& __k) const
01675     {
01676       while (__x != 0)
01677         if (_M_impl._M_key_compare(__k, _S_key(__x)))
01678           __y = __x, __x = _S_left(__x);
01679         else
01680           __x = _S_right(__x);
01681       return const_iterator(__y);
01682     }
01683 
01684   template<typename _Key, typename _Val, typename _KeyOfValue,
01685            typename _Compare, typename _Alloc>
01686     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01687                            _Compare, _Alloc>::iterator,
01688          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01689                            _Compare, _Alloc>::iterator>
01690     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01691     equal_range(const _Key& __k)
01692     {
01693       _Link_type __x = _M_begin();
01694       _Base_ptr __y = _M_end();
01695       while (__x != 0)
01696         {
01697           if (_M_impl._M_key_compare(_S_key(__x), __k))
01698             __x = _S_right(__x);
01699           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01700             __y = __x, __x = _S_left(__x);
01701           else
01702             {
01703               _Link_type __xu(__x);
01704               _Base_ptr __yu(__y);
01705               __y = __x, __x = _S_left(__x);
01706               __xu = _S_right(__xu);
01707               return pair<iterator,
01708                           iterator>(_M_lower_bound(__x, __y, __k),
01709                                     _M_upper_bound(__xu, __yu, __k));
01710             }
01711         }
01712       return pair<iterator, iterator>(iterator(__y),
01713                                       iterator(__y));
01714     }
01715 
01716   template<typename _Key, typename _Val, typename _KeyOfValue,
01717            typename _Compare, typename _Alloc>
01718     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01719                            _Compare, _Alloc>::const_iterator,
01720          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01721                            _Compare, _Alloc>::const_iterator>
01722     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01723     equal_range(const _Key& __k) const
01724     {
01725       _Const_Link_type __x = _M_begin();
01726       _Const_Base_ptr __y = _M_end();
01727       while (__x != 0)
01728         {
01729           if (_M_impl._M_key_compare(_S_key(__x), __k))
01730             __x = _S_right(__x);
01731           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01732             __y = __x, __x = _S_left(__x);
01733           else
01734             {
01735               _Const_Link_type __xu(__x);
01736               _Const_Base_ptr __yu(__y);
01737               __y = __x, __x = _S_left(__x);
01738               __xu = _S_right(__xu);
01739               return pair<const_iterator,
01740                           const_iterator>(_M_lower_bound(__x, __y, __k),
01741                                           _M_upper_bound(__xu, __yu, __k));
01742             }
01743         }
01744       return pair<const_iterator, const_iterator>(const_iterator(__y),
01745                                                   const_iterator(__y));
01746     }
01747 
01748   template<typename _Key, typename _Val, typename _KeyOfValue,
01749            typename _Compare, typename _Alloc>
01750     void
01751     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01752     swap(_Rb_tree& __t)
01753     _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
01754     {
01755       if (_M_root() == 0)
01756         {
01757           if (__t._M_root() != 0)
01758             {
01759               _M_root() = __t._M_root();
01760               _M_leftmost() = __t._M_leftmost();
01761               _M_rightmost() = __t._M_rightmost();
01762               _M_root()->_M_parent = _M_end();
01763               _M_impl._M_node_count = __t._M_impl._M_node_count;
01764               
01765               __t._M_impl._M_reset();
01766             }
01767         }
01768       else if (__t._M_root() == 0)
01769         {
01770           __t._M_root() = _M_root();
01771           __t._M_leftmost() = _M_leftmost();
01772           __t._M_rightmost() = _M_rightmost();
01773           __t._M_root()->_M_parent = __t._M_end();
01774           __t._M_impl._M_node_count = _M_impl._M_node_count;
01775           
01776           _M_impl._M_reset();
01777         }
01778       else
01779         {
01780           std::swap(_M_root(),__t._M_root());
01781           std::swap(_M_leftmost(),__t._M_leftmost());
01782           std::swap(_M_rightmost(),__t._M_rightmost());
01783           
01784           _M_root()->_M_parent = _M_end();
01785           __t._M_root()->_M_parent = __t._M_end();
01786           std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01787         }
01788       // No need to swap header's color as it does not change.
01789       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01790 
01791       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
01792                                 __t._M_get_Node_allocator());
01793     }
01794 
01795   template<typename _Key, typename _Val, typename _KeyOfValue,
01796            typename _Compare, typename _Alloc>
01797     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01798                            _Compare, _Alloc>::_Base_ptr,
01799          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01800                            _Compare, _Alloc>::_Base_ptr>
01801     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01802     _M_get_insert_unique_pos(const key_type& __k)
01803     {
01804       typedef pair<_Base_ptr, _Base_ptr> _Res;
01805       _Link_type __x = _M_begin();
01806       _Base_ptr __y = _M_end();
01807       bool __comp = true;
01808       while (__x != 0)
01809         {
01810           __y = __x;
01811           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
01812           __x = __comp ? _S_left(__x) : _S_right(__x);
01813         }
01814       iterator __j = iterator(__y);
01815       if (__comp)
01816         {
01817           if (__j == begin())
01818             return _Res(__x, __y);
01819           else
01820             --__j;
01821         }
01822       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
01823         return _Res(__x, __y);
01824       return _Res(__j._M_node, 0);
01825     }
01826 
01827   template<typename _Key, typename _Val, typename _KeyOfValue,
01828            typename _Compare, typename _Alloc>
01829     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01830                            _Compare, _Alloc>::_Base_ptr,
01831          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01832                            _Compare, _Alloc>::_Base_ptr>
01833     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01834     _M_get_insert_equal_pos(const key_type& __k)
01835     {
01836       typedef pair<_Base_ptr, _Base_ptr> _Res;
01837       _Link_type __x = _M_begin();
01838       _Base_ptr __y = _M_end();
01839       while (__x != 0)
01840         {
01841           __y = __x;
01842           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
01843                 _S_left(__x) : _S_right(__x);
01844         }
01845       return _Res(__x, __y);
01846     }
01847 
01848   template<typename _Key, typename _Val, typename _KeyOfValue,
01849            typename _Compare, typename _Alloc>
01850 #if __cplusplus >= 201103L
01851     template<typename _Arg>
01852 #endif
01853     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01854                            _Compare, _Alloc>::iterator, bool>
01855     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01856 #if __cplusplus >= 201103L
01857     _M_insert_unique(_Arg&& __v)
01858 #else
01859     _M_insert_unique(const _Val& __v)
01860 #endif
01861     {
01862       typedef pair<iterator, bool> _Res;
01863       pair<_Base_ptr, _Base_ptr> __res
01864         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
01865 
01866       if (__res.second)
01867         {
01868           _Alloc_node __an(*this);
01869           return _Res(_M_insert_(__res.first, __res.second,
01870                                  _GLIBCXX_FORWARD(_Arg, __v), __an),
01871                       true);
01872         }
01873 
01874       return _Res(iterator(__res.first), false);
01875     }
01876 
01877   template<typename _Key, typename _Val, typename _KeyOfValue,
01878            typename _Compare, typename _Alloc>
01879 #if __cplusplus >= 201103L
01880     template<typename _Arg>
01881 #endif
01882     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01883     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01884 #if __cplusplus >= 201103L
01885     _M_insert_equal(_Arg&& __v)
01886 #else
01887     _M_insert_equal(const _Val& __v)
01888 #endif
01889     {
01890       pair<_Base_ptr, _Base_ptr> __res
01891         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
01892       _Alloc_node __an(*this);
01893       return _M_insert_(__res.first, __res.second,
01894                         _GLIBCXX_FORWARD(_Arg, __v), __an);
01895     }
01896 
01897   template<typename _Key, typename _Val, typename _KeyOfValue,
01898            typename _Compare, typename _Alloc>
01899     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01900                            _Compare, _Alloc>::_Base_ptr,
01901          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01902                            _Compare, _Alloc>::_Base_ptr>
01903     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01904     _M_get_insert_hint_unique_pos(const_iterator __position,
01905                                   const key_type& __k)
01906     {
01907       iterator __pos = __position._M_const_cast();
01908       typedef pair<_Base_ptr, _Base_ptr> _Res;
01909 
01910       // end()
01911       if (__pos._M_node == _M_end())
01912         {
01913           if (size() > 0
01914               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
01915             return _Res(0, _M_rightmost());
01916           else
01917             return _M_get_insert_unique_pos(__k);
01918         }
01919       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
01920         {
01921           // First, try before...
01922           iterator __before = __pos;
01923           if (__pos._M_node == _M_leftmost()) // begin()
01924             return _Res(_M_leftmost(), _M_leftmost());
01925           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
01926             {
01927               if (_S_right(__before._M_node) == 0)
01928                 return _Res(0, __before._M_node);
01929               else
01930                 return _Res(__pos._M_node, __pos._M_node);
01931             }
01932           else
01933             return _M_get_insert_unique_pos(__k);
01934         }
01935       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
01936         {
01937           // ... then try after.
01938           iterator __after = __pos;
01939           if (__pos._M_node == _M_rightmost())
01940             return _Res(0, _M_rightmost());
01941           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
01942             {
01943               if (_S_right(__pos._M_node) == 0)
01944                 return _Res(0, __pos._M_node);
01945               else
01946                 return _Res(__after._M_node, __after._M_node);
01947             }
01948           else
01949             return _M_get_insert_unique_pos(__k);
01950         }
01951       else
01952         // Equivalent keys.
01953         return _Res(__pos._M_node, 0);
01954     }
01955 
01956   template<typename _Key, typename _Val, typename _KeyOfValue,
01957            typename _Compare, typename _Alloc>
01958 #if __cplusplus >= 201103L
01959     template<typename _Arg, typename _NodeGen>
01960 #else
01961     template<typename _NodeGen>
01962 #endif
01963       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01964       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01965       _M_insert_unique_(const_iterator __position,
01966 #if __cplusplus >= 201103L
01967                         _Arg&& __v,
01968 #else
01969                         const _Val& __v,
01970 #endif
01971                         _NodeGen& __node_gen)
01972     {
01973       pair<_Base_ptr, _Base_ptr> __res
01974         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
01975 
01976       if (__res.second)
01977         return _M_insert_(__res.first, __res.second,
01978                           _GLIBCXX_FORWARD(_Arg, __v),
01979                           __node_gen);
01980       return iterator(__res.first);
01981     }
01982 
01983   template<typename _Key, typename _Val, typename _KeyOfValue,
01984            typename _Compare, typename _Alloc>
01985     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01986                            _Compare, _Alloc>::_Base_ptr,
01987          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01988                            _Compare, _Alloc>::_Base_ptr>
01989     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01990     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
01991     {
01992       iterator __pos = __position._M_const_cast();
01993       typedef pair<_Base_ptr, _Base_ptr> _Res;
01994 
01995       // end()
01996       if (__pos._M_node == _M_end())
01997         {
01998           if (size() > 0
01999               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
02000             return _Res(0, _M_rightmost());
02001           else
02002             return _M_get_insert_equal_pos(__k);
02003         }
02004       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
02005         {
02006           // First, try before...
02007           iterator __before = __pos;
02008           if (__pos._M_node == _M_leftmost()) // begin()
02009             return _Res(_M_leftmost(), _M_leftmost());
02010           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
02011             {
02012               if (_S_right(__before._M_node) == 0)
02013                 return _Res(0, __before._M_node);
02014               else
02015                 return _Res(__pos._M_node, __pos._M_node);
02016             }
02017           else
02018             return _M_get_insert_equal_pos(__k);
02019         }
02020       else
02021         {
02022           // ... then try after.  
02023           iterator __after = __pos;
02024           if (__pos._M_node == _M_rightmost())
02025             return _Res(0, _M_rightmost());
02026           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
02027             {
02028               if (_S_right(__pos._M_node) == 0)
02029                 return _Res(0, __pos._M_node);
02030               else
02031                 return _Res(__after._M_node, __after._M_node);
02032             }
02033           else
02034             return _Res(0, 0);
02035         }
02036     }
02037 
02038   template<typename _Key, typename _Val, typename _KeyOfValue,
02039            typename _Compare, typename _Alloc>
02040 #if __cplusplus >= 201103L
02041     template<typename _Arg, typename _NodeGen>
02042 #else
02043     template<typename _NodeGen>
02044 #endif
02045       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02046       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02047       _M_insert_equal_(const_iterator __position,
02048 #if __cplusplus >= 201103L
02049                        _Arg&& __v,
02050 #else
02051                        const _Val& __v,
02052 #endif
02053                        _NodeGen& __node_gen)
02054       {
02055         pair<_Base_ptr, _Base_ptr> __res
02056           = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
02057 
02058         if (__res.second)
02059           return _M_insert_(__res.first, __res.second,
02060                             _GLIBCXX_FORWARD(_Arg, __v),
02061                             __node_gen);
02062 
02063         return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
02064       }
02065 
02066 #if __cplusplus >= 201103L
02067   template<typename _Key, typename _Val, typename _KeyOfValue,
02068            typename _Compare, typename _Alloc>
02069     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02070     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02071     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
02072     {
02073       bool __insert_left = (__x != 0 || __p == _M_end()
02074                             || _M_impl._M_key_compare(_S_key(__z),
02075                                                       _S_key(__p)));
02076 
02077       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
02078                                     this->_M_impl._M_header);
02079       ++_M_impl._M_node_count;
02080       return iterator(__z);
02081     }
02082 
02083   template<typename _Key, typename _Val, typename _KeyOfValue,
02084            typename _Compare, typename _Alloc>
02085     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02086     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02087     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
02088     {
02089       bool __insert_left = (__p == _M_end()
02090                             || !_M_impl._M_key_compare(_S_key(__p),
02091                                                        _S_key(__z)));
02092 
02093       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
02094                                     this->_M_impl._M_header);
02095       ++_M_impl._M_node_count;
02096       return iterator(__z);
02097     }
02098 
02099   template<typename _Key, typename _Val, typename _KeyOfValue,
02100            typename _Compare, typename _Alloc>
02101     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02102     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02103     _M_insert_equal_lower_node(_Link_type __z)
02104     {
02105       _Link_type __x = _M_begin();
02106       _Base_ptr __y = _M_end();
02107       while (__x != 0)
02108         {
02109           __y = __x;
02110           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
02111                 _S_left(__x) : _S_right(__x);
02112         }
02113       return _M_insert_lower_node(__y, __z);
02114     }
02115 
02116   template<typename _Key, typename _Val, typename _KeyOfValue,
02117            typename _Compare, typename _Alloc>
02118     template<typename... _Args>
02119       pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
02120                              _Compare, _Alloc>::iterator, bool>
02121       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02122       _M_emplace_unique(_Args&&... __args)
02123       {
02124         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02125 
02126         __try
02127           {
02128             typedef pair<iterator, bool> _Res;
02129             auto __res = _M_get_insert_unique_pos(_S_key(__z));
02130             if (__res.second)
02131               return _Res(_M_insert_node(__res.first, __res.second, __z), true);
02132         
02133             _M_drop_node(__z);
02134             return _Res(iterator(__res.first), false);
02135           }
02136         __catch(...)
02137           {
02138             _M_drop_node(__z);
02139             __throw_exception_again;
02140           }
02141       }
02142 
02143   template<typename _Key, typename _Val, typename _KeyOfValue,
02144            typename _Compare, typename _Alloc>
02145     template<typename... _Args>
02146       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02147       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02148       _M_emplace_equal(_Args&&... __args)
02149       {
02150         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02151 
02152         __try
02153           {
02154             auto __res = _M_get_insert_equal_pos(_S_key(__z));
02155             return _M_insert_node(__res.first, __res.second, __z);
02156           }
02157         __catch(...)
02158           {
02159             _M_drop_node(__z);
02160             __throw_exception_again;
02161           }
02162       }
02163 
02164   template<typename _Key, typename _Val, typename _KeyOfValue,
02165            typename _Compare, typename _Alloc>
02166     template<typename... _Args>
02167       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02168       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02169       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
02170       {
02171         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02172 
02173         __try
02174           {
02175             auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
02176 
02177             if (__res.second)
02178               return _M_insert_node(__res.first, __res.second, __z);
02179 
02180             _M_drop_node(__z);
02181             return iterator(__res.first);
02182           }
02183         __catch(...)
02184           {
02185             _M_drop_node(__z);
02186             __throw_exception_again;
02187           }
02188       }
02189 
02190   template<typename _Key, typename _Val, typename _KeyOfValue,
02191            typename _Compare, typename _Alloc>
02192     template<typename... _Args>
02193       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02194       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02195       _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
02196       {
02197         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02198 
02199         __try
02200           {
02201             auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
02202 
02203             if (__res.second)
02204               return _M_insert_node(__res.first, __res.second, __z);
02205 
02206             return _M_insert_equal_lower_node(__z);
02207           }
02208         __catch(...)
02209           {
02210             _M_drop_node(__z);
02211             __throw_exception_again;
02212           }
02213       }
02214 #endif
02215 
02216   template<typename _Key, typename _Val, typename _KoV,
02217            typename _Cmp, typename _Alloc>
02218     template<class _II>
02219       void
02220       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
02221       _M_insert_unique(_II __first, _II __last)
02222       {
02223         _Alloc_node __an(*this);
02224         for (; __first != __last; ++__first)
02225           _M_insert_unique_(end(), *__first, __an);
02226       }
02227 
02228   template<typename _Key, typename _Val, typename _KoV,
02229            typename _Cmp, typename _Alloc>
02230     template<class _II>
02231       void
02232       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
02233       _M_insert_equal(_II __first, _II __last)
02234       {
02235         _Alloc_node __an(*this);
02236         for (; __first != __last; ++__first)
02237           _M_insert_equal_(end(), *__first, __an);
02238       }
02239 
02240   template<typename _Key, typename _Val, typename _KeyOfValue,
02241            typename _Compare, typename _Alloc>
02242     void
02243     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02244     _M_erase_aux(const_iterator __position)
02245     {
02246       _Link_type __y =
02247         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
02248                                 (const_cast<_Base_ptr>(__position._M_node),
02249                                  this->_M_impl._M_header));
02250       _M_drop_node(__y);
02251       --_M_impl._M_node_count;
02252     }
02253 
02254   template<typename _Key, typename _Val, typename _KeyOfValue,
02255            typename _Compare, typename _Alloc>
02256     void
02257     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02258     _M_erase_aux(const_iterator __first, const_iterator __last)
02259     {
02260       if (__first == begin() && __last == end())
02261         clear();
02262       else
02263         while (__first != __last)
02264           erase(__first++);
02265     }
02266 
02267   template<typename _Key, typename _Val, typename _KeyOfValue,
02268            typename _Compare, typename _Alloc>
02269     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
02270     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02271     erase(const _Key& __x)
02272     {
02273       pair<iterator, iterator> __p = equal_range(__x);
02274       const size_type __old_size = size();
02275       erase(__p.first, __p.second);
02276       return __old_size - size();
02277     }
02278 
02279   template<typename _Key, typename _Val, typename _KeyOfValue,
02280            typename _Compare, typename _Alloc>
02281     void
02282     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02283     erase(const _Key* __first, const _Key* __last)
02284     {
02285       while (__first != __last)
02286         erase(*__first++);
02287     }
02288 
02289   template<typename _Key, typename _Val, typename _KeyOfValue,
02290            typename _Compare, typename _Alloc>
02291     typename _Rb_tree<_Key, _Val, _KeyOfValue,
02292                       _Compare, _Alloc>::iterator
02293     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02294     find(const _Key& __k)
02295     {
02296       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
02297       return (__j == end()
02298               || _M_impl._M_key_compare(__k,
02299                                         _S_key(__j._M_node))) ? end() : __j;
02300     }
02301 
02302   template<typename _Key, typename _Val, typename _KeyOfValue,
02303            typename _Compare, typename _Alloc>
02304     typename _Rb_tree<_Key, _Val, _KeyOfValue,
02305                       _Compare, _Alloc>::const_iterator
02306     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02307     find(const _Key& __k) const
02308     {
02309       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
02310       return (__j == end()
02311               || _M_impl._M_key_compare(__k, 
02312                                         _S_key(__j._M_node))) ? end() : __j;
02313     }
02314 
02315   template<typename _Key, typename _Val, typename _KeyOfValue,
02316            typename _Compare, typename _Alloc>
02317     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
02318     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02319     count(const _Key& __k) const
02320     {
02321       pair<const_iterator, const_iterator> __p = equal_range(__k);
02322       const size_type __n = std::distance(__p.first, __p.second);
02323       return __n;
02324     }
02325 
02326   _GLIBCXX_PURE unsigned int
02327   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
02328                        const _Rb_tree_node_base* __root) throw ();
02329 
02330   template<typename _Key, typename _Val, typename _KeyOfValue,
02331            typename _Compare, typename _Alloc>
02332     bool
02333     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
02334     {
02335       if (_M_impl._M_node_count == 0 || begin() == end())
02336         return _M_impl._M_node_count == 0 && begin() == end()
02337                && this->_M_impl._M_header._M_left == _M_end()
02338                && this->_M_impl._M_header._M_right == _M_end();
02339 
02340       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
02341       for (const_iterator __it = begin(); __it != end(); ++__it)
02342         {
02343           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
02344           _Const_Link_type __L = _S_left(__x);
02345           _Const_Link_type __R = _S_right(__x);
02346 
02347           if (__x->_M_color == _S_red)
02348             if ((__L && __L->_M_color == _S_red)
02349                 || (__R && __R->_M_color == _S_red))
02350               return false;
02351 
02352           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
02353             return false;
02354           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
02355             return false;
02356 
02357           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
02358             return false;
02359         }
02360 
02361       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
02362         return false;
02363       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
02364         return false;
02365       return true;
02366     }
02367 
02368 _GLIBCXX_END_NAMESPACE_VERSION
02369 } // namespace
02370 
02371 #endif