libstdc++-v3/include/bits/stl_tree.h

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