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

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1996,1997
  33  * Silicon Graphics Computer Systems, Inc.
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Silicon Graphics makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1994
  45  * Hewlett-Packard Company
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Hewlett-Packard Company makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  *
  55  *
  56  */
  57
  58 /** @file stl_tree.h
  59  *  This is an internal header file, included by other library headers.
  60  *  You should not attempt to use it directly.
  61  */
  62
  63 #ifndef _TREE_H
  64 #define _TREE_H 1
  65
  66 #include <bits/stl_algobase.h>
  67 #include <bits/allocator.h>
  68 #include <bits/stl_construct.h>
  69 #include <bits/stl_function.h>
  70 #include <bits/cpp_type_traits.h>
  71
  72 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
 138   _Rb_tree_node_base*
 139   _Rb_tree_increment(_Rb_tree_node_base* __x);
 140
 141   const _Rb_tree_node_base*
 142   _Rb_tree_increment(const _Rb_tree_node_base* __x);
 143
 144   _Rb_tree_node_base*
 145   _Rb_tree_decrement(_Rb_tree_node_base* __x);
 146
 147   const _Rb_tree_node_base*
 148   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
 149
 150   template<typename _Tp>
 151     struct _Rb_tree_iterator
 152     {
 153       typedef _Tp  value_type;
 154       typedef _Tp& reference;
 155       typedef _Tp* pointer;
 156
 157       typedef bidirectional_iterator_tag iterator_category;
 158       typedef ptrdiff_t                  difference_type;
 159
 160       typedef _Rb_tree_iterator<_Tp>        _Self;
 161       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 162       typedef _Rb_tree_node<_Tp>*           _Link_type;
 163
 164       _Rb_tree_iterator()
 165       : _M_node() { }
 166
 167       explicit
 168       _Rb_tree_iterator(_Link_type __x)
 169       : _M_node(__x) { }
 170
 171       reference
 172       operator*() const
 173       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 174
 175       pointer
 176       operator->() const
 177       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 178
 179       _Self&
 180       operator++()
 181       {
 182         _M_node = _Rb_tree_increment(_M_node);
 183         return *this;
 184       }
 185
 186       _Self
 187       operator++(int)
 188       {
 189         _Self __tmp = *this;
 190         _M_node = _Rb_tree_increment(_M_node);
 191         return __tmp;
 192       }
 193
 194       _Self&
 195       operator--()
 196       {
 197         _M_node = _Rb_tree_decrement(_M_node);
 198         return *this;
 199       }
 200
 201       _Self
 202       operator--(int)
 203       {
 204         _Self __tmp = *this;
 205         _M_node = _Rb_tree_decrement(_M_node);
 206         return __tmp;
 207       }
 208
 209       bool
 210       operator==(const _Self& __x) const
 211       { return _M_node == __x._M_node; }
 212
 213       bool
 214       operator!=(const _Self& __x) const
 215       { return _M_node != __x._M_node; }
 216
 217       _Base_ptr _M_node;
 218   };
 219
 220   template<typename _Tp>
 221     struct _Rb_tree_const_iterator
 222     {
 223       typedef _Tp        value_type;
 224       typedef const _Tp& reference;
 225       typedef const _Tp* pointer;
 226
 227       typedef _Rb_tree_iterator<_Tp> iterator;
 228
 229       typedef bidirectional_iterator_tag iterator_category;
 230       typedef ptrdiff_t                  difference_type;
 231
 232       typedef _Rb_tree_const_iterator<_Tp>        _Self;
 233       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
 234       typedef const _Rb_tree_node<_Tp>*           _Link_type;
 235
 236       _Rb_tree_const_iterator()
 237       : _M_node() { }
 238
 239       explicit
 240       _Rb_tree_const_iterator(_Link_type __x)
 241       : _M_node(__x) { }
 242
 243       _Rb_tree_const_iterator(const iterator& __it)
 244       : _M_node(__it._M_node) { }
 245
 246       reference
 247       operator*() const
 248       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 249
 250       pointer
 251       operator->() const
 252       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 253
 254       _Self&
 255       operator++()
 256       {
 257         _M_node = _Rb_tree_increment(_M_node);
 258         return *this;
 259       }
 260
 261       _Self
 262       operator++(int)
 263       {
 264         _Self __tmp = *this;
 265         _M_node = _Rb_tree_increment(_M_node);
 266         return __tmp;
 267       }
 268
 269       _Self&
 270       operator--()
 271       {
 272         _M_node = _Rb_tree_decrement(_M_node);
 273         return *this;
 274       }
 275
 276       _Self
 277       operator--(int)
 278       {
 279         _Self __tmp = *this;
 280         _M_node = _Rb_tree_decrement(_M_node);
 281         return __tmp;
 282       }
 283
 284       bool
 285       operator==(const _Self& __x) const
 286       { return _M_node == __x._M_node; }
 287
 288       bool
 289       operator!=(const _Self& __x) const
 290       { return _M_node != __x._M_node; }
 291
 292       _Base_ptr _M_node;
 293     };
 294
 295   template<typename _Val>
 296     inline bool
 297     operator==(const _Rb_tree_iterator<_Val>& __x,
 298                const _Rb_tree_const_iterator<_Val>& __y)
 299     { return __x._M_node == __y._M_node; }
 300
 301   template<typename _Val>
 302     inline bool
 303     operator!=(const _Rb_tree_iterator<_Val>& __x,
 304                const _Rb_tree_const_iterator<_Val>& __y)
 305     { return __x._M_node != __y._M_node; }
 306
 307   void
 308   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
 309                        _Rb_tree_node_base*& __root);
 310
 311   void
 312   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
 313                         _Rb_tree_node_base*& __root);
 314
 315   void
 316   _Rb_tree_insert_and_rebalance(const bool __insert_left,
 317                                 _Rb_tree_node_base* __x,
 318                                 _Rb_tree_node_base* __p,
 319                                 _Rb_tree_node_base& __header);
 320
 321   _Rb_tree_node_base*
 322   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 323                                _Rb_tree_node_base& __header);
 324
 325
 326   template<typename _Key, typename _Val, typename _KeyOfValue,
 327            typename _Compare, typename _Alloc = allocator<_Val> >
 328     class _Rb_tree
 329     {
 330       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 331               _Node_allocator;
 332
 333     protected:
 334       typedef _Rb_tree_node_base* _Base_ptr;
 335       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 336       typedef _Rb_tree_node<_Val> _Rb_tree_node;
 337
 338     public:
 339       typedef _Key key_type;
 340       typedef _Val value_type;
 341       typedef value_type* pointer;
 342       typedef const value_type* const_pointer;
 343       typedef value_type& reference;
 344       typedef const value_type& const_reference;
 345       typedef _Rb_tree_node* _Link_type;
 346       typedef const _Rb_tree_node* _Const_Link_type;
 347       typedef size_t size_type;
 348       typedef ptrdiff_t difference_type;
 349       typedef _Alloc allocator_type;
 350
 351       allocator_type
 352       get_allocator() const
 353       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 354
 355     protected:
 356       _Rb_tree_node*
 357       _M_get_node()
 358       { return _M_impl._Node_allocator::allocate(1); }
 359
 360       void
 361       _M_put_node(_Rb_tree_node* __p)
 362       { _M_impl._Node_allocator::deallocate(__p, 1); }
 363
 364       _Link_type
 365       _M_create_node(const value_type& __x)
 366       {
 367         _Link_type __tmp = _M_get_node();
 368         try
 369           { get_allocator().construct(&__tmp->_M_value_field, __x); }
 370         catch(...)
 371           {
 372             _M_put_node(__tmp);
 373             __throw_exception_again;
 374           }
 375         return __tmp;
 376       }
 377
 378       _Link_type
 379       _M_clone_node(_Const_Link_type __x)
 380       {
 381         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 382         __tmp->_M_color = __x->_M_color;
 383         __tmp->_M_left = 0;
 384         __tmp->_M_right = 0;
 385         return __tmp;
 386       }
 387
 388       void
 389       destroy_node(_Link_type __p)
 390       {
 391         get_allocator().destroy(&__p->_M_value_field);
 392         _M_put_node(__p);
 393       }
 394
 395     protected:
 396       template<typename _Key_compare,
 397                bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
 398         struct _Rb_tree_impl : public _Node_allocator
 399         {
 400           _Key_compare          _M_key_compare;
 401           _Rb_tree_node_base    _M_header;
 402           size_type             _M_node_count; // Keeps track of size of tree.
 403
 404           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 405                         const _Key_compare& __comp = _Key_compare())
 406           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 407             _M_node_count(0)
 408           {
 409             this->_M_header._M_color = _S_red;
 410             this->_M_header._M_parent = 0;
 411             this->_M_header._M_left = &this->_M_header;
 412             this->_M_header._M_right = &this->_M_header;
 413           }
 414         };
 415
 416       // Specialization for _Comparison types that are not capable of
 417       // being base classes / super classes.
 418       template<typename _Key_compare>
 419         struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
 420         {
 421           _Key_compare          _M_key_compare;
 422           _Rb_tree_node_base    _M_header;
 423           size_type             _M_node_count; // Keeps track of size of tree.
 424
 425           _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
 426                         const _Key_compare& __comp = _Key_compare())
 427           : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
 428           {
 429             this->_M_header._M_color = _S_red;
 430             this->_M_header._M_parent = 0;
 431             this->_M_header._M_left = &this->_M_header;
 432             this->_M_header._M_right = &this->_M_header;
 433           }
 434         };
 435
 436       _Rb_tree_impl<_Compare> _M_impl;
 437
 438     protected:
 439       _Base_ptr&
 440       _M_root()
 441       { return this->_M_impl._M_header._M_parent; }
 442
 443       _Const_Base_ptr
 444       _M_root() const
 445       { return this->_M_impl._M_header._M_parent; }
 446
 447       _Base_ptr&
 448       _M_leftmost()
 449       { return this->_M_impl._M_header._M_left; }
 450
 451       _Const_Base_ptr
 452       _M_leftmost() const
 453       { return this->_M_impl._M_header._M_left; }
 454
 455       _Base_ptr&
 456       _M_rightmost()
 457       { return this->_M_impl._M_header._M_right; }
 458
 459       _Const_Base_ptr
 460       _M_rightmost() const
 461       { return this->_M_impl._M_header._M_right; }
 462
 463       _Link_type
 464       _M_begin()
 465       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 466
 467       _Const_Link_type
 468       _M_begin() const
 469       {
 470         return static_cast<_Const_Link_type>
 471           (this->_M_impl._M_header._M_parent);
 472       }
 473
 474       _Link_type
 475       _M_end()
 476       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 477
 478       _Const_Link_type
 479       _M_end() const
 480       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 481
 482       static const_reference
 483       _S_value(_Const_Link_type __x)
 484       { return __x->_M_value_field; }
 485
 486       static const _Key&
 487       _S_key(_Const_Link_type __x)
 488       { return _KeyOfValue()(_S_value(__x)); }
 489
 490       static _Link_type
 491       _S_left(_Base_ptr __x)
 492       { return static_cast<_Link_type>(__x->_M_left); }
 493
 494       static _Const_Link_type
 495       _S_left(_Const_Base_ptr __x)
 496       { return static_cast<_Const_Link_type>(__x->_M_left); }
 497
 498       static _Link_type
 499       _S_right(_Base_ptr __x)
 500       { return static_cast<_Link_type>(__x->_M_right); }
 501
 502       static _Const_Link_type
 503       _S_right(_Const_Base_ptr __x)
 504       { return static_cast<_Const_Link_type>(__x->_M_right); }
 505
 506       static const_reference
 507       _S_value(_Const_Base_ptr __x)
 508       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 509
 510       static const _Key&
 511       _S_key(_Const_Base_ptr __x)
 512       { return _KeyOfValue()(_S_value(__x)); }
 513
 514       static _Base_ptr
 515       _S_minimum(_Base_ptr __x)
 516       { return _Rb_tree_node_base::_S_minimum(__x); }
 517
 518       static _Const_Base_ptr
 519       _S_minimum(_Const_Base_ptr __x)
 520       { return _Rb_tree_node_base::_S_minimum(__x); }
 521
 522       static _Base_ptr
 523       _S_maximum(_Base_ptr __x)
 524       { return _Rb_tree_node_base::_S_maximum(__x); }
 525
 526       static _Const_Base_ptr
 527       _S_maximum(_Const_Base_ptr __x)
 528       { return _Rb_tree_node_base::_S_maximum(__x); }
 529
 530     public:
 531       typedef _Rb_tree_iterator<value_type>       iterator;
 532       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 533
 534       typedef std::reverse_iterator<iterator>       reverse_iterator;
 535       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 536
 537     private:
 538       iterator
 539       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 540
 541       _Link_type
 542       _M_copy(_Const_Link_type __x, _Link_type __p);
 543
 544       void
 545       _M_erase(_Link_type __x);
 546
 547     public:
 548       // allocation/deallocation
 549       _Rb_tree()
 550       { }
 551
 552       _Rb_tree(const _Compare& __comp)
 553       : _M_impl(allocator_type(), __comp)
 554       { }
 555
 556       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 557       : _M_impl(__a, __comp)
 558       { }
 559
 560       _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 561       : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
 562       {
 563         if (__x._M_root() != 0)
 564           {
 565             _M_root() = _M_copy(__x._M_begin(), _M_end());
 566             _M_leftmost() = _S_minimum(_M_root());
 567             _M_rightmost() = _S_maximum(_M_root());
 568             _M_impl._M_node_count = __x._M_impl._M_node_count;
 569           }
 570       }
 571
 572       ~_Rb_tree()
 573       { _M_erase(_M_begin()); }
 574
 575       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 576       operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
 577
 578       // Accessors.
 579       _Compare
 580       key_comp() const
 581       { return _M_impl._M_key_compare; }
 582
 583       iterator
 584       begin()
 585       {
 586         return iterator(static_cast<_Link_type>
 587                         (this->_M_impl._M_header._M_left));
 588       }
 589
 590       const_iterator
 591       begin() const
 592       {
 593         return const_iterator(static_cast<_Const_Link_type>
 594                               (this->_M_impl._M_header._M_left));
 595       }
 596
 597       iterator
 598       end()
 599       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 600
 601       const_iterator
 602       end() const
 603       {
 604         return const_iterator(static_cast<_Const_Link_type>
 605                               (&this->_M_impl._M_header));
 606       }
 607
 608       reverse_iterator
 609       rbegin()
 610       { return reverse_iterator(end()); }
 611
 612       const_reverse_iterator
 613       rbegin() const
 614       { return const_reverse_iterator(end()); }
 615
 616       reverse_iterator
 617       rend()
 618       { return reverse_iterator(begin()); }
 619
 620       const_reverse_iterator
 621       rend() const
 622       { return const_reverse_iterator(begin()); }
 623
 624       bool
 625       empty() const
 626       { return _M_impl._M_node_count == 0; }
 627
 628       size_type
 629       size() const
 630       { return _M_impl._M_node_count; }
 631
 632       size_type
 633       max_size() const
 634       { return size_type(-1); }
 635
 636       void
 637       swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
 638
 639       // Insert/erase.
 640       pair<iterator,bool>
 641       insert_unique(const value_type& __x);
 642
 643       iterator
 644       insert_equal(const value_type& __x);
 645
 646       iterator
 647       insert_unique(iterator __position, const value_type& __x);
 648
 649       iterator
 650       insert_equal(iterator __position, const value_type& __x);
 651
 652       template<typename _InputIterator>
 653         void
 654         insert_unique(_InputIterator __first, _InputIterator __last);
 655
 656       template<typename _InputIterator>
 657         void
 658         insert_equal(_InputIterator __first, _InputIterator __last);
 659
 660       void
 661       erase(iterator __position);
 662
 663       size_type
 664       erase(const key_type& __x);
 665
 666       void
 667       erase(iterator __first, iterator __last);
 668
 669       void
 670       erase(const key_type* __first, const key_type* __last);
 671
 672       void
 673       clear()
 674       {
 675         _M_erase(_M_begin());
 676         _M_leftmost() = _M_end();
 677         _M_root() = 0;
 678         _M_rightmost() = _M_end();
 679         _M_impl._M_node_count = 0;
 680       }
 681
 682       // Set operations.
 683       iterator
 684       find(const key_type& __x);
 685
 686       const_iterator
 687       find(const key_type& __x) const;
 688
 689       size_type
 690       count(const key_type& __x) const;
 691
 692       iterator
 693       lower_bound(const key_type& __x);
 694
 695       const_iterator
 696       lower_bound(const key_type& __x) const;
 697
 698       iterator
 699       upper_bound(const key_type& __x);
 700
 701       const_iterator
 702       upper_bound(const key_type& __x) const;
 703
 704       pair<iterator,iterator>
 705       equal_range(const key_type& __x);
 706
 707       pair<const_iterator, const_iterator>
 708       equal_range(const key_type& __x) const;
 709
 710       // Debugging.
 711       bool
 712       __rb_verify() const;
 713     };
 714
 715   template<typename _Key, typename _Val, typename _KeyOfValue,
 716            typename _Compare, typename _Alloc>
 717     inline bool
 718     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 719                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 720     {
 721       return __x.size() == __y.size()
 722              && std::equal(__x.begin(), __x.end(), __y.begin());
 723     }
 724
 725   template<typename _Key, typename _Val, typename _KeyOfValue,
 726            typename _Compare, typename _Alloc>
 727     inline bool
 728     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 729               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 730     {
 731       return std::lexicographical_compare(__x.begin(), __x.end(),
 732                                           __y.begin(), __y.end());
 733     }
 734
 735   template<typename _Key, typename _Val, typename _KeyOfValue,
 736            typename _Compare, typename _Alloc>
 737     inline bool
 738     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 739                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 740     { return !(__x == __y); }
 741
 742   template<typename _Key, typename _Val, typename _KeyOfValue,
 743            typename _Compare, typename _Alloc>
 744     inline bool
 745     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 746               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 747     { return __y < __x; }
 748
 749   template<typename _Key, typename _Val, typename _KeyOfValue,
 750            typename _Compare, typename _Alloc>
 751     inline bool
 752     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 753                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 754     { return !(__y < __x); }
 755
 756   template<typename _Key, typename _Val, typename _KeyOfValue,
 757            typename _Compare, typename _Alloc>
 758     inline bool
 759     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 760                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 761     { return !(__x < __y); }
 762
 763   template<typename _Key, typename _Val, typename _KeyOfValue,
 764            typename _Compare, typename _Alloc>
 765     inline void
 766     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
 767          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
 768     { __x.swap(__y); }
 769
 770   template<typename _Key, typename _Val, typename _KeyOfValue,
 771            typename _Compare, typename _Alloc>
 772     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
 773     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 774     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
 775     {
 776       if (this != &__x)
 777         {
 778           // Note that _Key may be a constant type.
 779           clear();
 780           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 781           if (__x._M_root() != 0)
 782             {
 783               _M_root() = _M_copy(__x._M_begin(), _M_end());
 784               _M_leftmost() = _S_minimum(_M_root());
 785               _M_rightmost() = _S_maximum(_M_root());
 786               _M_impl._M_node_count = __x._M_impl._M_node_count;
 787             }
 788         }
 789       return *this;
 790     }
 791
 792   template<typename _Key, typename _Val, typename _KeyOfValue,
 793            typename _Compare, typename _Alloc>
 794     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 795     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 796     _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
 797     {
 798       bool __insert_left = (__x != 0 || __p == _M_end()
 799                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
 800                                                       _S_key(__p)));
 801
 802       _Link_type __z = _M_create_node(__v);
 803
 804       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
 805                                     this->_M_impl._M_header);
 806       ++_M_impl._M_node_count;
 807       return iterator(__z);
 808     }
 809
 810   template<typename _Key, typename _Val, typename _KeyOfValue,
 811            typename _Compare, typename _Alloc>
 812     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 813     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 814     insert_equal(const _Val& __v)
 815     {
 816       _Link_type __x = _M_begin();
 817       _Link_type __y = _M_end();
 818       while (__x != 0)
 819         {
 820           __y = __x;
 821           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 822                 _S_left(__x) : _S_right(__x);
 823         }
 824       return _M_insert(__x, __y, __v);
 825     }
 826
 827   template<typename _Key, typename _Val, typename _KeyOfValue,
 828            typename _Compare, typename _Alloc>
 829     void
 830     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 831     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
 832     {
 833       if (_M_root() == 0)
 834       {
 835         if (__t._M_root() != 0)
 836         {
 837           _M_root() = __t._M_root();
 838           _M_leftmost() = __t._M_leftmost();
 839           _M_rightmost() = __t._M_rightmost();
 840           _M_root()->_M_parent = _M_end();
 841
 842           __t._M_root() = 0;
 843           __t._M_leftmost() = __t._M_end();
 844           __t._M_rightmost() = __t._M_end();
 845         }
 846       }
 847       else if (__t._M_root() == 0)
 848       {
 849         __t._M_root() = _M_root();
 850         __t._M_leftmost() = _M_leftmost();
 851         __t._M_rightmost() = _M_rightmost();
 852         __t._M_root()->_M_parent = __t._M_end();
 853
 854         _M_root() = 0;
 855         _M_leftmost() = _M_end();
 856         _M_rightmost() = _M_end();
 857       }
 858       else
 859       {
 860         std::swap(_M_root(),__t._M_root());
 861         std::swap(_M_leftmost(),__t._M_leftmost());
 862         std::swap(_M_rightmost(),__t._M_rightmost());
 863
 864         _M_root()->_M_parent = _M_end();
 865         __t._M_root()->_M_parent = __t._M_end();
 866       }
 867       // No need to swap header's color as it does not change.
 868       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 869       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 870     }
 871
 872   template<typename _Key, typename _Val, typename _KeyOfValue,
 873            typename _Compare, typename _Alloc>
 874     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 875                            _Compare, _Alloc>::iterator, bool>
 876     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 877     insert_unique(const _Val& __v)
 878     {
 879       _Link_type __x = _M_begin();
 880       _Link_type __y = _M_end();
 881       bool __comp = true;
 882       while (__x != 0)
 883         {
 884           __y = __x;
 885           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 886           __x = __comp ? _S_left(__x) : _S_right(__x);
 887         }
 888       iterator __j = iterator(__y);
 889       if (__comp)
 890         if (__j == begin())
 891           return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 892         else
 893           --__j;
 894       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 895         return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
 896       return pair<iterator, bool>(__j, false);
 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     insert_unique(iterator __position, const _Val& __v)
 904     {
 905       // end()
 906       if (__position._M_node == _M_end())
 907         {
 908           if (size() > 0
 909               && _M_impl._M_key_compare(_S_key(_M_rightmost()),
 910                                         _KeyOfValue()(__v)))
 911             return _M_insert(0, _M_rightmost(), __v);
 912           else
 913             return insert_unique(__v).first;
 914         }
 915       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
 916                                       _S_key(__position._M_node)))
 917         {
 918           // First, try before...
 919           iterator __before = __position;
 920           if (__position._M_node == _M_leftmost()) // begin()
 921             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
 922           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
 923                                           _KeyOfValue()(__v)))
 924             {
 925               if (_S_right(__before._M_node) == 0)
 926                 return _M_insert(0, __before._M_node, __v);
 927               else
 928                 return _M_insert(__position._M_node,
 929                                  __position._M_node, __v);
 930             }
 931           else
 932             return insert_unique(__v).first;
 933         }
 934       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
 935                                       _KeyOfValue()(__v)))
 936         {
 937           // ... then try after.
 938           iterator __after = __position;
 939           if (__position._M_node == _M_rightmost())
 940             return _M_insert(0, _M_rightmost(), __v);
 941           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
 942                                           _S_key((++__after)._M_node)))
 943             {
 944               if (_S_right(__position._M_node) == 0)
 945                 return _M_insert(0, __position._M_node, __v);
 946               else
 947                 return _M_insert(__after._M_node, __after._M_node, __v);
 948             }
 949           else
 950             return insert_unique(__v).first;
 951         }
 952       else
 953         return __position; // Equivalent keys.
 954     }
 955
 956   template<typename _Key, typename _Val, typename _KeyOfValue,
 957            typename _Compare, typename _Alloc>
 958     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 959     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 960     insert_equal(iterator __position, const _Val& __v)
 961     {
 962       // end()
 963       if (__position._M_node == _M_end())
 964         {
 965           if (size() > 0
 966               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
 967                                          _S_key(_M_rightmost())))
 968             return _M_insert(0, _M_rightmost(), __v);
 969           else
 970             return insert_equal(__v);
 971         }
 972       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
 973                                        _KeyOfValue()(__v)))
 974         {
 975           // First, try before...
 976           iterator __before = __position;
 977           if (__position._M_node == _M_leftmost()) // begin()
 978             return _M_insert(_M_leftmost(), _M_leftmost(), __v);
 979           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
 980                                            _S_key((--__before)._M_node)))
 981             {
 982               if (_S_right(__before._M_node) == 0)
 983                 return _M_insert(0, __before._M_node, __v);
 984               else
 985                 return _M_insert(__position._M_node,
 986                                  __position._M_node, __v);
 987             }
 988           else
 989             return insert_equal(__v);
 990         }
 991       else
 992         {
 993           // ... then try after.
 994           iterator __after = __position;
 995           if (__position._M_node == _M_rightmost())
 996             return _M_insert(0, _M_rightmost(), __v);
 997           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
 998                                            _KeyOfValue()(__v)))
 999             {
1000               if (_S_right(__position._M_node) == 0)
1001                 return _M_insert(0, __position._M_node, __v);
1002               else
1003                 return _M_insert(__after._M_node, __after._M_node, __v);
1004             }
1005           else
1006             return insert_equal(__v);
1007         }
1008     }
1009
1010   template<typename _Key, typename _Val, typename _KoV,
1011            typename _Cmp, typename _Alloc>
1012     template<class _II>
1013       void
1014       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1015       insert_equal(_II __first, _II __last)
1016       {
1017         for (; __first != __last; ++__first)
1018           insert_equal(end(), *__first);
1019       }
1020
1021   template<typename _Key, typename _Val, typename _KoV,
1022            typename _Cmp, typename _Alloc>
1023     template<class _II>
1024     void
1025     _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1026     insert_unique(_II __first, _II __last)
1027     {
1028       for (; __first != __last; ++__first)
1029         insert_unique(end(), *__first);
1030     }
1031
1032   template<typename _Key, typename _Val, typename _KeyOfValue,
1033            typename _Compare, typename _Alloc>
1034     inline void
1035     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1036     erase(iterator __position)
1037     {
1038       _Link_type __y =
1039         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1040                                 (__position._M_node,
1041                                  this->_M_impl._M_header));
1042       destroy_node(__y);
1043       --_M_impl._M_node_count;
1044     }
1045
1046   template<typename _Key, typename _Val, typename _KeyOfValue,
1047            typename _Compare, typename _Alloc>
1048     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1049     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1050     erase(const _Key& __x)
1051     {
1052       pair<iterator,iterator> __p = equal_range(__x);
1053       size_type __n = std::distance(__p.first, __p.second);
1054       erase(__p.first, __p.second);
1055       return __n;
1056     }
1057
1058   template<typename _Key, typename _Val, typename _KoV,
1059            typename _Compare, typename _Alloc>
1060     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1061     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1062     _M_copy(_Const_Link_type __x, _Link_type __p)
1063     {
1064       // Structural copy.  __x and __p must be non-null.
1065       _Link_type __top = _M_clone_node(__x);
1066       __top->_M_parent = __p;
1067
1068       try
1069         {
1070           if (__x->_M_right)
1071             __top->_M_right = _M_copy(_S_right(__x), __top);
1072           __p = __top;
1073           __x = _S_left(__x);
1074
1075           while (__x != 0)
1076             {
1077               _Link_type __y = _M_clone_node(__x);
1078               __p->_M_left = __y;
1079               __y->_M_parent = __p;
1080               if (__x->_M_right)
1081                 __y->_M_right = _M_copy(_S_right(__x), __y);
1082               __p = __y;
1083               __x = _S_left(__x);
1084             }
1085         }
1086       catch(...)
1087         {
1088           _M_erase(__top);
1089           __throw_exception_again;
1090         }
1091       return __top;
1092     }
1093
1094   template<typename _Key, typename _Val, typename _KeyOfValue,
1095            typename _Compare, typename _Alloc>
1096     void
1097     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1098     _M_erase(_Link_type __x)
1099     {
1100       // Erase without rebalancing.
1101       while (__x != 0)
1102         {
1103           _M_erase(_S_right(__x));
1104           _Link_type __y = _S_left(__x);
1105           destroy_node(__x);
1106           __x = __y;
1107         }
1108     }
1109
1110   template<typename _Key, typename _Val, typename _KeyOfValue,
1111            typename _Compare, typename _Alloc>
1112     void
1113     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1114     erase(iterator __first, iterator __last)
1115     {
1116       if (__first == begin() && __last == end())
1117         clear();
1118       else
1119         while (__first != __last)
1120           erase(__first++);
1121     }
1122
1123   template<typename _Key, typename _Val, typename _KeyOfValue,
1124            typename _Compare, typename _Alloc>
1125     void
1126     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1127     erase(const _Key* __first, const _Key* __last)
1128     {
1129       while (__first != __last)
1130         erase(*__first++);
1131     }
1132
1133   template<typename _Key, typename _Val, typename _KeyOfValue,
1134            typename _Compare, typename _Alloc>
1135     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1136     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1137     find(const _Key& __k)
1138     {
1139       _Link_type __x = _M_begin(); // Current node.
1140       _Link_type __y = _M_end(); // Last node which is not less than __k.
1141
1142       while (__x != 0)
1143         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1144           __y = __x, __x = _S_left(__x);
1145         else
1146           __x = _S_right(__x);
1147
1148       iterator __j = iterator(__y);
1149       return (__j == end()
1150               || _M_impl._M_key_compare(__k,
1151                                         _S_key(__j._M_node))) ? end() : __j;
1152     }
1153
1154   template<typename _Key, typename _Val, typename _KeyOfValue,
1155            typename _Compare, typename _Alloc>
1156     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1157     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1158     find(const _Key& __k) const
1159     {
1160       _Const_Link_type __x = _M_begin(); // Current node.
1161       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1162
1163      while (__x != 0)
1164        {
1165          if (!_M_impl._M_key_compare(_S_key(__x), __k))
1166            __y = __x, __x = _S_left(__x);
1167          else
1168            __x = _S_right(__x);
1169        }
1170      const_iterator __j = const_iterator(__y);
1171      return (__j == end()
1172              || _M_impl._M_key_compare(__k,
1173                                        _S_key(__j._M_node))) ? end() : __j;
1174     }
1175
1176   template<typename _Key, typename _Val, typename _KeyOfValue,
1177            typename _Compare, typename _Alloc>
1178     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1179     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1180     count(const _Key& __k) const
1181     {
1182       pair<const_iterator, const_iterator> __p = equal_range(__k);
1183       const size_type __n = std::distance(__p.first, __p.second);
1184       return __n;
1185     }
1186
1187   template<typename _Key, typename _Val, typename _KeyOfValue,
1188            typename _Compare, typename _Alloc>
1189     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1190     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1191     lower_bound(const _Key& __k)
1192     {
1193       _Link_type __x = _M_begin(); // Current node.
1194       _Link_type __y = _M_end(); // Last node which is not less than __k.
1195
1196       while (__x != 0)
1197         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1198           __y = __x, __x = _S_left(__x);
1199         else
1200           __x = _S_right(__x);
1201
1202       return iterator(__y);
1203     }
1204
1205   template<typename _Key, typename _Val, typename _KeyOfValue,
1206            typename _Compare, typename _Alloc>
1207     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1208     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1209     lower_bound(const _Key& __k) const
1210     {
1211       _Const_Link_type __x = _M_begin(); // Current node.
1212       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1213
1214       while (__x != 0)
1215         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1216           __y = __x, __x = _S_left(__x);
1217         else
1218           __x = _S_right(__x);
1219
1220       return const_iterator(__y);
1221     }
1222
1223   template<typename _Key, typename _Val, typename _KeyOfValue,
1224            typename _Compare, typename _Alloc>
1225     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1226     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1227     upper_bound(const _Key& __k)
1228     {
1229       _Link_type __x = _M_begin(); // Current node.
1230       _Link_type __y = _M_end(); // Last node which is greater than __k.
1231
1232       while (__x != 0)
1233         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1234           __y = __x, __x = _S_left(__x);
1235         else
1236           __x = _S_right(__x);
1237
1238       return iterator(__y);
1239     }
1240
1241   template<typename _Key, typename _Val, typename _KeyOfValue,
1242            typename _Compare, typename _Alloc>
1243     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1244     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1245     upper_bound(const _Key& __k) const
1246     {
1247       _Const_Link_type __x = _M_begin(); // Current node.
1248       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1249
1250       while (__x != 0)
1251         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1252           __y = __x, __x = _S_left(__x);
1253         else
1254           __x = _S_right(__x);
1255
1256       return const_iterator(__y);
1257     }
1258
1259   template<typename _Key, typename _Val, typename _KeyOfValue,
1260            typename _Compare, typename _Alloc>
1261     inline
1262     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1263                            _Compare, _Alloc>::iterator,
1264          typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1265     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1266     equal_range(const _Key& __k)
1267     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1268
1269   template<typename _Key, typename _Val, typename _KoV,
1270            typename _Compare, typename _Alloc>
1271     inline
1272     pair<typename _Rb_tree<_Key, _Val, _KoV,
1273                            _Compare, _Alloc>::const_iterator,
1274          typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1275     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1276     equal_range(const _Key& __k) const
1277     { return pair<const_iterator, const_iterator>(lower_bound(__k),
1278                                                   upper_bound(__k)); }
1279
1280   unsigned int
1281   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1282                        const _Rb_tree_node_base* __root);
1283
1284   template<typename _Key, typename _Val, typename _KeyOfValue,
1285            typename _Compare, typename _Alloc>
1286     bool
1287     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1288     {
1289       if (_M_impl._M_node_count == 0 || begin() == end())
1290         return _M_impl._M_node_count == 0 && begin() == end()
1291                && this->_M_impl._M_header._M_left == _M_end()
1292                && this->_M_impl._M_header._M_right == _M_end();
1293
1294       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1295       for (const_iterator __it = begin(); __it != end(); ++__it)
1296         {
1297           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1298           _Const_Link_type __L = _S_left(__x);
1299           _Const_Link_type __R = _S_right(__x);
1300
1301           if (__x->_M_color == _S_red)
1302             if ((__L && __L->_M_color == _S_red)
1303                 || (__R && __R->_M_color == _S_red))
1304               return false;
1305
1306           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1307             return false;
1308           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1309             return false;
1310
1311           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1312             return false;
1313         }
1314
1315       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1316         return false;
1317       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1318         return false;
1319       return true;
1320     }
1321 } // namespace std
1322
1323 #endif