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

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1996,1997
  33  * Silicon Graphics Computer Systems, Inc.
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Silicon Graphics makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1994
  45  * Hewlett-Packard Company
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Hewlett-Packard Company makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  *
  55  *
  56  */
  57
  58 /** @file stl_tree.h
  59  *  This is an internal header file, included by other library headers.
  60  *  You should not attempt to use it directly.
  61  */
  62
  63 #ifndef _TREE_H
  64 #define _TREE_H 1
  65
  66 /*
  67
  68 Red-black tree class, designed for use in implementing STL
  69 associative containers (set, multiset, map, and multimap). The
  70 insertion and deletion algorithms are based on those in Cormen,
  71 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  72 except that
  73
  74 (1) the header cell is maintained with links not only to the root
  75 but also to the leftmost node of the tree, to enable constant time
  76 begin(), and to the rightmost node of the tree, to enable linear time
  77 performance when used with the generic set algorithms (set_union,
  78 etc.);
  79
  80 (2) when a node being deleted has two children its successor node is
  81 relinked into its place, rather than copied, so that the only
  82 iterators invalidated are those referring to the deleted node.
  83
  84 */
  85
  86 #include <bits/stl_algobase.h>
  87 #include <bits/allocator.h>
  88 #include <bits/stl_construct.h>
  89 #include <bits/stl_function.h>
  90
  91 namespace std
  92 {
  93   enum _Rb_tree_color { _S_red = false, _S_black = true };
  94
  95   struct _Rb_tree_node_base
  96   {
  97     typedef _Rb_tree_node_base* _Base_ptr;
  98     typedef const _Rb_tree_node_base* _Const_Base_ptr;
  99
 100     _Rb_tree_color      _M_color;
 101     _Base_ptr           _M_parent;
 102     _Base_ptr           _M_left;
 103     _Base_ptr           _M_right;
 104
 105     static _Base_ptr
 106     _S_minimum(_Base_ptr __x)
 107     {
 108       while (__x->_M_left != 0) __x = __x->_M_left;
 109       return __x;
 110     }
 111
 112     static _Const_Base_ptr
 113     _S_minimum(_Const_Base_ptr __x)
 114     {
 115       while (__x->_M_left != 0) __x = __x->_M_left;
 116       return __x;
 117     }
 118
 119     static _Base_ptr
 120     _S_maximum(_Base_ptr __x)
 121     {
 122       while (__x->_M_right != 0) __x = __x->_M_right;
 123       return __x;
 124     }
 125
 126     static _Const_Base_ptr
 127     _S_maximum(_Const_Base_ptr __x)
 128     {
 129       while (__x->_M_right != 0) __x = __x->_M_right;
 130       return __x;
 131     }
 132   };
 133
 134   template<typename _Val>
 135     struct _Rb_tree_node : public _Rb_tree_node_base
 136     {
 137       typedef _Rb_tree_node<_Val>* _Link_type;
 138       _Val _M_value_field;
 139     };
 140
 141   _Rb_tree_node_base*
 142   _Rb_tree_increment(_Rb_tree_node_base* __x);
 143
 144   const _Rb_tree_node_base*
 145   _Rb_tree_increment(const _Rb_tree_node_base* __x);
 146
 147   _Rb_tree_node_base*
 148   _Rb_tree_decrement(_Rb_tree_node_base* __x);
 149
 150   const _Rb_tree_node_base*
 151   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
 152
 153   template<typename _Tp>
 154     struct _Rb_tree_iterator
 155     {
 156       typedef _Tp  value_type;
 157       typedef _Tp& reference;
 158       typedef _Tp* pointer;
 159
 160       typedef bidirectional_iterator_tag iterator_category;
 161       typedef ptrdiff_t                  difference_type;
 162
 163       typedef _Rb_tree_iterator<_Tp>        _Self;
 164       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 165       typedef _Rb_tree_node<_Tp>*           _Link_type;
 166
 167       _Rb_tree_iterator() {}
 168
 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
 239       _Rb_tree_const_iterator(_Link_type __x)
 240       : _M_node(__x) {}
 241
 242       _Rb_tree_const_iterator(const iterator& __it)
 243       : _M_node(__it._M_node) {}
 244
 245       reference
 246       operator*() const
 247       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 248
 249       pointer
 250       operator->() const
 251       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 252
 253       _Self&
 254       operator++()
 255       {
 256         _M_node = _Rb_tree_increment(_M_node);
 257         return *this;
 258       }
 259
 260       _Self
 261       operator++(int)
 262       {
 263         _Self __tmp = *this;
 264         _M_node = _Rb_tree_increment(_M_node);
 265         return __tmp;
 266       }
 267
 268       _Self&
 269       operator--()
 270       {
 271         _M_node = _Rb_tree_decrement(_M_node);
 272         return *this;
 273       }
 274
 275       _Self
 276       operator--(int)
 277       {
 278         _Self __tmp = *this;
 279         _M_node = _Rb_tree_decrement(_M_node);
 280         return __tmp;
 281       }
 282
 283       bool
 284       operator==(const _Self& __x) const
 285       { return _M_node == __x._M_node; }
 286
 287       bool
 288       operator!=(const _Self& __x) const
 289       { return _M_node != __x._M_node; }
 290
 291       _Base_ptr _M_node;
 292   };
 293
 294   template<typename _Val>
 295     inline bool
 296     operator==(const _Rb_tree_iterator<_Val>& __x,
 297                const _Rb_tree_const_iterator<_Val>& __y)
 298     { return __x._M_node == __y._M_node; }
 299
 300   template<typename _Val>
 301     inline bool
 302     operator!=(const _Rb_tree_iterator<_Val>& __x,
 303                const _Rb_tree_const_iterator<_Val>& __y)
 304     { return __x._M_node != __y._M_node; }
 305
 306   void
 307   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
 308                        _Rb_tree_node_base*& __root);
 309
 310   void
 311   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
 312                         _Rb_tree_node_base*& __root);
 313
 314   void
 315   _Rb_tree_insert_and_rebalance(const bool          __insert_left,
 316                                 _Rb_tree_node_base* __x,
 317                                 _Rb_tree_node_base* __p,
 318                                 _Rb_tree_node_base& __header);
 319
 320   _Rb_tree_node_base*
 321   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 322                                _Rb_tree_node_base&       __header);
 323
 324
 325   template<typename _Key, typename _Val, typename _KeyOfValue,
 326            typename _Compare, typename _Alloc = allocator<_Val> >
 327     class _Rb_tree
 328       : protected _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 329     {
 330       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 331               _Node_allocator;
 332
 333     protected:
 334       typedef _Rb_tree_node_base* _Base_ptr;
 335       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 336       typedef _Rb_tree_node<_Val> _Rb_tree_node;
 337
 338     public:
 339       typedef _Key key_type;
 340       typedef _Val value_type;
 341       typedef value_type* pointer;
 342       typedef const value_type* const_pointer;
 343       typedef value_type& reference;
 344       typedef const value_type& const_reference;
 345       typedef _Rb_tree_node* _Link_type;
 346       typedef const _Rb_tree_node* _Const_Link_type;
 347       typedef size_t size_type;
 348       typedef ptrdiff_t difference_type;
 349
 350       typedef _Alloc allocator_type;
 351       allocator_type get_allocator() const
 352       { return *static_cast<const _Node_allocator*>(this); }
 353
 354     protected:
 355       _Rb_tree_node*
 356       _M_get_node()
 357       { return _Node_allocator::allocate(1); }
 358
 359       void
 360       _M_put_node(_Rb_tree_node* __p)
 361       { _Node_allocator::deallocate(__p, 1); }
 362
 363       _Link_type
 364       _M_create_node(const value_type& __x)
 365       {
 366         _Link_type __tmp = _M_get_node();
 367         try
 368           { std::_Construct(&__tmp->_M_value_field, __x); }
 369         catch(...)
 370           {
 371             _M_put_node(__tmp);
 372             __throw_exception_again;
 373           }
 374         return __tmp;
 375       }
 376
 377       _Link_type
 378       _M_clone_node(_Const_Link_type __x)
 379       {
 380         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 381         __tmp->_M_color = __x->_M_color;
 382         __tmp->_M_left = 0;
 383         __tmp->_M_right = 0;
 384         return __tmp;
 385       }
 386
 387       void
 388       destroy_node(_Link_type __p)
 389       {
 390         std::_Destroy(&__p->_M_value_field);
 391         _M_put_node(__p);
 392       }
 393
 394     protected:
 395       _Rb_tree_node_base _M_header;
 396       size_type _M_node_count; // keeps track of size of tree
 397       _Compare _M_key_compare;
 398
 399     protected:
 400       _Base_ptr&
 401       _M_root()
 402       { return this->_M_header._M_parent; }
 403
 404       _Const_Base_ptr
 405       _M_root() const
 406       { return this->_M_header._M_parent; }
 407
 408       _Base_ptr&
 409       _M_leftmost()
 410       { return this->_M_header._M_left; }
 411
 412       _Const_Base_ptr
 413       _M_leftmost() const
 414       { return this->_M_header._M_left; }
 415
 416       _Base_ptr&
 417       _M_rightmost()
 418       { return this->_M_header._M_right; }
 419
 420       _Const_Base_ptr
 421       _M_rightmost() const
 422       { return this->_M_header._M_right; }
 423
 424       _Link_type
 425       _M_begin()
 426       { return static_cast<_Link_type>(this->_M_header._M_parent); }
 427
 428       _Const_Link_type
 429       _M_begin() const
 430       { return static_cast<_Const_Link_type>(this->_M_header._M_parent); }
 431
 432       _Link_type
 433       _M_end()
 434       { return static_cast<_Link_type>(&this->_M_header); }
 435
 436       _Const_Link_type
 437       _M_end() const
 438       { return static_cast<_Const_Link_type>(&this->_M_header); }
 439
 440       static const_reference
 441       _S_value(_Const_Link_type __x)
 442       { return __x->_M_value_field; }
 443
 444       static const _Key&
 445       _S_key(_Const_Link_type __x)
 446       { return _KeyOfValue()(_S_value(__x)); }
 447
 448       static _Link_type
 449       _S_left(_Base_ptr __x)
 450       { return static_cast<_Link_type>(__x->_M_left); }
 451
 452       static _Const_Link_type
 453       _S_left(_Const_Base_ptr __x)
 454       { return static_cast<_Const_Link_type>(__x->_M_left); }
 455
 456       static _Link_type
 457       _S_right(_Base_ptr __x)
 458       { return static_cast<_Link_type>(__x->_M_right); }
 459
 460       static _Const_Link_type
 461       _S_right(_Const_Base_ptr __x)
 462       { return static_cast<_Const_Link_type>(__x->_M_right); }
 463
 464       static const_reference
 465       _S_value(_Const_Base_ptr __x)
 466       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 467
 468       static const _Key&
 469       _S_key(_Const_Base_ptr __x)
 470       { return _KeyOfValue()(_S_value(__x)); }
 471
 472       static _Base_ptr
 473       _S_minimum(_Base_ptr __x)
 474       { return _Rb_tree_node_base::_S_minimum(__x); }
 475
 476       static _Const_Base_ptr
 477       _S_minimum(_Const_Base_ptr __x)
 478       { return _Rb_tree_node_base::_S_minimum(__x); }
 479
 480       static _Base_ptr
 481       _S_maximum(_Base_ptr __x)
 482       { return _Rb_tree_node_base::_S_maximum(__x); }
 483
 484       static _Const_Base_ptr
 485       _S_maximum(_Const_Base_ptr __x)
 486       { return _Rb_tree_node_base::_S_maximum(__x); }
 487
 488     public:
 489       typedef _Rb_tree_iterator<value_type>       iterator;
 490       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 491
 492       typedef std::reverse_iterator<iterator>       reverse_iterator;
 493       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 494
 495     private:
 496       iterator
 497       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 498
 499       _Link_type
 500       _M_copy(_Const_Link_type __x, _Link_type __p);
 501
 502       void
 503       _M_erase(_Link_type __x);
 504
 505     public:
 506       // allocation/deallocation
 507       _Rb_tree()
 508         : _Node_allocator(allocator_type()),
 509           _M_node_count(0),
 510           _M_key_compare()
 511       { _M_empty_initialize(); }
 512
 513       _Rb_tree(const _Compare& __comp)
 514         : _Node_allocator(allocator_type()),
 515           _M_node_count(0),
 516           _M_key_compare(__comp)
 517       { _M_empty_initialize(); }
 518
 519       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 520         : _Node_allocator(__a),
 521           _M_node_count(0),
 522           _M_key_compare(__comp)
 523       { _M_empty_initialize(); }
 524
 525       _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
 526         : _Node_allocator(__x.get_allocator()),
 527           _M_node_count(0),
 528           _M_key_compare(__x._M_key_compare)
 529       {
 530         if (__x._M_root() == 0)
 531           _M_empty_initialize();
 532         else
 533           {
 534             this->_M_header._M_color = _S_red;
 535             _M_root() = _M_copy(__x._M_begin(), _M_end());
 536             _M_leftmost() = _S_minimum(_M_root());
 537             _M_rightmost() = _S_maximum(_M_root());
 538           }
 539         _M_node_count = __x._M_node_count;
 540       }
 541
 542       ~_Rb_tree() { _M_erase(_M_begin()); }
 543
 544       _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
 545       operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
 546
 547     private:
 548       void _M_empty_initialize()
 549       {
 550         // Used to distinguish header from __root, in iterator.operator++.
 551         this->_M_header._M_color = _S_red;
 552         _M_root() = 0;
 553         _M_leftmost() = _M_end();
 554         _M_rightmost() = _M_end();
 555       }
 556
 557     public:
 558       // Accessors.
 559       _Compare
 560       key_comp() const
 561       { return _M_key_compare; }
 562
 563       iterator
 564       begin()
 565       { return static_cast<_Link_type>(this->_M_header._M_left); }
 566
 567       const_iterator
 568       begin() const
 569       { return static_cast<_Const_Link_type>(this->_M_header._M_left); }
 570
 571       iterator
 572       end()
 573       { return static_cast<_Link_type>(&this->_M_header); }
 574
 575       const_iterator
 576       end() const
 577       { return static_cast<_Const_Link_type>(&this->_M_header); }
 578
 579       reverse_iterator
 580       rbegin()
 581       { return reverse_iterator(end()); }
 582
 583       const_reverse_iterator
 584       rbegin() const
 585       { return const_reverse_iterator(end()); }
 586
 587       reverse_iterator
 588       rend()
 589       { return reverse_iterator(begin()); }
 590
 591       const_reverse_iterator
 592       rend() const
 593       { return const_reverse_iterator(begin()); }
 594
 595       bool
 596       empty() const
 597       { return _M_node_count == 0; }
 598
 599       size_type
 600       size() const
 601       { return _M_node_count; }
 602
 603       size_type
 604       max_size() const
 605       { return size_type(-1); }
 606
 607       void
 608       swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
 609
 610       // Insert/erase.
 611       pair<iterator,bool>
 612       insert_unique(const value_type& __x);
 613
 614       iterator
 615       insert_equal(const value_type& __x);
 616
 617       iterator
 618       insert_unique(iterator __position, const value_type& __x);
 619
 620       iterator
 621       insert_equal(iterator __position, const value_type& __x);
 622
 623       template<typename _InputIterator>
 624       void
 625       insert_unique(_InputIterator __first, _InputIterator __last);
 626
 627       template<typename _InputIterator>
 628       void
 629       insert_equal(_InputIterator __first, _InputIterator __last);
 630
 631       void
 632       erase(iterator __position);
 633
 634       size_type
 635       erase(const key_type& __x);
 636
 637       void
 638       erase(iterator __first, iterator __last);
 639
 640       void
 641       erase(const key_type* __first, const key_type* __last);
 642
 643       void
 644       clear()
 645       {
 646         _M_erase(_M_begin());
 647         _M_leftmost() = _M_end();
 648         _M_root() = 0;
 649         _M_rightmost() = _M_end();
 650         _M_node_count = 0;
 651       }
 652
 653       // Set operations.
 654       iterator
 655       find(const key_type& __x);
 656
 657       const_iterator
 658       find(const key_type& __x) const;
 659
 660       size_type
 661       count(const key_type& __x) const;
 662
 663       iterator
 664       lower_bound(const key_type& __x);
 665
 666       const_iterator
 667       lower_bound(const key_type& __x) const;
 668
 669       iterator
 670       upper_bound(const key_type& __x);
 671
 672       const_iterator
 673       upper_bound(const key_type& __x) const;
 674
 675       pair<iterator,iterator>
 676       equal_range(const key_type& __x);
 677
 678       pair<const_iterator, const_iterator>
 679       equal_range(const key_type& __x) const;
 680
 681       // Debugging.
 682       bool
 683       __rb_verify() const;
 684     };
 685
 686   template<typename _Key, typename _Val, typename _KeyOfValue,
 687            typename _Compare, typename _Alloc>
 688     inline bool
 689     operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 690                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 691     {
 692       return __x.size() == __y.size()
 693              && equal(__x.begin(), __x.end(), __y.begin());
 694     }
 695
 696   template<typename _Key, typename _Val, typename _KeyOfValue,
 697            typename _Compare, typename _Alloc>
 698     inline bool
 699     operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 700               const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 701     {
 702       return lexicographical_compare(__x.begin(), __x.end(),
 703                                      __y.begin(), __y.end());
 704     }
 705
 706   template<typename _Key, typename _Val, typename _KeyOfValue,
 707            typename _Compare, typename _Alloc>
 708     inline bool
 709     operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 710                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 711     { return !(__x == __y); }
 712
 713   template<typename _Key, typename _Val, typename _KeyOfValue,
 714            typename _Compare, typename _Alloc>
 715     inline bool
 716     operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 717               const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 718     { return __y < __x; }
 719
 720   template<typename _Key, typename _Val, typename _KeyOfValue,
 721            typename _Compare, typename _Alloc>
 722     inline bool
 723     operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 724                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 725   { return !(__y < __x); }
 726
 727   template<typename _Key, typename _Val, typename _KeyOfValue,
 728            typename _Compare, typename _Alloc>
 729     inline bool
 730     operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 731                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 732   { return !(__x < __y); }
 733
 734   template<typename _Key, typename _Val, typename _KeyOfValue,
 735            typename _Compare, typename _Alloc>
 736     inline void
 737     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 738          _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 739     { __x.swap(__y); }
 740
 741   template<typename _Key, typename _Val, typename _KeyOfValue,
 742            typename _Compare, typename _Alloc>
 743     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
 744     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 745     operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
 746     {
 747       if (this != &__x)
 748         {
 749           // Note that _Key may be a constant type.
 750           clear();
 751           _M_key_compare = __x._M_key_compare;
 752           if (__x._M_root() != 0)
 753             {
 754               _M_root() = _M_copy(__x._M_begin(), _M_end());
 755               _M_leftmost() = _S_minimum(_M_root());
 756               _M_rightmost() = _S_maximum(_M_root());
 757               _M_node_count = __x._M_node_count;
 758             }
 759         }
 760       return *this;
 761     }
 762
 763   template<typename _Key, typename _Val, typename _KeyOfValue,
 764            typename _Compare, typename _Alloc>
 765     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 766     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 767     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 768     {
 769       _Link_type __z = _M_create_node(__v);
 770       bool __insert_left;
 771
 772       __insert_left = __x != 0 || __p == _M_end()
 773                       || _M_key_compare(_KeyOfValue()(__v), _S_key(__p));
 774
 775       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  this->_M_header);
 776       ++_M_node_count;
 777       return iterator(__z);
 778     }
 779
 780   template<typename _Key, typename _Val, typename _KeyOfValue,
 781            typename _Compare, typename _Alloc>
 782     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 783     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 784     insert_equal(const _Val& __v)
 785     {
 786       _Link_type __x = _M_begin();
 787       _Link_type __y = _M_end();
 788       while (__x != 0)
 789         {
 790           __y = __x;
 791           __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 792                 _S_left(__x) : _S_right(__x);
 793         }
 794       return _M_insert(__x, __y, __v);
 795     }
 796
 797   template<typename _Key, typename _Val, typename _KeyOfValue,
 798            typename _Compare, typename _Alloc>
 799     void
 800     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 801     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
 802     {
 803       if (_M_root() == 0)
 804       {
 805         if (__t._M_root() != 0)
 806         {
 807           _M_root() = __t._M_root();
 808           _M_leftmost() = __t._M_leftmost();
 809           _M_rightmost() = __t._M_rightmost();
 810           _M_root()->_M_parent = _M_end();
 811
 812           __t._M_root() = 0;
 813           __t._M_leftmost() = __t._M_end();
 814           __t._M_rightmost() = __t._M_end();
 815         }
 816       }
 817       else if (__t._M_root() == 0)
 818       {
 819         __t._M_root() = _M_root();
 820         __t._M_leftmost() = _M_leftmost();
 821         __t._M_rightmost() = _M_rightmost();
 822         __t._M_root()->_M_parent = __t._M_end();
 823
 824         _M_root() = 0;
 825         _M_leftmost() = _M_end();
 826         _M_rightmost() = _M_end();
 827       }
 828       else
 829       {
 830         std::swap(_M_root(),__t._M_root());
 831         std::swap(_M_leftmost(),__t._M_leftmost());
 832         std::swap(_M_rightmost(),__t._M_rightmost());
 833
 834         _M_root()->_M_parent = _M_end();
 835         __t._M_root()->_M_parent = __t._M_end();
 836       }
 837       // No need to swap header's color as it does not change.
 838       std::swap(this->_M_node_count, __t._M_node_count);
 839       std::swap(this->_M_key_compare, __t._M_key_compare);
 840     }
 841
 842   template<typename _Key, typename _Val, typename _KeyOfValue,
 843            typename _Compare, typename _Alloc>
 844     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
 845     bool>
 846     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 847     insert_unique(const _Val& __v)
 848     {
 849       _Link_type __x = _M_begin();
 850       _Link_type __y = _M_end();
 851       bool __comp = true;
 852       while (__x != 0)
 853         {
 854           __y = __x;
 855           __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 856           __x = __comp ? _S_left(__x) : _S_right(__x);
 857         }
 858       iterator __j = iterator(__y);
 859       if (__comp)
 860         if (__j == begin())
 861           return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 862         else
 863           --__j;
 864       if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 865         return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 866       return pair<iterator,bool>(__j, false);
 867     }
 868
 869   template<typename _Key, typename _Val, typename _KeyOfValue,
 870            typename _Compare, typename _Alloc>
 871     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 872     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 873     insert_unique(iterator __position, const _Val& __v)
 874     {
 875       if (__position._M_node == _M_leftmost())
 876         {
 877           // begin()
 878           if (size() > 0
 879               && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
 880             return _M_insert(__position._M_node, __position._M_node, __v);
 881           // first argument just needs to be non-null
 882           else
 883             return insert_unique(__v).first;
 884         }
 885       else if (__position._M_node == _M_end())
 886         {
 887           // end()
 888           if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
 889             return _M_insert(0, _M_rightmost(), __v);
 890           else
 891             return insert_unique(__v).first;
 892         }
 893       else
 894         {
 895           iterator __before = __position;
 896           --__before;
 897           if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
 898               && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node)))
 899             {
 900               if (_S_right(__before._M_node) == 0)
 901                 return _M_insert(0, __before._M_node, __v);
 902               else
 903                 return _M_insert(__position._M_node, __position._M_node, __v);
 904               // first argument just needs to be non-null
 905             }
 906           else
 907             return insert_unique(__v).first;
 908         }
 909     }
 910
 911   template<typename _Key, typename _Val, typename _KeyOfValue,
 912            typename _Compare, typename _Alloc>
 913     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 914     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 915     insert_equal(iterator __position, const _Val& __v)
 916     {
 917       if (__position._M_node == _M_leftmost())
 918         {
 919           // begin()
 920           if (size() > 0
 921               && !_M_key_compare(_S_key(__position._M_node),
 922                                  _KeyOfValue()(__v)))
 923             return _M_insert(__position._M_node, __position._M_node, __v);
 924           // first argument just needs to be non-null
 925           else
 926             return insert_equal(__v);
 927         }
 928       else if (__position._M_node == _M_end())
 929         {
 930           // end()
 931           if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
 932             return _M_insert(0, _M_rightmost(), __v);
 933           else
 934             return insert_equal(__v);
 935         }
 936       else
 937         {
 938           iterator __before = __position;
 939           --__before;
 940           if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
 941               && !_M_key_compare(_S_key(__position._M_node),
 942                                  _KeyOfValue()(__v)))
 943             {
 944               if (_S_right(__before._M_node) == 0)
 945                 return _M_insert(0, __before._M_node, __v);
 946               else
 947                 return _M_insert(__position._M_node, __position._M_node, __v);
 948               // first argument just needs to be non-null
 949             }
 950           else
 951             return insert_equal(__v);
 952         }
 953     }
 954
 955   template<typename _Key, typename _Val, typename _KoV,
 956            typename _Cmp, typename _Alloc>
 957     template<class _II>
 958       void
 959       _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
 960       insert_equal(_II __first, _II __last)
 961       {
 962         for ( ; __first != __last; ++__first)
 963           insert_equal(*__first);
 964       }
 965
 966   template<typename _Key, typename _Val, typename _KoV,
 967            typename _Cmp, typename _Alloc>
 968     template<class _II>
 969     void
 970     _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
 971     insert_unique(_II __first, _II __last)
 972     {
 973       for ( ; __first != __last; ++__first)
 974         insert_unique(*__first);
 975     }
 976
 977   template<typename _Key, typename _Val, typename _KeyOfValue,
 978            typename _Compare, typename _Alloc>
 979     inline void
 980     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
 981     {
 982       _Link_type __y =
 983         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
 984                                                              this->_M_header));
 985       destroy_node(__y);
 986       --_M_node_count;
 987     }
 988
 989   template<typename _Key, typename _Val, typename _KeyOfValue,
 990            typename _Compare, typename _Alloc>
 991     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
 992     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
 993     {
 994       pair<iterator,iterator> __p = equal_range(__x);
 995       size_type __n = std::distance(__p.first, __p.second);
 996       erase(__p.first, __p.second);
 997       return __n;
 998     }
 999
