home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / bits / stl_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  2003-12-15  |  42.8 KB  |  1,463 lines
  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 reverse_iterator<const_iterator> const_reverse_iterator;
  706.       typedef 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 
  1463.