libstdc++
stl_tree.h
Go to the documentation of this file.
00001 // RB tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1996,1997
00028  * Silicon Graphics Computer Systems, Inc.
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Silicon Graphics makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1994
00040  * Hewlett-Packard Company
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Hewlett-Packard Company makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  *
00050  *
00051  */
00052 
00053 /** @file bits/stl_tree.h
00054  *  This is an internal header file, included by other library headers.
00055  *  Do not attempt to use it directly. @headername{map,set}
00056  */
00057 
00058 #ifndef _STL_TREE_H
00059 #define _STL_TREE_H 1
00060 
00061 #pragma GCC system_header
00062 
00063 #include <bits/stl_algobase.h>
00064 #include <bits/allocator.h>
00065 #include <bits/stl_function.h>
00066 #include <bits/cpp_type_traits.h>
00067 #include <ext/alloc_traits.h>
00068 #if __cplusplus >= 201103L
00069 #include <ext/aligned_buffer.h>
00070 #endif
00071 
00072 namespace std _GLIBCXX_VISIBILITY(default)
00073 {
00074 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00075 
00076 #if __cplusplus > 201103L
00077 # define __cpp_lib_generic_associative_lookup 201304
00078 #endif
00079 
00080   // Red-black tree class, designed for use in implementing STL
00081   // associative containers (set, multiset, map, and multimap). The
00082   // insertion and deletion algorithms are based on those in Cormen,
00083   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
00084   // 1990), except that
00085   //
00086   // (1) the header cell is maintained with links not only to the root
00087   // but also to the leftmost node of the tree, to enable constant
00088   // time begin(), and to the rightmost node of the tree, to enable
00089   // linear time performance when used with the generic set algorithms
00090   // (set_union, etc.)
00091   // 
00092   // (2) when a node being deleted has two children its successor node
00093   // is relinked into its place, rather than copied, so that the only
00094   // iterators invalidated are those referring to the deleted node.
00095 
00096   enum _Rb_tree_color { _S_red = false, _S_black = true };
00097 
00098   struct _Rb_tree_node_base
00099   {
00100     typedef _Rb_tree_node_base* _Base_ptr;
00101     typedef const _Rb_tree_node_base* _Const_Base_ptr;
00102 
00103     _Rb_tree_color      _M_color;
00104     _Base_ptr           _M_parent;
00105     _Base_ptr           _M_left;
00106     _Base_ptr           _M_right;
00107 
00108     static _Base_ptr
00109     _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00110     {
00111       while (__x->_M_left != 0) __x = __x->_M_left;
00112       return __x;
00113     }
00114 
00115     static _Const_Base_ptr
00116     _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00117     {
00118       while (__x->_M_left != 0) __x = __x->_M_left;
00119       return __x;
00120     }
00121 
00122     static _Base_ptr
00123     _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00124     {
00125       while (__x->_M_right != 0) __x = __x->_M_right;
00126       return __x;
00127     }
00128 
00129     static _Const_Base_ptr
00130     _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00131     {
00132       while (__x->_M_right != 0) __x = __x->_M_right;
00133       return __x;
00134     }
00135   };
00136 
00137   template<typename _Val>
00138     struct _Rb_tree_node : public _Rb_tree_node_base
00139     {
00140       typedef _Rb_tree_node<_Val>* _Link_type;
00141 
00142 #if __cplusplus < 201103L
00143       _Val _M_value_field;
00144 
00145       _Val*
00146       _M_valptr()
00147       { return std::__addressof(_M_value_field); }
00148 
00149       const _Val*
00150       _M_valptr() const
00151       { return std::__addressof(_M_value_field); }
00152 #else
00153       __gnu_cxx::__aligned_membuf<_Val> _M_storage;
00154 
00155       _Val*
00156       _M_valptr()
00157       { return _M_storage._M_ptr(); }
00158 
00159       const _Val*
00160       _M_valptr() const
00161       { return _M_storage._M_ptr(); }
00162 #endif
00163     };
00164 
00165   _GLIBCXX_PURE _Rb_tree_node_base*
00166   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
00167 
00168   _GLIBCXX_PURE const _Rb_tree_node_base*
00169   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
00170 
00171   _GLIBCXX_PURE _Rb_tree_node_base*
00172   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
00173 
00174   _GLIBCXX_PURE const _Rb_tree_node_base*
00175   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
00176 
00177   template<typename _Tp>
00178     struct _Rb_tree_iterator
00179     {
00180       typedef _Tp  value_type;
00181       typedef _Tp& reference;
00182       typedef _Tp* pointer;
00183 
00184       typedef bidirectional_iterator_tag iterator_category;
00185       typedef ptrdiff_t                  difference_type;
00186 
00187       typedef _Rb_tree_iterator<_Tp>        _Self;
00188       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00189       typedef _Rb_tree_node<_Tp>*           _Link_type;
00190 
00191       _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
00192       : _M_node() { }
00193 
00194       explicit
00195       _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00196       : _M_node(__x) { }
00197 
00198       reference
00199       operator*() const _GLIBCXX_NOEXCEPT
00200       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
00201 
00202       pointer
00203       operator->() const _GLIBCXX_NOEXCEPT
00204       { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
00205 
00206       _Self&
00207       operator++() _GLIBCXX_NOEXCEPT
00208       {
00209         _M_node = _Rb_tree_increment(_M_node);
00210         return *this;
00211       }
00212 
00213       _Self
00214       operator++(int) _GLIBCXX_NOEXCEPT
00215       {
00216         _Self __tmp = *this;
00217         _M_node = _Rb_tree_increment(_M_node);
00218         return __tmp;
00219       }
00220 
00221       _Self&
00222       operator--() _GLIBCXX_NOEXCEPT
00223       {
00224         _M_node = _Rb_tree_decrement(_M_node);
00225         return *this;
00226       }
00227 
00228       _Self
00229       operator--(int) _GLIBCXX_NOEXCEPT
00230       {
00231         _Self __tmp = *this;
00232         _M_node = _Rb_tree_decrement(_M_node);
00233         return __tmp;
00234       }
00235 
00236       bool
00237       operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
00238       { return _M_node == __x._M_node; }
00239 
00240       bool
00241       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
00242       { return _M_node != __x._M_node; }
00243 
00244       _Base_ptr _M_node;
00245   };
00246 
00247   template<typename _Tp>
00248     struct _Rb_tree_const_iterator
00249     {
00250       typedef _Tp        value_type;
00251       typedef const _Tp& reference;
00252       typedef const _Tp* pointer;
00253 
00254       typedef _Rb_tree_iterator<_Tp> iterator;
00255 
00256       typedef bidirectional_iterator_tag iterator_category;
00257       typedef ptrdiff_t                  difference_type;
00258 
00259       typedef _Rb_tree_const_iterator<_Tp>        _Self;
00260       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00261       typedef const _Rb_tree_node<_Tp>*           _Link_type;
00262 
00263       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
00264       : _M_node() { }
00265 
00266       explicit
00267       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00268       : _M_node(__x) { }
00269 
00270       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
00271       : _M_node(__it._M_node) { }
00272 
00273       iterator
00274       _M_const_cast() const _GLIBCXX_NOEXCEPT
00275       { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
00276 
00277       reference
00278       operator*() const _GLIBCXX_NOEXCEPT
00279       { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
00280 
00281       pointer
00282       operator->() const _GLIBCXX_NOEXCEPT
00283       { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
00284 
00285       _Self&
00286       operator++() _GLIBCXX_NOEXCEPT
00287       {
00288         _M_node = _Rb_tree_increment(_M_node);
00289         return *this;
00290       }
00291 
00292       _Self
00293       operator++(int) _GLIBCXX_NOEXCEPT
00294       {
00295         _Self __tmp = *this;
00296         _M_node = _Rb_tree_increment(_M_node);
00297         return __tmp;
00298       }
00299 
00300       _Self&
00301       operator--() _GLIBCXX_NOEXCEPT
00302       {
00303         _M_node = _Rb_tree_decrement(_M_node);
00304         return *this;
00305       }
00306 
00307       _Self
00308       operator--(int) _GLIBCXX_NOEXCEPT
00309       {
00310         _Self __tmp = *this;
00311         _M_node = _Rb_tree_decrement(_M_node);
00312         return __tmp;
00313       }
00314 
00315       bool
00316       operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
00317       { return _M_node == __x._M_node; }
00318 
00319       bool
00320       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
00321       { return _M_node != __x._M_node; }
00322 
00323       _Base_ptr _M_node;
00324     };
00325 
00326   template<typename _Val>
00327     inline bool
00328     operator==(const _Rb_tree_iterator<_Val>& __x,
00329                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
00330     { return __x._M_node == __y._M_node; }
00331 
00332   template<typename _Val>
00333     inline bool
00334     operator!=(const _Rb_tree_iterator<_Val>& __x,
00335                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
00336     { return __x._M_node != __y._M_node; }
00337 
00338   void
00339   _Rb_tree_insert_and_rebalance(const bool __insert_left,
00340                                 _Rb_tree_node_base* __x,
00341                                 _Rb_tree_node_base* __p,
00342                                 _Rb_tree_node_base& __header) throw ();
00343 
00344   _Rb_tree_node_base*
00345   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00346                                _Rb_tree_node_base& __header) throw ();
00347 
00348 #if __cplusplus > 201103L
00349   template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
00350     struct __has_is_transparent
00351     { };
00352 
00353   template<typename _Cmp, typename _SfinaeType>
00354     struct __has_is_transparent<_Cmp, _SfinaeType,
00355                                 __void_t<typename _Cmp::is_transparent>>
00356     { typedef void type; };
00357 #endif
00358 
00359   template<typename _Key, typename _Val, typename _KeyOfValue,
00360            typename _Compare, typename _Alloc = allocator<_Val> >
00361     class _Rb_tree
00362     {
00363       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
00364         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
00365 
00366       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
00367 
00368     protected:
00369       typedef _Rb_tree_node_base*               _Base_ptr;
00370       typedef const _Rb_tree_node_base*         _Const_Base_ptr;
00371       typedef _Rb_tree_node<_Val>*              _Link_type;
00372       typedef const _Rb_tree_node<_Val>*        _Const_Link_type;
00373 
00374     private:
00375       // Functor recycling a pool of nodes and using allocation once the pool
00376       // is empty.
00377       struct _Reuse_or_alloc_node
00378       {
00379         _Reuse_or_alloc_node(_Rb_tree& __t)
00380           : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
00381         {
00382           if (_M_root)
00383             {
00384               _M_root->_M_parent = 0;
00385 
00386               if (_M_nodes->_M_left)
00387                 _M_nodes = _M_nodes->_M_left;
00388             }
00389           else
00390             _M_nodes = 0;
00391         }
00392 
00393 #if __cplusplus >= 201103L
00394         _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
00395 #endif
00396 
00397         ~_Reuse_or_alloc_node()
00398         { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
00399 
00400         template<typename _Arg>
00401           _Link_type
00402 #if __cplusplus < 201103L
00403           operator()(const _Arg& __arg)
00404 #else
00405           operator()(_Arg&& __arg)
00406 #endif
00407           {
00408             _Link_type __node = static_cast<_Link_type>(_M_extract());
00409             if (__node)
00410               {
00411                 _M_t._M_destroy_node(__node);
00412                 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
00413                 return __node;
00414               }
00415 
00416             return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
00417           }
00418 
00419       private:
00420         _Base_ptr
00421         _M_extract()
00422         {
00423           if (!_M_nodes)
00424             return _M_nodes;
00425 
00426           _Base_ptr __node = _M_nodes;
00427           _M_nodes = _M_nodes->_M_parent;
00428           if (_M_nodes)
00429             {
00430               if (_M_nodes->_M_right == __node)
00431                 {
00432                   _M_nodes->_M_right = 0;
00433 
00434                   if (_M_nodes->_M_left)
00435                     {
00436                       _M_nodes = _M_nodes->_M_left;
00437 
00438                       while (_M_nodes->_M_right)
00439                         _M_nodes = _M_nodes->_M_right;
00440 
00441                       if (_M_nodes->_M_left)
00442                         _M_nodes = _M_nodes->_M_left;
00443                     }
00444                 }
00445               else // __node is on the left.
00446                 _M_nodes->_M_left = 0;
00447             }
00448           else
00449             _M_root = 0;
00450 
00451           return __node;
00452         }
00453 
00454         _Base_ptr _M_root;
00455         _Base_ptr _M_nodes;
00456         _Rb_tree& _M_t;
00457       };
00458 
00459       // Functor similar to the previous one but without any pool of nodes to
00460       // recycle.
00461       struct _Alloc_node
00462       {
00463         _Alloc_node(_Rb_tree& __t)
00464           : _M_t(__t) { }
00465 
00466         template<typename _Arg>
00467           _Link_type
00468 #if __cplusplus < 201103L
00469           operator()(const _Arg& __arg) const
00470 #else
00471           operator()(_Arg&& __arg) const
00472 #endif
00473           { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
00474 
00475       private:
00476         _Rb_tree& _M_t;
00477       };
00478 
00479     public:
00480       typedef _Key                              key_type;
00481       typedef _Val                              value_type;
00482       typedef value_type*                       pointer;
00483       typedef const value_type*                 const_pointer;
00484       typedef value_type&                       reference;
00485       typedef const value_type&                 const_reference;
00486       typedef size_t                            size_type;
00487       typedef ptrdiff_t                         difference_type;
00488       typedef _Alloc                            allocator_type;
00489 
00490       _Node_allocator&
00491       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
00492       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
00493       
00494       const _Node_allocator&
00495       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
00496       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00497 
00498       allocator_type
00499       get_allocator() const _GLIBCXX_NOEXCEPT
00500       { return allocator_type(_M_get_Node_allocator()); }
00501 
00502     protected:
00503       _Link_type
00504       _M_get_node()
00505       { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
00506 
00507       void
00508       _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
00509       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
00510 
00511 #if __cplusplus < 201103L
00512       void
00513       _M_construct_node(_Link_type __node, const value_type& __x)
00514       {
00515         __try
00516           { get_allocator().construct(__node->_M_valptr(), __x); }
00517         __catch(...)
00518           {
00519             _M_put_node(__node);
00520             __throw_exception_again;
00521           }
00522       }
00523 
00524       _Link_type
00525       _M_create_node(const value_type& __x)
00526       {
00527         _Link_type __tmp = _M_get_node();
00528         _M_construct_node(__tmp, __x);
00529         return __tmp;
00530       }
00531 
00532       void
00533       _M_destroy_node(_Link_type __p)
00534       { get_allocator().destroy(__p->_M_valptr()); }
00535 #else
00536       template<typename... _Args>
00537         void
00538         _M_construct_node(_Link_type __node, _Args&&... __args)
00539         {
00540           __try
00541             {
00542               ::new(__node) _Rb_tree_node<_Val>;
00543               _Alloc_traits::construct(_M_get_Node_allocator(),
00544                                        __node->_M_valptr(),
00545                                        std::forward<_Args>(__args)...);
00546             }
00547           __catch(...)
00548             {
00549               __node->~_Rb_tree_node<_Val>();
00550               _M_put_node(__node);
00551               __throw_exception_again;
00552             }
00553         }
00554 
00555       template<typename... _Args>
00556         _Link_type
00557         _M_create_node(_Args&&... __args)
00558         {
00559           _Link_type __tmp = _M_get_node();
00560           _M_construct_node(__tmp, std::forward<_Args>(__args)...);
00561           return __tmp;
00562         }
00563 
00564       void
00565       _M_destroy_node(_Link_type __p) noexcept
00566       {
00567         _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
00568         __p->~_Rb_tree_node<_Val>();
00569       }
00570 #endif
00571 
00572       void
00573       _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
00574       {
00575         _M_destroy_node(__p);
00576         _M_put_node(__p);
00577       }
00578 
00579       template<typename _NodeGen>
00580         _Link_type
00581         _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
00582         {
00583           _Link_type __tmp = __node_gen(*__x->_M_valptr());
00584           __tmp->_M_color = __x->_M_color;
00585           __tmp->_M_left = 0;
00586           __tmp->_M_right = 0;
00587           return __tmp;
00588         }
00589 
00590     protected:
00591       // Unused _Is_pod_comparator is kept as it is part of mangled name.
00592       template<typename _Key_compare,
00593                bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
00594         struct _Rb_tree_impl : public _Node_allocator
00595         {
00596           _Key_compare          _M_key_compare;
00597           _Rb_tree_node_base    _M_header;
00598           size_type             _M_node_count; // Keeps track of size of tree.
00599 
00600           _Rb_tree_impl()
00601           : _Node_allocator(), _M_key_compare(), _M_header(),
00602             _M_node_count(0)
00603           { _M_initialize(); }
00604 
00605           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
00606           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
00607             _M_node_count(0)
00608           { _M_initialize(); }
00609 
00610 #if __cplusplus >= 201103L
00611           _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
00612           : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
00613             _M_header(), _M_node_count(0)
00614           { _M_initialize(); }
00615 #endif
00616 
00617           void
00618           _M_reset()
00619           {
00620             this->_M_header._M_parent = 0;
00621             this->_M_header._M_left = &this->_M_header;
00622             this->_M_header._M_right = &this->_M_header;
00623             this->_M_node_count = 0;
00624           }
00625 
00626         private:
00627           void
00628           _M_initialize()
00629           {
00630             this->_M_header._M_color = _S_red;
00631             this->_M_header._M_parent = 0;
00632             this->_M_header._M_left = &this->_M_header;
00633             this->_M_header._M_right = &this->_M_header;
00634           }         
00635         };
00636 
00637       _Rb_tree_impl<_Compare> _M_impl;
00638 
00639     protected:
00640       _Base_ptr&
00641       _M_root() _GLIBCXX_NOEXCEPT
00642       { return this->_M_impl._M_header._M_parent; }
00643 
00644       _Const_Base_ptr
00645       _M_root() const _GLIBCXX_NOEXCEPT
00646       { return this->_M_impl._M_header._M_parent; }
00647 
00648       _Base_ptr&
00649       _M_leftmost() _GLIBCXX_NOEXCEPT
00650       { return this->_M_impl._M_header._M_left; }
00651 
00652       _Const_Base_ptr
00653       _M_leftmost() const _GLIBCXX_NOEXCEPT
00654       { return this->_M_impl._M_header._M_left; }
00655 
00656       _Base_ptr&
00657       _M_rightmost() _GLIBCXX_NOEXCEPT
00658       { return this->_M_impl._M_header._M_right; }
00659 
00660       _Const_Base_ptr
00661       _M_rightmost() const _GLIBCXX_NOEXCEPT
00662       { return this->_M_impl._M_header._M_right; }
00663 
00664       _Link_type
00665       _M_begin() _GLIBCXX_NOEXCEPT
00666       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00667 
00668       _Const_Link_type
00669       _M_begin() const _GLIBCXX_NOEXCEPT
00670       {
00671         return static_cast<_Const_Link_type>
00672           (this->_M_impl._M_header._M_parent);
00673       }
00674 
00675       _Base_ptr
00676       _M_end() _GLIBCXX_NOEXCEPT
00677       { return &this->_M_impl._M_header; }
00678 
00679       _Const_Base_ptr
00680       _M_end() const _GLIBCXX_NOEXCEPT
00681       { return &this->_M_impl._M_header; }
00682 
00683       static const_reference
00684       _S_value(_Const_Link_type __x)
00685       { return *__x->_M_valptr(); }
00686 
00687       static const _Key&
00688       _S_key(_Const_Link_type __x)
00689       { return _KeyOfValue()(_S_value(__x)); }
00690 
00691       static _Link_type
00692       _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00693       { return static_cast<_Link_type>(__x->_M_left); }
00694 
00695       static _Const_Link_type
00696       _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00697       { return static_cast<_Const_Link_type>(__x->_M_left); }
00698 
00699       static _Link_type
00700       _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00701       { return static_cast<_Link_type>(__x->_M_right); }
00702 
00703       static _Const_Link_type
00704       _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00705       { return static_cast<_Const_Link_type>(__x->_M_right); }
00706 
00707       static const_reference
00708       _S_value(_Const_Base_ptr __x)
00709       { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
00710 
00711       static const _Key&
00712       _S_key(_Const_Base_ptr __x)
00713       { return _KeyOfValue()(_S_value(__x)); }
00714 
00715       static _Base_ptr
00716       _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00717       { return _Rb_tree_node_base::_S_minimum(__x); }
00718 
00719       static _Const_Base_ptr
00720       _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00721       { return _Rb_tree_node_base::_S_minimum(__x); }
00722 
00723       static _Base_ptr
00724       _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
00725       { return _Rb_tree_node_base::_S_maximum(__x); }
00726 
00727       static _Const_Base_ptr
00728       _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
00729       { return _Rb_tree_node_base::_S_maximum(__x); }
00730 
00731     public:
00732       typedef _Rb_tree_iterator<value_type>       iterator;
00733       typedef _Rb_tree_const_iterator<value_type> const_iterator;
00734 
00735       typedef std::reverse_iterator<iterator>       reverse_iterator;
00736       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00737 
00738       pair<_Base_ptr, _Base_ptr>
00739       _M_get_insert_unique_pos(const key_type& __k);
00740 
00741       pair<_Base_ptr, _Base_ptr>
00742       _M_get_insert_equal_pos(const key_type& __k);
00743 
00744       pair<_Base_ptr, _Base_ptr>
00745       _M_get_insert_hint_unique_pos(const_iterator __pos,
00746                                     const key_type& __k);
00747 
00748       pair<_Base_ptr, _Base_ptr>
00749       _M_get_insert_hint_equal_pos(const_iterator __pos,
00750                                    const key_type& __k);
00751 
00752     private:
00753 #if __cplusplus >= 201103L
00754       template<typename _Arg, typename _NodeGen>
00755         iterator
00756         _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
00757 
00758       iterator
00759       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
00760 
00761       template<typename _Arg>
00762         iterator
00763         _M_insert_lower(_Base_ptr __y, _Arg&& __v);
00764 
00765       template<typename _Arg>
00766         iterator
00767         _M_insert_equal_lower(_Arg&& __x);
00768 
00769       iterator
00770       _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
00771 
00772       iterator
00773       _M_insert_equal_lower_node(_Link_type __z);
00774 #else
00775       template<typename _NodeGen>
00776         iterator
00777         _M_insert_(_Base_ptr __x, _Base_ptr __y,
00778                    const value_type& __v, _NodeGen&);
00779 
00780       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00781       // 233. Insertion hints in associative containers.
00782       iterator
00783       _M_insert_lower(_Base_ptr __y, const value_type& __v);
00784 
00785       iterator
00786       _M_insert_equal_lower(const value_type& __x);
00787 #endif
00788 
00789       template<typename _NodeGen>
00790         _Link_type
00791         _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
00792 
00793       _Link_type
00794       _M_copy(_Const_Link_type __x, _Base_ptr __p)
00795       {
00796         _Alloc_node __an(*this);
00797         return _M_copy(__x, __p, __an);
00798       }
00799 
00800       void
00801       _M_erase(_Link_type __x);
00802 
00803       iterator
00804       _M_lower_bound(_Link_type __x, _Base_ptr __y,
00805                      const _Key& __k);
00806 
00807       const_iterator
00808       _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
00809                      const _Key& __k) const;
00810 
00811       iterator
00812       _M_upper_bound(_Link_type __x, _Base_ptr __y,
00813                      const _Key& __k);
00814 
00815       const_iterator
00816       _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
00817                      const _Key& __k) const;
00818 
00819     public:
00820       // allocation/deallocation
00821       _Rb_tree() { }
00822 
00823       _Rb_tree(const _Compare& __comp,
00824                const allocator_type& __a = allocator_type())
00825       : _M_impl(__comp, _Node_allocator(__a)) { }
00826 
00827       _Rb_tree(const _Rb_tree& __x)
00828       : _M_impl(__x._M_impl._M_key_compare,
00829                 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
00830       {
00831         if (__x._M_root() != 0)
00832           {
00833             _M_root() = _M_copy(__x._M_begin(), _M_end());
00834             _M_leftmost() = _S_minimum(_M_root());
00835             _M_rightmost() = _S_maximum(_M_root());
00836             _M_impl._M_node_count = __x._M_impl._M_node_count;
00837           }
00838       }
00839 
00840 #if __cplusplus >= 201103L
00841       _Rb_tree(const allocator_type& __a)
00842       : _M_impl(_Compare(), _Node_allocator(__a))
00843       { }
00844 
00845       _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
00846       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
00847       {
00848         if (__x._M_root() != nullptr)
00849           {
00850             _M_root() = _M_copy(__x._M_begin(), _M_end());
00851             _M_leftmost() = _S_minimum(_M_root());
00852             _M_rightmost() = _S_maximum(_M_root());
00853             _M_impl._M_node_count = __x._M_impl._M_node_count;
00854           }
00855       }
00856 
00857       _Rb_tree(_Rb_tree&& __x)
00858       : _M_impl(__x._M_impl._M_key_compare,
00859                 std::move(__x._M_get_Node_allocator()))
00860       {
00861         if (__x._M_root() != 0)
00862           _M_move_data(__x, std::true_type());
00863       }
00864 
00865       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
00866       : _Rb_tree(std::move(__x), _Node_allocator(__a))
00867       { }
00868 
00869       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
00870 #endif
00871 
00872       ~_Rb_tree() _GLIBCXX_NOEXCEPT
00873       { _M_erase(_M_begin()); }
00874 
00875       _Rb_tree&
00876       operator=(const _Rb_tree& __x);
00877 
00878       // Accessors.
00879       _Compare
00880       key_comp() const
00881       { return _M_impl._M_key_compare; }
00882 
00883       iterator
00884       begin() _GLIBCXX_NOEXCEPT
00885       { return iterator(this->_M_impl._M_header._M_left); }
00886 
00887       const_iterator
00888       begin() const _GLIBCXX_NOEXCEPT
00889       { return const_iterator(this->_M_impl._M_header._M_left); }
00890 
00891       iterator
00892       end() _GLIBCXX_NOEXCEPT
00893       { return iterator(&this->_M_impl._M_header); }
00894 
00895       const_iterator
00896       end() const _GLIBCXX_NOEXCEPT
00897       { return const_iterator(&this->_M_impl._M_header); }
00898 
00899       reverse_iterator
00900       rbegin() _GLIBCXX_NOEXCEPT
00901       { return reverse_iterator(end()); }
00902 
00903       const_reverse_iterator
00904       rbegin() const _GLIBCXX_NOEXCEPT
00905       { return const_reverse_iterator(end()); }
00906 
00907       reverse_iterator
00908       rend() _GLIBCXX_NOEXCEPT
00909       { return reverse_iterator(begin()); }
00910 
00911       const_reverse_iterator
00912       rend() const _GLIBCXX_NOEXCEPT
00913       { return const_reverse_iterator(begin()); }
00914 
00915       bool
00916       empty() const _GLIBCXX_NOEXCEPT
00917       { return _M_impl._M_node_count == 0; }
00918 
00919       size_type
00920       size() const _GLIBCXX_NOEXCEPT 
00921       { return _M_impl._M_node_count; }
00922 
00923       size_type
00924       max_size() const _GLIBCXX_NOEXCEPT
00925       { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
00926 
00927       void
00928       swap(_Rb_tree& __t)
00929       _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
00930 
00931       // Insert/erase.
00932 #if __cplusplus >= 201103L
00933       template<typename _Arg>
00934         pair<iterator, bool>
00935         _M_insert_unique(_Arg&& __x);
00936 
00937       template<typename _Arg>
00938         iterator
00939         _M_insert_equal(_Arg&& __x);
00940 
00941       template<typename _Arg, typename _NodeGen>
00942         iterator
00943         _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
00944 
00945       template<typename _Arg>
00946         iterator
00947         _M_insert_unique_(const_iterator __pos, _Arg&& __x)
00948         {
00949           _Alloc_node __an(*this);
00950           return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
00951         }
00952 
00953       template<typename _Arg, typename _NodeGen>
00954         iterator
00955         _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
00956 
00957       template<typename _Arg>
00958         iterator
00959         _M_insert_equal_(const_iterator __pos, _Arg&& __x)
00960         {
00961           _Alloc_node __an(*this);
00962           return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
00963         }
00964 
00965       template<typename... _Args>
00966         pair<iterator, bool>
00967         _M_emplace_unique(_Args&&... __args);
00968 
00969       template<typename... _Args>
00970         iterator
00971         _M_emplace_equal(_Args&&... __args);
00972 
00973       template<typename... _Args>
00974         iterator
00975         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
00976 
00977       template<typename... _Args>
00978         iterator
00979         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
00980 #else
00981       pair<iterator, bool>
00982       _M_insert_unique(const value_type& __x);
00983 
00984       iterator
00985       _M_insert_equal(const value_type& __x);
00986 
00987       template<typename _NodeGen>
00988         iterator
00989         _M_insert_unique_(const_iterator __pos, const value_type& __x,
00990                           _NodeGen&);
00991 
00992       iterator
00993       _M_insert_unique_(const_iterator __pos, const value_type& __x)
00994       {
00995         _Alloc_node __an(*this);
00996         return _M_insert_unique_(__pos, __x, __an);
00997       }
00998 
00999       template<typename _NodeGen>
01000         iterator
01001         _M_insert_equal_(const_iterator __pos, const value_type& __x,
01002                          _NodeGen&);
01003       iterator
01004       _M_insert_equal_(const_iterator __pos, const value_type& __x)
01005       {
01006         _Alloc_node __an(*this);
01007         return _M_insert_equal_(__pos, __x, __an);
01008       }
01009 #endif
01010 
01011       template<typename _InputIterator>
01012         void
01013         _M_insert_unique(_InputIterator __first, _InputIterator __last);
01014 
01015       template<typename _InputIterator>
01016         void
01017         _M_insert_equal(_InputIterator __first, _InputIterator __last);
01018 
01019     private:
01020       void
01021       _M_erase_aux(const_iterator __position);
01022 
01023       void
01024       _M_erase_aux(const_iterator __first, const_iterator __last);
01025 
01026     public:
01027 #if __cplusplus >= 201103L
01028       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01029       // DR 130. Associative erase should return an iterator.
01030       _GLIBCXX_ABI_TAG_CXX11
01031       iterator
01032       erase(const_iterator __position)
01033       {
01034         const_iterator __result = __position;
01035         ++__result;
01036         _M_erase_aux(__position);
01037         return __result._M_const_cast();
01038       }
01039 
01040       // LWG 2059.
01041       _GLIBCXX_ABI_TAG_CXX11
01042       iterator
01043       erase(iterator __position)
01044       {
01045         iterator __result = __position;
01046         ++__result;
01047         _M_erase_aux(__position);
01048         return __result;
01049       }
01050 #else
01051       void
01052       erase(iterator __position)
01053       { _M_erase_aux(__position); }
01054 
01055       void
01056       erase(const_iterator __position)
01057       { _M_erase_aux(__position); }
01058 #endif
01059       size_type
01060       erase(const key_type& __x);
01061 
01062 #if __cplusplus >= 201103L
01063       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01064       // DR 130. Associative erase should return an iterator.
01065       _GLIBCXX_ABI_TAG_CXX11
01066       iterator
01067       erase(const_iterator __first, const_iterator __last)
01068       {
01069         _M_erase_aux(__first, __last);
01070         return __last._M_const_cast();
01071       }
01072 #else
01073       void
01074       erase(iterator __first, iterator __last)
01075       { _M_erase_aux(__first, __last); }
01076 
01077       void
01078       erase(const_iterator __first, const_iterator __last)
01079       { _M_erase_aux(__first, __last); }
01080 #endif
01081       void
01082       erase(const key_type* __first, const key_type* __last);
01083 
01084       void
01085       clear() _GLIBCXX_NOEXCEPT
01086       {
01087         _M_erase(_M_begin());
01088         _M_impl._M_reset();
01089       }
01090 
01091       // Set operations.
01092       iterator
01093       find(const key_type& __k);
01094 
01095       const_iterator
01096       find(const key_type& __k) const;
01097 
01098       size_type
01099       count(const key_type& __k) const;
01100 
01101       iterator
01102       lower_bound(const key_type& __k)
01103       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
01104 
01105       const_iterator
01106       lower_bound(const key_type& __k) const
01107       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
01108 
01109       iterator
01110       upper_bound(const key_type& __k)
01111       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
01112 
01113       const_iterator
01114       upper_bound(const key_type& __k) const
01115       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
01116 
01117       pair<iterator, iterator>
01118       equal_range(const key_type& __k);
01119 
01120       pair<const_iterator, const_iterator>
01121       equal_range(const key_type& __k) const;
01122 
01123 #if __cplusplus > 201103L
01124       template<typename _Kt,
01125                typename _Req =
01126                  typename __has_is_transparent<_Compare, _Kt>::type>
01127         iterator
01128         _M_find_tr(const _Kt& __k)
01129         {
01130           const _Rb_tree* __const_this = this;
01131           return __const_this->_M_find_tr(__k)._M_const_cast();
01132         }
01133 
01134       template<typename _Kt,
01135                typename _Req =
01136                  typename __has_is_transparent<_Compare, _Kt>::type>
01137         const_iterator
01138         _M_find_tr(const _Kt& __k) const
01139         {
01140           auto __j = _M_lower_bound_tr(__k);
01141           if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
01142             __j = end();
01143           return __j;
01144         }
01145 
01146       template<typename _Kt,
01147                typename _Req =
01148                  typename __has_is_transparent<_Compare, _Kt>::type>
01149         size_type
01150         _M_count_tr(const _Kt& __k) const
01151         {
01152           auto __p = _M_equal_range_tr(__k);
01153           return std::distance(__p.first, __p.second);
01154         }
01155 
01156       template<typename _Kt,
01157                typename _Req =
01158                  typename __has_is_transparent<_Compare, _Kt>::type>
01159         iterator
01160         _M_lower_bound_tr(const _Kt& __k)
01161         {
01162           const _Rb_tree* __const_this = this;
01163           return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
01164         }
01165 
01166       template<typename _Kt,
01167                typename _Req =
01168                  typename __has_is_transparent<_Compare, _Kt>::type>
01169         const_iterator
01170         _M_lower_bound_tr(const _Kt& __k) const
01171         {
01172           auto __x = _M_begin();
01173           auto __y = _M_end();
01174           while (__x != 0)
01175             if (!_M_impl._M_key_compare(_S_key(__x), __k))
01176               {
01177                 __y = __x;
01178                 __x = _S_left(__x);
01179               }
01180             else
01181               __x = _S_right(__x);
01182           return const_iterator(__y);
01183         }
01184 
01185       template<typename _Kt,
01186                typename _Req =
01187                  typename __has_is_transparent<_Compare, _Kt>::type>
01188         iterator
01189         _M_upper_bound_tr(const _Kt& __k)
01190         {
01191           const _Rb_tree* __const_this = this;
01192           return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
01193         }
01194 
01195       template<typename _Kt,
01196                typename _Req =
01197                  typename __has_is_transparent<_Compare, _Kt>::type>
01198         const_iterator
01199         _M_upper_bound_tr(const _Kt& __k) const
01200         {
01201           auto __x = _M_begin();
01202           auto __y = _M_end();
01203           while (__x != 0)
01204             if (_M_impl._M_key_compare(__k, _S_key(__x)))
01205               {
01206                 __y = __x;
01207                 __x = _S_left(__x);
01208               }
01209             else
01210               __x = _S_right(__x);
01211           return const_iterator(__y);
01212         }
01213 
01214       template<typename _Kt,
01215                typename _Req =
01216                  typename __has_is_transparent<_Compare, _Kt>::type>
01217         pair<iterator, iterator>
01218         _M_equal_range_tr(const _Kt& __k)
01219         {
01220           const _Rb_tree* __const_this = this;
01221           auto __ret = __const_this->_M_equal_range_tr(__k);
01222           return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
01223         }
01224 
01225       template<typename _Kt,
01226                typename _Req =
01227                  typename __has_is_transparent<_Compare, _Kt>::type>
01228         pair<const_iterator, const_iterator>
01229         _M_equal_range_tr(const _Kt& __k) const
01230         {
01231           auto __low = _M_lower_bound_tr(__k);
01232           auto __high = __low;
01233           auto& __cmp = _M_impl._M_key_compare;
01234           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
01235             ++__high;
01236           return { __low, __high };
01237         }
01238 #endif
01239 
01240       // Debugging.
01241       bool
01242       __rb_verify() const;
01243 
01244 #if __cplusplus >= 201103L
01245       _Rb_tree&
01246       operator=(_Rb_tree&&)
01247       noexcept(_Alloc_traits::_S_nothrow_move()
01248                && is_nothrow_move_assignable<_Compare>::value);
01249 
01250       template<typename _Iterator>
01251         void
01252         _M_assign_unique(_Iterator, _Iterator);
01253 
01254       template<typename _Iterator>
01255         void
01256         _M_assign_equal(_Iterator, _Iterator);
01257 
01258     private:
01259       // Move elements from container with equal allocator.
01260       void
01261       _M_move_data(_Rb_tree&, std::true_type);
01262 
01263       // Move elements from container with possibly non-equal allocator,
01264       // which might result in a copy not a move.
01265       void
01266       _M_move_data(_Rb_tree&, std::false_type);
01267 
01268       // Move assignment from container with equal allocator.
01269       void
01270       _M_move_assign(_Rb_tree&, std::true_type);
01271 
01272       // Move assignment from container with possibly non-equal allocator,
01273       // which might result in a copy not a move.
01274       void
01275       _M_move_assign(_Rb_tree&, std::false_type);
01276 #endif
01277     };
01278 
01279   template<typename _Key, typename _Val, typename _KeyOfValue,
01280            typename _Compare, typename _Alloc>
01281     inline bool
01282     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01283                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01284     {
01285       return __x.size() == __y.size()
01286              && std::equal(__x.begin(), __x.end(), __y.begin());
01287     }
01288 
01289   template<typename _Key, typename _Val, typename _KeyOfValue,
01290            typename _Compare, typename _Alloc>
01291     inline bool
01292     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01293               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01294     {
01295       return std::lexicographical_compare(__x.begin(), __x.end(), 
01296                                           __y.begin(), __y.end());
01297     }
01298 
01299   template<typename _Key, typename _Val, typename _KeyOfValue,
01300            typename _Compare, typename _Alloc>
01301     inline bool
01302     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01303                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01304     { return !(__x == __y); }
01305 
01306   template<typename _Key, typename _Val, typename _KeyOfValue,
01307            typename _Compare, typename _Alloc>
01308     inline bool
01309     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01310               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01311     { return __y < __x; }
01312 
01313   template<typename _Key, typename _Val, typename _KeyOfValue,
01314            typename _Compare, typename _Alloc>
01315     inline bool
01316     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01317                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01318     { return !(__y < __x); }
01319 
01320   template<typename _Key, typename _Val, typename _KeyOfValue,
01321            typename _Compare, typename _Alloc>
01322     inline bool
01323     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01324                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01325     { return !(__x < __y); }
01326 
01327   template<typename _Key, typename _Val, typename _KeyOfValue,
01328            typename _Compare, typename _Alloc>
01329     inline void
01330     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01331          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01332     { __x.swap(__y); }
01333 
01334 #if __cplusplus >= 201103L
01335   template<typename _Key, typename _Val, typename _KeyOfValue,
01336            typename _Compare, typename _Alloc>
01337     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01338     _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
01339     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
01340     {
01341       using __eq = typename _Alloc_traits::is_always_equal;
01342       if (__x._M_root() != nullptr)
01343         _M_move_data(__x, __eq());
01344     }
01345 
01346   template<typename _Key, typename _Val, typename _KeyOfValue,
01347            typename _Compare, typename _Alloc>
01348     void
01349     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01350     _M_move_data(_Rb_tree& __x, std::true_type)
01351     {
01352       _M_root() = __x._M_root();
01353       _M_leftmost() = __x._M_leftmost();
01354       _M_rightmost() = __x._M_rightmost();
01355       _M_root()->_M_parent = _M_end();
01356 
01357       __x._M_root() = 0;
01358       __x._M_leftmost() = __x._M_end();
01359       __x._M_rightmost() = __x._M_end();
01360 
01361       this->_M_impl._M_node_count = __x._M_impl._M_node_count;
01362       __x._M_impl._M_node_count = 0;
01363     }
01364 
01365   template<typename _Key, typename _Val, typename _KeyOfValue,
01366            typename _Compare, typename _Alloc>
01367     void
01368     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01369     _M_move_data(_Rb_tree& __x, std::false_type)
01370     {
01371       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
01372           _M_move_data(__x, std::true_type());
01373       else
01374         {
01375           _Alloc_node __an(*this);
01376           auto __lbd =
01377             [&__an](const value_type& __cval)
01378             {
01379               auto& __val = const_cast<value_type&>(__cval);
01380               return __an(std::move_if_noexcept(__val));
01381             };
01382           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
01383           _M_leftmost() = _S_minimum(_M_root());
01384           _M_rightmost() = _S_maximum(_M_root());
01385           _M_impl._M_node_count = __x._M_impl._M_node_count;
01386         }
01387     }
01388 
01389   template<typename _Key, typename _Val, typename _KeyOfValue,
01390            typename _Compare, typename _Alloc>
01391     inline void
01392     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01393     _M_move_assign(_Rb_tree& __x, true_type)
01394     {
01395       clear();
01396       if (__x._M_root() != nullptr)
01397         _M_move_data(__x, std::true_type());
01398       std::__alloc_on_move(_M_get_Node_allocator(),
01399                            __x._M_get_Node_allocator());
01400     }
01401 
01402   template<typename _Key, typename _Val, typename _KeyOfValue,
01403            typename _Compare, typename _Alloc>
01404     void
01405     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01406     _M_move_assign(_Rb_tree& __x, false_type)
01407     {
01408       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
01409         return _M_move_assign(__x, true_type{});
01410 
01411       // Try to move each node reusing existing nodes and copying __x nodes
01412       // structure.
01413       _Reuse_or_alloc_node __roan(*this);
01414       _M_impl._M_reset();
01415       if (__x._M_root() != nullptr)
01416         {
01417           auto __lbd =
01418             [&__roan](const value_type& __cval)
01419             {
01420               auto& __val = const_cast<value_type&>(__cval);
01421               return __roan(std::move_if_noexcept(__val));
01422             };
01423           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
01424           _M_leftmost() = _S_minimum(_M_root());
01425           _M_rightmost() = _S_maximum(_M_root());
01426           _M_impl._M_node_count = __x._M_impl._M_node_count;
01427           __x.clear();
01428         }
01429     }
01430 
01431   template<typename _Key, typename _Val, typename _KeyOfValue,
01432            typename _Compare, typename _Alloc>
01433     inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
01434     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01435     operator=(_Rb_tree&& __x)
01436     noexcept(_Alloc_traits::_S_nothrow_move()
01437              && is_nothrow_move_assignable<_Compare>::value)
01438     {
01439       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
01440       constexpr bool __move_storage =
01441           _Alloc_traits::_S_propagate_on_move_assign()
01442           || _Alloc_traits::_S_always_equal();
01443       _M_move_assign(__x, __bool_constant<__move_storage>());
01444       return *this;
01445     }
01446 
01447   template<typename _Key, typename _Val, typename _KeyOfValue,
01448            typename _Compare, typename _Alloc>
01449     template<typename _Iterator>
01450       void
01451       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01452       _M_assign_unique(_Iterator __first, _Iterator __last)
01453       {
01454         _Reuse_or_alloc_node __roan(*this);
01455         _M_impl._M_reset();
01456         for (; __first != __last; ++__first)
01457           _M_insert_unique_(end(), *__first, __roan);
01458       }
01459 
01460   template<typename _Key, typename _Val, typename _KeyOfValue,
01461            typename _Compare, typename _Alloc>
01462     template<typename _Iterator>
01463       void
01464       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01465       _M_assign_equal(_Iterator __first, _Iterator __last)
01466       {
01467         _Reuse_or_alloc_node __roan(*this);
01468         _M_impl._M_reset();
01469         for (; __first != __last; ++__first)
01470           _M_insert_equal_(end(), *__first, __roan);
01471       }
01472 #endif
01473 
01474   template<typename _Key, typename _Val, typename _KeyOfValue,
01475            typename _Compare, typename _Alloc>
01476     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
01477     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01478     operator=(const _Rb_tree& __x)
01479     {
01480       if (this != &__x)
01481         {
01482           // Note that _Key may be a constant type.
01483 #if __cplusplus >= 201103L
01484           if (_Alloc_traits::_S_propagate_on_copy_assign())
01485             {
01486               auto& __this_alloc = this->_M_get_Node_allocator();
01487               auto& __that_alloc = __x._M_get_Node_allocator();
01488               if (!_Alloc_traits::_S_always_equal()
01489                   && __this_alloc != __that_alloc)
01490                 {
01491                   // Replacement allocator cannot free existing storage, we need
01492                   // to erase nodes first.
01493                   clear();
01494                   std::__alloc_on_copy(__this_alloc, __that_alloc);
01495                 }
01496             }
01497 #endif
01498 
01499           _Reuse_or_alloc_node __roan(*this);
01500           _M_impl._M_reset();
01501           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
01502           if (__x._M_root() != 0)
01503             {
01504               _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
01505               _M_leftmost() = _S_minimum(_M_root());
01506               _M_rightmost() = _S_maximum(_M_root());
01507               _M_impl._M_node_count = __x._M_impl._M_node_count;
01508             }
01509         }
01510 
01511       return *this;
01512     }
01513 
01514   template<typename _Key, typename _Val, typename _KeyOfValue,
01515            typename _Compare, typename _Alloc>
01516 #if __cplusplus >= 201103L
01517     template<typename _Arg, typename _NodeGen>
01518 #else
01519     template<typename _NodeGen>
01520 #endif
01521       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01522       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01523       _M_insert_(_Base_ptr __x, _Base_ptr __p,
01524 #if __cplusplus >= 201103L
01525                  _Arg&& __v,
01526 #else
01527                  const _Val& __v,
01528 #endif
01529                  _NodeGen& __node_gen)
01530       {
01531         bool __insert_left = (__x != 0 || __p == _M_end()
01532                               || _M_impl._M_key_compare(_KeyOfValue()(__v),
01533                                                         _S_key(__p)));
01534 
01535         _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
01536 
01537         _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
01538                                       this->_M_impl._M_header);
01539         ++_M_impl._M_node_count;
01540         return iterator(__z);
01541       }
01542 
01543   template<typename _Key, typename _Val, typename _KeyOfValue,
01544            typename _Compare, typename _Alloc>
01545 #if __cplusplus >= 201103L
01546     template<typename _Arg>
01547 #endif
01548     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01549     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01550 #if __cplusplus >= 201103L
01551     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
01552 #else
01553     _M_insert_lower(_Base_ptr __p, const _Val& __v)
01554 #endif
01555     {
01556       bool __insert_left = (__p == _M_end()
01557                             || !_M_impl._M_key_compare(_S_key(__p),
01558                                                        _KeyOfValue()(__v)));
01559 
01560       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
01561 
01562       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
01563                                     this->_M_impl._M_header);
01564       ++_M_impl._M_node_count;
01565       return iterator(__z);
01566     }
01567 
01568   template<typename _Key, typename _Val, typename _KeyOfValue,
01569            typename _Compare, typename _Alloc>
01570 #if __cplusplus >= 201103L
01571     template<typename _Arg>
01572 #endif
01573     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01574     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01575 #if __cplusplus >= 201103L
01576     _M_insert_equal_lower(_Arg&& __v)
01577 #else
01578     _M_insert_equal_lower(const _Val& __v)
01579 #endif
01580     {
01581       _Link_type __x = _M_begin();
01582       _Base_ptr __y = _M_end();
01583       while (__x != 0)
01584         {
01585           __y = __x;
01586           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
01587                 _S_left(__x) : _S_right(__x);
01588         }
01589       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
01590     }
01591 
01592   template<typename _Key, typename _Val, typename _KoV,
01593            typename _Compare, typename _Alloc>
01594     template<typename _NodeGen>
01595       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01596       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01597       _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
01598       {
01599         // Structural copy. __x and __p must be non-null.
01600         _Link_type __top = _M_clone_node(__x, __node_gen);
01601         __top->_M_parent = __p;
01602 
01603         __try
01604           {
01605             if (__x->_M_right)
01606               __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
01607             __p = __top;
01608             __x = _S_left(__x);
01609 
01610             while (__x != 0)
01611               {
01612                 _Link_type __y = _M_clone_node(__x, __node_gen);
01613                 __p->_M_left = __y;
01614                 __y->_M_parent = __p;
01615                 if (__x->_M_right)
01616                   __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
01617                 __p = __y;
01618                 __x = _S_left(__x);
01619               }
01620           }
01621         __catch(...)
01622           {
01623             _M_erase(__top);
01624             __throw_exception_again;
01625           }
01626         return __top;
01627       }
01628 
01629   template<typename _Key, typename _Val, typename _KeyOfValue,
01630            typename _Compare, typename _Alloc>
01631     void
01632     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01633     _M_erase(_Link_type __x)
01634     {
01635       // Erase without rebalancing.
01636       while (__x != 0)
01637         {
01638           _M_erase(_S_right(__x));
01639           _Link_type __y = _S_left(__x);
01640           _M_drop_node(__x);
01641           __x = __y;
01642         }
01643     }
01644 
01645   template<typename _Key, typename _Val, typename _KeyOfValue,
01646            typename _Compare, typename _Alloc>
01647     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01648                       _Compare, _Alloc>::iterator
01649     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01650     _M_lower_bound(_Link_type __x, _Base_ptr __y,
01651                    const _Key& __k)
01652     {
01653       while (__x != 0)
01654         if (!_M_impl._M_key_compare(_S_key(__x), __k))
01655           __y = __x, __x = _S_left(__x);
01656         else
01657           __x = _S_right(__x);
01658       return iterator(__y);
01659     }
01660 
01661   template<typename _Key, typename _Val, typename _KeyOfValue,
01662            typename _Compare, typename _Alloc>
01663     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01664                       _Compare, _Alloc>::const_iterator
01665     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01666     _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
01667                    const _Key& __k) const
01668     {
01669       while (__x != 0)
01670         if (!_M_impl._M_key_compare(_S_key(__x), __k))
01671           __y = __x, __x = _S_left(__x);
01672         else
01673           __x = _S_right(__x);
01674       return const_iterator(__y);
01675     }
01676 
01677   template<typename _Key, typename _Val, typename _KeyOfValue,
01678            typename _Compare, typename _Alloc>
01679     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01680                       _Compare, _Alloc>::iterator
01681     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01682     _M_upper_bound(_Link_type __x, _Base_ptr __y,
01683                    const _Key& __k)
01684     {
01685       while (__x != 0)
01686         if (_M_impl._M_key_compare(__k, _S_key(__x)))
01687           __y = __x, __x = _S_left(__x);
01688         else
01689           __x = _S_right(__x);
01690       return iterator(__y);
01691     }
01692 
01693   template<typename _Key, typename _Val, typename _KeyOfValue,
01694            typename _Compare, typename _Alloc>
01695     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01696                       _Compare, _Alloc>::const_iterator
01697     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01698     _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
01699                    const _Key& __k) const
01700     {
01701       while (__x != 0)
01702         if (_M_impl._M_key_compare(__k, _S_key(__x)))
01703           __y = __x, __x = _S_left(__x);
01704         else
01705           __x = _S_right(__x);
01706       return const_iterator(__y);
01707     }
01708 
01709   template<typename _Key, typename _Val, typename _KeyOfValue,
01710            typename _Compare, typename _Alloc>
01711     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01712                            _Compare, _Alloc>::iterator,
01713          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01714                            _Compare, _Alloc>::iterator>
01715     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01716     equal_range(const _Key& __k)
01717     {
01718       _Link_type __x = _M_begin();
01719       _Base_ptr __y = _M_end();
01720       while (__x != 0)
01721         {
01722           if (_M_impl._M_key_compare(_S_key(__x), __k))
01723             __x = _S_right(__x);
01724           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01725             __y = __x, __x = _S_left(__x);
01726           else
01727             {
01728               _Link_type __xu(__x);
01729               _Base_ptr __yu(__y);
01730               __y = __x, __x = _S_left(__x);
01731               __xu = _S_right(__xu);
01732               return pair<iterator,
01733                           iterator>(_M_lower_bound(__x, __y, __k),
01734                                     _M_upper_bound(__xu, __yu, __k));
01735             }
01736         }
01737       return pair<iterator, iterator>(iterator(__y),
01738                                       iterator(__y));
01739     }
01740 
01741   template<typename _Key, typename _Val, typename _KeyOfValue,
01742            typename _Compare, typename _Alloc>
01743     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01744                            _Compare, _Alloc>::const_iterator,
01745          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01746                            _Compare, _Alloc>::const_iterator>
01747     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01748     equal_range(const _Key& __k) const
01749     {
01750       _Const_Link_type __x = _M_begin();
01751       _Const_Base_ptr __y = _M_end();
01752       while (__x != 0)
01753         {
01754           if (_M_impl._M_key_compare(_S_key(__x), __k))
01755             __x = _S_right(__x);
01756           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01757             __y = __x, __x = _S_left(__x);
01758           else
01759             {
01760               _Const_Link_type __xu(__x);
01761               _Const_Base_ptr __yu(__y);
01762               __y = __x, __x = _S_left(__x);
01763               __xu = _S_right(__xu);
01764               return pair<const_iterator,
01765                           const_iterator>(_M_lower_bound(__x, __y, __k),
01766                                           _M_upper_bound(__xu, __yu, __k));
01767             }
01768         }
01769       return pair<const_iterator, const_iterator>(const_iterator(__y),
01770                                                   const_iterator(__y));
01771     }
01772 
01773   template<typename _Key, typename _Val, typename _KeyOfValue,
01774            typename _Compare, typename _Alloc>
01775     void
01776     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01777     swap(_Rb_tree& __t)
01778     _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
01779     {
01780       if (_M_root() == 0)
01781         {
01782           if (__t._M_root() != 0)
01783             {
01784               _M_root() = __t._M_root();
01785               _M_leftmost() = __t._M_leftmost();
01786               _M_rightmost() = __t._M_rightmost();
01787               _M_root()->_M_parent = _M_end();
01788               _M_impl._M_node_count = __t._M_impl._M_node_count;
01789               
01790               __t._M_impl._M_reset();
01791             }
01792         }
01793       else if (__t._M_root() == 0)
01794         {
01795           __t._M_root() = _M_root();
01796           __t._M_leftmost() = _M_leftmost();
01797           __t._M_rightmost() = _M_rightmost();
01798           __t._M_root()->_M_parent = __t._M_end();
01799           __t._M_impl._M_node_count = _M_impl._M_node_count;
01800           
01801           _M_impl._M_reset();
01802         }
01803       else
01804         {
01805           std::swap(_M_root(),__t._M_root());
01806           std::swap(_M_leftmost(),__t._M_leftmost());
01807           std::swap(_M_rightmost(),__t._M_rightmost());
01808           
01809           _M_root()->_M_parent = _M_end();
01810           __t._M_root()->_M_parent = __t._M_end();
01811           std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01812         }
01813       // No need to swap header's color as it does not change.
01814       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01815 
01816       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
01817                                 __t._M_get_Node_allocator());
01818     }
01819 
01820   template<typename _Key, typename _Val, typename _KeyOfValue,
01821            typename _Compare, typename _Alloc>
01822     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01823                            _Compare, _Alloc>::_Base_ptr,
01824          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01825                            _Compare, _Alloc>::_Base_ptr>
01826     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01827     _M_get_insert_unique_pos(const key_type& __k)
01828     {
01829       typedef pair<_Base_ptr, _Base_ptr> _Res;
01830       _Link_type __x = _M_begin();
01831       _Base_ptr __y = _M_end();
01832       bool __comp = true;
01833       while (__x != 0)
01834         {
01835           __y = __x;
01836           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
01837           __x = __comp ? _S_left(__x) : _S_right(__x);
01838         }
01839       iterator __j = iterator(__y);
01840       if (__comp)
01841         {
01842           if (__j == begin())
01843             return _Res(__x, __y);
01844           else
01845             --__j;
01846         }
01847       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
01848         return _Res(__x, __y);
01849       return _Res(__j._M_node, 0);
01850     }
01851 
01852   template<typename _Key, typename _Val, typename _KeyOfValue,
01853            typename _Compare, typename _Alloc>
01854     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01855                            _Compare, _Alloc>::_Base_ptr,
01856          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01857                            _Compare, _Alloc>::_Base_ptr>
01858     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01859     _M_get_insert_equal_pos(const key_type& __k)
01860     {
01861       typedef pair<_Base_ptr, _Base_ptr> _Res;
01862       _Link_type __x = _M_begin();
01863       _Base_ptr __y = _M_end();
01864       while (__x != 0)
01865         {
01866           __y = __x;
01867           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
01868                 _S_left(__x) : _S_right(__x);
01869         }
01870       return _Res(__x, __y);
01871     }
01872 
01873   template<typename _Key, typename _Val, typename _KeyOfValue,
01874            typename _Compare, typename _Alloc>
01875 #if __cplusplus >= 201103L
01876     template<typename _Arg>
01877 #endif
01878     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01879                            _Compare, _Alloc>::iterator, bool>
01880     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01881 #if __cplusplus >= 201103L
01882     _M_insert_unique(_Arg&& __v)
01883 #else
01884     _M_insert_unique(const _Val& __v)
01885 #endif
01886     {
01887       typedef pair<iterator, bool> _Res;
01888       pair<_Base_ptr, _Base_ptr> __res
01889         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
01890 
01891       if (__res.second)
01892         {
01893           _Alloc_node __an(*this);
01894           return _Res(_M_insert_(__res.first, __res.second,
01895                                  _GLIBCXX_FORWARD(_Arg, __v), __an),
01896                       true);
01897         }
01898 
01899       return _Res(iterator(__res.first), false);
01900     }
01901 
01902   template<typename _Key, typename _Val, typename _KeyOfValue,
01903            typename _Compare, typename _Alloc>
01904 #if __cplusplus >= 201103L
01905     template<typename _Arg>
01906 #endif
01907     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01908     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01909 #if __cplusplus >= 201103L
01910     _M_insert_equal(_Arg&& __v)
01911 #else
01912     _M_insert_equal(const _Val& __v)
01913 #endif
01914     {
01915       pair<_Base_ptr, _Base_ptr> __res
01916         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
01917       _Alloc_node __an(*this);
01918       return _M_insert_(__res.first, __res.second,
01919                         _GLIBCXX_FORWARD(_Arg, __v), __an);
01920     }
01921 
01922   template<typename _Key, typename _Val, typename _KeyOfValue,
01923            typename _Compare, typename _Alloc>
01924     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01925                            _Compare, _Alloc>::_Base_ptr,
01926          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01927                            _Compare, _Alloc>::_Base_ptr>
01928     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01929     _M_get_insert_hint_unique_pos(const_iterator __position,
01930                                   const key_type& __k)
01931     {
01932       iterator __pos = __position._M_const_cast();
01933       typedef pair<_Base_ptr, _Base_ptr> _Res;
01934 
01935       // end()
01936       if (__pos._M_node == _M_end())
01937         {
01938           if (size() > 0
01939               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
01940             return _Res(0, _M_rightmost());
01941           else
01942             return _M_get_insert_unique_pos(__k);
01943         }
01944       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
01945         {
01946           // First, try before...
01947           iterator __before = __pos;
01948           if (__pos._M_node == _M_leftmost()) // begin()
01949             return _Res(_M_leftmost(), _M_leftmost());
01950           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
01951             {
01952               if (_S_right(__before._M_node) == 0)
01953                 return _Res(0, __before._M_node);
01954               else
01955                 return _Res(__pos._M_node, __pos._M_node);
01956             }
01957           else
01958             return _M_get_insert_unique_pos(__k);
01959         }
01960       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
01961         {
01962           // ... then try after.
01963           iterator __after = __pos;
01964           if (__pos._M_node == _M_rightmost())
01965             return _Res(0, _M_rightmost());
01966           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
01967             {
01968               if (_S_right(__pos._M_node) == 0)
01969                 return _Res(0, __pos._M_node);
01970               else
01971                 return _Res(__after._M_node, __after._M_node);
01972             }
01973           else
01974             return _M_get_insert_unique_pos(__k);
01975         }
01976       else
01977         // Equivalent keys.
01978         return _Res(__pos._M_node, 0);
01979     }
01980 
01981   template<typename _Key, typename _Val, typename _KeyOfValue,
01982            typename _Compare, typename _Alloc>
01983 #if __cplusplus >= 201103L
01984     template<typename _Arg, typename _NodeGen>
01985 #else
01986     template<typename _NodeGen>
01987 #endif
01988       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01989       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01990       _M_insert_unique_(const_iterator __position,
01991 #if __cplusplus >= 201103L
01992                         _Arg&& __v,
01993 #else
01994                         const _Val& __v,
01995 #endif
01996                         _NodeGen& __node_gen)
01997     {
01998       pair<_Base_ptr, _Base_ptr> __res
01999         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
02000 
02001       if (__res.second)
02002         return _M_insert_(__res.first, __res.second,
02003                           _GLIBCXX_FORWARD(_Arg, __v),
02004                           __node_gen);
02005       return iterator(__res.first);
02006     }
02007 
02008   template<typename _Key, typename _Val, typename _KeyOfValue,
02009            typename _Compare, typename _Alloc>
02010     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
02011                            _Compare, _Alloc>::_Base_ptr,
02012          typename _Rb_tree<_Key, _Val, _KeyOfValue,
02013                            _Compare, _Alloc>::_Base_ptr>
02014     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02015     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
02016     {
02017       iterator __pos = __position._M_const_cast();
02018       typedef pair<_Base_ptr, _Base_ptr> _Res;
02019 
02020       // end()
02021       if (__pos._M_node == _M_end())
02022         {
02023           if (size() > 0
02024               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
02025             return _Res(0, _M_rightmost());
02026           else
02027             return _M_get_insert_equal_pos(__k);
02028         }
02029       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
02030         {
02031           // First, try before...
02032           iterator __before = __pos;
02033           if (__pos._M_node == _M_leftmost()) // begin()
02034             return _Res(_M_leftmost(), _M_leftmost());
02035           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
02036             {
02037               if (_S_right(__before._M_node) == 0)
02038                 return _Res(0, __before._M_node);
02039               else
02040                 return _Res(__pos._M_node, __pos._M_node);
02041             }
02042           else
02043             return _M_get_insert_equal_pos(__k);
02044         }
02045       else
02046         {
02047           // ... then try after.  
02048           iterator __after = __pos;
02049           if (__pos._M_node == _M_rightmost())
02050             return _Res(0, _M_rightmost());
02051           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
02052             {
02053               if (_S_right(__pos._M_node) == 0)
02054                 return _Res(0, __pos._M_node);
02055               else
02056                 return _Res(__after._M_node, __after._M_node);
02057             }
02058           else
02059             return _Res(0, 0);
02060         }
02061     }
02062 
02063   template<typename _Key, typename _Val, typename _KeyOfValue,
02064            typename _Compare, typename _Alloc>
02065 #if __cplusplus >= 201103L
02066     template<typename _Arg, typename _NodeGen>
02067 #else
02068     template<typename _NodeGen>
02069 #endif
02070       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02071       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02072       _M_insert_equal_(const_iterator __position,
02073 #if __cplusplus >= 201103L
02074                        _Arg&& __v,
02075 #else
02076                        const _Val& __v,
02077 #endif
02078                        _NodeGen& __node_gen)
02079       {
02080         pair<_Base_ptr, _Base_ptr> __res
02081           = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
02082 
02083         if (__res.second)
02084           return _M_insert_(__res.first, __res.second,
02085                             _GLIBCXX_FORWARD(_Arg, __v),
02086                             __node_gen);
02087 
02088         return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
02089       }
02090 
02091 #if __cplusplus >= 201103L
02092   template<typename _Key, typename _Val, typename _KeyOfValue,
02093            typename _Compare, typename _Alloc>
02094     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02095     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02096     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
02097     {
02098       bool __insert_left = (__x != 0 || __p == _M_end()
02099                             || _M_impl._M_key_compare(_S_key(__z),
02100                                                       _S_key(__p)));
02101 
02102       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
02103                                     this->_M_impl._M_header);
02104       ++_M_impl._M_node_count;
02105       return iterator(__z);
02106     }
02107 
02108   template<typename _Key, typename _Val, typename _KeyOfValue,
02109            typename _Compare, typename _Alloc>
02110     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02111     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02112     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
02113     {
02114       bool __insert_left = (__p == _M_end()
02115                             || !_M_impl._M_key_compare(_S_key(__p),
02116                                                        _S_key(__z)));
02117 
02118       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
02119                                     this->_M_impl._M_header);
02120       ++_M_impl._M_node_count;
02121       return iterator(__z);
02122     }
02123 
02124   template<typename _Key, typename _Val, typename _KeyOfValue,
02125            typename _Compare, typename _Alloc>
02126     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02127     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02128     _M_insert_equal_lower_node(_Link_type __z)
02129     {
02130       _Link_type __x = _M_begin();
02131       _Base_ptr __y = _M_end();
02132       while (__x != 0)
02133         {
02134           __y = __x;
02135           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
02136                 _S_left(__x) : _S_right(__x);
02137         }
02138       return _M_insert_lower_node(__y, __z);
02139     }
02140 
02141   template<typename _Key, typename _Val, typename _KeyOfValue,
02142            typename _Compare, typename _Alloc>
02143     template<typename... _Args>
02144       pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
02145                              _Compare, _Alloc>::iterator, bool>
02146       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02147       _M_emplace_unique(_Args&&... __args)
02148       {
02149         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02150 
02151         __try
02152           {
02153             typedef pair<iterator, bool> _Res;
02154             auto __res = _M_get_insert_unique_pos(_S_key(__z));
02155             if (__res.second)
02156               return _Res(_M_insert_node(__res.first, __res.second, __z), true);
02157         
02158             _M_drop_node(__z);
02159             return _Res(iterator(__res.first), false);
02160           }
02161         __catch(...)
02162           {
02163             _M_drop_node(__z);
02164             __throw_exception_again;
02165           }
02166       }
02167 
02168   template<typename _Key, typename _Val, typename _KeyOfValue,
02169            typename _Compare, typename _Alloc>
02170     template<typename... _Args>
02171       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02172       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02173       _M_emplace_equal(_Args&&... __args)
02174       {
02175         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02176 
02177         __try
02178           {
02179             auto __res = _M_get_insert_equal_pos(_S_key(__z));
02180             return _M_insert_node(__res.first, __res.second, __z);
02181           }
02182         __catch(...)
02183           {
02184             _M_drop_node(__z);
02185             __throw_exception_again;
02186           }
02187       }
02188 
02189   template<typename _Key, typename _Val, typename _KeyOfValue,
02190            typename _Compare, typename _Alloc>
02191     template<typename... _Args>
02192       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02193       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02194       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
02195       {
02196         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02197 
02198         __try
02199           {
02200             auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
02201 
02202             if (__res.second)
02203               return _M_insert_node(__res.first, __res.second, __z);
02204 
02205             _M_drop_node(__z);
02206             return iterator(__res.first);
02207           }
02208         __catch(...)
02209           {
02210             _M_drop_node(__z);
02211             __throw_exception_again;
02212           }
02213       }
02214 
02215   template<typename _Key, typename _Val, typename _KeyOfValue,
02216            typename _Compare, typename _Alloc>
02217     template<typename... _Args>
02218       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02219       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02220       _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
02221       {
02222         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02223 
02224         __try
02225           {
02226             auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
02227 
02228             if (__res.second)
02229               return _M_insert_node(__res.first, __res.second, __z);
02230 
02231             return _M_insert_equal_lower_node(__z);
02232           }
02233         __catch(...)
02234           {
02235             _M_drop_node(__z);
02236             __throw_exception_again;
02237           }
02238       }
02239 #endif
02240 
02241   template<typename _Key, typename _Val, typename _KoV,
02242            typename _Cmp, typename _Alloc>
02243     template<class _II>
02244       void
02245       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
02246       _M_insert_unique(_II __first, _II __last)
02247       {
02248         _Alloc_node __an(*this);
02249         for (; __first != __last; ++__first)
02250           _M_insert_unique_(end(), *__first, __an);
02251       }
02252 
02253   template<typename _Key, typename _Val, typename _KoV,
02254            typename _Cmp, typename _Alloc>
02255     template<class _II>
02256       void
02257       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
02258       _M_insert_equal(_II __first, _II __last)
02259       {
02260         _Alloc_node __an(*this);
02261         for (; __first != __last; ++__first)
02262           _M_insert_equal_(end(), *__first, __an);
02263       }
02264 
02265   template<typename _Key, typename _Val, typename _KeyOfValue,
02266            typename _Compare, typename _Alloc>
02267     void
02268     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02269     _M_erase_aux(const_iterator __position)
02270     {
02271       _Link_type __y =
02272         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
02273                                 (const_cast<_Base_ptr>(__position._M_node),
02274                                  this->_M_impl._M_header));
02275       _M_drop_node(__y);
02276       --_M_impl._M_node_count;
02277     }
02278 
02279   template<typename _Key, typename _Val, typename _KeyOfValue,
02280            typename _Compare, typename _Alloc>
02281     void
02282     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02283     _M_erase_aux(const_iterator __first, const_iterator __last)
02284     {
02285       if (__first == begin() && __last == end())
02286         clear();
02287       else
02288         while (__first != __last)
02289           erase(__first++);
02290     }
02291 
02292   template<typename _Key, typename _Val, typename _KeyOfValue,
02293            typename _Compare, typename _Alloc>
02294     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
02295     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02296     erase(const _Key& __x)
02297     {
02298       pair<iterator, iterator> __p = equal_range(__x);
02299       const size_type __old_size = size();
02300       erase(__p.first, __p.second);
02301       return __old_size - size();
02302     }
02303 
02304   template<typename _Key, typename _Val, typename _KeyOfValue,
02305            typename _Compare, typename _Alloc>
02306     void
02307     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02308     erase(const _Key* __first, const _Key* __last)
02309     {
02310       while (__first != __last)
02311         erase(*__first++);
02312     }
02313 
02314   template<typename _Key, typename _Val, typename _KeyOfValue,
02315            typename _Compare, typename _Alloc>
02316     typename _Rb_tree<_Key, _Val, _KeyOfValue,
02317                       _Compare, _Alloc>::iterator
02318     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02319     find(const _Key& __k)
02320     {
02321       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
02322       return (__j == end()
02323               || _M_impl._M_key_compare(__k,
02324                                         _S_key(__j._M_node))) ? end() : __j;
02325     }
02326 
02327   template<typename _Key, typename _Val, typename _KeyOfValue,
02328            typename _Compare, typename _Alloc>
02329     typename _Rb_tree<_Key, _Val, _KeyOfValue,
02330                       _Compare, _Alloc>::const_iterator
02331     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02332     find(const _Key& __k) const
02333     {
02334       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
02335       return (__j == end()
02336               || _M_impl._M_key_compare(__k, 
02337                                         _S_key(__j._M_node))) ? end() : __j;
02338     }
02339 
02340   template<typename _Key, typename _Val, typename _KeyOfValue,
02341            typename _Compare, typename _Alloc>
02342     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
02343     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02344     count(const _Key& __k) const
02345     {
02346       pair<const_iterator, const_iterator> __p = equal_range(__k);
02347       const size_type __n = std::distance(__p.first, __p.second);
02348       return __n;
02349     }
02350 
02351   _GLIBCXX_PURE unsigned int
02352   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
02353                        const _Rb_tree_node_base* __root) throw ();
02354 
02355   template<typename _Key, typename _Val, typename _KeyOfValue,
02356            typename _Compare, typename _Alloc>
02357     bool
02358     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
02359     {
02360       if (_M_impl._M_node_count == 0 || begin() == end())
02361         return _M_impl._M_node_count == 0 && begin() == end()
02362                && this->_M_impl._M_header._M_left == _M_end()
02363                && this->_M_impl._M_header._M_right == _M_end();
02364 
02365       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
02366       for (const_iterator __it = begin(); __it != end(); ++__it)
02367         {
02368           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
02369           _Const_Link_type __L = _S_left(__x);
02370           _Const_Link_type __R = _S_right(__x);
02371 
02372           if (__x->_M_color == _S_red)
02373             if ((__L && __L->_M_color == _S_red)
02374                 || (__R && __R->_M_color == _S_red))
02375               return false;
02376 
02377           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
02378             return false;
02379           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
02380             return false;
02381 
02382           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
02383             return false;
02384         }
02385 
02386       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
02387         return false;
02388       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
02389         return false;
02390       return true;
02391     }
02392 
02393 _GLIBCXX_END_NAMESPACE_VERSION
02394 } // namespace
02395 
02396 #endif