libstdc++-v3/include/bits/stl_tree.h

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2024 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1996,1997
  28  * Silicon Graphics Computer Systems, Inc.
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Silicon Graphics makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1994
  40  * Hewlett-Packard Company
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Hewlett-Packard Company makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  *
  50  *
  51  */
  52
  53 /** @file bits/stl_tree.h
  54  *  This is an internal header file, included by other library headers.
  55  *  Do not attempt to use it directly. @headername{map,set}
  56  */
  57
  58 #ifndef _STL_TREE_H
  59 #define _STL_TREE_H 1
  60
  61 #ifdef _GLIBCXX_SYSHDR
  62 #pragma GCC system_header
  63 #endif
  64
  65 #include <bits/stl_algobase.h>
  66 #include <bits/allocator.h>
  67 #include <bits/stl_function.h>
  68 #include <bits/cpp_type_traits.h>
  69 #include <ext/alloc_traits.h>
  70 #if __cplusplus >= 201103L
  71 # include <ext/aligned_buffer.h>
  72 #endif
  73 #if __cplusplus > 201402L
  74 # include <bits/node_handle.h>
  75 #endif
  76
  77 namespace std _GLIBCXX_VISIBILITY(default)
  78 {
  79 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  80
  81   // Red-black tree class, designed for use in implementing STL
  82   // associative containers (set, multiset, map, and multimap). The
  83   // insertion and deletion algorithms are based on those in Cormen,
  84   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  85   // 1990), except that
  86   //
  87   // (1) the header cell is maintained with links not only to the root
  88   // but also to the leftmost node of the tree, to enable constant
  89   // time begin(), and to the rightmost node of the tree, to enable
  90   // linear time performance when used with the generic set algorithms
  91   // (set_union, etc.)
  92   //
  93   // (2) when a node being deleted has two children its successor node
  94   // is relinked into its place, rather than copied, so that the only
  95   // iterators invalidated are those referring to the deleted node.
  96
  97   enum _Rb_tree_color { _S_red = false, _S_black = true };
  98
  99   struct _Rb_tree_node_base
 100   {
 101     typedef _Rb_tree_node_base* _Base_ptr;
 102     typedef const _Rb_tree_node_base* _Const_Base_ptr;
 103
 104     _Rb_tree_color      _M_color;
 105     _Base_ptr           _M_parent;
 106     _Base_ptr           _M_left;
 107     _Base_ptr           _M_right;
 108
 109     static _Base_ptr
 110     _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 111     {
 112       while (__x->_M_left != 0) __x = __x->_M_left;
 113       return __x;
 114     }
 115
 116     static _Const_Base_ptr
 117     _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
 118     {
 119       while (__x->_M_left != 0) __x = __x->_M_left;
 120       return __x;
 121     }
 122
 123     static _Base_ptr
 124     _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 125     {
 126       while (__x->_M_right != 0) __x = __x->_M_right;
 127       return __x;
 128     }
 129
 130     static _Const_Base_ptr
 131     _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
 132     {
 133       while (__x->_M_right != 0) __x = __x->_M_right;
 134       return __x;
 135     }
 136   };
 137
 138   // Helper type offering value initialization guarantee on the compare functor.
 139   template<typename _Key_compare>
 140     struct _Rb_tree_key_compare
 141     {
 142       _Key_compare              _M_key_compare;
 143
 144       _Rb_tree_key_compare()
 145       _GLIBCXX_NOEXCEPT_IF(
 146         is_nothrow_default_constructible<_Key_compare>::value)
 147       : _M_key_compare()
 148       { }
 149
 150       _Rb_tree_key_compare(const _Key_compare& __comp)
 151       : _M_key_compare(__comp)
 152       { }
 153
 154 #if __cplusplus >= 201103L
 155       // Copy constructor added for consistency with C++98 mode.
 156       _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
 157
 158       _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
 159         noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
 160       : _M_key_compare(__x._M_key_compare)
 161       { }
 162 #endif
 163     };
 164
 165   // Helper type to manage default initialization of node count and header.
 166   struct _Rb_tree_header
 167   {
 168     _Rb_tree_node_base  _M_header;
 169     size_t              _M_node_count; // Keeps track of size of tree.
 170
 171     _Rb_tree_header() _GLIBCXX_NOEXCEPT
 172     {
 173       _M_header._M_color = _S_red;
 174       _M_reset();
 175     }
 176
 177 #if __cplusplus >= 201103L
 178     _Rb_tree_header(_Rb_tree_header&& __x) noexcept
 179     {
 180       if (__x._M_header._M_parent != nullptr)
 181         _M_move_data(__x);
 182       else
 183         {
 184           _M_header._M_color = _S_red;
 185           _M_reset();
 186         }
 187     }
 188 #endif
 189
 190     void
 191     _M_move_data(_Rb_tree_header& __from)
 192     {
 193       _M_header._M_color = __from._M_header._M_color;
 194       _M_header._M_parent = __from._M_header._M_parent;
 195       _M_header._M_left = __from._M_header._M_left;
 196       _M_header._M_right = __from._M_header._M_right;
 197       _M_header._M_parent->_M_parent = &_M_header;
 198       _M_node_count = __from._M_node_count;
 199
 200       __from._M_reset();
 201     }
 202
 203     void
 204     _M_reset()
 205     {
 206       _M_header._M_parent = 0;
 207       _M_header._M_left = &_M_header;
 208       _M_header._M_right = &_M_header;
 209       _M_node_count = 0;
 210     }
 211   };
 212
 213   template<typename _Val>
 214     struct _Rb_tree_node : public _Rb_tree_node_base
 215     {
 216       typedef _Rb_tree_node<_Val>* _Link_type;
 217
 218 #if __cplusplus < 201103L
 219       _Val _M_value_field;
 220
 221       _Val*
 222       _M_valptr()
 223       { return std::__addressof(_M_value_field); }
 224
 225       const _Val*
 226       _M_valptr() const
 227       { return std::__addressof(_M_value_field); }
 228 #else
 229       __gnu_cxx::__aligned_membuf<_Val> _M_storage;
 230
 231       _Val*
 232       _M_valptr()
 233       { return _M_storage._M_ptr(); }
 234
 235       const _Val*
 236       _M_valptr() const
 237       { return _M_storage._M_ptr(); }
 238 #endif
 239     };
 240
 241   _GLIBCXX_PURE _Rb_tree_node_base*
 242   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
 243
 244   _GLIBCXX_PURE const _Rb_tree_node_base*
 245   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
 246
 247   _GLIBCXX_PURE _Rb_tree_node_base*
 248   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
 249
 250   _GLIBCXX_PURE const _Rb_tree_node_base*
 251   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
 252
 253   template<typename _Tp>
 254     struct _Rb_tree_iterator
 255     {
 256       typedef _Tp  value_type;
 257       typedef _Tp& reference;
 258       typedef _Tp* pointer;
 259
 260       typedef bidirectional_iterator_tag iterator_category;
 261       typedef ptrdiff_t                  difference_type;
 262
 263       typedef _Rb_tree_iterator<_Tp>            _Self;
 264       typedef _Rb_tree_node_base::_Base_ptr     _Base_ptr;
 265       typedef _Rb_tree_node<_Tp>*               _Link_type;
 266
 267       _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
 268       : _M_node() { }
 269
 270       explicit
 271       _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 272       : _M_node(__x) { }
 273
 274       reference
 275       operator*() const _GLIBCXX_NOEXCEPT
 276       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
 277
 278       pointer
 279       operator->() const _GLIBCXX_NOEXCEPT
 280       { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
 281
 282       _Self&
 283       operator++() _GLIBCXX_NOEXCEPT
 284       {
 285         _M_node = _Rb_tree_increment(_M_node);
 286         return *this;
 287       }
 288
 289       _Self
 290       operator++(int) _GLIBCXX_NOEXCEPT
 291       {
 292         _Self __tmp = *this;
 293         _M_node = _Rb_tree_increment(_M_node);
 294         return __tmp;
 295       }
 296
 297       _Self&
 298       operator--() _GLIBCXX_NOEXCEPT
 299       {
 300         _M_node = _Rb_tree_decrement(_M_node);
 301         return *this;
 302       }
 303
 304       _Self
 305       operator--(int) _GLIBCXX_NOEXCEPT
 306       {
 307         _Self __tmp = *this;
 308         _M_node = _Rb_tree_decrement(_M_node);
 309         return __tmp;
 310       }
 311
 312       friend bool
 313       operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
 314       { return __x._M_node == __y._M_node; }
 315
 316 #if ! __cpp_lib_three_way_comparison
 317       friend bool
 318       operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
 319       { return __x._M_node != __y._M_node; }
 320 #endif
 321
 322       _Base_ptr _M_node;
 323     };
 324
 325   template<typename _Tp>
 326     struct _Rb_tree_const_iterator
 327     {
 328       typedef _Tp        value_type;
 329       typedef const _Tp& reference;
 330       typedef const _Tp* pointer;
 331
 332       typedef _Rb_tree_iterator<_Tp> iterator;
 333
 334       typedef bidirectional_iterator_tag iterator_category;
 335       typedef ptrdiff_t                  difference_type;
 336
 337       typedef _Rb_tree_const_iterator<_Tp>              _Self;
 338       typedef _Rb_tree_node_base::_Const_Base_ptr       _Base_ptr;
 339       typedef const _Rb_tree_node<_Tp>*                 _Link_type;
 340
 341       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
 342       : _M_node() { }
 343
 344       explicit
 345       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 346       : _M_node(__x) { }
 347
 348       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
 349       : _M_node(__it._M_node) { }
 350
 351       iterator
 352       _M_const_cast() const _GLIBCXX_NOEXCEPT
 353       { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
 354
 355       reference
 356       operator*() const _GLIBCXX_NOEXCEPT
 357       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
 358
 359       pointer
 360       operator->() const _GLIBCXX_NOEXCEPT
 361       { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
 362
 363       _Self&
 364       operator++() _GLIBCXX_NOEXCEPT
 365       {
 366         _M_node = _Rb_tree_increment(_M_node);
 367         return *this;
 368       }
 369
 370       _Self
 371       operator++(int) _GLIBCXX_NOEXCEPT
 372       {
 373         _Self __tmp = *this;
 374         _M_node = _Rb_tree_increment(_M_node);
 375         return __tmp;
 376       }
 377
 378       _Self&
 379       operator--() _GLIBCXX_NOEXCEPT
 380       {
 381         _M_node = _Rb_tree_decrement(_M_node);
 382         return *this;
 383       }
 384
 385       _Self
 386       operator--(int) _GLIBCXX_NOEXCEPT
 387       {
 388         _Self __tmp = *this;
 389         _M_node = _Rb_tree_decrement(_M_node);
 390         return __tmp;
 391       }
 392
 393       friend bool
 394       operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
 395       { return __x._M_node == __y._M_node; }
 396
 397 #if ! __cpp_lib_three_way_comparison
 398       friend bool
 399       operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
 400       { return __x._M_node != __y._M_node; }
 401 #endif
 402
 403       _Base_ptr _M_node;
 404     };
 405
 406   __attribute__((__nonnull__))
 407   void
 408   _Rb_tree_insert_and_rebalance(const bool __insert_left,
 409                                 _Rb_tree_node_base* __x,
 410                                 _Rb_tree_node_base* __p,
 411                                 _Rb_tree_node_base& __header) throw ();
 412
 413   __attribute__((__nonnull__,__returns_nonnull__))
 414   _Rb_tree_node_base*
 415   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 416                                _Rb_tree_node_base& __header) throw ();
 417
 418 #if __cplusplus > 201402L
 419   template<typename _Tree1, typename _Cmp2>
 420     struct _Rb_tree_merge_helper { };
 421 #endif
 422
 423   template<typename _Key, typename _Val, typename _KeyOfValue,
 424            typename _Compare, typename _Alloc = allocator<_Val> >
 425     class _Rb_tree
 426     {
 427       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
 428         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
 429
 430       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
 431
 432     protected:
 433       typedef _Rb_tree_node_base*               _Base_ptr;
 434       typedef const _Rb_tree_node_base*         _Const_Base_ptr;
 435       typedef _Rb_tree_node<_Val>*              _Link_type;
 436       typedef const _Rb_tree_node<_Val>*        _Const_Link_type;
 437
 438     private:
 439       // Functor recycling a pool of nodes and using allocation once the pool
 440       // is empty.
 441       struct _Reuse_or_alloc_node
 442       {
 443         _Reuse_or_alloc_node(_Rb_tree& __t)
 444         : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
 445         {
 446           if (_M_root)
 447             {
 448               _M_root->_M_parent = 0;
 449
 450               if (_M_nodes->_M_left)
 451                 _M_nodes = _M_nodes->_M_left;
 452             }
 453           else
 454             _M_nodes = 0;
 455         }
 456
 457 #if __cplusplus >= 201103L
 458         _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
 459 #endif
 460
 461         ~_Reuse_or_alloc_node()
 462         { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
 463
 464         template<typename _Arg>
 465           _Link_type
 466           operator()(_GLIBCXX_FWDREF(_Arg) __arg)
 467           {
 468             _Link_type __node = static_cast<_Link_type>(_M_extract());
 469             if (__node)
 470               {
 471                 _M_t._M_destroy_node(__node);
 472                 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
 473                 return __node;
 474               }
 475
 476             return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
 477           }
 478
 479       private:
 480         _Base_ptr
 481         _M_extract()
 482         {
 483           if (!_M_nodes)
 484             return _M_nodes;
 485
 486           _Base_ptr __node = _M_nodes;
 487           _M_nodes = _M_nodes->_M_parent;
 488           if (_M_nodes)
 489             {
 490               if (_M_nodes->_M_right == __node)
 491                 {
 492                   _M_nodes->_M_right = 0;
 493
 494                   if (_M_nodes->_M_left)
 495                     {
 496                       _M_nodes = _M_nodes->_M_left;
 497
 498                       while (_M_nodes->_M_right)
 499                         _M_nodes = _M_nodes->_M_right;
 500
 501                       if (_M_nodes->_M_left)
 502                         _M_nodes = _M_nodes->_M_left;
 503                     }
 504                 }
 505               else // __node is on the left.
 506                 _M_nodes->_M_left = 0;
 507             }
 508           else
 509             _M_root = 0;
 510
 511           return __node;
 512         }
 513
 514         _Base_ptr _M_root;
 515         _Base_ptr _M_nodes;
 516         _Rb_tree& _M_t;
 517       };
 518
 519       // Functor similar to the previous one but without any pool of nodes to
 520       // recycle.
 521       struct _Alloc_node
 522       {
 523         _Alloc_node(_Rb_tree& __t)
 524         : _M_t(__t) { }
 525
 526         template<typename _Arg>
 527           _Link_type
 528           operator()(_GLIBCXX_FWDREF(_Arg) __arg) const
 529           { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
 530
 531       private:
 532         _Rb_tree& _M_t;
 533       };
 534
 535     public:
 536       typedef _Key                              key_type;
 537       typedef _Val                              value_type;
 538       typedef value_type*                       pointer;
 539       typedef const value_type*                 const_pointer;
 540       typedef value_type&                       reference;
 541       typedef const value_type&                 const_reference;
 542       typedef size_t                            size_type;
 543       typedef ptrdiff_t                         difference_type;
 544       typedef _Alloc                            allocator_type;
 545
 546       _Node_allocator&
 547       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
 548       { return this->_M_impl; }
 549
 550       const _Node_allocator&
 551       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
 552       { return this->_M_impl; }
 553
 554       allocator_type
 555       get_allocator() const _GLIBCXX_NOEXCEPT
 556       { return allocator_type(_M_get_Node_allocator()); }
 557
 558     protected:
 559       _Link_type
 560       _M_get_node()
 561       { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
 562
 563       void
 564       _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
 565       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
 566
 567 #if __cplusplus < 201103L
 568       void
 569       _M_construct_node(_Link_type __node, const value_type& __x)
 570       {
 571         __try
 572           { get_allocator().construct(__node->_M_valptr(), __x); }
 573         __catch(...)
 574           {
 575             _M_put_node(__node);
 576             __throw_exception_again;
 577           }
 578       }
 579
 580       _Link_type
 581       _M_create_node(const value_type& __x)
 582       {
 583         _Link_type __tmp = _M_get_node();
 584         _M_construct_node(__tmp, __x);
 585         return __tmp;
 586       }
 587 #else
 588       template<typename... _Args>
 589         void
 590         _M_construct_node(_Link_type __node, _Args&&... __args)
 591         {
 592           __try
 593             {
 594               ::new(__node) _Rb_tree_node<_Val>;
 595               _Alloc_traits::construct(_M_get_Node_allocator(),
 596                                        __node->_M_valptr(),
 597                                        std::forward<_Args>(__args)...);
 598             }
 599           __catch(...)
 600             {
 601               __node->~_Rb_tree_node<_Val>();
 602               _M_put_node(__node);
 603               __throw_exception_again;
 604             }
 605         }
 606
 607       template<typename... _Args>
 608         _Link_type
 609         _M_create_node(_Args&&... __args)
 610         {
 611           _Link_type __tmp = _M_get_node();
 612           _M_construct_node(__tmp, std::forward<_Args>(__args)...);
 613           return __tmp;
 614         }
 615 #endif
 616
 617       void
 618       _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT
 619       {
 620 #if __cplusplus < 201103L
 621         get_allocator().destroy(__p->_M_valptr());
 622 #else
 623         _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
 624         __p->~_Rb_tree_node<_Val>();
 625 #endif
 626       }
 627
 628       void
 629       _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
 630       {
 631         _M_destroy_node(__p);
 632         _M_put_node(__p);
 633       }
 634
 635       template<bool _MoveValue, typename _NodeGen>
 636         _Link_type
 637         _M_clone_node(_Link_type __x, _NodeGen& __node_gen)
 638         {
 639 #if __cplusplus >= 201103L
 640           using _Vp = __conditional_t<_MoveValue,
 641                                       value_type&&,
 642                                       const value_type&>;
 643 #endif
 644           _Link_type __tmp
 645             = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));
 646           __tmp->_M_color = __x->_M_color;
 647           __tmp->_M_left = 0;
 648           __tmp->_M_right = 0;
 649           return __tmp;
 650         }
 651
 652     protected:
 653 #if _GLIBCXX_INLINE_VERSION
 654       template<typename _Key_compare>
 655 #else
 656       // Unused _Is_pod_comparator is kept as it is part of mangled name.
 657       template<typename _Key_compare,
 658                bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
 659 #endif
 660         struct _Rb_tree_impl
 661         : public _Node_allocator
 662         , public _Rb_tree_key_compare<_Key_compare>
 663         , public _Rb_tree_header
 664         {
 665           typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
 666
 667           _Rb_tree_impl()
 668             _GLIBCXX_NOEXCEPT_IF(
 669                 is_nothrow_default_constructible<_Node_allocator>::value
 670                 && is_nothrow_default_constructible<_Base_key_compare>::value )
 671           : _Node_allocator()
 672           { }
 673
 674           _Rb_tree_impl(const _Rb_tree_impl& __x)
 675           : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
 676           , _Base_key_compare(__x._M_key_compare)
 677           , _Rb_tree_header()
 678           { }
 679
 680 #if __cplusplus < 201103L
 681           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
 682           : _Node_allocator(__a), _Base_key_compare(__comp)
 683           { }
 684 #else
 685           _Rb_tree_impl(_Rb_tree_impl&&)
 686             noexcept( is_nothrow_move_constructible<_Base_key_compare>::value )
 687           = default;
 688
 689           explicit
 690           _Rb_tree_impl(_Node_allocator&& __a)
 691           : _Node_allocator(std::move(__a))
 692           { }
 693
 694           _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
 695           : _Node_allocator(std::move(__a)),
 696             _Base_key_compare(std::move(__x)),
 697             _Rb_tree_header(std::move(__x))
 698           { }
 699
 700           _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 701           : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 702           { }
 703 #endif
 704         };
 705
 706       _Rb_tree_impl<_Compare> _M_impl;
 707
 708     protected:
 709       _Base_ptr&
 710       _M_root() _GLIBCXX_NOEXCEPT
 711       { return this->_M_impl._M_header._M_parent; }
 712
 713       _Const_Base_ptr
 714       _M_root() const _GLIBCXX_NOEXCEPT
 715       { return this->_M_impl._M_header._M_parent; }
 716
 717       _Base_ptr&
 718       _M_leftmost() _GLIBCXX_NOEXCEPT
 719       { return this->_M_impl._M_header._M_left; }
 720
 721       _Const_Base_ptr
 722       _M_leftmost() const _GLIBCXX_NOEXCEPT
 723       { return this->_M_impl._M_header._M_left; }
 724
 725       _Base_ptr&
 726       _M_rightmost() _GLIBCXX_NOEXCEPT
 727       { return this->_M_impl._M_header._M_right; }
 728
 729       _Const_Base_ptr
 730       _M_rightmost() const _GLIBCXX_NOEXCEPT
 731       { return this->_M_impl._M_header._M_right; }
 732
 733       _Link_type
 734       _M_mbegin() const _GLIBCXX_NOEXCEPT
 735       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 736
 737       _Link_type
 738       _M_begin() _GLIBCXX_NOEXCEPT
 739       { return _M_mbegin(); }
 740
 741       _Const_Link_type
 742       _M_begin() const _GLIBCXX_NOEXCEPT
 743       {
 744         return static_cast<_Const_Link_type>
 745           (this->_M_impl._M_header._M_parent);
 746       }
 747
 748       _Base_ptr
 749       _M_end() _GLIBCXX_NOEXCEPT
 750       { return &this->_M_impl._M_header; }
 751
 752       _Const_Base_ptr
 753       _M_end() const _GLIBCXX_NOEXCEPT
 754       { return &this->_M_impl._M_header; }
 755
 756       static const _Key&
 757       _S_key(_Const_Link_type __x)
 758       {
 759 #if __cplusplus >= 201103L
 760         // If we're asking for the key we're presumably using the comparison
 761         // object, and so this is a good place to sanity check it.
 762         static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
 763                       "comparison object must be invocable "
 764                       "with two arguments of key type");
 765 # if __cplusplus >= 201703L
 766         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 767         // 2542. Missing const requirements for associative containers
 768         if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
 769           static_assert(
 770               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
 771               "comparison object must be invocable as const");
 772 # endif // C++17
 773 #endif // C++11
 774
 775         return _KeyOfValue()(*__x->_M_valptr());
 776       }
 777
 778       static _Link_type
 779       _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 780       { return static_cast<_Link_type>(__x->_M_left); }
 781
 782       static _Const_Link_type
 783       _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
 784       { return static_cast<_Const_Link_type>(__x->_M_left); }
 785
 786       static _Link_type
 787       _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 788       { return static_cast<_Link_type>(__x->_M_right); }
 789
 790       static _Const_Link_type
 791       _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
 792       { return static_cast<_Const_Link_type>(__x->_M_right); }
 793
 794       static const _Key&
 795       _S_key(_Const_Base_ptr __x)
 796       { return _S_key(static_cast<_Const_Link_type>(__x)); }
 797
 798       static _Base_ptr
 799       _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 800       { return _Rb_tree_node_base::_S_minimum(__x); }
 801
 802       static _Const_Base_ptr
 803       _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
 804       { return _Rb_tree_node_base::_S_minimum(__x); }
 805
 806       static _Base_ptr
 807       _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
 808       { return _Rb_tree_node_base::_S_maximum(__x); }
 809
 810       static _Const_Base_ptr
 811       _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
 812       { return _Rb_tree_node_base::_S_maximum(__x); }
 813
 814     public:
 815       typedef _Rb_tree_iterator<value_type>       iterator;
 816       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 817
 818       typedef std::reverse_iterator<iterator>       reverse_iterator;
 819       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 820
 821 #if __cplusplus > 201402L
 822       using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
 823       using insert_return_type = _Node_insert_return<
 824         __conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
 825         node_type>;
 826 #endif
 827
 828       pair<_Base_ptr, _Base_ptr>
 829       _M_get_insert_unique_pos(const key_type& __k);
 830
 831       pair<_Base_ptr, _Base_ptr>
 832       _M_get_insert_equal_pos(const key_type& __k);
 833
 834       pair<_Base_ptr, _Base_ptr>
 835       _M_get_insert_hint_unique_pos(const_iterator __pos,
 836                                     const key_type& __k);
 837
 838       pair<_Base_ptr, _Base_ptr>
 839       _M_get_insert_hint_equal_pos(const_iterator __pos,
 840                                    const key_type& __k);
 841
 842     private:
 843 #if __cplusplus >= 201103L
 844       template<typename _Arg, typename _NodeGen>
 845         iterator
 846         _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
 847
 848       iterator
 849       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
 850
 851       template<typename _Arg>
 852         iterator
 853         _M_insert_lower(_Base_ptr __y, _Arg&& __v);
 854
 855       template<typename _Arg>
 856         iterator
 857         _M_insert_equal_lower(_Arg&& __x);
 858
 859       iterator
 860       _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
 861
 862       iterator
 863       _M_insert_equal_lower_node(_Link_type __z);
 864 #else
 865       template<typename _NodeGen>
 866         iterator
 867         _M_insert_(_Base_ptr __x, _Base_ptr __y,
 868                    const value_type& __v, _NodeGen&);
 869
 870       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 871       // 233. Insertion hints in associative containers.
 872       iterator
 873       _M_insert_lower(_Base_ptr __y, const value_type& __v);
 874
 875       iterator
 876       _M_insert_equal_lower(const value_type& __x);
 877 #endif
 878
 879       enum { __as_lvalue, __as_rvalue };
 880
 881       template<bool _MoveValues, typename _NodeGen>
 882         _Link_type
 883         _M_copy(_Link_type, _Base_ptr, _NodeGen&);
 884
 885       template<bool _MoveValues, typename _NodeGen>
 886         _Link_type
 887         _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
 888         {
 889           _Link_type __root =
 890             _M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen);
 891           _M_leftmost() = _S_minimum(__root);
 892           _M_rightmost() = _S_maximum(__root);
 893           _M_impl._M_node_count = __x._M_impl._M_node_count;
 894           return __root;
 895         }
 896
 897       _Link_type
 898       _M_copy(const _Rb_tree& __x)
 899       {
 900         _Alloc_node __an(*this);
 901         return _M_copy<__as_lvalue>(__x, __an);
 902       }
 903
 904       void
 905       _M_erase(_Link_type __x);
 906
 907       iterator
 908       _M_lower_bound(_Link_type __x, _Base_ptr __y,
 909                      const _Key& __k);
 910
 911       const_iterator
 912       _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
 913                      const _Key& __k) const;
 914
 915       iterator
 916       _M_upper_bound(_Link_type __x, _Base_ptr __y,
 917                      const _Key& __k);
 918
 919       const_iterator
 920       _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
 921                      const _Key& __k) const;
 922
 923     public:
 924       // allocation/deallocation
 925 #if __cplusplus < 201103L
 926       _Rb_tree() { }
 927 #else
 928       _Rb_tree() = default;
 929 #endif
 930
 931       _Rb_tree(const _Compare& __comp,
 932                const allocator_type& __a = allocator_type())
 933       : _M_impl(__comp, _Node_allocator(__a)) { }
 934
 935       _Rb_tree(const _Rb_tree& __x)
 936       : _M_impl(__x._M_impl)
 937       {
 938         if (__x._M_root() != 0)
 939           _M_root() = _M_copy(__x);
 940       }
 941
 942 #if __cplusplus >= 201103L
 943       _Rb_tree(const allocator_type& __a)
 944       : _M_impl(_Node_allocator(__a))
 945       { }
 946
 947       _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
 948       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
 949       {
 950         if (__x._M_root() != nullptr)
 951           _M_root() = _M_copy(__x);
 952       }
 953
 954       _Rb_tree(_Rb_tree&&) = default;
 955
 956       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
 957       : _Rb_tree(std::move(__x), _Node_allocator(__a))
 958       { }
 959
 960     private:
 961       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
 962       noexcept(is_nothrow_default_constructible<_Compare>::value)
 963       : _M_impl(std::move(__x._M_impl), std::move(__a))
 964       { }
 965
 966       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
 967       : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
 968       {
 969         if (__x._M_root() != nullptr)
 970           _M_move_data(__x, false_type{});
 971       }
 972
 973     public:
 974       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
 975       noexcept( noexcept(
 976         _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
 977                  std::declval<typename _Alloc_traits::is_always_equal>())) )
 978       : _Rb_tree(std::move(__x), std::move(__a),
 979                  typename _Alloc_traits::is_always_equal{})
 980       { }
 981 #endif
 982
 983       ~_Rb_tree() _GLIBCXX_NOEXCEPT
 984       { _M_erase(_M_begin()); }
 985
 986       _Rb_tree&
 987       operator=(const _Rb_tree& __x);
 988
 989       // Accessors.
 990       _Compare
 991       key_comp() const
 992       { return _M_impl._M_key_compare; }
 993
 994       iterator
 995       begin() _GLIBCXX_NOEXCEPT
 996       { return iterator(this->_M_impl._M_header._M_left); }
 997
 998       const_iterator
 999       begin() const _GLIBCXX_NOEXCEPT
