From 006621455482edd8abf46a05292120745f99f7ec Mon Sep 17 00:00:00 2001 From: Enrico Zini Date: Tue, 29 Sep 2009 15:08:02 +0100 Subject: Initial import --- rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html | 1533 +++++++++++++++++++++ 1 file changed, 1533 insertions(+) create mode 100644 rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html (limited to 'rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html') diff --git a/rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html b/rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html new file mode 100644 index 0000000..9827a27 --- /dev/null +++ b/rep/usr/include/c++/4.3/bits/stl_tree.h.gcov.html @@ -0,0 +1,1533 @@ + + + + + + + LCOV - lcov.info - /usr/include/c++/4.3/bits/stl_tree.h + + + + + + + + + + + + + +
LTP GCOV extension - code coverage report
+ + + + + + + + + + + + + + + + + + + + + + + +
Current view:directory - usr/include/c++/4.3/bits - stl_tree.h
Test:lcov.info
Date:2008-08-14Instrumented lines:295
Code covered:94.2 %Executed lines:278
+
+ + + + + + + + + 

+       1                 : // RB tree implementation -*- C++ -*-
+       2                 : 
+       3                 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
+       4                 : // Free Software Foundation, Inc.
+       5                 : //
+       6                 : // This file is part of the GNU ISO C++ Library.  This library is free
+       7                 : // software; you can redistribute it and/or modify it under the
+       8                 : // terms of the GNU General Public License as published by the
+       9                 : // Free Software Foundation; either version 2, or (at your option)
+      10                 : // any later version.
+      11                 : 
+      12                 : // This library is distributed in the hope that it will be useful,
+      13                 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
+      14                 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+      15                 : // GNU General Public License for more details.
+      16                 : 
+      17                 : // You should have received a copy of the GNU General Public License along
+      18                 : // with this library; see the file COPYING.  If not, write to the Free
+      19                 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+      20                 : // USA.
+      21                 : 
+      22                 : // As a special exception, you may use this file as part of a free software
+      23                 : // library without restriction.  Specifically, if other files instantiate
+      24                 : // templates or use macros or inline functions from this file, or you compile
+      25                 : // this file and link it with other files to produce an executable, this
+      26                 : // file does not by itself cause the resulting executable to be covered by
+      27                 : // the GNU General Public License.  This exception does not however
+      28                 : // invalidate any other reasons why the executable file might be covered by
+      29                 : // the GNU General Public License.
+      30                 : 
+      31                 : /*
+      32                 :  *
+      33                 :  * Copyright (c) 1996,1997
+      34                 :  * Silicon Graphics Computer Systems, Inc.
+      35                 :  *
+      36                 :  * Permission to use, copy, modify, distribute and sell this software
+      37                 :  * and its documentation for any purpose is hereby granted without fee,
+      38                 :  * provided that the above copyright notice appear in all copies and
+      39                 :  * that both that copyright notice and this permission notice appear
+      40                 :  * in supporting documentation.  Silicon Graphics makes no
+      41                 :  * representations about the suitability of this software for any
+      42                 :  * purpose.  It is provided "as is" without express or implied warranty.
+      43                 :  *
+      44                 :  *
+      45                 :  * Copyright (c) 1994
+      46                 :  * Hewlett-Packard Company
+      47                 :  *
+      48                 :  * Permission to use, copy, modify, distribute and sell this software
+      49                 :  * and its documentation for any purpose is hereby granted without fee,
+      50                 :  * provided that the above copyright notice appear in all copies and
+      51                 :  * that both that copyright notice and this permission notice appear
+      52                 :  * in supporting documentation.  Hewlett-Packard Company makes no
+      53                 :  * representations about the suitability of this software for any
+      54                 :  * purpose.  It is provided "as is" without express or implied warranty.
+      55                 :  *
+      56                 :  *
+      57                 :  */
+      58                 : 
+      59                 : /** @file stl_tree.h
+      60                 :  *  This is an internal header file, included by other library headers.
+      61                 :  *  You should not attempt to use it directly.
+      62                 :  */
+      63                 : 
+      64                 : #ifndef _STL_TREE_H
+      65                 : #define _STL_TREE_H 1
+      66                 : 
+      67                 : #include <bits/stl_algobase.h>
+      68                 : #include <bits/allocator.h>
+      69                 : #include <bits/stl_function.h>
+      70                 : #include <bits/cpp_type_traits.h>
+      71                 : 
+      72                 : _GLIBCXX_BEGIN_NAMESPACE(std)
+      73                 : 
+      74                 :   // Red-black tree class, designed for use in implementing STL
+      75                 :   // associative containers (set, multiset, map, and multimap). The
+      76                 :   // insertion and deletion algorithms are based on those in Cormen,
+      77                 :   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
+      78                 :   // 1990), except that
+      79                 :   //
+      80                 :   // (1) the header cell is maintained with links not only to the root
+      81                 :   // but also to the leftmost node of the tree, to enable constant
+      82                 :   // time begin(), and to the rightmost node of the tree, to enable
+      83                 :   // linear time performance when used with the generic set algorithms
+      84                 :   // (set_union, etc.)
+      85                 :   // 
+      86                 :   // (2) when a node being deleted has two children its successor node
+      87                 :   // is relinked into its place, rather than copied, so that the only
+      88                 :   // iterators invalidated are those referring to the deleted node.
+      89                 : 
+      90                 :   enum _Rb_tree_color { _S_red = false, _S_black = true };
+      91                 : 
+      92                 :   struct _Rb_tree_node_base
+      93                 :   {
+      94                 :     typedef _Rb_tree_node_base* _Base_ptr;
+      95                 :     typedef const _Rb_tree_node_base* _Const_Base_ptr;
+      96                 : 
+      97                 :     _Rb_tree_color      _M_color;
+      98                 :     _Base_ptr           _M_parent;
+      99                 :     _Base_ptr           _M_left;
+     100                 :     _Base_ptr           _M_right;
+     101                 : 
+     102                 :     static _Base_ptr
+     103          880633 :     _S_minimum(_Base_ptr __x)
+     104                 :     {
+     105          880633 :       while (__x->_M_left != 0) __x = __x->_M_left;
+     106          880633 :       return __x;
+     107                 :     }
+     108                 : 
+     109                 :     static _Const_Base_ptr
+     110                 :     _S_minimum(_Const_Base_ptr __x)
+     111                 :     {
+     112                 :       while (__x->_M_left != 0) __x = __x->_M_left;
+     113                 :       return __x;
+     114                 :     }
+     115                 : 
+     116                 :     static _Base_ptr
+     117          880633 :     _S_maximum(_Base_ptr __x)
+     118                 :     {
+     119          880633 :       while (__x->_M_right != 0) __x = __x->_M_right;
+     120          880633 :       return __x;
+     121                 :     }
+     122                 : 
+     123                 :     static _Const_Base_ptr
+     124                 :     _S_maximum(_Const_Base_ptr __x)
+     125                 :     {
+     126                 :       while (__x->_M_right != 0) __x = __x->_M_right;
+     127                 :       return __x;
+     128                 :     }
+     129                 :   };
+     130                 : 
+     131                 :   template<typename _Val>
+     132                 :     struct _Rb_tree_node : public _Rb_tree_node_base
+     133                 :     {
+     134                 :       typedef _Rb_tree_node<_Val>* _Link_type;
+     135                 :       _Val _M_value_field;
+     136                 :     };
+     137                 : 
+     138                 :   _Rb_tree_node_base*
+     139                 :   _Rb_tree_increment(_Rb_tree_node_base* __x);
+     140                 : 
+     141                 :   const _Rb_tree_node_base*
+     142                 :   _Rb_tree_increment(const _Rb_tree_node_base* __x);
+     143                 : 
+     144                 :   _Rb_tree_node_base*
+     145                 :   _Rb_tree_decrement(_Rb_tree_node_base* __x);
+     146                 : 
+     147                 :   const _Rb_tree_node_base*
+     148                 :   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
+     149                 : 
+     150                 :   template<typename _Tp>
+     151                 :     struct _Rb_tree_iterator
+     152                 :     {
+     153                 :       typedef _Tp  value_type;
+     154                 :       typedef _Tp& reference;
+     155                 :       typedef _Tp* pointer;
+     156                 : 
+     157                 :       typedef bidirectional_iterator_tag iterator_category;
+     158                 :       typedef ptrdiff_t                  difference_type;
+     159                 : 
+     160                 :       typedef _Rb_tree_iterator<_Tp>        _Self;
+     161                 :       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
+     162                 :       typedef _Rb_tree_node<_Tp>*           _Link_type;
+     163                 : 
+     164                 :       _Rb_tree_iterator()
+     165                 :       : _M_node() { }
+     166                 : 
+     167                 :       explicit
+     168         4550329 :       _Rb_tree_iterator(_Link_type __x)
+     169         4550329 :       : _M_node(__x) { }
+     170                 : 
+     171                 :       reference
+     172            9593 :       operator*() const
+     173            9593 :       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
+     174                 : 
+     175                 :       pointer
+     176           32985 :       operator->() const
+     177           32985 :       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
+     178                 : 
+     179                 :       _Self&
+     180                 :       operator++()
+     181                 :       {
+     182                 :         _M_node = _Rb_tree_increment(_M_node);
+     183                 :         return *this;
+     184                 :       }
+     185                 : 
+     186                 :       _Self
+     187             658 :       operator++(int)
+     188                 :       {
+     189             658 :         _Self __tmp = *this;
+     190             658 :         _M_node = _Rb_tree_increment(_M_node);
+     191                 :         return __tmp;
+     192                 :       }
+     193                 : 
+     194                 :       _Self&
+     195           83333 :       operator--()
+     196                 :       {
+     197           83333 :         _M_node = _Rb_tree_decrement(_M_node);
+     198           83333 :         return *this;
+     199                 :       }
+     200                 : 
+     201                 :       _Self
+     202                 :       operator--(int)
+     203                 :       {
+     204                 :         _Self __tmp = *this;
+     205                 :         _M_node = _Rb_tree_decrement(_M_node);
+     206                 :         return __tmp;
+     207                 :       }
+     208                 : 
+     209                 :       bool
+     210          638793 :       operator==(const _Self& __x) const
+     211          638793 :       { return _M_node == __x._M_node; }
+     212                 : 
+     213                 :       bool
+     214             749 :       operator!=(const _Self& __x) const
+     215             749 :       { return _M_node != __x._M_node; }
+     216                 : 
+     217                 :       _Base_ptr _M_node;
+     218                 :   };
+     219                 : 
+     220                 :   template<typename _Tp>
+     221                 :     struct _Rb_tree_const_iterator
+     222                 :     {
+     223                 :       typedef _Tp        value_type;
+     224                 :       typedef const _Tp& reference;
+     225                 :       typedef const _Tp* pointer;
+     226                 : 
+     227                 :       typedef _Rb_tree_iterator<_Tp> iterator;
+     228                 : 
+     229                 :       typedef bidirectional_iterator_tag iterator_category;
+     230                 :       typedef ptrdiff_t                  difference_type;
+     231                 : 
+     232                 :       typedef _Rb_tree_const_iterator<_Tp>        _Self;
+     233                 :       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
+     234                 :       typedef const _Rb_tree_node<_Tp>*           _Link_type;
+     235                 : 
+     236                 :       _Rb_tree_const_iterator()
+     237                 :       : _M_node() { }
+     238                 : 
+     239                 :       explicit
+     240         2494703 :       _Rb_tree_const_iterator(_Link_type __x)
+     241         2494703 :       : _M_node(__x) { }
+     242                 : 
+     243         1643427 :       _Rb_tree_const_iterator(const iterator& __it)
+     244         1643427 :       : _M_node(__it._M_node) { }
+     245                 : 
+     246                 :       reference
+     247         1553025 :       operator*() const
+     248         1553025 :       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
+     249                 : 
+     250                 :       pointer
+     251          817027 :       operator->() const
+     252          817027 :       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
+     253                 : 
+     254                 :       _Self&
+     255         1717591 :       operator++()
+     256                 :       {
+     257         1717591 :         _M_node = _Rb_tree_increment(_M_node);
+     258         1717591 :         return *this;
+     259                 :       }
+     260                 : 
+     261                 :       _Self
+     262            9048 :       operator++(int)
+     263                 :       {
+     264            9048 :         _Self __tmp = *this;
+     265            9048 :         _M_node = _Rb_tree_increment(_M_node);
+     266                 :         return __tmp;
+     267                 :       }
+     268                 : 
+     269                 :       _Self&
+     270            2000 :       operator--()
+     271                 :       {
+     272            2000 :         _M_node = _Rb_tree_decrement(_M_node);
+     273            2000 :         return *this;
+     274                 :       }
+     275                 : 
+     276                 :       _Self
+     277                 :       operator--(int)
+     278                 :       {
+     279                 :         _Self __tmp = *this;
+     280                 :         _M_node = _Rb_tree_decrement(_M_node);
+     281                 :         return __tmp;
+     282                 :       }
+     283                 : 
+     284                 :       bool
+     285          177758 :       operator==(const _Self& __x) const
+     286          177758 :       { return _M_node == __x._M_node; }
+     287                 : 
+     288                 :       bool
+     289         2095612 :       operator!=(const _Self& __x) const
+     290         2095612 :       { return _M_node != __x._M_node; }
+     291                 : 
+     292                 :       _Base_ptr _M_node;
+     293                 :     };
+     294                 : 
+     295                 :   template<typename _Val>
+     296                 :     inline bool
+     297                 :     operator==(const _Rb_tree_iterator<_Val>& __x,
+     298                 :                const _Rb_tree_const_iterator<_Val>& __y)
+     299                 :     { return __x._M_node == __y._M_node; }
+     300                 : 
+     301                 :   template<typename _Val>
+     302                 :     inline bool
+     303                 :     operator!=(const _Rb_tree_iterator<_Val>& __x,
+     304                 :                const _Rb_tree_const_iterator<_Val>& __y)
+     305                 :     { return __x._M_node != __y._M_node; }
+     306                 : 
+     307                 :   void
+     308                 :   _Rb_tree_insert_and_rebalance(const bool __insert_left,
+     309                 :                                 _Rb_tree_node_base* __x,
+     310                 :                                 _Rb_tree_node_base* __p,
+     311                 :                                 _Rb_tree_node_base& __header);
+     312                 : 
+     313                 :   _Rb_tree_node_base*
+     314                 :   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
+     315                 :                                _Rb_tree_node_base& __header);
+     316                 : 
+     317                 : 
+     318                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     319                 :            typename _Compare, typename _Alloc = allocator<_Val> >
+     320                 :     class _Rb_tree
+     321                 :     {
+     322                 :       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
+     323                 :               _Node_allocator;
+     324                 : 
+     325                 :     protected:
+     326                 :       typedef _Rb_tree_node_base* _Base_ptr;
+     327                 :       typedef const _Rb_tree_node_base* _Const_Base_ptr;
+     328                 : 
+     329                 :     public:
+     330                 :       typedef _Key key_type;
+     331                 :       typedef _Val value_type;
+     332                 :       typedef value_type* pointer;
+     333                 :       typedef const value_type* const_pointer;
+     334                 :       typedef value_type& reference;
+     335                 :       typedef const value_type& const_reference;
+     336                 :       typedef _Rb_tree_node<_Val>* _Link_type;
+     337                 :       typedef const _Rb_tree_node<_Val>* _Const_Link_type;
+     338                 :       typedef size_t size_type;
+     339                 :       typedef ptrdiff_t difference_type;
+     340                 :       typedef _Alloc allocator_type;
+     341                 : 
+     342                 :       _Node_allocator&
+     343                 :       _M_get_Node_allocator()
+     344                 :       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
+     345                 :       
+     346                 :       const _Node_allocator&
+     347        12223942 :       _M_get_Node_allocator() const
+     348        12223942 :       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
+     349                 : 
+     350                 :       allocator_type
+     351        11289346 :       get_allocator() const
+     352        11289346 :       { return allocator_type(_M_get_Node_allocator()); }
+     353                 : 
+     354                 :     protected:
+     355                 :       _Link_type
+     356         5644688 :       _M_get_node()
+     357         5644688 :       { return _M_impl._Node_allocator::allocate(1); }
+     358                 : 
+     359                 :       void
+     360         5644658 :       _M_put_node(_Link_type __p)
+     361         5644658 :       { _M_impl._Node_allocator::deallocate(__p, 1); }
+     362                 : 
+     363                 :       _Link_type
+     364         5644688 :       _M_create_node(const value_type& __x)
+     365                 :       {
+     366         5644688 :         _Link_type __tmp = _M_get_node();
+     367                 :         try
+     368         5644688 :           { get_allocator().construct(&__tmp->_M_value_field, __x); }
+     369               0 :         catch(...)
+     370                 :           {
+     371               0 :             _M_put_node(__tmp);
+     372               0 :             __throw_exception_again;
+     373                 :           }
+     374         5644688 :         return __tmp;
+     375                 :       }
+     376                 : 
+     377                 :       _Link_type
+     378         3573982 :       _M_clone_node(_Const_Link_type __x)
+     379                 :       {
+     380         3573982 :         _Link_type __tmp = _M_create_node(__x->_M_value_field);
+     381         3573982 :         __tmp->_M_color = __x->_M_color;
+     382         3573982 :         __tmp->_M_left = 0;
+     383         3573982 :         __tmp->_M_right = 0;
+     384         3573982 :         return __tmp;
+     385                 :       }
+     386                 : 
+     387                 :       void
+     388         5644658 :       _M_destroy_node(_Link_type __p)
+     389                 :       {
+     390         5644658 :         get_allocator().destroy(&__p->_M_value_field);
+     391         5644658 :         _M_put_node(__p);
+     392         5644658 :       }
+     393                 : 
+     394                 :     protected:
+     395                 :       template<typename _Key_compare, 
+     396                 :                bool _Is_pod_comparator = __is_pod(_Key_compare)>
+     397                 :         struct _Rb_tree_impl : public _Node_allocator
+     398         1320929 :         {
+     399                 :           _Key_compare          _M_key_compare;
+     400                 :           _Rb_tree_node_base    _M_header;
+     401                 :           size_type             _M_node_count; // Keeps track of size of tree.
+     402                 : 
+     403          280599 :           _Rb_tree_impl()
+     404                 :           : _Node_allocator(), _M_key_compare(), _M_header(),
+     405          280599 :             _M_node_count(0)
+     406          280599 :           { _M_initialize(); }
+     407                 : 
+     408          934596 :           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
+     409                 :           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
+     410          934596 :             _M_node_count(0)
+     411          934596 :           { _M_initialize(); }
+     412                 : 
+     413                 :         private:
+     414                 :           void
+     415         1215195 :           _M_initialize()
+     416                 :           {
+     417         1215195 :             this->_M_header._M_color = _S_red;
+     418         1215195 :             this->_M_header._M_parent = 0;
+     419         1215195 :             this->_M_header._M_left = &this->_M_header;
+     420         1215195 :             this->_M_header._M_right = &this->_M_header;
+     421         1215195 :           }         
+     422                 :         };
+     423                 : 
+     424                 :       _Rb_tree_impl<_Compare> _M_impl;
+     425                 : 
+     426                 :     protected:
+     427                 :       _Base_ptr&
+     428         2729891 :       _M_root()
+     429         2729891 :       { return this->_M_impl._M_header._M_parent; }
+     430                 : 
+     431                 :       _Const_Base_ptr
+     432          934693 :       _M_root() const
+     433          934693 :       { return this->_M_impl._M_header._M_parent; }
+     434                 : 
+     435                 :       _Base_ptr&
+     436          970809 :       _M_leftmost()
+     437          970809 :       { return this->_M_impl._M_header._M_left; }
+     438                 : 
+     439                 :       _Const_Base_ptr
+     440                 :       _M_leftmost() const
+     441                 :       { return this->_M_impl._M_header._M_left; }
+     442                 : 
+     443                 :       _Base_ptr&
+     444         2012568 :       _M_rightmost()
+     445         2012568 :       { return this->_M_impl._M_header._M_right; }
+     446                 : 
+     447                 :       _Const_Base_ptr
+     448                 :       _M_rightmost() const
+     449                 :       { return this->_M_impl._M_header._M_right; }
+     450                 : 
+     451                 :       _Link_type
+     452         3119123 :       _M_begin()
+     453         3119123 :       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
+     454                 : 
+     455                 :       _Const_Link_type
+     456          884565 :       _M_begin() const
+     457                 :       {
+     458                 :         return static_cast<_Const_Link_type>
+     459          884565 :           (this->_M_impl._M_header._M_parent);
+     460                 :       }
+     461                 : 
+     462                 :       _Link_type
+     463         5489610 :       _M_end()
+     464         5489610 :       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
+     465                 : 
+     466                 :       _Const_Link_type
+     467            3932 :       _M_end() const
+     468            3932 :       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
+     469                 : 
+     470                 :       static const_reference
+     471         7342455 :       _S_value(_Const_Link_type __x)
+     472         7342455 :       { return __x->_M_value_field; }
+     473                 : 
+     474                 :       static const _Key&
+     475         7342455 :       _S_key(_Const_Link_type __x)
+     476         7342455 :       { return _KeyOfValue()(_S_value(__x)); }
+     477                 : 
+     478                 :       static _Link_type
+     479         6468290 :       _S_left(_Base_ptr __x)
+     480         6468290 :       { return static_cast<_Link_type>(__x->_M_left); }
+     481                 : 
+     482                 :       static _Const_Link_type
+     483         3579867 :       _S_left(_Const_Base_ptr __x)
+     484         3579867 :       { return static_cast<_Const_Link_type>(__x->_M_left); }
+     485                 : 
+     486                 :       static _Link_type
+     487        12155056 :       _S_right(_Base_ptr __x)
+     488        12155056 :       { return static_cast<_Link_type>(__x->_M_right); }
+     489                 : 
+     490                 :       static _Const_Link_type
+     491         1503831 :       _S_right(_Const_Base_ptr __x)
+     492         1503831 :       { return static_cast<_Const_Link_type>(__x->_M_right); }
+     493                 : 
+     494                 :       static const_reference
+     495         3381491 :       _S_value(_Const_Base_ptr __x)
+     496         3381491 :       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
+     497                 : 
+     498                 :       static const _Key&
+     499         3381491 :       _S_key(_Const_Base_ptr __x)
+     500         3381491 :       { return _KeyOfValue()(_S_value(__x)); }
+     501                 : 
+     502                 :       static _Base_ptr
+     503          880633 :       _S_minimum(_Base_ptr __x)
+     504          880633 :       { return _Rb_tree_node_base::_S_minimum(__x); }
+     505                 : 
+     506                 :       static _Const_Base_ptr
+     507                 :       _S_minimum(_Const_Base_ptr __x)
+     508                 :       { return _Rb_tree_node_base::_S_minimum(__x); }
+     509                 : 
+     510                 :       static _Base_ptr
+     511          880633 :       _S_maximum(_Base_ptr __x)
+     512          880633 :       { return _Rb_tree_node_base::_S_maximum(__x); }
+     513                 : 
+     514                 :       static _Const_Base_ptr
+     515                 :       _S_maximum(_Const_Base_ptr __x)
+     516                 :       { return _Rb_tree_node_base::_S_maximum(__x); }
+     517                 : 
+     518                 :     public:
+     519                 :       typedef _Rb_tree_iterator<value_type>       iterator;
+     520                 :       typedef _Rb_tree_const_iterator<value_type> const_iterator;
+     521                 : 
+     522                 :       typedef std::reverse_iterator<iterator>       reverse_iterator;
+     523                 :       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+     524                 : 
+     525                 :     private:
+     526                 :       iterator
+     527                 :       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
+     528                 :                  const value_type& __v);
+     529                 : 
+     530                 :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
+     531                 :       // 233. Insertion hints in associative containers.
+     532                 :       iterator
+     533                 :       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
+     534                 : 
+     535                 :       iterator
+     536                 :       _M_insert_equal_lower(const value_type& __x);
+     537                 : 
+     538                 :       _Link_type
+     539                 :       _M_copy(_Const_Link_type __x, _Link_type __p);
+     540                 : 
+     541                 :       void
+     542                 :       _M_erase(_Link_type __x);
+     543                 : 
+     544                 :       iterator
+     545                 :       _M_lower_bound(_Link_type __x, _Link_type __y,
+     546                 :                      const _Key& __k);
+     547                 : 
+     548                 :       const_iterator
+     549                 :       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
+     550                 :                      const _Key& __k) const;
+     551                 : 
+     552                 :       iterator
+     553                 :       _M_upper_bound(_Link_type __x, _Link_type __y,
+     554                 :                      const _Key& __k);
+     555                 : 
+     556                 :       const_iterator
+     557                 :       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
+     558                 :                      const _Key& __k) const;
+     559                 : 
+     560                 :     public:
+     561                 :       // allocation/deallocation
+     562          280599 :       _Rb_tree() { }
+     563                 : 
+     564                 :       _Rb_tree(const _Compare& __comp,
+     565                 :                const allocator_type& __a = allocator_type())
+     566                 :       : _M_impl(__comp, __a) { }
+     567                 : 
+     568          934596 :       _Rb_tree(const _Rb_tree& __x)
+     569          934596 :       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
+     570                 :       {
+     571          934596 :         if (__x._M_root() != 0)
+     572                 :           {
+     573          880580 :             _M_root() = _M_copy(__x._M_begin(), _M_end());
+     574          880580 :             _M_leftmost() = _S_minimum(_M_root());
+     575          880580 :             _M_rightmost() = _S_maximum(_M_root());
+     576          880580 :             _M_impl._M_node_count = __x._M_impl._M_node_count;
+     577                 :           }
+     578          934596 :       }
+     579                 : 
+     580                 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
+     581                 :       _Rb_tree(_Rb_tree&& __x);
+     582                 : #endif
+     583                 : 
+     584         1320929 :       ~_Rb_tree()
+     585         1320929 :       { _M_erase(_M_begin()); }
+     586                 : 
+     587                 :       _Rb_tree&
+     588                 :       operator=(const _Rb_tree& __x);
+     589                 : 
+     590                 :       // Accessors.
+     591                 :       _Compare
+     592            3296 :       key_comp() const
+     593            3296 :       { return _M_impl._M_key_compare; }
+     594                 : 
+     595                 :       iterator
+     596          538878 :       begin()
+     597                 :       { 
+     598                 :         return iterator(static_cast<_Link_type>
+     599          538878 :                         (this->_M_impl._M_header._M_left));
+     600                 :       }
+     601                 : 
+     602                 :       const_iterator
+     603          468185 :       begin() const
+     604                 :       { 
+     605                 :         return const_iterator(static_cast<_Const_Link_type>
+     606          468185 :                               (this->_M_impl._M_header._M_left));
+     607                 :       }
+     608                 : 
+     609                 :       iterator
+     610          230534 :       end()
+     611          230534 :       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
+     612                 : 
+     613                 :       const_iterator
+     614         2022586 :       end() const
+     615                 :       { 
+     616                 :         return const_iterator(static_cast<_Const_Link_type>
+     617         2022586 :                               (&this->_M_impl._M_header));
+     618                 :       }
+     619                 : 
+     620                 :       reverse_iterator
+     621                 :       rbegin()
+     622                 :       { return reverse_iterator(end()); }
+     623                 : 
+     624                 :       const_reverse_iterator
+     625              32 :       rbegin() const
+     626              32 :       { return const_reverse_iterator(end()); }
+     627                 : 
+     628                 :       reverse_iterator
+     629                 :       rend()
+     630                 :       { return reverse_iterator(begin()); }
+     631                 : 
+     632                 :       const_reverse_iterator
+     633                 :       rend() const
+     634                 :       { return const_reverse_iterator(begin()); }
+     635                 : 
+     636                 :       bool
+     637          342325 :       empty() const
+     638          342325 :       { return _M_impl._M_node_count == 0; }
+     639                 : 
+     640                 :       size_type
+     641          734435 :       size() const
+     642          734435 :       { return _M_impl._M_node_count; }
+     643                 : 
+     644                 :       size_type
+     645                 :       max_size() const
+     646                 :       { return get_allocator().max_size(); }
+     647                 : 
+     648                 :       void
+     649                 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
+     650                 :       swap(_Rb_tree&& __t);
+     651                 : #else
+     652                 :       swap(_Rb_tree& __t);      
+     653                 : #endif
+     654                 : 
+     655                 :       // Insert/erase.
+     656                 :       pair<iterator, bool>
+     657                 :       _M_insert_unique(const value_type& __x);
+     658                 : 
+     659                 :       iterator
+     660                 :       _M_insert_equal(const value_type& __x);
+     661                 : 
+     662                 :       iterator
+     663                 :       _M_insert_unique_(const_iterator __position, const value_type& __x);
+     664                 : 
+     665                 :       iterator
+     666                 :       _M_insert_equal_(const_iterator __position, const value_type& __x);
+     667                 : 
+     668                 :       template<typename _InputIterator>
+     669                 :         void
+     670                 :         _M_insert_unique(_InputIterator __first, _InputIterator __last);
+     671                 : 
+     672                 :       template<typename _InputIterator>
+     673                 :         void
+     674                 :         _M_insert_equal(_InputIterator __first, _InputIterator __last);
+     675                 : 
+     676                 :       void
+     677                 :       erase(iterator __position);
+     678                 : 
+     679                 :       void
+     680                 :       erase(const_iterator __position);
+     681                 : 
+     682                 :       size_type
+     683                 :       erase(const key_type& __x);
+     684                 : 
+     685                 :       void
+     686                 :       erase(iterator __first, iterator __last);
+     687                 : 
+     688                 :       void
+     689                 :       erase(const_iterator __first, const_iterator __last);
+     690                 : 
+     691                 :       void
+     692                 :       erase(const key_type* __first, const key_type* __last);
+     693                 : 
+     694                 :       void
+     695           87992 :       clear()
+     696                 :       {
+     697           87992 :         _M_erase(_M_begin());
+     698           87992 :         _M_leftmost() = _M_end();
+     699           87992 :         _M_root() = 0;
+     700           87992 :         _M_rightmost() = _M_end();
+     701           87992 :         _M_impl._M_node_count = 0;
+     702           87992 :       }
+     703                 : 
+     704                 :       // Set operations.
+     705                 :       iterator
+     706                 :       find(const key_type& __k);
+     707                 : 
+     708                 :       const_iterator
+     709                 :       find(const key_type& __k) const;
+     710                 : 
+     711                 :       size_type
+     712                 :       count(const key_type& __k) const;
+     713                 : 
+     714                 :       iterator
+     715            6297 :       lower_bound(const key_type& __k)
+     716            6297 :       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+     717                 : 
+     718                 :       const_iterator
+     719                 :       lower_bound(const key_type& __k) const
+     720                 :       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+     721                 : 
+     722                 :       iterator
+     723                 :       upper_bound(const key_type& __k)
+     724                 :       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+     725                 : 
+     726                 :       const_iterator
+     727                 :       upper_bound(const key_type& __k) const
+     728                 :       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+     729                 : 
+     730                 :       pair<iterator, iterator>
+     731                 :       equal_range(const key_type& __k);
+     732                 : 
+     733                 :       pair<const_iterator, const_iterator>
+     734                 :       equal_range(const key_type& __k) const;
+     735                 : 
+     736                 :       // Debugging.
+     737                 :       bool
+     738                 :       __rb_verify() const;
+     739                 :     };
+     740                 : 
+     741                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     742                 :            typename _Compare, typename _Alloc>
+     743                 :     inline bool
+     744                 :     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     745               4 :                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     746                 :     {
+     747                 :       return __x.size() == __y.size()
+     748               4 :              && std::equal(__x.begin(), __x.end(), __y.begin());
+     749                 :     }
+     750                 : 
+     751                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     752                 :            typename _Compare, typename _Alloc>
+     753                 :     inline bool
+     754                 :     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     755                 :               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     756                 :     {
+     757                 :       return std::lexicographical_compare(__x.begin(), __x.end(), 
+     758                 :                                           __y.begin(), __y.end());
+     759                 :     }
+     760                 : 
+     761                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     762                 :            typename _Compare, typename _Alloc>
+     763                 :     inline bool
+     764                 :     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     765                 :                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     766                 :     { return !(__x == __y); }
+     767                 : 
+     768                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     769                 :            typename _Compare, typename _Alloc>
+     770                 :     inline bool
+     771                 :     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     772                 :               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     773                 :     { return __y < __x; }
+     774                 : 
+     775                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     776                 :            typename _Compare, typename _Alloc>
+     777                 :     inline bool
+     778                 :     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     779                 :                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     780                 :     { return !(__y < __x); }
+     781                 : 
+     782                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     783                 :            typename _Compare, typename _Alloc>
+     784                 :     inline bool
+     785                 :     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     786                 :                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     787                 :     { return !(__x < __y); }
+     788                 : 
+     789                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     790                 :            typename _Compare, typename _Alloc>
+     791                 :     inline void
+     792                 :     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+     793                 :          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
+     794                 :     { __x.swap(__y); }
+     795                 : 
+     796                 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
+     797                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     798                 :            typename _Compare, typename _Alloc>
+     799                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     800                 :     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
+     801                 :     : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
+     802                 :     {
+     803                 :       if (__x._M_root() != 0)
+     804                 :         {
+     805                 :           _M_root() = __x._M_root();
+     806                 :           _M_leftmost() = __x._M_leftmost();
+     807                 :           _M_rightmost() = __x._M_rightmost();
+     808                 :           _M_root()->_M_parent = _M_end();
+     809                 : 
+     810                 :           __x._M_root() = 0;
+     811                 :           __x._M_leftmost() = __x._M_end();
+     812                 :           __x._M_rightmost() = __x._M_end();
+     813                 : 
+     814                 :           this->_M_impl._M_node_count = __x._M_impl._M_node_count;
+     815                 :           __x._M_impl._M_node_count = 0;
+     816                 :         }
+     817                 :     }
+     818                 : #endif
+     819                 : 
+     820                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     821                 :            typename _Compare, typename _Alloc>
+     822                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
+     823                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     824              97 :     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
+     825                 :     {
+     826              97 :       if (this != &__x)
+     827                 :         {
+     828                 :           // Note that _Key may be a constant type.
+     829              97 :           clear();
+     830              97 :           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
+     831              97 :           if (__x._M_root() != 0)
+     832                 :             {
+     833              53 :               _M_root() = _M_copy(__x._M_begin(), _M_end());
+     834              53 :               _M_leftmost() = _S_minimum(_M_root());
+     835              53 :               _M_rightmost() = _S_maximum(_M_root());
+     836              53 :               _M_impl._M_node_count = __x._M_impl._M_node_count;
+     837                 :             }
+     838                 :         }
+     839              97 :       return *this;
+     840                 :     }
+     841                 : 
+     842                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     843                 :            typename _Compare, typename _Alloc>
+     844                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+     845                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     846         2070706 :     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
+     847                 :     {
+     848                 :       bool __insert_left = (__x != 0 || __p == _M_end()
+     849                 :                             || _M_impl._M_key_compare(_KeyOfValue()(__v), 
+     850         2070706 :                                                       _S_key(__p)));
+     851                 : 
+     852         2070706 :       _Link_type __z = _M_create_node(__v);
+     853                 : 
+     854         2070706 :       _Rb_tree_insert_and_rebalance(__insert_left, __z,
+     855                 :                                     const_cast<_Base_ptr>(__p),  
+     856                 :                                     this->_M_impl._M_header);
+     857         2070706 :       ++_M_impl._M_node_count;
+     858         2070706 :       return iterator(__z);
+     859                 :     }
+     860                 : 
+     861                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     862                 :            typename _Compare, typename _Alloc>
+     863                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+     864                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     865                 :     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+     866                 :     {
+     867                 :       bool __insert_left = (__x != 0 || __p == _M_end()
+     868                 :                             || !_M_impl._M_key_compare(_S_key(__p),
+     869                 :                                                        _KeyOfValue()(__v)));
+     870                 : 
+     871                 :       _Link_type __z = _M_create_node(__v);
+     872                 : 
+     873                 :       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
+     874                 :                                     this->_M_impl._M_header);
+     875                 :       ++_M_impl._M_node_count;
+     876                 :       return iterator(__z);
+     877                 :     }
+     878                 : 
+     879                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     880                 :            typename _Compare, typename _Alloc>
+     881                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+     882                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     883                 :     _M_insert_equal_lower(const _Val& __v)
+     884                 :     {
+     885                 :       _Link_type __x = _M_begin();
+     886                 :       _Link_type __y = _M_end();
+     887                 :       while (__x != 0)
+     888                 :         {
+     889                 :           __y = __x;
+     890                 :           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+     891                 :                 _S_left(__x) : _S_right(__x);
+     892                 :         }
+     893                 :       return _M_insert_lower(__x, __y, __v);
+     894                 :     }
+     895                 : 
+     896                 :   template<typename _Key, typename _Val, typename _KoV,
+     897                 :            typename _Compare, typename _Alloc>
+     898                 :     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
+     899                 :     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
+     900         2381075 :     _M_copy(_Const_Link_type __x, _Link_type __p)
+     901                 :     {
+     902                 :       // Structural copy.  __x and __p must be non-null.
+     903         2381075 :       _Link_type __top = _M_clone_node(__x);
+     904         2381075 :       __top->_M_parent = __p;
+     905                 : 
+     906                 :       try
+     907                 :         {
+     908         2381075 :           if (__x->_M_right)
+     909         1355924 :             __top->_M_right = _M_copy(_S_right(__x), __top);
+     910         2381075 :           __p = __top;
+     911         2381075 :           __x = _S_left(__x);
+     912                 : 
+     913         5955057 :           while (__x != 0)
+     914                 :             {
+     915         1192907 :               _Link_type __y = _M_clone_node(__x);
+     916         1192907 :               __p->_M_left = __y;
+     917         1192907 :               __y->_M_parent = __p;
+     918         1192907 :               if (__x->_M_right)
+     919          144518 :                 __y->_M_right = _M_copy(_S_right(__x), __y);
+     920         1192907 :               __p = __y;
+     921         1192907 :               __x = _S_left(__x);
+     922                 :             }
+     923                 :         }
+     924               0 :       catch(...)
+     925                 :         {
+     926               0 :           _M_erase(__top);
+     927               0 :           __throw_exception_again;
+     928                 :         }
+     929         2381075 :       return __top;
+     930                 :     }
+     931                 : 
+     932                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     933                 :            typename _Compare, typename _Alloc>
+     934                 :     void
+     935                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     936         7053477 :     _M_erase(_Link_type __x)
+     937                 :     {
+     938                 :       // Erase without rebalancing.
+     939        19751483 :       while (__x != 0)
+     940                 :         {
+     941         5644529 :           _M_erase(_S_right(__x));
+     942         5644529 :           _Link_type __y = _S_left(__x);
+     943         5644529 :           _M_destroy_node(__x);
+     944         5644529 :           __x = __y;
+     945                 :         }
+     946         7053477 :     }
+     947                 : 
+     948                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     949                 :            typename _Compare, typename _Alloc>
+     950                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
+     951                 :                       _Compare, _Alloc>::iterator
+     952                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     953                 :     _M_lower_bound(_Link_type __x, _Link_type __y,
+     954           56455 :                    const _Key& __k)
+     955                 :     {
+     956          956283 :       while (__x != 0)
+     957          843373 :         if (!_M_impl._M_key_compare(_S_key(__x), __k))
+     958          159236 :           __y = __x, __x = _S_left(__x);
+     959                 :         else
+     960          684137 :           __x = _S_right(__x);
+     961           56455 :       return iterator(__y);
+     962                 :     }
+     963                 : 
+     964                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     965                 :            typename _Compare, typename _Alloc>
+     966                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
+     967                 :                       _Compare, _Alloc>::const_iterator
+     968                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     969                 :     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
+     970            3932 :                    const _Key& __k) const
+     971                 :     {
+     972           16029 :       while (__x != 0)
+     973            8165 :         if (!_M_impl._M_key_compare(_S_key(__x), __k))
+     974            5885 :           __y = __x, __x = _S_left(__x);
+     975                 :         else
+     976            2280 :           __x = _S_right(__x);
+     977            3932 :       return const_iterator(__y);
+     978                 :     }
+     979                 : 
+     980                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     981                 :            typename _Compare, typename _Alloc>
+     982                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
+     983                 :                       _Compare, _Alloc>::iterator
+     984                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+     985                 :     _M_upper_bound(_Link_type __x, _Link_type __y,
+     986               2 :                    const _Key& __k)
+     987                 :     {
+     988               4 :       while (__x != 0)
+     989               0 :         if (_M_impl._M_key_compare(__k, _S_key(__x)))
+     990               0 :           __y = __x, __x = _S_left(__x);
+     991                 :         else
+     992               0 :           __x = _S_right(__x);
+     993               2 :       return iterator(__y);
+     994                 :     }
+     995                 : 
+     996                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+     997                 :            typename _Compare, typename _Alloc>
+     998                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
+     999                 :                       _Compare, _Alloc>::const_iterator
+    1000                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1001                 :     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
+    1002                 :                    const _Key& __k) const
+    1003                 :     {
+    1004                 :       while (__x != 0)
+    1005                 :         if (_M_impl._M_key_compare(__k, _S_key(__x)))
+    1006                 :           __y = __x, __x = _S_left(__x);
+    1007                 :         else
+    1008                 :           __x = _S_right(__x);
+    1009                 :       return const_iterator(__y);
+    1010                 :     }
+    1011                 : 
+    1012                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1013                 :            typename _Compare, typename _Alloc>
+    1014                 :     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1015                 :                            _Compare, _Alloc>::iterator,
+    1016                 :          typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1017                 :                            _Compare, _Alloc>::iterator>
+    1018                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1019               9 :     equal_range(const _Key& __k)
+    1020                 :     {
+    1021               9 :       _Link_type __x = _M_begin();
+    1022               9 :       _Link_type __y = _M_end();
+    1023              20 :       while (__x != 0)
+    1024                 :         {
+    1025               4 :           if (_M_impl._M_key_compare(_S_key(__x), __k))
+    1026               0 :             __x = _S_right(__x);
+    1027               4 :           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+    1028               2 :             __y = __x, __x = _S_left(__x);
+    1029                 :           else
+    1030                 :             {
+    1031               2 :               _Link_type __xu(__x), __yu(__y);
+    1032               2 :               __y = __x, __x = _S_left(__x);
+    1033               2 :               __xu = _S_right(__xu);
+    1034                 :               return pair<iterator,
+    1035                 :                           iterator>(_M_lower_bound(__x, __y, __k),
+    1036               2 :                                     _M_upper_bound(__xu, __yu, __k));
+    1037                 :             }
+    1038                 :         }
+    1039                 :       return pair<iterator, iterator>(iterator(__y),
+    1040               7 :                                       iterator(__y));
+    1041                 :     }
+    1042                 : 
+    1043                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1044                 :            typename _Compare, typename _Alloc>
+    1045                 :     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1046                 :                            _Compare, _Alloc>::const_iterator,
+    1047                 :          typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1048                 :                            _Compare, _Alloc>::const_iterator>
+    1049                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1050                 :     equal_range(const _Key& __k) const
+    1051                 :     {
+    1052                 :       _Const_Link_type __x = _M_begin();
+    1053                 :       _Const_Link_type __y = _M_end();
+    1054                 :       while (__x != 0)
+    1055                 :         {
+    1056                 :           if (_M_impl._M_key_compare(_S_key(__x), __k))
+    1057                 :             __x = _S_right(__x);
+    1058                 :           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+    1059                 :             __y = __x, __x = _S_left(__x);
+    1060                 :           else
+    1061                 :             {
+    1062                 :               _Const_Link_type __xu(__x), __yu(__y);
+    1063                 :               __y = __x, __x = _S_left(__x);
+    1064                 :               __xu = _S_right(__xu);
+    1065                 :               return pair<const_iterator,
+    1066                 :                           const_iterator>(_M_lower_bound(__x, __y, __k),
+    1067                 :                                           _M_upper_bound(__xu, __yu, __k));
+    1068                 :             }
+    1069                 :         }
+    1070                 :       return pair<const_iterator, const_iterator>(const_iterator(__y),
+    1071                 :                                                   const_iterator(__y));
+    1072                 :     }
+    1073                 : 
+    1074                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1075                 :            typename _Compare, typename _Alloc>
+    1076                 :     void
+    1077                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1078                 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
+    1079                 :     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t)
+    1080                 : #else
+    1081                 :     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
+    1082                 : #endif
+    1083                 :     {
+    1084                 :       if (_M_root() == 0)
+    1085                 :         {
+    1086                 :           if (__t._M_root() != 0)
+    1087                 :             {
+    1088                 :               _M_root() = __t._M_root();
+    1089                 :               _M_leftmost() = __t._M_leftmost();
+    1090                 :               _M_rightmost() = __t._M_rightmost();
+    1091                 :               _M_root()->_M_parent = _M_end();
+    1092                 :               
+    1093                 :               __t._M_root() = 0;
+    1094                 :               __t._M_leftmost() = __t._M_end();
+    1095                 :               __t._M_rightmost() = __t._M_end();
+    1096                 :             }
+    1097                 :         }
+    1098                 :       else if (__t._M_root() == 0)
+    1099                 :         {
+    1100                 :           __t._M_root() = _M_root();
+    1101                 :           __t._M_leftmost() = _M_leftmost();
+    1102                 :           __t._M_rightmost() = _M_rightmost();
+    1103                 :           __t._M_root()->_M_parent = __t._M_end();
+    1104                 :           
+    1105                 :           _M_root() = 0;
+    1106                 :           _M_leftmost() = _M_end();
+    1107                 :           _M_rightmost() = _M_end();
+    1108                 :         }
+    1109                 :       else
+    1110                 :         {
+    1111                 :           std::swap(_M_root(),__t._M_root());
+    1112                 :           std::swap(_M_leftmost(),__t._M_leftmost());
+    1113                 :           std::swap(_M_rightmost(),__t._M_rightmost());
+    1114                 :           
+    1115                 :           _M_root()->_M_parent = _M_end();
+    1116                 :           __t._M_root()->_M_parent = __t._M_end();
+    1117                 :         }
+    1118                 :       // No need to swap header's color as it does not change.
+    1119                 :       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
+    1120                 :       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
+    1121                 :       
+    1122                 :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
+    1123                 :       // 431. Swapping containers with unequal allocators.
+    1124                 :       std::__alloc_swap<_Node_allocator>::
+    1125                 :         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
+    1126                 :     }
+    1127                 : 
+    1128                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1129                 :            typename _Compare, typename _Alloc>
+    1130                 :     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1131                 :                            _Compare, _Alloc>::iterator, bool>
+    1132                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1133         1653740 :     _M_insert_unique(const _Val& __v)
+    1134                 :     {
+    1135         1653740 :       _Link_type __x = _M_begin();
+    1136         1653740 :       _Link_type __y = _M_end();
+    1137         1653740 :       bool __comp = true;
+    1138         9798389 :       while (__x != 0)
+    1139                 :         {
+    1140         6490909 :           __y = __x;
+    1141         6490909 :           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
+    1142         6490909 :           __x = __comp ? _S_left(__x) : _S_right(__x);
+    1143                 :         }
+    1144         1653740 :       iterator __j = iterator(__y);
+    1145         1653740 :       if (__comp)
+    1146                 :         {
+    1147          536188 :           if (__j == begin())
+    1148          452855 :             return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
+    1149                 :           else
+    1150           83333 :             --__j;
+    1151                 :         }
+    1152         1200885 :       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
+    1153         1095156 :         return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
+    1154          105729 :       return pair<iterator, bool>(__j, false);
+    1155                 :     }
+    1156                 : 
+    1157                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1158                 :            typename _Compare, typename _Alloc>
+    1159                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    1160                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1161                 :     _M_insert_equal(const _Val& __v)
+    1162                 :     {
+    1163                 :       _Link_type __x = _M_begin();
+    1164                 :       _Link_type __y = _M_end();
+    1165                 :       while (__x != 0)
+    1166                 :         {
+    1167                 :           __y = __x;
+    1168                 :           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
+    1169                 :                 _S_left(__x) : _S_right(__x);
+    1170                 :         }
+    1171                 :       return _M_insert_(__x, __y, __v);
+    1172                 :     }
+    1173                 : 
+    1174                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1175                 :            typename _Compare, typename _Alloc>
+    1176                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    1177                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1178          652700 :     _M_insert_unique_(const_iterator __position, const _Val& __v)
+    1179                 :     {
+    1180                 :       // end()
+    1181          652700 :       if (__position._M_node == _M_end())
+    1182                 :         {
+    1183          649758 :           if (size() > 0
+    1184                 :               && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
+    1185                 :                                         _KeyOfValue()(__v)))
+    1186          521501 :             return _M_insert_(0, _M_rightmost(), __v);
+    1187                 :           else
+    1188          128257 :             return _M_insert_unique(__v).first;
+    1189                 :         }
+    1190            2942 :       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+    1191                 :                                       _S_key(__position._M_node)))
+    1192                 :         {
+    1193                 :           // First, try before...
+    1194            2040 :           const_iterator __before = __position;
+    1195            2040 :           if (__position._M_node == _M_leftmost()) // begin()
+    1196              72 :             return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
+    1197            1968 :           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
+    1198                 :                                           _KeyOfValue()(__v)))
+    1199                 :             {
+    1200            1101 :               if (_S_right(__before._M_node) == 0)
+    1201             562 :                 return _M_insert_(0, __before._M_node, __v);
+    1202                 :               else
+    1203                 :                 return _M_insert_(__position._M_node,
+    1204             539 :                                   __position._M_node, __v);
+    1205                 :             }
+    1206                 :           else
+    1207             867 :             return _M_insert_unique(__v).first;
+    1208                 :         }
+    1209             902 :       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
+    1210                 :                                       _KeyOfValue()(__v)))
+    1211                 :         {
+    1212                 :           // ... then try after.
+    1213             902 :           const_iterator __after = __position;
+    1214             902 :           if (__position._M_node == _M_rightmost())
+    1215              13 :             return _M_insert_(0, _M_rightmost(), __v);
+    1216             889 :           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+    1217                 :                                           _S_key((++__after)._M_node)))
+    1218                 :             {
+    1219               8 :               if (_S_right(__position._M_node) == 0)
+    1220               4 :                 return _M_insert_(0, __position._M_node, __v);
+    1221                 :               else
+    1222               4 :                 return _M_insert_(__after._M_node, __after._M_node, __v);
+    1223                 :             }
+    1224                 :           else
+    1225             881 :             return _M_insert_unique(__v).first;
+    1226                 :         }
+    1227                 :       else
+    1228                 :         // Equivalent keys.
+    1229                 :         return iterator(static_cast<_Link_type>
+    1230               0 :                         (const_cast<_Base_ptr>(__position._M_node)));
+    1231                 :     }
+    1232                 : 
+    1233                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1234                 :            typename _Compare, typename _Alloc>
+    1235                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    1236                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1237                 :     _M_insert_equal_(const_iterator __position, const _Val& __v)
+    1238                 :     {
+    1239                 :       // end()
+    1240                 :       if (__position._M_node == _M_end())
+    1241                 :         {
+    1242                 :           if (size() > 0
+    1243                 :               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
+    1244                 :                                          _S_key(_M_rightmost())))
+    1245                 :             return _M_insert_(0, _M_rightmost(), __v);
+    1246                 :           else
+    1247                 :             return _M_insert_equal(__v);
+    1248                 :         }
+    1249                 :       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
+    1250                 :                                        _KeyOfValue()(__v)))
+    1251                 :         {
+    1252                 :           // First, try before...
+    1253                 :           const_iterator __before = __position;
+    1254                 :           if (__position._M_node == _M_leftmost()) // begin()
+    1255                 :             return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
+    1256                 :           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
+    1257                 :                                            _S_key((--__before)._M_node)))
+    1258                 :             {
+    1259                 :               if (_S_right(__before._M_node) == 0)
+    1260                 :                 return _M_insert_(0, __before._M_node, __v);
+    1261                 :               else
+    1262                 :                 return _M_insert_(__position._M_node,
+    1263                 :                                   __position._M_node, __v);
+    1264                 :             }
+    1265                 :           else
+    1266                 :             return _M_insert_equal(__v);
+    1267                 :         }
+    1268                 :       else
+    1269                 :         {
+    1270                 :           // ... then try after.  
+    1271                 :           const_iterator __after = __position;
+    1272                 :           if (__position._M_node == _M_rightmost())
+    1273                 :             return _M_insert_(0, _M_rightmost(), __v);
+    1274                 :           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
+    1275                 :                                            _KeyOfValue()(__v)))
+    1276                 :             {
+    1277                 :               if (_S_right(__position._M_node) == 0)
+    1278                 :                 return _M_insert_(0, __position._M_node, __v);
+    1279                 :               else
+    1280                 :                 return _M_insert_(__after._M_node, __after._M_node, __v);
+    1281                 :             }
+    1282                 :           else
+    1283                 :             return _M_insert_equal_lower(__v);
+    1284                 :         }
+    1285                 :     }
+    1286                 : 
+    1287                 :   template<typename _Key, typename _Val, typename _KoV,
+    1288                 :            typename _Cmp, typename _Alloc>
+    1289                 :     template<class _II>
+    1290                 :       void
+    1291                 :       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
+    1292                 :       _M_insert_unique(_II __first, _II __last)
+    1293                 :       {
+    1294                 :         for (; __first != __last; ++__first)
+    1295                 :           _M_insert_unique_(end(), *__first);
+    1296                 :       }
+    1297                 : 
+    1298                 :   template<typename _Key, typename _Val, typename _KoV,
+    1299                 :            typename _Cmp, typename _Alloc>
+    1300                 :     template<class _II>
+    1301                 :       void
+    1302                 :       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
+    1303                 :       _M_insert_equal(_II __first, _II __last)
+    1304                 :       {
+    1305                 :         for (; __first != __last; ++__first)
+    1306                 :           _M_insert_equal_(end(), *__first);
+    1307                 :       }
+    1308                 : 
+    1309                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1310                 :            typename _Compare, typename _Alloc>
+    1311                 :     inline void
+    1312                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1313               0 :     erase(iterator __position)
+    1314                 :     {
+    1315                 :       _Link_type __y =
+    1316                 :         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
+    1317                 :                                 (__position._M_node,
+    1318               0 :                                  this->_M_impl._M_header));
+    1319               0 :       _M_destroy_node(__y);
+    1320               0 :       --_M_impl._M_node_count;
+    1321               0 :     }
+    1322                 : 
+    1323                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1324                 :            typename _Compare, typename _Alloc>
+    1325                 :     inline void
+    1326                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1327             129 :     erase(const_iterator __position)
+    1328                 :     {
+    1329                 :       _Link_type __y =
+    1330                 :         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
+    1331                 :                                 (const_cast<_Base_ptr>(__position._M_node),
+    1332             129 :                                  this->_M_impl._M_header));
+    1333             129 :       _M_destroy_node(__y);
+    1334             129 :       --_M_impl._M_node_count;
+    1335             129 :     }
+    1336                 : 
+    1337                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1338                 :            typename _Compare, typename _Alloc>
+    1339                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+    1340                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1341               9 :     erase(const _Key& __x)
+    1342                 :     {
+    1343               9 :       pair<iterator, iterator> __p = equal_range(__x);
+    1344               9 :       const size_type __old_size = size();
+    1345               9 :       erase(__p.first, __p.second);
+    1346               9 :       return __old_size - size();
+    1347                 :     }
+    1348                 : 
+    1349                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1350                 :            typename _Compare, typename _Alloc>
+    1351                 :     void
+    1352                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1353               9 :     erase(iterator __first, iterator __last)
+    1354                 :     {
+    1355               9 :       if (__first == begin() && __last == end())
+    1356               7 :         clear();
+    1357                 :       else
+    1358               4 :         while (__first != __last)
+    1359               0 :           erase(__first++);
+    1360               9 :     }
+    1361                 : 
+    1362                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1363                 :            typename _Compare, typename _Alloc>
+    1364                 :     void
+    1365                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1366                 :     erase(const_iterator __first, const_iterator __last)
+    1367                 :     {
+    1368                 :       if (__first == begin() && __last == end())
+    1369                 :         clear();
+    1370                 :       else
+    1371                 :         while (__first != __last)
+    1372                 :           erase(__first++);
+    1373                 :     }
+    1374                 : 
+    1375                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1376                 :            typename _Compare, typename _Alloc>
+    1377                 :     void
+    1378                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1379                 :     erase(const _Key* __first, const _Key* __last)
+    1380                 :     {
+    1381                 :       while (__first != __last)
+    1382                 :         erase(*__first++);
+    1383                 :     }
+    1384                 : 
+    1385                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1386                 :            typename _Compare, typename _Alloc>
+    1387                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1388                 :                       _Compare, _Alloc>::iterator
+    1389                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1390           50156 :     find(const _Key& __k)
+    1391                 :     {
+    1392           50156 :       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+    1393                 :       return (__j == end()
+    1394                 :               || _M_impl._M_key_compare(__k,
+    1395           50156 :                                         _S_key(__j._M_node))) ? end() : __j;
+    1396                 :     }
+    1397                 : 
+    1398                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1399                 :            typename _Compare, typename _Alloc>
+    1400                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
+    1401                 :                       _Compare, _Alloc>::const_iterator
+    1402                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1403            3932 :     find(const _Key& __k) const
+    1404                 :     {
+    1405            3932 :       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+    1406                 :       return (__j == end()
+    1407                 :               || _M_impl._M_key_compare(__k, 
+    1408            3932 :                                         _S_key(__j._M_node))) ? end() : __j;
+    1409                 :     }
+    1410                 : 
+    1411                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1412                 :            typename _Compare, typename _Alloc>
+    1413                 :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+    1414                 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    1415                 :     count(const _Key& __k) const
+    1416                 :     {
+    1417                 :       pair<const_iterator, const_iterator> __p = equal_range(__k);
+    1418                 :       const size_type __n = std::distance(__p.first, __p.second);
+    1419                 :       return __n;
+    1420                 :     }
+    1421                 : 
+    1422                 :   unsigned int
+    1423                 :   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
+    1424                 :                        const _Rb_tree_node_base* __root);
+    1425                 : 
+    1426                 :   template<typename _Key, typename _Val, typename _KeyOfValue,
+    1427                 :            typename _Compare, typename _Alloc>
+    1428                 :     bool
+    1429                 :     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
+    1430                 :     {
+    1431                 :       if (_M_impl._M_node_count == 0 || begin() == end())
+    1432                 :         return _M_impl._M_node_count == 0 && begin() == end()
+    1433                 :                && this->_M_impl._M_header._M_left == _M_end()
+    1434                 :                && this->_M_impl._M_header._M_right == _M_end();
+    1435                 : 
+    1436                 :       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
+    1437                 :       for (const_iterator __it = begin(); __it != end(); ++__it)
+    1438                 :         {
+    1439                 :           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
+    1440                 :           _Const_Link_type __L = _S_left(__x);
+    1441                 :           _Const_Link_type __R = _S_right(__x);
+    1442                 : 
+    1443                 :           if (__x->_M_color == _S_red)
+    1444                 :             if ((__L && __L->_M_color == _S_red)
+    1445                 :                 || (__R && __R->_M_color == _S_red))
+    1446                 :               return false;
+    1447                 : 
+    1448                 :           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
+    1449                 :             return false;
+    1450                 :           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
+    1451                 :             return false;
+    1452                 : 
+    1453                 :           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
+    1454                 :             return false;
+    1455                 :         }
+    1456                 : 
+    1457                 :       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
+    1458                 :         return false;
+    1459                 :       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
+    1460                 :         return false;
+    1461                 :       return true;
+    1462                 :     }
+    1463                 : 
+    1464                 : _GLIBCXX_END_NAMESPACE
+    1465                 : 
+    1466                 : #endif
+
+
+
+ + + + +
Generated by: LTP GCOV extension version 1.6
+
+ + + -- cgit v1.2.3