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

   1 // RB tree implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 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 __GLIBCPP_INTERNAL_TREE_H
  64 #define __GLIBCPP_INTERNAL_TREE_H
  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/stl_alloc.h>
  88 #include <bits/stl_construct.h>
  89 #include <bits/stl_function.h>
  90
  91 namespace std
  92 {
  93   enum _Rb_tree_color { _M_red = false, _M_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 == _M_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(_Link_type __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 = _M_red;
 309     while (__x != __root
 310            && __x->_M_parent->_M_color == _M_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 == _M_red)
 316               {
 317                 __x->_M_parent->_M_color = _M_black;
 318                 __y->_M_color = _M_black;
 319                 __x->_M_parent->_M_parent->_M_color = _M_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 = _M_black;
 330                 __x->_M_parent->_M_parent->_M_color = _M_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 == _M_red)
 338               {
 339                 __x->_M_parent->_M_color = _M_black;
 340                 __y->_M_color = _M_black;
 341                 __x->_M_parent->_M_parent->_M_color = _M_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 = _M_black;
 352                 __x->_M_parent->_M_parent->_M_color = _M_red;
 353                 _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
 354               }
 355           }
 356       }
 357     __root->_M_color = _M_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 != _M_red)
 434       {
 435         while (__x != __root && (__x == 0 || __x->_M_color == _M_black))
 436           if (__x == __x_parent->_M_left)
 437             {
 438               _Rb_tree_node_base* __w = __x_parent->_M_right;
 439               if (__w->_M_color == _M_red)
 440                 {
 441                   __w->_M_color = _M_black;
 442                   __x_parent->_M_color = _M_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 == _M_black) &&
 448                   (__w->_M_right == 0 ||
 449                    __w->_M_right->_M_color == _M_black))
 450                 {
 451                   __w->_M_color = _M_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 == _M_black)
 459                     {
 460                       if (__w->_M_left) __w->_M_left->_M_color = _M_black;
 461                       __w->_M_color = _M_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 = _M_black;
 467                   if (__w->_M_right)
 468                     __w->_M_right->_M_color = _M_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 == _M_red)
 478                 {
 479                   __w->_M_color = _M_black;
 480                   __x_parent->_M_color = _M_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 == _M_black) &&
 486                   (__w->_M_left == 0 ||
 487                    __w->_M_left->_M_color == _M_black))
 488                 {
 489                   __w->_M_color = _M_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 == _M_black)
 496                     {
 497                       if (__w->_M_right) __w->_M_right->_M_color = _M_black;
 498                       __w->_M_color = _M_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 = _M_black;
 504                   if (__w->_M_left)
 505                     __w->_M_left->_M_color = _M_black;
 506                   _Rb_tree_rotate_right(__x_parent, __root);
 507                   break;
 508                 }
 509             }
 510         if (__x) __x->_M_color = _M_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), _M_header(0) {}
 532
 533     protected:
 534       typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
 535       _M_node_allocator;
 536
 537       _Rb_tree_node<_Tp>* _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&) : _M_header(0) {}
 556
 557     protected:
 558       _Rb_tree_node<_Tp>* _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) { _M_header = _M_get_node(); }
 580       ~_Rb_tree_base() { _M_put_node(_M_header); }
 581     };
 582
 583
 584   template<typename _Key, typename _Val, typename _KeyOfValue,
 585            typename _Compare, typename _Alloc = allocator<_Val> >
 586     class _Rb_tree : protected _Rb_tree_base<_Val, _Alloc>
 587     {
 588       typedef _Rb_tree_base<_Val, _Alloc> _Base;
 589
 590     protected:
 591       typedef _Rb_tree_node_base* _Base_ptr;
 592       typedef _Rb_tree_node<_Val> _Rb_tree_node;
 593
 594     public:
 595       typedef _Key key_type;
 596       typedef _Val value_type;
 597       typedef value_type* pointer;
 598       typedef const value_type* const_pointer;
 599       typedef value_type& reference;
 600       typedef const value_type& const_reference;
 601       typedef _Rb_tree_node* _Link_type;
 602       typedef size_t size_type;
 603       typedef ptrdiff_t difference_type;
 604
 605       typedef typename _Base::allocator_type allocator_type;
 606       allocator_type get_allocator() const { return _Base::get_allocator(); }
 607
 608     protected:
 609       using _Base::_M_get_node;
 610       using _Base::_M_put_node;
 611       using _Base::_M_header;
 612
 613       _Link_type
 614       _M_create_node(const value_type& __x)
 615       {
 616         _Link_type __tmp = _M_get_node();
 617         try
 618           { _Construct(&__tmp->_M_value_field, __x); }
 619         catch(...)
 620           {
 621           _M_put_node(__tmp);
 622           __throw_exception_again;
 623           }
 624         return __tmp;
 625       }
 626
 627       _Link_type
 628       _M_clone_node(_Link_type __x)
 629       {
 630         _Link_type __tmp = _M_create_node(__x->_M_value_field);
 631         __tmp->_M_color = __x->_M_color;
 632         __tmp->_M_left = 0;
 633         __tmp->_M_right = 0;
 634         return __tmp;
 635       }
 636
 637       void
 638       destroy_node(_Link_type __p)
 639       {
 640         _Destroy(&__p->_M_value_field);
 641         _M_put_node(__p);
 642       }
 643
 644       size_type _M_node_count; // keeps track of size of tree
 645       _Compare _M_key_compare;
 646
 647       _Link_type&
 648       _M_root() const { return (_Link_type&) _M_header->_M_parent; }
 649
 650       _Link_type&
 651       _M_leftmost() const { return (_Link_type&) _M_header->_M_left; }
 652
 653       _Link_type&
 654       _M_rightmost() const { return (_Link_type&) _M_header->_M_right; }
 655
 656       static _Link_type&
 657       _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
 658
 659       static _Link_type&
 660       _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); }
 661
 662       static _Link_type&
 663       _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); }
 664
 665       static reference
 666       _S_value(_Link_type __x) { return __x->_M_value_field; }
 667
 668       static const _Key&
 669       _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
 670
 671       static _Rb_tree_color&
 672       _S_color(_Link_type __x) { return __x->_M_color; }
 673
 674       static _Link_type&
 675       _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
 676
 677       static _Link_type&
 678       _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); }
 679
 680       static _Link_type&
 681       _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); }
 682
 683       static reference
 684       _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; }
 685
 686       static const _Key&
 687       _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));}
 688
 689       static _Rb_tree_color&
 690       _S_color(_Base_ptr __x) { return (_Link_type(__x)->_M_color); }
 691
 692       static _Link_type
 693       _S_minimum(_Link_type __x)
 694       { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
 695
 696       static _Link_type
 697       _S_maximum(_Link_type __x)
 698       { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
 699
 700     public:
 701       typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
 702       typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
 703       const_iterator;
 704
 705       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 706       typedef std::reverse_iterator<iterator> reverse_iterator;
 707
 708     private:
 709       iterator
 710       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 711
 712       _Link_type
 713       _M_copy(_Link_type __x, _Link_type __p);
 714
 715       void
 716       _M_erase(_Link_type __x);
 717
 718     public:
 719       // allocation/deallocation
 720       _Rb_tree()
 721         : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
 722       { _M_empty_initialize(); }
 723
 724       _Rb_tree(const _Compare& __comp)
 725         : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
 726       { _M_empty_initialize(); }
 727
 728       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 729         : _Base(__a), _M_node_count(0), _M_key_compare(__comp)
 730       { _M_empty_initialize(); }
 731
 732       _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
 733         : _Base(__x.get_allocator()), _M_node_count(0),
 734                  _M_key_compare(__x._M_key_compare)
 735       {
 736         if (__x._M_root() == 0)
 737           _M_empty_initialize();
 738         else
 739           {
 740             _S_color(_M_header) = _M_red;
 741             _M_root() = _M_copy(__x._M_root(), _M_header);
 742             _M_leftmost() = _S_minimum(_M_root());
 743             _M_rightmost() = _S_maximum(_M_root());
 744           }
 745         _M_node_count = __x._M_node_count;
 746       }
 747
 748       ~_Rb_tree() { clear(); }
 749
 750       _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
 751       operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
 752
 753     private:
 754       void _M_empty_initialize()
 755       {
 756         _S_color(_M_header) = _M_red; // used to distinguish header from
 757         // __root, in iterator.operator++
 758         _M_root() = 0;
 759         _M_leftmost() = _M_header;
 760         _M_rightmost() = _M_header;
 761       }
 762
 763     public:
 764       // Accessors.
 765       _Compare
 766       key_comp() const { return _M_key_compare; }
 767
 768       iterator
 769       begin() { return _M_leftmost(); }
 770
 771       const_iterator
 772       begin() const { return _M_leftmost(); }
 773
 774       iterator
 775       end() { return _M_header; }
 776
 777       const_iterator
 778       end() const { return _M_header; }
 779
 780       reverse_iterator
 781       rbegin() { return reverse_iterator(end()); }
 782
 783       const_reverse_iterator
 784       rbegin() const { return const_reverse_iterator(end()); }
 785
 786       reverse_iterator
 787       rend() { return reverse_iterator(begin()); }
 788
 789       const_reverse_iterator
 790       rend() const { return const_reverse_iterator(begin()); }
 791
 792       bool
 793       empty() const { return _M_node_count == 0; }
 794
 795       size_type
 796       size() const { return _M_node_count; }
 797
 798       size_type
 799       max_size() const { return size_type(-1); }
 800
 801       void
 802       swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
 803       {
 804         std::swap(_M_header, __t._M_header);
 805         std::swap(_M_node_count, __t._M_node_count);
 806         std::swap(_M_key_compare, __t._M_key_compare);
 807       }
 808
 809       // Insert/erase.
 810       pair<iterator,bool>
 811       insert_unique(const value_type& __x);
 812
 813       iterator
 814       insert_equal(const value_type& __x);
 815
 816       iterator
 817       insert_unique(iterator __position, const value_type& __x);
 818
 819       iterator
 820       insert_equal(iterator __position, const value_type& __x);
 821
 822       template<typename _InputIterator>
 823       void
 824       insert_unique(_InputIterator __first, _InputIterator __last);
 825
 826       template<typename _InputIterator>
 827       void
 828       insert_equal(_InputIterator __first, _InputIterator __last);
 829
 830       void
 831       erase(iterator __position);
 832
 833       size_type
 834       erase(const key_type& __x);
 835
 836       void
 837       erase(iterator __first, iterator __last);
 838
 839       void
 840       erase(const key_type* __first, const key_type* __last);
 841
 842       void
 843       clear()
 844       {
 845         if (_M_node_count != 0)
 846           {
 847             _M_erase(_M_root());
 848             _M_leftmost() = _M_header;
 849             _M_root() = 0;
 850             _M_rightmost() = _M_header;
 851             _M_node_count = 0;
 852           }
 853       }
 854
 855       // Set operations.
 856       iterator
 857       find(const key_type& __x);
 858
 859       const_iterator
 860       find(const key_type& __x) const;
 861
 862       size_type
 863       count(const key_type& __x) const;
 864
 865       iterator
 866       lower_bound(const key_type& __x);
 867
 868       const_iterator
 869       lower_bound(const key_type& __x) const;
 870
 871       iterator
 872       upper_bound(const key_type& __x);
 873
 874       const_iterator
 875       upper_bound(const key_type& __x) const;
 876
 877       pair<iterator,iterator>
 878       equal_range(const key_type& __x);
 879
 880       pair<const_iterator, const_iterator>
 881       equal_range(const key_type& __x) const;
 882
 883       // Debugging.
 884       bool
 885       __rb_verify() const;
 886     };
 887
 888   template<typename _Key, typename _Val, typename _KeyOfValue,
 889            typename _Compare, typename _Alloc>
 890     inline bool
 891     operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 892                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 893     {
 894       return __x.size() == __y.size() &&
 895         equal(__x.begin(), __x.end(), __y.begin());
 896     }
 897
 898   template<typename _Key, typename _Val, typename _KeyOfValue,
 899            typename _Compare, typename _Alloc>
 900     inline bool
 901     operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 902               const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 903     {
 904       return lexicographical_compare(__x.begin(), __x.end(),
 905                                      __y.begin(), __y.end());
 906     }
 907
 908   template<typename _Key, typename _Val, typename _KeyOfValue,
 909            typename _Compare, typename _Alloc>
 910     inline bool
 911     operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 912                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 913     { return !(__x == __y); }
 914
 915   template<typename _Key, typename _Val, typename _KeyOfValue,
 916            typename _Compare, typename _Alloc>
 917     inline bool
 918     operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 919               const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 920     { return __y < __x; }
 921
 922   template<typename _Key, typename _Val, typename _KeyOfValue,
 923            typename _Compare, typename _Alloc>
 924     inline bool
 925     operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 926                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 927   { return !(__y < __x); }
 928
 929   template<typename _Key, typename _Val, typename _KeyOfValue,
 930            typename _Compare, typename _Alloc>
 931     inline bool
 932     operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 933                const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 934   { return !(__x < __y); }
 935
 936   template<typename _Key, typename _Val, typename _KeyOfValue,
 937            typename _Compare, typename _Alloc>
 938     inline void
 939     swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 940          _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
 941     { __x.swap(__y); }
 942
 943   template<typename _Key, typename _Val, typename _KeyOfValue,
 944            typename _Compare, typename _Alloc>
 945     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
 946     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 947     operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
 948     {
 949       if (this != &__x)
 950         {
 951           // Note that _Key may be a constant type.
 952           clear();
 953           _M_node_count = 0;
 954           _M_key_compare = __x._M_key_compare;
 955           if (__x._M_root() == 0)
 956             {
 957               _M_root() = 0;
 958               _M_leftmost() = _M_header;
 959               _M_rightmost() = _M_header;
 960             }
 961           else
 962             {
 963               _M_root() = _M_copy(__x._M_root(), _M_header);
 964               _M_leftmost() = _S_minimum(_M_root());
 965               _M_rightmost() = _S_maximum(_M_root());
 966               _M_node_count = __x._M_node_count;
 967             }
 968         }
 969       return *this;
 970     }
 971
 972   template<typename _Key, typename _Val, typename _KeyOfValue,
 973            typename _Compare, typename _Alloc>
 974     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
 975     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
 976     _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v)
 977     {
 978       _Link_type __x = (_Link_type) __x_;
 979       _Link_type __y = (_Link_type) __y_;
 980       _Link_type __z;
 981
 982       if (__y == _M_header || __x != 0 ||
 983           _M_key_compare(_KeyOfValue()(__v), _S_key(__y)))
 984         {
 985           __z = _M_create_node(__v);
 986           _S_left(__y) = __z;               // also makes _M_leftmost() = __z
 987           //    when __y == _M_header
 988           if (__y == _M_header)
 989             {
 990               _M_root() = __z;
 991               _M_rightmost() = __z;
 992             }
 993           else if (__y == _M_leftmost())
 994             _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
 995         }
 996       else
 997         {
 998           __z = _M_create_node(__v);
 999           _S_right(__y) = __z;
1000           // Maintain _M_rightmost() pointing to max node.
1001           if (__y == _M_rightmost())
1002             _M_rightmost() = __z;
1003         }
1004       _S_parent(__z) = __y;
1005       _S_left(__z) = 0;
1006       _S_right(__z) = 0;
1007       _Rb_tree_rebalance(__z, _M_header->_M_parent);
1008       ++_M_node_count;
1009       return iterator(__z);
1010     }
1011
1012   template<typename _Key, typename _Val, typename _KeyOfValue,
1013            typename _Compare, typename _Alloc>
1014     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1015     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1016     insert_equal(const _Val& __v)
1017     {
1018       _Link_type __y = _M_header;
1019       _Link_type __x = _M_root();
1020       while (__x != 0)
1021         {
1022           __y = __x;
1023           __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1024             _S_left(__x) : _S_right(__x);
1025         }
1026       return _M_insert(__x, __y, __v);
1027     }
1028
1029   template<typename _Key, typename _Val, typename _KeyOfValue,
1030            typename _Compare, typename _Alloc>
1031     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
1032     bool>
1033     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1034     insert_unique(const _Val& __v)
1035     {
1036       _Link_type __y = _M_header;
1037       _Link_type __x = _M_root();
1038       bool __comp = true;
1039       while (__x != 0)
1040         {
1041           __y = __x;
1042           __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1043           __x = __comp ? _S_left(__x) : _S_right(__x);
1044         }
1045       iterator __j = iterator(__y);
1046       if (__comp)
1047         if (__j == begin())
1048           return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
1049         else
1050           --__j;
1051       if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1052         return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
1053       return pair<iterator,bool>(__j, false);
1054     }
1055
1056
1057   template<typename _Key, typename _Val, typename _KeyOfValue,
1058            typename _Compare, typename _Alloc>
1059     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1060     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1061     insert_unique(iterator __position, const _Val& __v)
1062     {
1063       if (__position._M_node == _M_header->_M_left)
1064         {
1065           // begin()
1066           if (size() > 0 &&
1067               _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
1068             return _M_insert(__position._M_node, __position._M_node, __v);
1069           // first argument just needs to be non-null
1070           else
1071             return insert_unique(__v).first;
1072         }
1073       else if (__position._M_node == _M_header)
1074         {
1075           // end()
1076           if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
1077             return _M_insert(0, _M_rightmost(), __v);
1078           else
1079             return insert_unique(__v).first;
1080         }
1081       else
1082         {
1083           iterator __before = __position;
1084           --__before;
1085           if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
1086               && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node)))
1087             {
1088               if (_S_right(__before._M_node) == 0)
1089                 return _M_insert(0, __before._M_node, __v);
1090               else
1091                 return _M_insert(__position._M_node, __position._M_node, __v);
1092               // first argument just needs to be non-null
1093             }
1094           else
1095             return insert_unique(__v).first;
1096         }
1097     }
1098
1099   template<typename _Key, typename _Val, typename _KeyOfValue,
1100            typename _Compare, typename _Alloc>
1101     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1102     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1103     insert_equal(iterator __position, const _Val& __v)
1104     {
1105       if (__position._M_node == _M_header->_M_left)
1106         {
1107           // begin()
1108           if (size() > 0 &&
1109               !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
1110             return _M_insert(__position._M_node, __position._M_node, __v);
1111           // first argument just needs to be non-null
1112           else
1113             return insert_equal(__v);
1114         }
1115       else if (__position._M_node == _M_header)
1116         {
1117           // end()
1118           if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
1119             return _M_insert(0, _M_rightmost(), __v);
1120           else
1121             return insert_equal(__v);
1122         }
1123       else
1124         {
1125           iterator __before = __position;
1126           --__before;
1127           if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
1128               && !_M_key_compare(_S_key(__position._M_node),
1129                                  _KeyOfValue()(__v)))
1130             {
1131               if (_S_right(__before._M_node) == 0)
1132                 return _M_insert(0, __before._M_node, __v);
1133               else
1134                 return _M_insert(__position._M_node, __position._M_node, __v);
1135               // first argument just needs to be non-null
1136             }
1137           else
1138             return insert_equal(__v);
1139         }
1140     }
1141
1142   template<typename _Key, typename _Val, typename _KoV,
1143            typename _Cmp, typename _Alloc>
1144     template<class _II>
1145       void
1146       _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
1147       insert_equal(_II __first, _II __last)
1148       {
1149         for ( ; __first != __last; ++__first)
1150           insert_equal(*__first);
1151       }
1152
1153   template<typename _Key, typename _Val, typename _KoV,
1154            typename _Cmp, typename _Alloc>
1155     template<class _II>
1156     void
1157     _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
1158     insert_unique(_II __first, _II __last)
1159     {
1160       for ( ; __first != __last; ++__first)
1161         insert_unique(*__first);
1162     }
1163
1164   template<typename _Key, typename _Val, typename _KeyOfValue,
1165            typename _Compare, typename _Alloc>
1166     inline void
1167     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
1168     {
1169       _Link_type __y =
1170         (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
1171                                                   _M_header->_M_parent,
1172                                                   _M_header->_M_left,
1173                                                   _M_header->_M_right);
1174       destroy_node(__y);
1175       --_M_node_count;
1176     }
1177
1178   template<typename _Key, typename _Val, typename _KeyOfValue,
1179            typename _Compare, typename _Alloc>
1180     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1181     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
1182     {
1183       pair<iterator,iterator> __p = equal_range(__x);
1184       size_type __n = distance(__p.first, __p.second);
1185       erase(__p.first, __p.second);
1186       return __n;
1187     }
1188
1189   template<typename _Key, typename _Val, typename _KoV,
1190            typename _Compare, typename _Alloc>
1191     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1192     _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
1193     _M_copy(_Link_type __x, _Link_type __p)
1194     {
1195       // Structural copy.  __x and __p must be non-null.
1196       _Link_type __top = _M_clone_node(__x);
1197       __top->_M_parent = __p;
1198
1199       try
1200         {
1201           if (__x->_M_right)
1202             __top->_M_right = _M_copy(_S_right(__x), __top);
1203           __p = __top;
1204           __x = _S_left(__x);
1205
1206           while (__x != 0)
1207             {
1208               _Link_type __y = _M_clone_node(__x);
1209               __p->_M_left = __y;
1210               __y->_M_parent = __p;
1211               if (__x->_M_right)
1212                 __y->_M_right = _M_copy(_S_right(__x), __y);
1213               __p = __y;
1214               __x = _S_left(__x);
1215             }
1216         }
1217       catch(...)
1218         {
1219           _M_erase(__top);
1220           __throw_exception_again;
1221         }
1222       return __top;
1223     }
1224
1225   template<typename _Key, typename _Val, typename _KeyOfValue,
1226            typename _Compare, typename _Alloc>
1227     void
1228     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
1229     {
1230       // Erase without rebalancing.
1231       while (__x != 0)
1232         {
1233           _M_erase(_S_right(__x));
1234           _Link_type __y = _S_left(__x);
1235           destroy_node(__x);
1236           __x = __y;
1237         }
1238     }
1239
1240   template<typename _Key, typename _Val, typename _KeyOfValue,
1241            typename _Compare, typename _Alloc>
1242     void
1243     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1244     erase(iterator __first, iterator __last)
1245     {
1246       if (__first == begin() && __last == end())
1247         clear();
1248       else
1249         while (__first != __last) erase(__first++);
1250     }
1251
1252   template<typename _Key, typename _Val, typename _KeyOfValue,
1253            typename _Compare, typename _Alloc>
1254     void
1255     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1256     erase(const _Key* __first, const _Key* __last)
1257     {
1258       while (__first != __last)
1259         erase(*__first++);
1260     }
1261
1262   template<typename _Key, typename _Val, typename _KeyOfValue,
1263            typename _Compare, typename _Alloc>
1264     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1265     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
1266     {
1267       _Link_type __y = _M_header;  // Last node which is not less than __k.
1268       _Link_type __x = _M_root();  // Current node.
1269
1270       while (__x != 0)
1271         if (!_M_key_compare(_S_key(__x), __k))
1272           __y = __x, __x = _S_left(__x);
1273         else
1274           __x = _S_right(__x);
1275
1276       iterator __j = iterator(__y);
1277       return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1278         end() : __j;
1279     }
1280
1281   template<typename _Key, typename _Val, typename _KeyOfValue,
1282            typename _Compare, typename _Alloc>
1283     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1284     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1285     find(const _Key& __k) const
1286     {
1287       _Link_type __y = _M_header; // Last node which is not less than __k.
1288       _Link_type __x = _M_root(); // Current node.
1289
1290      while (__x != 0)
1291        {
1292          if (!_M_key_compare(_S_key(__x), __k))
1293            __y = __x, __x = _S_left(__x);
1294          else
1295            __x = _S_right(__x);
1296        }
1297      const_iterator __j = const_iterator(__y);
1298      return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
1299        end() : __j;
1300     }
1301
1302   template<typename _Key, typename _Val, typename _KeyOfValue,
1303            typename _Compare, typename _Alloc>
1304     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1305     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1306     count(const _Key& __k) const
1307     {
1308       pair<const_iterator, const_iterator> __p = equal_range(__k);
1309       size_type __n = distance(__p.first, __p.second);
1310       return __n;
1311     }
1312
1313   template<typename _Key, typename _Val, typename _KeyOfValue,
1314            typename _Compare, typename _Alloc>
1315     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1316     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1317     lower_bound(const _Key& __k)
1318     {
1319       _Link_type __y = _M_header; /* Last node which is not less than __k. */
1320       _Link_type __x = _M_root(); /* Current node. */
1321
1322       while (__x != 0)
1323         if (!_M_key_compare(_S_key(__x), __k))
1324           __y = __x, __x = _S_left(__x);
1325         else
1326           __x = _S_right(__x);
1327
1328       return iterator(__y);
1329     }
1330
1331   template<typename _Key, typename _Val, typename _KeyOfValue,
1332            typename _Compare, typename _Alloc>
1333     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1334     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1335     lower_bound(const _Key& __k) const
1336     {
1337       _Link_type __y = _M_header; /* Last node which is not less than __k. */
1338       _Link_type __x = _M_root(); /* Current node. */
1339
1340       while (__x != 0)
1341         if (!_M_key_compare(_S_key(__x), __k))
1342           __y = __x, __x = _S_left(__x);
1343         else
1344           __x = _S_right(__x);
1345
1346       return const_iterator(__y);
1347     }
1348
1349   template<typename _Key, typename _Val, typename _KeyOfValue,
1350            typename _Compare, typename _Alloc>
1351     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1352     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1353     upper_bound(const _Key& __k)
1354     {
1355       _Link_type __y = _M_header; /* Last node which is greater than __k. */
1356       _Link_type __x = _M_root(); /* Current node. */
1357
1358       while (__x != 0)
1359         if (_M_key_compare(__k, _S_key(__x)))
1360           __y = __x, __x = _S_left(__x);
1361         else
1362           __x = _S_right(__x);
1363
1364       return iterator(__y);
1365     }
1366
1367   template<typename _Key, typename _Val, typename _KeyOfValue,
1368            typename _Compare, typename _Alloc>
1369     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1370     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1371     upper_bound(const _Key& __k) const
1372     {
1373       _Link_type __y = _M_header; /* Last node which is greater than __k. */
1374       _Link_type __x = _M_root(); /* Current node. */
1375
1376       while (__x != 0)
1377         if (_M_key_compare(__k, _S_key(__x)))
1378           __y = __x, __x = _S_left(__x);
1379         else
1380           __x = _S_right(__x);
1381
1382       return const_iterator(__y);
1383     }
1384
1385   template<typename _Key, typename _Val, typename _KeyOfValue,
1386            typename _Compare, typename _Alloc>
1387     inline
1388     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
1389                                                                    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
1390     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1391     equal_range(const _Key& __k)
1392     { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1393
1394   template<typename _Key, typename _Val, typename _KoV,
1395            typename _Compare, typename _Alloc>
1396   inline
1397   pair<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator,
1398                                                                 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1399   _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>
1400   ::equal_range(const _Key& __k) const
1401   {
1402     return pair<const_iterator,const_iterator>(lower_bound(__k),
1403                                                upper_bound(__k));
1404   }
1405
1406   inline int
1407   __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
1408   {
1409     if (__node == 0)
1410       return 0;
1411     int __sum = 0;
1412     do
1413       {
1414         if (__node->_M_color == _M_black)
1415           ++__sum;
1416         if (__node == __root)
1417           break;
1418         __node = __node->_M_parent;
1419       }
1420     while (1);
1421     return __sum;
1422   }
1423
1424   template<typename _Key, typename _Val, typename _KeyOfValue,
1425            typename _Compare, typename _Alloc>
1426     bool
1427     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1428     {
1429     if (_M_node_count == 0 || begin() == end())
1430       return _M_node_count == 0 && begin() == end() &&
1431         _M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
1432
1433     int __len = __black_count(_M_leftmost(), _M_root());
1434     for (const_iterator __it = begin(); __it != end(); ++__it)
1435       {
1436         _Link_type __x = (_Link_type) __it._M_node;
1437         _Link_type __L = _S_left(__x);
1438         _Link_type __R = _S_right(__x);
1439
1440         if (__x->_M_color == _M_red)
1441           if ((__L && __L->_M_color == _M_red)
1442               || (__R && __R->_M_color == _M_red))
1443             return false;
1444
1445         if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
1446           return false;
1447         if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
1448           return false;
1449
1450         if (!__L && !__R && __black_count(__x, _M_root()) != __len)
1451           return false;
1452       }
1453
1454     if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1455       return false;
1456     if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1457       return false;
1458     return true;
1459     }
1460 } // namespace std
1461
1462 #endif