l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/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()
 356       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
 357
 358       const _Node_allocator&
 359       _M_get_Node_allocator() const
 360       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 361
 362       allocator_type
 363       get_allocator() const
 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         private:
 454           void
 455           _M_initialize()
 456           {
 457             this->_M_header._M_color = _S_red;
 458             this->_M_header._M_parent = 0;
 459             this->_M_header._M_left = &this->_M_header;
 460             this->_M_header._M_right = &this->_M_header;
 461           }
 462         };
 463
 464       _Rb_tree_impl<_Compare> _M_impl;
 465
 466     protected:
 467       _Base_ptr&
 468       _M_root()
 469       { return this->_M_impl._M_header._M_parent; }
 470
 471       _Const_Base_ptr
 472       _M_root() const
 473       { return this->_M_impl._M_header._M_parent; }
 474
 475       _Base_ptr&
 476       _M_leftmost()
 477       { return this->_M_impl._M_header._M_left; }
 478
 479       _Const_Base_ptr
 480       _M_leftmost() const
 481       { return this->_M_impl._M_header._M_left; }
 482
 483       _Base_ptr&
 484       _M_rightmost()
 485       { return this->_M_impl._M_header._M_right; }
 486
 487       _Const_Base_ptr
 488       _M_rightmost() const
 489       { return this->_M_impl._M_header._M_right; }
 490
 491       _Link_type
 492       _M_begin()
 493       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 494
 495       _Const_Link_type
 496       _M_begin() const
 497       {
 498         return static_cast<_Const_Link_type>
 499           (this->_M_impl._M_header._M_parent);
 500       }
 501
 502       _Link_type
 503       _M_end()
 504       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 505
 506       _Const_Link_type
 507       _M_end() const
 508       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 509
 510       static const_reference
 511       _S_value(_Const_Link_type __x)
 512       { return __x->_M_value_field; }
 513
 514       static const _Key&
 515       _S_key(_Const_Link_type __x)
 516       { return _KeyOfValue()(_S_value(__x)); }
 517
 518       static _Link_type
 519       _S_left(_Base_ptr __x)
 520       { return static_cast<_Link_type>(__x->_M_left); }
 521
 522       static _Const_Link_type
 523       _S_left(_Const_Base_ptr __x)
 524       { return static_cast<_Const_Link_type>(__x->_M_left); }
 525
 526       static _Link_type
 527       _S_right(_Base_ptr __x)
 528       { return static_cast<_Link_type>(__x->_M_right); }
 529
 530       static _Const_Link_type
 531       _S_right(_Const_Base_ptr __x)
 532       { return static_cast<_Const_Link_type>(__x->_M_right); }
 533
 534       static const_reference
 535       _S_value(_Const_Base_ptr __x)
 536       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 537
 538       static const _Key&
 539       _S_key(_Const_Base_ptr __x)
 540       { return _KeyOfValue()(_S_value(__x)); }
 541
 542       static _Base_ptr
 543       _S_minimum(_Base_ptr __x)
 544       { return _Rb_tree_node_base::_S_minimum(__x); }
 545
 546       static _Const_Base_ptr
 547       _S_minimum(_Const_Base_ptr __x)
 548       { return _Rb_tree_node_base::_S_minimum(__x); }
 549
 550       static _Base_ptr
 551       _S_maximum(_Base_ptr __x)
 552       { return _Rb_tree_node_base::_S_maximum(__x); }
 553
 554       static _Const_Base_ptr
 555       _S_maximum(_Const_Base_ptr __x)
 556       { return _Rb_tree_node_base::_S_maximum(__x); }
 557
 558     public:
 559       typedef _Rb_tree_iterator<value_type>       iterator;
 560       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 561
 562       typedef std::reverse_iterator<iterator>       reverse_iterator;
 563       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 564
 565     private:
 566 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 567       template<typename _Arg>
 568         iterator
 569         _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
 570
 571       template<typename _Arg>
 572         iterator
 573         _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
 574
 575       template<typename _Arg>
 576         iterator
 577         _M_insert_equal_lower(_Arg&& __x);
 578 #else
 579       iterator
 580       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
 581                  const value_type& __v);
 582
 583       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 584       // 233. Insertion hints in associative containers.
 585       iterator
 586       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 587
 588       iterator
 589       _M_insert_equal_lower(const value_type& __x);
 590 #endif
 591
 592       _Link_type
 593       _M_copy(_Const_Link_type __x, _Link_type __p);
 594
 595       void
 596       _M_erase(_Link_type __x);
 597
 598       iterator
 599       _M_lower_bound(_Link_type __x, _Link_type __y,
 600                      const _Key& __k);
 601
 602       const_iterator
 603       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
 604                      const _Key& __k) const;
 605
 606       iterator
 607       _M_upper_bound(_Link_type __x, _Link_type __y,
 608                      const _Key& __k);
 609
 610       const_iterator
 611       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
 612                      const _Key& __k) const;
 613
 614     public:
 615       // allocation/deallocation
 616       _Rb_tree() { }
 617
 618       _Rb_tree(const _Compare& __comp,
 619                const allocator_type& __a = allocator_type())
 620       : _M_impl(__comp, __a) { }
 621
 622       _Rb_tree(const _Rb_tree& __x)
 623       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
 624       {
 625         if (__x._M_root() != 0)
 626           {
 627             _M_root() = _M_copy(__x._M_begin(), _M_end());
 628             _M_leftmost() = _S_minimum(_M_root());
 629             _M_rightmost() = _S_maximum(_M_root());
 630             _M_impl._M_node_count = __x._M_impl._M_node_count;
 631           }
 632       }
 633
 634 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 635       _Rb_tree(_Rb_tree&& __x);
 636 #endif
 637
 638       ~_Rb_tree()
 639       { _M_erase(_M_begin()); }
 640
 641       _Rb_tree&
 642       operator=(const _Rb_tree& __x);
 643
 644       // Accessors.
 645       _Compare
 646       key_comp() const
 647       { return _M_impl._M_key_compare; }
 648
 649       iterator
 650       begin()
 651       {
 652         return iterator(static_cast<_Link_type>
 653                         (this->_M_impl._M_header._M_left));
 654       }
 655
 656       const_iterator
 657       begin() const
 658       {
 659         return const_iterator(static_cast<_Const_Link_type>
 660                               (this->_M_impl._M_header._M_left));
 661       }
 662
 663       iterator
 664       end()
 665       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 666
 667       const_iterator
 668       end() const
 669       {
 670         return const_iterator(static_cast<_Const_Link_type>
 671                               (&this->_M_impl._M_header));
 672       }
 673
 674       reverse_iterator
 675       rbegin()
 676       { return reverse_iterator(end()); }
 677
 678       const_reverse_iterator
 679       rbegin() const
 680       { return const_reverse_iterator(end()); }
 681
 682       reverse_iterator
 683       rend()
 684       { return reverse_iterator(begin()); }
 685
 686       const_reverse_iterator
 687       rend() const
 688       { return const_reverse_iterator(begin()); }
 689
 690       bool
 691       empty() const
 692       { return _M_impl._M_node_count == 0; }
 693
 694       size_type
 695       size() const
 696       { return _M_impl._M_node_count; }
 697
 698       size_type
 699       max_size() const
 700       { return _M_get_Node_allocator().max_size(); }
 701
 702       void
 703       swap(_Rb_tree& __t);
 704
 705       // Insert/erase.
 706 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 707       template<typename _Arg>
 708         pair<iterator, bool>
 709         _M_insert_unique(_Arg&& __x);
 710
 711       template<typename _Arg>
 712         iterator
 713         _M_insert_equal(_Arg&& __x);
 714
 715       template<typename _Arg>
 716         iterator
 717         _M_insert_unique_(const_iterator __position, _Arg&& __x);
 718
 719       template<typename _Arg>
 720         iterator
 721         _M_insert_equal_(const_iterator __position, _Arg&& __x);
 722 #else
 723       pair<iterator, bool>
 724       _M_insert_unique(const value_type& __x);
 725
 726       iterator
 727       _M_insert_equal(const value_type& __x);
 728
 729       iterator
 730       _M_insert_unique_(const_iterator __position, const value_type& __x);
 731
 732       iterator
 733       _M_insert_equal_(const_iterator __position, const value_type& __x);
 734 #endif
 735
 736       template<typename _InputIterator>
 737         void
 738         _M_insert_unique(_InputIterator __first, _InputIterator __last);
 739
 740       template<typename _InputIterator>
 741         void
 742         _M_insert_equal(_InputIterator __first, _InputIterator __last);
 743
 744     private:
 745       void
 746       _M_erase_aux(const_iterator __position);
 747
 748       void
 749       _M_erase_aux(const_iterator __first, const_iterator __last);
 750
 751     public:
 752 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 753       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 754       // DR 130. Associative erase should return an iterator.
 755       iterator
 756       erase(const_iterator __position)
 757       {
 758         const_iterator __result = __position;
 759         ++__result;
 760         _M_erase_aux(__position);
 761         return __result._M_const_cast();
 762       }
 763 #else
 764       void
 765       erase(iterator __position)
 766       { _M_erase_aux(__position); }
 767
 768       void
 769       erase(const_iterator __position)
 770       { _M_erase_aux(__position); }
 771 #endif
 772       size_type
 773       erase(const key_type& __x);
 774
 775 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 776       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 777       // DR 130. Associative erase should return an iterator.
 778       iterator
 779       erase(const_iterator __first, const_iterator __last)
 780       {
 781         _M_erase_aux(__first, __last);
 782         return __last._M_const_cast();
 783       }
 784 #else
 785       void
 786       erase(iterator __first, iterator __last)
 787       { _M_erase_aux(__first, __last); }
 788
 789       void
 790       erase(const_iterator __first, const_iterator __last)
 791       { _M_erase_aux(__first, __last); }
 792 #endif
 793       void
 794       erase(const key_type* __first, const key_type* __last);
 795
 796       void
 797       clear()
 798       {
 799         _M_erase(_M_begin());
 800         _M_leftmost() = _M_end();
 801         _M_root() = 0;
 802         _M_rightmost() = _M_end();
 803         _M_impl._M_node_count = 0;
 804       }
 805
 806       // Set operations.
 807       iterator
 808       find(const key_type& __k);
 809
 810       const_iterator
 811       find(const key_type& __k) const;
 812
 813       size_type
 814       count(const key_type& __k) const;
 815
 816       iterator
 817       lower_bound(const key_type& __k)
 818       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
 819
 820       const_iterator
 821       lower_bound(const key_type& __k) const
 822       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
 823
 824       iterator
 825       upper_bound(const key_type& __k)
 826       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
 827
 828       const_iterator
 829       upper_bound(const key_type& __k) const
 830       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
 831
 832       pair<iterator, iterator>
 833       equal_range(const key_type& __k);
 834
 835       pair<const_iterator, const_iterator>
 836       equal_range(const key_type& __k) const;
 837
 838       // Debugging.
 839       bool
 840       __rb_verify() const;
 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 __x.size() == __y.size()
 850              && std::equal(__x.begin(), __x.end(), __y.begin());
 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     {
 859       return std::lexicographical_compare(__x.begin(), __x.end(),
 860                                           __y.begin(), __y.end());
 861     }
 862
 863   template<typename _Key, typename _Val, typename _KeyOfValue,
 864            typename _Compare, typename _Alloc>
 865     inline bool
 866     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 867                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 868     { return !(__x == __y); }
 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     { return __y < __x; }
 876
 877   template<typename _Key, typename _Val, typename _KeyOfValue,
 878            typename _Compare, typename _Alloc>
 879     inline bool
 880     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 881                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 882     { return !(__y < __x); }
 883
 884   template<typename _Key, typename _Val, typename _KeyOfValue,
 885            typename _Compare, typename _Alloc>
 886     inline bool
 887     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 888                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 889     { return !(__x < __y); }
 890
 891   template<typename _Key, typename _Val, typename _KeyOfValue,
 892            typename _Compare, typename _Alloc>
 893     inline void
 894     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 895          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 896     { __x.swap(__y); }
 897
 898 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 899   template<typename _Key, typename _Val, typename _KeyOfValue,
 900            typename _Compare, typename _Alloc>
 901     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 902     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
 903     : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
 904     {
 905       if (__x._M_root() != 0)
 906         {
 907           _M_root() = __x._M_root();
 908           _M_leftmost() = __x._M_leftmost();
 909           _M_rightmost() = __x._M_rightmost();
 910           _M_root()->_M_parent = _M_end();
 911
 912           __x._M_root() = 0;
 913           __x._M_leftmost() = __x._M_end();
 914           __x._M_rightmost() = __x._M_end();
 915
 916           this->_M_impl._M_node_count = __x._M_impl._M_node_count;
 917           __x._M_impl._M_node_count = 0;
 918         }
 919     }
 920 #endif
 921
 922   template<typename _Key, typename _Val, typename _KeyOfValue,
 923            typename _Compare, typename _Alloc>
 924     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 925     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 926     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 927     {
 928       if (this != &__x)
 929         {
 930           // Note that _Key may be a constant type.
 931           clear();
 932           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 933           if (__x._M_root() != 0)
 934             {
 935               _M_root() = _M_copy(__x._M_begin(), _M_end());
 936               _M_leftmost() = _S_minimum(_M_root());
 937               _M_rightmost() = _S_maximum(_M_root());
 938               _M_impl._M_node_count = __x._M_impl._M_node_count;
 939             }
 940         }
 941       return *this;
 942     }
 943
 944   template<typename _Key, typename _Val, typename _KeyOfValue,
 945            typename _Compare, typename _Alloc>
 946 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 947     template<typename _Arg>
 948 #endif
 949     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 950     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 951 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 952     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
 953 #else
 954     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
 955 #endif
 956     {
 957       bool __insert_left = (__x != 0 || __p == _M_end()
 958                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 959                                                       _S_key(__p)));
 960
 961       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
 962
 963       _Rb_tree_insert_and_rebalance(__insert_left, __z,
 964                                     const_cast<_Base_ptr>(__p),
 965                                     this->_M_impl._M_header);
 966       ++_M_impl._M_node_count;
 967       return iterator(__z);
 968     }
 969
 970   template<typename _Key, typename _Val, typename _KeyOfValue,
 971            typename _Compare, typename _Alloc>
 972 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 973     template<typename _Arg>
 974 #endif
 975     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 976     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 977 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 978     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
 979 #else
 980     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 981 #endif
 982     {
 983       bool __insert_left = (__x != 0 || __p == _M_end()
 984                             || !_M_impl._M_key_compare(_S_key(__p),
 985                                                        _KeyOfValue()(__v)));
 986
 987       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
 988
 989       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 990                                     this->_M_impl._M_header);
 991       ++_M_impl._M_node_count;
 992       return iterator(__z);
 993     }
 994
 995   template<typename _Key, typename _Val, typename _KeyOfValue,
 996            typename _Compare, typename _Alloc>
 997 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 998     template<typename _Arg>
 999 #endif
