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

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