LCOV - code coverage report
Current view: top level - usr/include/c++/4.8/bits - stl_tree.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 221 283 78.1 %
Date: 2013-07-07 Functions: 315 455 69.2 %
Branches: 185 434 42.6 %

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

Generated by: LCOV version 1.9