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