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

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