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

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