1000       { return const_iterator(this->_M_impl._M_header._M_left); }
1001
1002       iterator
1003       end() _GLIBCXX_NOEXCEPT
1004       { return iterator(&this->_M_impl._M_header); }
1005
1006       const_iterator
1007       end() const _GLIBCXX_NOEXCEPT
1008       { return const_iterator(&this->_M_impl._M_header); }
1009
1010       reverse_iterator
1011       rbegin() _GLIBCXX_NOEXCEPT
1012       { return reverse_iterator(end()); }
1013
1014       const_reverse_iterator
1015       rbegin() const _GLIBCXX_NOEXCEPT
1016       { return const_reverse_iterator(end()); }
1017
1018       reverse_iterator
1019       rend() _GLIBCXX_NOEXCEPT
1020       { return reverse_iterator(begin()); }
1021
1022       const_reverse_iterator
1023       rend() const _GLIBCXX_NOEXCEPT
1024       { return const_reverse_iterator(begin()); }
1025
1026       _GLIBCXX_NODISCARD bool
1027       empty() const _GLIBCXX_NOEXCEPT
1028       { return _M_impl._M_node_count == 0; }
1029
1030       size_type
1031       size() const _GLIBCXX_NOEXCEPT
1032       { return _M_impl._M_node_count; }
1033
1034       size_type
1035       max_size() const _GLIBCXX_NOEXCEPT
1036       { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1037
1038       void
1039       swap(_Rb_tree& __t)
1040       _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1041
1042       // Insert/erase.
1043 #if __cplusplus >= 201103L
1044       template<typename _Arg>
1045         pair<iterator, bool>
1046         _M_insert_unique(_Arg&& __x);
1047
1048       template<typename _Arg>
1049         iterator
1050         _M_insert_equal(_Arg&& __x);
1051
1052       template<typename _Arg, typename _NodeGen>
1053         iterator
1054         _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1055
1056       template<typename _Arg>
1057         iterator
1058         _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1059         {
1060           _Alloc_node __an(*this);
1061           return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1062         }
1063
1064       template<typename _Arg, typename _NodeGen>
1065         iterator
1066         _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1067
1068       template<typename _Arg>
1069         iterator
1070         _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1071         {
1072           _Alloc_node __an(*this);
1073           return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1074         }
1075
1076       template<typename... _Args>
1077         pair<iterator, bool>
1078         _M_emplace_unique(_Args&&... __args);
1079
1080       template<typename... _Args>
1081         iterator
1082         _M_emplace_equal(_Args&&... __args);
1083
1084       template<typename... _Args>
1085         iterator
1086         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1087
1088       template<typename... _Args>
1089         iterator
1090         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1091
1092       template<typename _Iter>
1093         using __same_value_type
1094           = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1095
1096       template<typename _InputIterator>
1097         __enable_if_t<__same_value_type<_InputIterator>::value>
1098         _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1099         {
1100           _Alloc_node __an(*this);
1101           for (; __first != __last; ++__first)
1102             _M_insert_unique_(end(), *__first, __an);
1103         }
1104
1105       template<typename _InputIterator>
1106         __enable_if_t<!__same_value_type<_InputIterator>::value>
1107         _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1108         {
1109           for (; __first != __last; ++__first)
1110             _M_emplace_unique(*__first);
1111         }
1112
1113       template<typename _InputIterator>
1114         __enable_if_t<__same_value_type<_InputIterator>::value>
1115         _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1116         {
1117           _Alloc_node __an(*this);
1118           for (; __first != __last; ++__first)
1119             _M_insert_equal_(end(), *__first, __an);
1120         }
1121
1122       template<typename _InputIterator>
1123         __enable_if_t<!__same_value_type<_InputIterator>::value>
1124         _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1125         {
1126           for (; __first != __last; ++__first)
1127             _M_emplace_equal(*__first);
1128         }
1129 #else
1130       pair<iterator, bool>
1131       _M_insert_unique(const value_type& __x);
1132
1133       iterator
1134       _M_insert_equal(const value_type& __x);
1135
1136       template<typename _NodeGen>
1137         iterator
1138         _M_insert_unique_(const_iterator __pos, const value_type& __x,
1139                           _NodeGen&);
1140
1141       iterator
1142       _M_insert_unique_(const_iterator __pos, const value_type& __x)
1143       {
1144         _Alloc_node __an(*this);
1145         return _M_insert_unique_(__pos, __x, __an);
1146       }
1147
1148       template<typename _NodeGen>
1149         iterator
1150         _M_insert_equal_(const_iterator __pos, const value_type& __x,
1151                          _NodeGen&);
1152       iterator
1153       _M_insert_equal_(const_iterator __pos, const value_type& __x)
1154       {
1155         _Alloc_node __an(*this);
1156         return _M_insert_equal_(__pos, __x, __an);
1157       }
1158
1159       template<typename _InputIterator>
1160         void
1161         _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1162         {
1163           _Alloc_node __an(*this);
1164           for (; __first != __last; ++__first)
1165             _M_insert_unique_(end(), *__first, __an);
1166         }
1167
1168       template<typename _InputIterator>
1169         void
1170         _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1171         {
1172           _Alloc_node __an(*this);
1173           for (; __first != __last; ++__first)
1174             _M_insert_equal_(end(), *__first, __an);
1175         }
1176 #endif
1177
1178     private:
1179       void
1180       _M_erase_aux(const_iterator __position);
1181
1182       void
1183       _M_erase_aux(const_iterator __first, const_iterator __last);
1184
1185     public:
1186 #if __cplusplus >= 201103L
1187       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1188       // DR 130. Associative erase should return an iterator.
1189       _GLIBCXX_ABI_TAG_CXX11
1190       iterator
1191       erase(const_iterator __position)
1192       {
1193         __glibcxx_assert(__position != end());
1194         const_iterator __result = __position;
1195         ++__result;
1196         _M_erase_aux(__position);
1197         return __result._M_const_cast();
1198       }
1199
1200       // LWG 2059.
1201       _GLIBCXX_ABI_TAG_CXX11
1202       iterator
1203       erase(iterator __position)
1204       {
1205         __glibcxx_assert(__position != end());
1206         iterator __result = __position;
1207         ++__result;
1208         _M_erase_aux(__position);
1209         return __result;
1210       }
1211 #else
1212       void
1213       erase(iterator __position)
1214       {
1215         __glibcxx_assert(__position != end());
1216         _M_erase_aux(__position);
1217       }
1218
1219       void
1220       erase(const_iterator __position)
1221       {
1222         __glibcxx_assert(__position != end());
1223         _M_erase_aux(__position);
1224       }
1225 #endif
1226
1227       size_type
1228       erase(const key_type& __x);
1229
1230 #if __cplusplus >= 201103L
1231       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1232       // DR 130. Associative erase should return an iterator.
1233       _GLIBCXX_ABI_TAG_CXX11
1234       iterator
1235       erase(const_iterator __first, const_iterator __last)
1236       {
1237         _M_erase_aux(__first, __last);
1238         return __last._M_const_cast();
1239       }
1240 #else
1241       void
1242       erase(iterator __first, iterator __last)
1243       { _M_erase_aux(__first, __last); }
1244
1245       void
1246       erase(const_iterator __first, const_iterator __last)
1247       { _M_erase_aux(__first, __last); }
1248 #endif
1249
1250       void
1251       clear() _GLIBCXX_NOEXCEPT
1252       {
1253         _M_erase(_M_begin());
1254         _M_impl._M_reset();
1255       }
1256
1257       // Set operations.
1258       iterator
1259       find(const key_type& __k);
1260
1261       const_iterator
1262       find(const key_type& __k) const;
1263
1264       size_type
1265       count(const key_type& __k) const;
1266
1267       iterator
1268       lower_bound(const key_type& __k)
1269       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1270
1271       const_iterator
1272       lower_bound(const key_type& __k) const
1273       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1274
1275       iterator
1276       upper_bound(const key_type& __k)
1277       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1278
1279       const_iterator
1280       upper_bound(const key_type& __k) const
1281       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1282
1283       pair<iterator, iterator>
1284       equal_range(const key_type& __k);
1285
1286       pair<const_iterator, const_iterator>
1287       equal_range(const key_type& __k) const;
1288
1289 #if __cplusplus >= 201402L
1290       template<typename _Kt,
1291                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1292         iterator
1293         _M_find_tr(const _Kt& __k)
1294         {
1295           const _Rb_tree* __const_this = this;
1296           return __const_this->_M_find_tr(__k)._M_const_cast();
1297         }
1298
1299       template<typename _Kt,
1300                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1301         const_iterator
1302         _M_find_tr(const _Kt& __k) const
1303         {
1304           auto __j = _M_lower_bound_tr(__k);
1305           if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1306             __j = end();
1307           return __j;
1308         }
1309
1310       template<typename _Kt,
1311                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1312         size_type
1313         _M_count_tr(const _Kt& __k) const
1314         {
1315           auto __p = _M_equal_range_tr(__k);
1316           return std::distance(__p.first, __p.second);
1317         }
1318
1319       template<typename _Kt,
1320                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1321         iterator
1322         _M_lower_bound_tr(const _Kt& __k)
1323         {
1324           const _Rb_tree* __const_this = this;
1325           return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1326         }
1327
1328       template<typename _Kt,
1329                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1330         const_iterator
1331         _M_lower_bound_tr(const _Kt& __k) const
1332         {
1333           auto __x = _M_begin();
1334           auto __y = _M_end();
1335           while (__x != 0)
1336             if (!_M_impl._M_key_compare(_S_key(__x), __k))
1337               {
1338                 __y = __x;
1339                 __x = _S_left(__x);
1340               }
1341             else
1342               __x = _S_right(__x);
1343           return const_iterator(__y);
1344         }
1345
1346       template<typename _Kt,
1347                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1348         iterator
1349         _M_upper_bound_tr(const _Kt& __k)
1350         {
1351           const _Rb_tree* __const_this = this;
1352           return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1353         }
1354
1355       template<typename _Kt,
1356                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1357         const_iterator
1358         _M_upper_bound_tr(const _Kt& __k) const
1359         {
1360           auto __x = _M_begin();
1361           auto __y = _M_end();
1362           while (__x != 0)
1363             if (_M_impl._M_key_compare(__k, _S_key(__x)))
1364               {
1365                 __y = __x;
1366                 __x = _S_left(__x);
1367               }
1368             else
1369               __x = _S_right(__x);
1370           return const_iterator(__y);
1371         }
1372
1373       template<typename _Kt,
1374                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1375         pair<iterator, iterator>
1376         _M_equal_range_tr(const _Kt& __k)
1377         {
1378           const _Rb_tree* __const_this = this;
1379           auto __ret = __const_this->_M_equal_range_tr(__k);
1380           return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1381         }
1382
1383       template<typename _Kt,
1384                typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1385         pair<const_iterator, const_iterator>
1386         _M_equal_range_tr(const _Kt& __k) const
1387         {
1388           auto __low = _M_lower_bound_tr(__k);
1389           auto __high = __low;
1390           auto& __cmp = _M_impl._M_key_compare;
1391           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1392             ++__high;
1393           return { __low, __high };
1394         }
1395 #endif
1396
1397       // Debugging.
1398       bool
1399       __rb_verify() const;
1400
1401 #if __cplusplus >= 201103L
1402       _Rb_tree&
1403       operator=(_Rb_tree&&)
1404       noexcept(_Alloc_traits::_S_nothrow_move()
1405                && is_nothrow_move_assignable<_Compare>::value);
1406
1407       template<typename _Iterator>
1408         void
1409         _M_assign_unique(_Iterator, _Iterator);
1410
1411       template<typename _Iterator>
1412         void
1413         _M_assign_equal(_Iterator, _Iterator);
1414
1415     private:
1416       // Move elements from container with equal allocator.
1417       void
1418       _M_move_data(_Rb_tree& __x, true_type)
1419       { _M_impl._M_move_data(__x._M_impl); }
1420
1421       // Move elements from container with possibly non-equal allocator,
1422       // which might result in a copy not a move.
1423       void
1424       _M_move_data(_Rb_tree&, false_type);
1425
1426       // Move assignment from container with equal allocator.
1427       void
1428       _M_move_assign(_Rb_tree&, true_type);
1429
1430       // Move assignment from container with possibly non-equal allocator,
1431       // which might result in a copy not a move.
1432       void
1433       _M_move_assign(_Rb_tree&, false_type);
1434 #endif
1435
1436 #if __glibcxx_node_extract // >= C++17
1437     public:
1438       /// Re-insert an extracted node.
1439       insert_return_type
1440       _M_reinsert_node_unique(node_type&& __nh)
1441       {
1442         insert_return_type __ret;
1443         if (__nh.empty())
1444           __ret.position = end();
1445         else
1446           {
1447             __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1448
1449             auto __res = _M_get_insert_unique_pos(__nh._M_key());
1450             if (__res.second)
1451               {
1452                 __ret.position
1453                   = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1454                 __nh.release();
1455                 __ret.inserted = true;
1456               }
1457             else
1458               {
1459                 __ret.node = std::move(__nh);
1460                 __ret.position = iterator(__res.first);
1461                 __ret.inserted = false;
1462               }
1463           }
1464         return __ret;
1465       }
1466
1467       /// Re-insert an extracted node.
1468       iterator
1469       _M_reinsert_node_equal(node_type&& __nh)
1470       {
1471         iterator __ret;
1472         if (__nh.empty())
1473           __ret = end();
1474         else
1475           {
1476             __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1477             auto __res = _M_get_insert_equal_pos(__nh._M_key());
1478             if (__res.second)
1479               __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1480             else
1481               __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1482             __nh.release();
1483           }
1484         return __ret;
1485       }
1486
1487       /// Re-insert an extracted node.
1488       iterator
1489       _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1490       {
1491         iterator __ret;
1492         if (__nh.empty())
1493           __ret = end();
1494         else
1495           {
1496             __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1497             auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1498             if (__res.second)
1499               {
1500                 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1501                 __nh.release();
1502               }
1503             else
1504               __ret = iterator(__res.first);
1505           }
1506         return __ret;
1507       }
1508
1509       /// Re-insert an extracted node.
1510       iterator
1511       _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1512       {
1513         iterator __ret;
1514         if (__nh.empty())
1515           __ret = end();
1516         else
1517           {
1518             __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1519             auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1520             if (__res.second)
1521               __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1522             else
1523               __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1524             __nh.release();
1525           }
1526         return __ret;
1527       }
1528
1529       /// Extract a node.
1530       node_type
1531       extract(const_iterator __pos)
1532       {
1533         auto __ptr = _Rb_tree_rebalance_for_erase(
1534             __pos._M_const_cast()._M_node, _M_impl._M_header);
1535         --_M_impl._M_node_count;
1536         return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
1537       }
1538
1539       /// Extract a node.
1540       node_type
1541       extract(const key_type& __k)
1542       {
1543         node_type __nh;
1544         auto __pos = find(__k);
1545         if (__pos != end())
1546           __nh = extract(const_iterator(__pos));
1547         return __nh;
1548       }
1549
1550       template<typename _Compare2>
1551         using _Compatible_tree
1552           = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1553
1554       template<typename, typename>
1555         friend struct _Rb_tree_merge_helper;
1556
1557       /// Merge from a compatible container into one with unique keys.
1558       template<typename _Compare2>
1559         void
1560         _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1561         {
1562           using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1563           for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1564             {
1565               auto __pos = __i++;
1566               auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1567               if (__res.second)
1568                 {
1569                   auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1570                   auto __ptr = _Rb_tree_rebalance_for_erase(
1571                       __pos._M_node, __src_impl._M_header);
1572                   --__src_impl._M_node_count;
1573                   _M_insert_node(__res.first, __res.second,
1574                                  static_cast<_Link_type>(__ptr));
1575                 }
1576             }
1577         }
1578
1579       /// Merge from a compatible container into one with equivalent keys.
1580       template<typename _Compare2>
1581         void
1582         _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1583         {
1584           using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1585           for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1586             {
1587               auto __pos = __i++;
1588               auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1589               if (__res.second)
1590                 {
1591                   auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1592                   auto __ptr = _Rb_tree_rebalance_for_erase(
1593                       __pos._M_node, __src_impl._M_header);
1594                   --__src_impl._M_node_count;
1595                   _M_insert_node(__res.first, __res.second,
1596                                  static_cast<_Link_type>(__ptr));
1597                 }
1598             }
1599         }
1600 #endif // C++17 node_extract
1601
1602       friend bool
1603       operator==(const _Rb_tree& __x, const _Rb_tree& __y)
1604       {
1605         return __x.size() == __y.size()
1606           && std::equal(__x.begin(), __x.end(), __y.begin());
1607       }
1608
1609 #if __cpp_lib_three_way_comparison
1610       friend auto
1611       operator<=>(const _Rb_tree& __x, const _Rb_tree& __y)
1612       {
1613         if constexpr (requires { typename __detail::__synth3way_t<_Val>; })
1614           return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1615                                                         __y.begin(), __y.end(),
1616                                                         __detail::__synth3way);
1617       }
1618 #else
1619       friend bool
1620       operator<(const _Rb_tree& __x, const _Rb_tree& __y)
1621       {
1622         return std::lexicographical_compare(__x.begin(), __x.end(),
1623                                             __y.begin(), __y.end());
1624       }
1625 #endif
1626
1627     private:
1628 #if __cplusplus >= 201103L
1629       // An RAII _Node handle
1630       struct _Auto_node
1631       {
1632         template<typename... _Args>
1633           _Auto_node(_Rb_tree& __t, _Args&&... __args)
1634           : _M_t(__t),
1635             _M_node(__t._M_create_node(std::forward<_Args>(__args)...))
1636           { }
1637
1638         ~_Auto_node()
1639         {
1640           if (_M_node)
1641             _M_t._M_drop_node(_M_node);
1642         }
1643
1644         _Auto_node(_Auto_node&& __n)
1645         : _M_t(__n._M_t), _M_node(__n._M_node)
1646         { __n._M_node = nullptr; }
1647
1648         const _Key&
1649         _M_key() const
1650         { return _S_key(_M_node); }
1651
1652         iterator
1653         _M_insert(pair<_Base_ptr, _Base_ptr> __p)
1654         {
1655           auto __it = _M_t._M_insert_node(__p.first, __p.second, _M_node);
1656           _M_node = nullptr;
1657           return __it;
1658         }
1659
1660         iterator
1661         _M_insert_equal_lower()
1662         {
1663           auto __it = _M_t._M_insert_equal_lower_node(_M_node);
1664           _M_node = nullptr;
1665           return __it;
1666         }
1667
1668         _Rb_tree& _M_t;
1669         _Link_type _M_node;
1670       };
1671 #endif // C++11
1672     };
1673
1674   template<typename _Key, typename _Val, typename _KeyOfValue,
1675            typename _Compare, typename _Alloc>
1676     inline void
1677     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1678          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1679     { __x.swap(__y); }
1680
1681 #if __cplusplus >= 201103L
1682   template<typename _Key, typename _Val, typename _KeyOfValue,
1683            typename _Compare, typename _Alloc>
1684     void
1685     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1686     _M_move_data(_Rb_tree& __x, false_type)
1687     {
1688       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1689         _M_move_data(__x, true_type());
1690       else
1691         {
1692           constexpr bool __move = !__move_if_noexcept_cond<value_type>::value;
1693           _Alloc_node __an(*this);
1694           _M_root() = _M_copy<__move>(__x, __an);
1695           if _GLIBCXX17_CONSTEXPR (__move)
1696             __x.clear();
1697         }
1698     }
1699
1700   template<typename _Key, typename _Val, typename _KeyOfValue,
1701            typename _Compare, typename _Alloc>
1702     inline void
1703     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1704     _M_move_assign(_Rb_tree& __x, true_type)
1705     {
1706       clear();
1707       if (__x._M_root() != nullptr)
1708         _M_move_data(__x, true_type());
1709       std::__alloc_on_move(_M_get_Node_allocator(),
1710                            __x._M_get_Node_allocator());
1711     }
1712
1713   template<typename _Key, typename _Val, typename _KeyOfValue,
1714            typename _Compare, typename _Alloc>
1715     void
1716     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1717     _M_move_assign(_Rb_tree& __x, false_type)
1718     {
1719       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1720         return _M_move_assign(__x, true_type{});
1721
1722       // Try to move each node reusing existing nodes and copying __x nodes
1723       // structure.
1724       _Reuse_or_alloc_node __roan(*this);
1725       _M_impl._M_reset();
1726       if (__x._M_root() != nullptr)
1727         {
1728           _M_root() = _M_copy<__as_rvalue>(__x, __roan);
1729           __x.clear();
1730         }
1731     }
1732
1733   template<typename _Key, typename _Val, typename _KeyOfValue,
1734            typename _Compare, typename _Alloc>
1735     inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1736     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1737     operator=(_Rb_tree&& __x)
1738     noexcept(_Alloc_traits::_S_nothrow_move()
1739              && is_nothrow_move_assignable<_Compare>::value)
1740     {
1741       _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1742       _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
1743       return *this;
1744     }
1745
1746   template<typename _Key, typename _Val, typename _KeyOfValue,
1747            typename _Compare, typename _Alloc>
1748     template<typename _Iterator>
1749       void
1750       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1751       _M_assign_unique(_Iterator __first, _Iterator __last)
1752       {
1753         _Reuse_or_alloc_node __roan(*this);
1754         _M_impl._M_reset();
1755         for (; __first != __last; ++__first)
1756           _M_insert_unique_(end(), *__first, __roan);
1757       }
1758
1759   template<typename _Key, typename _Val, typename _KeyOfValue,
1760            typename _Compare, typename _Alloc>
1761     template<typename _Iterator>
1762       void
1763       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1764       _M_assign_equal(_Iterator __first, _Iterator __last)
1765       {
1766         _Reuse_or_alloc_node __roan(*this);
1767         _M_impl._M_reset();
1768         for (; __first != __last; ++__first)
1769           _M_insert_equal_(end(), *__first, __roan);
1770       }
1771 #endif
1772
1773   template<typename _Key, typename _Val, typename _KeyOfValue,
1774            typename _Compare, typename _Alloc>
1775     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1776     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1777     operator=(const _Rb_tree& __x)
1778     {
1779       if (this != std::__addressof(__x))
1780         {
1781           // Note that _Key may be a constant type.
1782 #if __cplusplus >= 201103L
1783           if (_Alloc_traits::_S_propagate_on_copy_assign())
1784             {
1785               auto& __this_alloc = this->_M_get_Node_allocator();
1786               auto& __that_alloc = __x._M_get_Node_allocator();
1787               if (!_Alloc_traits::_S_always_equal()
1788                   && __this_alloc != __that_alloc)
1789                 {
1790                   // Replacement allocator cannot free existing storage, we need
1791                   // to erase nodes first.
1792                   clear();
1793                   std::__alloc_on_copy(__this_alloc, __that_alloc);
1794                 }
1795             }
1796 #endif
1797
1798           _Reuse_or_alloc_node __roan(*this);
1799           _M_impl._M_reset();
1800           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1801           if (__x._M_root() != 0)
1802             _M_root() = _M_copy<__as_lvalue>(__x, __roan);
1803         }
1804
1805       return *this;
1806     }
1807
1808   template<typename _Key, typename _Val, typename _KeyOfValue,
1809            typename _Compare, typename _Alloc>
1810 #if __cplusplus >= 201103L
1811     template<typename _Arg, typename _NodeGen>
1812 #else
1813     template<typename _NodeGen>
1814 #endif
1815       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1816       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1817       _M_insert_(_Base_ptr __x, _Base_ptr __p,
1818 #if __cplusplus >= 201103L
1819                  _Arg&& __v,
1820 #else
1821                  const _Val& __v,
1822 #endif
1823                  _NodeGen& __node_gen)
1824       {
1825         bool __insert_left = (__x != 0 || __p == _M_end()
1826                               || _M_impl._M_key_compare(_KeyOfValue()(__v),
1827                                                         _S_key(__p)));
1828
1829         _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1830
1831         _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1832                                       this->_M_impl._M_header);
1833         ++_M_impl._M_node_count;
1834         return iterator(__z);
1835       }
1836
1837   template<typename _Key, typename _Val, typename _KeyOfValue,
1838            typename _Compare, typename _Alloc>
1839 #if __cplusplus >= 201103L
1840     template<typename _Arg>
1841 #endif
1842     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1843     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1844 #if __cplusplus >= 201103L
1845     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1846 #else
1847     _M_insert_lower(_Base_ptr __p, const _Val& __v)
1848 #endif
1849     {
1850       bool __insert_left = (__p == _M_end()
1851                             || !_M_impl._M_key_compare(_S_key(__p),
1852                                                        _KeyOfValue()(__v)));
1853
1854       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1855
1856       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1857                                     this->_M_impl._M_header);
1858       ++_M_impl._M_node_count;
1859       return iterator(__z);
1860     }
1861
1862   template<typename _Key, typename _Val, typename _KeyOfValue,
1863            typename _Compare, typename _Alloc>
1864 #if __cplusplus >= 201103L
1865     template<typename _Arg>
1866 #endif
1867     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1868     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1869 #if __cplusplus >= 201103L
1870     _M_insert_equal_lower(_Arg&& __v)
1871 #else
1872     _M_insert_equal_lower(const _Val& __v)
1873 #endif
1874     {
1875       _Link_type __x = _M_begin();
1876       _Base_ptr __y = _M_end();
1877       while (__x != 0)
1878         {
1879           __y = __x;
1880           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1881                 _S_left(__x) : _S_right(__x);
1882         }
1883       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1884     }
1885
1886   template<typename _Key, typename _Val, typename _KoV,
1887            typename _Compare, typename _Alloc>
1888     template<bool _MoveValues, typename _NodeGen>
1889       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1890       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1891       _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1892       {
1893         // Structural copy. __x and __p must be non-null.
1894         _Link_type __top = _M_clone_node<_MoveValues>(__x, __node_gen);
1895         __top->_M_parent = __p;
1896
1897         __try
1898           {
1899             if (__x->_M_right)
1900               __top->_M_right =
1901                 _M_copy<_MoveValues>(_S_right(__x), __top, __node_gen);
1902             __p = __top;
1903             __x = _S_left(__x);
1904
1905             while (__x != 0)
1906               {
1907                 _Link_type __y = _M_clone_node<_MoveValues>(__x, __node_gen);
1908                 __p->_M_left = __y;
1909                 __y->_M_parent = __p;
1910                 if (__x->_M_right)
1911                   __y->_M_right = _M_copy<_MoveValues>(_S_right(__x),
1912                                                        __y, __node_gen);
1913                 __p = __y;
1914                 __x = _S_left(__x);
1915               }
1916           }
1917         __catch(...)
1918           {
1919             _M_erase(__top);
1920             __throw_exception_again;
1921           }
1922         return __top;
1923       }
1924
1925   template<typename _Key, typename _Val, typename _KeyOfValue,
1926            typename _Compare, typename _Alloc>
1927     void
1928     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1929     _M_erase(_Link_type __x)
1930     {
1931       // Erase without rebalancing.
1932       while (__x != 0)
1933         {
1934           _M_erase(_S_right(__x));
1935           _Link_type __y = _S_left(__x);
1936           _M_drop_node(__x);
1937           __x = __y;
1938         }
1939     }
1940
1941   template<typename _Key, typename _Val, typename _KeyOfValue,
1942            typename _Compare, typename _Alloc>
1943     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1944                       _Compare, _Alloc>::iterator
1945     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1946     _M_lower_bound(_Link_type __x, _Base_ptr __y,
1947                    const _Key& __k)
1948     {
1949       while (__x != 0)
1950         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1951           __y = __x, __x = _S_left(__x);
1952         else
1953           __x = _S_right(__x);
1954       return iterator(__y);
1955     }
1956
1957   template<typename _Key, typename _Val, typename _KeyOfValue,
1958            typename _Compare, typename _Alloc>
1959     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1960                       _Compare, _Alloc>::const_iterator
1961     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1962     _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1963                    const _Key& __k) const
1964     {
1965       while (__x != 0)
1966         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1967           __y = __x, __x = _S_left(__x);
1968         else
1969           __x = _S_right(__x);
1970       return const_iterator(__y);
1971     }
1972
1973   template<typename _Key, typename _Val, typename _KeyOfValue,
1974            typename _Compare, typename _Alloc>
1975     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1976                       _Compare, _Alloc>::iterator
1977     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1978     _M_upper_bound(_Link_type __x, _Base_ptr __y,
1979                    const _Key& __k)
1980     {
1981       while (__x != 0)
1982         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1983           __y = __x, __x = _S_left(__x);
1984         else
1985           __x = _S_right(__x);
1986       return iterator(__y);
1987     }
1988
1989   template<typename _Key, typename _Val, typename _KeyOfValue,
1990            typename _Compare, typename _Alloc>
1991     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1992                       _Compare, _Alloc>::const_iterator
1993     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1994     _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1995                    const _Key& __k) const
1996     {
1997       while (__x != 0)
1998         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1999           __y = __x, __x = _S_left(__x);
2000         else
2001           __x = _S_right(__x);
2002       return const_iterator(__y);
2003     }
2004
2005   template<typename _Key, typename _Val, typename _KeyOfValue,
2006            typename _Compare, typename _Alloc>
2007     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2008                            _Compare, _Alloc>::iterator,
2009          typename _Rb_tree<_Key, _Val, _KeyOfValue,
2010                            _Compare, _Alloc>::iterator>
2011     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2012     equal_range(const _Key& __k)
2013     {
2014       _Link_type __x = _M_begin();
2015       _Base_ptr __y = _M_end();
2016       while (__x != 0)
2017         {
2018           if (_M_impl._M_key_compare(_S_key(__x), __k))
2019             __x = _S_right(__x);
2020           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2021             __y = __x, __x = _S_left(__x);
2022           else
2023             {
2024               _Link_type __xu(__x);
2025               _Base_ptr __yu(__y);
2026               __y = __x, __x = _S_left(__x);
2027               __xu = _S_right(__xu);
2028               return pair<iterator,
2029                           iterator>(_M_lower_bound(__x, __y, __k),
2030                                     _M_upper_bound(__xu, __yu, __k));
2031             }
2032         }
2033       return pair<iterator, iterator>(iterator(__y),
2034                                       iterator(__y));
2035     }
2036
2037   template<typename _Key, typename _Val, typename _KeyOfValue,
2038            typename _Compare, typename _Alloc>
2039     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2040                            _Compare, _Alloc>::const_iterator,
2041          typename _Rb_tree<_Key, _Val, _KeyOfValue,
2042                            _Compare, _Alloc>::const_iterator>
2043     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2044     equal_range(const _Key& __k) const
2045     {
2046       _Const_Link_type __x = _M_begin();
2047       _Const_Base_ptr __y = _M_end();
2048       while (__x != 0)
2049         {
2050           if (_M_impl._M_key_compare(_S_key(__x), __k))
2051             __x = _S_right(__x);
2052           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2053             __y = __x, __x = _S_left(__x);
2054           else
2055             {
2056               _Const_Link_type __xu(__x);
2057               _Const_Base_ptr __yu(__y);
2058               __y = __x, __x = _S_left(__x);
2059               __xu = _S_right(__xu);
2060               return pair<const_iterator,
2061                           const_iterator>(_M_lower_bound(__x, __y, __k),
2062                                           _M_upper_bound(__xu, __yu, __k));
2063             }
2064         }
2065       return pair<const_iterator, const_iterator>(const_iterator(__y),
2066                                                   const_iterator(__y));
2067     }
2068
2069   template<typename _Key, typename _Val, typename _KeyOfValue,
2070            typename _Compare, typename _Alloc>
2071     void
2072     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2073     swap(_Rb_tree& __t)
2074     _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2075     {
2076       if (_M_root() == 0)
2077         {
2078           if (__t._M_root() != 0)
2079             _M_impl._M_move_data(__t._M_impl);
2080         }
2081       else if (__t._M_root() == 0)
2082         __t._M_impl._M_move_data(_M_impl);
2083       else
2084         {
2085           std::swap(_M_root(),__t._M_root());
2086           std::swap(_M_leftmost(),__t._M_leftmost());
2087           std::swap(_M_rightmost(),__t._M_rightmost());
2088
2089           _M_root()->_M_parent = _M_end();
2090           __t._M_root()->_M_parent = __t._M_end();
2091           std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2092         }
2093       // No need to swap header's color as it does not change.
2094       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2095
2096       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2097                                 __t._M_get_Node_allocator());
2098     }
2099
2100   template<typename _Key, typename _Val, typename _KeyOfValue,
2101            typename _Compare, typename _Alloc>
2102     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2103                            _Compare, _Alloc>::_Base_ptr,
2104          typename _Rb_tree<_Key, _Val, _KeyOfValue,
2105                            _Compare, _Alloc>::_Base_ptr>
2106     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2107     _M_get_insert_unique_pos(const key_type& __k)
2108     {
2109       typedef pair<_Base_ptr, _Base_ptr> _Res;
2110       _Link_type __x = _M_begin();
2111       _Base_ptr __y = _M_end();
2112       bool __comp = true;
2113       while (__x != 0)
2114         {
2115           __y = __x;
2116           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2117           __x = __comp ? _S_left(__x) : _S_right(__x);
2118         }
2119       iterator __j = iterator(__y);
2120       if (__comp)
2121         {
2122           if (__j == begin())
2123             return _Res(__x, __y);
2124           else
2125             --__j;
2126         }
2127       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2128         return _Res(__x, __y);
2129       return _Res(__j._M_node, 0);
2130     }
2131
2132   template<typename _Key, typename _Val, typename _KeyOfValue,
2133            typename _Compare, typename _Alloc>
2134     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2135                            _Compare, _Alloc>::_Base_ptr,
2136          typename _Rb_tree<_Key, _Val, _KeyOfValue,
2137                            _Compare, _Alloc>::_Base_ptr>
2138     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2139     _M_get_insert_equal_pos(const key_type& __k)
2140     {
2141       typedef pair<_Base_ptr, _Base_ptr> _Res;
2142       _Link_type __x = _M_begin();
2143       _Base_ptr __y = _M_end();
2144       while (__x != 0)
2145         {
2146           __y = __x;
2147           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2148                 _S_left(__x) : _S_right(__x);
2149         }
2150       return _Res(__x, __y);
2151     }
2152
2153   template<typename _Key, typename _Val, typename _KeyOfValue,
2154            typename _Compare, typename _Alloc>
2155 #if __cplusplus >= 201103L
2156     template<typename _Arg>
2157 #endif
2158     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2159                            _Compare, _Alloc>::iterator, bool>
2160     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2161 #if __cplusplus >= 201103L
2162     _M_insert_unique(_Arg&& __v)
2163 #else
2164     _M_insert_unique(const _Val& __v)
2165 #endif
2166     {
2167       typedef pair<iterator, bool> _Res;
2168       pair<_Base_ptr, _Base_ptr> __res
2169         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2170
2171       if (__res.second)
2172         {
2173           _Alloc_node __an(*this);
2174           return _Res(_M_insert_(__res.first, __res.second,
2175                                  _GLIBCXX_FORWARD(_Arg, __v), __an),
2176                       true);
2177         }
2178
2179       return _Res(iterator(__res.first), false);
2180     }
2181
2182   template<typename _Key, typename _Val, typename _KeyOfValue,
2183            typename _Compare, typename _Alloc>
2184 #if __cplusplus >= 201103L
2185     template<typename _Arg>
2186 #endif
2187     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2188     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2189 #if __cplusplus >= 201103L
2190     _M_insert_equal(_Arg&& __v)
2191 #else
2192     _M_insert_equal(const _Val& __v)
2193 #endif
2194     {
2195       pair<_Base_ptr, _Base_ptr> __res
2196         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2197       _Alloc_node __an(*this);
2198       return _M_insert_(__res.first, __res.second,
2199                         _GLIBCXX_FORWARD(_Arg, __v), __an);
2200     }
2201
2202   template<typename _Key, typename _Val, typename _KeyOfValue,
2203            typename _Compare, typename _Alloc>
2204     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2205                            _Compare, _Alloc>::_Base_ptr,
2206          typename _Rb_tree<_Key, _Val, _KeyOfValue,
2207                            _Compare, _Alloc>::_Base_ptr>
2208     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2209     _M_get_insert_hint_unique_pos(const_iterator __position,
2210                                   const key_type& __k)
2211     {
2212       iterator __pos = __position._M_const_cast();
2213       typedef pair<_Base_ptr, _Base_ptr> _Res;
2214
2215       // end()
2216       if (__pos._M_node == _M_end())
2217         {
2218           if (size() > 0
2219               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2220             return _Res(0, _M_rightmost());
2221           else
2222             return _M_get_insert_unique_pos(__k);
2223         }
2224       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2225         {
2226           // First, try before...
2227           iterator __before = __pos;
2228           if (__pos._M_node == _M_leftmost()) // begin()
2229             return _Res(_M_leftmost(), _M_leftmost());
2230           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2231             {
2232               if (_S_right(__before._M_node) == 0)
2233                 return _Res(0, __before._M_node);
2234               else
2235                 return _Res(__pos._M_node, __pos._M_node);
2236             }
2237           else
2238             return _M_get_insert_unique_pos(__k);
2239         }
2240       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2241         {
2242           // ... then try after.
2243           iterator __after = __pos;
2244           if (__pos._M_node == _M_rightmost())
2245             return _Res(0, _M_rightmost());
2246           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2247             {
2248               if (_S_right(__pos._M_node) == 0)
2249                 return _Res(0, __pos._M_node);
2250               else
2251                 return _Res(__after._M_node, __after._M_node);
2252             }
2253           else
2254             return _M_get_insert_unique_pos(__k);
2255         }
2256       else
2257         // Equivalent keys.
2258         return _Res(__pos._M_node, 0);
2259     }
2260
2261   template<typename _Key, typename _Val, typename _KeyOfValue,
2262            typename _Compare, typename _Alloc>
2263 #if __cplusplus >= 201103L
2264     template<typename _Arg, typename _NodeGen>
2265 #else
2266     template<typename _NodeGen>
2267 #endif
2268       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2269       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2270       _M_insert_unique_(const_iterator __position,
2271 #if __cplusplus >= 201103L
2272                         _Arg&& __v,
2273 #else
2274                         const _Val& __v,
2275 #endif
2276                         _NodeGen& __node_gen)
2277     {
2278       pair<_Base_ptr, _Base_ptr> __res
2279         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2280
2281       if (__res.second)
2282         return _M_insert_(__res.first, __res.second,
2283                           _GLIBCXX_FORWARD(_Arg, __v),
2284                           __node_gen);
2285       return iterator(__res.first);
2286     }
2287
2288   template<typename _Key, typename _Val, typename _KeyOfValue,
2289            typename _Compare, typename _Alloc>
2290     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2291                            _Compare, _Alloc>::_Base_ptr,
2292          typename _Rb_tree<_Key, _Val, _KeyOfValue,
2293                            _Compare, _Alloc>::_Base_ptr>
2294     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2295     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2296     {
2297       iterator __pos = __position._M_const_cast();
2298       typedef pair<_Base_ptr, _Base_ptr> _Res;
2299
2300       // end()
2301       if (__pos._M_node == _M_end())
2302         {
2303           if (size() > 0
2304               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2305             return _Res(0, _M_rightmost());
2306           else
2307             return _M_get_insert_equal_pos(__k);
2308         }
2309       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2310         {
2311           // First, try before...
2312           iterator __before = __pos;
2313           if (__pos._M_node == _M_leftmost()) // begin()
2314             return _Res(_M_leftmost(), _M_leftmost());
2315           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2316             {
2317               if (_S_right(__before._M_node) == 0)
2318                 return _Res(0, __before._M_node);
2319               else
2320                 return _Res(__pos._M_node, __pos._M_node);
2321             }
2322           else
2323             return _M_get_insert_equal_pos(__k);
2324         }
2325       else
2326         {
2327           // ... then try after.
2328           iterator __after = __pos;
2329           if (__pos._M_node == _M_rightmost())
2330             return _Res(0, _M_rightmost());
2331           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2332             {
2333               if (_S_right(__pos._M_node) == 0)
2334                 return _Res(0, __pos._M_node);
2335               else
2336                 return _Res(__after._M_node, __after._M_node);
2337             }
2338           else
2339             return _Res(0, 0);
2340         }
2341     }
2342
2343   template<typename _Key, typename _Val, typename _KeyOfValue,
2344            typename _Compare, typename _Alloc>
2345 #if __cplusplus >= 201103L
2346     template<typename _Arg, typename _NodeGen>
2347 #else
2348     template<typename _NodeGen>
2349 #endif
2350       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2351       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2352       _M_insert_equal_(const_iterator __position,
2353 #if __cplusplus >= 201103L
2354                        _Arg&& __v,
2355 #else
2356                        const _Val& __v,
2357 #endif
2358                        _NodeGen& __node_gen)
2359       {
2360         pair<_Base_ptr, _Base_ptr> __res
2361           = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2362
2363         if (__res.second)
2364           return _M_insert_(__res.first, __res.second,
2365                             _GLIBCXX_FORWARD(_Arg, __v),
2366                             __node_gen);
2367
2368         return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2369       }
2370
2371 #if __cplusplus >= 201103L
2372   template<typename _Key, typename _Val, typename _KeyOfValue,
2373            typename _Compare, typename _Alloc>
2374     auto
2375     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2376     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2377     -> iterator
2378     {
2379       bool __insert_left = (__x != 0 || __p == _M_end()
2380                             || _M_impl._M_key_compare(_S_key(__z),
2381                                                       _S_key(__p)));
2382
2383       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2384                                     this->_M_impl._M_header);
2385       ++_M_impl._M_node_count;
2386       return iterator(__z);
2387     }
2388
2389   template<typename _Key, typename _Val, typename _KeyOfValue,
2390            typename _Compare, typename _Alloc>
2391     auto
2392     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2393     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2394     -> iterator
2395     {
2396       bool __insert_left = (__p == _M_end()
2397                             || !_M_impl._M_key_compare(_S_key(__p),
2398                                                        _S_key(__z)));
2399
2400       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2401                                     this->_M_impl._M_header);
2402       ++_M_impl._M_node_count;
2403       return iterator(__z);
2404     }
2405
2406   template<typename _Key, typename _Val, typename _KeyOfValue,
2407            typename _Compare, typename _Alloc>
2408     auto
2409     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2410     _M_insert_equal_lower_node(_Link_type __z)
2411     -> iterator
2412     {
2413       _Link_type __x = _M_begin();
2414       _Base_ptr __y = _M_end();
2415       while (__x != 0)
2416         {
2417           __y = __x;
2418           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2419                 _S_left(__x) : _S_right(__x);
2420         }
2421       return _M_insert_lower_node(__y, __z);
2422     }
2423
2424   template<typename _Key, typename _Val, typename _KeyOfValue,
2425            typename _Compare, typename _Alloc>
2426     template<typename... _Args>
2427       auto
2428       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2429       _M_emplace_unique(_Args&&... __args)
2430       -> pair<iterator, bool>
2431       {
2432         _Auto_node __z(*this, std::forward<_Args>(__args)...);
2433         auto __res = _M_get_insert_unique_pos(__z._M_key());
2434         if (__res.second)
2435           return {__z._M_insert(__res), true};
2436         return {iterator(__res.first), false};
2437       }
2438
2439   template<typename _Key, typename _Val, typename _KeyOfValue,
2440            typename _Compare, typename _Alloc>
2441     template<typename... _Args>
2442       auto
2443       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2444       _M_emplace_equal(_Args&&... __args)
2445       -> iterator
2446       {
2447         _Auto_node __z(*this, std::forward<_Args>(__args)...);
2448         auto __res = _M_get_insert_equal_pos(__z._M_key());
2449         return __z._M_insert(__res);
2450       }
2451
2452   template<typename _Key, typename _Val, typename _KeyOfValue,
2453            typename _Compare, typename _Alloc>
2454     template<typename... _Args>
2455       auto
2456       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2457       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2458       -> iterator
2459       {
2460         _Auto_node __z(*this, std::forward<_Args>(__args)...);
2461         auto __res = _M_get_insert_hint_unique_pos(__pos, __z._M_key());
2462         if (__res.second)
2463           return __z._M_insert(__res);
2464         return iterator(__res.first);
2465       }
2466
2467   template<typename _Key, typename _Val, typename _KeyOfValue,
2468            typename _Compare, typename _Alloc>
2469     template<typename... _Args>
2470       auto
2471       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2472       _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2473       -> iterator
2474       {
2475         _Auto_node __z(*this, std::forward<_Args>(__args)...);
2476         auto __res = _M_get_insert_hint_equal_pos(__pos, __z._M_key());
2477         if (__res.second)
2478           return __z._M_insert(__res);
2479         return __z._M_insert_equal_lower();
2480       }
2481 #endif
2482
2483
2484   template<typename _Key, typename _Val, typename _KeyOfValue,
2485            typename _Compare, typename _Alloc>
2486     void
2487     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2488     _M_erase_aux(const_iterator __position)
2489     {
2490       _Link_type __y =
2491         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2492                                 (const_cast<_Base_ptr>(__position._M_node),
2493                                  this->_M_impl._M_header));
2494       _M_drop_node(__y);
2495       --_M_impl._M_node_count;
2496     }
2497
2498   template<typename _Key, typename _Val, typename _KeyOfValue,
2499            typename _Compare, typename _Alloc>
2500     void
2501     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2502     _M_erase_aux(const_iterator __first, const_iterator __last)
2503     {
2504       if (__first == begin() && __last == end())
2505         clear();
2506       else
2507         while (__first != __last)
2508           _M_erase_aux(__first++);
2509     }
2510
2511   template<typename _Key, typename _Val, typename _KeyOfValue,
2512            typename _Compare, typename _Alloc>
2513     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2514     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2515     erase(const _Key& __x)
2516     {
2517       pair<iterator, iterator> __p = equal_range(__x);
2518       const size_type __old_size = size();
2519       _M_erase_aux(__p.first, __p.second);
2520       return __old_size - size();
2521     }
2522
2523   template<typename _Key, typename _Val, typename _KeyOfValue,
2524            typename _Compare, typename _Alloc>
2525     typename _Rb_tree<_Key, _Val, _KeyOfValue,
2526                       _Compare, _Alloc>::iterator
2527     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2528     find(const _Key& __k)
2529     {
2530       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2531       return (__j == end()
2532               || _M_impl._M_key_compare(__k,
2533                                         _S_key(__j._M_node))) ? end() : __j;
2534     }
2535
2536   template<typename _Key, typename _Val, typename _KeyOfValue,
2537            typename _Compare, typename _Alloc>
2538     typename _Rb_tree<_Key, _Val, _KeyOfValue,
2539                       _Compare, _Alloc>::const_iterator
2540     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2541     find(const _Key& __k) const
2542     {
2543       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2544       return (__j == end()
2545               || _M_impl._M_key_compare(__k,
2546                                         _S_key(__j._M_node))) ? end() : __j;
2547     }
2548
2549   template<typename _Key, typename _Val, typename _KeyOfValue,
2550            typename _Compare, typename _Alloc>
2551     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2552     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2553     count(const _Key& __k) const
2554     {
2555       pair<const_iterator, const_iterator> __p = equal_range(__k);
2556       const size_type __n = std::distance(__p.first, __p.second);
2557       return __n;
2558     }
2559
2560   _GLIBCXX_PURE unsigned int
2561   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2562                        const _Rb_tree_node_base* __root) throw ();
2563
2564   template<typename _Key, typename _Val, typename _KeyOfValue,
2565            typename _Compare, typename _Alloc>
2566     bool
2567     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2568     {
2569       if (_M_impl._M_node_count == 0 || begin() == end())
2570         return _M_impl._M_node_count == 0 && begin() == end()
2571                && this->_M_impl._M_header._M_left == _M_end()
2572                && this->_M_impl._M_header._M_right == _M_end();
2573
2574       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2575       for (const_iterator __it = begin(); __it != end(); ++__it)
2576         {
2577           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2578           _Const_Link_type __L = _S_left(__x);
2579           _Const_Link_type __R = _S_right(__x);
2580
2581           if (__x->_M_color == _S_red)
2582             if ((__L && __L->_M_color == _S_red)
2583                 || (__R && __R->_M_color == _S_red))
2584               return false;
2585
2586           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2587             return false;
2588           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2589             return false;
2590
2591           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2592             return false;
2593         }
2594
2595       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2596         return false;
2597       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2598         return false;
2599       return true;
2600     }
2601
2602 #if __cplusplus > 201402L
2603   // Allow access to internals of compatible _Rb_tree specializations.
2604   template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
2605            typename _Alloc, typename _Cmp2>
2606     struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2607                                  _Cmp2>
2608     {
2609     private:
2610       friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2611
2612       static auto&
2613       _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2614       { return __tree._M_impl; }
2615     };
2616 #endif // C++17
2617
2618 _GLIBCXX_END_NAMESPACE_VERSION
2619 } // namespace
2620
2621 #endif