l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/bits/stl_tree.h

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