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

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