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