contrib/gcc-5.0/libstdc++-v3/include/bits/stl_tree.h

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