contrib/libstdc++/include/bits/stl_tree.h

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1996,1997
  34  * Silicon Graphics Computer Systems, Inc.
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Silicon Graphics makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1994
  46  * Hewlett-Packard Company
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Hewlett-Packard Company makes no
  53  * representations about the suitability of this software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  *
  56  *
  57  */
  58
  59 /** @file stl_tree.h
  60  *  This is an internal header file, included by other library headers.
  61  *  You should not attempt to use it directly.
  62  */
  63
  64 #ifndef _TREE_H
  65 #define _TREE_H 1
  66
  67 #pragma GCC system_header
  68
  69 #include <bits/stl_algobase.h>
  70 #include <bits/allocator.h>
  71 #include <bits/stl_construct.h>
  72 #include <bits/stl_function.h>
  73 #include <bits/cpp_type_traits.h>
  74
  75 _GLIBCXX_BEGIN_NAMESPACE(std)
  76
  77   // Red-black tree class, designed for use in implementing STL
  78   // associative containers (set, multiset, map, and multimap). The
  79   // insertion and deletion algorithms are based on those in Cormen,
  80   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  81   // 1990), except that
  82   //
  83   // (1) the header cell is maintained with links not only to the root
  84   // but also to the leftmost node of the tree, to enable constant
  85   // time begin(), and to the rightmost node of the tree, to enable
  86   // linear time performance when used with the generic set algorithms
  87   // (set_union, etc.)
  88   //
  89   // (2) when a node being deleted has two children its successor node
  90   // is relinked into its place, rather than copied, so that the only
  91   // iterators invalidated are those referring to the deleted node.
  92
  93   enum _Rb_tree_color { _S_red = false, _S_black = true };
  94
  95   struct _Rb_tree_node_base
  96   {
  97     typedef _Rb_tree_node_base* _Base_ptr;
  98     typedef const _Rb_tree_node_base* _Const_Base_ptr;
  99
 100     _Rb_tree_color      _M_color;
 101     _Base_ptr           _M_parent;
 102     _Base_ptr           _M_left;
 103     _Base_ptr           _M_right;
 104
 105     static _Base_ptr
 106     _S_minimum(_Base_ptr __x)
 107     {
 108       while (__x->_M_left != 0) __x = __x->_M_left;
 109       return __x;
 110     }
 111
 112     static _Const_Base_ptr
 113     _S_minimum(_Const_Base_ptr __x)
 114     {
 115       while (__x->_M_left != 0) __x = __x->_M_left;
 116       return __x;
 117     }
 118
 119     static _Base_ptr
 120     _S_maximum(_Base_ptr __x)
 121     {
 122       while (__x->_M_right != 0) __x = __x->_M_right;
 123       return __x;
 124     }
 125
 126     static _Const_Base_ptr
 127     _S_maximum(_Const_Base_ptr __x)
 128     {
 129       while (__x->_M_right != 0) __x = __x->_M_right;
 130       return __x;
 131     }
 132   };
 133
 134   template<typename _Val>
 135     struct _Rb_tree_node : public _Rb_tree_node_base
 136     {
 137       typedef _Rb_tree_node<_Val>* _Link_type;
 138       _Val _M_value_field;
 139     };
 140
 141   _Rb_tree_node_base*
 142   _Rb_tree_increment(_Rb_tree_node_base* __x);
 143
 144   const _Rb_tree_node_base*
 145   _Rb_tree_increment(const _Rb_tree_node_base* __x);
 146
 147   _Rb_tree_node_base*
 148   _Rb_tree_decrement(_Rb_tree_node_base* __x);
 149
 150   const _Rb_tree_node_base*
 151   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
 152
 153   template<typename _Tp>
 154     struct _Rb_tree_iterator
 155     {
 156       typedef _Tp  value_type;
 157       typedef _Tp& reference;
 158       typedef _Tp* pointer;
 159
 160       typedef bidirectional_iterator_tag iterator_category;
 161       typedef ptrdiff_t                  difference_type;
 162
 163       typedef _Rb_tree_iterator<_Tp>        _Self;
 164       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 165       typedef _Rb_tree_node<_Tp>*           _Link_type;
 166
 167       _Rb_tree_iterator()
 168       : _M_node() { }
 169
 170       explicit
 171       _Rb_tree_iterator(_Link_type __x)
 172       : _M_node(__x) { }
 173
 174       reference
 175       operator*() const
 176       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 177
 178       pointer
 179       operator->() const
 180       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 181
 182       _Self&
 183       operator++()
 184       {
 185         _M_node = _Rb_tree_increment(_M_node);
 186         return *this;
 187       }
 188
 189       _Self
 190       operator++(int)
 191       {
 192         _Self __tmp = *this;
 193         _M_node = _Rb_tree_increment(_M_node);
 194         return __tmp;
 195       }
 196
 197       _Self&
 198       operator--()
 199       {
 200         _M_node = _Rb_tree_decrement(_M_node);
 201         return *this;
 202       }
 203
 204       _Self
 205       operator--(int)
 206       {
 207         _Self __tmp = *this;
 208         _M_node = _Rb_tree_decrement(_M_node);
 209         return __tmp;
 210       }
 211
 212       bool
 213       operator==(const _Self& __x) const
 214       { return _M_node == __x._M_node; }
 215
 216       bool
 217       operator!=(const _Self& __x) const
 218       { return _M_node != __x._M_node; }
 219
 220       _Base_ptr _M_node;
 221   };
 222
 223   template<typename _Tp>
 224     struct _Rb_tree_const_iterator
 225     {
 226       typedef _Tp        value_type;
 227       typedef const _Tp& reference;
 228       typedef const _Tp* pointer;
 229
 230       typedef _Rb_tree_iterator<_Tp> iterator;
 231
 232       typedef bidirectional_iterator_tag iterator_category;
 233       typedef ptrdiff_t                  difference_type;
 234
 235       typedef _Rb_tree_const_iterator<_Tp>        _Self;
 236       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
 237       typedef const _Rb_tree_node<_Tp>*           _Link_type;
 238
 239       _Rb_tree_const_iterator()
 240       : _M_node() { }
 241
 242       explicit
 243       _Rb_tree_const_iterator(_Link_type __x)
 244       : _M_node(__x) { }
 245
 246       _Rb_tree_const_iterator(const iterator& __it)
 247       : _M_node(__it._M_node) { }
 248
 249       reference
 250       operator*() const
 251       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 252
 253       pointer
 254       operator->() const
 255       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 256
 257       _Self&
 258       operator++()
 259       {
 260         _M_node = _Rb_tree_increment(_M_node);
 261         return *this;
 262       }
 263
 264       _Self
 265       operator++(int)
 266       {
 267         _Self __tmp = *this;
 268         _M_node = _Rb_tree_increment(_M_node);
 269         return __tmp;
 270       }
 271
 272       _Self&
 273       operator--()
 274       {
 275         _M_node = _Rb_tree_decrement(_M_node);
 276         return *this;
 277       }
 278
 279       _Self
 280       operator--(int)
 281       {
 282         _Self __tmp = *this;
 283         _M_node = _Rb_tree_decrement(_M_node);
 284         return __tmp;
 285       }
 286
 287       bool
 288       operator==(const _Self& __x) const
 289       { return _M_node == __x._M_node; }
 290
 291       bool
 292       operator!=(const _Self& __x) const
 293       { return _M_node != __x._M_node; }
 294
 295       _Base_ptr _M_node;
 296     };
 297
 298   template<typename _Val>
 299     inline bool
 300     operator==(const _Rb_tree_iterator<_Val>& __x,
 301                const _Rb_tree_const_iterator<_Val>& __y)
 302     { return __x._M_node == __y._M_node; }
 303
 304   template<typename _Val>
 305     inline bool
 306     operator!=(const _Rb_tree_iterator<_Val>& __x,
 307                const _Rb_tree_const_iterator<_Val>& __y)
 308     { return __x._M_node != __y._M_node; }
 309
 310   void
 311   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
 312                        _Rb_tree_node_base*& __root);
 313
 314   void
 315   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
 316                         _Rb_tree_node_base*& __root);
 317
 318   void
 319   _Rb_tree_insert_and_rebalance(const bool __insert_left,
 320                                 _Rb_tree_node_base* __x,
 321                                 _Rb_tree_node_base* __p,
 322                                 _Rb_tree_node_base& __header);
 323
 324   _Rb_tree_node_base*
 325   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 326                                _Rb_tree_node_base& __header);
 327
 328
 329   template<typename _Key, typename _Val, typename _KeyOfValue,
 330            typename _Compare, typename _Alloc = allocator<_Val> >
 331     class _Rb_tree
 332     {
 333       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 334               _Node_allocator;
 335
 336     protected:
 337       typedef _Rb_tree_node_base* _Base_ptr;
 338       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 339       typedef _Rb_tree_node<_Val> _Rb_tree_node;
 340
 341     public:
 342       typedef _Key key_type;
 343       typedef _Val value_type;
 344       typedef value_type* pointer;
 345       typedef const value_type* const_pointer;
 346       typedef value_type& reference;
 347       typedef const value_type& const_reference;
 348       typedef _Rb_tree_node* _Link_type;
 349       typedef const _Rb_tree_node* _Const_Link_type;
 350       typedef size_t size_type;
 351       typedef ptrdiff_t difference_type;
 352       typedef _Alloc allocator_type;
 353
 354       _Node_allocator&
 355       _M_get_Node_allocator()
 356       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
 357
 358       const _Node_allocator&
 359       _M_get_Node_allocator() const
 360       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 361
 362       allocator_type
 363       get_allocator() const
 364       { return allocator_type(_M_get_Node_allocator()); }
 365
 366     protected:
 367       _Rb_tree_node*
 368       _M_get_node()
 369       { return _M_impl._Node_allocator::allocate(1); }
 370
 371       void
 372       _M_put_node(_Rb_tree_node* __p)
 373       { _M_impl._Node_allocator::deallocate(__p, 1); }
 374
 375       _Link_type
 376       _M_create_node(const value_type& __x)
 377       {
 378         _Link_type __tmp = _M_get_node();
 379         try
 380           { get_allocator().construct(&__tmp->_M_value_field, __x); }
 381         catch(...)
 382           {
 383             _M_put_node(__tmp);
 384             __throw_exception_again;
 385           }
 386         return __tmp;
 387       }
 388
 389       _Link_type
 390       _M_clone_node(_Const_Link_type __x)
 391       {
 392         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 393         __tmp->_M_color = __x->_M_color;
 394         __tmp->_M_left = 0;
 395         __tmp->_M_right = 0;
 396         return __tmp;
 397       }
 398
 399       void
 400       _M_destroy_node(_Link_type __p)
 401       {
 402         get_allocator().destroy(&__p->_M_value_field);
 403         _M_put_node(__p);
 404       }
 405
 406     protected:
 407       template<typename _Key_compare,
 408                bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
 409         struct _Rb_tree_impl : public _Node_allocator
 410         {
 411           _Key_compare          _M_key_compare;
 412           _Rb_tree_node_base    _M_header;
 413           size_type             _M_node_count; // Keeps track of size of tree.
 414
 415           _Rb_tree_impl()
 416           : _Node_allocator(), _M_key_compare(), _M_header(),
 417             _M_node_count(0)
 418           { _M_initialize(); }
 419
 420           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
 421           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 422             _M_node_count(0)
 423           { _M_initialize(); }
 424
 425         private:
 426           void
 427           _M_initialize()
 428           {
 429             this->_M_header._M_color = _S_red;
 430             this->_M_header._M_parent = 0;
 431             this->_M_header._M_left = &this->_M_header;
 432             this->_M_header._M_right = &this->_M_header;
 433           }
 434         };
 435
 436       // Specialization for _Comparison types that are not capable of
 437       // being base classes / super classes.
 438       template<typename _Key_compare>
 439         struct _Rb_tree_impl<_Key_compare, true> : 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         private:
 456           void
 457           _M_initialize()
 458           {
 459             this->_M_header._M_color = _S_red;
 460             this->_M_header._M_parent = 0;
 461             this->_M_header._M_left = &this->_M_header;
 462             this->_M_header._M_right = &this->_M_header;
 463           }
 464         };
 465
 466       _Rb_tree_impl<_Compare> _M_impl;
 467
 468     protected:
 469       _Base_ptr&
 470       _M_root()
 471       { return this->_M_impl._M_header._M_parent; }
 472
 473       _Const_Base_ptr
 474       _M_root() const
 475       { return this->_M_impl._M_header._M_parent; }
 476
 477       _Base_ptr&
 478       _M_leftmost()
 479       { return this->_M_impl._M_header._M_left; }
 480
 481       _Const_Base_ptr
 482       _M_leftmost() const
 483       { return this->_M_impl._M_header._M_left; }
 484
 485       _Base_ptr&
 486       _M_rightmost()
 487       { return this->_M_impl._M_header._M_right; }
 488
 489       _Const_Base_ptr
 490       _M_rightmost() const
 491       { return this->_M_impl._M_header._M_right; }
 492
 493       _Link_type
 494       _M_begin()
 495       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 496
 497       _Const_Link_type
 498       _M_begin() const
 499       {
 500         return static_cast<_Const_Link_type>
 501           (this->_M_impl._M_header._M_parent);
 502       }
 503
 504       _Link_type
 505       _M_end()
 506       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 507
 508       _Const_Link_type
 509       _M_end() const
 510       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 511
 512       static const_reference
 513       _S_value(_Const_Link_type __x)
 514       { return __x->_M_value_field; }
 515
 516       static const _Key&
 517       _S_key(_Const_Link_type __x)
 518       { return _KeyOfValue()(_S_value(__x)); }
 519
 520       static _Link_type
 521       _S_left(_Base_ptr __x)
 522       { return static_cast<_Link_type>(__x->_M_left); }
 523
 524       static _Const_Link_type
 525       _S_left(_Const_Base_ptr __x)
 526       { return static_cast<_Const_Link_type>(__x->_M_left); }
 527
 528       static _Link_type
 529       _S_right(_Base_ptr __x)
 530       { return static_cast<_Link_type>(__x->_M_right); }
 531
 532       static _Const_Link_type
 533       _S_right(_Const_Base_ptr __x)
 534       { return static_cast<_Const_Link_type>(__x->_M_right); }
 535
 536       static const_reference
 537       _S_value(_Const_Base_ptr __x)
 538       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 539
 540       static const _Key&
 541       _S_key(_Const_Base_ptr __x)
 542       { return _KeyOfValue()(_S_value(__x)); }
 543
 544       static _Base_ptr
 545       _S_minimum(_Base_ptr __x)
 546       { return _Rb_tree_node_base::_S_minimum(__x); }
 547
 548       static _Const_Base_ptr
 549       _S_minimum(_Const_Base_ptr __x)
 550       { return _Rb_tree_node_base::_S_minimum(__x); }
 551
 552       static _Base_ptr
 553       _S_maximum(_Base_ptr __x)
 554       { return _Rb_tree_node_base::_S_maximum(__x); }
 555
 556       static _Const_Base_ptr
 557       _S_maximum(_Const_Base_ptr __x)
 558       { return _Rb_tree_node_base::_S_maximum(__x); }
 559
 560     public:
 561       typedef _Rb_tree_iterator<value_type>       iterator;
 562       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 563
 564       typedef std::reverse_iterator<iterator>       reverse_iterator;
 565       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 566
 567     private:
 568       iterator
 569       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 570
 571       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 572       // 233. Insertion hints in associative containers.
 573       iterator
 574       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 575
 576       const_iterator
 577       _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
 578                 const value_type& __v);
 579
 580       _Link_type
 581       _M_copy(_Const_Link_type __x, _Link_type __p);
 582
 583       void
 584       _M_erase(_Link_type __x);
 585
 586     public:
 587       // allocation/deallocation
 588       _Rb_tree()
 589       { }
 590
 591       _Rb_tree(const _Compare& __comp,
 592                const allocator_type& __a = allocator_type())
 593       : _M_impl(__comp, __a)
 594       { }
 595
 596       _Rb_tree(const _Rb_tree& __x)
 597       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
 598       {
 599         if (__x._M_root() != 0)
 600           {
 601             _M_root() = _M_copy(__x._M_begin(), _M_end());
 602             _M_leftmost() = _S_minimum(_M_root());
 603             _M_rightmost() = _S_maximum(_M_root());
 604             _M_impl._M_node_count = __x._M_impl._M_node_count;
 605           }
 606       }
 607
 608       ~_Rb_tree()
 609       { _M_erase(_M_begin()); }
 610
 611       _Rb_tree&
 612       operator=(const _Rb_tree& __x);
 613
 614       // Accessors.
 615       _Compare
 616       key_comp() const
 617       { return _M_impl._M_key_compare; }
 618
 619       iterator
 620       begin()
 621       {
 622         return iterator(static_cast<_Link_type>
 623                         (this->_M_impl._M_header._M_left));
 624       }
 625
 626       const_iterator
 627       begin() const
 628       {
 629         return const_iterator(static_cast<_Const_Link_type>
 630                               (this->_M_impl._M_header._M_left));
 631       }
 632
 633       iterator
 634       end()
 635       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 636
 637       const_iterator
 638       end() const
 639       {
 640         return const_iterator(static_cast<_Const_Link_type>
 641                               (&this->_M_impl._M_header));
 642       }
 643
 644       reverse_iterator
 645       rbegin()
 646       { return reverse_iterator(end()); }
 647
 648       const_reverse_iterator
 649       rbegin() const
 650       { return const_reverse_iterator(end()); }
 651
 652       reverse_iterator
 653       rend()
 654       { return reverse_iterator(begin()); }
 655
 656       const_reverse_iterator
 657       rend() const
 658       { return const_reverse_iterator(begin()); }
 659
 660       bool
 661       empty() const
 662       { return _M_impl._M_node_count == 0; }
 663
 664       size_type
 665       size() const
 666       { return _M_impl._M_node_count; }
 667
 668       size_type
 669       max_size() const
 670       { return get_allocator().max_size(); }
 671
 672       void
 673       swap(_Rb_tree& __t);
 674
 675       // Insert/erase.
 676       pair<iterator, bool>
 677       _M_insert_unique(const value_type& __x);
 678
 679       iterator
 680       _M_insert_equal(const value_type& __x);
 681
 682       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 683       // 233. Insertion hints in associative containers.
 684       iterator
 685       _M_insert_equal_lower(const value_type& __x);
 686
 687       iterator
 688       _M_insert_unique(iterator __position, const value_type& __x);
 689
 690       const_iterator
 691       _M_insert_unique(const_iterator __position, const value_type& __x);
 692
 693       iterator
 694       _M_insert_equal(iterator __position, const value_type& __x);
 695
 696       const_iterator
 697       _M_insert_equal(const_iterator __position, const value_type& __x);
 698
 699       template<typename _InputIterator>
 700         void
 701         _M_insert_unique(_InputIterator __first, _InputIterator __last);
 702
 703       template<typename _InputIterator>
 704         void
 705         _M_insert_equal(_InputIterator __first, _InputIterator __last);
 706
 707       void
 708       erase(iterator __position);
 709
 710       void
 711       erase(const_iterator __position);
 712
 713       size_type
 714       erase(const key_type& __x);
 715
 716       void
 717       erase(iterator __first, iterator __last);
 718
 719       void
 720       erase(const_iterator __first, const_iterator __last);
 721
 722       void
 723       erase(const key_type* __first, const key_type* __last);
 724
 725       void
 726       clear()
 727       {
 728         _M_erase(_M_begin());
 729         _M_leftmost() = _M_end();
 730         _M_root() = 0;
 731         _M_rightmost() = _M_end();
 732         _M_impl._M_node_count = 0;
 733       }
 734
 735       // Set operations.
 736       iterator
 737       find(const key_type& __x);
 738
 739       const_iterator
 740       find(const key_type& __x) const;
 741
 742       size_type
 743       count(const key_type& __x) const;
 744
 745       iterator
 746       lower_bound(const key_type& __x);
 747
 748       const_iterator
 749       lower_bound(const key_type& __x) const;
 750
 751       iterator
 752       upper_bound(const key_type& __x);
 753
 754       const_iterator
 755       upper_bound(const key_type& __x) const;
 756
 757       pair<iterator,iterator>
 758       equal_range(const key_type& __x);
 759
 760       pair<const_iterator, const_iterator>
 761       equal_range(const key_type& __x) const;
 762
 763       // Debugging.
 764       bool
 765       __rb_verify() const;
 766     };
 767
 768   template<typename _Key, typename _Val, typename _KeyOfValue,
 769            typename _Compare, typename _Alloc>
 770     inline bool
 771     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 772                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 773     {
 774       return __x.size() == __y.size()
 775              && std::equal(__x.begin(), __x.end(), __y.begin());
 776     }
 777
 778   template<typename _Key, typename _Val, typename _KeyOfValue,
 779            typename _Compare, typename _Alloc>
 780     inline bool
 781     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 782               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 783     {
 784       return std::lexicographical_compare(__x.begin(), __x.end(),
 785                                           __y.begin(), __y.end());
 786     }
 787
 788   template<typename _Key, typename _Val, typename _KeyOfValue,
 789            typename _Compare, typename _Alloc>
 790     inline bool
 791     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 792                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 793     { return !(__x == __y); }
 794
 795   template<typename _Key, typename _Val, typename _KeyOfValue,
 796            typename _Compare, typename _Alloc>
 797     inline bool
 798     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 799               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 800     { return __y < __x; }
 801
 802   template<typename _Key, typename _Val, typename _KeyOfValue,
 803            typename _Compare, typename _Alloc>
 804     inline bool
 805     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 806                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 807     { return !(__y < __x); }
 808
 809   template<typename _Key, typename _Val, typename _KeyOfValue,
 810            typename _Compare, typename _Alloc>
 811     inline bool
 812     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 813                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 814     { return !(__x < __y); }
 815
 816   template<typename _Key, typename _Val, typename _KeyOfValue,
 817            typename _Compare, typename _Alloc>
 818     inline void
 819     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 820          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 821     { __x.swap(__y); }
 822
 823   template<typename _Key, typename _Val, typename _KeyOfValue,
 824            typename _Compare, typename _Alloc>
 825     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 826     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 827     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 828     {
 829       if (this != &__x)
 830         {
 831           // Note that _Key may be a constant type.
 832           clear();
 833           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 834           if (__x._M_root() != 0)
 835             {
 836               _M_root() = _M_copy(__x._M_begin(), _M_end());
 837               _M_leftmost() = _S_minimum(_M_root());
 838               _M_rightmost() = _S_maximum(_M_root());
 839               _M_impl._M_node_count = __x._M_impl._M_node_count;
 840             }
 841         }
 842       return *this;
 843     }
 844
 845   template<typename _Key, typename _Val, typename _KeyOfValue,
 846            typename _Compare, typename _Alloc>
 847     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 848     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 849     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 850     {
 851       bool __insert_left = (__x != 0 || __p == _M_end()
 852                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 853                                                       _S_key(__p)));
 854
 855       _Link_type __z = _M_create_node(__v);
 856
 857       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 858                                     this->_M_impl._M_header);
 859       ++_M_impl._M_node_count;
 860       return iterator(__z);
 861     }
 862
 863   template<typename _Key, typename _Val, typename _KeyOfValue,
 864            typename _Compare, typename _Alloc>
 865     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 866     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 867     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 868     {
 869       bool __insert_left = (__x != 0 || __p == _M_end()
 870                             || !_M_impl._M_key_compare(_S_key(__p),
 871                                                        _KeyOfValue()(__v)));
 872
 873       _Link_type __z = _M_create_node(__v);
 874
 875       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 876                                     this->_M_impl._M_header);
 877       ++_M_impl._M_node_count;
 878       return iterator(__z);
 879     }
 880
 881   template<typename _Key, typename _Val, typename _KeyOfValue,
 882            typename _Compare, typename _Alloc>
 883     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
 884     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 885     _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
 886     {
 887       bool __insert_left = (__x != 0 || __p == _M_end()
 888                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 889                                                       _S_key(__p)));
 890
 891       _Link_type __z = _M_create_node(__v);
 892
 893       _Rb_tree_insert_and_rebalance(__insert_left, __z,
 894                                     const_cast<_Base_ptr>(__p),
 895                                     this->_M_impl._M_header);
 896       ++_M_impl._M_node_count;
 897       return const_iterator(__z);
 898     }
 899
 900   template<typename _Key, typename _Val, typename _KeyOfValue,
 901            typename _Compare, typename _Alloc>
 902     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 903     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 904     _M_insert_equal(const _Val& __v)
 905     {
 906       _Link_type __x = _M_begin();
 907       _Link_type __y = _M_end();
 908       while (__x != 0)
 909         {
 910           __y = __x;
 911           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 912                 _S_left(__x) : _S_right(__x);
 913         }
 914       return _M_insert(__x, __y, __v);
 915     }
 916
 917   template<typename _Key, typename _Val, typename _KeyOfValue,
 918            typename _Compare, typename _Alloc>
 919     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 920     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 921     _M_insert_equal_lower(const _Val& __v)
 922     {
 923       _Link_type __x = _M_begin();
 924       _Link_type __y = _M_end();
 925       while (__x != 0)
 926         {
 927           __y = __x;
 928           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
 929                 _S_left(__x) : _S_right(__x);
 930         }
 931       return _M_insert_lower(__x, __y, __v);
 932     }
 933
 934   template<typename _Key, typename _Val, typename _KeyOfValue,
 935            typename _Compare, typename _Alloc>
 936     void
 937     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 938     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
 939     {
 940       if (_M_root() == 0)
 941         {
 942           if (__t._M_root() != 0)
 943             {
 944               _M_root() = __t._M_root();
 945               _M_leftmost() = __t._M_leftmost();
 946               _M_rightmost() = __t._M_rightmost();
 947               _M_root()->_M_parent = _M_end();
 948
 949               __t._M_root() = 0;
 950               __t._M_leftmost() = __t._M_end();
 951               __t._M_rightmost() = __t._M_end();
 952             }
 953         }
 954       else if (__t._M_root() == 0)
 955         {
 956           __t._M_root() = _M_root();
 957           __t._M_leftmost() = _M_leftmost();
 958           __t._M_rightmost() = _M_rightmost();
 959           __t._M_root()->_M_parent = __t._M_end();
 960
 961           _M_root() = 0;
 962           _M_leftmost() = _M_end();
 963           _M_rightmost() = _M_end();
 964         }
 965       else
 966         {
 967           std::swap(_M_root(),__t._M_root());
 968           std::swap(_M_leftmost(),__t._M_leftmost());
 969           std::swap(_M_rightmost(),__t._M_rightmost());
 970
 971           _M_root()->_M_parent = _M_end();
 972           __t._M_root()->_M_parent = __t._M_end();
 973         }
 974       // No need to swap header's color as it does not change.
 975       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 976       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 977
 978       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 979       // 431. Swapping containers with unequal allocators.
 980       std::__alloc_swap<_Node_allocator>::
 981         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
 982     }
 983
 984   template<typename _Key, typename _Val, typename _KeyOfValue,
 985            typename _Compare, typename _Alloc>
 986     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 987                            _Compare, _Alloc>::iterator, bool>
 988     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 989     _M_insert_unique(const _Val& __v)
 990     {
 991       _Link_type __x = _M_begin();
 992       _Link_type __y = _M_end();
 993       bool __comp = true;
 994       while (__x != 0)
 995         {
 996           __y = __x;
 997           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 998           __x = __comp ? _S_left(__x) : _S_right(__x);
 999         }
1000       iterator __j = iterator(__y);
1001       if (__comp)
1002         {
1003           if (__j == begin())
1004             return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
1005           else
1006             --__j;
1007         }
1008       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1009         return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
1010       return pair<iterator, bool>(__j, false);
1011     }
1012
1013   template<typename _Key, typename _Val, typename _KeyOfValue,
1014            typename _Compare, typename _Alloc>
1015     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1016     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1017     _M_insert_unique(iterator __position, const _Val& __v)
1018     {
1019       // end()
1020       if (__position._M_node == _M_end())
1021         {
1022           if (size() > 0
1023               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1024                                         _KeyOfValue()(__v)))
1025             return _M_insert(0, _M_rightmost(), __v);
1026           else
1027             return _M_insert_unique(__v).first;
1028         }
1029       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1030                                       _S_key(__position._M_node)))
1031         {
1032           // First, try before...
1033           iterator __before = __position;
1034           if (__position._M_node == _M_leftmost()) // begin()
1035             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1036           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1037                                           _KeyOfValue()(__v)))
1038             {
1039               if (_S_right(__before._M_node) == 0)
1040                 return _M_insert(0, __before._M_node, __v);
1041               else
1042                 return _M_insert(__position._M_node,
1043                                  __position._M_node, __v);
1044             }
1045           else
1046             return _M_insert_unique(__v).first;
1047         }
1048       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1049                                       _KeyOfValue()(__v)))
1050         {
1051           // ... then try after.
1052           iterator __after = __position;
1053           if (__position._M_node == _M_rightmost())
1054             return _M_insert(0, _M_rightmost(), __v);
1055           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1056                                           _S_key((++__after)._M_node)))
1057             {
1058               if (_S_right(__position._M_node) == 0)
1059                 return _M_insert(0, __position._M_node, __v);
1060               else
1061                 return _M_insert(__after._M_node, __after._M_node, __v);
1062             }
1063           else
1064             return _M_insert_unique(__v).first;
1065         }
1066       else
1067         return __position; // Equivalent keys.
1068     }
1069
1070   template<typename _Key, typename _Val, typename _KeyOfValue,
1071            typename _Compare, typename _Alloc>
1072     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1073     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1074     _M_insert_unique(const_iterator __position, const _Val& __v)
1075     {
1076       // end()
1077       if (__position._M_node == _M_end())
1078         {
1079           if (size() > 0
1080               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1081                                         _KeyOfValue()(__v)))
1082             return _M_insert(0, _M_rightmost(), __v);
1083           else
1084             return const_iterator(_M_insert_unique(__v).first);
1085         }
1086       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1087                                       _S_key(__position._M_node)))
1088         {
1089           // First, try before...
1090           const_iterator __before = __position;
1091           if (__position._M_node == _M_leftmost()) // begin()
1092             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1093           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1094                                           _KeyOfValue()(__v)))
1095             {
1096               if (_S_right(__before._M_node) == 0)
1097                 return _M_insert(0, __before._M_node, __v);
1098               else
1099                 return _M_insert(__position._M_node,
1100                                  __position._M_node, __v);
1101             }
1102           else
1103             return const_iterator(_M_insert_unique(__v).first);
1104         }
1105       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1106                                       _KeyOfValue()(__v)))
1107         {
1108           // ... then try after.
1109           const_iterator __after = __position;
1110           if (__position._M_node == _M_rightmost())
1111             return _M_insert(0, _M_rightmost(), __v);
1112           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1113                                           _S_key((++__after)._M_node)))
1114             {
1115               if (_S_right(__position._M_node) == 0)
1116                 return _M_insert(0, __position._M_node, __v);
1117               else
1118                 return _M_insert(__after._M_node, __after._M_node, __v);
1119             }
1120           else
1121             return const_iterator(_M_insert_unique(__v).first);
1122         }
1123       else
1124         return __position; // Equivalent keys.
1125     }
1126
1127   template<typename _Key, typename _Val, typename _KeyOfValue,
1128            typename _Compare, typename _Alloc>
1129     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1130     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1131     _M_insert_equal(iterator __position, const _Val& __v)
1132     {
1133       // end()
1134       if (__position._M_node == _M_end())
1135         {
1136           if (size() > 0
1137               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1138                                          _S_key(_M_rightmost())))
1139             return _M_insert(0, _M_rightmost(), __v);
1140           else
1141             return _M_insert_equal(__v);
1142         }
1143       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1144                                        _KeyOfValue()(__v)))
1145         {
1146           // First, try before...
1147           iterator __before = __position;
1148           if (__position._M_node == _M_leftmost()) // begin()
1149             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1150           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1151                                            _S_key((--__before)._M_node)))
1152             {
1153               if (_S_right(__before._M_node) == 0)
1154                 return _M_insert(0, __before._M_node, __v);
1155               else
1156                 return _M_insert(__position._M_node,
1157                                  __position._M_node, __v);
1158             }
1159           else
1160             return _M_insert_equal(__v);
1161         }
1162       else
1163         {
1164           // ... then try after.
1165           iterator __after = __position;
1166           if (__position._M_node == _M_rightmost())
1167             return _M_insert(0, _M_rightmost(), __v);
1168           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1169                                            _KeyOfValue()(__v)))
1170             {
1171               if (_S_right(__position._M_node) == 0)
1172                 return _M_insert(0, __position._M_node, __v);
1173               else
1174                 return _M_insert(__after._M_node, __after._M_node, __v);
1175             }
1176           else
1177             return _M_insert_equal_lower(__v);
1178         }
1179     }
1180
1181   template<typename _Key, typename _Val, typename _KeyOfValue,
1182            typename _Compare, typename _Alloc>
1183     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1184     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1185     _M_insert_equal(const_iterator __position, const _Val& __v)
1186     {
1187       // end()
1188       if (__position._M_node == _M_end())
1189         {
1190           if (size() > 0
1191               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1192                                          _S_key(_M_rightmost())))
1193             return _M_insert(0, _M_rightmost(), __v);
1194           else
1195             return const_iterator(_M_insert_equal(__v));
1196         }
1197       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1198                                        _KeyOfValue()(__v)))
1199         {
1200           // First, try before...
1201           const_iterator __before = __position;
1202           if (__position._M_node == _M_leftmost()) // begin()
1203             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1204           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1205                                            _S_key((--__before)._M_node)))
1206             {
1207               if (_S_right(__before._M_node) == 0)
1208                 return _M_insert(0, __before._M_node, __v);
1209               else
1210                 return _M_insert(__position._M_node,
1211                                  __position._M_node, __v);
1212             }
1213           else
1214             return const_iterator(_M_insert_equal(__v));
1215         }
1216       else
1217         {
1218           // ... then try after.
1219           const_iterator __after = __position;
1220           if (__position._M_node == _M_rightmost())
1221             return _M_insert(0, _M_rightmost(), __v);
1222           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1223                                            _KeyOfValue()(__v)))
1224             {
1225               if (_S_right(__position._M_node) == 0)
1226                 return _M_insert(0, __position._M_node, __v);
1227               else
1228                 return _M_insert(__after._M_node, __after._M_node, __v);
1229             }
1230           else
1231             return const_iterator(_M_insert_equal_lower(__v));
1232         }
1233     }
1234
1235   template<typename _Key, typename _Val, typename _KoV,
1236            typename _Cmp, typename _Alloc>
1237     template<class _II>
1238       void
1239       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1240       _M_insert_equal(_II __first, _II __last)
1241       {
1242         for (; __first != __last; ++__first)
1243           _M_insert_equal(end(), *__first);
1244       }
1245
1246   template<typename _Key, typename _Val, typename _KoV,
1247            typename _Cmp, typename _Alloc>
1248     template<class _II>
1249       void
1250       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1251       _M_insert_unique(_II __first, _II __last)
1252       {
1253         for (; __first != __last; ++__first)
1254           _M_insert_unique(end(), *__first);
1255       }
1256
1257   template<typename _Key, typename _Val, typename _KeyOfValue,
1258            typename _Compare, typename _Alloc>
1259     inline void
1260     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1261     erase(iterator __position)
1262     {
1263       _Link_type __y =
1264         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1265                                 (__position._M_node,
1266                                  this->_M_impl._M_header));
1267       _M_destroy_node(__y);
1268       --_M_impl._M_node_count;
1269     }
1270
1271   template<typename _Key, typename _Val, typename _KeyOfValue,
1272            typename _Compare, typename _Alloc>
1273     inline void
1274     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1275     erase(const_iterator __position)
1276     {
1277       _Link_type __y =
1278         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1279                                 (const_cast<_Base_ptr>(__position._M_node),
1280                                  this->_M_impl._M_header));
1281       _M_destroy_node(__y);
1282       --_M_impl._M_node_count;
1283     }
1284
1285   template<typename _Key, typename _Val, typename _KeyOfValue,
1286            typename _Compare, typename _Alloc>
1287     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1288     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1289     erase(const _Key& __x)
1290     {
1291       pair<iterator, iterator> __p = equal_range(__x);
1292       const size_type __old_size = size();
1293       erase(__p.first, __p.second);
1294       return __old_size - size();
1295     }
1296
1297   template<typename _Key, typename _Val, typename _KoV,
1298            typename _Compare, typename _Alloc>
1299     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1300     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1301     _M_copy(_Const_Link_type __x, _Link_type __p)
1302     {
1303       // Structural copy.  __x and __p must be non-null.
1304       _Link_type __top = _M_clone_node(__x);
1305       __top->_M_parent = __p;
1306
1307       try
1308         {
1309           if (__x->_M_right)
1310             __top->_M_right = _M_copy(_S_right(__x), __top);
1311           __p = __top;
1312           __x = _S_left(__x);
1313
1314           while (__x != 0)
1315             {
1316               _Link_type __y = _M_clone_node(__x);
1317               __p->_M_left = __y;
1318               __y->_M_parent = __p;
1319               if (__x->_M_right)
1320                 __y->_M_right = _M_copy(_S_right(__x), __y);
1321               __p = __y;
1322               __x = _S_left(__x);
1323             }
1324         }
1325       catch(...)
1326         {
1327           _M_erase(__top);
1328           __throw_exception_again;
1329         }
1330       return __top;
1331     }
1332
1333   template<typename _Key, typename _Val, typename _KeyOfValue,
1334            typename _Compare, typename _Alloc>
1335     void
1336     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1337     _M_erase(_Link_type __x)
1338     {
1339       // Erase without rebalancing.
1340       while (__x != 0)
1341         {
1342           _M_erase(_S_right(__x));
1343           _Link_type __y = _S_left(__x);
1344           _M_destroy_node(__x);
1345           __x = __y;
1346         }
1347     }
1348
1349   template<typename _Key, typename _Val, typename _KeyOfValue,
1350            typename _Compare, typename _Alloc>
1351     void
1352     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1353     erase(iterator __first, iterator __last)
1354     {
1355       if (__first == begin() && __last == end())
1356         clear();
1357       else
1358         while (__first != __last)
1359           erase(__first++);
1360     }
1361
1362   template<typename _Key, typename _Val, typename _KeyOfValue,
1363            typename _Compare, typename _Alloc>
1364     void
1365     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1366     erase(const_iterator __first, const_iterator __last)
1367     {
1368       if (__first == begin() && __last == end())
1369         clear();
1370       else
1371         while (__first != __last)
1372           erase(__first++);
1373     }
1374
1375   template<typename _Key, typename _Val, typename _KeyOfValue,
1376            typename _Compare, typename _Alloc>
1377     void
1378     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1379     erase(const _Key* __first, const _Key* __last)
1380     {
1381       while (__first != __last)
1382         erase(*__first++);
1383     }
1384
1385   template<typename _Key, typename _Val, typename _KeyOfValue,
1386            typename _Compare, typename _Alloc>
1387     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1388     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1389     find(const _Key& __k)
1390     {
1391       _Link_type __x = _M_begin(); // Current node.
1392       _Link_type __y = _M_end(); // Last node which is not less than __k.
1393
1394       while (__x != 0)
1395         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1396           __y = __x, __x = _S_left(__x);
1397         else
1398           __x = _S_right(__x);
1399
1400       iterator __j = iterator(__y);
1401       return (__j == end()
1402               || _M_impl._M_key_compare(__k,
1403                                         _S_key(__j._M_node))) ? end() : __j;
1404     }
1405
1406   template<typename _Key, typename _Val, typename _KeyOfValue,
1407            typename _Compare, typename _Alloc>
1408     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1409     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1410     find(const _Key& __k) const
1411     {
1412       _Const_Link_type __x = _M_begin(); // Current node.
1413       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1414
1415      while (__x != 0)
1416        {
1417          if (!_M_impl._M_key_compare(_S_key(__x), __k))
1418            __y = __x, __x = _S_left(__x);
1419          else
1420            __x = _S_right(__x);
1421        }
1422      const_iterator __j = const_iterator(__y);
1423      return (__j == end()
1424              || _M_impl._M_key_compare(__k,
1425                                        _S_key(__j._M_node))) ? end() : __j;
1426     }
1427
1428   template<typename _Key, typename _Val, typename _KeyOfValue,
1429            typename _Compare, typename _Alloc>
1430     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1431     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1432     count(const _Key& __k) const
1433     {
1434       pair<const_iterator, const_iterator> __p = equal_range(__k);
1435       const size_type __n = std::distance(__p.first, __p.second);
1436       return __n;
1437     }
1438
1439   template<typename _Key, typename _Val, typename _KeyOfValue,
1440            typename _Compare, typename _Alloc>
1441     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1442     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1443     lower_bound(const _Key& __k)
1444     {
1445       _Link_type __x = _M_begin(); // Current node.
1446       _Link_type __y = _M_end(); // Last node which is not less than __k.
1447
1448       while (__x != 0)
1449         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1450           __y = __x, __x = _S_left(__x);
1451         else
1452           __x = _S_right(__x);
1453
1454       return iterator(__y);
1455     }
1456
1457   template<typename _Key, typename _Val, typename _KeyOfValue,
1458            typename _Compare, typename _Alloc>
1459     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1460     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1461     lower_bound(const _Key& __k) const
1462     {
1463       _Const_Link_type __x = _M_begin(); // Current node.
1464       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1465
1466       while (__x != 0)
1467         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1468           __y = __x, __x = _S_left(__x);
1469         else
1470           __x = _S_right(__x);
1471
1472       return const_iterator(__y);
1473     }
1474
1475   template<typename _Key, typename _Val, typename _KeyOfValue,
1476            typename _Compare, typename _Alloc>
1477     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1478     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1479     upper_bound(const _Key& __k)
1480     {
1481       _Link_type __x = _M_begin(); // Current node.
1482       _Link_type __y = _M_end(); // Last node which is greater than __k.
1483
1484       while (__x != 0)
1485         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1486           __y = __x, __x = _S_left(__x);
1487         else
1488           __x = _S_right(__x);
1489
1490       return iterator(__y);
1491     }
1492
1493   template<typename _Key, typename _Val, typename _KeyOfValue,
1494            typename _Compare, typename _Alloc>
1495     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1496     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1497     upper_bound(const _Key& __k) const
1498     {
1499       _Const_Link_type __x = _M_begin(); // Current node.
1500       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1501
1502       while (__x != 0)
1503         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1504           __y = __x, __x = _S_left(__x);
1505         else
1506           __x = _S_right(__x);
1507
1508       return const_iterator(__y);
1509     }
1510
1511   template<typename _Key, typename _Val, typename _KeyOfValue,
1512            typename _Compare, typename _Alloc>
1513     inline
1514     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1515                            _Compare, _Alloc>::iterator,
1516          typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1517     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1518     equal_range(const _Key& __k)
1519     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1520
1521   template<typename _Key, typename _Val, typename _KoV,
1522            typename _Compare, typename _Alloc>
1523     inline
1524     pair<typename _Rb_tree<_Key, _Val, _KoV,
1525                            _Compare, _Alloc>::const_iterator,
1526          typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1527     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1528     equal_range(const _Key& __k) const
1529     { return pair<const_iterator, const_iterator>(lower_bound(__k),
1530                                                   upper_bound(__k)); }
1531
1532   unsigned int
1533   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1534                        const _Rb_tree_node_base* __root);
1535
1536   template<typename _Key, typename _Val, typename _KeyOfValue,
1537            typename _Compare, typename _Alloc>
1538     bool
1539     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1540     {
1541       if (_M_impl._M_node_count == 0 || begin() == end())
1542         return _M_impl._M_node_count == 0 && begin() == end()
1543                && this->_M_impl._M_header._M_left == _M_end()
1544                && this->_M_impl._M_header._M_right == _M_end();
1545
1546       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1547       for (const_iterator __it = begin(); __it != end(); ++__it)
1548         {
1549           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1550           _Const_Link_type __L = _S_left(__x);
1551           _Const_Link_type __R = _S_right(__x);
1552
1553           if (__x->_M_color == _S_red)
1554             if ((__L && __L->_M_color == _S_red)
1555                 || (__R && __R->_M_color == _S_red))
1556               return false;
1557
1558           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1559             return false;
1560           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1561             return false;
1562
1563           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1564             return false;
1565         }
1566
1567       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1568         return false;
1569       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1570         return false;
1571       return true;
1572     }
1573
1574 _GLIBCXX_END_NAMESPACE
1575
1576 #endif