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

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