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