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

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