Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. // RB tree implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-2013 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 3, 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. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. /*
  26.  *
  27.  * Copyright (c) 1996,1997
  28.  * Silicon Graphics Computer Systems, Inc.
  29.  *
  30.  * Permission to use, copy, modify, distribute and sell this software
  31.  * and its documentation for any purpose is hereby granted without fee,
  32.  * provided that the above copyright notice appear in all copies and
  33.  * that both that copyright notice and this permission notice appear
  34.  * in supporting documentation.  Silicon Graphics makes no
  35.  * representations about the suitability of this software for any
  36.  * purpose.  It is provided "as is" without express or implied warranty.
  37.  *
  38.  *
  39.  * Copyright (c) 1994
  40.  * Hewlett-Packard Company
  41.  *
  42.  * Permission to use, copy, modify, distribute and sell this software
  43.  * and its documentation for any purpose is hereby granted without fee,
  44.  * provided that the above copyright notice appear in all copies and
  45.  * that both that copyright notice and this permission notice appear
  46.  * in supporting documentation.  Hewlett-Packard Company makes no
  47.  * representations about the suitability of this software for any
  48.  * purpose.  It is provided "as is" without express or implied warranty.
  49.  *
  50.  *
  51.  */
  52.  
  53. /** @file bits/stl_tree.h
  54.  *  This is an internal header file, included by other library headers.
  55.  *  Do not attempt to use it directly. @headername{map,set}
  56.  */
  57.  
  58. #ifndef _STL_TREE_H
  59. #define _STL_TREE_H 1
  60.  
  61. #include <bits/stl_algobase.h>
  62. #include <bits/allocator.h>
  63. #include <bits/stl_function.h>
  64. #include <bits/cpp_type_traits.h>
  65. #if __cplusplus >= 201103L
  66. #include <bits/alloc_traits.h>
  67. #endif
  68.  
  69. namespace std _GLIBCXX_VISIBILITY(default)
  70. {
  71. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  72.  
  73.   // Red-black tree class, designed for use in implementing STL
  74.   // associative containers (set, multiset, map, and multimap). The
  75.   // insertion and deletion algorithms are based on those in Cormen,
  76.   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  77.   // 1990), except that
  78.   //
  79.   // (1) the header cell is maintained with links not only to the root
  80.   // but also to the leftmost node of the tree, to enable constant
  81.   // time begin(), and to the rightmost node of the tree, to enable
  82.   // linear time performance when used with the generic set algorithms
  83.   // (set_union, etc.)
  84.   //
  85.   // (2) when a node being deleted has two children its successor node
  86.   // is relinked into its place, rather than copied, so that the only
  87.   // iterators invalidated are those referring to the deleted node.
  88.  
  89.   enum _Rb_tree_color { _S_red = false, _S_black = true };
  90.  
  91.   struct _Rb_tree_node_base
  92.   {
  93.     typedef _Rb_tree_node_base* _Base_ptr;
  94.     typedef const _Rb_tree_node_base* _Const_Base_ptr;
  95.  
  96.     _Rb_tree_color      _M_color;
  97.     _Base_ptr           _M_parent;
  98.     _Base_ptr           _M_left;
  99.     _Base_ptr           _M_right;
  100.  
  101.     static _Base_ptr
  102.     _S_minimum(_Base_ptr __x)
  103.     {
  104.       while (__x->_M_left != 0) __x = __x->_M_left;
  105.       return __x;
  106.     }
  107.  
  108.     static _Const_Base_ptr
  109.     _S_minimum(_Const_Base_ptr __x)
  110.     {
  111.       while (__x->_M_left != 0) __x = __x->_M_left;
  112.       return __x;
  113.     }
  114.  
  115.     static _Base_ptr
  116.     _S_maximum(_Base_ptr __x)
  117.     {
  118.       while (__x->_M_right != 0) __x = __x->_M_right;
  119.       return __x;
  120.     }
  121.  
  122.     static _Const_Base_ptr
  123.     _S_maximum(_Const_Base_ptr __x)
  124.     {
  125.       while (__x->_M_right != 0) __x = __x->_M_right;
  126.       return __x;
  127.     }
  128.   };
  129.  
  130.   template<typename _Val>
  131.     struct _Rb_tree_node : public _Rb_tree_node_base
  132.     {
  133.       typedef _Rb_tree_node<_Val>* _Link_type;
  134.       _Val _M_value_field;
  135.  
  136. #if __cplusplus >= 201103L
  137.       template<typename... _Args>
  138.         _Rb_tree_node(_Args&&... __args)
  139.         : _Rb_tree_node_base(),
  140.           _M_value_field(std::forward<_Args>(__args)...) { }
  141. #endif
  142.     };
  143.  
  144.   _GLIBCXX_PURE _Rb_tree_node_base*
  145.   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
  146.  
  147.   _GLIBCXX_PURE const _Rb_tree_node_base*
  148.   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
  149.  
  150.   _GLIBCXX_PURE _Rb_tree_node_base*
  151.   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
  152.  
  153.   _GLIBCXX_PURE const _Rb_tree_node_base*
  154.   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
  155.  
  156.   template<typename _Tp>
  157.     struct _Rb_tree_iterator
  158.     {
  159.       typedef _Tp  value_type;
  160.       typedef _Tp& reference;
  161.       typedef _Tp* pointer;
  162.  
  163.       typedef bidirectional_iterator_tag iterator_category;
  164.       typedef ptrdiff_t                  difference_type;
  165.  
  166.       typedef _Rb_tree_iterator<_Tp>        _Self;
  167.       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  168.       typedef _Rb_tree_node<_Tp>*           _Link_type;
  169.  
  170.       _Rb_tree_iterator()
  171.       : _M_node() { }
  172.  
  173.       explicit
  174.       _Rb_tree_iterator(_Link_type __x)
  175.       : _M_node(__x) { }
  176.  
  177.       reference
  178.       operator*() const
  179.       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
  180.  
  181.       pointer
  182.       operator->() const
  183.       { return std::__addressof(static_cast<_Link_type>
  184.                                 (_M_node)->_M_value_field); }
  185.  
  186.       _Self&
  187.       operator++()
  188.       {
  189.         _M_node = _Rb_tree_increment(_M_node);
  190.         return *this;
  191.       }
  192.  
  193.       _Self
  194.       operator++(int)
  195.       {
  196.         _Self __tmp = *this;
  197.         _M_node = _Rb_tree_increment(_M_node);
  198.         return __tmp;
  199.       }
  200.  
  201.       _Self&
  202.       operator--()
  203.       {
  204.         _M_node = _Rb_tree_decrement(_M_node);
  205.         return *this;
  206.       }
  207.  
  208.       _Self
  209.       operator--(int)
  210.       {
  211.         _Self __tmp = *this;
  212.         _M_node = _Rb_tree_decrement(_M_node);
  213.         return __tmp;
  214.       }
  215.  
  216.       bool
  217.       operator==(const _Self& __x) const
  218.       { return _M_node == __x._M_node; }
  219.  
  220.       bool
  221.       operator!=(const _Self& __x) const
  222.       { return _M_node != __x._M_node; }
  223.  
  224.       _Base_ptr _M_node;
  225.   };
  226.  
  227.   template<typename _Tp>
  228.     struct _Rb_tree_const_iterator
  229.     {
  230.       typedef _Tp        value_type;
  231.       typedef const _Tp& reference;
  232.       typedef const _Tp* pointer;
  233.  
  234.       typedef _Rb_tree_iterator<_Tp> iterator;
  235.  
  236.       typedef bidirectional_iterator_tag iterator_category;
  237.       typedef ptrdiff_t                  difference_type;
  238.  
  239.       typedef _Rb_tree_const_iterator<_Tp>        _Self;
  240.       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
  241.       typedef const _Rb_tree_node<_Tp>*           _Link_type;
  242.  
  243.       _Rb_tree_const_iterator()
  244.       : _M_node() { }
  245.  
  246.       explicit
  247.       _Rb_tree_const_iterator(_Link_type __x)
  248.       : _M_node(__x) { }
  249.  
  250.       _Rb_tree_const_iterator(const iterator& __it)
  251.       : _M_node(__it._M_node) { }
  252.  
  253.       iterator
  254.       _M_const_cast() const
  255.       { return iterator(static_cast<typename iterator::_Link_type>
  256.                         (const_cast<typename iterator::_Base_ptr>(_M_node))); }
  257.  
  258.       reference
  259.       operator*() const
  260.       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
  261.  
  262.       pointer
  263.       operator->() const
  264.       { return std::__addressof(static_cast<_Link_type>
  265.                                 (_M_node)->_M_value_field); }
  266.  
  267.       _Self&
  268.       operator++()
  269.       {
  270.         _M_node = _Rb_tree_increment(_M_node);
  271.         return *this;
  272.       }
  273.  
  274.       _Self
  275.       operator++(int)
  276.       {
  277.         _Self __tmp = *this;
  278.         _M_node = _Rb_tree_increment(_M_node);
  279.         return __tmp;
  280.       }
  281.  
  282.       _Self&
  283.       operator--()
  284.       {
  285.         _M_node = _Rb_tree_decrement(_M_node);
  286.         return *this;
  287.       }
  288.  
  289.       _Self
  290.       operator--(int)
  291.       {
  292.         _Self __tmp = *this;
  293.         _M_node = _Rb_tree_decrement(_M_node);
  294.         return __tmp;
  295.       }
  296.  
  297.       bool
  298.       operator==(const _Self& __x) const
  299.       { return _M_node == __x._M_node; }
  300.  
  301.       bool
  302.       operator!=(const _Self& __x) const
  303.       { return _M_node != __x._M_node; }
  304.  
  305.       _Base_ptr _M_node;
  306.     };
  307.  
  308.   template<typename _Val>
  309.     inline bool
  310.     operator==(const _Rb_tree_iterator<_Val>& __x,
  311.                const _Rb_tree_const_iterator<_Val>& __y)
  312.     { return __x._M_node == __y._M_node; }
  313.  
  314.   template<typename _Val>
  315.     inline bool
  316.     operator!=(const _Rb_tree_iterator<_Val>& __x,
  317.                const _Rb_tree_const_iterator<_Val>& __y)
  318.     { return __x._M_node != __y._M_node; }
  319.  
  320.   void
  321.   _Rb_tree_insert_and_rebalance(const bool __insert_left,
  322.                                 _Rb_tree_node_base* __x,
  323.                                 _Rb_tree_node_base* __p,
  324.                                 _Rb_tree_node_base& __header) throw ();
  325.  
  326.   _Rb_tree_node_base*
  327.   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
  328.                                _Rb_tree_node_base& __header) throw ();
  329.  
  330.  
  331.   template<typename _Key, typename _Val, typename _KeyOfValue,
  332.            typename _Compare, typename _Alloc = allocator<_Val> >
  333.     class _Rb_tree
  334.     {
  335.       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
  336.               _Node_allocator;
  337.  
  338.     protected:
  339.       typedef _Rb_tree_node_base*               _Base_ptr;
  340.       typedef const _Rb_tree_node_base*         _Const_Base_ptr;
  341.  
  342.     public:
  343.       typedef _Key                              key_type;
  344.       typedef _Val                              value_type;
  345.       typedef value_type*                       pointer;
  346.       typedef const value_type*                 const_pointer;
  347.       typedef value_type&                       reference;
  348.       typedef const value_type&                 const_reference;
  349.       typedef _Rb_tree_node<_Val>*              _Link_type;
  350.       typedef const _Rb_tree_node<_Val>*        _Const_Link_type;
  351.       typedef size_t                            size_type;
  352.       typedef ptrdiff_t                         difference_type;
  353.       typedef _Alloc                            allocator_type;
  354.  
  355.       _Node_allocator&
  356.       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
  357.       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
  358.      
  359.       const _Node_allocator&
  360.       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
  361.       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
  362.  
  363.       allocator_type
  364.       get_allocator() const _GLIBCXX_NOEXCEPT
  365.       { return allocator_type(_M_get_Node_allocator()); }
  366.  
  367.     protected:
  368.       _Link_type
  369.       _M_get_node()
  370.       { return _M_impl._Node_allocator::allocate(1); }
  371.  
  372.       void
  373.       _M_put_node(_Link_type __p)
  374.       { _M_impl._Node_allocator::deallocate(__p, 1); }
  375.  
  376. #if __cplusplus < 201103L
  377.       _Link_type
  378.       _M_create_node(const value_type& __x)
  379.       {
  380.         _Link_type __tmp = _M_get_node();
  381.         __try
  382.           { get_allocator().construct
  383.               (std::__addressof(__tmp->_M_value_field), __x); }
  384.         __catch(...)
  385.           {
  386.             _M_put_node(__tmp);
  387.             __throw_exception_again;
  388.           }
  389.         return __tmp;
  390.       }
  391.  
  392.       void
  393.       _M_destroy_node(_Link_type __p)
  394.       {
  395.         get_allocator().destroy(std::__addressof(__p->_M_value_field));
  396.         _M_put_node(__p);
  397.       }
  398. #else
  399.       template<typename... _Args>
  400.         _Link_type
  401.         _M_create_node(_Args&&... __args)
  402.         {
  403.           _Link_type __tmp = _M_get_node();
  404.           __try
  405.             {
  406.               allocator_traits<_Node_allocator>::
  407.                 construct(_M_get_Node_allocator(), __tmp,
  408.                           std::forward<_Args>(__args)...);
  409.             }
  410.           __catch(...)
  411.             {
  412.               _M_put_node(__tmp);
  413.               __throw_exception_again;
  414.             }
  415.           return __tmp;
  416.         }
  417.  
  418.       void
  419.       _M_destroy_node(_Link_type __p)
  420.       {
  421.         _M_get_Node_allocator().destroy(__p);
  422.         _M_put_node(__p);
  423.       }
  424. #endif
  425.  
  426.       _Link_type
  427.       _M_clone_node(_Const_Link_type __x)
  428.       {
  429.         _Link_type __tmp = _M_create_node(__x->_M_value_field);
  430.         __tmp->_M_color = __x->_M_color;
  431.         __tmp->_M_left = 0;
  432.         __tmp->_M_right = 0;
  433.         return __tmp;
  434.       }
  435.  
  436.     protected:
  437.       template<typename _Key_compare,
  438.                bool _Is_pod_comparator = __is_pod(_Key_compare)>
  439.         struct _Rb_tree_impl : public _Node_allocator
  440.         {
  441.           _Key_compare          _M_key_compare;
  442.           _Rb_tree_node_base    _M_header;
  443.           size_type             _M_node_count; // Keeps track of size of tree.
  444.  
  445.           _Rb_tree_impl()
  446.           : _Node_allocator(), _M_key_compare(), _M_header(),
  447.             _M_node_count(0)
  448.           { _M_initialize(); }
  449.  
  450.           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
  451.           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
  452.             _M_node_count(0)
  453.           { _M_initialize(); }
  454.  
  455. #if __cplusplus >= 201103L
  456.           _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
  457.           : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
  458.             _M_header(), _M_node_count(0)
  459.           { _M_initialize(); }
  460. #endif
  461.  
  462.         private:
  463.           void
  464.           _M_initialize()
  465.           {
  466.             this->_M_header._M_color = _S_red;
  467.             this->_M_header._M_parent = 0;
  468.             this->_M_header._M_left = &this->_M_header;
  469.             this->_M_header._M_right = &this->_M_header;
  470.           }        
  471.         };
  472.  
  473.       _Rb_tree_impl<_Compare> _M_impl;
  474.  
  475.     protected:
  476.       _Base_ptr&
  477.       _M_root()
  478.       { return this->_M_impl._M_header._M_parent; }
  479.  
  480.       _Const_Base_ptr
  481.       _M_root() const
  482.       { return this->_M_impl._M_header._M_parent; }
  483.  
  484.       _Base_ptr&
  485.       _M_leftmost()
  486.       { return this->_M_impl._M_header._M_left; }
  487.  
  488.       _Const_Base_ptr
  489.       _M_leftmost() const
  490.       { return this->_M_impl._M_header._M_left; }
  491.  
  492.       _Base_ptr&
  493.       _M_rightmost()
  494.       { return this->_M_impl._M_header._M_right; }
  495.  
  496.       _Const_Base_ptr
  497.       _M_rightmost() const
  498.       { return this->_M_impl._M_header._M_right; }
  499.  
  500.       _Link_type
  501.       _M_begin()
  502.       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
  503.  
  504.       _Const_Link_type
  505.       _M_begin() const
  506.       {
  507.         return static_cast<_Const_Link_type>
  508.           (this->_M_impl._M_header._M_parent);
  509.       }
  510.  
  511.       _Link_type
  512.       _M_end()
  513.       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
  514.  
  515.       _Const_Link_type
  516.       _M_end() const
  517.       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
  518.  
  519.       static const_reference
  520.       _S_value(_Const_Link_type __x)
  521.       { return __x->_M_value_field; }
  522.  
  523.       static const _Key&
  524.       _S_key(_Const_Link_type __x)
  525.       { return _KeyOfValue()(_S_value(__x)); }
  526.  
  527.       static _Link_type
  528.       _S_left(_Base_ptr __x)
  529.       { return static_cast<_Link_type>(__x->_M_left); }
  530.  
  531.       static _Const_Link_type
  532.       _S_left(_Const_Base_ptr __x)
  533.       { return static_cast<_Const_Link_type>(__x->_M_left); }
  534.  
  535.       static _Link_type
  536.       _S_right(_Base_ptr __x)
  537.       { return static_cast<_Link_type>(__x->_M_right); }
  538.  
  539.       static _Const_Link_type
  540.       _S_right(_Const_Base_ptr __x)
  541.       { return static_cast<_Const_Link_type>(__x->_M_right); }
  542.  
  543.       static const_reference
  544.       _S_value(_Const_Base_ptr __x)
  545.       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
  546.  
  547.       static const _Key&
  548.       _S_key(_Const_Base_ptr __x)
  549.       { return _KeyOfValue()(_S_value(__x)); }
  550.  
  551.       static _Base_ptr
  552.       _S_minimum(_Base_ptr __x)
  553.       { return _Rb_tree_node_base::_S_minimum(__x); }
  554.  
  555.       static _Const_Base_ptr
  556.       _S_minimum(_Const_Base_ptr __x)
  557.       { return _Rb_tree_node_base::_S_minimum(__x); }
  558.  
  559.       static _Base_ptr
  560.       _S_maximum(_Base_ptr __x)
  561.       { return _Rb_tree_node_base::_S_maximum(__x); }
  562.  
  563.       static _Const_Base_ptr
  564.       _S_maximum(_Const_Base_ptr __x)
  565.       { return _Rb_tree_node_base::_S_maximum(__x); }
  566.  
  567.     public:
  568.       typedef _Rb_tree_iterator<value_type>       iterator;
  569.       typedef _Rb_tree_const_iterator<value_type> const_iterator;
  570.  
  571.       typedef std::reverse_iterator<iterator>       reverse_iterator;
  572.       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  573.  
  574.     private:
  575.       pair<_Base_ptr, _Base_ptr>
  576.       _M_get_insert_unique_pos(const key_type& __k);
  577.  
  578.       pair<_Base_ptr, _Base_ptr>
  579.       _M_get_insert_equal_pos(const key_type& __k);
  580.  
  581.       pair<_Base_ptr, _Base_ptr>
  582.       _M_get_insert_hint_unique_pos(const_iterator __pos,
  583.                                     const key_type& __k);
  584.  
  585.       pair<_Base_ptr, _Base_ptr>
  586.       _M_get_insert_hint_equal_pos(const_iterator __pos,
  587.                                    const key_type& __k);
  588.  
  589. #if __cplusplus >= 201103L
  590.       template<typename _Arg>
  591.         iterator
  592.         _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
  593.  
  594.       iterator
  595.       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
  596.  
  597.       template<typename _Arg>
  598.         iterator
  599.         _M_insert_lower(_Base_ptr __y, _Arg&& __v);
  600.  
  601.       template<typename _Arg>
  602.         iterator
  603.         _M_insert_equal_lower(_Arg&& __x);
  604.  
  605.       iterator
  606.       _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
  607.  
  608.       iterator
  609.       _M_insert_equal_lower_node(_Link_type __z);
  610. #else
  611.       iterator
  612.       _M_insert_(_Base_ptr __x, _Base_ptr __y,
  613.                  const value_type& __v);
  614.  
  615.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  616.       // 233. Insertion hints in associative containers.
  617.       iterator
  618.       _M_insert_lower(_Base_ptr __y, const value_type& __v);
  619.  
  620.       iterator
  621.       _M_insert_equal_lower(const value_type& __x);
  622. #endif
  623.  
  624.       _Link_type
  625.       _M_copy(_Const_Link_type __x, _Link_type __p);
  626.  
  627.       void
  628.       _M_erase(_Link_type __x);
  629.  
  630.       iterator
  631.       _M_lower_bound(_Link_type __x, _Link_type __y,
  632.                      const _Key& __k);
  633.  
  634.       const_iterator
  635.       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
  636.                      const _Key& __k) const;
  637.  
  638.       iterator
  639.       _M_upper_bound(_Link_type __x, _Link_type __y,
  640.                      const _Key& __k);
  641.  
  642.       const_iterator
  643.       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
  644.                      const _Key& __k) const;
  645.  
  646.     public:
  647.       // allocation/deallocation
  648.       _Rb_tree() { }
  649.  
  650.       _Rb_tree(const _Compare& __comp,
  651.                const allocator_type& __a = allocator_type())
  652.       : _M_impl(__comp, _Node_allocator(__a)) { }
  653.  
  654.       _Rb_tree(const _Rb_tree& __x)
  655.       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
  656.       {
  657.         if (__x._M_root() != 0)
  658.           {
  659.             _M_root() = _M_copy(__x._M_begin(), _M_end());
  660.             _M_leftmost() = _S_minimum(_M_root());
  661.             _M_rightmost() = _S_maximum(_M_root());
  662.             _M_impl._M_node_count = __x._M_impl._M_node_count;
  663.           }
  664.       }
  665.  
  666. #if __cplusplus >= 201103L
  667.       _Rb_tree(_Rb_tree&& __x);
  668. #endif
  669.  
  670.       ~_Rb_tree() _GLIBCXX_NOEXCEPT
  671.       { _M_erase(_M_begin()); }
  672.  
  673.       _Rb_tree&
  674.       operator=(const _Rb_tree& __x);
  675.  
  676.       // Accessors.
  677.       _Compare
  678.       key_comp() const
  679.       { return _M_impl._M_key_compare; }
  680.  
  681.       iterator
  682.       begin() _GLIBCXX_NOEXCEPT
  683.       {
  684.         return iterator(static_cast<_Link_type>
  685.                         (this->_M_impl._M_header._M_left));
  686.       }
  687.  
  688.       const_iterator
  689.       begin() const _GLIBCXX_NOEXCEPT
  690.       {
  691.         return const_iterator(static_cast<_Const_Link_type>
  692.                               (this->_M_impl._M_header._M_left));
  693.       }
  694.  
  695.       iterator
  696.       end() _GLIBCXX_NOEXCEPT
  697.       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
  698.  
  699.       const_iterator
  700.       end() const _GLIBCXX_NOEXCEPT
  701.       {
  702.         return const_iterator(static_cast<_Const_Link_type>
  703.                               (&this->_M_impl._M_header));
  704.       }
  705.  
  706.       reverse_iterator
  707.       rbegin() _GLIBCXX_NOEXCEPT
  708.       { return reverse_iterator(end()); }
  709.  
  710.       const_reverse_iterator
  711.       rbegin() const _GLIBCXX_NOEXCEPT
  712.       { return const_reverse_iterator(end()); }
  713.  
  714.       reverse_iterator
  715.       rend() _GLIBCXX_NOEXCEPT
  716.       { return reverse_iterator(begin()); }
  717.  
  718.       const_reverse_iterator
  719.       rend() const _GLIBCXX_NOEXCEPT
  720.       { return const_reverse_iterator(begin()); }
  721.  
  722.       bool
  723.       empty() const _GLIBCXX_NOEXCEPT
  724.       { return _M_impl._M_node_count == 0; }
  725.  
  726.       size_type
  727.       size() const _GLIBCXX_NOEXCEPT
  728.       { return _M_impl._M_node_count; }
  729.  
  730.       size_type
  731.       max_size() const _GLIBCXX_NOEXCEPT
  732.       { return _M_get_Node_allocator().max_size(); }
  733.  
  734.       void
  735.       swap(_Rb_tree& __t);      
  736.  
  737.       // Insert/erase.
  738. #if __cplusplus >= 201103L
  739.       template<typename _Arg>
  740.         pair<iterator, bool>
  741.         _M_insert_unique(_Arg&& __x);
  742.  
  743.       template<typename _Arg>
  744.         iterator
  745.         _M_insert_equal(_Arg&& __x);
  746.  
  747.       template<typename _Arg>
  748.         iterator
  749.         _M_insert_unique_(const_iterator __position, _Arg&& __x);
  750.  
  751.       template<typename _Arg>
  752.         iterator
  753.         _M_insert_equal_(const_iterator __position, _Arg&& __x);
  754.  
  755.       template<typename... _Args>
  756.         pair<iterator, bool>
  757.         _M_emplace_unique(_Args&&... __args);
  758.  
  759.       template<typename... _Args>
  760.         iterator
  761.         _M_emplace_equal(_Args&&... __args);
  762.  
  763.       template<typename... _Args>
  764.         iterator
  765.         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
  766.  
  767.       template<typename... _Args>
  768.         iterator
  769.         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
  770. #else
  771.       pair<iterator, bool>
  772.       _M_insert_unique(const value_type& __x);
  773.  
  774.       iterator
  775.       _M_insert_equal(const value_type& __x);
  776.  
  777.       iterator
  778.       _M_insert_unique_(const_iterator __position, const value_type& __x);
  779.  
  780.       iterator
  781.       _M_insert_equal_(const_iterator __position, const value_type& __x);
  782. #endif
  783.  
  784.       template<typename _InputIterator>
  785.         void
  786.         _M_insert_unique(_InputIterator __first, _InputIterator __last);
  787.  
  788.       template<typename _InputIterator>
  789.         void
  790.         _M_insert_equal(_InputIterator __first, _InputIterator __last);
  791.  
  792.     private:
  793.       void
  794.       _M_erase_aux(const_iterator __position);
  795.  
  796.       void
  797.       _M_erase_aux(const_iterator __first, const_iterator __last);
  798.  
  799.     public:
  800. #if __cplusplus >= 201103L
  801.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  802.       // DR 130. Associative erase should return an iterator.
  803.       _GLIBCXX_ABI_TAG_CXX11
  804.       iterator
  805.       erase(const_iterator __position)
  806.       {
  807.         const_iterator __result = __position;
  808.         ++__result;
  809.         _M_erase_aux(__position);
  810.         return __result._M_const_cast();
  811.       }
  812.  
  813.       // LWG 2059.
  814.       _GLIBCXX_ABI_TAG_CXX11
  815.       iterator
  816.       erase(iterator __position)
  817.       {
  818.         iterator __result = __position;
  819.         ++__result;
  820.         _M_erase_aux(__position);
  821.         return __result;
  822.       }
  823. #else
  824.       void
  825.       erase(iterator __position)
  826.       { _M_erase_aux(__position); }
  827.  
  828.       void
  829.       erase(const_iterator __position)
  830.       { _M_erase_aux(__position); }
  831. #endif
  832.       size_type
  833.       erase(const key_type& __x);
  834.  
  835. #if __cplusplus >= 201103L
  836.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  837.       // DR 130. Associative erase should return an iterator.
  838.       _GLIBCXX_ABI_TAG_CXX11
  839.       iterator
  840.       erase(const_iterator __first, const_iterator __last)
  841.       {
  842.         _M_erase_aux(__first, __last);
  843.         return __last._M_const_cast();
  844.       }
  845. #else
  846.       void
  847.       erase(iterator __first, iterator __last)
  848.       { _M_erase_aux(__first, __last); }
  849.  
  850.       void
  851.       erase(const_iterator __first, const_iterator __last)
  852.       { _M_erase_aux(__first, __last); }
  853. #endif
  854.       void
  855.       erase(const key_type* __first, const key_type* __last);
  856.  
  857.       void
  858.       clear() _GLIBCXX_NOEXCEPT
  859.       {
  860.         _M_erase(_M_begin());
  861.         _M_leftmost() = _M_end();
  862.         _M_root() = 0;
  863.         _M_rightmost() = _M_end();
  864.         _M_impl._M_node_count = 0;
  865.       }
  866.  
  867.       // Set operations.
  868.       iterator
  869.       find(const key_type& __k);
  870.  
  871.       const_iterator
  872.       find(const key_type& __k) const;
  873.  
  874.       size_type
  875.       count(const key_type& __k) const;
  876.  
  877.       iterator
  878.       lower_bound(const key_type& __k)
  879.       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
  880.  
  881.       const_iterator
  882.       lower_bound(const key_type& __k) const
  883.       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
  884.  
  885.       iterator
  886.       upper_bound(const key_type& __k)
  887.       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
  888.  
  889.       const_iterator
  890.       upper_bound(const key_type& __k) const
  891.       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
  892.  
  893.       pair<iterator, iterator>
  894.       equal_range(const key_type& __k);
  895.  
  896.       pair<const_iterator, const_iterator>
  897.       equal_range(const key_type& __k) const;
  898.  
  899.       // Debugging.
  900.       bool
  901.       __rb_verify() const;
  902.     };
  903.  
  904.   template<typename _Key, typename _Val, typename _KeyOfValue,
  905.            typename _Compare, typename _Alloc>
  906.     inline bool
  907.     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  908.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  909.     {
  910.       return __x.size() == __y.size()
  911.              && std::equal(__x.begin(), __x.end(), __y.begin());
  912.     }
  913.  
  914.   template<typename _Key, typename _Val, typename _KeyOfValue,
  915.            typename _Compare, typename _Alloc>
  916.     inline bool
  917.     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  918.               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  919.     {
  920.       return std::lexicographical_compare(__x.begin(), __x.end(),
  921.                                           __y.begin(), __y.end());
  922.     }
  923.  
  924.   template<typename _Key, typename _Val, typename _KeyOfValue,
  925.            typename _Compare, typename _Alloc>
  926.     inline bool
  927.     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  928.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  929.     { return !(__x == __y); }
  930.  
  931.   template<typename _Key, typename _Val, typename _KeyOfValue,
  932.            typename _Compare, typename _Alloc>
  933.     inline bool
  934.     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  935.               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  936.     { return __y < __x; }
  937.  
  938.   template<typename _Key, typename _Val, typename _KeyOfValue,
  939.            typename _Compare, typename _Alloc>
  940.     inline bool
  941.     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  942.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  943.     { return !(__y < __x); }
  944.  
  945.   template<typename _Key, typename _Val, typename _KeyOfValue,
  946.            typename _Compare, typename _Alloc>
  947.     inline bool
  948.     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  949.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  950.     { return !(__x < __y); }
  951.  
  952.   template<typename _Key, typename _Val, typename _KeyOfValue,
  953.            typename _Compare, typename _Alloc>
  954.     inline void
  955.     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  956.          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  957.     { __x.swap(__y); }
  958.  
  959. #if __cplusplus >= 201103L
  960.   template<typename _Key, typename _Val, typename _KeyOfValue,
  961.            typename _Compare, typename _Alloc>
  962.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  963.     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
  964.     : _M_impl(__x._M_impl._M_key_compare,
  965.               std::move(__x._M_get_Node_allocator()))
  966.     {
  967.       if (__x._M_root() != 0)
  968.         {
  969.           _M_root() = __x._M_root();
  970.           _M_leftmost() = __x._M_leftmost();
  971.           _M_rightmost() = __x._M_rightmost();
  972.           _M_root()->_M_parent = _M_end();
  973.  
  974.           __x._M_root() = 0;
  975.           __x._M_leftmost() = __x._M_end();
  976.           __x._M_rightmost() = __x._M_end();
  977.  
  978.           this->_M_impl._M_node_count = __x._M_impl._M_node_count;
  979.           __x._M_impl._M_node_count = 0;
  980.         }
  981.     }
  982. #endif
  983.  
  984.   template<typename _Key, typename _Val, typename _KeyOfValue,
  985.            typename _Compare, typename _Alloc>
  986.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
  987.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  988.     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
  989.     {
  990.       if (this != &__x)
  991.         {
  992.           // Note that _Key may be a constant type.
  993.           clear();
  994.           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
  995.           if (__x._M_root() != 0)
  996.             {
  997.               _M_root() = _M_copy(__x._M_begin(), _M_end());
  998.               _M_leftmost() = _S_minimum(_M_root());
  999.               _M_rightmost() = _S_maximum(_M_root());
  1000.               _M_impl._M_node_count = __x._M_impl._M_node_count;
  1001.             }
  1002.         }
  1003.       return *this;
  1004.     }
  1005.  
  1006.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1007.            typename _Compare, typename _Alloc>
  1008. #if __cplusplus >= 201103L
  1009.     template<typename _Arg>
  1010. #endif
  1011.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1012.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1013. #if __cplusplus >= 201103L
  1014.     _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
  1015. #else
  1016.     _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
  1017. #endif
  1018.     {
  1019.       bool __insert_left = (__x != 0 || __p == _M_end()
  1020.                             || _M_impl._M_key_compare(_KeyOfValue()(__v),
  1021.                                                       _S_key(__p)));
  1022.  
  1023.       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
  1024.  
  1025.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  1026.                                     this->_M_impl._M_header);
  1027.       ++_M_impl._M_node_count;
  1028.       return iterator(__z);
  1029.     }
  1030.  
  1031.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1032.            typename _Compare, typename _Alloc>
  1033. #if __cplusplus >= 201103L
  1034.     template<typename _Arg>
  1035. #endif
  1036.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1037.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1038. #if __cplusplus >= 201103L
  1039.     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
  1040. #else
  1041.     _M_insert_lower(_Base_ptr __p, const _Val& __v)
  1042. #endif
  1043.     {
  1044.       bool __insert_left = (__p == _M_end()
  1045.                             || !_M_impl._M_key_compare(_S_key(__p),
  1046.                                                        _KeyOfValue()(__v)));
  1047.  
  1048.       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
  1049.  
  1050.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  1051.                                     this->_M_impl._M_header);
  1052.       ++_M_impl._M_node_count;
  1053.       return iterator(__z);
  1054.     }
  1055.  
  1056.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1057.            typename _Compare, typename _Alloc>
  1058. #if __cplusplus >= 201103L
  1059.     template<typename _Arg>
  1060. #endif
  1061.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1062.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1063. #if __cplusplus >= 201103L
  1064.     _M_insert_equal_lower(_Arg&& __v)
  1065. #else
  1066.     _M_insert_equal_lower(const _Val& __v)
  1067. #endif
  1068.     {
  1069.       _Link_type __x = _M_begin();
  1070.       _Link_type __y = _M_end();
  1071.       while (__x != 0)
  1072.         {
  1073.           __y = __x;
  1074.           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
  1075.                 _S_left(__x) : _S_right(__x);
  1076.         }
  1077.       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
  1078.     }
  1079.  
  1080.   template<typename _Key, typename _Val, typename _KoV,
  1081.            typename _Compare, typename _Alloc>
  1082.     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
  1083.     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
  1084.     _M_copy(_Const_Link_type __x, _Link_type __p)
  1085.     {
  1086.       // Structural copy.  __x and __p must be non-null.
  1087.       _Link_type __top = _M_clone_node(__x);
  1088.       __top->_M_parent = __p;
  1089.  
  1090.       __try
  1091.         {
  1092.           if (__x->_M_right)
  1093.             __top->_M_right = _M_copy(_S_right(__x), __top);
  1094.           __p = __top;
  1095.           __x = _S_left(__x);
  1096.  
  1097.           while (__x != 0)
  1098.             {
  1099.               _Link_type __y = _M_clone_node(__x);
  1100.               __p->_M_left = __y;
  1101.               __y->_M_parent = __p;
  1102.               if (__x->_M_right)
  1103.                 __y->_M_right = _M_copy(_S_right(__x), __y);
  1104.               __p = __y;
  1105.               __x = _S_left(__x);
  1106.             }
  1107.         }
  1108.       __catch(...)
  1109.         {
  1110.           _M_erase(__top);
  1111.           __throw_exception_again;
  1112.         }
  1113.       return __top;
  1114.     }
  1115.  
  1116.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1117.            typename _Compare, typename _Alloc>
  1118.     void
  1119.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1120.     _M_erase(_Link_type __x)
  1121.     {
  1122.       // Erase without rebalancing.
  1123.       while (__x != 0)
  1124.         {
  1125.           _M_erase(_S_right(__x));
  1126.           _Link_type __y = _S_left(__x);
  1127.           _M_destroy_node(__x);
  1128.           __x = __y;
  1129.         }
  1130.     }
  1131.  
  1132.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1133.            typename _Compare, typename _Alloc>
  1134.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1135.                       _Compare, _Alloc>::iterator
  1136.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1137.     _M_lower_bound(_Link_type __x, _Link_type __y,
  1138.                    const _Key& __k)
  1139.     {
  1140.       while (__x != 0)
  1141.         if (!_M_impl._M_key_compare(_S_key(__x), __k))
  1142.           __y = __x, __x = _S_left(__x);
  1143.         else
  1144.           __x = _S_right(__x);
  1145.       return iterator(__y);
  1146.     }
  1147.  
  1148.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1149.            typename _Compare, typename _Alloc>
  1150.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1151.                       _Compare, _Alloc>::const_iterator
  1152.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1153.     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
  1154.                    const _Key& __k) const
  1155.     {
  1156.       while (__x != 0)
  1157.         if (!_M_impl._M_key_compare(_S_key(__x), __k))
  1158.           __y = __x, __x = _S_left(__x);
  1159.         else
  1160.           __x = _S_right(__x);
  1161.       return const_iterator(__y);
  1162.     }
  1163.  
  1164.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1165.            typename _Compare, typename _Alloc>
  1166.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1167.                       _Compare, _Alloc>::iterator
  1168.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1169.     _M_upper_bound(_Link_type __x, _Link_type __y,
  1170.                    const _Key& __k)
  1171.     {
  1172.       while (__x != 0)
  1173.         if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1174.           __y = __x, __x = _S_left(__x);
  1175.         else
  1176.           __x = _S_right(__x);
  1177.       return iterator(__y);
  1178.     }
  1179.  
  1180.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1181.            typename _Compare, typename _Alloc>
  1182.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1183.                       _Compare, _Alloc>::const_iterator
  1184.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1185.     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
  1186.                    const _Key& __k) const
  1187.     {
  1188.       while (__x != 0)
  1189.         if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1190.           __y = __x, __x = _S_left(__x);
  1191.         else
  1192.           __x = _S_right(__x);
  1193.       return const_iterator(__y);
  1194.     }
  1195.  
  1196.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1197.            typename _Compare, typename _Alloc>
  1198.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1199.                            _Compare, _Alloc>::iterator,
  1200.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1201.                            _Compare, _Alloc>::iterator>
  1202.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1203.     equal_range(const _Key& __k)
  1204.     {
  1205.       _Link_type __x = _M_begin();
  1206.       _Link_type __y = _M_end();
  1207.       while (__x != 0)
  1208.         {
  1209.           if (_M_impl._M_key_compare(_S_key(__x), __k))
  1210.             __x = _S_right(__x);
  1211.           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1212.             __y = __x, __x = _S_left(__x);
  1213.           else
  1214.             {
  1215.               _Link_type __xu(__x), __yu(__y);
  1216.               __y = __x, __x = _S_left(__x);
  1217.               __xu = _S_right(__xu);
  1218.               return pair<iterator,
  1219.                           iterator>(_M_lower_bound(__x, __y, __k),
  1220.                                     _M_upper_bound(__xu, __yu, __k));
  1221.             }
  1222.         }
  1223.       return pair<iterator, iterator>(iterator(__y),
  1224.                                       iterator(__y));
  1225.     }
  1226.  
  1227.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1228.            typename _Compare, typename _Alloc>
  1229.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1230.                            _Compare, _Alloc>::const_iterator,
  1231.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1232.                            _Compare, _Alloc>::const_iterator>
  1233.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1234.     equal_range(const _Key& __k) const
  1235.     {
  1236.       _Const_Link_type __x = _M_begin();
  1237.       _Const_Link_type __y = _M_end();
  1238.       while (__x != 0)
  1239.         {
  1240.           if (_M_impl._M_key_compare(_S_key(__x), __k))
  1241.             __x = _S_right(__x);
  1242.           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1243.             __y = __x, __x = _S_left(__x);
  1244.           else
  1245.             {
  1246.               _Const_Link_type __xu(__x), __yu(__y);
  1247.               __y = __x, __x = _S_left(__x);
  1248.               __xu = _S_right(__xu);
  1249.               return pair<const_iterator,
  1250.                           const_iterator>(_M_lower_bound(__x, __y, __k),
  1251.                                           _M_upper_bound(__xu, __yu, __k));
  1252.             }
  1253.         }
  1254.       return pair<const_iterator, const_iterator>(const_iterator(__y),
  1255.                                                   const_iterator(__y));
  1256.     }
  1257.  
  1258.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1259.            typename _Compare, typename _Alloc>
  1260.     void
  1261.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1262.     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
  1263.     {
  1264.       if (_M_root() == 0)
  1265.         {
  1266.           if (__t._M_root() != 0)
  1267.             {
  1268.               _M_root() = __t._M_root();
  1269.               _M_leftmost() = __t._M_leftmost();
  1270.               _M_rightmost() = __t._M_rightmost();
  1271.               _M_root()->_M_parent = _M_end();
  1272.              
  1273.               __t._M_root() = 0;
  1274.               __t._M_leftmost() = __t._M_end();
  1275.               __t._M_rightmost() = __t._M_end();
  1276.             }
  1277.         }
  1278.       else if (__t._M_root() == 0)
  1279.         {
  1280.           __t._M_root() = _M_root();
  1281.           __t._M_leftmost() = _M_leftmost();
  1282.           __t._M_rightmost() = _M_rightmost();
  1283.           __t._M_root()->_M_parent = __t._M_end();
  1284.          
  1285.           _M_root() = 0;
  1286.           _M_leftmost() = _M_end();
  1287.           _M_rightmost() = _M_end();
  1288.         }
  1289.       else
  1290.         {
  1291.           std::swap(_M_root(),__t._M_root());
  1292.           std::swap(_M_leftmost(),__t._M_leftmost());
  1293.           std::swap(_M_rightmost(),__t._M_rightmost());
  1294.          
  1295.           _M_root()->_M_parent = _M_end();
  1296.           __t._M_root()->_M_parent = __t._M_end();
  1297.         }
  1298.       // No need to swap header's color as it does not change.
  1299.       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
  1300.       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
  1301.      
  1302.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1303.       // 431. Swapping containers with unequal allocators.
  1304.       std::__alloc_swap<_Node_allocator>::
  1305.         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
  1306.     }
  1307.  
  1308.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1309.            typename _Compare, typename _Alloc>
  1310.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1311.                            _Compare, _Alloc>::_Base_ptr,
  1312.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1313.                            _Compare, _Alloc>::_Base_ptr>
  1314.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1315.     _M_get_insert_unique_pos(const key_type& __k)
  1316.     {
  1317.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1318.       _Link_type __x = _M_begin();
  1319.       _Link_type __y = _M_end();
  1320.       bool __comp = true;
  1321.       while (__x != 0)
  1322.         {
  1323.           __y = __x;
  1324.           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
  1325.           __x = __comp ? _S_left(__x) : _S_right(__x);
  1326.         }
  1327.       iterator __j = iterator(__y);
  1328.       if (__comp)
  1329.         {
  1330.           if (__j == begin())
  1331.             return _Res(__x, __y);
  1332.           else
  1333.             --__j;
  1334.         }
  1335.       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
  1336.         return _Res(__x, __y);
  1337.       return _Res(__j._M_node, 0);
  1338.     }
  1339.  
  1340.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1341.            typename _Compare, typename _Alloc>
  1342.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1343.                            _Compare, _Alloc>::_Base_ptr,
  1344.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1345.                            _Compare, _Alloc>::_Base_ptr>
  1346.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1347.     _M_get_insert_equal_pos(const key_type& __k)
  1348.     {
  1349.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1350.       _Link_type __x = _M_begin();
  1351.       _Link_type __y = _M_end();
  1352.       while (__x != 0)
  1353.         {
  1354.           __y = __x;
  1355.           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
  1356.                 _S_left(__x) : _S_right(__x);
  1357.         }
  1358.       return _Res(__x, __y);
  1359.     }
  1360.  
  1361.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1362.            typename _Compare, typename _Alloc>
  1363. #if __cplusplus >= 201103L
  1364.     template<typename _Arg>
  1365. #endif
  1366.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1367.                            _Compare, _Alloc>::iterator, bool>
  1368.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1369. #if __cplusplus >= 201103L
  1370.     _M_insert_unique(_Arg&& __v)
  1371. #else
  1372.     _M_insert_unique(const _Val& __v)
  1373. #endif
  1374.     {
  1375.       typedef pair<iterator, bool> _Res;
  1376.       pair<_Base_ptr, _Base_ptr> __res
  1377.         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
  1378.  
  1379.       if (__res.second)
  1380.         return _Res(_M_insert_(__res.first, __res.second,
  1381.                                _GLIBCXX_FORWARD(_Arg, __v)),
  1382.                     true);
  1383.  
  1384.       return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
  1385.     }
  1386.  
  1387.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1388.            typename _Compare, typename _Alloc>
  1389. #if __cplusplus >= 201103L
  1390.     template<typename _Arg>
  1391. #endif
  1392.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1393.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1394. #if __cplusplus >= 201103L
  1395.     _M_insert_equal(_Arg&& __v)
  1396. #else
  1397.     _M_insert_equal(const _Val& __v)
  1398. #endif
  1399.     {
  1400.       pair<_Base_ptr, _Base_ptr> __res
  1401.         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
  1402.       return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
  1403.     }
  1404.  
  1405.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1406.            typename _Compare, typename _Alloc>
  1407.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1408.                            _Compare, _Alloc>::_Base_ptr,
  1409.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1410.                            _Compare, _Alloc>::_Base_ptr>
  1411.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1412.     _M_get_insert_hint_unique_pos(const_iterator __position,
  1413.                                   const key_type& __k)
  1414.     {
  1415.       iterator __pos = __position._M_const_cast();
  1416.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1417.  
  1418.       // end()
  1419.       if (__pos._M_node == _M_end())
  1420.         {
  1421.           if (size() > 0
  1422.               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
  1423.             return _Res(0, _M_rightmost());
  1424.           else
  1425.             return _M_get_insert_unique_pos(__k);
  1426.         }
  1427.       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
  1428.         {
  1429.           // First, try before...
  1430.           iterator __before = __pos;
  1431.           if (__pos._M_node == _M_leftmost()) // begin()
  1432.             return _Res(_M_leftmost(), _M_leftmost());
  1433.           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
  1434.             {
  1435.               if (_S_right(__before._M_node) == 0)
  1436.                 return _Res(0, __before._M_node);
  1437.               else
  1438.                 return _Res(__pos._M_node, __pos._M_node);
  1439.             }
  1440.           else
  1441.             return _M_get_insert_unique_pos(__k);
  1442.         }
  1443.       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
  1444.         {
  1445.           // ... then try after.
  1446.           iterator __after = __pos;
  1447.           if (__pos._M_node == _M_rightmost())
  1448.             return _Res(0, _M_rightmost());
  1449.           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
  1450.             {
  1451.               if (_S_right(__pos._M_node) == 0)
  1452.                 return _Res(0, __pos._M_node);
  1453.               else
  1454.                 return _Res(__after._M_node, __after._M_node);
  1455.             }
  1456.           else
  1457.             return _M_get_insert_unique_pos(__k);
  1458.         }
  1459.       else
  1460.         // Equivalent keys.
  1461.         return _Res(__pos._M_node, 0);
  1462.     }
  1463.  
  1464.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1465.            typename _Compare, typename _Alloc>
  1466. #if __cplusplus >= 201103L
  1467.     template<typename _Arg>
  1468. #endif
  1469.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1470.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1471. #if __cplusplus >= 201103L
  1472.     _M_insert_unique_(const_iterator __position, _Arg&& __v)
  1473. #else
  1474.     _M_insert_unique_(const_iterator __position, const _Val& __v)
  1475. #endif
  1476.     {
  1477.       pair<_Base_ptr, _Base_ptr> __res
  1478.         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
  1479.  
  1480.       if (__res.second)
  1481.         return _M_insert_(__res.first, __res.second,
  1482.                           _GLIBCXX_FORWARD(_Arg, __v));
  1483.       return iterator(static_cast<_Link_type>(__res.first));
  1484.     }
  1485.  
  1486.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1487.            typename _Compare, typename _Alloc>
  1488.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1489.                            _Compare, _Alloc>::_Base_ptr,
  1490.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1491.                            _Compare, _Alloc>::_Base_ptr>
  1492.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1493.     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
  1494.     {
  1495.       iterator __pos = __position._M_const_cast();
  1496.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1497.  
  1498.       // end()
  1499.       if (__pos._M_node == _M_end())
  1500.         {
  1501.           if (size() > 0
  1502.               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
  1503.             return _Res(0, _M_rightmost());
  1504.           else
  1505.             return _M_get_insert_equal_pos(__k);
  1506.         }
  1507.       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
  1508.         {
  1509.           // First, try before...
  1510.           iterator __before = __pos;
  1511.           if (__pos._M_node == _M_leftmost()) // begin()
  1512.             return _Res(_M_leftmost(), _M_leftmost());
  1513.           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
  1514.             {
  1515.               if (_S_right(__before._M_node) == 0)
  1516.                 return _Res(0, __before._M_node);
  1517.               else
  1518.                 return _Res(__pos._M_node, __pos._M_node);
  1519.             }
  1520.           else
  1521.             return _M_get_insert_equal_pos(__k);
  1522.         }
  1523.       else
  1524.         {
  1525.           // ... then try after.  
  1526.           iterator __after = __pos;
  1527.           if (__pos._M_node == _M_rightmost())
  1528.             return _Res(0, _M_rightmost());
  1529.           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
  1530.             {
  1531.               if (_S_right(__pos._M_node) == 0)
  1532.                 return _Res(0, __pos._M_node);
  1533.               else
  1534.                 return _Res(__after._M_node, __after._M_node);
  1535.             }
  1536.           else
  1537.             return _Res(0, 0);
  1538.         }
  1539.     }
  1540.  
  1541.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1542.            typename _Compare, typename _Alloc>
  1543. #if __cplusplus >= 201103L
  1544.     template<typename _Arg>
  1545. #endif
  1546.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1547.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1548. #if __cplusplus >= 201103L
  1549.     _M_insert_equal_(const_iterator __position, _Arg&& __v)
  1550. #else
  1551.     _M_insert_equal_(const_iterator __position, const _Val& __v)
  1552. #endif
  1553.     {
  1554.       pair<_Base_ptr, _Base_ptr> __res
  1555.         = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
  1556.  
  1557.       if (__res.second)
  1558.         return _M_insert_(__res.first, __res.second,
  1559.                           _GLIBCXX_FORWARD(_Arg, __v));
  1560.  
  1561.       return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
  1562.     }
  1563.  
  1564. #if __cplusplus >= 201103L
  1565.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1566.            typename _Compare, typename _Alloc>
  1567.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1568.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1569.     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
  1570.     {
  1571.       bool __insert_left = (__x != 0 || __p == _M_end()
  1572.                             || _M_impl._M_key_compare(_S_key(__z),
  1573.                                                       _S_key(__p)));
  1574.  
  1575.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  1576.                                     this->_M_impl._M_header);
  1577.       ++_M_impl._M_node_count;
  1578.       return iterator(__z);
  1579.     }
  1580.  
  1581.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1582.            typename _Compare, typename _Alloc>
  1583.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1584.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1585.     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
  1586.     {
  1587.       bool __insert_left = (__p == _M_end()
  1588.                             || !_M_impl._M_key_compare(_S_key(__p),
  1589.                                                        _S_key(__z)));
  1590.  
  1591.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  1592.                                     this->_M_impl._M_header);
  1593.       ++_M_impl._M_node_count;
  1594.       return iterator(__z);
  1595.     }
  1596.  
  1597.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1598.            typename _Compare, typename _Alloc>
  1599.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1600.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1601.     _M_insert_equal_lower_node(_Link_type __z)
  1602.     {
  1603.       _Link_type __x = _M_begin();
  1604.       _Link_type __y = _M_end();
  1605.       while (__x != 0)
  1606.         {
  1607.           __y = __x;
  1608.           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
  1609.                 _S_left(__x) : _S_right(__x);
  1610.         }
  1611.       return _M_insert_lower_node(__y, __z);
  1612.     }
  1613.  
  1614.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1615.            typename _Compare, typename _Alloc>
  1616.     template<typename... _Args>
  1617.       pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1618.                              _Compare, _Alloc>::iterator, bool>
  1619.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1620.       _M_emplace_unique(_Args&&... __args)
  1621.       {
  1622.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  1623.  
  1624.         __try
  1625.           {
  1626.             typedef pair<iterator, bool> _Res;
  1627.             auto __res = _M_get_insert_unique_pos(_S_key(__z));
  1628.             if (__res.second)
  1629.               return _Res(_M_insert_node(__res.first, __res.second, __z), true);
  1630.        
  1631.             _M_destroy_node(__z);
  1632.             return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
  1633.           }
  1634.         __catch(...)
  1635.           {
  1636.             _M_destroy_node(__z);
  1637.             __throw_exception_again;
  1638.           }
  1639.       }
  1640.  
  1641.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1642.            typename _Compare, typename _Alloc>
  1643.     template<typename... _Args>
  1644.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1645.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1646.       _M_emplace_equal(_Args&&... __args)
  1647.       {
  1648.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  1649.  
  1650.         __try
  1651.           {
  1652.             auto __res = _M_get_insert_equal_pos(_S_key(__z));
  1653.             return _M_insert_node(__res.first, __res.second, __z);
  1654.           }
  1655.         __catch(...)
  1656.           {
  1657.             _M_destroy_node(__z);
  1658.             __throw_exception_again;
  1659.           }
  1660.       }
  1661.  
  1662.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1663.            typename _Compare, typename _Alloc>
  1664.     template<typename... _Args>
  1665.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1666.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1667.       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
  1668.       {
  1669.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  1670.  
  1671.         __try
  1672.           {
  1673.             auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
  1674.  
  1675.             if (__res.second)
  1676.               return _M_insert_node(__res.first, __res.second, __z);
  1677.  
  1678.             _M_destroy_node(__z);
  1679.             return iterator(static_cast<_Link_type>(__res.first));
  1680.           }
  1681.         __catch(...)
  1682.           {
  1683.             _M_destroy_node(__z);
  1684.             __throw_exception_again;
  1685.           }
  1686.       }
  1687.  
  1688.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1689.            typename _Compare, typename _Alloc>
  1690.     template<typename... _Args>
  1691.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1692.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1693.       _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
  1694.       {
  1695.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  1696.  
  1697.         __try
  1698.           {
  1699.             auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
  1700.  
  1701.             if (__res.second)
  1702.               return _M_insert_node(__res.first, __res.second, __z);
  1703.  
  1704.             return _M_insert_equal_lower_node(__z);
  1705.           }
  1706.         __catch(...)
  1707.           {
  1708.             _M_destroy_node(__z);
  1709.             __throw_exception_again;
  1710.           }
  1711.       }
  1712. #endif
  1713.  
  1714.   template<typename _Key, typename _Val, typename _KoV,
  1715.            typename _Cmp, typename _Alloc>
  1716.     template<class _II>
  1717.       void
  1718.       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
  1719.       _M_insert_unique(_II __first, _II __last)
  1720.       {
  1721.         for (; __first != __last; ++__first)
  1722.           _M_insert_unique_(end(), *__first);
  1723.       }
  1724.  
  1725.   template<typename _Key, typename _Val, typename _KoV,
  1726.            typename _Cmp, typename _Alloc>
  1727.     template<class _II>
  1728.       void
  1729.       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
  1730.       _M_insert_equal(_II __first, _II __last)
  1731.       {
  1732.         for (; __first != __last; ++__first)
  1733.           _M_insert_equal_(end(), *__first);
  1734.       }
  1735.  
  1736.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1737.            typename _Compare, typename _Alloc>
  1738.     void
  1739.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1740.     _M_erase_aux(const_iterator __position)
  1741.     {
  1742.       _Link_type __y =
  1743.         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
  1744.                                 (const_cast<_Base_ptr>(__position._M_node),
  1745.                                  this->_M_impl._M_header));
  1746.       _M_destroy_node(__y);
  1747.       --_M_impl._M_node_count;
  1748.     }
  1749.  
  1750.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1751.            typename _Compare, typename _Alloc>
  1752.     void
  1753.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1754.     _M_erase_aux(const_iterator __first, const_iterator __last)
  1755.     {
  1756.       if (__first == begin() && __last == end())
  1757.         clear();
  1758.       else
  1759.         while (__first != __last)
  1760.           erase(__first++);
  1761.     }
  1762.  
  1763.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1764.            typename _Compare, typename _Alloc>
  1765.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
  1766.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1767.     erase(const _Key& __x)
  1768.     {
  1769.       pair<iterator, iterator> __p = equal_range(__x);
  1770.       const size_type __old_size = size();
  1771.       erase(__p.first, __p.second);
  1772.       return __old_size - size();
  1773.     }
  1774.  
  1775.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1776.            typename _Compare, typename _Alloc>
  1777.     void
  1778.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1779.     erase(const _Key* __first, const _Key* __last)
  1780.     {
  1781.       while (__first != __last)
  1782.         erase(*__first++);
  1783.     }
  1784.  
  1785.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1786.            typename _Compare, typename _Alloc>
  1787.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1788.                       _Compare, _Alloc>::iterator
  1789.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1790.     find(const _Key& __k)
  1791.     {
  1792.       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  1793.       return (__j == end()
  1794.               || _M_impl._M_key_compare(__k,
  1795.                                         _S_key(__j._M_node))) ? end() : __j;
  1796.     }
  1797.  
  1798.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1799.            typename _Compare, typename _Alloc>
  1800.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1801.                       _Compare, _Alloc>::const_iterator
  1802.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1803.     find(const _Key& __k) const
  1804.     {
  1805.       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  1806.       return (__j == end()
  1807.               || _M_impl._M_key_compare(__k,
  1808.                                         _S_key(__j._M_node))) ? end() : __j;
  1809.     }
  1810.  
  1811.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1812.            typename _Compare, typename _Alloc>
  1813.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
  1814.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1815.     count(const _Key& __k) const
  1816.     {
  1817.       pair<const_iterator, const_iterator> __p = equal_range(__k);
  1818.       const size_type __n = std::distance(__p.first, __p.second);
  1819.       return __n;
  1820.     }
  1821.  
  1822.   _GLIBCXX_PURE unsigned int
  1823.   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
  1824.                        const _Rb_tree_node_base* __root) throw ();
  1825.  
  1826.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1827.            typename _Compare, typename _Alloc>
  1828.     bool
  1829.     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
  1830.     {
  1831.       if (_M_impl._M_node_count == 0 || begin() == end())
  1832.         return _M_impl._M_node_count == 0 && begin() == end()
  1833.                && this->_M_impl._M_header._M_left == _M_end()
  1834.                && this->_M_impl._M_header._M_right == _M_end();
  1835.  
  1836.       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
  1837.       for (const_iterator __it = begin(); __it != end(); ++__it)
  1838.         {
  1839.           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
  1840.           _Const_Link_type __L = _S_left(__x);
  1841.           _Const_Link_type __R = _S_right(__x);
  1842.  
  1843.           if (__x->_M_color == _S_red)
  1844.             if ((__L && __L->_M_color == _S_red)
  1845.                 || (__R && __R->_M_color == _S_red))
  1846.               return false;
  1847.  
  1848.           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
  1849.             return false;
  1850.           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
  1851.             return false;
  1852.  
  1853.           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
  1854.             return false;
  1855.         }
  1856.  
  1857.       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
  1858.         return false;
  1859.       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
  1860.         return false;
  1861.       return true;
  1862.     }
  1863.  
  1864. _GLIBCXX_END_NAMESPACE_VERSION
  1865. } // namespace
  1866.  
  1867. #endif
  1868.