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

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2013 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 #include <bits/stl_algobase.h>
  62 #include <bits/allocator.h>
  63 #include <bits/stl_function.h>
  64 #include <bits/cpp_type_traits.h>
  65 #if __cplusplus >= 201103L
  66 #include <bits/alloc_traits.h>
  67 #endif
  68
  69 namespace std _GLIBCXX_VISIBILITY(default)
  70 {
  71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  72
  73   // Red-black tree class, designed for use in implementing STL
  74   // associative containers (set, multiset, map, and multimap). The
  75   // insertion and deletion algorithms are based on those in Cormen,
  76   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  77   // 1990), except that
  78   //
  79   // (1) the header cell is maintained with links not only to the root
  80   // but also to the leftmost node of the tree, to enable constant
  81   // time begin(), and to the rightmost node of the tree, to enable
  82   // linear time performance when used with the generic set algorithms
  83   // (set_union, etc.)
  84   //
  85   // (2) when a node being deleted has two children its successor node
  86   // is relinked into its place, rather than copied, so that the only
  87   // iterators invalidated are those referring to the deleted node.
  88
  89   enum _Rb_tree_color { _S_red = false, _S_black = true };
  90
  91   struct _Rb_tree_node_base
  92   {
  93     typedef _Rb_tree_node_base* _Base_ptr;
  94     typedef const _Rb_tree_node_base* _Const_Base_ptr;
  95
  96     _Rb_tree_color      _M_color;
  97     _Base_ptr           _M_parent;
  98     _Base_ptr           _M_left;
  99     _Base_ptr           _M_right;
 100
 101     static _Base_ptr
 102     _S_minimum(_Base_ptr __x)
 103     {
 104       while (__x->_M_left != 0) __x = __x->_M_left;
 105       return __x;
 106     }
 107
 108     static _Const_Base_ptr
 109     _S_minimum(_Const_Base_ptr __x)
 110     {
 111       while (__x->_M_left != 0) __x = __x->_M_left;
 112       return __x;
 113     }
 114
 115     static _Base_ptr
 116     _S_maximum(_Base_ptr __x)
 117     {
 118       while (__x->_M_right != 0) __x = __x->_M_right;
 119       return __x;
 120     }
 121
 122     static _Const_Base_ptr
 123     _S_maximum(_Const_Base_ptr __x)
 124     {
 125       while (__x->_M_right != 0) __x = __x->_M_right;
 126       return __x;
 127     }
 128   };
 129
 130   template<typename _Val>
 131     struct _Rb_tree_node : public _Rb_tree_node_base
 132     {
 133       typedef _Rb_tree_node<_Val>* _Link_type;
 134       _Val _M_value_field;
 135
 136 #if __cplusplus >= 201103L
 137       template<typename... _Args>
 138         _Rb_tree_node(_Args&&... __args)
 139         : _Rb_tree_node_base(),
 140           _M_value_field(std::forward<_Args>(__args)...) { }
 141 #endif
 142     };
 143
 144   _GLIBCXX_PURE _Rb_tree_node_base*
 145   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
 146
 147   _GLIBCXX_PURE const _Rb_tree_node_base*
 148   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
 149
 150   _GLIBCXX_PURE _Rb_tree_node_base*
 151   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
 152
 153   _GLIBCXX_PURE const _Rb_tree_node_base*
 154   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
 155
 156   template<typename _Tp>
 157     struct _Rb_tree_iterator
 158     {
 159       typedef _Tp  value_type;
 160       typedef _Tp& reference;
 161       typedef _Tp* pointer;
 162
 163       typedef bidirectional_iterator_tag iterator_category;
 164       typedef ptrdiff_t                  difference_type;
 165
 166       typedef _Rb_tree_iterator<_Tp>        _Self;
 167       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 168       typedef _Rb_tree_node<_Tp>*           _Link_type;
 169
 170       _Rb_tree_iterator()
 171       : _M_node() { }
 172
 173       explicit
 174       _Rb_tree_iterator(_Link_type __x)
 175       : _M_node(__x) { }
 176
 177       reference
 178       operator*() const
 179       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 180
 181       pointer
 182       operator->() const
 183       { return std::__addressof(static_cast<_Link_type>
 184                                 (_M_node)->_M_value_field); }
 185
 186       _Self&
 187       operator++()
 188       {
 189         _M_node = _Rb_tree_increment(_M_node);
 190         return *this;
 191       }
 192
 193       _Self
 194       operator++(int)
 195       {
 196         _Self __tmp = *this;
 197         _M_node = _Rb_tree_increment(_M_node);
 198         return __tmp;
 199       }
 200
 201       _Self&
 202       operator--()
 203       {
 204         _M_node = _Rb_tree_decrement(_M_node);
 205         return *this;
 206       }
 207
 208       _Self
 209       operator--(int)
 210       {
 211         _Self __tmp = *this;
 212         _M_node = _Rb_tree_decrement(_M_node);
 213         return __tmp;
 214       }
 215
 216       bool
 217       operator==(const _Self& __x) const
 218       { return _M_node == __x._M_node; }
 219
 220       bool
 221       operator!=(const _Self& __x) const
 222       { return _M_node != __x._M_node; }
 223
 224       _Base_ptr _M_node;
 225   };
 226
 227   template<typename _Tp>
 228     struct _Rb_tree_const_iterator
 229     {
 230       typedef _Tp        value_type;
 231       typedef const _Tp& reference;
 232       typedef const _Tp* pointer;
 233
 234       typedef _Rb_tree_iterator<_Tp> iterator;
 235
 236       typedef bidirectional_iterator_tag iterator_category;
 237       typedef ptrdiff_t                  difference_type;
 238
 239       typedef _Rb_tree_const_iterator<_Tp>        _Self;
 240       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
 241       typedef const _Rb_tree_node<_Tp>*           _Link_type;
 242
 243       _Rb_tree_const_iterator()
 244       : _M_node() { }
 245
 246       explicit
 247       _Rb_tree_const_iterator(_Link_type __x)
 248       : _M_node(__x) { }
 249
 250       _Rb_tree_const_iterator(const iterator& __it)
 251       : _M_node(__it._M_node) { }
 252
 253       iterator
 254       _M_const_cast() const
 255       { return iterator(static_cast<typename iterator::_Link_type>
 256                         (const_cast<typename iterator::_Base_ptr>(_M_node))); }
 257
 258       reference
 259       operator*() const
 260       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 261
 262       pointer
 263       operator->() const
 264       { return std::__addressof(static_cast<_Link_type>
 265                                 (_M_node)->_M_value_field); }
 266
 267       _Self&
 268       operator++()
 269       {
 270         _M_node = _Rb_tree_increment(_M_node);
 271         return *this;
 272       }
 273
 274       _Self
 275       operator++(int)
 276       {
 277         _Self __tmp = *this;
 278         _M_node = _Rb_tree_increment(_M_node);
 279         return __tmp;
 280       }
 281
 282       _Self&
 283       operator--()
 284       {
 285         _M_node = _Rb_tree_decrement(_M_node);
 286         return *this;
 287       }
 288
 289       _Self
 290       operator--(int)
 291       {
 292         _Self __tmp = *this;
 293         _M_node = _Rb_tree_decrement(_M_node);
 294         return __tmp;
 295       }
 296
 297       bool
 298       operator==(const _Self& __x) const
 299       { return _M_node == __x._M_node; }
 300
 301       bool
 302       operator!=(const _Self& __x) const
 303       { return _M_node != __x._M_node; }
 304
 305       _Base_ptr _M_node;
 306     };
 307
 308   template<typename _Val>
 309     inline bool
 310     operator==(const _Rb_tree_iterator<_Val>& __x,
 311                const _Rb_tree_const_iterator<_Val>& __y)
 312     { return __x._M_node == __y._M_node; }
 313
 314   template<typename _Val>
 315     inline bool
 316     operator!=(const _Rb_tree_iterator<_Val>& __x,
 317                const _Rb_tree_const_iterator<_Val>& __y)
 318     { return __x._M_node != __y._M_node; }
 319
 320   void
 321   _Rb_tree_insert_and_rebalance(const bool __insert_left,
 322                                 _Rb_tree_node_base* __x,
 323                                 _Rb_tree_node_base* __p,
 324                                 _Rb_tree_node_base& __header) throw ();
 325
 326   _Rb_tree_node_base*
 327   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 328                                _Rb_tree_node_base& __header) throw ();
 329
 330
 331   template<typename _Key, typename _Val, typename _KeyOfValue,
 332            typename _Compare, typename _Alloc = allocator<_Val> >
 333     class _Rb_tree
 334     {
 335       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 336               _Node_allocator;
 337
 338     protected:
 339       typedef _Rb_tree_node_base* _Base_ptr;
 340       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 341
 342     public:
 343       typedef _Key key_type;
 344       typedef _Val value_type;
 345       typedef value_type* pointer;
 346       typedef const value_type* const_pointer;
 347       typedef value_type& reference;
 348       typedef const value_type& const_reference;
 349       typedef _Rb_tree_node<_Val>* _Link_type;
 350       typedef const _Rb_tree_node<_Val>* _Const_Link_type;
 351       typedef size_t size_type;
 352       typedef ptrdiff_t difference_type;
 353       typedef _Alloc allocator_type;
 354
 355       _Node_allocator&
 356       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
 357       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
 358
 359       const _Node_allocator&
 360       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
 361       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 362
 363       allocator_type
 364       get_allocator() const _GLIBCXX_NOEXCEPT
 365       { return allocator_type(_M_get_Node_allocator()); }
 366
 367     protected:
 368       _Link_type
 369       _M_get_node()
 370       { return _M_impl._Node_allocator::allocate(1); }
 371
 372       void
 373       _M_put_node(_Link_type __p)
 374       { _M_impl._Node_allocator::deallocate(__p, 1); }
 375
 376 #if __cplusplus < 201103L
 377       _Link_type
 378       _M_create_node(const value_type& __x)
 379       {
 380         _Link_type __tmp = _M_get_node();
 381         __try
 382           { get_allocator().construct
 383               (std::__addressof(__tmp->_M_value_field), __x); }
 384         __catch(...)
 385           {
 386             _M_put_node(__tmp);
 387             __throw_exception_again;
 388           }
 389         return __tmp;
 390       }
 391
 392       void
 393       _M_destroy_node(_Link_type __p)
 394       {
 395         get_allocator().destroy(std::__addressof(__p->_M_value_field));
 396         _M_put_node(__p);
 397       }
 398 #else
 399       template<typename... _Args>
 400         _Link_type
 401         _M_create_node(_Args&&... __args)
 402         {
 403           _Link_type __tmp = _M_get_node();
 404           __try
 405             {
 406               allocator_traits<_Node_allocator>::
 407                 construct(_M_get_Node_allocator(), __tmp,
 408                           std::forward<_Args>(__args)...);
 409             }
 410           __catch(...)
 411             {
 412               _M_put_node(__tmp);
 413               __throw_exception_again;
 414             }
 415           return __tmp;
 416         }
 417
 418       void
 419       _M_destroy_node(_Link_type __p)
 420       {
 421         _M_get_Node_allocator().destroy(__p);
 422         _M_put_node(__p);
 423       }
 424 #endif
 425
 426       _Link_type
 427       _M_clone_node(_Const_Link_type __x)
 428       {
 429         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 430         __tmp->_M_color = __x->_M_color;
 431         __tmp->_M_left = 0;
 432         __tmp->_M_right = 0;
 433         return __tmp;
 434       }
 435
 436     protected:
 437       template<typename _Key_compare,
 438                bool _Is_pod_comparator = __is_pod(_Key_compare)>
 439         struct _Rb_tree_impl : public _Node_allocator
 440         {
 441           _Key_compare          _M_key_compare;
 442           _Rb_tree_node_base    _M_header;
 443           size_type             _M_node_count; // Keeps track of size of tree.
 444
 445           _Rb_tree_impl()
 446           : _Node_allocator(), _M_key_compare(), _M_header(),
 447             _M_node_count(0)
 448           { _M_initialize(); }
 449
 450           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
 451           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 452             _M_node_count(0)
 453           { _M_initialize(); }
 454
 455 #if __cplusplus >= 201103L
 456           _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 457           : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
 458             _M_header(), _M_node_count(0)
 459           { _M_initialize(); }
 460 #endif
 461
 462         private:
 463           void
 464           _M_initialize()
 465           {
 466             this->_M_header._M_color = _S_red;
 467             this->_M_header._M_parent = 0;
 468             this->_M_header._M_left = &this->_M_header;
 469             this->_M_header._M_right = &this->_M_header;
 470           }
 471         };
 472
 473       _Rb_tree_impl<_Compare> _M_impl;
 474
 475     protected:
 476       _Base_ptr&
 477       _M_root()
 478       { return this->_M_impl._M_header._M_parent; }
 479
 480       _Const_Base_ptr
 481       _M_root() const
 482       { return this->_M_impl._M_header._M_parent; }
 483
 484       _Base_ptr&
 485       _M_leftmost()
 486       { return this->_M_impl._M_header._M_left; }
 487
 488       _Const_Base_ptr
 489       _M_leftmost() const
 490       { return this->_M_impl._M_header._M_left; }
 491
 492       _Base_ptr&
 493       _M_rightmost()
 494       { return this->_M_impl._M_header._M_right; }
 495
 496       _Const_Base_ptr
 497       _M_rightmost() const
 498       { return this->_M_impl._M_header._M_right; }
 499
 500       _Link_type
 501       _M_begin()
 502       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 503
 504       _Const_Link_type
 505       _M_begin() const
 506       {
 507         return static_cast<_Const_Link_type>
 508           (this->_M_impl._M_header._M_parent);
 509       }
 510
 511       _Link_type
 512       _M_end()
 513       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 514
 515       _Const_Link_type
 516       _M_end() const
 517       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 518
 519       static const_reference
 520       _S_value(_Const_Link_type __x)
 521       { return __x->_M_value_field; }
 522
 523       static const _Key&
 524       _S_key(_Const_Link_type __x)
 525       { return _KeyOfValue()(_S_value(__x)); }
 526
 527       static _Link_type
 528       _S_left(_Base_ptr __x)
 529       { return static_cast<_Link_type>(__x->_M_left); }
 530
 531       static _Const_Link_type
 532       _S_left(_Const_Base_ptr __x)
 533       { return static_cast<_Const_Link_type>(__x->_M_left); }
 534
 535       static _Link_type
 536       _S_right(_Base_ptr __x)
 537       { return static_cast<_Link_type>(__x->_M_right); }
 538
 539       static _Const_Link_type
 540       _S_right(_Const_Base_ptr __x)
 541       { return static_cast<_Const_Link_type>(__x->_M_right); }
 542
 543       static const_reference
 544       _S_value(_Const_Base_ptr __x)
 545       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 546
 547       static const _Key&
 548       _S_key(_Const_Base_ptr __x)
 549       { return _KeyOfValue()(_S_value(__x)); }
 550
 551       static _Base_ptr
 552       _S_minimum(_Base_ptr __x)
 553       { return _Rb_tree_node_base::_S_minimum(__x); }
 554
 555       static _Const_Base_ptr
 556       _S_minimum(_Const_Base_ptr __x)
 557       { return _Rb_tree_node_base::_S_minimum(__x); }
 558
 559       static _Base_ptr
 560       _S_maximum(_Base_ptr __x)
 561       { return _Rb_tree_node_base::_S_maximum(__x); }
 562
 563       static _Const_Base_ptr
 564       _S_maximum(_Const_Base_ptr __x)
 565       { return _Rb_tree_node_base::_S_maximum(__x); }
 566
 567     public:
 568       typedef _Rb_tree_iterator<value_type>       iterator;
 569       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 570
 571       typedef std::reverse_iterator<iterator>       reverse_iterator;
 572       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 573
 574     private:
 575       pair<_Base_ptr, _Base_ptr>
 576       _M_get_insert_unique_pos(const key_type& __k);
 577
 578       pair<_Base_ptr, _Base_ptr>
 579       _M_get_insert_equal_pos(const key_type& __k);
 580
 581       pair<_Base_ptr, _Base_ptr>
 582       _M_get_insert_hint_unique_pos(const_iterator __pos,
 583                                     const key_type& __k);
 584
 585       pair<_Base_ptr, _Base_ptr>
 586       _M_get_insert_hint_equal_pos(const_iterator __pos,
 587                                    const key_type& __k);
 588
 589 #if __cplusplus >= 201103L
 590       template<typename _Arg>
 591         iterator
 592         _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
 593
 594       iterator
 595       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
 596
 597       template<typename _Arg>
 598         iterator
 599         _M_insert_lower(_Base_ptr __y, _Arg&& __v);
 600
 601       template<typename _Arg>
 602         iterator
 603         _M_insert_equal_lower(_Arg&& __x);
 604
 605       iterator
 606       _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
 607
 608       iterator
 609       _M_insert_equal_lower_node(_Link_type __z);
 610 #else
 611       iterator
 612       _M_insert_(_Base_ptr __x, _Base_ptr __y,
 613                  const value_type& __v);
 614
 615       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 616       // 233. Insertion hints in associative containers.
 617       iterator
 618       _M_insert_lower(_Base_ptr __y, const value_type& __v);
 619
 620       iterator
 621       _M_insert_equal_lower(const value_type& __x);
 622 #endif
 623
 624       _Link_type
 625       _M_copy(_Const_Link_type __x, _Link_type __p);
 626
 627       void
 628       _M_erase(_Link_type __x);
 629
 630       iterator
 631       _M_lower_bound(_Link_type __x, _Link_type __y,
 632                      const _Key& __k);
 633
 634       const_iterator
 635       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
 636                      const _Key& __k) const;
 637
 638       iterator
 639       _M_upper_bound(_Link_type __x, _Link_type __y,
 640                      const _Key& __k);
 641
 642       const_iterator
 643       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
 644                      const _Key& __k) const;
 645
 646     public:
 647       // allocation/deallocation
 648       _Rb_tree() { }
 649
 650       _Rb_tree(const _Compare& __comp,
 651                const allocator_type& __a = allocator_type())
 652       : _M_impl(__comp, _Node_allocator(__a)) { }
 653
 654       _Rb_tree(const _Rb_tree& __x)
 655       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
 656       {
 657         if (__x._M_root() != 0)
 658           {
 659             _M_root() = _M_copy(__x._M_begin(), _M_end());
 660             _M_leftmost() = _S_minimum(_M_root());
 661             _M_rightmost() = _S_maximum(_M_root());
 662             _M_impl._M_node_count = __x._M_impl._M_node_count;
 663           }
 664       }
 665
 666 #if __cplusplus >= 201103L
 667       _Rb_tree(_Rb_tree&& __x);
 668 #endif
 669
 670       ~_Rb_tree() _GLIBCXX_NOEXCEPT
 671       { _M_erase(_M_begin()); }
 672
 673       _Rb_tree&
 674       operator=(const _Rb_tree& __x);
 675
 676       // Accessors.
 677       _Compare
 678       key_comp() const
 679       { return _M_impl._M_key_compare; }
 680
 681       iterator
 682       begin() _GLIBCXX_NOEXCEPT
 683       {
 684         return iterator(static_cast<_Link_type>
 685                         (this->_M_impl._M_header._M_left));
 686       }
 687
 688       const_iterator
 689       begin() const _GLIBCXX_NOEXCEPT
 690       {
 691         return const_iterator(static_cast<_Const_Link_type>
 692                               (this->_M_impl._M_header._M_left));
 693       }
 694
 695       iterator
 696       end() _GLIBCXX_NOEXCEPT
 697       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 698
 699       const_iterator
 700       end() const _GLIBCXX_NOEXCEPT
 701       {
 702         return const_iterator(static_cast<_Const_Link_type>
 703                               (&this->_M_impl._M_header));
 704       }
 705
 706       reverse_iterator
 707       rbegin() _GLIBCXX_NOEXCEPT
 708       { return reverse_iterator(end()); }
 709
 710       const_reverse_iterator
 711       rbegin() const _GLIBCXX_NOEXCEPT
 712       { return const_reverse_iterator(end()); }
 713
 714       reverse_iterator
 715       rend() _GLIBCXX_NOEXCEPT
 716       { return reverse_iterator(begin()); }
 717
 718       const_reverse_iterator
 719       rend() const _GLIBCXX_NOEXCEPT
 720       { return const_reverse_iterator(begin()); }
 721
 722       bool
 723       empty() const _GLIBCXX_NOEXCEPT
 724       { return _M_impl._M_node_count == 0; }
 725
 726       size_type
 727       size() const _GLIBCXX_NOEXCEPT
 728       { return _M_impl._M_node_count; }
 729
 730       size_type
 731       max_size() const _GLIBCXX_NOEXCEPT
 732       { return _M_get_Node_allocator().max_size(); }
 733
 734       void
 735       swap(_Rb_tree& __t);
 736
 737       // Insert/erase.
 738 #if __cplusplus >= 201103L
 739       template<typename _Arg>
 740         pair<iterator, bool>
 741         _M_insert_unique(_Arg&& __x);
 742
 743       template<typename _Arg>
 744         iterator
 745         _M_insert_equal(_Arg&& __x);
 746
 747       template<typename _Arg>
 748         iterator
 749         _M_insert_unique_(const_iterator __position, _Arg&& __x);
 750
 751       template<typename _Arg>
 752         iterator
 753         _M_insert_equal_(const_iterator __position, _Arg&& __x);
 754
 755       template<typename... _Args>
 756         pair<iterator, bool>
 757         _M_emplace_unique(_Args&&... __args);
 758
 759       template<typename... _Args>
 760         iterator
 761         _M_emplace_equal(_Args&&... __args);
 762
 763       template<typename... _Args>
 764         iterator
 765         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
 766
 767       template<typename... _Args>
 768         iterator
 769         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
 770 #else
 771       pair<iterator, bool>
 772       _M_insert_unique(const value_type& __x);
 773
 774       iterator
 775       _M_insert_equal(const value_type& __x);
 776
 777       iterator
 778       _M_insert_unique_(const_iterator __position, const value_type& __x);
 779
 780       iterator
 781       _M_insert_equal_(const_iterator __position, const value_type& __x);
 782 #endif
 783
 784       template<typename _InputIterator>
 785         void
 786         _M_insert_unique(_InputIterator __first, _InputIterator __last);
 787
 788       template<typename _InputIterator>
 789         void
 790         _M_insert_equal(_InputIterator __first, _InputIterator __last);
 791
 792     private:
 793       void
 794       _M_erase_aux(const_iterator __position);
 795
 796       void
 797       _M_erase_aux(const_iterator __first, const_iterator __last);
 798
 799     public:
 800 #if __cplusplus >= 201103L
 801       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 802       // DR 130. Associative erase should return an iterator.
 803       iterator
 804       erase(const_iterator __position)
 805       {
 806         const_iterator __result = __position;
 807         ++__result;
 808         _M_erase_aux(__position);
 809         return __result._M_const_cast();
 810       }
 811
 812       // LWG 2059.
 813       iterator
 814       erase(iterator __position)
 815       {
 816         iterator __result = __position;
 817         ++__result;
 818         _M_erase_aux(__position);
 819         return __result;
 820       }
 821 #else
 822       void
 823       erase(iterator __position)
 824       { _M_erase_aux(__position); }
 825
 826       void
 827       erase(const_iterator __position)
 828       { _M_erase_aux(__position); }
 829 #endif
 830       size_type
 831       erase(const key_type& __x);
 832
 833 #if __cplusplus >= 201103L
 834       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 835       // DR 130. Associative erase should return an iterator.
 836       iterator
 837       erase(const_iterator __first, const_iterator __last)
 838       {
 839         _M_erase_aux(__first, __last);
 840         return __last._M_const_cast();
 841       }
 842 #else
 843       void
 844       erase(iterator __first, iterator __last)
 845       { _M_erase_aux(__first, __last); }
 846
 847       void
 848       erase(const_iterator __first, const_iterator __last)
 849       { _M_erase_aux(__first, __last); }
 850 #endif
 851       void
 852       erase(const key_type* __first, const key_type* __last);
 853
 854       void
 855       clear() _GLIBCXX_NOEXCEPT
 856       {
 857         _M_erase(_M_begin());
 858         _M_leftmost() = _M_end();
 859         _M_root() = 0;
 860         _M_rightmost() = _M_end();
 861         _M_impl._M_node_count = 0;
 862       }
 863
 864       // Set operations.
 865       iterator
 866       find(const key_type& __k);
 867
 868       const_iterator
 869       find(const key_type& __k) const;
 870
 871       size_type
 872       count(const key_type& __k) const;
 873
 874       iterator
 875       lower_bound(const key_type& __k)
 876       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
 877
 878       const_iterator
 879       lower_bound(const key_type& __k) const
 880       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
 881
 882       iterator
 883       upper_bound(const key_type& __k)
 884       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
 885
 886       const_iterator
 887       upper_bound(const key_type& __k) const
 888       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
 889
 890       pair<iterator, iterator>
 891       equal_range(const key_type& __k);
 892
 893       pair<const_iterator, const_iterator>
 894       equal_range(const key_type& __k) const;
 895
 896       // Debugging.
 897       bool
 898       __rb_verify() const;
 899     };
 900
 901   template<typename _Key, typename _Val, typename _KeyOfValue,
 902            typename _Compare, typename _Alloc>
 903     inline bool
 904     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 905                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 906     {
 907       return __x.size() == __y.size()
 908              && std::equal(__x.begin(), __x.end(), __y.begin());
 909     }
 910
 911   template<typename _Key, typename _Val, typename _KeyOfValue,
 912            typename _Compare, typename _Alloc>
 913     inline bool
 914     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 915               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 916     {
 917       return std::lexicographical_compare(__x.begin(), __x.end(),
 918                                           __y.begin(), __y.end());
 919     }
 920
 921   template<typename _Key, typename _Val, typename _KeyOfValue,
 922            typename _Compare, typename _Alloc>
 923     inline bool
 924     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 925                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 926     { return !(__x == __y); }
 927
 928   template<typename _Key, typename _Val, typename _KeyOfValue,
 929            typename _Compare, typename _Alloc>
 930     inline bool
 931     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 932               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 933     { return __y < __x; }
 934
 935   template<typename _Key, typename _Val, typename _KeyOfValue,
 936            typename _Compare, typename _Alloc>
 937     inline bool
 938     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 939                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 940     { return !(__y < __x); }
 941
 942   template<typename _Key, typename _Val, typename _KeyOfValue,
 943            typename _Compare, typename _Alloc>
 944     inline bool
 945     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 946                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 947     { return !(__x < __y); }
 948
 949   template<typename _Key, typename _Val, typename _KeyOfValue,
 950            typename _Compare, typename _Alloc>
 951     inline void
 952     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 953          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 954     { __x.swap(__y); }
 955
 956 #if __cplusplus >= 201103L
 957   template<typename _Key, typename _Val, typename _KeyOfValue,
 958            typename _Compare, typename _Alloc>
 959     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 960     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
 961     : _M_impl(__x._M_impl._M_key_compare,
 962               std::move(__x._M_get_Node_allocator()))
 963     {
 964       if (__x._M_root() != 0)
 965         {
 966           _M_root() = __x._M_root();
 967           _M_leftmost() = __x._M_leftmost();
 968           _M_rightmost() = __x._M_rightmost();
 969           _M_root()->_M_parent = _M_end();
 970
 971           __x._M_root() = 0;
 972           __x._M_leftmost() = __x._M_end();
 973           __x._M_rightmost() = __x._M_end();
 974
 975           this->_M_impl._M_node_count = __x._M_impl._M_node_count;
 976           __x._M_impl._M_node_count = 0;
 977         }
 978     }
 979 #endif
 980
 981   template<typename _Key, typename _Val, typename _KeyOfValue,
 982            typename _Compare, typename _Alloc>
 983     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 984     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 985     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 986     {
 987       if (this != &__x)
 988         {
 989           // Note that _Key may be a constant type.
 990           clear();
 991           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 992           if (__x._M_root() != 0)
 993             {
 994               _M_root() = _M_copy(__x._M_begin(), _M_end());
 995               _M_leftmost() = _S_minimum(_M_root());
 996               _M_rightmost() = _S_maximum(_M_root());
 997               _M_impl._M_node_count = __x._M_impl._M_node_count;
 998             }
 999         }
1000       return *this;
1001     }
1002
1003   template<typename _Key, typename _Val, typename _KeyOfValue,
1004            typename _Compare, typename _Alloc>
1005 #if __cplusplus >= 201103L
1006     template<typename _Arg>
1007 #endif
1008     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1009     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1010 #if __cplusplus >= 201103L
1011     _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
1012 #else
1013     _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
1014 #endif
1015     {
1016       bool __insert_left = (__x != 0 || __p == _M_end()
1017                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
1018                                                       _S_key(__p)));
1019
1020       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1021
1022       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1023                                     this->_M_impl._M_header);
1024       ++_M_impl._M_node_count;
1025       return iterator(__z);
1026     }
1027
1028   template<typename _Key, typename _Val, typename _KeyOfValue,
1029            typename _Compare, typename _Alloc>
1030 #if __cplusplus >= 201103L
1031     template<typename _Arg>
1032 #endif
1033     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1034     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1035 #if __cplusplus >= 201103L
1036     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1037 #else
1038     _M_insert_lower(_Base_ptr __p, const _Val& __v)
1039 #endif
1040     {
1041       bool __insert_left = (__p == _M_end()
1042                             || !_M_impl._M_key_compare(_S_key(__p),
1043                                                        _KeyOfValue()(__v)));
1044
1045       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1046
1047       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1048                                     this->_M_impl._M_header);
1049       ++_M_impl._M_node_count;
1050       return iterator(__z);
1051     }
1052
1053   template<typename _Key, typename _Val, typename _KeyOfValue,
1054            typename _Compare, typename _Alloc>
1055 #if __cplusplus >= 201103L
1056     template<typename _Arg>
1057 #endif
1058     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1059     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1060 #if __cplusplus >= 201103L
1061     _M_insert_equal_lower(_Arg&& __v)
1062 #else
1063     _M_insert_equal_lower(const _Val& __v)
1064 #endif
1065     {
1066       _Link_type __x = _M_begin();
1067       _Link_type __y = _M_end();
1068       while (__x != 0)
1069         {
1070           __y = __x;
1071           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1072                 _S_left(__x) : _S_right(__x);
1073         }
1074       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1075     }
1076
1077   template<typename _Key, typename _Val, typename _KoV,
1078            typename _Compare, typename _Alloc>
1079     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1080     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1081     _M_copy(_Const_Link_type __x, _Link_type __p)
1082     {
1083       // Structural copy.  __x and __p must be non-null.
1084       _Link_type __top = _M_clone_node(__x);
1085       __top->_M_parent = __p;
1086
1087       __try
1088         {
1089           if (__x->_M_right)
1090             __top->_M_right = _M_copy(_S_right(__x), __top);
1091           __p = __top;
1092           __x = _S_left(__x);
1093
1094           while (__x != 0)
1095             {
1096               _Link_type __y = _M_clone_node(__x);
1097               __p->_M_left = __y;
1098               __y->_M_parent = __p;
1099               if (__x->_M_right)
1100                 __y->_M_right = _M_copy(_S_right(__x), __y);
1101               __p = __y;
1102               __x = _S_left(__x);
1103             }
1104         }
1105       __catch(...)
1106         {
1107           _M_erase(__top);
1108           __throw_exception_again;
1109         }
1110       return __top;
1111     }
1112
1113   template<typename _Key, typename _Val, typename _KeyOfValue,
1114            typename _Compare, typename _Alloc>
1115     void
1116     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1117     _M_erase(_Link_type __x)
1118     {
1119       // Erase without rebalancing.
1120       while (__x != 0)
1121         {
1122           _M_erase(_S_right(__x));
1123           _Link_type __y = _S_left(__x);
1124           _M_destroy_node(__x);
1125           __x = __y;
1126         }
1127     }
1128
1129   template<typename _Key, typename _Val, typename _KeyOfValue,
1130            typename _Compare, typename _Alloc>
1131     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1132                       _Compare, _Alloc>::iterator
1133     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1134     _M_lower_bound(_Link_type __x, _Link_type __y,
1135                    const _Key& __k)
1136     {
1137       while (__x != 0)
1138         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1139           __y = __x, __x = _S_left(__x);
1140         else
1141           __x = _S_right(__x);
1142       return iterator(__y);
1143     }
1144
1145   template<typename _Key, typename _Val, typename _KeyOfValue,
1146            typename _Compare, typename _Alloc>
1147     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1148                       _Compare, _Alloc>::const_iterator
1149     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1150     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1151                    const _Key& __k) const
1152     {
1153       while (__x != 0)
1154         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1155           __y = __x, __x = _S_left(__x);
1156         else
1157           __x = _S_right(__x);
1158       return const_iterator(__y);
1159     }
1160
1161   template<typename _Key, typename _Val, typename _KeyOfValue,
1162            typename _Compare, typename _Alloc>
1163     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1164                       _Compare, _Alloc>::iterator
1165     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1166     _M_upper_bound(_Link_type __x, _Link_type __y,
1167                    const _Key& __k)
1168     {
1169       while (__x != 0)
1170         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1171           __y = __x, __x = _S_left(__x);
1172         else
1173           __x = _S_right(__x);
1174       return iterator(__y);
1175     }
1176
1177   template<typename _Key, typename _Val, typename _KeyOfValue,
1178            typename _Compare, typename _Alloc>
1179     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1180                       _Compare, _Alloc>::const_iterator
1181     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1182     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1183                    const _Key& __k) const
1184     {
1185       while (__x != 0)
1186         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1187           __y = __x, __x = _S_left(__x);
1188         else
1189           __x = _S_right(__x);
1190       return const_iterator(__y);
1191     }
1192
1193   template<typename _Key, typename _Val, typename _KeyOfValue,
1194            typename _Compare, typename _Alloc>
1195     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1196                            _Compare, _Alloc>::iterator,
1197          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1198                            _Compare, _Alloc>::iterator>
1199     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1200     equal_range(const _Key& __k)
1201     {
1202       _Link_type __x = _M_begin();
1203       _Link_type __y = _M_end();
1204       while (__x != 0)
1205         {
1206           if (_M_impl._M_key_compare(_S_key(__x), __k))
1207             __x = _S_right(__x);
1208           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1209             __y = __x, __x = _S_left(__x);
1210           else
1211             {
1212               _Link_type __xu(__x), __yu(__y);
1213               __y = __x, __x = _S_left(__x);
1214               __xu = _S_right(__xu);
1215               return pair<iterator,
1216                           iterator>(_M_lower_bound(__x, __y, __k),
1217                                     _M_upper_bound(__xu, __yu, __k));
1218             }
1219         }
1220       return pair<iterator, iterator>(iterator(__y),
1221                                       iterator(__y));
1222     }
1223
1224   template<typename _Key, typename _Val, typename _KeyOfValue,
1225            typename _Compare, typename _Alloc>
1226     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1227                            _Compare, _Alloc>::const_iterator,
1228          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1229                            _Compare, _Alloc>::const_iterator>
1230     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1231     equal_range(const _Key& __k) const
1232     {
1233       _Const_Link_type __x = _M_begin();
1234       _Const_Link_type __y = _M_end();
1235       while (__x != 0)
1236         {
1237           if (_M_impl._M_key_compare(_S_key(__x), __k))
1238             __x = _S_right(__x);
1239           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1240             __y = __x, __x = _S_left(__x);
1241           else
1242             {
1243               _Const_Link_type __xu(__x), __yu(__y);
1244               __y = __x, __x = _S_left(__x);
1245               __xu = _S_right(__xu);
1246               return pair<const_iterator,
1247                           const_iterator>(_M_lower_bound(__x, __y, __k),
1248                                           _M_upper_bound(__xu, __yu, __k));
1249             }
1250         }
1251       return pair<const_iterator, const_iterator>(const_iterator(__y),
1252                                                   const_iterator(__y));
1253     }
1254
1255   template<typename _Key, typename _Val, typename _KeyOfValue,
1256            typename _Compare, typename _Alloc>
1257     void
1258     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1259     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1260     {
1261       if (_M_root() == 0)
1262         {
1263           if (__t._M_root() != 0)
1264             {
1265               _M_root() = __t._M_root();
1266               _M_leftmost() = __t._M_leftmost();
1267               _M_rightmost() = __t._M_rightmost();
1268               _M_root()->_M_parent = _M_end();
1269
1270               __t._M_root() = 0;
1271               __t._M_leftmost() = __t._M_end();
1272               __t._M_rightmost() = __t._M_end();
1273             }
1274         }
1275       else if (__t._M_root() == 0)
1276         {
1277           __t._M_root() = _M_root();
1278           __t._M_leftmost() = _M_leftmost();
1279           __t._M_rightmost() = _M_rightmost();
1280           __t._M_root()->_M_parent = __t._M_end();
1281
1282           _M_root() = 0;
1283           _M_leftmost() = _M_end();
1284           _M_rightmost() = _M_end();
1285         }
1286       else
1287         {
1288           std::swap(_M_root(),__t._M_root());
1289           std::swap(_M_leftmost(),__t._M_leftmost());
1290           std::swap(_M_rightmost(),__t._M_rightmost());
1291
1292           _M_root()->_M_parent = _M_end();
1293           __t._M_root()->_M_parent = __t._M_end();
1294         }
1295       // No need to swap header's color as it does not change.
1296       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1297       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1298
1299       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1300       // 431. Swapping containers with unequal allocators.
1301       std::__alloc_swap<_Node_allocator>::
1302         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1303     }
1304
1305   template<typename _Key, typename _Val, typename _KeyOfValue,
1306            typename _Compare, typename _Alloc>
1307     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1308                            _Compare, _Alloc>::_Base_ptr,
1309          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1310                            _Compare, _Alloc>::_Base_ptr>
1311     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1312     _M_get_insert_unique_pos(const key_type& __k)
1313     {
1314       typedef pair<_Base_ptr, _Base_ptr> _Res;
1315       _Link_type __x = _M_begin();
1316       _Link_type __y = _M_end();
1317       bool __comp = true;
1318       while (__x != 0)
1319         {
1320           __y = __x;
1321           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1322           __x = __comp ? _S_left(__x) : _S_right(__x);
1323         }
1324       iterator __j = iterator(__y);
1325       if (__comp)
1326         {
1327           if (__j == begin())
1328             return _Res(__x, __y);
1329           else
1330             --__j;
1331         }
1332       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1333         return _Res(__x, __y);
1334       return _Res(__j._M_node, 0);
1335     }
1336
1337   template<typename _Key, typename _Val, typename _KeyOfValue,
1338            typename _Compare, typename _Alloc>
1339     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1340                            _Compare, _Alloc>::_Base_ptr,
1341          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1342                            _Compare, _Alloc>::_Base_ptr>
1343     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1344     _M_get_insert_equal_pos(const key_type& __k)
1345     {
1346       typedef pair<_Base_ptr, _Base_ptr> _Res;
1347       _Link_type __x = _M_begin();
1348       _Link_type __y = _M_end();
1349       while (__x != 0)
1350         {
1351           __y = __x;
1352           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1353                 _S_left(__x) : _S_right(__x);
1354         }
1355       return _Res(__x, __y);
1356     }
1357
1358   template<typename _Key, typename _Val, typename _KeyOfValue,
1359            typename _Compare, typename _Alloc>
1360 #if __cplusplus >= 201103L
1361     template<typename _Arg>
1362 #endif
1363     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1364                            _Compare, _Alloc>::iterator, bool>
1365     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1366 #if __cplusplus >= 201103L
1367     _M_insert_unique(_Arg&& __v)
1368 #else
1369     _M_insert_unique(const _Val& __v)
1370 #endif
1371     {
1372       typedef pair<iterator, bool> _Res;
1373       pair<_Base_ptr, _Base_ptr> __res
1374         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1375
1376       if (__res.second)
1377         return _Res(_M_insert_(__res.first, __res.second,
1378                                _GLIBCXX_FORWARD(_Arg, __v)),
1379                     true);
1380
1381       return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1382     }
1383
1384   template<typename _Key, typename _Val, typename _KeyOfValue,
1385            typename _Compare, typename _Alloc>
1386 #if __cplusplus >= 201103L
1387     template<typename _Arg>
1388 #endif
1389     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1390     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1391 #if __cplusplus >= 201103L
1392     _M_insert_equal(_Arg&& __v)
1393 #else
1394     _M_insert_equal(const _Val& __v)
1395 #endif
1396     {
1397       pair<_Base_ptr, _Base_ptr> __res
1398         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1399       return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
1400     }
1401
1402   template<typename _Key, typename _Val, typename _KeyOfValue,
1403            typename _Compare, typename _Alloc>
1404     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1405                            _Compare, _Alloc>::_Base_ptr,
1406          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1407                            _Compare, _Alloc>::_Base_ptr>
1408     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1409     _M_get_insert_hint_unique_pos(const_iterator __position,
1410                                   const key_type& __k)
1411     {
1412       iterator __pos = __position._M_const_cast();
1413       typedef pair<_Base_ptr, _Base_ptr> _Res;
1414
1415       // end()
1416       if (__pos._M_node == _M_end())
1417         {
1418           if (size() > 0
1419               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1420             return _Res(0, _M_rightmost());
1421           else
1422             return _M_get_insert_unique_pos(__k);
1423         }
1424       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1425         {
1426           // First, try before...
1427           iterator __before = __pos;
1428           if (__pos._M_node == _M_leftmost()) // begin()
1429             return _Res(_M_leftmost(), _M_leftmost());
1430           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1431             {
1432               if (_S_right(__before._M_node) == 0)
1433                 return _Res(0, __before._M_node);
1434               else
1435                 return _Res(__pos._M_node, __pos._M_node);
1436             }
1437           else
1438             return _M_get_insert_unique_pos(__k);
1439         }
1440       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1441         {
1442           // ... then try after.
1443           iterator __after = __pos;
1444           if (__pos._M_node == _M_rightmost())
1445             return _Res(0, _M_rightmost());
1446           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1447             {
1448               if (_S_right(__pos._M_node) == 0)
1449                 return _Res(0, __pos._M_node);
1450               else
1451                 return _Res(__after._M_node, __after._M_node);
1452             }
1453           else
1454             return _M_get_insert_unique_pos(__k);
1455         }
1456       else
1457         // Equivalent keys.
1458         return _Res(__pos._M_node, 0);
1459     }
1460
1461   template<typename _Key, typename _Val, typename _KeyOfValue,
1462            typename _Compare, typename _Alloc>
1463 #if __cplusplus >= 201103L
1464     template<typename _Arg>
1465 #endif
1466     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1467     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1468 #if __cplusplus >= 201103L
1469     _M_insert_unique_(const_iterator __position, _Arg&& __v)
1470 #else
1471     _M_insert_unique_(const_iterator __position, const _Val& __v)
1472 #endif
1473     {
1474       pair<_Base_ptr, _Base_ptr> __res
1475         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1476
1477       if (__res.second)
1478         return _M_insert_(__res.first, __res.second,
1479                           _GLIBCXX_FORWARD(_Arg, __v));
1480       return iterator(static_cast<_Link_type>(__res.first));
1481     }
1482
1483   template<typename _Key, typename _Val, typename _KeyOfValue,
1484            typename _Compare, typename _Alloc>
1485     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1486                            _Compare, _Alloc>::_Base_ptr,
1487          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1488                            _Compare, _Alloc>::_Base_ptr>
1489     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1490     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1491     {
1492       iterator __pos = __position._M_const_cast();
1493       typedef pair<_Base_ptr, _Base_ptr> _Res;
1494
1495       // end()
1496       if (__pos._M_node == _M_end())
1497         {
1498           if (size() > 0
1499               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1500             return _Res(0, _M_rightmost());
1501           else
1502             return _M_get_insert_equal_pos(__k);
1503         }
1504       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1505         {
1506           // First, try before...
1507           iterator __before = __pos;
1508           if (__pos._M_node == _M_leftmost()) // begin()
1509             return _Res(_M_leftmost(), _M_leftmost());
1510           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
1511             {
1512               if (_S_right(__before._M_node) == 0)
1513                 return _Res(0, __before._M_node);
1514               else
1515                 return _Res(__pos._M_node, __pos._M_node);
1516             }
1517           else
1518             return _M_get_insert_equal_pos(__k);
1519         }
1520       else
1521         {
1522           // ... then try after.
1523           iterator __after = __pos;
1524           if (__pos._M_node == _M_rightmost())
1525             return _Res(0, _M_rightmost());
1526           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
1527             {
1528               if (_S_right(__pos._M_node) == 0)
1529                 return _Res(0, __pos._M_node);
1530               else
1531                 return _Res(__after._M_node, __after._M_node);
1532             }
1533           else
1534             return _Res(0, 0);
1535         }
1536     }
1537
1538   template<typename _Key, typename _Val, typename _KeyOfValue,
1539            typename _Compare, typename _Alloc>
1540 #if __cplusplus >= 201103L
1541     template<typename _Arg>
1542 #endif
1543     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1544     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1545 #if __cplusplus >= 201103L
1546     _M_insert_equal_(const_iterator __position, _Arg&& __v)
1547 #else
1548     _M_insert_equal_(const_iterator __position, const _Val& __v)
1549 #endif
1550     {
1551       pair<_Base_ptr, _Base_ptr> __res
1552         = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
1553
1554       if (__res.second)
1555         return _M_insert_(__res.first, __res.second,
1556                           _GLIBCXX_FORWARD(_Arg, __v));
1557
1558       return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1559     }
1560
1561 #if __cplusplus >= 201103L
1562   template<typename _Key, typename _Val, typename _KeyOfValue,
1563            typename _Compare, typename _Alloc>
1564     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1565     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1566     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
1567     {
1568       bool __insert_left = (__x != 0 || __p == _M_end()
1569                             || _M_impl._M_key_compare(_S_key(__z),
1570                                                       _S_key(__p)));
1571
1572       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1573                                     this->_M_impl._M_header);
1574       ++_M_impl._M_node_count;
1575       return iterator(__z);
1576     }
1577
1578   template<typename _Key, typename _Val, typename _KeyOfValue,
1579            typename _Compare, typename _Alloc>
1580     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1581     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1582     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
1583     {
1584       bool __insert_left = (__p == _M_end()
1585                             || !_M_impl._M_key_compare(_S_key(__p),
1586                                                        _S_key(__z)));
1587
1588       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1589                                     this->_M_impl._M_header);
1590       ++_M_impl._M_node_count;
1591       return iterator(__z);
1592     }
1593
1594   template<typename _Key, typename _Val, typename _KeyOfValue,
1595            typename _Compare, typename _Alloc>
1596     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1597     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1598     _M_insert_equal_lower_node(_Link_type __z)
1599     {
1600       _Link_type __x = _M_begin();
1601       _Link_type __y = _M_end();
1602       while (__x != 0)
1603         {
1604           __y = __x;
1605           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
1606                 _S_left(__x) : _S_right(__x);
1607         }
1608       return _M_insert_lower_node(__y, __z);
1609     }
1610
1611   template<typename _Key, typename _Val, typename _KeyOfValue,
1612            typename _Compare, typename _Alloc>
1613     template<typename... _Args>
1614       pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1615                              _Compare, _Alloc>::iterator, bool>
1616       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1617       _M_emplace_unique(_Args&&... __args)
1618       {
1619         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1620
1621         __try
1622           {
1623             typedef pair<iterator, bool> _Res;
1624             auto __res = _M_get_insert_unique_pos(_S_key(__z));
1625             if (__res.second)
1626               return _Res(_M_insert_node(__res.first, __res.second, __z), true);
1627
1628             _M_destroy_node(__z);
1629             return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1630           }
1631         __catch(...)
1632           {
1633             _M_destroy_node(__z);
1634             __throw_exception_again;
1635           }
1636       }
1637
1638   template<typename _Key, typename _Val, typename _KeyOfValue,
1639            typename _Compare, typename _Alloc>
1640     template<typename... _Args>
1641       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1642       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1643       _M_emplace_equal(_Args&&... __args)
1644       {
1645         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1646
1647         __try
1648           {
1649             auto __res = _M_get_insert_equal_pos(_S_key(__z));
1650             return _M_insert_node(__res.first, __res.second, __z);
1651           }
1652         __catch(...)
1653           {
1654             _M_destroy_node(__z);
1655             __throw_exception_again;
1656           }
1657       }
1658
1659   template<typename _Key, typename _Val, typename _KeyOfValue,
1660            typename _Compare, typename _Alloc>
1661     template<typename... _Args>
1662       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1663       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1664       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
1665       {
1666         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1667
1668         __try
1669           {
1670             auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
1671
1672             if (__res.second)
1673               return _M_insert_node(__res.first, __res.second, __z);
1674
1675             _M_destroy_node(__z);
1676             return iterator(static_cast<_Link_type>(__res.first));
1677           }
1678         __catch(...)
1679           {
1680             _M_destroy_node(__z);
1681             __throw_exception_again;
1682           }
1683       }
1684
1685   template<typename _Key, typename _Val, typename _KeyOfValue,
1686            typename _Compare, typename _Alloc>
1687     template<typename... _Args>
1688       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1689       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1690       _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
1691       {
1692         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1693
1694         __try
1695           {
1696             auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
1697
1698             if (__res.second)
1699               return _M_insert_node(__res.first, __res.second, __z);
1700
1701             return _M_insert_equal_lower_node(__z);
1702           }
1703         __catch(...)
1704           {
1705             _M_destroy_node(__z);
1706             __throw_exception_again;
1707           }
1708       }
1709 #endif
1710
1711   template<typename _Key, typename _Val, typename _KoV,
1712            typename _Cmp, typename _Alloc>
1713     template<class _II>
1714       void
1715       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1716       _M_insert_unique(_II __first, _II __last)
1717       {
1718         for (; __first != __last; ++__first)
1719           _M_insert_unique_(end(), *__first);
1720       }
1721
1722   template<typename _Key, typename _Val, typename _KoV,
1723            typename _Cmp, typename _Alloc>
1724     template<class _II>
1725       void
1726       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1727       _M_insert_equal(_II __first, _II __last)
1728       {
1729         for (; __first != __last; ++__first)
1730           _M_insert_equal_(end(), *__first);
1731       }
1732
1733   template<typename _Key, typename _Val, typename _KeyOfValue,
1734            typename _Compare, typename _Alloc>
1735     void
1736     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1737     _M_erase_aux(const_iterator __position)
1738     {
1739       _Link_type __y =
1740         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1741                                 (const_cast<_Base_ptr>(__position._M_node),
1742                                  this->_M_impl._M_header));
1743       _M_destroy_node(__y);
1744       --_M_impl._M_node_count;
1745     }
1746
1747   template<typename _Key, typename _Val, typename _KeyOfValue,
1748            typename _Compare, typename _Alloc>
1749     void
1750     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1751     _M_erase_aux(const_iterator __first, const_iterator __last)
1752     {
1753       if (__first == begin() && __last == end())
1754         clear();
1755       else
1756         while (__first != __last)
1757           erase(__first++);
1758     }
1759
1760   template<typename _Key, typename _Val, typename _KeyOfValue,
1761            typename _Compare, typename _Alloc>
1762     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1763     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1764     erase(const _Key& __x)
1765     {
1766       pair<iterator, iterator> __p = equal_range(__x);
1767       const size_type __old_size = size();
1768       erase(__p.first, __p.second);
1769       return __old_size - size();
1770     }
1771
1772   template<typename _Key, typename _Val, typename _KeyOfValue,
1773            typename _Compare, typename _Alloc>
1774     void
1775     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1776     erase(const _Key* __first, const _Key* __last)
1777     {
1778       while (__first != __last)
1779         erase(*__first++);
1780     }
1781
1782   template<typename _Key, typename _Val, typename _KeyOfValue,
1783            typename _Compare, typename _Alloc>
1784     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1785                       _Compare, _Alloc>::iterator
1786     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1787     find(const _Key& __k)
1788     {
1789       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1790       return (__j == end()
1791               || _M_impl._M_key_compare(__k,
1792                                         _S_key(__j._M_node))) ? end() : __j;
1793     }
1794
1795   template<typename _Key, typename _Val, typename _KeyOfValue,
1796            typename _Compare, typename _Alloc>
1797     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1798                       _Compare, _Alloc>::const_iterator
1799     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1800     find(const _Key& __k) const
1801     {
1802       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1803       return (__j == end()
1804               || _M_impl._M_key_compare(__k,
1805                                         _S_key(__j._M_node))) ? end() : __j;
1806     }
1807
1808   template<typename _Key, typename _Val, typename _KeyOfValue,
1809            typename _Compare, typename _Alloc>
1810     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1811     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1812     count(const _Key& __k) const
1813     {
1814       pair<const_iterator, const_iterator> __p = equal_range(__k);
1815       const size_type __n = std::distance(__p.first, __p.second);
1816       return __n;
1817     }
1818
1819   _GLIBCXX_PURE unsigned int
1820   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1821                        const _Rb_tree_node_base* __root) throw ();
1822
1823   template<typename _Key, typename _Val, typename _KeyOfValue,
1824            typename _Compare, typename _Alloc>
1825     bool
1826     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1827     {
1828       if (_M_impl._M_node_count == 0 || begin() == end())
1829         return _M_impl._M_node_count == 0 && begin() == end()
1830                && this->_M_impl._M_header._M_left == _M_end()
1831                && this->_M_impl._M_header._M_right == _M_end();
1832
1833       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1834       for (const_iterator __it = begin(); __it != end(); ++__it)
1835         {
1836           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1837           _Const_Link_type __L = _S_left(__x);
1838           _Const_Link_type __R = _S_right(__x);
1839
1840           if (__x->_M_color == _S_red)
1841             if ((__L && __L->_M_color == _S_red)
1842                 || (__R && __R->_M_color == _S_red))
1843               return false;
1844
1845           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1846             return false;
1847           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1848             return false;
1849
1850           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1851             return false;
1852         }
1853
1854       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1855         return false;
1856       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1857         return false;
1858       return true;
1859     }
1860
1861 _GLIBCXX_END_NAMESPACE_VERSION
1862 } // namespace
1863
1864 #endif