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