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