1000     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1001     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1002 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1003     _M_insert_equal_lower(_Arg&& __v)
1004 #else
1005     _M_insert_equal_lower(const _Val& __v)
1006 #endif
1007     {
1008       _Link_type __x = _M_begin();
1009       _Link_type __y = _M_end();
1010       while (__x != 0)
1011         {
1012           __y = __x;
1013           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1014                 _S_left(__x) : _S_right(__x);
1015         }
1016       return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1017     }
1018
1019   template<typename _Key, typename _Val, typename _KoV,
1020            typename _Compare, typename _Alloc>
1021     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1022     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1023     _M_copy(_Const_Link_type __x, _Link_type __p)
1024     {
1025       // Structural copy.  __x and __p must be non-null.
1026       _Link_type __top = _M_clone_node(__x);
1027       __top->_M_parent = __p;
1028
1029       __try
1030         {
1031           if (__x->_M_right)
1032             __top->_M_right = _M_copy(_S_right(__x), __top);
1033           __p = __top;
1034           __x = _S_left(__x);
1035
1036           while (__x != 0)
1037             {
1038               _Link_type __y = _M_clone_node(__x);
1039               __p->_M_left = __y;
1040               __y->_M_parent = __p;
1041               if (__x->_M_right)
1042                 __y->_M_right = _M_copy(_S_right(__x), __y);
1043               __p = __y;
1044               __x = _S_left(__x);
1045             }
1046         }
1047       __catch(...)
1048         {
1049           _M_erase(__top);
1050           __throw_exception_again;
1051         }
1052       return __top;
1053     }
1054
1055   template<typename _Key, typename _Val, typename _KeyOfValue,
1056            typename _Compare, typename _Alloc>
1057     void
1058     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1059     _M_erase(_Link_type __x)
1060     {
1061       // Erase without rebalancing.
1062       while (__x != 0)
1063         {
1064           _M_erase(_S_right(__x));
1065           _Link_type __y = _S_left(__x);
1066           _M_destroy_node(__x);
1067           __x = __y;
1068         }
1069     }
1070
1071   template<typename _Key, typename _Val, typename _KeyOfValue,
1072            typename _Compare, typename _Alloc>
1073     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1074                       _Compare, _Alloc>::iterator
1075     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1076     _M_lower_bound(_Link_type __x, _Link_type __y,
1077                    const _Key& __k)
1078     {
1079       while (__x != 0)
1080         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1081           __y = __x, __x = _S_left(__x);
1082         else
1083           __x = _S_right(__x);
1084       return iterator(__y);
1085     }
1086
1087   template<typename _Key, typename _Val, typename _KeyOfValue,
1088            typename _Compare, typename _Alloc>
1089     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1090                       _Compare, _Alloc>::const_iterator
1091     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1092     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1093                    const _Key& __k) const
1094     {
1095       while (__x != 0)
1096         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1097           __y = __x, __x = _S_left(__x);
1098         else
1099           __x = _S_right(__x);
1100       return const_iterator(__y);
1101     }
1102
1103   template<typename _Key, typename _Val, typename _KeyOfValue,
1104            typename _Compare, typename _Alloc>
1105     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1106                       _Compare, _Alloc>::iterator
1107     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1108     _M_upper_bound(_Link_type __x, _Link_type __y,
1109                    const _Key& __k)
1110     {
1111       while (__x != 0)
1112         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1113           __y = __x, __x = _S_left(__x);
1114         else
1115           __x = _S_right(__x);
1116       return iterator(__y);
1117     }
1118
1119   template<typename _Key, typename _Val, typename _KeyOfValue,
1120            typename _Compare, typename _Alloc>
1121     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1122                       _Compare, _Alloc>::const_iterator
1123     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1124     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1125                    const _Key& __k) const
1126     {
1127       while (__x != 0)
1128         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1129           __y = __x, __x = _S_left(__x);
1130         else
1131           __x = _S_right(__x);
1132       return const_iterator(__y);
1133     }
1134
1135   template<typename _Key, typename _Val, typename _KeyOfValue,
1136            typename _Compare, typename _Alloc>
1137     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1138                            _Compare, _Alloc>::iterator,
1139          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1140                            _Compare, _Alloc>::iterator>
1141     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1142     equal_range(const _Key& __k)
1143     {
1144       _Link_type __x = _M_begin();
1145       _Link_type __y = _M_end();
1146       while (__x != 0)
1147         {
1148           if (_M_impl._M_key_compare(_S_key(__x), __k))
1149             __x = _S_right(__x);
1150           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1151             __y = __x, __x = _S_left(__x);
1152           else
1153             {
1154               _Link_type __xu(__x), __yu(__y);
1155               __y = __x, __x = _S_left(__x);
1156               __xu = _S_right(__xu);
1157               return pair<iterator,
1158                           iterator>(_M_lower_bound(__x, __y, __k),
1159                                     _M_upper_bound(__xu, __yu, __k));
1160             }
1161         }
1162       return pair<iterator, iterator>(iterator(__y),
1163                                       iterator(__y));
1164     }
1165
1166   template<typename _Key, typename _Val, typename _KeyOfValue,
1167            typename _Compare, typename _Alloc>
1168     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1169                            _Compare, _Alloc>::const_iterator,
1170          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1171                            _Compare, _Alloc>::const_iterator>
1172     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1173     equal_range(const _Key& __k) const
1174     {
1175       _Const_Link_type __x = _M_begin();
1176       _Const_Link_type __y = _M_end();
1177       while (__x != 0)
1178         {
1179           if (_M_impl._M_key_compare(_S_key(__x), __k))
1180             __x = _S_right(__x);
1181           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1182             __y = __x, __x = _S_left(__x);
1183           else
1184             {
1185               _Const_Link_type __xu(__x), __yu(__y);
1186               __y = __x, __x = _S_left(__x);
1187               __xu = _S_right(__xu);
1188               return pair<const_iterator,
1189                           const_iterator>(_M_lower_bound(__x, __y, __k),
1190                                           _M_upper_bound(__xu, __yu, __k));
1191             }
1192         }
1193       return pair<const_iterator, const_iterator>(const_iterator(__y),
1194                                                   const_iterator(__y));
1195     }
1196
1197   template<typename _Key, typename _Val, typename _KeyOfValue,
1198            typename _Compare, typename _Alloc>
1199     void
1200     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1201     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1202     {
1203       if (_M_root() == 0)
1204         {
1205           if (__t._M_root() != 0)
1206             {
1207               _M_root() = __t._M_root();
1208               _M_leftmost() = __t._M_leftmost();
1209               _M_rightmost() = __t._M_rightmost();
1210               _M_root()->_M_parent = _M_end();
1211
1212               __t._M_root() = 0;
1213               __t._M_leftmost() = __t._M_end();
1214               __t._M_rightmost() = __t._M_end();
1215             }
1216         }
1217       else if (__t._M_root() == 0)
1218         {
1219           __t._M_root() = _M_root();
1220           __t._M_leftmost() = _M_leftmost();
1221           __t._M_rightmost() = _M_rightmost();
1222           __t._M_root()->_M_parent = __t._M_end();
1223
1224           _M_root() = 0;
1225           _M_leftmost() = _M_end();
1226           _M_rightmost() = _M_end();
1227         }
1228       else
1229         {
1230           std::swap(_M_root(),__t._M_root());
1231           std::swap(_M_leftmost(),__t._M_leftmost());
1232           std::swap(_M_rightmost(),__t._M_rightmost());
1233
1234           _M_root()->_M_parent = _M_end();
1235           __t._M_root()->_M_parent = __t._M_end();
1236         }
1237       // No need to swap header's color as it does not change.
1238       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1239       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1240
1241       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1242       // 431. Swapping containers with unequal allocators.
1243       std::__alloc_swap<_Node_allocator>::
1244         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1245     }
1246
1247   template<typename _Key, typename _Val, typename _KeyOfValue,
1248            typename _Compare, typename _Alloc>
1249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1250     template<typename _Arg>
1251 #endif
1252     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1253                            _Compare, _Alloc>::iterator, bool>
1254     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1255 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1256     _M_insert_unique(_Arg&& __v)
1257 #else
1258     _M_insert_unique(const _Val& __v)
1259 #endif
1260     {
1261       _Link_type __x = _M_begin();
1262       _Link_type __y = _M_end();
1263       bool __comp = true;
1264       while (__x != 0)
1265         {
1266           __y = __x;
1267           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1268           __x = __comp ? _S_left(__x) : _S_right(__x);
1269         }
1270       iterator __j = iterator(__y);
1271       if (__comp)
1272         {
1273           if (__j == begin())
1274             return pair<iterator, bool>
1275               (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1276           else
1277             --__j;
1278         }
1279       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1280         return pair<iterator, bool>
1281           (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1282       return pair<iterator, bool>(__j, false);
1283     }
1284
1285   template<typename _Key, typename _Val, typename _KeyOfValue,
1286            typename _Compare, typename _Alloc>
1287 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1288     template<typename _Arg>
1289 #endif
1290     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1291     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1292 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1293     _M_insert_equal(_Arg&& __v)
1294 #else
1295     _M_insert_equal(const _Val& __v)
1296 #endif
1297     {
1298       _Link_type __x = _M_begin();
1299       _Link_type __y = _M_end();
1300       while (__x != 0)
1301         {
1302           __y = __x;
1303           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1304                 _S_left(__x) : _S_right(__x);
1305         }
1306       return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1307     }
1308
1309   template<typename _Key, typename _Val, typename _KeyOfValue,
1310            typename _Compare, typename _Alloc>
1311 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1312     template<typename _Arg>
1313 #endif
1314     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1315     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1317     _M_insert_unique_(const_iterator __position, _Arg&& __v)
1318 #else
1319     _M_insert_unique_(const_iterator __position, const _Val& __v)
1320 #endif
1321     {
1322       // end()
1323       if (__position._M_node == _M_end())
1324         {
1325           if (size() > 0
1326               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1327                                         _KeyOfValue()(__v)))
1328             return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
1329           else
1330             return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1331         }
1332       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1333                                       _S_key(__position._M_node)))
1334         {
1335           // First, try before...
1336           const_iterator __before = __position;
1337           if (__position._M_node == _M_leftmost()) // begin()
1338             return _M_insert_(_M_leftmost(), _M_leftmost(),
1339                               _GLIBCXX_FORWARD(_Arg, __v));
1340           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1341                                           _KeyOfValue()(__v)))
1342             {
1343               if (_S_right(__before._M_node) == 0)
1344                 return _M_insert_(0, __before._M_node,
1345                                   _GLIBCXX_FORWARD(_Arg, __v));
1346               else
1347                 return _M_insert_(__position._M_node,
1348                                   __position._M_node,
1349                                   _GLIBCXX_FORWARD(_Arg, __v));
1350             }
1351           else
1352             return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1353         }
1354       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1355                                       _KeyOfValue()(__v)))
1356         {
1357           // ... then try after.
1358           const_iterator __after = __position;
1359           if (__position._M_node == _M_rightmost())
1360             return _M_insert_(0, _M_rightmost(),
1361                               _GLIBCXX_FORWARD(_Arg, __v));
1362           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1363                                           _S_key((++__after)._M_node)))
1364             {
1365               if (_S_right(__position._M_node) == 0)
1366                 return _M_insert_(0, __position._M_node,
1367                                   _GLIBCXX_FORWARD(_Arg, __v));
1368               else
1369                 return _M_insert_(__after._M_node, __after._M_node,
1370                                   _GLIBCXX_FORWARD(_Arg, __v));
1371             }
1372           else
1373             return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1374         }
1375       else
1376         // Equivalent keys.
1377         return __position._M_const_cast();
1378     }
1379
1380   template<typename _Key, typename _Val, typename _KeyOfValue,
1381            typename _Compare, typename _Alloc>
1382 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1383     template<typename _Arg>
1384 #endif
1385     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1386     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1387 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1388     _M_insert_equal_(const_iterator __position, _Arg&& __v)
1389 #else
1390     _M_insert_equal_(const_iterator __position, const _Val& __v)
1391 #endif
1392     {
1393       // end()
1394       if (__position._M_node == _M_end())
1395         {
1396           if (size() > 0
1397               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1398                                          _S_key(_M_rightmost())))
1399             return _M_insert_(0, _M_rightmost(),
1400                               _GLIBCXX_FORWARD(_Arg, __v));
1401           else
1402             return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1403         }
1404       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1405                                        _KeyOfValue()(__v)))
1406         {
1407           // First, try before...
1408           const_iterator __before = __position;
1409           if (__position._M_node == _M_leftmost()) // begin()
1410             return _M_insert_(_M_leftmost(), _M_leftmost(),
1411                               _GLIBCXX_FORWARD(_Arg, __v));
1412           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1413                                            _S_key((--__before)._M_node)))
1414             {
1415               if (_S_right(__before._M_node) == 0)
1416                 return _M_insert_(0, __before._M_node,
1417                                   _GLIBCXX_FORWARD(_Arg, __v));
1418               else
1419                 return _M_insert_(__position._M_node,
1420                                   __position._M_node,
1421                                   _GLIBCXX_FORWARD(_Arg, __v));
1422             }
1423           else
1424             return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1425         }
1426       else
1427         {
1428           // ... then try after.
1429           const_iterator __after = __position;
1430           if (__position._M_node == _M_rightmost())
1431             return _M_insert_(0, _M_rightmost(),
1432                               _GLIBCXX_FORWARD(_Arg, __v));
1433           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1434                                            _KeyOfValue()(__v)))
1435             {
1436               if (_S_right(__position._M_node) == 0)
1437                 return _M_insert_(0, __position._M_node,
1438                                   _GLIBCXX_FORWARD(_Arg, __v));
1439               else
1440                 return _M_insert_(__after._M_node, __after._M_node,
1441                                   _GLIBCXX_FORWARD(_Arg, __v));
1442             }
1443           else
1444             return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1445         }
1446     }
1447
1448   template<typename _Key, typename _Val, typename _KoV,
1449            typename _Cmp, typename _Alloc>
1450     template<class _II>
1451       void
1452       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1453       _M_insert_unique(_II __first, _II __last)
1454       {
1455         for (; __first != __last; ++__first)
1456           _M_insert_unique_(end(), *__first);
1457       }
1458
1459   template<typename _Key, typename _Val, typename _KoV,
1460            typename _Cmp, typename _Alloc>
1461     template<class _II>
1462       void
1463       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1464       _M_insert_equal(_II __first, _II __last)
1465       {
1466         for (; __first != __last; ++__first)
1467           _M_insert_equal_(end(), *__first);
1468       }
1469
1470   template<typename _Key, typename _Val, typename _KeyOfValue,
1471            typename _Compare, typename _Alloc>
1472     void
1473     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1474     _M_erase_aux(const_iterator __position)
1475     {
1476       _Link_type __y =
1477         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1478                                 (const_cast<_Base_ptr>(__position._M_node),
1479                                  this->_M_impl._M_header));
1480       _M_destroy_node(__y);
1481       --_M_impl._M_node_count;
1482     }
1483
1484   template<typename _Key, typename _Val, typename _KeyOfValue,
1485            typename _Compare, typename _Alloc>
1486     void
1487     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1488     _M_erase_aux(const_iterator __first, const_iterator __last)
1489     {
1490       if (__first == begin() && __last == end())
1491         clear();
1492       else
1493         while (__first != __last)
1494           erase(__first++);
1495     }
1496
1497   template<typename _Key, typename _Val, typename _KeyOfValue,
1498            typename _Compare, typename _Alloc>
1499     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1500     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1501     erase(const _Key& __x)
1502     {
1503       pair<iterator, iterator> __p = equal_range(__x);
1504       const size_type __old_size = size();
1505       erase(__p.first, __p.second);
1506       return __old_size - size();
1507     }
1508
1509   template<typename _Key, typename _Val, typename _KeyOfValue,
1510            typename _Compare, typename _Alloc>
1511     void
1512     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1513     erase(const _Key* __first, const _Key* __last)
1514     {
1515       while (__first != __last)
1516         erase(*__first++);
1517     }
1518
1519   template<typename _Key, typename _Val, typename _KeyOfValue,
1520            typename _Compare, typename _Alloc>
1521     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1522                       _Compare, _Alloc>::iterator
1523     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1524     find(const _Key& __k)
1525     {
1526       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1527       return (__j == end()
1528               || _M_impl._M_key_compare(__k,
1529                                         _S_key(__j._M_node))) ? end() : __j;
1530     }
1531
1532   template<typename _Key, typename _Val, typename _KeyOfValue,
1533            typename _Compare, typename _Alloc>
1534     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1535                       _Compare, _Alloc>::const_iterator
1536     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1537     find(const _Key& __k) const
1538     {
1539       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1540       return (__j == end()
1541               || _M_impl._M_key_compare(__k,
1542                                         _S_key(__j._M_node))) ? end() : __j;
1543     }
1544
1545   template<typename _Key, typename _Val, typename _KeyOfValue,
1546            typename _Compare, typename _Alloc>
1547     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1548     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1549     count(const _Key& __k) const
1550     {
1551       pair<const_iterator, const_iterator> __p = equal_range(__k);
1552       const size_type __n = std::distance(__p.first, __p.second);
1553       return __n;
1554     }
1555
1556   _GLIBCXX_PURE unsigned int
1557   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1558                        const _Rb_tree_node_base* __root) throw ();
1559
1560   template<typename _Key, typename _Val, typename _KeyOfValue,
1561            typename _Compare, typename _Alloc>
1562     bool
1563     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1564     {
1565       if (_M_impl._M_node_count == 0 || begin() == end())
1566         return _M_impl._M_node_count == 0 && begin() == end()
1567                && this->_M_impl._M_header._M_left == _M_end()
1568                && this->_M_impl._M_header._M_right == _M_end();
1569
1570       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1571       for (const_iterator __it = begin(); __it != end(); ++__it)
1572         {
1573           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1574           _Const_Link_type __L = _S_left(__x);
1575           _Const_Link_type __R = _S_right(__x);
1576
1577           if (__x->_M_color == _S_red)
1578             if ((__L && __L->_M_color == _S_red)
1579                 || (__R && __R->_M_color == _S_red))
1580               return false;
1581
1582           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1583             return false;
1584           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1585             return false;
1586
1587           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1588             return false;
1589         }
1590
1591       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1592         return false;
1593       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1594         return false;
1595       return true;
1596     }
1597
1598 _GLIBCXX_END_NAMESPACE_VERSION
1599 } // namespace
1600
1601 #endif