prebuilt/linux-x86/toolchain/i686-linux-glibc2.7-4.4.3/i686-linux/include/c++/4.4.3/bits/stl_tree.h

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