1000   template<typename _Key, typename _Val, typename _KoV,
1001            typename _Compare, typename _Alloc>
1002     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1003     _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
1004     _M_copy(_Const_Link_type __x, _Link_type __p)
1005     {
1006       // Structural copy.  __x and __p must be non-null.
1007       _Link_type __top = _M_clone_node(__x);
1008       __top->_M_parent = __p;
1009
1010       try
1011         {
1012           if (__x->_M_right)
1013             __top->_M_right = _M_copy(_S_right(__x), __top);
1014           __p = __top;
1015           __x = _S_left(__x);
1016
1017           while (__x != 0)
1018             {
1019               _Link_type __y = _M_clone_node(__x);
1020               __p->_M_left = __y;
1021               __y->_M_parent = __p;
1022               if (__x->_M_right)
1023                 __y->_M_right = _M_copy(_S_right(__x), __y);
1024               __p = __y;
1025               __x = _S_left(__x);
1026             }
1027         }
1028       catch(...)
1029         {
1030           _M_erase(__top);
1031           __throw_exception_again;
1032         }
1033       return __top;
1034     }
1035
1036   template<typename _Key, typename _Val, typename _KeyOfValue,
1037            typename _Compare, typename _Alloc>
1038     void
1039     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
1040     {
1041       // Erase without rebalancing.
1042       while (__x != 0)
1043         {
1044           _M_erase(_S_right(__x));
1045           _Link_type __y = _S_left(__x);
1046           destroy_node(__x);
1047           __x = __y;
1048         }
1049     }
1050
1051   template<typename _Key, typename _Val, typename _KeyOfValue,
1052            typename _Compare, typename _Alloc>
1053     void
1054     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1055     erase(iterator __first, iterator __last)
1056     {
1057       if (__first == begin() && __last == end())
1058         clear();
1059       else
1060         while (__first != __last) erase(__first++);
1061     }
1062
1063   template<typename _Key, typename _Val, typename _KeyOfValue,
1064            typename _Compare, typename _Alloc>
1065     void
1066     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1067     erase(const _Key* __first, const _Key* __last)
1068     {
1069       while (__first != __last)
1070         erase(*__first++);
1071     }
1072
1073   template<typename _Key, typename _Val, typename _KeyOfValue,
1074            typename _Compare, typename _Alloc>
1075     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1076     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
1077     {
1078       _Link_type __x = _M_begin(); // Current node.
1079       _Link_type __y = _M_end(); // Last node which is not less than __k.
1080
1081       while (__x != 0)
1082         if (!_M_key_compare(_S_key(__x), __k))
1083           __y = __x, __x = _S_left(__x);
1084         else
1085           __x = _S_right(__x);
1086
1087       iterator __j = iterator(__y);
1088       return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1089         end() : __j;
1090     }
1091
1092   template<typename _Key, typename _Val, typename _KeyOfValue,
1093            typename _Compare, typename _Alloc>
1094     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1095     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1096     find(const _Key& __k) const
1097     {
1098       _Const_Link_type __x = _M_begin(); // Current node.
1099       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1100
1101      while (__x != 0)
1102        {
1103          if (!_M_key_compare(_S_key(__x), __k))
1104            __y = __x, __x = _S_left(__x);
1105          else
1106            __x = _S_right(__x);
1107        }
1108      const_iterator __j = const_iterator(__y);
1109      return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1110        end() : __j;
1111     }
1112
1113   template<typename _Key, typename _Val, typename _KeyOfValue,
1114            typename _Compare, typename _Alloc>
1115     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1116     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1117     count(const _Key& __k) const
1118     {
1119       pair<const_iterator, const_iterator> __p = equal_range(__k);
1120       const size_type __n = std::distance(__p.first, __p.second);
1121       return __n;
1122     }
1123
1124   template<typename _Key, typename _Val, typename _KeyOfValue,
1125            typename _Compare, typename _Alloc>
1126     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1127     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1128     lower_bound(const _Key& __k)
1129     {
1130       _Link_type __x = _M_begin(); // Current node.
1131       _Link_type __y = _M_end(); // Last node which is not less than __k.
1132
1133       while (__x != 0)
1134         if (!_M_key_compare(_S_key(__x), __k))
1135           __y = __x, __x = _S_left(__x);
1136         else
1137           __x = _S_right(__x);
1138
1139       return iterator(__y);
1140     }
1141
1142   template<typename _Key, typename _Val, typename _KeyOfValue,
1143            typename _Compare, typename _Alloc>
1144     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1145     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1146     lower_bound(const _Key& __k) const
1147     {
1148       _Const_Link_type __x = _M_begin(); // Current node.
1149       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1150
1151       while (__x != 0)
1152         if (!_M_key_compare(_S_key(__x), __k))
1153           __y = __x, __x = _S_left(__x);
1154         else
1155           __x = _S_right(__x);
1156
1157       return const_iterator(__y);
1158     }
1159
1160   template<typename _Key, typename _Val, typename _KeyOfValue,
1161            typename _Compare, typename _Alloc>
1162     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1163     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1164     upper_bound(const _Key& __k)
1165     {
1166       _Link_type __x = _M_begin(); // Current node.
1167       _Link_type __y = _M_end(); // Last node which is greater than __k.
1168
1169       while (__x != 0)
1170         if (_M_key_compare(__k, _S_key(__x)))
1171           __y = __x, __x = _S_left(__x);
1172         else
1173           __x = _S_right(__x);
1174
1175       return iterator(__y);
1176     }
1177
1178   template<typename _Key, typename _Val, typename _KeyOfValue,
1179            typename _Compare, typename _Alloc>
1180     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1181     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1182     upper_bound(const _Key& __k) const
1183     {
1184       _Const_Link_type __x = _M_begin(); // Current node.
1185       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1186
1187       while (__x != 0)
1188         if (_M_key_compare(__k, _S_key(__x)))
1189           __y = __x, __x = _S_left(__x);
1190         else
1191           __x = _S_right(__x);
1192
1193       return const_iterator(__y);
1194     }
1195
1196   template<typename _Key, typename _Val, typename _KeyOfValue,
1197            typename _Compare, typename _Alloc>
1198     inline
1199     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,
1200                            _Compare,_Alloc>::iterator,
1201          typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
1202     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1203     equal_range(const _Key& __k)
1204     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1205
1206   template<typename _Key, typename _Val, typename _KoV,
1207            typename _Compare, typename _Alloc>
1208   inline
1209   pair<typename _Rb_tree<_Key, _Val, _KoV,
1210                          _Compare, _Alloc>::const_iterator,
1211        typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1212   _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>
1213   ::equal_range(const _Key& __k) const
1214   { return pair<const_iterator, const_iterator>(lower_bound(__k),
1215                                                 upper_bound(__k)); }
1216
1217   unsigned int
1218   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1219                        const _Rb_tree_node_base* __root);
1220
1221   template<typename _Key, typename _Val, typename _KeyOfValue,
1222            typename _Compare, typename _Alloc>
1223     bool
1224     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1225     {
1226     if (_M_node_count == 0 || begin() == end())
1227       return _M_node_count == 0 && begin() == end()
1228              && this->_M_header._M_left == _M_end()
1229              && this->_M_header._M_right == _M_end();
1230
1231     unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1232     for (const_iterator __it = begin(); __it != end(); ++__it)
1233       {
1234         _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1235         _Const_Link_type __L = _S_left(__x);
1236         _Const_Link_type __R = _S_right(__x);
1237
1238         if (__x->_M_color == _S_red)
1239           if ((__L && __L->_M_color == _S_red)
1240               || (__R && __R->_M_color == _S_red))
1241             return false;
1242
1243         if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
1244           return false;
1245         if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
1246           return false;
1247
1248         if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1249           return false;
1250       }
1251
1252     if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1253       return false;
1254     if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1255       return false;
1256     return true;
1257     }
1258 } // namespace std
1259
1260 #endif