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