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_insert_and_rebalance(const bool __insert_left,
 310                                 _Rb_tree_node_base* __x,
 311                                 _Rb_tree_node_base* __p,
 312                                 _Rb_tree_node_base& __header);
 313
 314   _Rb_tree_node_base*
 315   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 316                                _Rb_tree_node_base& __header);
 317
 318
 319   template<typename _Key, typename _Val, typename _KeyOfValue,
 320            typename _Compare, typename _Alloc = allocator<_Val> >
 321     class _Rb_tree
 322     {
 323       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 324               _Node_allocator;
 325
 326     protected:
 327       typedef _Rb_tree_node_base* _Base_ptr;
 328       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 329       typedef _Rb_tree_node<_Val> _Rb_tree_node;
 330
 331     public:
 332       typedef _Key key_type;
 333       typedef _Val value_type;
 334       typedef value_type* pointer;
 335       typedef const value_type* const_pointer;
 336       typedef value_type& reference;
 337       typedef const value_type& const_reference;
 338       typedef _Rb_tree_node* _Link_type;
 339       typedef const _Rb_tree_node* _Const_Link_type;
 340       typedef size_t size_type;
 341       typedef ptrdiff_t difference_type;
 342       typedef _Alloc allocator_type;
 343
 344       _Node_allocator&
 345       _M_get_Node_allocator()
 346       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
 347
 348       const _Node_allocator&
 349       _M_get_Node_allocator() const
 350       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 351
 352       allocator_type
 353       get_allocator() const
 354       { return allocator_type(_M_get_Node_allocator()); }
 355
 356     protected:
 357       _Rb_tree_node*
 358       _M_get_node()
 359       { return _M_impl._Node_allocator::allocate(1); }
 360
 361       void
 362       _M_put_node(_Rb_tree_node* __p)
 363       { _M_impl._Node_allocator::deallocate(__p, 1); }
 364
 365       _Link_type
 366       _M_create_node(const value_type& __x)
 367       {
 368         _Link_type __tmp = _M_get_node();
 369         try
 370           { get_allocator().construct(&__tmp->_M_value_field, __x); }
 371         catch(...)
 372           {
 373             _M_put_node(__tmp);
 374             __throw_exception_again;
 375           }
 376         return __tmp;
 377       }
 378
 379       _Link_type
 380       _M_clone_node(_Const_Link_type __x)
 381       {
 382         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 383         __tmp->_M_color = __x->_M_color;
 384         __tmp->_M_left = 0;
 385         __tmp->_M_right = 0;
 386         return __tmp;
 387       }
 388
 389       void
 390       _M_destroy_node(_Link_type __p)
 391       {
 392         get_allocator().destroy(&__p->_M_value_field);
 393         _M_put_node(__p);
 394       }
 395
 396     protected:
 397       template<typename _Key_compare,
 398                bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
 399         struct _Rb_tree_impl : public _Node_allocator
 400         {
 401           _Key_compare          _M_key_compare;
 402           _Rb_tree_node_base    _M_header;
 403           size_type             _M_node_count; // Keeps track of size of tree.
 404
 405           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 406                         const _Key_compare& __comp = _Key_compare())
 407           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 408             _M_node_count(0)
 409           {
 410             this->_M_header._M_color = _S_red;
 411             this->_M_header._M_parent = 0;
 412             this->_M_header._M_left = &this->_M_header;
 413             this->_M_header._M_right = &this->_M_header;
 414           }
 415         };
 416
 417       // Specialization for _Comparison types that are not capable of
 418       // being base classes / super classes.
 419       template<typename _Key_compare>
 420         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
 421         {
 422           _Key_compare          _M_key_compare;
 423           _Rb_tree_node_base    _M_header;
 424           size_type             _M_node_count; // Keeps track of size of tree.
 425
 426           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 427                         const _Key_compare& __comp = _Key_compare())
 428           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 429             _M_node_count(0)
 430           {
 431             this->_M_header._M_color = _S_red;
 432             this->_M_header._M_parent = 0;
 433             this->_M_header._M_left = &this->_M_header;
 434             this->_M_header._M_right = &this->_M_header;
 435           }
 436         };
 437
 438       _Rb_tree_impl<_Compare> _M_impl;
 439
 440     protected:
 441       _Base_ptr&
 442       _M_root()
 443       { return this->_M_impl._M_header._M_parent; }
 444
 445       _Const_Base_ptr
 446       _M_root() const
 447       { return this->_M_impl._M_header._M_parent; }
 448
 449       _Base_ptr&
 450       _M_leftmost()
 451       { return this->_M_impl._M_header._M_left; }
 452
 453       _Const_Base_ptr
 454       _M_leftmost() const
 455       { return this->_M_impl._M_header._M_left; }
 456
 457       _Base_ptr&
 458       _M_rightmost()
 459       { return this->_M_impl._M_header._M_right; }
 460
 461       _Const_Base_ptr
 462       _M_rightmost() const
 463       { return this->_M_impl._M_header._M_right; }
 464
 465       _Link_type
 466       _M_begin()
 467       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 468
 469       _Const_Link_type
 470       _M_begin() const
 471       {
 472         return static_cast<_Const_Link_type>
 473           (this->_M_impl._M_header._M_parent);
 474       }
 475
 476       _Link_type
 477       _M_end()
 478       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 479
 480       _Const_Link_type
 481       _M_end() const
 482       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 483
 484       static const_reference
 485       _S_value(_Const_Link_type __x)
 486       { return __x->_M_value_field; }
 487
 488       static const _Key&
 489       _S_key(_Const_Link_type __x)
 490       { return _KeyOfValue()(_S_value(__x)); }
 491
 492       static _Link_type
 493       _S_left(_Base_ptr __x)
 494       { return static_cast<_Link_type>(__x->_M_left); }
 495
 496       static _Const_Link_type
 497       _S_left(_Const_Base_ptr __x)
 498       { return static_cast<_Const_Link_type>(__x->_M_left); }
 499
 500       static _Link_type
 501       _S_right(_Base_ptr __x)
 502       { return static_cast<_Link_type>(__x->_M_right); }
 503
 504       static _Const_Link_type
 505       _S_right(_Const_Base_ptr __x)
 506       { return static_cast<_Const_Link_type>(__x->_M_right); }
 507
 508       static const_reference
 509       _S_value(_Const_Base_ptr __x)
 510       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 511
 512       static const _Key&
 513       _S_key(_Const_Base_ptr __x)
 514       { return _KeyOfValue()(_S_value(__x)); }
 515
 516       static _Base_ptr
 517       _S_minimum(_Base_ptr __x)
 518       { return _Rb_tree_node_base::_S_minimum(__x); }
 519
 520       static _Const_Base_ptr
 521       _S_minimum(_Const_Base_ptr __x)
 522       { return _Rb_tree_node_base::_S_minimum(__x); }
 523
 524       static _Base_ptr
 525       _S_maximum(_Base_ptr __x)
 526       { return _Rb_tree_node_base::_S_maximum(__x); }
 527
 528       static _Const_Base_ptr
 529       _S_maximum(_Const_Base_ptr __x)
 530       { return _Rb_tree_node_base::_S_maximum(__x); }
 531
 532     public:
 533       typedef _Rb_tree_iterator<value_type>       iterator;
 534       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 535
 536       typedef std::reverse_iterator<iterator>       reverse_iterator;
 537       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 538
 539     private:
 540       iterator
 541       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
 542                  const value_type& __v);
 543
 544       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 545       // 233. Insertion hints in associative containers.
 546       iterator
 547       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 548
 549       iterator
 550       _M_insert_equal_lower(const value_type& __x);
 551
 552       _Link_type
 553       _M_copy(_Const_Link_type __x, _Link_type __p);
 554
 555       void
 556       _M_erase(_Link_type __x);
 557
 558       iterator
 559       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
 560                      const _Key& __k) const;
 561
 562       iterator
 563       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
 564                      const _Key& __k) const;
 565
 566       pair<iterator, iterator>
 567       _M_equal_range(const _Key& __k) const;
 568
 569     public:
 570       // allocation/deallocation
 571       _Rb_tree()
 572       { }
 573
 574       _Rb_tree(const _Compare& __comp)
 575       : _M_impl(allocator_type(), __comp)
 576       { }
 577
 578       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 579       : _M_impl(__a, __comp)
 580       { }
 581
 582       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 583       : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare)
 584       {
 585         if (__x._M_root() != 0)
 586           {
 587             _M_root() = _M_copy(__x._M_begin(), _M_end());
 588             _M_leftmost() = _S_minimum(_M_root());
 589             _M_rightmost() = _S_maximum(_M_root());
 590             _M_impl._M_node_count = __x._M_impl._M_node_count;
 591           }
 592       }
 593
 594       ~_Rb_tree()
 595       { _M_erase(_M_begin()); }
 596
 597       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 598       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
 599
 600       // Accessors.
 601       _Compare
 602       key_comp() const
 603       { return _M_impl._M_key_compare; }
 604
 605       iterator
 606       begin()
 607       {
 608         return iterator(static_cast<_Link_type>
 609                         (this->_M_impl._M_header._M_left));
 610       }
 611
 612       const_iterator
 613       begin() const
 614       {
 615         return const_iterator(static_cast<_Const_Link_type>
 616                               (this->_M_impl._M_header._M_left));
 617       }
 618
 619       iterator
 620       end()
 621       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 622
 623       const_iterator
 624       end() const
 625       {
 626         return const_iterator(static_cast<_Const_Link_type>
 627                               (&this->_M_impl._M_header));
 628       }
 629
 630       reverse_iterator
 631       rbegin()
 632       { return reverse_iterator(end()); }
 633
 634       const_reverse_iterator
 635       rbegin() const
 636       { return const_reverse_iterator(end()); }
 637
 638       reverse_iterator
 639       rend()
 640       { return reverse_iterator(begin()); }
 641
 642       const_reverse_iterator
 643       rend() const
 644       { return const_reverse_iterator(begin()); }
 645
 646       bool
 647       empty() const
 648       { return _M_impl._M_node_count == 0; }
 649
 650       size_type
 651       size() const
 652       { return _M_impl._M_node_count; }
 653
 654       size_type
 655       max_size() const
 656       { return get_allocator().max_size(); }
 657
 658       void
 659       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
 660
 661       // Insert/erase.
 662       pair<iterator, bool>
 663       _M_insert_unique(const value_type& __x);
 664
 665       iterator
 666       _M_insert_equal(const value_type& __x);
 667
 668       iterator
 669       _M_insert_unique_(const_iterator __position, const value_type& __x);
 670
 671       iterator
 672       _M_insert_equal_(const_iterator __position, const value_type& __x);
 673
 674       template<typename _InputIterator>
 675         void
 676         _M_insert_unique(_InputIterator __first, _InputIterator __last);
 677
 678       template<typename _InputIterator>
 679         void
 680         _M_insert_equal(_InputIterator __first, _InputIterator __last);
 681
 682       void
 683       erase(iterator __position);
 684
 685       void
 686       erase(const_iterator __position);
 687
 688       size_type
 689       erase(const key_type& __x);
 690
 691       void
 692       erase(iterator __first, iterator __last);
 693
 694       void
 695       erase(const_iterator __first, const_iterator __last);
 696
 697       void
 698       erase(const key_type* __first, const key_type* __last);
 699
 700       void
 701       clear()
 702       {
 703         _M_erase(_M_begin());
 704         _M_leftmost() = _M_end();
 705         _M_root() = 0;
 706         _M_rightmost() = _M_end();
 707         _M_impl._M_node_count = 0;
 708       }
 709
 710       // Set operations.
 711       iterator
 712       find(const key_type& __k);
 713
 714       const_iterator
 715       find(const key_type& __k) const;
 716
 717       size_type
 718       count(const key_type& __k) const;
 719
 720       iterator
 721       lower_bound(const key_type& __k)
 722       { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
 723
 724       const_iterator
 725       lower_bound(const key_type& __k) const
 726       { return const_iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
 727
 728       iterator
 729       upper_bound(const key_type& __k)
 730       { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
 731
 732       const_iterator
 733       upper_bound(const key_type& __k) const
 734       { return const_iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
 735
 736       pair<iterator, iterator>
 737       equal_range(const key_type& __k)
 738       { return pair<iterator, iterator>(_M_equal_range(__k)); }
 739
 740       pair<const_iterator, const_iterator>
 741       equal_range(const key_type& __k) const
 742       { return pair<const_iterator, const_iterator>(_M_equal_range(__k)); }
 743
 744       // Debugging.
 745       bool
 746       __rb_verify() const;
 747     };
 748
 749   template<typename _Key, typename _Val, typename _KeyOfValue,
 750            typename _Compare, typename _Alloc>
 751     inline bool
 752     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 753                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 754     {
 755       return __x.size() == __y.size()
 756              && std::equal(__x.begin(), __x.end(), __y.begin());
 757     }
 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     {
 765       return std::lexicographical_compare(__x.begin(), __x.end(),
 766                                           __y.begin(), __y.end());
 767     }
 768
 769   template<typename _Key, typename _Val, typename _KeyOfValue,
 770            typename _Compare, typename _Alloc>
 771     inline bool
 772     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 773                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 774     { return !(__x == __y); }
 775
 776   template<typename _Key, typename _Val, typename _KeyOfValue,
 777            typename _Compare, typename _Alloc>
 778     inline bool
 779     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 780               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 781     { return __y < __x; }
 782
 783   template<typename _Key, typename _Val, typename _KeyOfValue,
 784            typename _Compare, typename _Alloc>
 785     inline bool
 786     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 787                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 788     { return !(__y < __x); }
 789
 790   template<typename _Key, typename _Val, typename _KeyOfValue,
 791            typename _Compare, typename _Alloc>
 792     inline bool
 793     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 794                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 795     { return !(__x < __y); }
 796
 797   template<typename _Key, typename _Val, typename _KeyOfValue,
 798            typename _Compare, typename _Alloc>
 799     inline void
 800     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 801          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 802     { __x.swap(__y); }
 803
 804   template<typename _Key, typename _Val, typename _KeyOfValue,
 805            typename _Compare, typename _Alloc>
 806     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 807     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 808     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 809     {
 810       if (this != &__x)
 811         {
 812           // Note that _Key may be a constant type.
 813           clear();
 814           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 815           if (__x._M_root() != 0)
 816             {
 817               _M_root() = _M_copy(__x._M_begin(), _M_end());
 818               _M_leftmost() = _S_minimum(_M_root());
 819               _M_rightmost() = _S_maximum(_M_root());
 820               _M_impl._M_node_count = __x._M_impl._M_node_count;
 821             }
 822         }
 823       return *this;
 824     }
 825
 826   template<typename _Key, typename _Val, typename _KeyOfValue,
 827            typename _Compare, typename _Alloc>
 828     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 829     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 830     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
 831     {
 832       bool __insert_left = (__x != 0 || __p == _M_end()
 833                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 834                                                       _S_key(__p)));
 835
 836       _Link_type __z = _M_create_node(__v);
 837
 838       _Rb_tree_insert_and_rebalance(__insert_left, __z,
 839                                     const_cast<_Base_ptr>(__p),
 840                                     this->_M_impl._M_header);
 841       ++_M_impl._M_node_count;
 842       return iterator(__z);
 843     }
 844
 845   template<typename _Key, typename _Val, typename _KeyOfValue,
 846            typename _Compare, typename _Alloc>
 847     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 848     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 849     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 850     {
 851       bool __insert_left = (__x != 0 || __p == _M_end()
 852                             || !_M_impl._M_key_compare(_S_key(__p),
 853                                                        _KeyOfValue()(__v)));
 854
 855       _Link_type __z = _M_create_node(__v);
 856
 857       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 858                                     this->_M_impl._M_header);
 859       ++_M_impl._M_node_count;
 860       return iterator(__z);
 861     }
 862
 863   template<typename _Key, typename _Val, typename _KeyOfValue,
 864            typename _Compare, typename _Alloc>
 865     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 866     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 867     _M_insert_equal_lower(const _Val& __v)
 868     {
 869       _Link_type __x = _M_begin();
 870       _Link_type __y = _M_end();
 871       while (__x != 0)
 872         {
 873           __y = __x;
 874           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
 875                 _S_left(__x) : _S_right(__x);
 876         }
 877       return _M_insert_lower(__x, __y, __v);
 878     }
 879
 880   template<typename _Key, typename _Val, typename _KoV,
 881            typename _Compare, typename _Alloc>
 882     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
 883     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
 884     _M_copy(_Const_Link_type __x, _Link_type __p)
 885     {
 886       // Structural copy.  __x and __p must be non-null.
 887       _Link_type __top = _M_clone_node(__x);
 888       __top->_M_parent = __p;
 889
 890       try
 891         {
 892           if (__x->_M_right)
 893             __top->_M_right = _M_copy(_S_right(__x), __top);
 894           __p = __top;
 895           __x = _S_left(__x);
 896
 897           while (__x != 0)
 898             {
 899               _Link_type __y = _M_clone_node(__x);
 900               __p->_M_left = __y;
 901               __y->_M_parent = __p;
 902               if (__x->_M_right)
 903                 __y->_M_right = _M_copy(_S_right(__x), __y);
 904               __p = __y;
 905               __x = _S_left(__x);
 906             }
 907         }
 908       catch(...)
 909         {
 910           _M_erase(__top);
 911           __throw_exception_again;
 912         }
 913       return __top;
 914     }
 915
 916   template<typename _Key, typename _Val, typename _KeyOfValue,
 917            typename _Compare, typename _Alloc>
 918     void
 919     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 920     _M_erase(_Link_type __x)
 921     {
 922       // Erase without rebalancing.
 923       while (__x != 0)
 924         {
 925           _M_erase(_S_right(__x));
 926           _Link_type __y = _S_left(__x);
 927           _M_destroy_node(__x);
 928           __x = __y;
 929         }
 930     }
 931
 932   template<typename _Key, typename _Val, typename _KeyOfValue,
 933            typename _Compare, typename _Alloc>
 934     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 935     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 936     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
 937                    const _Key& __k) const
 938     {
 939       while (__x != 0)
 940         if (!_M_impl._M_key_compare(_S_key(__x), __k))
 941           __y = __x, __x = _S_left(__x);
 942         else
 943           __x = _S_right(__x);
 944       return iterator(const_cast<_Link_type>(__y));
 945     }
 946
 947   template<typename _Key, typename _Val, typename _KeyOfValue,
 948            typename _Compare, typename _Alloc>
 949     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 950     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 951     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
 952                    const _Key& __k) const
 953     {
 954       while (__x != 0)
 955         if (_M_impl._M_key_compare(__k, _S_key(__x)))
 956           __y = __x, __x = _S_left(__x);
 957         else
 958           __x = _S_right(__x);
 959       return iterator(const_cast<_Link_type>(__y));
 960     }
 961
 962   template<typename _Key, typename _Val, typename _KeyOfValue,
 963            typename _Compare, typename _Alloc>
 964     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 965                            _Compare, _Alloc>::iterator,
 966          typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
 967     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 968     _M_equal_range(const _Key& __k) const
 969     {
 970       _Const_Link_type __x = _M_begin();
 971       _Const_Link_type __y = _M_end();
 972       while (__x != 0)
 973         {
 974           if (_M_impl._M_key_compare(_S_key(__x), __k))
 975             __x = _S_right(__x);
 976           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
 977             __y = __x, __x = _S_left(__x);
 978           else
 979             {
 980               _Const_Link_type __xu(__x), __yu(__y);
 981               __y = __x, __x = _S_left(__x);
 982               __xu = _S_right(__xu);
 983               return pair<iterator, iterator>(_M_lower_bound(__x, __y, __k),
 984                                               _M_upper_bound(__xu, __yu, __k));
 985             }
 986         }
 987       return pair<iterator, iterator>(iterator(const_cast<_Link_type>(__y)),
 988                                       iterator(const_cast<_Link_type>(__y)));
 989     }
 990
 991   template<typename _Key, typename _Val, typename _KeyOfValue,
 992            typename _Compare, typename _Alloc>
 993     void
 994     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 995     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
 996     {
 997       if (_M_root() == 0)
 998         {
 999           if (__t._M_root() != 0)
1000             {
1001               _M_root() = __t._M_root();
1002               _M_leftmost() = __t._M_leftmost();
1003               _M_rightmost() = __t._M_rightmost();
1004               _M_root()->_M_parent = _M_end();
1005
1006               __t._M_root() = 0;
1007               __t._M_leftmost() = __t._M_end();
1008               __t._M_rightmost() = __t._M_end();
1009             }
1010         }
1011       else if (__t._M_root() == 0)
1012         {
1013           __t._M_root() = _M_root();
1014           __t._M_leftmost() = _M_leftmost();
1015           __t._M_rightmost() = _M_rightmost();
1016           __t._M_root()->_M_parent = __t._M_end();
1017
1018           _M_root() = 0;
1019           _M_leftmost() = _M_end();
1020           _M_rightmost() = _M_end();
1021         }
1022       else
1023         {
1024           std::swap(_M_root(),__t._M_root());
1025           std::swap(_M_leftmost(),__t._M_leftmost());
1026           std::swap(_M_rightmost(),__t._M_rightmost());
1027
1028           _M_root()->_M_parent = _M_end();
1029           __t._M_root()->_M_parent = __t._M_end();
1030         }
1031       // No need to swap header's color as it does not change.
1032       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1033       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1034
1035       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1036       // 431. Swapping containers with unequal allocators.
1037       std::__alloc_swap<_Node_allocator>::
1038         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1039     }
1040
1041   template<typename _Key, typename _Val, typename _KeyOfValue,
1042            typename _Compare, typename _Alloc>
1043     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1044                            _Compare, _Alloc>::iterator, bool>
1045     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1046     _M_insert_unique(const _Val& __v)
1047     {
1048       _Link_type __x = _M_begin();
1049       _Link_type __y = _M_end();
1050       bool __comp = true;
1051       while (__x != 0)
1052         {
1053           __y = __x;
1054           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1055           __x = __comp ? _S_left(__x) : _S_right(__x);
1056         }
1057       iterator __j = iterator(__y);
1058       if (__comp)
1059         if (__j == begin())
1060           return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
1061         else
1062           --__j;
1063       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1064         return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
1065       return pair<iterator, bool>(__j, false);
1066     }
1067
1068   template<typename _Key, typename _Val, typename _KeyOfValue,
1069            typename _Compare, typename _Alloc>
1070     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1071     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1072     _M_insert_equal(const _Val& __v)
1073     {
1074       _Link_type __x = _M_begin();
1075       _Link_type __y = _M_end();
1076       while (__x != 0)
1077         {
1078           __y = __x;
1079           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1080                 _S_left(__x) : _S_right(__x);
1081         }
1082       return _M_insert_(__x, __y, __v);
1083     }
1084
1085   template<typename _Key, typename _Val, typename _KeyOfValue,
1086            typename _Compare, typename _Alloc>
1087     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1088     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1089     _M_insert_unique_(const_iterator __position, const _Val& __v)
1090     {
1091       // end()
1092       if (__position._M_node == _M_end())
1093         {
1094           if (size() > 0
1095               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1096                                         _KeyOfValue()(__v)))
1097             return _M_insert_(0, _M_rightmost(), __v);
1098           else
1099             return _M_insert_unique(__v).first;
1100         }
1101       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1102                                       _S_key(__position._M_node)))
1103         {
1104           // First, try before...
1105           const_iterator __before = __position;
1106           if (__position._M_node == _M_leftmost()) // begin()
1107             return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1108           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1109                                           _KeyOfValue()(__v)))
1110             {
1111               if (_S_right(__before._M_node) == 0)
1112                 return _M_insert_(0, __before._M_node, __v);
1113               else
1114                 return _M_insert_(__position._M_node,
1115                                   __position._M_node, __v);
1116             }
1117           else
1118             return _M_insert_unique(__v).first;
1119         }
1120       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1121                                       _KeyOfValue()(__v)))
1122         {
1123           // ... then try after.
1124           const_iterator __after = __position;
1125           if (__position._M_node == _M_rightmost())
1126             return _M_insert_(0, _M_rightmost(), __v);
1127           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1128                                           _S_key((++__after)._M_node)))
1129             {
1130               if (_S_right(__position._M_node) == 0)
1131                 return _M_insert_(0, __position._M_node, __v);
1132               else
1133                 return _M_insert_(__after._M_node, __after._M_node, __v);
1134             }
1135           else
1136             return _M_insert_unique(__v).first;
1137         }
1138       else
1139         // Equivalent keys.
1140         return iterator(static_cast<_Link_type>
1141                         (const_cast<_Base_ptr>(__position._M_node)));
1142     }
1143
1144   template<typename _Key, typename _Val, typename _KeyOfValue,
1145            typename _Compare, typename _Alloc>
1146     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1147     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1148     _M_insert_equal_(const_iterator __position, const _Val& __v)
1149     {
1150       // end()
1151       if (__position._M_node == _M_end())
1152         {
1153           if (size() > 0
1154               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1155                                          _S_key(_M_rightmost())))
1156             return _M_insert_(0, _M_rightmost(), __v);
1157           else
1158             return _M_insert_equal(__v);
1159         }
1160       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1161                                        _KeyOfValue()(__v)))
1162         {
1163           // First, try before...
1164           const_iterator __before = __position;
1165           if (__position._M_node == _M_leftmost()) // begin()
1166             return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1167           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1168                                            _S_key((--__before)._M_node)))
1169             {
1170               if (_S_right(__before._M_node) == 0)
1171                 return _M_insert_(0, __before._M_node, __v);
1172               else
1173                 return _M_insert_(__position._M_node,
1174                                   __position._M_node, __v);
1175             }
1176           else
1177             return _M_insert_equal(__v);
1178         }
1179       else
1180         {
1181           // ... then try after.
1182           const_iterator __after = __position;
1183           if (__position._M_node == _M_rightmost())
1184             return _M_insert_(0, _M_rightmost(), __v);
1185           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1186                                            _KeyOfValue()(__v)))
1187             {
1188               if (_S_right(__position._M_node) == 0)
1189                 return _M_insert_(0, __position._M_node, __v);
1190               else
1191                 return _M_insert_(__after._M_node, __after._M_node, __v);
1192             }
1193           else
1194             return _M_insert_equal_lower(__v);
1195         }
1196     }
1197
1198   template<typename _Key, typename _Val, typename _KoV,
1199            typename _Cmp, typename _Alloc>
1200     template<class _II>
1201       void
1202       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1203       _M_insert_unique(_II __first, _II __last)
1204       {
1205         for (; __first != __last; ++__first)
1206           _M_insert_unique_(end(), *__first);
1207       }
1208
1209   template<typename _Key, typename _Val, typename _KoV,
1210            typename _Cmp, typename _Alloc>
1211     template<class _II>
1212       void
1213       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1214       _M_insert_equal(_II __first, _II __last)
1215       {
1216         for (; __first != __last; ++__first)
1217           _M_insert_equal_(end(), *__first);
1218       }
1219
1220   template<typename _Key, typename _Val, typename _KeyOfValue,
1221            typename _Compare, typename _Alloc>
1222     inline void
1223     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1224     erase(iterator __position)
1225     {
1226       _Link_type __y =
1227         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1228                                 (__position._M_node,
1229                                  this->_M_impl._M_header));
1230       _M_destroy_node(__y);
1231       --_M_impl._M_node_count;
1232     }
1233
1234   template<typename _Key, typename _Val, typename _KeyOfValue,
1235            typename _Compare, typename _Alloc>
1236     inline void
1237     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1238     erase(const_iterator __position)
1239     {
1240       _Link_type __y =
1241         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1242                                 (const_cast<_Base_ptr>(__position._M_node),
1243                                  this->_M_impl._M_header));
1244       _M_destroy_node(__y);
1245       --_M_impl._M_node_count;
1246     }
1247
1248   template<typename _Key, typename _Val, typename _KeyOfValue,
1249            typename _Compare, typename _Alloc>
1250     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1251     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1252     erase(const _Key& __x)
1253     {
1254       pair<iterator, iterator> __p = equal_range(__x);
1255       const size_type __old_size = size();
1256       erase(__p.first, __p.second);
1257       return __old_size - size();
1258     }
1259
1260   template<typename _Key, typename _Val, typename _KeyOfValue,
1261            typename _Compare, typename _Alloc>
1262     void
1263     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1264     erase(iterator __first, iterator __last)
1265     {
1266       if (__first == begin() && __last == end())
1267         clear();
1268       else
1269         while (__first != __last)
1270           erase(__first++);
1271     }
1272
1273   template<typename _Key, typename _Val, typename _KeyOfValue,
1274            typename _Compare, typename _Alloc>
1275     void
1276     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1277     erase(const_iterator __first, const_iterator __last)
1278     {
1279       if (__first == begin() && __last == end())
1280         clear();
1281       else
1282         while (__first != __last)
1283           erase(__first++);
1284     }
1285
1286   template<typename _Key, typename _Val, typename _KeyOfValue,
1287            typename _Compare, typename _Alloc>
1288     void
1289     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1290     erase(const _Key* __first, const _Key* __last)
1291     {
1292       while (__first != __last)
1293         erase(*__first++);
1294     }
1295
1296   template<typename _Key, typename _Val, typename _KeyOfValue,
1297            typename _Compare, typename _Alloc>
1298     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1299     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1300     find(const _Key& __k)
1301     {
1302       iterator __j = iterator(_M_lower_bound(_M_begin(), _M_end(), __k));
1303       return (__j == end()
1304               || _M_impl._M_key_compare(__k,
1305                                         _S_key(__j._M_node))) ? end() : __j;
1306     }
1307
1308   template<typename _Key, typename _Val, typename _KeyOfValue,
1309            typename _Compare, typename _Alloc>
1310     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1311     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1312     find(const _Key& __k) const
1313     {
1314       const_iterator __j = const_iterator(_M_lower_bound(_M_begin(),
1315                                                          _M_end(), __k));
1316       return (__j == end()
1317               || _M_impl._M_key_compare(__k,
1318                                         _S_key(__j._M_node))) ? end() : __j;
1319     }
1320
1321   template<typename _Key, typename _Val, typename _KeyOfValue,
1322            typename _Compare, typename _Alloc>
1323     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1324     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1325     count(const _Key& __k) const
1326     {
1327       pair<const_iterator, const_iterator> __p = equal_range(__k);
1328       const size_type __n = std::distance(__p.first, __p.second);
1329       return __n;
1330     }
1331
1332   unsigned int
1333   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1334                        const _Rb_tree_node_base* __root);
1335
1336   template<typename _Key, typename _Val, typename _KeyOfValue,
1337            typename _Compare, typename _Alloc>
1338     bool
1339     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1340     {
1341       if (_M_impl._M_node_count == 0 || begin() == end())
1342         return _M_impl._M_node_count == 0 && begin() == end()
1343                && this->_M_impl._M_header._M_left == _M_end()
1344                && this->_M_impl._M_header._M_right == _M_end();
1345
1346       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1347       for (const_iterator __it = begin(); __it != end(); ++__it)
1348         {
1349           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1350           _Const_Link_type __L = _S_left(__x);
1351           _Const_Link_type __R = _S_right(__x);
1352
1353           if (__x->_M_color == _S_red)
1354             if ((__L && __L->_M_color == _S_red)
1355                 || (__R && __R->_M_color == _S_red))
1356               return false;
1357
1358           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1359             return false;
1360           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1361             return false;
1362
1363           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1364             return false;
1365         }
1366
1367       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1368         return false;
1369       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1370         return false;
1371       return true;
1372     }
1373
1374 _GLIBCXX_END_NAMESPACE
1375
1376 #endif