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(const _Node_allocator& __a = _Node_allocator(),
 414                         const _Key_compare& __comp = _Key_compare())
 415           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 416             _M_node_count(0)
 417           {
 418             this->_M_header._M_color = _S_red;
 419             this->_M_header._M_parent = 0;
 420             this->_M_header._M_left = &this->_M_header;
 421             this->_M_header._M_right = &this->_M_header;
 422           }
 423         };
 424
 425       // Specialization for _Comparison types that are not capable of
 426       // being base classes / super classes.
 427       template<typename _Key_compare>
 428         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
 429         {
 430           _Key_compare          _M_key_compare;
 431           _Rb_tree_node_base    _M_header;
 432           size_type             _M_node_count; // Keeps track of size of tree.
 433
 434           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 435                         const _Key_compare& __comp = _Key_compare())
 436           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 437             _M_node_count(0)
 438           {
 439             this->_M_header._M_color = _S_red;
 440             this->_M_header._M_parent = 0;
 441             this->_M_header._M_left = &this->_M_header;
 442             this->_M_header._M_right = &this->_M_header;
 443           }
 444         };
 445
 446       _Rb_tree_impl<_Compare> _M_impl;
 447
 448     protected:
 449       _Base_ptr&
 450       _M_root()
 451       { return this->_M_impl._M_header._M_parent; }
 452
 453       _Const_Base_ptr
 454       _M_root() const
 455       { return this->_M_impl._M_header._M_parent; }
 456
 457       _Base_ptr&
 458       _M_leftmost()
 459       { return this->_M_impl._M_header._M_left; }
 460
 461       _Const_Base_ptr
 462       _M_leftmost() const
 463       { return this->_M_impl._M_header._M_left; }
 464
 465       _Base_ptr&
 466       _M_rightmost()
 467       { return this->_M_impl._M_header._M_right; }
 468
 469       _Const_Base_ptr
 470       _M_rightmost() const
 471       { return this->_M_impl._M_header._M_right; }
 472
 473       _Link_type
 474       _M_begin()
 475       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 476
 477       _Const_Link_type
 478       _M_begin() const
 479       {
 480         return static_cast<_Const_Link_type>
 481           (this->_M_impl._M_header._M_parent);
 482       }
 483
 484       _Link_type
 485       _M_end()
 486       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 487
 488       _Const_Link_type
 489       _M_end() const
 490       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 491
 492       static const_reference
 493       _S_value(_Const_Link_type __x)
 494       { return __x->_M_value_field; }
 495
 496       static const _Key&
 497       _S_key(_Const_Link_type __x)
 498       { return _KeyOfValue()(_S_value(__x)); }
 499
 500       static _Link_type
 501       _S_left(_Base_ptr __x)
 502       { return static_cast<_Link_type>(__x->_M_left); }
 503
 504       static _Const_Link_type
 505       _S_left(_Const_Base_ptr __x)
 506       { return static_cast<_Const_Link_type>(__x->_M_left); }
 507
 508       static _Link_type
 509       _S_right(_Base_ptr __x)
 510       { return static_cast<_Link_type>(__x->_M_right); }
 511
 512       static _Const_Link_type
 513       _S_right(_Const_Base_ptr __x)
 514       { return static_cast<_Const_Link_type>(__x->_M_right); }
 515
 516       static const_reference
 517       _S_value(_Const_Base_ptr __x)
 518       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 519
 520       static const _Key&
 521       _S_key(_Const_Base_ptr __x)
 522       { return _KeyOfValue()(_S_value(__x)); }
 523
 524       static _Base_ptr
 525       _S_minimum(_Base_ptr __x)
 526       { return _Rb_tree_node_base::_S_minimum(__x); }
 527
 528       static _Const_Base_ptr
 529       _S_minimum(_Const_Base_ptr __x)
 530       { return _Rb_tree_node_base::_S_minimum(__x); }
 531
 532       static _Base_ptr
 533       _S_maximum(_Base_ptr __x)
 534       { return _Rb_tree_node_base::_S_maximum(__x); }
 535
 536       static _Const_Base_ptr
 537       _S_maximum(_Const_Base_ptr __x)
 538       { return _Rb_tree_node_base::_S_maximum(__x); }
 539
 540     public:
 541       typedef _Rb_tree_iterator<value_type>       iterator;
 542       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 543
 544       typedef std::reverse_iterator<iterator>       reverse_iterator;
 545       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 546
 547     private:
 548       iterator
 549       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 550
 551       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 552       // 233. Insertion hints in associative containers.
 553       iterator
 554       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 555
 556       const_iterator
 557       _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
 558                 const value_type& __v);
 559
 560       _Link_type
 561       _M_copy(_Const_Link_type __x, _Link_type __p);
 562
 563       void
 564       _M_erase(_Link_type __x);
 565
 566     public:
 567       // allocation/deallocation
 568       _Rb_tree()
 569       { }
 570
 571       _Rb_tree(const _Compare& __comp)
 572       : _M_impl(allocator_type(), __comp)
 573       { }
 574
 575       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 576       : _M_impl(__a, __comp)
 577       { }
 578
 579       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 580       : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare)
 581       {
 582         if (__x._M_root() != 0)
 583           {
 584             _M_root() = _M_copy(__x._M_begin(), _M_end());
 585             _M_leftmost() = _S_minimum(_M_root());
 586             _M_rightmost() = _S_maximum(_M_root());
 587             _M_impl._M_node_count = __x._M_impl._M_node_count;
 588           }
 589       }
 590
 591       ~_Rb_tree()
 592       { _M_erase(_M_begin()); }
 593
 594       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 595       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
 596
 597       // Accessors.
 598       _Compare
 599       key_comp() const
 600       { return _M_impl._M_key_compare; }
 601
 602       iterator
 603       begin()
 604       {
 605         return iterator(static_cast<_Link_type>
 606                         (this->_M_impl._M_header._M_left));
 607       }
 608
 609       const_iterator
 610       begin() const
 611       {
 612         return const_iterator(static_cast<_Const_Link_type>
 613                               (this->_M_impl._M_header._M_left));
 614       }
 615
 616       iterator
 617       end()
 618       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 619
 620       const_iterator
 621       end() const
 622       {
 623         return const_iterator(static_cast<_Const_Link_type>
 624                               (&this->_M_impl._M_header));
 625       }
 626
 627       reverse_iterator
 628       rbegin()
 629       { return reverse_iterator(end()); }
 630
 631       const_reverse_iterator
 632       rbegin() const
 633       { return const_reverse_iterator(end()); }
 634
 635       reverse_iterator
 636       rend()
 637       { return reverse_iterator(begin()); }
 638
 639       const_reverse_iterator
 640       rend() const
 641       { return const_reverse_iterator(begin()); }
 642
 643       bool
 644       empty() const
 645       { return _M_impl._M_node_count == 0; }
 646
 647       size_type
 648       size() const
 649       { return _M_impl._M_node_count; }
 650
 651       size_type
 652       max_size() const
 653       { return get_allocator().max_size(); }
 654
 655       void
 656       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
 657
 658       // Insert/erase.
 659       pair<iterator, bool>
 660       _M_insert_unique(const value_type& __x);
 661
 662       iterator
 663       _M_insert_equal(const value_type& __x);
 664
 665       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 666       // 233. Insertion hints in associative containers.
 667       iterator
 668       _M_insert_equal_lower(const value_type& __x);
 669
 670       iterator
 671       _M_insert_unique(iterator __position, const value_type& __x);
 672
 673       const_iterator
 674       _M_insert_unique(const_iterator __position, const value_type& __x);
 675
 676       iterator
 677       _M_insert_equal(iterator __position, const value_type& __x);
 678
 679       const_iterator
 680       _M_insert_equal(const_iterator __position, const value_type& __x);
 681
 682       template<typename _InputIterator>
 683         void
 684         _M_insert_unique(_InputIterator __first, _InputIterator __last);
 685
 686       template<typename _InputIterator>
 687         void
 688         _M_insert_equal(_InputIterator __first, _InputIterator __last);
 689
 690       void
 691       erase(iterator __position);
 692
 693       void
 694       erase(const_iterator __position);
 695
 696       size_type
 697       erase(const key_type& __x);
 698
 699       void
 700       erase(iterator __first, iterator __last);
 701
 702       void
 703       erase(const_iterator __first, const_iterator __last);
 704
 705       void
 706       erase(const key_type* __first, const key_type* __last);
 707
 708       void
 709       clear()
 710       {
 711         _M_erase(_M_begin());
 712         _M_leftmost() = _M_end();
 713         _M_root() = 0;
 714         _M_rightmost() = _M_end();
 715         _M_impl._M_node_count = 0;
 716       }
 717
 718       // Set operations.
 719       iterator
 720       find(const key_type& __x);
 721
 722       const_iterator
 723       find(const key_type& __x) const;
 724
 725       size_type
 726       count(const key_type& __x) const;
 727
 728       iterator
 729       lower_bound(const key_type& __x);
 730
 731       const_iterator
 732       lower_bound(const key_type& __x) const;
 733
 734       iterator
 735       upper_bound(const key_type& __x);
 736
 737       const_iterator
 738       upper_bound(const key_type& __x) const;
 739
 740       pair<iterator,iterator>
 741       equal_range(const key_type& __x);
 742
 743       pair<const_iterator, const_iterator>
 744       equal_range(const key_type& __x) const;
 745
 746       // Debugging.
 747       bool
 748       __rb_verify() const;
 749     };
 750
 751   template<typename _Key, typename _Val, typename _KeyOfValue,
 752            typename _Compare, typename _Alloc>
 753     inline bool
 754     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 755                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 756     {
 757       return __x.size() == __y.size()
 758              && std::equal(__x.begin(), __x.end(), __y.begin());
 759     }
 760
 761   template<typename _Key, typename _Val, typename _KeyOfValue,
 762            typename _Compare, typename _Alloc>
 763     inline bool
 764     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 765               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 766     {
 767       return std::lexicographical_compare(__x.begin(), __x.end(),
 768                                           __y.begin(), __y.end());
 769     }
 770
 771   template<typename _Key, typename _Val, typename _KeyOfValue,
 772            typename _Compare, typename _Alloc>
 773     inline bool
 774     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 775                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 776     { return !(__x == __y); }
 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     { return __y < __x; }
 784
 785   template<typename _Key, typename _Val, typename _KeyOfValue,
 786            typename _Compare, typename _Alloc>
 787     inline bool
 788     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 789                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 790     { return !(__y < __x); }
 791
 792   template<typename _Key, typename _Val, typename _KeyOfValue,
 793            typename _Compare, typename _Alloc>
 794     inline bool
 795     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 796                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 797     { return !(__x < __y); }
 798
 799   template<typename _Key, typename _Val, typename _KeyOfValue,
 800            typename _Compare, typename _Alloc>
 801     inline void
 802     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 803          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 804     { __x.swap(__y); }
 805
 806   template<typename _Key, typename _Val, typename _KeyOfValue,
 807            typename _Compare, typename _Alloc>
 808     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 809     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 810     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 811     {
 812       if (this != &__x)
 813         {
 814           // Note that _Key may be a constant type.
 815           clear();
 816           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 817           if (__x._M_root() != 0)
 818             {
 819               _M_root() = _M_copy(__x._M_begin(), _M_end());
 820               _M_leftmost() = _S_minimum(_M_root());
 821               _M_rightmost() = _S_maximum(_M_root());
 822               _M_impl._M_node_count = __x._M_impl._M_node_count;
 823             }
 824         }
 825       return *this;
 826     }
 827
 828   template<typename _Key, typename _Val, typename _KeyOfValue,
 829            typename _Compare, typename _Alloc>
 830     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 831     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 832     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 833     {
 834       bool __insert_left = (__x != 0 || __p == _M_end()
 835                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 836                                                       _S_key(__p)));
 837
 838       _Link_type __z = _M_create_node(__v);
 839
 840       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 841                                     this->_M_impl._M_header);
 842       ++_M_impl._M_node_count;
 843       return iterator(__z);
 844     }
 845
 846   template<typename _Key, typename _Val, typename _KeyOfValue,
 847            typename _Compare, typename _Alloc>
 848     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 849     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 850     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 851     {
 852       bool __insert_left = (__x != 0 || __p == _M_end()
 853                             || !_M_impl._M_key_compare(_S_key(__p),
 854                                                        _KeyOfValue()(__v)));
 855
 856       _Link_type __z = _M_create_node(__v);
 857
 858       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 859                                     this->_M_impl._M_header);
 860       ++_M_impl._M_node_count;
 861       return iterator(__z);
 862     }
 863
 864   template<typename _Key, typename _Val, typename _KeyOfValue,
 865            typename _Compare, typename _Alloc>
 866     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
 867     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 868     _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
 869     {
 870       bool __insert_left = (__x != 0 || __p == _M_end()
 871                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 872                                                       _S_key(__p)));
 873
 874       _Link_type __z = _M_create_node(__v);
 875
 876       _Rb_tree_insert_and_rebalance(__insert_left, __z,
 877                                     const_cast<_Base_ptr>(__p),
 878                                     this->_M_impl._M_header);
 879       ++_M_impl._M_node_count;
 880       return const_iterator(__z);
 881     }
 882
 883   template<typename _Key, typename _Val, typename _KeyOfValue,
 884            typename _Compare, typename _Alloc>
 885     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 886     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 887     _M_insert_equal(const _Val& __v)
 888     {
 889       _Link_type __x = _M_begin();
 890       _Link_type __y = _M_end();
 891       while (__x != 0)
 892         {
 893           __y = __x;
 894           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 895                 _S_left(__x) : _S_right(__x);
 896         }
 897       return _M_insert(__x, __y, __v);
 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_lower(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(_S_key(__x), _KeyOfValue()(__v)) ?
 912                 _S_left(__x) : _S_right(__x);
 913         }
 914       return _M_insert_lower(__x, __y, __v);
 915     }
 916
 917   template<typename _Key, typename _Val, typename _KeyOfValue,
 918            typename _Compare, typename _Alloc>
 919     void
 920     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 921     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
 922     {
 923       if (_M_root() == 0)
 924         {
 925           if (__t._M_root() != 0)
 926             {
 927               _M_root() = __t._M_root();
 928               _M_leftmost() = __t._M_leftmost();
 929               _M_rightmost() = __t._M_rightmost();
 930               _M_root()->_M_parent = _M_end();
 931
 932               __t._M_root() = 0;
 933               __t._M_leftmost() = __t._M_end();
 934               __t._M_rightmost() = __t._M_end();
 935             }
 936         }
 937       else if (__t._M_root() == 0)
 938         {
 939           __t._M_root() = _M_root();
 940           __t._M_leftmost() = _M_leftmost();
 941           __t._M_rightmost() = _M_rightmost();
 942           __t._M_root()->_M_parent = __t._M_end();
 943
 944           _M_root() = 0;
 945           _M_leftmost() = _M_end();
 946           _M_rightmost() = _M_end();
 947         }
 948       else
 949         {
 950           std::swap(_M_root(),__t._M_root());
 951           std::swap(_M_leftmost(),__t._M_leftmost());
 952           std::swap(_M_rightmost(),__t._M_rightmost());
 953
 954           _M_root()->_M_parent = _M_end();
 955           __t._M_root()->_M_parent = __t._M_end();
 956         }
 957       // No need to swap header's color as it does not change.
 958       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 959       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 960
 961       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 962       // 431. Swapping containers with unequal allocators.
 963       std::__alloc_swap<_Node_allocator>::
 964         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
 965     }
 966
 967   template<typename _Key, typename _Val, typename _KeyOfValue,
 968            typename _Compare, typename _Alloc>
 969     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 970                            _Compare, _Alloc>::iterator, bool>
 971     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 972     _M_insert_unique(const _Val& __v)
 973     {
 974       _Link_type __x = _M_begin();
 975       _Link_type __y = _M_end();
 976       bool __comp = true;
 977       while (__x != 0)
 978         {
 979           __y = __x;
 980           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 981           __x = __comp ? _S_left(__x) : _S_right(__x);
 982         }
 983       iterator __j = iterator(__y);
 984       if (__comp)
 985         if (__j == begin())
 986           return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 987         else
 988           --__j;
 989       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 990         return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
 991       return pair<iterator, bool>(__j, false);
 992     }
 993
 994   template<typename _Key, typename _Val, typename _KeyOfValue,
 995            typename _Compare, typename _Alloc>
 996     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 997     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 998     _M_insert_unique(iterator __position, const _Val& __v)
 999     {
1000       // end()
1001       if (__position._M_node == _M_end())
1002         {
1003           if (size() > 0
1004               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1005                                         _KeyOfValue()(__v)))
1006             return _M_insert(0, _M_rightmost(), __v);
1007           else
1008             return _M_insert_unique(__v).first;
1009         }
1010       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1011                                       _S_key(__position._M_node)))
1012         {
1013           // First, try before...
1014           iterator __before = __position;
1015           if (__position._M_node == _M_leftmost()) // begin()
1016             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1017           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1018                                           _KeyOfValue()(__v)))
1019             {
1020               if (_S_right(__before._M_node) == 0)
1021                 return _M_insert(0, __before._M_node, __v);
1022               else
1023                 return _M_insert(__position._M_node,
1024                                  __position._M_node, __v);
1025             }
1026           else
1027             return _M_insert_unique(__v).first;
1028         }
1029       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1030                                       _KeyOfValue()(__v)))
1031         {
1032           // ... then try after.
1033           iterator __after = __position;
1034           if (__position._M_node == _M_rightmost())
1035             return _M_insert(0, _M_rightmost(), __v);
1036           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1037                                           _S_key((++__after)._M_node)))
1038             {
1039               if (_S_right(__position._M_node) == 0)
1040                 return _M_insert(0, __position._M_node, __v);
1041               else
1042                 return _M_insert(__after._M_node, __after._M_node, __v);
1043             }
1044           else
1045             return _M_insert_unique(__v).first;
1046         }
1047       else
1048         return __position; // Equivalent keys.
1049     }
1050
1051   template<typename _Key, typename _Val, typename _KeyOfValue,
1052            typename _Compare, typename _Alloc>
1053     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1054     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1055     _M_insert_unique(const_iterator __position, const _Val& __v)
1056     {
1057       // end()
1058       if (__position._M_node == _M_end())
1059         {
1060           if (size() > 0
1061               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1062                                         _KeyOfValue()(__v)))
1063             return _M_insert(0, _M_rightmost(), __v);
1064           else
1065             return const_iterator(_M_insert_unique(__v).first);
1066         }
1067       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1068                                       _S_key(__position._M_node)))
1069         {
1070           // First, try before...
1071           const_iterator __before = __position;
1072           if (__position._M_node == _M_leftmost()) // begin()
1073             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1074           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1075                                           _KeyOfValue()(__v)))
1076             {
1077               if (_S_right(__before._M_node) == 0)
1078                 return _M_insert(0, __before._M_node, __v);
1079               else
1080                 return _M_insert(__position._M_node,
1081                                  __position._M_node, __v);
1082             }
1083           else
1084             return const_iterator(_M_insert_unique(__v).first);
1085         }
1086       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1087                                       _KeyOfValue()(__v)))
1088         {
1089           // ... then try after.
1090           const_iterator __after = __position;
1091           if (__position._M_node == _M_rightmost())
1092             return _M_insert(0, _M_rightmost(), __v);
1093           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1094                                           _S_key((++__after)._M_node)))
1095             {
1096               if (_S_right(__position._M_node) == 0)
1097                 return _M_insert(0, __position._M_node, __v);
1098               else
1099                 return _M_insert(__after._M_node, __after._M_node, __v);
1100             }
1101           else
1102             return const_iterator(_M_insert_unique(__v).first);
1103         }
1104       else
1105         return __position; // Equivalent keys.
1106     }
1107
1108   template<typename _Key, typename _Val, typename _KeyOfValue,
1109            typename _Compare, typename _Alloc>
1110     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1111     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1112     _M_insert_equal(iterator __position, const _Val& __v)
1113     {
1114       // end()
1115       if (__position._M_node == _M_end())
1116         {
1117           if (size() > 0
1118               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1119                                          _S_key(_M_rightmost())))
1120             return _M_insert(0, _M_rightmost(), __v);
1121           else
1122             return _M_insert_equal(__v);
1123         }
1124       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1125                                        _KeyOfValue()(__v)))
1126         {
1127           // First, try before...
1128           iterator __before = __position;
1129           if (__position._M_node == _M_leftmost()) // begin()
1130             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1131           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1132                                            _S_key((--__before)._M_node)))
1133             {
1134               if (_S_right(__before._M_node) == 0)
1135                 return _M_insert(0, __before._M_node, __v);
1136               else
1137                 return _M_insert(__position._M_node,
1138                                  __position._M_node, __v);
1139             }
1140           else
1141             return _M_insert_equal(__v);
1142         }
1143       else
1144         {
1145           // ... then try after.
1146           iterator __after = __position;
1147           if (__position._M_node == _M_rightmost())
1148             return _M_insert(0, _M_rightmost(), __v);
1149           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1150                                            _KeyOfValue()(__v)))
1151             {
1152               if (_S_right(__position._M_node) == 0)
1153                 return _M_insert(0, __position._M_node, __v);
1154               else
1155                 return _M_insert(__after._M_node, __after._M_node, __v);
1156             }
1157           else
1158             return _M_insert_equal_lower(__v);
1159         }
1160     }
1161
1162   template<typename _Key, typename _Val, typename _KeyOfValue,
1163            typename _Compare, typename _Alloc>
1164     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1165     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1166     _M_insert_equal(const_iterator __position, const _Val& __v)
1167     {
1168       // end()
1169       if (__position._M_node == _M_end())
1170         {
1171           if (size() > 0
1172               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1173                                          _S_key(_M_rightmost())))
1174             return _M_insert(0, _M_rightmost(), __v);
1175           else
1176             return const_iterator(_M_insert_equal(__v));
1177         }
1178       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1179                                        _KeyOfValue()(__v)))
1180         {
1181           // First, try before...
1182           const_iterator __before = __position;
1183           if (__position._M_node == _M_leftmost()) // begin()
1184             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1185           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1186                                            _S_key((--__before)._M_node)))
1187             {
1188               if (_S_right(__before._M_node) == 0)
1189                 return _M_insert(0, __before._M_node, __v);
1190               else
1191                 return _M_insert(__position._M_node,
1192                                  __position._M_node, __v);
1193             }
1194           else
1195             return const_iterator(_M_insert_equal(__v));
1196         }
1197       else
1198         {
1199           // ... then try after.
1200           const_iterator __after = __position;
1201           if (__position._M_node == _M_rightmost())
1202             return _M_insert(0, _M_rightmost(), __v);
1203           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1204                                            _KeyOfValue()(__v)))
1205             {
1206               if (_S_right(__position._M_node) == 0)
1207                 return _M_insert(0, __position._M_node, __v);
1208               else
1209                 return _M_insert(__after._M_node, __after._M_node, __v);
1210             }
1211           else
1212             return const_iterator(_M_insert_equal_lower(__v));
1213         }
1214     }
1215
1216   template<typename _Key, typename _Val, typename _KoV,
1217            typename _Cmp, typename _Alloc>
1218     template<class _II>
1219       void
1220       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1221       _M_insert_equal(_II __first, _II __last)
1222       {
1223         for (; __first != __last; ++__first)
1224           _M_insert_equal(end(), *__first);
1225       }
1226
1227   template<typename _Key, typename _Val, typename _KoV,
1228            typename _Cmp, typename _Alloc>
1229     template<class _II>
1230       void
1231       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1232       _M_insert_unique(_II __first, _II __last)
1233       {
1234         for (; __first != __last; ++__first)
1235           _M_insert_unique(end(), *__first);
1236       }
1237
1238   template<typename _Key, typename _Val, typename _KeyOfValue,
1239            typename _Compare, typename _Alloc>
1240     inline void
1241     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1242     erase(iterator __position)
1243     {
1244       _Link_type __y =
1245         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1246                                 (__position._M_node,
1247                                  this->_M_impl._M_header));
1248       _M_destroy_node(__y);
1249       --_M_impl._M_node_count;
1250     }
1251
1252   template<typename _Key, typename _Val, typename _KeyOfValue,
1253            typename _Compare, typename _Alloc>
1254     inline void
1255     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1256     erase(const_iterator __position)
1257     {
1258       _Link_type __y =
1259         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1260                                 (const_cast<_Base_ptr>(__position._M_node),
1261                                  this->_M_impl._M_header));
1262       _M_destroy_node(__y);
1263       --_M_impl._M_node_count;
1264     }
1265
1266   template<typename _Key, typename _Val, typename _KeyOfValue,
1267            typename _Compare, typename _Alloc>
1268     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1269     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1270     erase(const _Key& __x)
1271     {
1272       pair<iterator, iterator> __p = equal_range(__x);
1273       const size_type __old_size = size();
1274       erase(__p.first, __p.second);
1275       return __old_size - size();
1276     }
1277
1278   template<typename _Key, typename _Val, typename _KoV,
1279            typename _Compare, typename _Alloc>
1280     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1281     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1282     _M_copy(_Const_Link_type __x, _Link_type __p)
1283     {
1284       // Structural copy.  __x and __p must be non-null.
1285       _Link_type __top = _M_clone_node(__x);
1286       __top->_M_parent = __p;
1287
1288       try
1289         {
1290           if (__x->_M_right)
1291             __top->_M_right = _M_copy(_S_right(__x), __top);
1292           __p = __top;
1293           __x = _S_left(__x);
1294
1295           while (__x != 0)
1296             {
1297               _Link_type __y = _M_clone_node(__x);
1298               __p->_M_left = __y;
1299               __y->_M_parent = __p;
1300               if (__x->_M_right)
1301                 __y->_M_right = _M_copy(_S_right(__x), __y);
1302               __p = __y;
1303               __x = _S_left(__x);
1304             }
1305         }
1306       catch(...)
1307         {
1308           _M_erase(__top);
1309           __throw_exception_again;
1310         }
1311       return __top;
1312     }
1313
1314   template<typename _Key, typename _Val, typename _KeyOfValue,
1315            typename _Compare, typename _Alloc>
1316     void
1317     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1318     _M_erase(_Link_type __x)
1319     {
1320       // Erase without rebalancing.
1321       while (__x != 0)
1322         {
1323           _M_erase(_S_right(__x));
1324           _Link_type __y = _S_left(__x);
1325           _M_destroy_node(__x);
1326           __x = __y;
1327         }
1328     }
1329
1330   template<typename _Key, typename _Val, typename _KeyOfValue,
1331            typename _Compare, typename _Alloc>
1332     void
1333     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1334     erase(iterator __first, iterator __last)
1335     {
1336       if (__first == begin() && __last == end())
1337         clear();
1338       else
1339         while (__first != __last)
1340           erase(__first++);
1341     }
1342
1343   template<typename _Key, typename _Val, typename _KeyOfValue,
1344            typename _Compare, typename _Alloc>
1345     void
1346     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1347     erase(const_iterator __first, const_iterator __last)
1348     {
1349       if (__first == begin() && __last == end())
1350         clear();
1351       else
1352         while (__first != __last)
1353           erase(__first++);
1354     }
1355
1356   template<typename _Key, typename _Val, typename _KeyOfValue,
1357            typename _Compare, typename _Alloc>
1358     void
1359     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1360     erase(const _Key* __first, const _Key* __last)
1361     {
1362       while (__first != __last)
1363         erase(*__first++);
1364     }
1365
1366   template<typename _Key, typename _Val, typename _KeyOfValue,
1367            typename _Compare, typename _Alloc>
1368     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1369     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1370     find(const _Key& __k)
1371     {
1372       _Link_type __x = _M_begin(); // Current node.
1373       _Link_type __y = _M_end(); // Last node which is not less than __k.
1374
1375       while (__x != 0)
1376         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1377           __y = __x, __x = _S_left(__x);
1378         else
1379           __x = _S_right(__x);
1380
1381       iterator __j = iterator(__y);
1382       return (__j == end()
1383               || _M_impl._M_key_compare(__k,
1384                                         _S_key(__j._M_node))) ? end() : __j;
1385     }
1386
1387   template<typename _Key, typename _Val, typename _KeyOfValue,
1388            typename _Compare, typename _Alloc>
1389     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1390     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1391     find(const _Key& __k) const
1392     {
1393       _Const_Link_type __x = _M_begin(); // Current node.
1394       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1395
1396      while (__x != 0)
1397        {
1398          if (!_M_impl._M_key_compare(_S_key(__x), __k))
1399            __y = __x, __x = _S_left(__x);
1400          else
1401            __x = _S_right(__x);
1402        }
1403      const_iterator __j = const_iterator(__y);
1404      return (__j == end()
1405              || _M_impl._M_key_compare(__k,
1406                                        _S_key(__j._M_node))) ? end() : __j;
1407     }
1408
1409   template<typename _Key, typename _Val, typename _KeyOfValue,
1410            typename _Compare, typename _Alloc>
1411     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1412     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1413     count(const _Key& __k) const
1414     {
1415       pair<const_iterator, const_iterator> __p = equal_range(__k);
1416       const size_type __n = std::distance(__p.first, __p.second);
1417       return __n;
1418     }
1419
1420   template<typename _Key, typename _Val, typename _KeyOfValue,
1421            typename _Compare, typename _Alloc>
1422     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1423     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1424     lower_bound(const _Key& __k)
1425     {
1426       _Link_type __x = _M_begin(); // Current node.
1427       _Link_type __y = _M_end(); // Last node which is not less than __k.
1428
1429       while (__x != 0)
1430         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1431           __y = __x, __x = _S_left(__x);
1432         else
1433           __x = _S_right(__x);
1434
1435       return iterator(__y);
1436     }
1437
1438   template<typename _Key, typename _Val, typename _KeyOfValue,
1439            typename _Compare, typename _Alloc>
1440     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1441     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1442     lower_bound(const _Key& __k) const
1443     {
1444       _Const_Link_type __x = _M_begin(); // Current node.
1445       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1446
1447       while (__x != 0)
1448         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1449           __y = __x, __x = _S_left(__x);
1450         else
1451           __x = _S_right(__x);
1452
1453       return const_iterator(__y);
1454     }
1455
1456   template<typename _Key, typename _Val, typename _KeyOfValue,
1457            typename _Compare, typename _Alloc>
1458     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1459     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1460     upper_bound(const _Key& __k)
1461     {
1462       _Link_type __x = _M_begin(); // Current node.
1463       _Link_type __y = _M_end(); // Last node which is greater than __k.
1464
1465       while (__x != 0)
1466         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1467           __y = __x, __x = _S_left(__x);
1468         else
1469           __x = _S_right(__x);
1470
1471       return iterator(__y);
1472     }
1473
1474   template<typename _Key, typename _Val, typename _KeyOfValue,
1475            typename _Compare, typename _Alloc>
1476     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1477     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1478     upper_bound(const _Key& __k) const
1479     {
1480       _Const_Link_type __x = _M_begin(); // Current node.
1481       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1482
1483       while (__x != 0)
1484         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1485           __y = __x, __x = _S_left(__x);
1486         else
1487           __x = _S_right(__x);
1488
1489       return const_iterator(__y);
1490     }
1491
1492   template<typename _Key, typename _Val, typename _KeyOfValue,
1493            typename _Compare, typename _Alloc>
1494     inline
1495     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1496                            _Compare, _Alloc>::iterator,
1497          typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1498     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1499     equal_range(const _Key& __k)
1500     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1501
1502   template<typename _Key, typename _Val, typename _KoV,
1503            typename _Compare, typename _Alloc>
1504     inline
1505     pair<typename _Rb_tree<_Key, _Val, _KoV,
1506                            _Compare, _Alloc>::const_iterator,
1507          typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1508     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1509     equal_range(const _Key& __k) const
1510     { return pair<const_iterator, const_iterator>(lower_bound(__k),
1511                                                   upper_bound(__k)); }
1512
1513   unsigned int
1514   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1515                        const _Rb_tree_node_base* __root);
1516
1517   template<typename _Key, typename _Val, typename _KeyOfValue,
1518            typename _Compare, typename _Alloc>
1519     bool
1520     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1521     {
1522       if (_M_impl._M_node_count == 0 || begin() == end())
1523         return _M_impl._M_node_count == 0 && begin() == end()
1524                && this->_M_impl._M_header._M_left == _M_end()
1525                && this->_M_impl._M_header._M_right == _M_end();
1526
1527       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1528       for (const_iterator __it = begin(); __it != end(); ++__it)
1529         {
1530           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1531           _Const_Link_type __L = _S_left(__x);
1532           _Const_Link_type __R = _S_right(__x);
1533
1534           if (__x->_M_color == _S_red)
1535             if ((__L && __L->_M_color == _S_red)
1536                 || (__R && __R->_M_color == _S_red))
1537               return false;
1538
1539           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1540             return false;
1541           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1542             return false;
1543
1544           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1545             return false;
1546         }
1547
1548       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1549         return false;
1550       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1551         return false;
1552       return true;
1553     }
1554
1555 _GLIBCXX_END_NAMESPACE
1556
1557 #endif