libstdc++-v3/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       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       const_iterator
 552       _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
 553                 const value_type& __v);
 554
 555       _Link_type
 556       _M_copy(_Const_Link_type __x, _Link_type __p);
 557
 558       void
 559       _M_erase(_Link_type __x);
 560
 561     public:
 562       // allocation/deallocation
 563       _Rb_tree()
 564       { }
 565
 566       _Rb_tree(const _Compare& __comp)
 567       : _M_impl(allocator_type(), __comp)
 568       { }
 569
 570       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 571       : _M_impl(__a, __comp)
 572       { }
 573
 574       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 575       : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare)
 576       {
 577         if (__x._M_root() != 0)
 578           {
 579             _M_root() = _M_copy(__x._M_begin(), _M_end());
 580             _M_leftmost() = _S_minimum(_M_root());
 581             _M_rightmost() = _S_maximum(_M_root());
 582             _M_impl._M_node_count = __x._M_impl._M_node_count;
 583           }
 584       }
 585
 586       ~_Rb_tree()
 587       { _M_erase(_M_begin()); }
 588
 589       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 590       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
 591
 592       // Accessors.
 593       _Compare
 594       key_comp() const
 595       { return _M_impl._M_key_compare; }
 596
 597       iterator
 598       begin()
 599       {
 600         return iterator(static_cast<_Link_type>
 601                         (this->_M_impl._M_header._M_left));
 602       }
 603
 604       const_iterator
 605       begin() const
 606       {
 607         return const_iterator(static_cast<_Const_Link_type>
 608                               (this->_M_impl._M_header._M_left));
 609       }
 610
 611       iterator
 612       end()
 613       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 614
 615       const_iterator
 616       end() const
 617       {
 618         return const_iterator(static_cast<_Const_Link_type>
 619                               (&this->_M_impl._M_header));
 620       }
 621
 622       reverse_iterator
 623       rbegin()
 624       { return reverse_iterator(end()); }
 625
 626       const_reverse_iterator
 627       rbegin() const
 628       { return const_reverse_iterator(end()); }
 629
 630       reverse_iterator
 631       rend()
 632       { return reverse_iterator(begin()); }
 633
 634       const_reverse_iterator
 635       rend() const
 636       { return const_reverse_iterator(begin()); }
 637
 638       bool
 639       empty() const
 640       { return _M_impl._M_node_count == 0; }
 641
 642       size_type
 643       size() const
 644       { return _M_impl._M_node_count; }
 645
 646       size_type
 647       max_size() const
 648       { return size_type(-1); }
 649
 650       void
 651       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
 652
 653       // Insert/erase.
 654       pair<iterator,bool>
 655       insert_unique(const value_type& __x);
 656
 657       iterator
 658       insert_equal(const value_type& __x);
 659
 660       iterator
 661       insert_unique(iterator __position, const value_type& __x);
 662
 663       const_iterator
 664       insert_unique(const_iterator __position, const value_type& __x);
 665
 666       iterator
 667       insert_equal(iterator __position, const value_type& __x);
 668
 669       const_iterator
 670       insert_equal(const_iterator __position, const value_type& __x);
 671
 672       template<typename _InputIterator>
 673         void
 674         insert_unique(_InputIterator __first, _InputIterator __last);
 675
 676       template<typename _InputIterator>
 677         void
 678         insert_equal(_InputIterator __first, _InputIterator __last);
 679
 680       void
 681       erase(iterator __position);
 682
 683       void
 684       erase(const_iterator __position);
 685
 686       size_type
 687       erase(const key_type& __x);
 688
 689       void
 690       erase(iterator __first, iterator __last);
 691
 692       void
 693       erase(const_iterator __first, const_iterator __last);
 694
 695       void
 696       erase(const key_type* __first, const key_type* __last);
 697
 698       void
 699       clear()
 700       {
 701         _M_erase(_M_begin());
 702         _M_leftmost() = _M_end();
 703         _M_root() = 0;
 704         _M_rightmost() = _M_end();
 705         _M_impl._M_node_count = 0;
 706       }
 707
 708       // Set operations.
 709       iterator
 710       find(const key_type& __x);
 711
 712       const_iterator
 713       find(const key_type& __x) const;
 714
 715       size_type
 716       count(const key_type& __x) const;
 717
 718       iterator
 719       lower_bound(const key_type& __x);
 720
 721       const_iterator
 722       lower_bound(const key_type& __x) const;
 723
 724       iterator
 725       upper_bound(const key_type& __x);
 726
 727       const_iterator
 728       upper_bound(const key_type& __x) const;
 729
 730       pair<iterator,iterator>
 731       equal_range(const key_type& __x);
 732
 733       pair<const_iterator, const_iterator>
 734       equal_range(const key_type& __x) const;
 735
 736       // Debugging.
 737       bool
 738       __rb_verify() const;
 739     };
 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     {
 747       return __x.size() == __y.size()
 748              && std::equal(__x.begin(), __x.end(), __y.begin());
 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 std::lexicographical_compare(__x.begin(), __x.end(),
 758                                           __y.begin(), __y.end());
 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     { return !(__x == __y); }
 767
 768   template<typename _Key, typename _Val, typename _KeyOfValue,
 769            typename _Compare, typename _Alloc>
 770     inline bool
 771     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 772               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 773     { return __y < __x; }
 774
 775   template<typename _Key, typename _Val, typename _KeyOfValue,
 776            typename _Compare, typename _Alloc>
 777     inline bool
 778     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 779                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 780     { return !(__y < __x); }
 781
 782   template<typename _Key, typename _Val, typename _KeyOfValue,
 783            typename _Compare, typename _Alloc>
 784     inline bool
 785     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 786                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 787     { return !(__x < __y); }
 788
 789   template<typename _Key, typename _Val, typename _KeyOfValue,
 790            typename _Compare, typename _Alloc>
 791     inline void
 792     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 793          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 794     { __x.swap(__y); }
 795
 796   template<typename _Key, typename _Val, typename _KeyOfValue,
 797            typename _Compare, typename _Alloc>
 798     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 799     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 800     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 801     {
 802       if (this != &__x)
 803         {
 804           // Note that _Key may be a constant type.
 805           clear();
 806           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 807           if (__x._M_root() != 0)
 808             {
 809               _M_root() = _M_copy(__x._M_begin(), _M_end());
 810               _M_leftmost() = _S_minimum(_M_root());
 811               _M_rightmost() = _S_maximum(_M_root());
 812               _M_impl._M_node_count = __x._M_impl._M_node_count;
 813             }
 814         }
 815       return *this;
 816     }
 817
 818   template<typename _Key, typename _Val, typename _KeyOfValue,
 819            typename _Compare, typename _Alloc>
 820     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 821     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 822     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 823     {
 824       bool __insert_left = (__x != 0 || __p == _M_end()
 825                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 826                                                       _S_key(__p)));
 827
 828       _Link_type __z = _M_create_node(__v);
 829
 830       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 831                                     this->_M_impl._M_header);
 832       ++_M_impl._M_node_count;
 833       return iterator(__z);
 834     }
 835
 836   template<typename _Key, typename _Val, typename _KeyOfValue,
 837            typename _Compare, typename _Alloc>
 838     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
 839     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 840     _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
 841     {
 842       bool __insert_left = (__x != 0 || __p == _M_end()
 843                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 844                                                       _S_key(__p)));
 845
 846       _Link_type __z = _M_create_node(__v);
 847
 848       _Rb_tree_insert_and_rebalance(__insert_left, __z,
 849                                     const_cast<_Base_ptr>(__p),
 850                                     this->_M_impl._M_header);
 851       ++_M_impl._M_node_count;
 852       return const_iterator(__z);
 853     }
 854
 855   template<typename _Key, typename _Val, typename _KeyOfValue,
 856            typename _Compare, typename _Alloc>
 857     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 858     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 859     insert_equal(const _Val& __v)
 860     {
 861       _Link_type __x = _M_begin();
 862       _Link_type __y = _M_end();
 863       while (__x != 0)
 864         {
 865           __y = __x;
 866           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 867                 _S_left(__x) : _S_right(__x);
 868         }
 869       return _M_insert(__x, __y, __v);
 870     }
 871
 872   template<typename _Key, typename _Val, typename _KeyOfValue,
 873            typename _Compare, typename _Alloc>
 874     void
 875     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 876     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
 877     {
 878       if (_M_root() == 0)
 879       {
 880         if (__t._M_root() != 0)
 881         {
 882           _M_root() = __t._M_root();
 883           _M_leftmost() = __t._M_leftmost();
 884           _M_rightmost() = __t._M_rightmost();
 885           _M_root()->_M_parent = _M_end();
 886
 887           __t._M_root() = 0;
 888           __t._M_leftmost() = __t._M_end();
 889           __t._M_rightmost() = __t._M_end();
 890         }
 891       }
 892       else if (__t._M_root() == 0)
 893       {
 894         __t._M_root() = _M_root();
 895         __t._M_leftmost() = _M_leftmost();
 896         __t._M_rightmost() = _M_rightmost();
 897         __t._M_root()->_M_parent = __t._M_end();
 898
 899         _M_root() = 0;
 900         _M_leftmost() = _M_end();
 901         _M_rightmost() = _M_end();
 902       }
 903       else
 904       {
 905         std::swap(_M_root(),__t._M_root());
 906         std::swap(_M_leftmost(),__t._M_leftmost());
 907         std::swap(_M_rightmost(),__t._M_rightmost());
 908
 909         _M_root()->_M_parent = _M_end();
 910         __t._M_root()->_M_parent = __t._M_end();
 911       }
 912       // No need to swap header's color as it does not change.
 913       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 914       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 915     }
 916
 917   template<typename _Key, typename _Val, typename _KeyOfValue,
 918            typename _Compare, typename _Alloc>
 919     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 920                            _Compare, _Alloc>::iterator, bool>
 921     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 922     insert_unique(const _Val& __v)
 923     {
 924       _Link_type __x = _M_begin();
 925       _Link_type __y = _M_end();
 926       bool __comp = true;
 927       while (__x != 0)
 928         {
 929           __y = __x;
 930           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 931           __x = __comp ? _S_left(__x) : _S_right(__x);
 932         }
 933       iterator __j = iterator(__y);
 934       if (__comp)
 935         if (__j == begin())
 936           return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 937         else
 938           --__j;
 939       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 940         return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
 941       return pair<iterator, bool>(__j, false);
 942     }
 943
 944   template<typename _Key, typename _Val, typename _KeyOfValue,
 945            typename _Compare, typename _Alloc>
 946     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 947     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 948     insert_unique(iterator __position, const _Val& __v)
 949     {
 950       // end()
 951       if (__position._M_node == _M_end())
 952         {
 953           if (size() > 0
 954               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
 955                                         _KeyOfValue()(__v)))
 956             return _M_insert(0, _M_rightmost(), __v);
 957           else
 958             return insert_unique(__v).first;
 959         }
 960       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
 961                                       _S_key(__position._M_node)))
 962         {
 963           // First, try before...
 964           iterator __before = __position;
 965           if (__position._M_node == _M_leftmost()) // begin()
 966             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
 967           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
 968                                           _KeyOfValue()(__v)))
 969             {
 970               if (_S_right(__before._M_node) == 0)
 971                 return _M_insert(0, __before._M_node, __v);
 972               else
 973                 return _M_insert(__position._M_node,
 974                                  __position._M_node, __v);
 975             }
 976           else
 977             return insert_unique(__v).first;
 978         }
 979       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
 980                                       _KeyOfValue()(__v)))
 981         {
 982           // ... then try after.
 983           iterator __after = __position;
 984           if (__position._M_node == _M_rightmost())
 985             return _M_insert(0, _M_rightmost(), __v);
 986           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
 987                                           _S_key((++__after)._M_node)))
 988             {
 989               if (_S_right(__position._M_node) == 0)
 990                 return _M_insert(0, __position._M_node, __v);
 991               else
 992                 return _M_insert(__after._M_node, __after._M_node, __v);
 993             }
 994           else
 995             return insert_unique(__v).first;
 996         }
 997       else
 998         return __position; // Equivalent keys.
 999     }
