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