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

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