LCOV - code coverage report
Current view: top level - usr/include/c++/6/bits - stl_tree.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 190 0.0 %
Date: 2018-11-14 16:53:58 Functions: 0 55 0.0 %

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

Generated by: LCOV version 1.13