contrib/gcc-3.4/libstdc++-v3/include/bits/stl_tree.h

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