LCOV - code coverage report
Current view: top level - usr/include/c++/9/bits - stl_tree.h (source / functions) Hit Total Coverage
Test: ROSE Lines: 375 465 80.6 %
Date: 2022-12-08 13:48:47 Functions: 746 2613 28.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14