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