1000
1001   template<typename _Key, typename _Val, typename _KeyOfValue,
1002            typename _Compare, typename _Alloc>
1003     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1004     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1005     insert_unique(const_iterator __position, const _Val& __v)
1006     {
1007       // end()
1008       if (__position._M_node == _M_end())
1009         {
1010           if (size() > 0
1011               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1012                                         _KeyOfValue()(__v)))
1013             return _M_insert(0, _M_rightmost(), __v);
1014           else
1015             return const_iterator(insert_unique(__v).first);
1016         }
1017       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1018                                       _S_key(__position._M_node)))
1019         {
1020           // First, try before...
1021           const_iterator __before = __position;
1022           if (__position._M_node == _M_leftmost()) // begin()
1023             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1024           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1025                                           _KeyOfValue()(__v)))
1026             {
1027               if (_S_right(__before._M_node) == 0)
1028                 return _M_insert(0, __before._M_node, __v);
1029               else
1030                 return _M_insert(__position._M_node,
1031                                  __position._M_node, __v);
1032             }
1033           else
1034             return const_iterator(insert_unique(__v).first);
1035         }
1036       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1037                                       _KeyOfValue()(__v)))
1038         {
1039           // ... then try after.
1040           const_iterator __after = __position;
1041           if (__position._M_node == _M_rightmost())
1042             return _M_insert(0, _M_rightmost(), __v);
1043           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1044                                           _S_key((++__after)._M_node)))
1045             {
1046               if (_S_right(__position._M_node) == 0)
1047                 return _M_insert(0, __position._M_node, __v);
1048               else
1049                 return _M_insert(__after._M_node, __after._M_node, __v);
1050             }
1051           else
1052             return const_iterator(insert_unique(__v).first);
1053         }
1054       else
1055         return __position; // Equivalent keys.
1056     }
1057
1058   template<typename _Key, typename _Val, typename _KeyOfValue,
1059            typename _Compare, typename _Alloc>
1060     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1061     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1062     insert_equal(iterator __position, const _Val& __v)
1063     {
1064       // end()
1065       if (__position._M_node == _M_end())
1066         {
1067           if (size() > 0
1068               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1069                                          _S_key(_M_rightmost())))
1070             return _M_insert(0, _M_rightmost(), __v);
1071           else
1072             return insert_equal(__v);
1073         }
1074       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1075                                        _KeyOfValue()(__v)))
1076         {
1077           // First, try before...
1078           iterator __before = __position;
1079           if (__position._M_node == _M_leftmost()) // begin()
1080             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1081           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1082                                            _S_key((--__before)._M_node)))
1083             {
1084               if (_S_right(__before._M_node) == 0)
1085                 return _M_insert(0, __before._M_node, __v);
1086               else
1087                 return _M_insert(__position._M_node,
1088                                  __position._M_node, __v);
1089             }
1090           else
1091             return insert_equal(__v);
1092         }
1093       else
1094         {
1095           // ... then try after.
1096           iterator __after = __position;
1097           if (__position._M_node == _M_rightmost())
1098             return _M_insert(0, _M_rightmost(), __v);
1099           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1100                                            _KeyOfValue()(__v)))
1101             {
1102               if (_S_right(__position._M_node) == 0)
1103                 return _M_insert(0, __position._M_node, __v);
1104               else
1105                 return _M_insert(__after._M_node, __after._M_node, __v);
1106             }
1107           else
1108             return insert_equal(__v);
1109         }
1110     }
1111
1112   template<typename _Key, typename _Val, typename _KeyOfValue,
1113            typename _Compare, typename _Alloc>
1114     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1115     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1116     insert_equal(const_iterator __position, const _Val& __v)
1117     {
1118       // end()
1119       if (__position._M_node == _M_end())
1120         {
1121           if (size() > 0
1122               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1123                                          _S_key(_M_rightmost())))
1124             return _M_insert(0, _M_rightmost(), __v);
1125           else
1126             return const_iterator(insert_equal(__v));
1127         }
1128       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1129                                        _KeyOfValue()(__v)))
1130         {
1131           // First, try before...
1132           const_iterator __before = __position;
1133           if (__position._M_node == _M_leftmost()) // begin()
1134             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1135           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1136                                            _S_key((--__before)._M_node)))
1137             {
1138               if (_S_right(__before._M_node) == 0)
1139                 return _M_insert(0, __before._M_node, __v);
1140               else
1141                 return _M_insert(__position._M_node,
1142                                  __position._M_node, __v);
1143             }
1144           else
1145             return const_iterator(insert_equal(__v));
1146         }
1147       else
1148         {
1149           // ... then try after.
1150           const_iterator __after = __position;
1151           if (__position._M_node == _M_rightmost())
1152             return _M_insert(0, _M_rightmost(), __v);
1153           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1154                                            _KeyOfValue()(__v)))
1155             {
1156               if (_S_right(__position._M_node) == 0)
1157                 return _M_insert(0, __position._M_node, __v);
1158               else
1159                 return _M_insert(__after._M_node, __after._M_node, __v);
1160             }
1161           else
1162             return const_iterator(insert_equal(__v));
1163         }
1164     }
1165
1166   template<typename _Key, typename _Val, typename _KoV,
1167            typename _Cmp, typename _Alloc>
1168     template<class _II>
1169       void
1170       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1171       insert_equal(_II __first, _II __last)
1172       {
1173         for (; __first != __last; ++__first)
1174           insert_equal(end(), *__first);
1175       }
1176
1177   template<typename _Key, typename _Val, typename _KoV,
1178            typename _Cmp, typename _Alloc>
1179     template<class _II>
1180       void
1181       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1182       insert_unique(_II __first, _II __last)
1183       {
1184         for (; __first != __last; ++__first)
1185           insert_unique(end(), *__first);
1186       }
1187
1188   template<typename _Key, typename _Val, typename _KeyOfValue,
1189            typename _Compare, typename _Alloc>
1190     inline void
1191     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1192     erase(iterator __position)
1193     {
1194       _Link_type __y =
1195         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1196                                 (__position._M_node,
1197                                  this->_M_impl._M_header));
1198       destroy_node(__y);
1199       --_M_impl._M_node_count;
1200     }
1201
1202   template<typename _Key, typename _Val, typename _KeyOfValue,
1203            typename _Compare, typename _Alloc>
1204     inline void
1205     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1206     erase(const_iterator __position)
1207     {
1208       _Link_type __y =
1209         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1210                                 (const_cast<_Base_ptr>(__position._M_node),
1211                                  this->_M_impl._M_header));
1212       destroy_node(__y);
1213       --_M_impl._M_node_count;
1214     }
1215
1216   template<typename _Key, typename _Val, typename _KeyOfValue,
1217            typename _Compare, typename _Alloc>
1218     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1219     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1220     erase(const _Key& __x)
1221     {
1222       pair<iterator,iterator> __p = equal_range(__x);
1223       size_type __n = std::distance(__p.first, __p.second);
1224       erase(__p.first, __p.second);
1225       return __n;
1226     }
1227
1228   template<typename _Key, typename _Val, typename _KoV,
1229            typename _Compare, typename _Alloc>
1230     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1231     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1232     _M_copy(_Const_Link_type __x, _Link_type __p)
1233     {
1234       // Structural copy.  __x and __p must be non-null.
1235       _Link_type __top = _M_clone_node(__x);
1236       __top->_M_parent = __p;
1237
1238       try
1239         {
1240           if (__x->_M_right)
1241             __top->_M_right = _M_copy(_S_right(__x), __top);
1242           __p = __top;
1243           __x = _S_left(__x);
1244
1245           while (__x != 0)
1246             {
1247               _Link_type __y = _M_clone_node(__x);
1248               __p->_M_left = __y;
1249               __y->_M_parent = __p;
1250               if (__x->_M_right)
1251                 __y->_M_right = _M_copy(_S_right(__x), __y);
1252               __p = __y;
1253               __x = _S_left(__x);
1254             }
1255         }
1256       catch(...)
1257         {
1258           _M_erase(__top);
1259           __throw_exception_again;
1260         }
1261       return __top;
1262     }
1263
1264   template<typename _Key, typename _Val, typename _KeyOfValue,
1265            typename _Compare, typename _Alloc>
1266     void
1267     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1268     _M_erase(_Link_type __x)
1269     {
1270       // Erase without rebalancing.
1271       while (__x != 0)
1272         {
1273           _M_erase(_S_right(__x));
1274           _Link_type __y = _S_left(__x);
1275           destroy_node(__x);
1276           __x = __y;
1277         }
1278     }
1279
1280   template<typename _Key, typename _Val, typename _KeyOfValue,
1281            typename _Compare, typename _Alloc>
1282     void
1283     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1284     erase(iterator __first, iterator __last)
1285     {
1286       if (__first == begin() && __last == end())
1287         clear();
1288       else
1289         while (__first != __last)
1290           erase(__first++);
1291     }
1292
1293   template<typename _Key, typename _Val, typename _KeyOfValue,
1294            typename _Compare, typename _Alloc>
1295     void
1296     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1297     erase(const_iterator __first, const_iterator __last)
1298     {
1299       if (__first == begin() && __last == end())
1300         clear();
1301       else
1302         while (__first != __last)
1303           erase(__first++);
1304     }
1305
1306   template<typename _Key, typename _Val, typename _KeyOfValue,
1307            typename _Compare, typename _Alloc>
1308     void
1309     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1310     erase(const _Key* __first, const _Key* __last)
1311     {
1312       while (__first != __last)
1313         erase(*__first++);
1314     }
1315
1316   template<typename _Key, typename _Val, typename _KeyOfValue,
1317            typename _Compare, typename _Alloc>
1318     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1319     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1320     find(const _Key& __k)
1321     {
1322       _Link_type __x = _M_begin(); // Current node.
1323       _Link_type __y = _M_end(); // Last node which is not less than __k.
1324
1325       while (__x != 0)
1326         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1327           __y = __x, __x = _S_left(__x);
1328         else
1329           __x = _S_right(__x);
1330
1331       iterator __j = iterator(__y);
1332       return (__j == end()
1333               || _M_impl._M_key_compare(__k,
1334                                         _S_key(__j._M_node))) ? end() : __j;
1335     }
1336
1337   template<typename _Key, typename _Val, typename _KeyOfValue,
1338            typename _Compare, typename _Alloc>
1339     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1340     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1341     find(const _Key& __k) const
1342     {
1343       _Const_Link_type __x = _M_begin(); // Current node.
1344       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1345
1346      while (__x != 0)
1347        {
1348          if (!_M_impl._M_key_compare(_S_key(__x), __k))
1349            __y = __x, __x = _S_left(__x);
1350          else
1351            __x = _S_right(__x);
1352        }
1353      const_iterator __j = const_iterator(__y);
1354      return (__j == end()
1355              || _M_impl._M_key_compare(__k,
1356                                        _S_key(__j._M_node))) ? end() : __j;
1357     }
1358
1359   template<typename _Key, typename _Val, typename _KeyOfValue,
1360            typename _Compare, typename _Alloc>
1361     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1362     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1363     count(const _Key& __k) const
1364     {
1365       pair<const_iterator, const_iterator> __p = equal_range(__k);
1366       const size_type __n = std::distance(__p.first, __p.second);
1367       return __n;
1368     }
1369
1370   template<typename _Key, typename _Val, typename _KeyOfValue,
1371            typename _Compare, typename _Alloc>
1372     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1373     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1374     lower_bound(const _Key& __k)
1375     {
1376       _Link_type __x = _M_begin(); // Current node.
1377       _Link_type __y = _M_end(); // Last node which is not less than __k.
1378
1379       while (__x != 0)
1380         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1381           __y = __x, __x = _S_left(__x);
1382         else
1383           __x = _S_right(__x);
1384
1385       return iterator(__y);
1386     }
1387
1388   template<typename _Key, typename _Val, typename _KeyOfValue,
1389            typename _Compare, typename _Alloc>
1390     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1391     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1392     lower_bound(const _Key& __k) const
1393     {
1394       _Const_Link_type __x = _M_begin(); // Current node.
1395       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1396
1397       while (__x != 0)
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       return const_iterator(__y);
1404     }
1405
1406   template<typename _Key, typename _Val, typename _KeyOfValue,
1407            typename _Compare, typename _Alloc>
1408     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1409     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1410     upper_bound(const _Key& __k)
1411     {
1412       _Link_type __x = _M_begin(); // Current node.
1413       _Link_type __y = _M_end(); // Last node which is greater than __k.
1414
1415       while (__x != 0)
1416         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1417           __y = __x, __x = _S_left(__x);
1418         else
1419           __x = _S_right(__x);
1420
1421       return iterator(__y);
1422     }
1423
1424   template<typename _Key, typename _Val, typename _KeyOfValue,
1425            typename _Compare, typename _Alloc>
1426     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1427     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1428     upper_bound(const _Key& __k) const
1429     {
1430       _Const_Link_type __x = _M_begin(); // Current node.
1431       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1432
1433       while (__x != 0)
1434         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1435           __y = __x, __x = _S_left(__x);
1436         else
1437           __x = _S_right(__x);
1438
1439       return const_iterator(__y);
1440     }
1441
1442   template<typename _Key, typename _Val, typename _KeyOfValue,
1443            typename _Compare, typename _Alloc>
1444     inline
1445     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1446                            _Compare, _Alloc>::iterator,
1447          typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1448     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1449     equal_range(const _Key& __k)
1450     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1451
1452   template<typename _Key, typename _Val, typename _KoV,
1453            typename _Compare, typename _Alloc>
1454     inline
1455     pair<typename _Rb_tree<_Key, _Val, _KoV,
1456                            _Compare, _Alloc>::const_iterator,
1457          typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1458     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1459     equal_range(const _Key& __k) const
1460     { return pair<const_iterator, const_iterator>(lower_bound(__k),
1461                                                   upper_bound(__k)); }
1462
1463   unsigned int
1464   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1465                        const _Rb_tree_node_base* __root);
1466
1467   template<typename _Key, typename _Val, typename _KeyOfValue,
1468            typename _Compare, typename _Alloc>
1469     bool
1470     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1471     {
1472       if (_M_impl._M_node_count == 0 || begin() == end())
1473         return _M_impl._M_node_count == 0 && begin() == end()
1474                && this->_M_impl._M_header._M_left == _M_end()
1475                && this->_M_impl._M_header._M_right == _M_end();
1476
1477       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1478       for (const_iterator __it = begin(); __it != end(); ++__it)
1479         {
1480           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1481           _Const_Link_type __L = _S_left(__x);
1482           _Const_Link_type __R = _S_right(__x);
1483
1484           if (__x->_M_color == _S_red)
1485             if ((__L && __L->_M_color == _S_red)
1486                 || (__R && __R->_M_color == _S_red))
1487               return false;
1488
1489           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1490             return false;
1491           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1492             return false;
1493
1494           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1495             return false;
1496         }
1497
1498       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1499         return false;
1500       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1501         return false;
1502       return true;
1503     }
1504
1505 _GLIBCXX_END_NAMESPACE
1506
1507 #endif