Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // RB tree implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-2015 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. #pragma GCC system_header
  62.  
  63. #include <bits/stl_algobase.h>
  64. #include <bits/allocator.h>
  65. #include <bits/stl_function.h>
  66. #include <bits/cpp_type_traits.h>
  67. #include <ext/alloc_traits.h>
  68. #if __cplusplus >= 201103L
  69. #include <ext/aligned_buffer.h>
  70. #endif
  71.  
  72. namespace std _GLIBCXX_VISIBILITY(default)
  73. {
  74. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  75.  
  76.   // Red-black tree class, designed for use in implementing STL
  77.   // associative containers (set, multiset, map, and multimap). The
  78.   // insertion and deletion algorithms are based on those in Cormen,
  79.   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
  80.   // 1990), except that
  81.   //
  82.   // (1) the header cell is maintained with links not only to the root
  83.   // but also to the leftmost node of the tree, to enable constant
  84.   // time begin(), and to the rightmost node of the tree, to enable
  85.   // linear time performance when used with the generic set algorithms
  86.   // (set_union, etc.)
  87.   //
  88.   // (2) when a node being deleted has two children its successor node
  89.   // is relinked into its place, rather than copied, so that the only
  90.   // iterators invalidated are those referring to the deleted node.
  91.  
  92.   enum _Rb_tree_color { _S_red = false, _S_black = true };
  93.  
  94.   struct _Rb_tree_node_base
  95.   {
  96.     typedef _Rb_tree_node_base* _Base_ptr;
  97.     typedef const _Rb_tree_node_base* _Const_Base_ptr;
  98.  
  99.     _Rb_tree_color      _M_color;
  100.     _Base_ptr           _M_parent;
  101.     _Base_ptr           _M_left;
  102.     _Base_ptr           _M_right;
  103.  
  104.     static _Base_ptr
  105.     _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  106.     {
  107.       while (__x->_M_left != 0) __x = __x->_M_left;
  108.       return __x;
  109.     }
  110.  
  111.     static _Const_Base_ptr
  112.     _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
  113.     {
  114.       while (__x->_M_left != 0) __x = __x->_M_left;
  115.       return __x;
  116.     }
  117.  
  118.     static _Base_ptr
  119.     _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  120.     {
  121.       while (__x->_M_right != 0) __x = __x->_M_right;
  122.       return __x;
  123.     }
  124.  
  125.     static _Const_Base_ptr
  126.     _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
  127.     {
  128.       while (__x->_M_right != 0) __x = __x->_M_right;
  129.       return __x;
  130.     }
  131.   };
  132.  
  133.   template<typename _Val>
  134.     struct _Rb_tree_node : public _Rb_tree_node_base
  135.     {
  136.       typedef _Rb_tree_node<_Val>* _Link_type;
  137.  
  138. #if __cplusplus < 201103L
  139.       _Val _M_value_field;
  140.  
  141.       _Val*
  142.       _M_valptr()
  143.       { return std::__addressof(_M_value_field); }
  144.  
  145.       const _Val*
  146.       _M_valptr() const
  147.       { return std::__addressof(_M_value_field); }
  148. #else
  149.       __gnu_cxx::__aligned_membuf<_Val> _M_storage;
  150.  
  151.       _Val*
  152.       _M_valptr()
  153.       { return _M_storage._M_ptr(); }
  154.  
  155.       const _Val*
  156.       _M_valptr() const
  157.       { return _M_storage._M_ptr(); }
  158. #endif
  159.     };
  160.  
  161.   _GLIBCXX_PURE _Rb_tree_node_base*
  162.   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
  163.  
  164.   _GLIBCXX_PURE const _Rb_tree_node_base*
  165.   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
  166.  
  167.   _GLIBCXX_PURE _Rb_tree_node_base*
  168.   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
  169.  
  170.   _GLIBCXX_PURE const _Rb_tree_node_base*
  171.   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
  172.  
  173.   template<typename _Tp>
  174.     struct _Rb_tree_iterator
  175.     {
  176.       typedef _Tp  value_type;
  177.       typedef _Tp& reference;
  178.       typedef _Tp* pointer;
  179.  
  180.       typedef bidirectional_iterator_tag iterator_category;
  181.       typedef ptrdiff_t                  difference_type;
  182.  
  183.       typedef _Rb_tree_iterator<_Tp>        _Self;
  184.       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  185.       typedef _Rb_tree_node<_Tp>*           _Link_type;
  186.  
  187.       _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
  188.       : _M_node() { }
  189.  
  190.       explicit
  191.       _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  192.       : _M_node(__x) { }
  193.  
  194.       reference
  195.       operator*() const _GLIBCXX_NOEXCEPT
  196.       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
  197.  
  198.       pointer
  199.       operator->() const _GLIBCXX_NOEXCEPT
  200.       { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
  201.  
  202.       _Self&
  203.       operator++() _GLIBCXX_NOEXCEPT
  204.       {
  205.         _M_node = _Rb_tree_increment(_M_node);
  206.         return *this;
  207.       }
  208.  
  209.       _Self
  210.       operator++(int) _GLIBCXX_NOEXCEPT
  211.       {
  212.         _Self __tmp = *this;
  213.         _M_node = _Rb_tree_increment(_M_node);
  214.         return __tmp;
  215.       }
  216.  
  217.       _Self&
  218.       operator--() _GLIBCXX_NOEXCEPT
  219.       {
  220.         _M_node = _Rb_tree_decrement(_M_node);
  221.         return *this;
  222.       }
  223.  
  224.       _Self
  225.       operator--(int) _GLIBCXX_NOEXCEPT
  226.       {
  227.         _Self __tmp = *this;
  228.         _M_node = _Rb_tree_decrement(_M_node);
  229.         return __tmp;
  230.       }
  231.  
  232.       bool
  233.       operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
  234.       { return _M_node == __x._M_node; }
  235.  
  236.       bool
  237.       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
  238.       { return _M_node != __x._M_node; }
  239.  
  240.       _Base_ptr _M_node;
  241.   };
  242.  
  243.   template<typename _Tp>
  244.     struct _Rb_tree_const_iterator
  245.     {
  246.       typedef _Tp        value_type;
  247.       typedef const _Tp& reference;
  248.       typedef const _Tp* pointer;
  249.  
  250.       typedef _Rb_tree_iterator<_Tp> iterator;
  251.  
  252.       typedef bidirectional_iterator_tag iterator_category;
  253.       typedef ptrdiff_t                  difference_type;
  254.  
  255.       typedef _Rb_tree_const_iterator<_Tp>        _Self;
  256.       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
  257.       typedef const _Rb_tree_node<_Tp>*           _Link_type;
  258.  
  259.       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
  260.       : _M_node() { }
  261.  
  262.       explicit
  263.       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  264.       : _M_node(__x) { }
  265.  
  266.       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
  267.       : _M_node(__it._M_node) { }
  268.  
  269.       iterator
  270.       _M_const_cast() const _GLIBCXX_NOEXCEPT
  271.       { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
  272.  
  273.       reference
  274.       operator*() const _GLIBCXX_NOEXCEPT
  275.       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
  276.  
  277.       pointer
  278.       operator->() const _GLIBCXX_NOEXCEPT
  279.       { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
  280.  
  281.       _Self&
  282.       operator++() _GLIBCXX_NOEXCEPT
  283.       {
  284.         _M_node = _Rb_tree_increment(_M_node);
  285.         return *this;
  286.       }
  287.  
  288.       _Self
  289.       operator++(int) _GLIBCXX_NOEXCEPT
  290.       {
  291.         _Self __tmp = *this;
  292.         _M_node = _Rb_tree_increment(_M_node);
  293.         return __tmp;
  294.       }
  295.  
  296.       _Self&
  297.       operator--() _GLIBCXX_NOEXCEPT
  298.       {
  299.         _M_node = _Rb_tree_decrement(_M_node);
  300.         return *this;
  301.       }
  302.  
  303.       _Self
  304.       operator--(int) _GLIBCXX_NOEXCEPT
  305.       {
  306.         _Self __tmp = *this;
  307.         _M_node = _Rb_tree_decrement(_M_node);
  308.         return __tmp;
  309.       }
  310.  
  311.       bool
  312.       operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
  313.       { return _M_node == __x._M_node; }
  314.  
  315.       bool
  316.       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
  317.       { return _M_node != __x._M_node; }
  318.  
  319.       _Base_ptr _M_node;
  320.     };
  321.  
  322.   template<typename _Val>
  323.     inline bool
  324.     operator==(const _Rb_tree_iterator<_Val>& __x,
  325.                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
  326.     { return __x._M_node == __y._M_node; }
  327.  
  328.   template<typename _Val>
  329.     inline bool
  330.     operator!=(const _Rb_tree_iterator<_Val>& __x,
  331.                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
  332.     { return __x._M_node != __y._M_node; }
  333.  
  334.   void
  335.   _Rb_tree_insert_and_rebalance(const bool __insert_left,
  336.                                 _Rb_tree_node_base* __x,
  337.                                 _Rb_tree_node_base* __p,
  338.                                 _Rb_tree_node_base& __header) throw ();
  339.  
  340.   _Rb_tree_node_base*
  341.   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
  342.                                _Rb_tree_node_base& __header) throw ();
  343.  
  344.  
  345.   template<typename _Key, typename _Val, typename _KeyOfValue,
  346.            typename _Compare, typename _Alloc = allocator<_Val> >
  347.     class _Rb_tree
  348.     {
  349.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
  350.         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
  351.  
  352.       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
  353.  
  354.     protected:
  355.       typedef _Rb_tree_node_base*               _Base_ptr;
  356.       typedef const _Rb_tree_node_base*         _Const_Base_ptr;
  357.       typedef _Rb_tree_node<_Val>*              _Link_type;
  358.       typedef const _Rb_tree_node<_Val>*        _Const_Link_type;
  359.  
  360.     private:
  361.       // Functor recycling a pool of nodes and using allocation once the pool
  362.       // is empty.
  363.       struct _Reuse_or_alloc_node
  364.       {
  365.         _Reuse_or_alloc_node(_Rb_tree& __t)
  366.           : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
  367.         {
  368.           if (_M_root)
  369.             {
  370.               _M_root->_M_parent = 0;
  371.  
  372.               if (_M_nodes->_M_left)
  373.                 _M_nodes = _M_nodes->_M_left;
  374.             }
  375.           else
  376.             _M_nodes = 0;
  377.         }
  378.  
  379. #if __cplusplus >= 201103L
  380.         _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
  381. #endif
  382.  
  383.         ~_Reuse_or_alloc_node()
  384.         { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
  385.  
  386.         template<typename _Arg>
  387.           _Link_type
  388. #if __cplusplus < 201103L
  389.           operator()(const _Arg& __arg)
  390. #else
  391.           operator()(_Arg&& __arg)
  392. #endif
  393.           {
  394.             _Link_type __node = static_cast<_Link_type>(_M_extract());
  395.             if (__node)
  396.               {
  397.                 _M_t._M_destroy_node(__node);
  398.                 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
  399.                 return __node;
  400.               }
  401.  
  402.             return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
  403.           }
  404.  
  405.       private:
  406.         _Base_ptr
  407.         _M_extract()
  408.         {
  409.           if (!_M_nodes)
  410.             return _M_nodes;
  411.  
  412.           _Base_ptr __node = _M_nodes;
  413.           _M_nodes = _M_nodes->_M_parent;
  414.           if (_M_nodes)
  415.             {
  416.               if (_M_nodes->_M_right == __node)
  417.                 {
  418.                   _M_nodes->_M_right = 0;
  419.  
  420.                   if (_M_nodes->_M_left)
  421.                     {
  422.                       _M_nodes = _M_nodes->_M_left;
  423.  
  424.                       while (_M_nodes->_M_right)
  425.                         _M_nodes = _M_nodes->_M_right;
  426.  
  427.                       if (_M_nodes->_M_left)
  428.                         _M_nodes = _M_nodes->_M_left;
  429.                     }
  430.                 }
  431.               else // __node is on the left.
  432.                 _M_nodes->_M_left = 0;
  433.             }
  434.           else
  435.             _M_root = 0;
  436.  
  437.           return __node;
  438.         }
  439.  
  440.         _Base_ptr _M_root;
  441.         _Base_ptr _M_nodes;
  442.         _Rb_tree& _M_t;
  443.       };
  444.  
  445.       // Functor similar to the previous one but without any pool of nodes to
  446.       // recycle.
  447.       struct _Alloc_node
  448.       {
  449.         _Alloc_node(_Rb_tree& __t)
  450.           : _M_t(__t) { }
  451.  
  452.         template<typename _Arg>
  453.           _Link_type
  454. #if __cplusplus < 201103L
  455.           operator()(const _Arg& __arg) const
  456. #else
  457.           operator()(_Arg&& __arg) const
  458. #endif
  459.           { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
  460.  
  461.       private:
  462.         _Rb_tree& _M_t;
  463.       };
  464.  
  465.     public:
  466.       typedef _Key                              key_type;
  467.       typedef _Val                              value_type;
  468.       typedef value_type*                       pointer;
  469.       typedef const value_type*                 const_pointer;
  470.       typedef value_type&                       reference;
  471.       typedef const value_type&                 const_reference;
  472.       typedef size_t                            size_type;
  473.       typedef ptrdiff_t                         difference_type;
  474.       typedef _Alloc                            allocator_type;
  475.  
  476.       _Node_allocator&
  477.       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
  478.       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
  479.      
  480.       const _Node_allocator&
  481.       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
  482.       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
  483.  
  484.       allocator_type
  485.       get_allocator() const _GLIBCXX_NOEXCEPT
  486.       { return allocator_type(_M_get_Node_allocator()); }
  487.  
  488.     protected:
  489.       _Link_type
  490.       _M_get_node()
  491.       { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
  492.  
  493.       void
  494.       _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
  495.       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
  496.  
  497. #if __cplusplus < 201103L
  498.       void
  499.       _M_construct_node(_Link_type __node, const value_type& __x)
  500.       {
  501.         __try
  502.           { get_allocator().construct(__node->_M_valptr(), __x); }
  503.         __catch(...)
  504.           {
  505.             _M_put_node(__node);
  506.             __throw_exception_again;
  507.           }
  508.       }
  509.  
  510.       _Link_type
  511.       _M_create_node(const value_type& __x)
  512.       {
  513.         _Link_type __tmp = _M_get_node();
  514.         _M_construct_node(__tmp, __x);
  515.         return __tmp;
  516.       }
  517.  
  518.       void
  519.       _M_destroy_node(_Link_type __p)
  520.       { get_allocator().destroy(__p->_M_valptr()); }
  521. #else
  522.       template<typename... _Args>
  523.         void
  524.         _M_construct_node(_Link_type __node, _Args&&... __args)
  525.         {
  526.           __try
  527.             {
  528.               ::new(__node) _Rb_tree_node<_Val>;
  529.               _Alloc_traits::construct(_M_get_Node_allocator(),
  530.                                        __node->_M_valptr(),
  531.                                        std::forward<_Args>(__args)...);
  532.             }
  533.           __catch(...)
  534.             {
  535.               __node->~_Rb_tree_node<_Val>();
  536.               _M_put_node(__node);
  537.               __throw_exception_again;
  538.             }
  539.         }
  540.  
  541.       template<typename... _Args>
  542.         _Link_type
  543.         _M_create_node(_Args&&... __args)
  544.         {
  545.           _Link_type __tmp = _M_get_node();
  546.           _M_construct_node(__tmp, std::forward<_Args>(__args)...);
  547.           return __tmp;
  548.         }
  549.  
  550.       void
  551.       _M_destroy_node(_Link_type __p) noexcept
  552.       {
  553.         _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
  554.         __p->~_Rb_tree_node<_Val>();
  555.       }
  556. #endif
  557.  
  558.       void
  559.       _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
  560.       {
  561.         _M_destroy_node(__p);
  562.         _M_put_node(__p);
  563.       }
  564.  
  565.       template<typename _NodeGen>
  566.         _Link_type
  567.         _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
  568.         {
  569.           _Link_type __tmp = __node_gen(*__x->_M_valptr());
  570.           __tmp->_M_color = __x->_M_color;
  571.           __tmp->_M_left = 0;
  572.           __tmp->_M_right = 0;
  573.           return __tmp;
  574.         }
  575.  
  576.     protected:
  577.       // Unused _Is_pod_comparator is kept as it is part of mangled name.
  578.       template<typename _Key_compare,
  579.                bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
  580.         struct _Rb_tree_impl : public _Node_allocator
  581.         {
  582.           _Key_compare          _M_key_compare;
  583.           _Rb_tree_node_base    _M_header;
  584.           size_type             _M_node_count; // Keeps track of size of tree.
  585.  
  586.           _Rb_tree_impl()
  587.           : _Node_allocator(), _M_key_compare(), _M_header(),
  588.             _M_node_count(0)
  589.           { _M_initialize(); }
  590.  
  591.           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
  592.           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
  593.             _M_node_count(0)
  594.           { _M_initialize(); }
  595.  
  596. #if __cplusplus >= 201103L
  597.           _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
  598.           : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
  599.             _M_header(), _M_node_count(0)
  600.           { _M_initialize(); }
  601. #endif
  602.  
  603.           void
  604.           _M_reset()
  605.           {
  606.             this->_M_header._M_parent = 0;
  607.             this->_M_header._M_left = &this->_M_header;
  608.             this->_M_header._M_right = &this->_M_header;
  609.             this->_M_node_count = 0;
  610.           }
  611.  
  612.         private:
  613.           void
  614.           _M_initialize()
  615.           {
  616.             this->_M_header._M_color = _S_red;
  617.             this->_M_header._M_parent = 0;
  618.             this->_M_header._M_left = &this->_M_header;
  619.             this->_M_header._M_right = &this->_M_header;
  620.           }        
  621.         };
  622.  
  623.       _Rb_tree_impl<_Compare> _M_impl;
  624.  
  625.     protected:
  626.       _Base_ptr&
  627.       _M_root() _GLIBCXX_NOEXCEPT
  628.       { return this->_M_impl._M_header._M_parent; }
  629.  
  630.       _Const_Base_ptr
  631.       _M_root() const _GLIBCXX_NOEXCEPT
  632.       { return this->_M_impl._M_header._M_parent; }
  633.  
  634.       _Base_ptr&
  635.       _M_leftmost() _GLIBCXX_NOEXCEPT
  636.       { return this->_M_impl._M_header._M_left; }
  637.  
  638.       _Const_Base_ptr
  639.       _M_leftmost() const _GLIBCXX_NOEXCEPT
  640.       { return this->_M_impl._M_header._M_left; }
  641.  
  642.       _Base_ptr&
  643.       _M_rightmost() _GLIBCXX_NOEXCEPT
  644.       { return this->_M_impl._M_header._M_right; }
  645.  
  646.       _Const_Base_ptr
  647.       _M_rightmost() const _GLIBCXX_NOEXCEPT
  648.       { return this->_M_impl._M_header._M_right; }
  649.  
  650.       _Link_type
  651.       _M_begin() _GLIBCXX_NOEXCEPT
  652.       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
  653.  
  654.       _Const_Link_type
  655.       _M_begin() const _GLIBCXX_NOEXCEPT
  656.       {
  657.         return static_cast<_Const_Link_type>
  658.           (this->_M_impl._M_header._M_parent);
  659.       }
  660.  
  661.       _Link_type
  662.       _M_end() _GLIBCXX_NOEXCEPT
  663.       { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
  664.  
  665.       _Const_Link_type
  666.       _M_end() const _GLIBCXX_NOEXCEPT
  667.       { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
  668.  
  669.       static const_reference
  670.       _S_value(_Const_Link_type __x)
  671.       { return *__x->_M_valptr(); }
  672.  
  673.       static const _Key&
  674.       _S_key(_Const_Link_type __x)
  675.       { return _KeyOfValue()(_S_value(__x)); }
  676.  
  677.       static _Link_type
  678.       _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  679.       { return static_cast<_Link_type>(__x->_M_left); }
  680.  
  681.       static _Const_Link_type
  682.       _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
  683.       { return static_cast<_Const_Link_type>(__x->_M_left); }
  684.  
  685.       static _Link_type
  686.       _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  687.       { return static_cast<_Link_type>(__x->_M_right); }
  688.  
  689.       static _Const_Link_type
  690.       _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
  691.       { return static_cast<_Const_Link_type>(__x->_M_right); }
  692.  
  693.       static const_reference
  694.       _S_value(_Const_Base_ptr __x)
  695.       { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
  696.  
  697.       static const _Key&
  698.       _S_key(_Const_Base_ptr __x)
  699.       { return _KeyOfValue()(_S_value(__x)); }
  700.  
  701.       static _Base_ptr
  702.       _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  703.       { return _Rb_tree_node_base::_S_minimum(__x); }
  704.  
  705.       static _Const_Base_ptr
  706.       _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
  707.       { return _Rb_tree_node_base::_S_minimum(__x); }
  708.  
  709.       static _Base_ptr
  710.       _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
  711.       { return _Rb_tree_node_base::_S_maximum(__x); }
  712.  
  713.       static _Const_Base_ptr
  714.       _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
  715.       { return _Rb_tree_node_base::_S_maximum(__x); }
  716.  
  717.     public:
  718.       typedef _Rb_tree_iterator<value_type>       iterator;
  719.       typedef _Rb_tree_const_iterator<value_type> const_iterator;
  720.  
  721.       typedef std::reverse_iterator<iterator>       reverse_iterator;
  722.       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  723.  
  724.     private:
  725.       pair<_Base_ptr, _Base_ptr>
  726.       _M_get_insert_unique_pos(const key_type& __k);
  727.  
  728.       pair<_Base_ptr, _Base_ptr>
  729.       _M_get_insert_equal_pos(const key_type& __k);
  730.  
  731.       pair<_Base_ptr, _Base_ptr>
  732.       _M_get_insert_hint_unique_pos(const_iterator __pos,
  733.                                     const key_type& __k);
  734.  
  735.       pair<_Base_ptr, _Base_ptr>
  736.       _M_get_insert_hint_equal_pos(const_iterator __pos,
  737.                                    const key_type& __k);
  738.  
  739. #if __cplusplus >= 201103L
  740.       template<typename _Arg, typename _NodeGen>
  741.         iterator
  742.         _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
  743.  
  744.       iterator
  745.       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
  746.  
  747.       template<typename _Arg>
  748.         iterator
  749.         _M_insert_lower(_Base_ptr __y, _Arg&& __v);
  750.  
  751.       template<typename _Arg>
  752.         iterator
  753.         _M_insert_equal_lower(_Arg&& __x);
  754.  
  755.       iterator
  756.       _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
  757.  
  758.       iterator
  759.       _M_insert_equal_lower_node(_Link_type __z);
  760. #else
  761.       template<typename _NodeGen>
  762.         iterator
  763.         _M_insert_(_Base_ptr __x, _Base_ptr __y,
  764.                    const value_type& __v, _NodeGen&);
  765.  
  766.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  767.       // 233. Insertion hints in associative containers.
  768.       iterator
  769.       _M_insert_lower(_Base_ptr __y, const value_type& __v);
  770.  
  771.       iterator
  772.       _M_insert_equal_lower(const value_type& __x);
  773. #endif
  774.  
  775.       template<typename _NodeGen>
  776.         _Link_type
  777.         _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen&);
  778.  
  779.       _Link_type
  780.       _M_copy(_Const_Link_type __x, _Link_type __p)
  781.       {
  782.         _Alloc_node __an(*this);
  783.         return _M_copy(__x, __p, __an);
  784.       }
  785.  
  786.       void
  787.       _M_erase(_Link_type __x);
  788.  
  789.       iterator
  790.       _M_lower_bound(_Link_type __x, _Link_type __y,
  791.                      const _Key& __k);
  792.  
  793.       const_iterator
  794.       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
  795.                      const _Key& __k) const;
  796.  
  797.       iterator
  798.       _M_upper_bound(_Link_type __x, _Link_type __y,
  799.                      const _Key& __k);
  800.  
  801.       const_iterator
  802.       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
  803.                      const _Key& __k) const;
  804.  
  805.     public:
  806.       // allocation/deallocation
  807.       _Rb_tree() { }
  808.  
  809.       _Rb_tree(const _Compare& __comp,
  810.                const allocator_type& __a = allocator_type())
  811.       : _M_impl(__comp, _Node_allocator(__a)) { }
  812.  
  813.       _Rb_tree(const _Rb_tree& __x)
  814.       : _M_impl(__x._M_impl._M_key_compare,
  815.                 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
  816.       {
  817.         if (__x._M_root() != 0)
  818.           {
  819.             _M_root() = _M_copy(__x._M_begin(), _M_end());
  820.             _M_leftmost() = _S_minimum(_M_root());
  821.             _M_rightmost() = _S_maximum(_M_root());
  822.             _M_impl._M_node_count = __x._M_impl._M_node_count;
  823.           }
  824.       }
  825.  
  826. #if __cplusplus >= 201103L
  827.       _Rb_tree(const allocator_type& __a)
  828.       : _M_impl(_Compare(), _Node_allocator(__a))
  829.       { }
  830.  
  831.       _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
  832.       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
  833.       {
  834.         if (__x._M_root() != nullptr)
  835.           {
  836.             _M_root() = _M_copy(__x._M_begin(), _M_end());
  837.             _M_leftmost() = _S_minimum(_M_root());
  838.             _M_rightmost() = _S_maximum(_M_root());
  839.             _M_impl._M_node_count = __x._M_impl._M_node_count;
  840.           }
  841.       }
  842.  
  843.       _Rb_tree(_Rb_tree&& __x)
  844.       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
  845.       {
  846.         if (__x._M_root() != 0)
  847.           _M_move_data(__x, std::true_type());
  848.       }
  849.  
  850.       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
  851.       : _Rb_tree(std::move(__x), _Node_allocator(__a))
  852.       { }
  853.  
  854.       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
  855. #endif
  856.  
  857.       ~_Rb_tree() _GLIBCXX_NOEXCEPT
  858.       { _M_erase(_M_begin()); }
  859.  
  860.       _Rb_tree&
  861.       operator=(const _Rb_tree& __x);
  862.  
  863.       // Accessors.
  864.       _Compare
  865.       key_comp() const
  866.       { return _M_impl._M_key_compare; }
  867.  
  868.       iterator
  869.       begin() _GLIBCXX_NOEXCEPT
  870.       { return iterator(this->_M_impl._M_header._M_left); }
  871.  
  872.       const_iterator
  873.       begin() const _GLIBCXX_NOEXCEPT
  874.       { return const_iterator(this->_M_impl._M_header._M_left); }
  875.  
  876.       iterator
  877.       end() _GLIBCXX_NOEXCEPT
  878.       { return iterator(&this->_M_impl._M_header); }
  879.  
  880.       const_iterator
  881.       end() const _GLIBCXX_NOEXCEPT
  882.       { return const_iterator(&this->_M_impl._M_header); }
  883.  
  884.       reverse_iterator
  885.       rbegin() _GLIBCXX_NOEXCEPT
  886.       { return reverse_iterator(end()); }
  887.  
  888.       const_reverse_iterator
  889.       rbegin() const _GLIBCXX_NOEXCEPT
  890.       { return const_reverse_iterator(end()); }
  891.  
  892.       reverse_iterator
  893.       rend() _GLIBCXX_NOEXCEPT
  894.       { return reverse_iterator(begin()); }
  895.  
  896.       const_reverse_iterator
  897.       rend() const _GLIBCXX_NOEXCEPT
  898.       { return const_reverse_iterator(begin()); }
  899.  
  900.       bool
  901.       empty() const _GLIBCXX_NOEXCEPT
  902.       { return _M_impl._M_node_count == 0; }
  903.  
  904.       size_type
  905.       size() const _GLIBCXX_NOEXCEPT
  906.       { return _M_impl._M_node_count; }
  907.  
  908.       size_type
  909.       max_size() const _GLIBCXX_NOEXCEPT
  910.       { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
  911.  
  912.       void
  913. #if __cplusplus >= 201103L
  914.       swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
  915. #else
  916.       swap(_Rb_tree& __t);
  917. #endif
  918.  
  919.       // Insert/erase.
  920. #if __cplusplus >= 201103L
  921.       template<typename _Arg>
  922.         pair<iterator, bool>
  923.         _M_insert_unique(_Arg&& __x);
  924.  
  925.       template<typename _Arg>
  926.         iterator
  927.         _M_insert_equal(_Arg&& __x);
  928.  
  929.       template<typename _Arg, typename _NodeGen>
  930.         iterator
  931.         _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
  932.  
  933.       template<typename _Arg>
  934.         iterator
  935.         _M_insert_unique_(const_iterator __pos, _Arg&& __x)
  936.         {
  937.           _Alloc_node __an(*this);
  938.           return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
  939.         }
  940.  
  941.       template<typename _Arg, typename _NodeGen>
  942.         iterator
  943.         _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
  944.  
  945.       template<typename _Arg>
  946.         iterator
  947.         _M_insert_equal_(const_iterator __pos, _Arg&& __x)
  948.         {
  949.           _Alloc_node __an(*this);
  950.           return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
  951.         }
  952.  
  953.       template<typename... _Args>
  954.         pair<iterator, bool>
  955.         _M_emplace_unique(_Args&&... __args);
  956.  
  957.       template<typename... _Args>
  958.         iterator
  959.         _M_emplace_equal(_Args&&... __args);
  960.  
  961.       template<typename... _Args>
  962.         iterator
  963.         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
  964.  
  965.       template<typename... _Args>
  966.         iterator
  967.         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
  968. #else
  969.       pair<iterator, bool>
  970.       _M_insert_unique(const value_type& __x);
  971.  
  972.       iterator
  973.       _M_insert_equal(const value_type& __x);
  974.  
  975.       template<typename _NodeGen>
  976.         iterator
  977.         _M_insert_unique_(const_iterator __pos, const value_type& __x,
  978.                           _NodeGen&);
  979.  
  980.       iterator
  981.       _M_insert_unique_(const_iterator __pos, const value_type& __x)
  982.       {
  983.         _Alloc_node __an(*this);
  984.         return _M_insert_unique_(__pos, __x, __an);
  985.       }
  986.  
  987.       template<typename _NodeGen>
  988.         iterator
  989.         _M_insert_equal_(const_iterator __pos, const value_type& __x,
  990.                          _NodeGen&);
  991.       iterator
  992.       _M_insert_equal_(const_iterator __pos, const value_type& __x)
  993.       {
  994.         _Alloc_node __an(*this);
  995.         return _M_insert_equal_(__pos, __x, __an);
  996.       }
  997. #endif
  998.  
  999.       template<typename _InputIterator>
  1000.         void
  1001.         _M_insert_unique(_InputIterator __first, _InputIterator __last);
  1002.  
  1003.       template<typename _InputIterator>
  1004.         void
  1005.         _M_insert_equal(_InputIterator __first, _InputIterator __last);
  1006.  
  1007.     private:
  1008.       void
  1009.       _M_erase_aux(const_iterator __position);
  1010.  
  1011.       void
  1012.       _M_erase_aux(const_iterator __first, const_iterator __last);
  1013.  
  1014.     public:
  1015. #if __cplusplus >= 201103L
  1016.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1017.       // DR 130. Associative erase should return an iterator.
  1018.       _GLIBCXX_ABI_TAG_CXX11
  1019.       iterator
  1020.       erase(const_iterator __position)
  1021.       {
  1022.         const_iterator __result = __position;
  1023.         ++__result;
  1024.         _M_erase_aux(__position);
  1025.         return __result._M_const_cast();
  1026.       }
  1027.  
  1028.       // LWG 2059.
  1029.       _GLIBCXX_ABI_TAG_CXX11
  1030.       iterator
  1031.       erase(iterator __position)
  1032.       {
  1033.         iterator __result = __position;
  1034.         ++__result;
  1035.         _M_erase_aux(__position);
  1036.         return __result;
  1037.       }
  1038. #else
  1039.       void
  1040.       erase(iterator __position)
  1041.       { _M_erase_aux(__position); }
  1042.  
  1043.       void
  1044.       erase(const_iterator __position)
  1045.       { _M_erase_aux(__position); }
  1046. #endif
  1047.       size_type
  1048.       erase(const key_type& __x);
  1049.  
  1050. #if __cplusplus >= 201103L
  1051.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1052.       // DR 130. Associative erase should return an iterator.
  1053.       _GLIBCXX_ABI_TAG_CXX11
  1054.       iterator
  1055.       erase(const_iterator __first, const_iterator __last)
  1056.       {
  1057.         _M_erase_aux(__first, __last);
  1058.         return __last._M_const_cast();
  1059.       }
  1060. #else
  1061.       void
  1062.       erase(iterator __first, iterator __last)
  1063.       { _M_erase_aux(__first, __last); }
  1064.  
  1065.       void
  1066.       erase(const_iterator __first, const_iterator __last)
  1067.       { _M_erase_aux(__first, __last); }
  1068. #endif
  1069.       void
  1070.       erase(const key_type* __first, const key_type* __last);
  1071.  
  1072.       void
  1073.       clear() _GLIBCXX_NOEXCEPT
  1074.       {
  1075.         _M_erase(_M_begin());
  1076.         _M_impl._M_reset();
  1077.       }
  1078.  
  1079.       // Set operations.
  1080.       iterator
  1081.       find(const key_type& __k);
  1082.  
  1083.       const_iterator
  1084.       find(const key_type& __k) const;
  1085.  
  1086.       size_type
  1087.       count(const key_type& __k) const;
  1088.  
  1089.       iterator
  1090.       lower_bound(const key_type& __k)
  1091.       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
  1092.  
  1093.       const_iterator
  1094.       lower_bound(const key_type& __k) const
  1095.       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
  1096.  
  1097.       iterator
  1098.       upper_bound(const key_type& __k)
  1099.       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
  1100.  
  1101.       const_iterator
  1102.       upper_bound(const key_type& __k) const
  1103.       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
  1104.  
  1105.       pair<iterator, iterator>
  1106.       equal_range(const key_type& __k);
  1107.  
  1108.       pair<const_iterator, const_iterator>
  1109.       equal_range(const key_type& __k) const;
  1110.  
  1111. #if __cplusplus > 201103L
  1112.       template<typename _Cmp, typename _Kt, typename = __void_t<>>
  1113.         struct __is_transparent { };
  1114.  
  1115.       template<typename _Cmp, typename _Kt>
  1116.         struct
  1117.         __is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
  1118.         { typedef void type; };
  1119.  
  1120.       static auto _S_iter(_Link_type __x) { return iterator(__x); }
  1121.  
  1122.       static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
  1123.  
  1124.       template<typename _Cmp, typename _Link, typename _Kt>
  1125.         static auto
  1126.         _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
  1127.         {
  1128.           while (__x != 0)
  1129.             if (!__cmp(_S_key(__x), __k))
  1130.               __y = __x, __x = _S_left(__x);
  1131.             else
  1132.               __x = _S_right(__x);
  1133.           return _S_iter(__y);
  1134.         }
  1135.  
  1136.       template<typename _Cmp, typename _Link, typename _Kt>
  1137.         static auto
  1138.         _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
  1139.         {
  1140.           while (__x != 0)
  1141.             if (__cmp(__k, _S_key(__x)))
  1142.               __y = __x, __x = _S_left(__x);
  1143.             else
  1144.               __x = _S_right(__x);
  1145.           return _S_iter(__y);
  1146.         }
  1147.  
  1148.       template<typename _Kt,
  1149.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1150.         iterator
  1151.         _M_find_tr(const _Kt& __k)
  1152.         {
  1153.           auto& __cmp = _M_impl._M_key_compare;
  1154.           auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
  1155.           return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
  1156.             ? end() : __j;
  1157.         }
  1158.  
  1159.       template<typename _Kt,
  1160.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1161.         const_iterator
  1162.         _M_find_tr(const _Kt& __k) const
  1163.         {
  1164.           auto& __cmp = _M_impl._M_key_compare;
  1165.           auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
  1166.           return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
  1167.             ? end() : __j;
  1168.         }
  1169.  
  1170.       template<typename _Kt,
  1171.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1172.         size_type
  1173.         _M_count_tr(const _Kt& __k) const
  1174.         {
  1175.           auto __p = _M_equal_range_tr(__k);
  1176.           return std::distance(__p.first, __p.second);
  1177.         }
  1178.  
  1179.       template<typename _Kt,
  1180.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1181.         iterator
  1182.         _M_lower_bound_tr(const _Kt& __k)
  1183.         {
  1184.           auto& __cmp = _M_impl._M_key_compare;
  1185.           return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
  1186.         }
  1187.  
  1188.       template<typename _Kt,
  1189.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1190.         const_iterator
  1191.         _M_lower_bound_tr(const _Kt& __k) const
  1192.         {
  1193.           auto& __cmp = _M_impl._M_key_compare;
  1194.           return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
  1195.         }
  1196.  
  1197.       template<typename _Kt,
  1198.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1199.         iterator
  1200.         _M_upper_bound_tr(const _Kt& __k)
  1201.         {
  1202.           auto& __cmp = _M_impl._M_key_compare;
  1203.           return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
  1204.         }
  1205.  
  1206.       template<typename _Kt,
  1207.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1208.         const_iterator
  1209.         _M_upper_bound_tr(const _Kt& __k) const
  1210.         {
  1211.           auto& __cmp = _M_impl._M_key_compare;
  1212.           return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
  1213.         }
  1214.  
  1215.       template<typename _Kt,
  1216.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1217.         pair<iterator, iterator>
  1218.         _M_equal_range_tr(const _Kt& __k)
  1219.         {
  1220.           auto __low = _M_lower_bound_tr(__k);
  1221.           auto __high = __low;
  1222.           auto& __cmp = _M_impl._M_key_compare;
  1223.           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
  1224.             ++__high;
  1225.           return { __low, __high };
  1226.         }
  1227.  
  1228.       template<typename _Kt,
  1229.                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
  1230.         pair<const_iterator, const_iterator>
  1231.         _M_equal_range_tr(const _Kt& __k) const
  1232.         {
  1233.           auto __low = _M_lower_bound_tr(__k);
  1234.           auto __high = __low;
  1235.           auto& __cmp = _M_impl._M_key_compare;
  1236.           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
  1237.             ++__high;
  1238.           return { __low, __high };
  1239.         }
  1240. #endif
  1241.  
  1242.       // Debugging.
  1243.       bool
  1244.       __rb_verify() const;
  1245.  
  1246. #if __cplusplus >= 201103L
  1247.       _Rb_tree&
  1248.       operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move());
  1249.  
  1250.       template<typename _Iterator>
  1251.         void
  1252.         _M_assign_unique(_Iterator, _Iterator);
  1253.  
  1254.       template<typename _Iterator>
  1255.         void
  1256.         _M_assign_equal(_Iterator, _Iterator);
  1257.  
  1258.     private:
  1259.       // Move elements from container with equal allocator.
  1260.       void
  1261.       _M_move_data(_Rb_tree&, std::true_type);
  1262.  
  1263.       // Move elements from container with possibly non-equal allocator,
  1264.       // which might result in a copy not a move.
  1265.       void
  1266.       _M_move_data(_Rb_tree&, std::false_type);
  1267. #endif
  1268.     };
  1269.  
  1270.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1271.            typename _Compare, typename _Alloc>
  1272.     inline bool
  1273.     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1274.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1275.     {
  1276.       return __x.size() == __y.size()
  1277.              && std::equal(__x.begin(), __x.end(), __y.begin());
  1278.     }
  1279.  
  1280.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1281.            typename _Compare, typename _Alloc>
  1282.     inline bool
  1283.     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1284.               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1285.     {
  1286.       return std::lexicographical_compare(__x.begin(), __x.end(),
  1287.                                           __y.begin(), __y.end());
  1288.     }
  1289.  
  1290.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1291.            typename _Compare, typename _Alloc>
  1292.     inline bool
  1293.     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1294.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1295.     { return !(__x == __y); }
  1296.  
  1297.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1298.            typename _Compare, typename _Alloc>
  1299.     inline bool
  1300.     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1301.               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1302.     { return __y < __x; }
  1303.  
  1304.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1305.            typename _Compare, typename _Alloc>
  1306.     inline bool
  1307.     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1308.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1309.     { return !(__y < __x); }
  1310.  
  1311.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1312.            typename _Compare, typename _Alloc>
  1313.     inline bool
  1314.     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1315.                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1316.     { return !(__x < __y); }
  1317.  
  1318.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1319.            typename _Compare, typename _Alloc>
  1320.     inline void
  1321.     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
  1322.          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  1323.     { __x.swap(__y); }
  1324.  
  1325. #if __cplusplus >= 201103L
  1326.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1327.            typename _Compare, typename _Alloc>
  1328.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1329.     _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
  1330.     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
  1331.     {
  1332.       using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
  1333.       if (__x._M_root() != nullptr)
  1334.         _M_move_data(__x, __eq());
  1335.     }
  1336.  
  1337.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1338.            typename _Compare, typename _Alloc>
  1339.     void
  1340.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1341.     _M_move_data(_Rb_tree& __x, std::true_type)
  1342.     {
  1343.       _M_root() = __x._M_root();
  1344.       _M_leftmost() = __x._M_leftmost();
  1345.       _M_rightmost() = __x._M_rightmost();
  1346.       _M_root()->_M_parent = _M_end();
  1347.  
  1348.       __x._M_root() = 0;
  1349.       __x._M_leftmost() = __x._M_end();
  1350.       __x._M_rightmost() = __x._M_end();
  1351.  
  1352.       this->_M_impl._M_node_count = __x._M_impl._M_node_count;
  1353.       __x._M_impl._M_node_count = 0;
  1354.     }
  1355.  
  1356.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1357.            typename _Compare, typename _Alloc>
  1358.     void
  1359.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1360.     _M_move_data(_Rb_tree& __x, std::false_type)
  1361.     {
  1362.       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
  1363.           _M_move_data(__x, std::true_type());
  1364.       else
  1365.         {
  1366.           _Alloc_node __an(*this);
  1367.           auto __lbd =
  1368.             [&__an](const value_type& __cval)
  1369.             {
  1370.               auto& __val = const_cast<value_type&>(__cval);
  1371.               return __an(std::move_if_noexcept(__val));
  1372.             };
  1373.           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
  1374.           _M_leftmost() = _S_minimum(_M_root());
  1375.           _M_rightmost() = _S_maximum(_M_root());
  1376.           _M_impl._M_node_count = __x._M_impl._M_node_count;
  1377.         }
  1378.     }
  1379.  
  1380.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1381.            typename _Compare, typename _Alloc>
  1382.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
  1383.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1384.     operator=(_Rb_tree&& __x)
  1385.     noexcept(_Alloc_traits::_S_nothrow_move())
  1386.     {
  1387.       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
  1388.       if (_Alloc_traits::_S_propagate_on_move_assign()
  1389.           || _Alloc_traits::_S_always_equal()
  1390.           || _M_get_Node_allocator() == __x._M_get_Node_allocator())
  1391.         {
  1392.           clear();
  1393.           if (__x._M_root() != nullptr)
  1394.             _M_move_data(__x, std::true_type());
  1395.           std::__alloc_on_move(_M_get_Node_allocator(),
  1396.                                __x._M_get_Node_allocator());
  1397.           return *this;
  1398.         }
  1399.  
  1400.       // Try to move each node reusing existing nodes and copying __x nodes
  1401.       // structure.
  1402.       _Reuse_or_alloc_node __roan(*this);
  1403.       _M_impl._M_reset();
  1404.       if (__x._M_root() != nullptr)
  1405.         {
  1406.           auto __lbd =
  1407.             [&__roan](const value_type& __cval)
  1408.             {
  1409.               auto& __val = const_cast<value_type&>(__cval);
  1410.               return __roan(std::move_if_noexcept(__val));
  1411.             };
  1412.           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
  1413.           _M_leftmost() = _S_minimum(_M_root());
  1414.           _M_rightmost() = _S_maximum(_M_root());
  1415.           _M_impl._M_node_count = __x._M_impl._M_node_count;
  1416.           __x.clear();
  1417.         }
  1418.       return *this;
  1419.     }
  1420.  
  1421.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1422.            typename _Compare, typename _Alloc>
  1423.     template<typename _Iterator>
  1424.       void
  1425.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1426.       _M_assign_unique(_Iterator __first, _Iterator __last)
  1427.       {
  1428.         _Reuse_or_alloc_node __roan(*this);
  1429.         _M_impl._M_reset();
  1430.         for (; __first != __last; ++__first)
  1431.           _M_insert_unique_(end(), *__first, __roan);
  1432.       }
  1433.  
  1434.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1435.            typename _Compare, typename _Alloc>
  1436.     template<typename _Iterator>
  1437.       void
  1438.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1439.       _M_assign_equal(_Iterator __first, _Iterator __last)
  1440.       {
  1441.         _Reuse_or_alloc_node __roan(*this);
  1442.         _M_impl._M_reset();
  1443.         for (; __first != __last; ++__first)
  1444.           _M_insert_equal_(end(), *__first, __roan);
  1445.       }
  1446. #endif
  1447.  
  1448.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1449.            typename _Compare, typename _Alloc>
  1450.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
  1451.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1452.     operator=(const _Rb_tree& __x)
  1453.     {
  1454.       if (this != &__x)
  1455.         {
  1456.           // Note that _Key may be a constant type.
  1457. #if __cplusplus >= 201103L
  1458.           if (_Alloc_traits::_S_propagate_on_copy_assign())
  1459.             {
  1460.               auto& __this_alloc = this->_M_get_Node_allocator();
  1461.               auto& __that_alloc = __x._M_get_Node_allocator();
  1462.               if (!_Alloc_traits::_S_always_equal()
  1463.                   && __this_alloc != __that_alloc)
  1464.                 {
  1465.                   // Replacement allocator cannot free existing storage, we need
  1466.                   // to erase nodes first.
  1467.                   clear();
  1468.                   std::__alloc_on_copy(__this_alloc, __that_alloc);
  1469.                 }
  1470.             }
  1471. #endif
  1472.  
  1473.           _Reuse_or_alloc_node __roan(*this);
  1474.           _M_impl._M_reset();
  1475.           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
  1476.           if (__x._M_root() != 0)
  1477.             {
  1478.               _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
  1479.               _M_leftmost() = _S_minimum(_M_root());
  1480.               _M_rightmost() = _S_maximum(_M_root());
  1481.               _M_impl._M_node_count = __x._M_impl._M_node_count;
  1482.             }
  1483.         }
  1484.  
  1485.       return *this;
  1486.     }
  1487.  
  1488.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1489.            typename _Compare, typename _Alloc>
  1490. #if __cplusplus >= 201103L
  1491.     template<typename _Arg, typename _NodeGen>
  1492. #else
  1493.     template<typename _NodeGen>
  1494. #endif
  1495.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1496.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1497.       _M_insert_(_Base_ptr __x, _Base_ptr __p,
  1498. #if __cplusplus >= 201103L
  1499.                  _Arg&& __v,
  1500. #else
  1501.                  const _Val& __v,
  1502. #endif
  1503.                  _NodeGen& __node_gen)
  1504.       {
  1505.         bool __insert_left = (__x != 0 || __p == _M_end()
  1506.                               || _M_impl._M_key_compare(_KeyOfValue()(__v),
  1507.                                                         _S_key(__p)));
  1508.  
  1509.         _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
  1510.  
  1511.         _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  1512.                                       this->_M_impl._M_header);
  1513.         ++_M_impl._M_node_count;
  1514.         return iterator(__z);
  1515.       }
  1516.  
  1517.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1518.            typename _Compare, typename _Alloc>
  1519. #if __cplusplus >= 201103L
  1520.     template<typename _Arg>
  1521. #endif
  1522.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1523.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1524. #if __cplusplus >= 201103L
  1525.     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
  1526. #else
  1527.     _M_insert_lower(_Base_ptr __p, const _Val& __v)
  1528. #endif
  1529.     {
  1530.       bool __insert_left = (__p == _M_end()
  1531.                             || !_M_impl._M_key_compare(_S_key(__p),
  1532.                                                        _KeyOfValue()(__v)));
  1533.  
  1534.       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
  1535.  
  1536.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  1537.                                     this->_M_impl._M_header);
  1538.       ++_M_impl._M_node_count;
  1539.       return iterator(__z);
  1540.     }
  1541.  
  1542.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1543.            typename _Compare, typename _Alloc>
  1544. #if __cplusplus >= 201103L
  1545.     template<typename _Arg>
  1546. #endif
  1547.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1548.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1549. #if __cplusplus >= 201103L
  1550.     _M_insert_equal_lower(_Arg&& __v)
  1551. #else
  1552.     _M_insert_equal_lower(const _Val& __v)
  1553. #endif
  1554.     {
  1555.       _Link_type __x = _M_begin();
  1556.       _Link_type __y = _M_end();
  1557.       while (__x != 0)
  1558.         {
  1559.           __y = __x;
  1560.           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
  1561.                 _S_left(__x) : _S_right(__x);
  1562.         }
  1563.       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
  1564.     }
  1565.  
  1566.   template<typename _Key, typename _Val, typename _KoV,
  1567.            typename _Compare, typename _Alloc>
  1568.     template<typename _NodeGen>
  1569.       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
  1570.       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
  1571.       _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
  1572.       {
  1573.         // Structural copy. __x and __p must be non-null.
  1574.         _Link_type __top = _M_clone_node(__x, __node_gen);
  1575.         __top->_M_parent = __p;
  1576.  
  1577.         __try
  1578.           {
  1579.             if (__x->_M_right)
  1580.               __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
  1581.             __p = __top;
  1582.             __x = _S_left(__x);
  1583.  
  1584.             while (__x != 0)
  1585.               {
  1586.                 _Link_type __y = _M_clone_node(__x, __node_gen);
  1587.                 __p->_M_left = __y;
  1588.                 __y->_M_parent = __p;
  1589.                 if (__x->_M_right)
  1590.                   __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
  1591.                 __p = __y;
  1592.                 __x = _S_left(__x);
  1593.               }
  1594.           }
  1595.         __catch(...)
  1596.           {
  1597.             _M_erase(__top);
  1598.             __throw_exception_again;
  1599.           }
  1600.         return __top;
  1601.       }
  1602.  
  1603.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1604.            typename _Compare, typename _Alloc>
  1605.     void
  1606.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1607.     _M_erase(_Link_type __x)
  1608.     {
  1609.       // Erase without rebalancing.
  1610.       while (__x != 0)
  1611.         {
  1612.           _M_erase(_S_right(__x));
  1613.           _Link_type __y = _S_left(__x);
  1614.           _M_drop_node(__x);
  1615.           __x = __y;
  1616.         }
  1617.     }
  1618.  
  1619.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1620.            typename _Compare, typename _Alloc>
  1621.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1622.                       _Compare, _Alloc>::iterator
  1623.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1624.     _M_lower_bound(_Link_type __x, _Link_type __y,
  1625.                    const _Key& __k)
  1626.     {
  1627.       while (__x != 0)
  1628.         if (!_M_impl._M_key_compare(_S_key(__x), __k))
  1629.           __y = __x, __x = _S_left(__x);
  1630.         else
  1631.           __x = _S_right(__x);
  1632.       return iterator(__y);
  1633.     }
  1634.  
  1635.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1636.            typename _Compare, typename _Alloc>
  1637.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1638.                       _Compare, _Alloc>::const_iterator
  1639.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1640.     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
  1641.                    const _Key& __k) const
  1642.     {
  1643.       while (__x != 0)
  1644.         if (!_M_impl._M_key_compare(_S_key(__x), __k))
  1645.           __y = __x, __x = _S_left(__x);
  1646.         else
  1647.           __x = _S_right(__x);
  1648.       return const_iterator(__y);
  1649.     }
  1650.  
  1651.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1652.            typename _Compare, typename _Alloc>
  1653.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1654.                       _Compare, _Alloc>::iterator
  1655.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1656.     _M_upper_bound(_Link_type __x, _Link_type __y,
  1657.                    const _Key& __k)
  1658.     {
  1659.       while (__x != 0)
  1660.         if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1661.           __y = __x, __x = _S_left(__x);
  1662.         else
  1663.           __x = _S_right(__x);
  1664.       return iterator(__y);
  1665.     }
  1666.  
  1667.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1668.            typename _Compare, typename _Alloc>
  1669.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1670.                       _Compare, _Alloc>::const_iterator
  1671.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1672.     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
  1673.                    const _Key& __k) const
  1674.     {
  1675.       while (__x != 0)
  1676.         if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1677.           __y = __x, __x = _S_left(__x);
  1678.         else
  1679.           __x = _S_right(__x);
  1680.       return const_iterator(__y);
  1681.     }
  1682.  
  1683.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1684.            typename _Compare, typename _Alloc>
  1685.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1686.                            _Compare, _Alloc>::iterator,
  1687.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1688.                            _Compare, _Alloc>::iterator>
  1689.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1690.     equal_range(const _Key& __k)
  1691.     {
  1692.       _Link_type __x = _M_begin();
  1693.       _Link_type __y = _M_end();
  1694.       while (__x != 0)
  1695.         {
  1696.           if (_M_impl._M_key_compare(_S_key(__x), __k))
  1697.             __x = _S_right(__x);
  1698.           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1699.             __y = __x, __x = _S_left(__x);
  1700.           else
  1701.             {
  1702.               _Link_type __xu(__x), __yu(__y);
  1703.               __y = __x, __x = _S_left(__x);
  1704.               __xu = _S_right(__xu);
  1705.               return pair<iterator,
  1706.                           iterator>(_M_lower_bound(__x, __y, __k),
  1707.                                     _M_upper_bound(__xu, __yu, __k));
  1708.             }
  1709.         }
  1710.       return pair<iterator, iterator>(iterator(__y),
  1711.                                       iterator(__y));
  1712.     }
  1713.  
  1714.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1715.            typename _Compare, typename _Alloc>
  1716.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1717.                            _Compare, _Alloc>::const_iterator,
  1718.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1719.                            _Compare, _Alloc>::const_iterator>
  1720.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1721.     equal_range(const _Key& __k) const
  1722.     {
  1723.       _Const_Link_type __x = _M_begin();
  1724.       _Const_Link_type __y = _M_end();
  1725.       while (__x != 0)
  1726.         {
  1727.           if (_M_impl._M_key_compare(_S_key(__x), __k))
  1728.             __x = _S_right(__x);
  1729.           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
  1730.             __y = __x, __x = _S_left(__x);
  1731.           else
  1732.             {
  1733.               _Const_Link_type __xu(__x), __yu(__y);
  1734.               __y = __x, __x = _S_left(__x);
  1735.               __xu = _S_right(__xu);
  1736.               return pair<const_iterator,
  1737.                           const_iterator>(_M_lower_bound(__x, __y, __k),
  1738.                                           _M_upper_bound(__xu, __yu, __k));
  1739.             }
  1740.         }
  1741.       return pair<const_iterator, const_iterator>(const_iterator(__y),
  1742.                                                   const_iterator(__y));
  1743.     }
  1744.  
  1745.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1746.            typename _Compare, typename _Alloc>
  1747.     void
  1748.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1749.     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
  1750. #if __cplusplus >= 201103L
  1751.     noexcept(_Alloc_traits::_S_nothrow_swap())
  1752. #endif
  1753.     {
  1754.       if (_M_root() == 0)
  1755.         {
  1756.           if (__t._M_root() != 0)
  1757.             {
  1758.               _M_root() = __t._M_root();
  1759.               _M_leftmost() = __t._M_leftmost();
  1760.               _M_rightmost() = __t._M_rightmost();
  1761.               _M_root()->_M_parent = _M_end();
  1762.               _M_impl._M_node_count = __t._M_impl._M_node_count;
  1763.              
  1764.               __t._M_impl._M_reset();
  1765.             }
  1766.         }
  1767.       else if (__t._M_root() == 0)
  1768.         {
  1769.           __t._M_root() = _M_root();
  1770.           __t._M_leftmost() = _M_leftmost();
  1771.           __t._M_rightmost() = _M_rightmost();
  1772.           __t._M_root()->_M_parent = __t._M_end();
  1773.           __t._M_impl._M_node_count = _M_impl._M_node_count;
  1774.          
  1775.           _M_impl._M_reset();
  1776.         }
  1777.       else
  1778.         {
  1779.           std::swap(_M_root(),__t._M_root());
  1780.           std::swap(_M_leftmost(),__t._M_leftmost());
  1781.           std::swap(_M_rightmost(),__t._M_rightmost());
  1782.          
  1783.           _M_root()->_M_parent = _M_end();
  1784.           __t._M_root()->_M_parent = __t._M_end();
  1785.           std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
  1786.         }
  1787.       // No need to swap header's color as it does not change.
  1788.       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
  1789.  
  1790.       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
  1791.                                 __t._M_get_Node_allocator());
  1792.     }
  1793.  
  1794.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1795.            typename _Compare, typename _Alloc>
  1796.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1797.                            _Compare, _Alloc>::_Base_ptr,
  1798.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1799.                            _Compare, _Alloc>::_Base_ptr>
  1800.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1801.     _M_get_insert_unique_pos(const key_type& __k)
  1802.     {
  1803.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1804.       _Link_type __x = _M_begin();
  1805.       _Link_type __y = _M_end();
  1806.       bool __comp = true;
  1807.       while (__x != 0)
  1808.         {
  1809.           __y = __x;
  1810.           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
  1811.           __x = __comp ? _S_left(__x) : _S_right(__x);
  1812.         }
  1813.       iterator __j = iterator(__y);
  1814.       if (__comp)
  1815.         {
  1816.           if (__j == begin())
  1817.             return _Res(__x, __y);
  1818.           else
  1819.             --__j;
  1820.         }
  1821.       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
  1822.         return _Res(__x, __y);
  1823.       return _Res(__j._M_node, 0);
  1824.     }
  1825.  
  1826.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1827.            typename _Compare, typename _Alloc>
  1828.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1829.                            _Compare, _Alloc>::_Base_ptr,
  1830.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1831.                            _Compare, _Alloc>::_Base_ptr>
  1832.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1833.     _M_get_insert_equal_pos(const key_type& __k)
  1834.     {
  1835.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1836.       _Link_type __x = _M_begin();
  1837.       _Link_type __y = _M_end();
  1838.       while (__x != 0)
  1839.         {
  1840.           __y = __x;
  1841.           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
  1842.                 _S_left(__x) : _S_right(__x);
  1843.         }
  1844.       return _Res(__x, __y);
  1845.     }
  1846.  
  1847.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1848.            typename _Compare, typename _Alloc>
  1849. #if __cplusplus >= 201103L
  1850.     template<typename _Arg>
  1851. #endif
  1852.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1853.                            _Compare, _Alloc>::iterator, bool>
  1854.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1855. #if __cplusplus >= 201103L
  1856.     _M_insert_unique(_Arg&& __v)
  1857. #else
  1858.     _M_insert_unique(const _Val& __v)
  1859. #endif
  1860.     {
  1861.       typedef pair<iterator, bool> _Res;
  1862.       pair<_Base_ptr, _Base_ptr> __res
  1863.         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
  1864.  
  1865.       if (__res.second)
  1866.         {
  1867.           _Alloc_node __an(*this);
  1868.           return _Res(_M_insert_(__res.first, __res.second,
  1869.                                  _GLIBCXX_FORWARD(_Arg, __v), __an),
  1870.                       true);
  1871.         }
  1872.  
  1873.       return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
  1874.     }
  1875.  
  1876.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1877.            typename _Compare, typename _Alloc>
  1878. #if __cplusplus >= 201103L
  1879.     template<typename _Arg>
  1880. #endif
  1881.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1882.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1883. #if __cplusplus >= 201103L
  1884.     _M_insert_equal(_Arg&& __v)
  1885. #else
  1886.     _M_insert_equal(const _Val& __v)
  1887. #endif
  1888.     {
  1889.       pair<_Base_ptr, _Base_ptr> __res
  1890.         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
  1891.       _Alloc_node __an(*this);
  1892.       return _M_insert_(__res.first, __res.second,
  1893.                         _GLIBCXX_FORWARD(_Arg, __v), __an);
  1894.     }
  1895.  
  1896.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1897.            typename _Compare, typename _Alloc>
  1898.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1899.                            _Compare, _Alloc>::_Base_ptr,
  1900.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1901.                            _Compare, _Alloc>::_Base_ptr>
  1902.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1903.     _M_get_insert_hint_unique_pos(const_iterator __position,
  1904.                                   const key_type& __k)
  1905.     {
  1906.       iterator __pos = __position._M_const_cast();
  1907.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1908.  
  1909.       // end()
  1910.       if (__pos._M_node == _M_end())
  1911.         {
  1912.           if (size() > 0
  1913.               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
  1914.             return _Res(0, _M_rightmost());
  1915.           else
  1916.             return _M_get_insert_unique_pos(__k);
  1917.         }
  1918.       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
  1919.         {
  1920.           // First, try before...
  1921.           iterator __before = __pos;
  1922.           if (__pos._M_node == _M_leftmost()) // begin()
  1923.             return _Res(_M_leftmost(), _M_leftmost());
  1924.           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
  1925.             {
  1926.               if (_S_right(__before._M_node) == 0)
  1927.                 return _Res(0, __before._M_node);
  1928.               else
  1929.                 return _Res(__pos._M_node, __pos._M_node);
  1930.             }
  1931.           else
  1932.             return _M_get_insert_unique_pos(__k);
  1933.         }
  1934.       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
  1935.         {
  1936.           // ... then try after.
  1937.           iterator __after = __pos;
  1938.           if (__pos._M_node == _M_rightmost())
  1939.             return _Res(0, _M_rightmost());
  1940.           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
  1941.             {
  1942.               if (_S_right(__pos._M_node) == 0)
  1943.                 return _Res(0, __pos._M_node);
  1944.               else
  1945.                 return _Res(__after._M_node, __after._M_node);
  1946.             }
  1947.           else
  1948.             return _M_get_insert_unique_pos(__k);
  1949.         }
  1950.       else
  1951.         // Equivalent keys.
  1952.         return _Res(__pos._M_node, 0);
  1953.     }
  1954.  
  1955.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1956.            typename _Compare, typename _Alloc>
  1957. #if __cplusplus >= 201103L
  1958.     template<typename _Arg, typename _NodeGen>
  1959. #else
  1960.     template<typename _NodeGen>
  1961. #endif
  1962.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  1963.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1964.       _M_insert_unique_(const_iterator __position,
  1965. #if __cplusplus >= 201103L
  1966.                         _Arg&& __v,
  1967. #else
  1968.                         const _Val& __v,
  1969. #endif
  1970.                         _NodeGen& __node_gen)
  1971.     {
  1972.       pair<_Base_ptr, _Base_ptr> __res
  1973.         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
  1974.  
  1975.       if (__res.second)
  1976.         return _M_insert_(__res.first, __res.second,
  1977.                           _GLIBCXX_FORWARD(_Arg, __v),
  1978.                           __node_gen);
  1979.       return iterator(static_cast<_Link_type>(__res.first));
  1980.     }
  1981.  
  1982.   template<typename _Key, typename _Val, typename _KeyOfValue,
  1983.            typename _Compare, typename _Alloc>
  1984.     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1985.                            _Compare, _Alloc>::_Base_ptr,
  1986.          typename _Rb_tree<_Key, _Val, _KeyOfValue,
  1987.                            _Compare, _Alloc>::_Base_ptr>
  1988.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  1989.     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
  1990.     {
  1991.       iterator __pos = __position._M_const_cast();
  1992.       typedef pair<_Base_ptr, _Base_ptr> _Res;
  1993.  
  1994.       // end()
  1995.       if (__pos._M_node == _M_end())
  1996.         {
  1997.           if (size() > 0
  1998.               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
  1999.             return _Res(0, _M_rightmost());
  2000.           else
  2001.             return _M_get_insert_equal_pos(__k);
  2002.         }
  2003.       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
  2004.         {
  2005.           // First, try before...
  2006.           iterator __before = __pos;
  2007.           if (__pos._M_node == _M_leftmost()) // begin()
  2008.             return _Res(_M_leftmost(), _M_leftmost());
  2009.           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
  2010.             {
  2011.               if (_S_right(__before._M_node) == 0)
  2012.                 return _Res(0, __before._M_node);
  2013.               else
  2014.                 return _Res(__pos._M_node, __pos._M_node);
  2015.             }
  2016.           else
  2017.             return _M_get_insert_equal_pos(__k);
  2018.         }
  2019.       else
  2020.         {
  2021.           // ... then try after.  
  2022.           iterator __after = __pos;
  2023.           if (__pos._M_node == _M_rightmost())
  2024.             return _Res(0, _M_rightmost());
  2025.           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
  2026.             {
  2027.               if (_S_right(__pos._M_node) == 0)
  2028.                 return _Res(0, __pos._M_node);
  2029.               else
  2030.                 return _Res(__after._M_node, __after._M_node);
  2031.             }
  2032.           else
  2033.             return _Res(0, 0);
  2034.         }
  2035.     }
  2036.  
  2037.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2038.            typename _Compare, typename _Alloc>
  2039. #if __cplusplus >= 201103L
  2040.     template<typename _Arg, typename _NodeGen>
  2041. #else
  2042.     template<typename _NodeGen>
  2043. #endif
  2044.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2045.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2046.       _M_insert_equal_(const_iterator __position,
  2047. #if __cplusplus >= 201103L
  2048.                        _Arg&& __v,
  2049. #else
  2050.                        const _Val& __v,
  2051. #endif
  2052.                        _NodeGen& __node_gen)
  2053.       {
  2054.         pair<_Base_ptr, _Base_ptr> __res
  2055.           = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
  2056.  
  2057.         if (__res.second)
  2058.           return _M_insert_(__res.first, __res.second,
  2059.                             _GLIBCXX_FORWARD(_Arg, __v),
  2060.                             __node_gen);
  2061.  
  2062.         return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
  2063.       }
  2064.  
  2065. #if __cplusplus >= 201103L
  2066.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2067.            typename _Compare, typename _Alloc>
  2068.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2069.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2070.     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
  2071.     {
  2072.       bool __insert_left = (__x != 0 || __p == _M_end()
  2073.                             || _M_impl._M_key_compare(_S_key(__z),
  2074.                                                       _S_key(__p)));
  2075.  
  2076.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  2077.                                     this->_M_impl._M_header);
  2078.       ++_M_impl._M_node_count;
  2079.       return iterator(__z);
  2080.     }
  2081.  
  2082.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2083.            typename _Compare, typename _Alloc>
  2084.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2085.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2086.     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
  2087.     {
  2088.       bool __insert_left = (__p == _M_end()
  2089.                             || !_M_impl._M_key_compare(_S_key(__p),
  2090.                                                        _S_key(__z)));
  2091.  
  2092.       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
  2093.                                     this->_M_impl._M_header);
  2094.       ++_M_impl._M_node_count;
  2095.       return iterator(__z);
  2096.     }
  2097.  
  2098.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2099.            typename _Compare, typename _Alloc>
  2100.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2101.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2102.     _M_insert_equal_lower_node(_Link_type __z)
  2103.     {
  2104.       _Link_type __x = _M_begin();
  2105.       _Link_type __y = _M_end();
  2106.       while (__x != 0)
  2107.         {
  2108.           __y = __x;
  2109.           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
  2110.                 _S_left(__x) : _S_right(__x);
  2111.         }
  2112.       return _M_insert_lower_node(__y, __z);
  2113.     }
  2114.  
  2115.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2116.            typename _Compare, typename _Alloc>
  2117.     template<typename... _Args>
  2118.       pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  2119.                              _Compare, _Alloc>::iterator, bool>
  2120.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2121.       _M_emplace_unique(_Args&&... __args)
  2122.       {
  2123.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  2124.  
  2125.         __try
  2126.           {
  2127.             typedef pair<iterator, bool> _Res;
  2128.             auto __res = _M_get_insert_unique_pos(_S_key(__z));
  2129.             if (__res.second)
  2130.               return _Res(_M_insert_node(__res.first, __res.second, __z), true);
  2131.        
  2132.             _M_drop_node(__z);
  2133.             return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
  2134.           }
  2135.         __catch(...)
  2136.           {
  2137.             _M_drop_node(__z);
  2138.             __throw_exception_again;
  2139.           }
  2140.       }
  2141.  
  2142.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2143.            typename _Compare, typename _Alloc>
  2144.     template<typename... _Args>
  2145.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2146.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2147.       _M_emplace_equal(_Args&&... __args)
  2148.       {
  2149.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  2150.  
  2151.         __try
  2152.           {
  2153.             auto __res = _M_get_insert_equal_pos(_S_key(__z));
  2154.             return _M_insert_node(__res.first, __res.second, __z);
  2155.           }
  2156.         __catch(...)
  2157.           {
  2158.             _M_drop_node(__z);
  2159.             __throw_exception_again;
  2160.           }
  2161.       }
  2162.  
  2163.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2164.            typename _Compare, typename _Alloc>
  2165.     template<typename... _Args>
  2166.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2167.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2168.       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
  2169.       {
  2170.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  2171.  
  2172.         __try
  2173.           {
  2174.             auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
  2175.  
  2176.             if (__res.second)
  2177.               return _M_insert_node(__res.first, __res.second, __z);
  2178.  
  2179.             _M_drop_node(__z);
  2180.             return iterator(static_cast<_Link_type>(__res.first));
  2181.           }
  2182.         __catch(...)
  2183.           {
  2184.             _M_drop_node(__z);
  2185.             __throw_exception_again;
  2186.           }
  2187.       }
  2188.  
  2189.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2190.            typename _Compare, typename _Alloc>
  2191.     template<typename... _Args>
  2192.       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  2193.       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2194.       _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
  2195.       {
  2196.         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
  2197.  
  2198.         __try
  2199.           {
  2200.             auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
  2201.  
  2202.             if (__res.second)
  2203.               return _M_insert_node(__res.first, __res.second, __z);
  2204.  
  2205.             return _M_insert_equal_lower_node(__z);
  2206.           }
  2207.         __catch(...)
  2208.           {
  2209.             _M_drop_node(__z);
  2210.             __throw_exception_again;
  2211.           }
  2212.       }
  2213. #endif
  2214.  
  2215.   template<typename _Key, typename _Val, typename _KoV,
  2216.            typename _Cmp, typename _Alloc>
  2217.     template<class _II>
  2218.       void
  2219.       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
  2220.       _M_insert_unique(_II __first, _II __last)
  2221.       {
  2222.         _Alloc_node __an(*this);
  2223.         for (; __first != __last; ++__first)
  2224.           _M_insert_unique_(end(), *__first, __an);
  2225.       }
  2226.  
  2227.   template<typename _Key, typename _Val, typename _KoV,
  2228.            typename _Cmp, typename _Alloc>
  2229.     template<class _II>
  2230.       void
  2231.       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
  2232.       _M_insert_equal(_II __first, _II __last)
  2233.       {
  2234.         _Alloc_node __an(*this);
  2235.         for (; __first != __last; ++__first)
  2236.           _M_insert_equal_(end(), *__first, __an);
  2237.       }
  2238.  
  2239.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2240.            typename _Compare, typename _Alloc>
  2241.     void
  2242.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2243.     _M_erase_aux(const_iterator __position)
  2244.     {
  2245.       _Link_type __y =
  2246.         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
  2247.                                 (const_cast<_Base_ptr>(__position._M_node),
  2248.                                  this->_M_impl._M_header));
  2249.       _M_drop_node(__y);
  2250.       --_M_impl._M_node_count;
  2251.     }
  2252.  
  2253.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2254.            typename _Compare, typename _Alloc>
  2255.     void
  2256.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2257.     _M_erase_aux(const_iterator __first, const_iterator __last)
  2258.     {
  2259.       if (__first == begin() && __last == end())
  2260.         clear();
  2261.       else
  2262.         while (__first != __last)
  2263.           erase(__first++);
  2264.     }
  2265.  
  2266.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2267.            typename _Compare, typename _Alloc>
  2268.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
  2269.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2270.     erase(const _Key& __x)
  2271.     {
  2272.       pair<iterator, iterator> __p = equal_range(__x);
  2273.       const size_type __old_size = size();
  2274.       erase(__p.first, __p.second);
  2275.       return __old_size - size();
  2276.     }
  2277.  
  2278.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2279.            typename _Compare, typename _Alloc>
  2280.     void
  2281.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2282.     erase(const _Key* __first, const _Key* __last)
  2283.     {
  2284.       while (__first != __last)
  2285.         erase(*__first++);
  2286.     }
  2287.  
  2288.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2289.            typename _Compare, typename _Alloc>
  2290.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  2291.                       _Compare, _Alloc>::iterator
  2292.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2293.     find(const _Key& __k)
  2294.     {
  2295.       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  2296.       return (__j == end()
  2297.               || _M_impl._M_key_compare(__k,
  2298.                                         _S_key(__j._M_node))) ? end() : __j;
  2299.     }
  2300.  
  2301.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2302.            typename _Compare, typename _Alloc>
  2303.     typename _Rb_tree<_Key, _Val, _KeyOfValue,
  2304.                       _Compare, _Alloc>::const_iterator
  2305.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2306.     find(const _Key& __k) const
  2307.     {
  2308.       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  2309.       return (__j == end()
  2310.               || _M_impl._M_key_compare(__k,
  2311.                                         _S_key(__j._M_node))) ? end() : __j;
  2312.     }
  2313.  
  2314.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2315.            typename _Compare, typename _Alloc>
  2316.     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
  2317.     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  2318.     count(const _Key& __k) const
  2319.     {
  2320.       pair<const_iterator, const_iterator> __p = equal_range(__k);
  2321.       const size_type __n = std::distance(__p.first, __p.second);
  2322.       return __n;
  2323.     }
  2324.  
  2325.   _GLIBCXX_PURE unsigned int
  2326.   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
  2327.                        const _Rb_tree_node_base* __root) throw ();
  2328.  
  2329.   template<typename _Key, typename _Val, typename _KeyOfValue,
  2330.            typename _Compare, typename _Alloc>
  2331.     bool
  2332.     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
  2333.     {
  2334.       if (_M_impl._M_node_count == 0 || begin() == end())
  2335.         return _M_impl._M_node_count == 0 && begin() == end()
  2336.                && this->_M_impl._M_header._M_left == _M_end()
  2337.                && this->_M_impl._M_header._M_right == _M_end();
  2338.  
  2339.       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
  2340.       for (const_iterator __it = begin(); __it != end(); ++__it)
  2341.         {
  2342.           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
  2343.           _Const_Link_type __L = _S_left(__x);
  2344.           _Const_Link_type __R = _S_right(__x);
  2345.  
  2346.           if (__x->_M_color == _S_red)
  2347.             if ((__L && __L->_M_color == _S_red)
  2348.                 || (__R && __R->_M_color == _S_red))
  2349.               return false;
  2350.  
  2351.           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
  2352.             return false;
  2353.           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
  2354.             return false;
  2355.  
  2356.           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
  2357.             return false;
  2358.         }
  2359.  
  2360.       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
  2361.         return false;
  2362.       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
  2363.         return false;
  2364.       return true;
  2365.     }
  2366.  
  2367. _GLIBCXX_END_NAMESPACE_VERSION
  2368. } // namespace
  2369.  
  2370. #endif
  2371.