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