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, __x._M_get_Node_allocator())
00845       {
00846         if (__x._M_root() != 0)
00847           _M_move_data(__x, std::true_type());
00848       }
00849 
00850       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
00851       : _Rb_tree(std::move(__x), _Node_allocator(__a))
00852       { }
00853 
00854       _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
00855 #endif
00856 
00857       ~_Rb_tree() _GLIBCXX_NOEXCEPT
00858       { _M_erase(_M_begin()); }
00859 
00860       _Rb_tree&
00861       operator=(const _Rb_tree& __x);
00862 
00863       // Accessors.
00864       _Compare
00865       key_comp() const
00866       { return _M_impl._M_key_compare; }
00867 
00868       iterator
00869       begin() _GLIBCXX_NOEXCEPT
00870       { return iterator(this->_M_impl._M_header._M_left); }
00871 
00872       const_iterator
00873       begin() const _GLIBCXX_NOEXCEPT
00874       { return const_iterator(this->_M_impl._M_header._M_left); }
00875 
00876       iterator
00877       end() _GLIBCXX_NOEXCEPT
00878       { return iterator(&this->_M_impl._M_header); }
00879 
00880       const_iterator
00881       end() const _GLIBCXX_NOEXCEPT
00882       { return const_iterator(&this->_M_impl._M_header); }
00883 
00884       reverse_iterator
00885       rbegin() _GLIBCXX_NOEXCEPT
00886       { return reverse_iterator(end()); }
00887 
00888       const_reverse_iterator
00889       rbegin() const _GLIBCXX_NOEXCEPT
00890       { return const_reverse_iterator(end()); }
00891 
00892       reverse_iterator
00893       rend() _GLIBCXX_NOEXCEPT
00894       { return reverse_iterator(begin()); }
00895 
00896       const_reverse_iterator
00897       rend() const _GLIBCXX_NOEXCEPT
00898       { return const_reverse_iterator(begin()); }
00899 
00900       bool
00901       empty() const _GLIBCXX_NOEXCEPT
00902       { return _M_impl._M_node_count == 0; }
00903 
00904       size_type
00905       size() const _GLIBCXX_NOEXCEPT 
00906       { return _M_impl._M_node_count; }
00907 
00908       size_type
00909       max_size() const _GLIBCXX_NOEXCEPT
00910       { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
00911 
00912       void
00913 #if __cplusplus >= 201103L
00914       swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
00915 #else
00916       swap(_Rb_tree& __t);
00917 #endif
00918 
00919       // Insert/erase.
00920 #if __cplusplus >= 201103L
00921       template<typename _Arg>
00922         pair<iterator, bool>
00923         _M_insert_unique(_Arg&& __x);
00924 
00925       template<typename _Arg>
00926         iterator
00927         _M_insert_equal(_Arg&& __x);
00928 
00929       template<typename _Arg, typename _NodeGen>
00930         iterator
00931         _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
00932 
00933       template<typename _Arg>
00934         iterator
00935         _M_insert_unique_(const_iterator __pos, _Arg&& __x)
00936         {
00937           _Alloc_node __an(*this);
00938           return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
00939         }
00940 
00941       template<typename _Arg, typename _NodeGen>
00942         iterator
00943         _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
00944 
00945       template<typename _Arg>
00946         iterator
00947         _M_insert_equal_(const_iterator __pos, _Arg&& __x)
00948         {
00949           _Alloc_node __an(*this);
00950           return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
00951         }
00952 
00953       template<typename... _Args>
00954         pair<iterator, bool>
00955         _M_emplace_unique(_Args&&... __args);
00956 
00957       template<typename... _Args>
00958         iterator
00959         _M_emplace_equal(_Args&&... __args);
00960 
00961       template<typename... _Args>
00962         iterator
00963         _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
00964 
00965       template<typename... _Args>
00966         iterator
00967         _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
00968 #else
00969       pair<iterator, bool>
00970       _M_insert_unique(const value_type& __x);
00971 
00972       iterator
00973       _M_insert_equal(const value_type& __x);
00974 
00975       template<typename _NodeGen>
00976         iterator
00977         _M_insert_unique_(const_iterator __pos, const value_type& __x,
00978                           _NodeGen&);
00979 
00980       iterator
00981       _M_insert_unique_(const_iterator __pos, const value_type& __x)
00982       {
00983         _Alloc_node __an(*this);
00984         return _M_insert_unique_(__pos, __x, __an);
00985       }
00986 
00987       template<typename _NodeGen>
00988         iterator
00989         _M_insert_equal_(const_iterator __pos, const value_type& __x,
00990                          _NodeGen&);
00991       iterator
00992       _M_insert_equal_(const_iterator __pos, const value_type& __x)
00993       {
00994         _Alloc_node __an(*this);
00995         return _M_insert_equal_(__pos, __x, __an);
00996       }
00997 #endif
00998 
00999       template<typename _InputIterator>
01000         void
01001         _M_insert_unique(_InputIterator __first, _InputIterator __last);
01002 
01003       template<typename _InputIterator>
01004         void
01005         _M_insert_equal(_InputIterator __first, _InputIterator __last);
01006 
01007     private:
01008       void
01009       _M_erase_aux(const_iterator __position);
01010 
01011       void
01012       _M_erase_aux(const_iterator __first, const_iterator __last);
01013 
01014     public:
01015 #if __cplusplus >= 201103L
01016       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01017       // DR 130. Associative erase should return an iterator.
01018       _GLIBCXX_ABI_TAG_CXX11
01019       iterator
01020       erase(const_iterator __position)
01021       {
01022         const_iterator __result = __position;
01023         ++__result;
01024         _M_erase_aux(__position);
01025         return __result._M_const_cast();
01026       }
01027 
01028       // LWG 2059.
01029       _GLIBCXX_ABI_TAG_CXX11
01030       iterator
01031       erase(iterator __position)
01032       {
01033         iterator __result = __position;
01034         ++__result;
01035         _M_erase_aux(__position);
01036         return __result;
01037       }
01038 #else
01039       void
01040       erase(iterator __position)
01041       { _M_erase_aux(__position); }
01042 
01043       void
01044       erase(const_iterator __position)
01045       { _M_erase_aux(__position); }
01046 #endif
01047       size_type
01048       erase(const key_type& __x);
01049 
01050 #if __cplusplus >= 201103L
01051       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01052       // DR 130. Associative erase should return an iterator.
01053       _GLIBCXX_ABI_TAG_CXX11
01054       iterator
01055       erase(const_iterator __first, const_iterator __last)
01056       {
01057         _M_erase_aux(__first, __last);
01058         return __last._M_const_cast();
01059       }
01060 #else
01061       void
01062       erase(iterator __first, iterator __last)
01063       { _M_erase_aux(__first, __last); }
01064 
01065       void
01066       erase(const_iterator __first, const_iterator __last)
01067       { _M_erase_aux(__first, __last); }
01068 #endif
01069       void
01070       erase(const key_type* __first, const key_type* __last);
01071 
01072       void
01073       clear() _GLIBCXX_NOEXCEPT
01074       {
01075         _M_erase(_M_begin());
01076         _M_impl._M_reset();
01077       }
01078 
01079       // Set operations.
01080       iterator
01081       find(const key_type& __k);
01082 
01083       const_iterator
01084       find(const key_type& __k) const;
01085 
01086       size_type
01087       count(const key_type& __k) const;
01088 
01089       iterator
01090       lower_bound(const key_type& __k)
01091       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
01092 
01093       const_iterator
01094       lower_bound(const key_type& __k) const
01095       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
01096 
01097       iterator
01098       upper_bound(const key_type& __k)
01099       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
01100 
01101       const_iterator
01102       upper_bound(const key_type& __k) const
01103       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
01104 
01105       pair<iterator, iterator>
01106       equal_range(const key_type& __k);
01107 
01108       pair<const_iterator, const_iterator>
01109       equal_range(const key_type& __k) const;
01110 
01111 #if __cplusplus > 201103L
01112       template<typename _Cmp, typename _Kt, typename = __void_t<>>
01113         struct __is_transparent { };
01114 
01115       template<typename _Cmp, typename _Kt>
01116         struct
01117         __is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
01118         { typedef void type; };
01119 
01120       static auto _S_iter(_Link_type __x) { return iterator(__x); }
01121 
01122       static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
01123 
01124       template<typename _Cmp, typename _Link, typename _Kt>
01125         static auto
01126         _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
01127         {
01128           while (__x != 0)
01129             if (!__cmp(_S_key(__x), __k))
01130               __y = __x, __x = _S_left(__x);
01131             else
01132               __x = _S_right(__x);
01133           return _S_iter(__y);
01134         }
01135 
01136       template<typename _Cmp, typename _Link, typename _Kt>
01137         static auto
01138         _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
01139         {
01140           while (__x != 0)
01141             if (__cmp(__k, _S_key(__x)))
01142               __y = __x, __x = _S_left(__x);
01143             else
01144               __x = _S_right(__x);
01145           return _S_iter(__y);
01146         }
01147 
01148       template<typename _Kt,
01149                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01150         iterator
01151         _M_find_tr(const _Kt& __k)
01152         {
01153           auto& __cmp = _M_impl._M_key_compare;
01154           auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
01155           return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
01156             ? end() : __j;
01157         }
01158 
01159       template<typename _Kt,
01160                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01161         const_iterator
01162         _M_find_tr(const _Kt& __k) const
01163         {
01164           auto& __cmp = _M_impl._M_key_compare;
01165           auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
01166           return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
01167             ? end() : __j;
01168         }
01169 
01170       template<typename _Kt,
01171                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01172         size_type
01173         _M_count_tr(const _Kt& __k) const
01174         {
01175           auto __p = _M_equal_range_tr(__k);
01176           return std::distance(__p.first, __p.second);
01177         }
01178 
01179       template<typename _Kt,
01180                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01181         iterator
01182         _M_lower_bound_tr(const _Kt& __k)
01183         {
01184           auto& __cmp = _M_impl._M_key_compare;
01185           return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
01186         }
01187 
01188       template<typename _Kt,
01189                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01190         const_iterator
01191         _M_lower_bound_tr(const _Kt& __k) const
01192         {
01193           auto& __cmp = _M_impl._M_key_compare;
01194           return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
01195         }
01196 
01197       template<typename _Kt,
01198                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01199         iterator
01200         _M_upper_bound_tr(const _Kt& __k)
01201         {
01202           auto& __cmp = _M_impl._M_key_compare;
01203           return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
01204         }
01205 
01206       template<typename _Kt,
01207                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01208         const_iterator
01209         _M_upper_bound_tr(const _Kt& __k) const
01210         {
01211           auto& __cmp = _M_impl._M_key_compare;
01212           return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
01213         }
01214 
01215       template<typename _Kt,
01216                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01217         pair<iterator, iterator>
01218         _M_equal_range_tr(const _Kt& __k)
01219         {
01220           auto __low = _M_lower_bound_tr(__k);
01221           auto __high = __low;
01222           auto& __cmp = _M_impl._M_key_compare;
01223           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
01224             ++__high;
01225           return { __low, __high };
01226         }
01227 
01228       template<typename _Kt,
01229                typename _Req = typename __is_transparent<_Compare, _Kt>::type>
01230         pair<const_iterator, const_iterator>
01231         _M_equal_range_tr(const _Kt& __k) const
01232         {
01233           auto __low = _M_lower_bound_tr(__k);
01234           auto __high = __low;
01235           auto& __cmp = _M_impl._M_key_compare;
01236           while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
01237             ++__high;
01238           return { __low, __high };
01239         }
01240 #endif
01241 
01242       // Debugging.
01243       bool
01244       __rb_verify() const;
01245 
01246 #if __cplusplus >= 201103L
01247       _Rb_tree&
01248       operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move());
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 #endif
01268     };
01269 
01270   template<typename _Key, typename _Val, typename _KeyOfValue,
01271            typename _Compare, typename _Alloc>
01272     inline bool
01273     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01274                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01275     {
01276       return __x.size() == __y.size()
01277              && std::equal(__x.begin(), __x.end(), __y.begin());
01278     }
01279 
01280   template<typename _Key, typename _Val, typename _KeyOfValue,
01281            typename _Compare, typename _Alloc>
01282     inline bool
01283     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01284               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01285     {
01286       return std::lexicographical_compare(__x.begin(), __x.end(), 
01287                                           __y.begin(), __y.end());
01288     }
01289 
01290   template<typename _Key, typename _Val, typename _KeyOfValue,
01291            typename _Compare, typename _Alloc>
01292     inline bool
01293     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01294                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01295     { return !(__x == __y); }
01296 
01297   template<typename _Key, typename _Val, typename _KeyOfValue,
01298            typename _Compare, typename _Alloc>
01299     inline bool
01300     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01301               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01302     { return __y < __x; }
01303 
01304   template<typename _Key, typename _Val, typename _KeyOfValue,
01305            typename _Compare, typename _Alloc>
01306     inline bool
01307     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01308                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01309     { return !(__y < __x); }
01310 
01311   template<typename _Key, typename _Val, typename _KeyOfValue,
01312            typename _Compare, typename _Alloc>
01313     inline bool
01314     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01315                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01316     { return !(__x < __y); }
01317 
01318   template<typename _Key, typename _Val, typename _KeyOfValue,
01319            typename _Compare, typename _Alloc>
01320     inline void
01321     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
01322          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
01323     { __x.swap(__y); }
01324 
01325 #if __cplusplus >= 201103L
01326   template<typename _Key, typename _Val, typename _KeyOfValue,
01327            typename _Compare, typename _Alloc>
01328     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01329     _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
01330     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
01331     {
01332       using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
01333       if (__x._M_root() != nullptr)
01334         _M_move_data(__x, __eq());
01335     }
01336 
01337   template<typename _Key, typename _Val, typename _KeyOfValue,
01338            typename _Compare, typename _Alloc>
01339     void
01340     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01341     _M_move_data(_Rb_tree& __x, std::true_type)
01342     {
01343       _M_root() = __x._M_root();
01344       _M_leftmost() = __x._M_leftmost();
01345       _M_rightmost() = __x._M_rightmost();
01346       _M_root()->_M_parent = _M_end();
01347 
01348       __x._M_root() = 0;
01349       __x._M_leftmost() = __x._M_end();
01350       __x._M_rightmost() = __x._M_end();
01351 
01352       this->_M_impl._M_node_count = __x._M_impl._M_node_count;
01353       __x._M_impl._M_node_count = 0;
01354     }
01355 
01356   template<typename _Key, typename _Val, typename _KeyOfValue,
01357            typename _Compare, typename _Alloc>
01358     void
01359     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01360     _M_move_data(_Rb_tree& __x, std::false_type)
01361     {
01362       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
01363           _M_move_data(__x, std::true_type());
01364       else
01365         {
01366           _Alloc_node __an(*this);
01367           auto __lbd =
01368             [&__an](const value_type& __cval)
01369             {
01370               auto& __val = const_cast<value_type&>(__cval);
01371               return __an(std::move_if_noexcept(__val));
01372             };
01373           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
01374           _M_leftmost() = _S_minimum(_M_root());
01375           _M_rightmost() = _S_maximum(_M_root());
01376           _M_impl._M_node_count = __x._M_impl._M_node_count;
01377         }
01378     }
01379 
01380   template<typename _Key, typename _Val, typename _KeyOfValue,
01381            typename _Compare, typename _Alloc>
01382     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
01383     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01384     operator=(_Rb_tree&& __x)
01385     noexcept(_Alloc_traits::_S_nothrow_move())
01386     {
01387       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
01388       if (_Alloc_traits::_S_propagate_on_move_assign()
01389           || _Alloc_traits::_S_always_equal()
01390           || _M_get_Node_allocator() == __x._M_get_Node_allocator())
01391         {
01392           clear();
01393           if (__x._M_root() != nullptr)
01394             _M_move_data(__x, std::true_type());
01395           std::__alloc_on_move(_M_get_Node_allocator(),
01396                                __x._M_get_Node_allocator());
01397           return *this;
01398         }
01399 
01400       // Try to move each node reusing existing nodes and copying __x nodes
01401       // structure.
01402       _Reuse_or_alloc_node __roan(*this);
01403       _M_impl._M_reset();
01404       if (__x._M_root() != nullptr)
01405         {
01406           auto __lbd =
01407             [&__roan](const value_type& __cval)
01408             {
01409               auto& __val = const_cast<value_type&>(__cval);
01410               return __roan(std::move_if_noexcept(__val));
01411             };
01412           _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
01413           _M_leftmost() = _S_minimum(_M_root());
01414           _M_rightmost() = _S_maximum(_M_root());
01415           _M_impl._M_node_count = __x._M_impl._M_node_count;
01416           __x.clear();
01417         }
01418       return *this;
01419     }
01420 
01421   template<typename _Key, typename _Val, typename _KeyOfValue,
01422            typename _Compare, typename _Alloc>
01423     template<typename _Iterator>
01424       void
01425       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01426       _M_assign_unique(_Iterator __first, _Iterator __last)
01427       {
01428         _Reuse_or_alloc_node __roan(*this);
01429         _M_impl._M_reset();
01430         for (; __first != __last; ++__first)
01431           _M_insert_unique_(end(), *__first, __roan);
01432       }
01433 
01434   template<typename _Key, typename _Val, typename _KeyOfValue,
01435            typename _Compare, typename _Alloc>
01436     template<typename _Iterator>
01437       void
01438       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01439       _M_assign_equal(_Iterator __first, _Iterator __last)
01440       {
01441         _Reuse_or_alloc_node __roan(*this);
01442         _M_impl._M_reset();
01443         for (; __first != __last; ++__first)
01444           _M_insert_equal_(end(), *__first, __roan);
01445       }
01446 #endif
01447 
01448   template<typename _Key, typename _Val, typename _KeyOfValue,
01449            typename _Compare, typename _Alloc>
01450     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
01451     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01452     operator=(const _Rb_tree& __x)
01453     {
01454       if (this != &__x)
01455         {
01456           // Note that _Key may be a constant type.
01457 #if __cplusplus >= 201103L
01458           if (_Alloc_traits::_S_propagate_on_copy_assign())
01459             {
01460               auto& __this_alloc = this->_M_get_Node_allocator();
01461               auto& __that_alloc = __x._M_get_Node_allocator();
01462               if (!_Alloc_traits::_S_always_equal()
01463                   && __this_alloc != __that_alloc)
01464                 {
01465                   // Replacement allocator cannot free existing storage, we need
01466                   // to erase nodes first.
01467                   clear();
01468                   std::__alloc_on_copy(__this_alloc, __that_alloc);
01469                 }
01470             }
01471 #endif
01472 
01473           _Reuse_or_alloc_node __roan(*this);
01474           _M_impl._M_reset();
01475           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
01476           if (__x._M_root() != 0)
01477             {
01478               _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
01479               _M_leftmost() = _S_minimum(_M_root());
01480               _M_rightmost() = _S_maximum(_M_root());
01481               _M_impl._M_node_count = __x._M_impl._M_node_count;
01482             }
01483         }
01484 
01485       return *this;
01486     }
01487 
01488   template<typename _Key, typename _Val, typename _KeyOfValue,
01489            typename _Compare, typename _Alloc>
01490 #if __cplusplus >= 201103L
01491     template<typename _Arg, typename _NodeGen>
01492 #else
01493     template<typename _NodeGen>
01494 #endif
01495       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01496       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01497       _M_insert_(_Base_ptr __x, _Base_ptr __p,
01498 #if __cplusplus >= 201103L
01499                  _Arg&& __v,
01500 #else
01501                  const _Val& __v,
01502 #endif
01503                  _NodeGen& __node_gen)
01504       {
01505         bool __insert_left = (__x != 0 || __p == _M_end()
01506                               || _M_impl._M_key_compare(_KeyOfValue()(__v),
01507                                                         _S_key(__p)));
01508 
01509         _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
01510 
01511         _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
01512                                       this->_M_impl._M_header);
01513         ++_M_impl._M_node_count;
01514         return iterator(__z);
01515       }
01516 
01517   template<typename _Key, typename _Val, typename _KeyOfValue,
01518            typename _Compare, typename _Alloc>
01519 #if __cplusplus >= 201103L
01520     template<typename _Arg>
01521 #endif
01522     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01523     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01524 #if __cplusplus >= 201103L
01525     _M_insert_lower(_Base_ptr __p, _Arg&& __v)
01526 #else
01527     _M_insert_lower(_Base_ptr __p, const _Val& __v)
01528 #endif
01529     {
01530       bool __insert_left = (__p == _M_end()
01531                             || !_M_impl._M_key_compare(_S_key(__p),
01532                                                        _KeyOfValue()(__v)));
01533 
01534       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
01535 
01536       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
01537                                     this->_M_impl._M_header);
01538       ++_M_impl._M_node_count;
01539       return iterator(__z);
01540     }
01541 
01542   template<typename _Key, typename _Val, typename _KeyOfValue,
01543            typename _Compare, typename _Alloc>
01544 #if __cplusplus >= 201103L
01545     template<typename _Arg>
01546 #endif
01547     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01548     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01549 #if __cplusplus >= 201103L
01550     _M_insert_equal_lower(_Arg&& __v)
01551 #else
01552     _M_insert_equal_lower(const _Val& __v)
01553 #endif
01554     {
01555       _Link_type __x = _M_begin();
01556       _Link_type __y = _M_end();
01557       while (__x != 0)
01558         {
01559           __y = __x;
01560           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
01561                 _S_left(__x) : _S_right(__x);
01562         }
01563       return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
01564     }
01565 
01566   template<typename _Key, typename _Val, typename _KoV,
01567            typename _Compare, typename _Alloc>
01568     template<typename _NodeGen>
01569       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
01570       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
01571       _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
01572       {
01573         // Structural copy. __x and __p must be non-null.
01574         _Link_type __top = _M_clone_node(__x, __node_gen);
01575         __top->_M_parent = __p;
01576 
01577         __try
01578           {
01579             if (__x->_M_right)
01580               __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
01581             __p = __top;
01582             __x = _S_left(__x);
01583 
01584             while (__x != 0)
01585               {
01586                 _Link_type __y = _M_clone_node(__x, __node_gen);
01587                 __p->_M_left = __y;
01588                 __y->_M_parent = __p;
01589                 if (__x->_M_right)
01590                   __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
01591                 __p = __y;
01592                 __x = _S_left(__x);
01593               }
01594           }
01595         __catch(...)
01596           {
01597             _M_erase(__top);
01598             __throw_exception_again;
01599           }
01600         return __top;
01601       }
01602 
01603   template<typename _Key, typename _Val, typename _KeyOfValue,
01604            typename _Compare, typename _Alloc>
01605     void
01606     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01607     _M_erase(_Link_type __x)
01608     {
01609       // Erase without rebalancing.
01610       while (__x != 0)
01611         {
01612           _M_erase(_S_right(__x));
01613           _Link_type __y = _S_left(__x);
01614           _M_drop_node(__x);
01615           __x = __y;
01616         }
01617     }
01618 
01619   template<typename _Key, typename _Val, typename _KeyOfValue,
01620            typename _Compare, typename _Alloc>
01621     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01622                       _Compare, _Alloc>::iterator
01623     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01624     _M_lower_bound(_Link_type __x, _Link_type __y,
01625                    const _Key& __k)
01626     {
01627       while (__x != 0)
01628         if (!_M_impl._M_key_compare(_S_key(__x), __k))
01629           __y = __x, __x = _S_left(__x);
01630         else
01631           __x = _S_right(__x);
01632       return iterator(__y);
01633     }
01634 
01635   template<typename _Key, typename _Val, typename _KeyOfValue,
01636            typename _Compare, typename _Alloc>
01637     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01638                       _Compare, _Alloc>::const_iterator
01639     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01640     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
01641                    const _Key& __k) const
01642     {
01643       while (__x != 0)
01644         if (!_M_impl._M_key_compare(_S_key(__x), __k))
01645           __y = __x, __x = _S_left(__x);
01646         else
01647           __x = _S_right(__x);
01648       return const_iterator(__y);
01649     }
01650 
01651   template<typename _Key, typename _Val, typename _KeyOfValue,
01652            typename _Compare, typename _Alloc>
01653     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01654                       _Compare, _Alloc>::iterator
01655     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01656     _M_upper_bound(_Link_type __x, _Link_type __y,
01657                    const _Key& __k)
01658     {
01659       while (__x != 0)
01660         if (_M_impl._M_key_compare(__k, _S_key(__x)))
01661           __y = __x, __x = _S_left(__x);
01662         else
01663           __x = _S_right(__x);
01664       return iterator(__y);
01665     }
01666 
01667   template<typename _Key, typename _Val, typename _KeyOfValue,
01668            typename _Compare, typename _Alloc>
01669     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01670                       _Compare, _Alloc>::const_iterator
01671     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01672     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
01673                    const _Key& __k) const
01674     {
01675       while (__x != 0)
01676         if (_M_impl._M_key_compare(__k, _S_key(__x)))
01677           __y = __x, __x = _S_left(__x);
01678         else
01679           __x = _S_right(__x);
01680       return const_iterator(__y);
01681     }
01682 
01683   template<typename _Key, typename _Val, typename _KeyOfValue,
01684            typename _Compare, typename _Alloc>
01685     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01686                            _Compare, _Alloc>::iterator,
01687          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01688                            _Compare, _Alloc>::iterator>
01689     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01690     equal_range(const _Key& __k)
01691     {
01692       _Link_type __x = _M_begin();
01693       _Link_type __y = _M_end();
01694       while (__x != 0)
01695         {
01696           if (_M_impl._M_key_compare(_S_key(__x), __k))
01697             __x = _S_right(__x);
01698           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01699             __y = __x, __x = _S_left(__x);
01700           else
01701             {
01702               _Link_type __xu(__x), __yu(__y);
01703               __y = __x, __x = _S_left(__x);
01704               __xu = _S_right(__xu);
01705               return pair<iterator,
01706                           iterator>(_M_lower_bound(__x, __y, __k),
01707                                     _M_upper_bound(__xu, __yu, __k));
01708             }
01709         }
01710       return pair<iterator, iterator>(iterator(__y),
01711                                       iterator(__y));
01712     }
01713 
01714   template<typename _Key, typename _Val, typename _KeyOfValue,
01715            typename _Compare, typename _Alloc>
01716     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01717                            _Compare, _Alloc>::const_iterator,
01718          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01719                            _Compare, _Alloc>::const_iterator>
01720     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01721     equal_range(const _Key& __k) const
01722     {
01723       _Const_Link_type __x = _M_begin();
01724       _Const_Link_type __y = _M_end();
01725       while (__x != 0)
01726         {
01727           if (_M_impl._M_key_compare(_S_key(__x), __k))
01728             __x = _S_right(__x);
01729           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01730             __y = __x, __x = _S_left(__x);
01731           else
01732             {
01733               _Const_Link_type __xu(__x), __yu(__y);
01734               __y = __x, __x = _S_left(__x);
01735               __xu = _S_right(__xu);
01736               return pair<const_iterator,
01737                           const_iterator>(_M_lower_bound(__x, __y, __k),
01738                                           _M_upper_bound(__xu, __yu, __k));
01739             }
01740         }
01741       return pair<const_iterator, const_iterator>(const_iterator(__y),
01742                                                   const_iterator(__y));
01743     }
01744 
01745   template<typename _Key, typename _Val, typename _KeyOfValue,
01746            typename _Compare, typename _Alloc>
01747     void
01748     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01749     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
01750 #if __cplusplus >= 201103L
01751     noexcept(_Alloc_traits::_S_nothrow_swap())
01752 #endif
01753     {
01754       if (_M_root() == 0)
01755         {
01756           if (__t._M_root() != 0)
01757             {
01758               _M_root() = __t._M_root();
01759               _M_leftmost() = __t._M_leftmost();
01760               _M_rightmost() = __t._M_rightmost();
01761               _M_root()->_M_parent = _M_end();
01762               _M_impl._M_node_count = __t._M_impl._M_node_count;
01763               
01764               __t._M_impl._M_reset();
01765             }
01766         }
01767       else if (__t._M_root() == 0)
01768         {
01769           __t._M_root() = _M_root();
01770           __t._M_leftmost() = _M_leftmost();
01771           __t._M_rightmost() = _M_rightmost();
01772           __t._M_root()->_M_parent = __t._M_end();
01773           __t._M_impl._M_node_count = _M_impl._M_node_count;
01774           
01775           _M_impl._M_reset();
01776         }
01777       else
01778         {
01779           std::swap(_M_root(),__t._M_root());
01780           std::swap(_M_leftmost(),__t._M_leftmost());
01781           std::swap(_M_rightmost(),__t._M_rightmost());
01782           
01783           _M_root()->_M_parent = _M_end();
01784           __t._M_root()->_M_parent = __t._M_end();
01785           std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01786         }
01787       // No need to swap header's color as it does not change.
01788       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01789 
01790       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
01791                                 __t._M_get_Node_allocator());
01792     }
01793 
01794   template<typename _Key, typename _Val, typename _KeyOfValue,
01795            typename _Compare, typename _Alloc>
01796     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01797                            _Compare, _Alloc>::_Base_ptr,
01798          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01799                            _Compare, _Alloc>::_Base_ptr>
01800     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01801     _M_get_insert_unique_pos(const key_type& __k)
01802     {
01803       typedef pair<_Base_ptr, _Base_ptr> _Res;
01804       _Link_type __x = _M_begin();
01805       _Link_type __y = _M_end();
01806       bool __comp = true;
01807       while (__x != 0)
01808         {
01809           __y = __x;
01810           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
01811           __x = __comp ? _S_left(__x) : _S_right(__x);
01812         }
01813       iterator __j = iterator(__y);
01814       if (__comp)
01815         {
01816           if (__j == begin())
01817             return _Res(__x, __y);
01818           else
01819             --__j;
01820         }
01821       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
01822         return _Res(__x, __y);
01823       return _Res(__j._M_node, 0);
01824     }
01825 
01826   template<typename _Key, typename _Val, typename _KeyOfValue,
01827            typename _Compare, typename _Alloc>
01828     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01829                            _Compare, _Alloc>::_Base_ptr,
01830          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01831                            _Compare, _Alloc>::_Base_ptr>
01832     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01833     _M_get_insert_equal_pos(const key_type& __k)
01834     {
01835       typedef pair<_Base_ptr, _Base_ptr> _Res;
01836       _Link_type __x = _M_begin();
01837       _Link_type __y = _M_end();
01838       while (__x != 0)
01839         {
01840           __y = __x;
01841           __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
01842                 _S_left(__x) : _S_right(__x);
01843         }
01844       return _Res(__x, __y);
01845     }
01846 
01847   template<typename _Key, typename _Val, typename _KeyOfValue,
01848            typename _Compare, typename _Alloc>
01849 #if __cplusplus >= 201103L
01850     template<typename _Arg>
01851 #endif
01852     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01853                            _Compare, _Alloc>::iterator, bool>
01854     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01855 #if __cplusplus >= 201103L
01856     _M_insert_unique(_Arg&& __v)
01857 #else
01858     _M_insert_unique(const _Val& __v)
01859 #endif
01860     {
01861       typedef pair<iterator, bool> _Res;
01862       pair<_Base_ptr, _Base_ptr> __res
01863         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
01864 
01865       if (__res.second)
01866         {
01867           _Alloc_node __an(*this);
01868           return _Res(_M_insert_(__res.first, __res.second,
01869                                  _GLIBCXX_FORWARD(_Arg, __v), __an),
01870                       true);
01871         }
01872 
01873       return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
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     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01882     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01883 #if __cplusplus >= 201103L
01884     _M_insert_equal(_Arg&& __v)
01885 #else
01886     _M_insert_equal(const _Val& __v)
01887 #endif
01888     {
01889       pair<_Base_ptr, _Base_ptr> __res
01890         = _M_get_insert_equal_pos(_KeyOfValue()(__v));
01891       _Alloc_node __an(*this);
01892       return _M_insert_(__res.first, __res.second,
01893                         _GLIBCXX_FORWARD(_Arg, __v), __an);
01894     }
01895 
01896   template<typename _Key, typename _Val, typename _KeyOfValue,
01897            typename _Compare, typename _Alloc>
01898     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01899                            _Compare, _Alloc>::_Base_ptr,
01900          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01901                            _Compare, _Alloc>::_Base_ptr>
01902     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01903     _M_get_insert_hint_unique_pos(const_iterator __position,
01904                                   const key_type& __k)
01905     {
01906       iterator __pos = __position._M_const_cast();
01907       typedef pair<_Base_ptr, _Base_ptr> _Res;
01908 
01909       // end()
01910       if (__pos._M_node == _M_end())
01911         {
01912           if (size() > 0
01913               && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
01914             return _Res(0, _M_rightmost());
01915           else
01916             return _M_get_insert_unique_pos(__k);
01917         }
01918       else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
01919         {
01920           // First, try before...
01921           iterator __before = __pos;
01922           if (__pos._M_node == _M_leftmost()) // begin()
01923             return _Res(_M_leftmost(), _M_leftmost());
01924           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
01925             {
01926               if (_S_right(__before._M_node) == 0)
01927                 return _Res(0, __before._M_node);
01928               else
01929                 return _Res(__pos._M_node, __pos._M_node);
01930             }
01931           else
01932             return _M_get_insert_unique_pos(__k);
01933         }
01934       else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
01935         {
01936           // ... then try after.
01937           iterator __after = __pos;
01938           if (__pos._M_node == _M_rightmost())
01939             return _Res(0, _M_rightmost());
01940           else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
01941             {
01942               if (_S_right(__pos._M_node) == 0)
01943                 return _Res(0, __pos._M_node);
01944               else
01945                 return _Res(__after._M_node, __after._M_node);
01946             }
01947           else
01948             return _M_get_insert_unique_pos(__k);
01949         }
01950       else
01951         // Equivalent keys.
01952         return _Res(__pos._M_node, 0);
01953     }
01954 
01955   template<typename _Key, typename _Val, typename _KeyOfValue,
01956            typename _Compare, typename _Alloc>
01957 #if __cplusplus >= 201103L
01958     template<typename _Arg, typename _NodeGen>
01959 #else
01960     template<typename _NodeGen>
01961 #endif
01962       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01963       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01964       _M_insert_unique_(const_iterator __position,
01965 #if __cplusplus >= 201103L
01966                         _Arg&& __v,
01967 #else
01968                         const _Val& __v,
01969 #endif
01970                         _NodeGen& __node_gen)
01971     {
01972       pair<_Base_ptr, _Base_ptr> __res
01973         = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
01974 
01975       if (__res.second)
01976         return _M_insert_(__res.first, __res.second,
01977                           _GLIBCXX_FORWARD(_Arg, __v),
01978                           __node_gen);
01979       return iterator(static_cast<_Link_type>(__res.first));
01980     }
01981 
01982   template<typename _Key, typename _Val, typename _KeyOfValue,
01983            typename _Compare, typename _Alloc>
01984     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01985                            _Compare, _Alloc>::_Base_ptr,
01986          typename _Rb_tree<_Key, _Val, _KeyOfValue,
01987                            _Compare, _Alloc>::_Base_ptr>
01988     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01989     _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
01990     {
01991       iterator __pos = __position._M_const_cast();
01992       typedef pair<_Base_ptr, _Base_ptr> _Res;
01993 
01994       // end()
01995       if (__pos._M_node == _M_end())
01996         {
01997           if (size() > 0
01998               && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
01999             return _Res(0, _M_rightmost());
02000           else
02001             return _M_get_insert_equal_pos(__k);
02002         }
02003       else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
02004         {
02005           // First, try before...
02006           iterator __before = __pos;
02007           if (__pos._M_node == _M_leftmost()) // begin()
02008             return _Res(_M_leftmost(), _M_leftmost());
02009           else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
02010             {
02011               if (_S_right(__before._M_node) == 0)
02012                 return _Res(0, __before._M_node);
02013               else
02014                 return _Res(__pos._M_node, __pos._M_node);
02015             }
02016           else
02017             return _M_get_insert_equal_pos(__k);
02018         }
02019       else
02020         {
02021           // ... then try after.  
02022           iterator __after = __pos;
02023           if (__pos._M_node == _M_rightmost())
02024             return _Res(0, _M_rightmost());
02025           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
02026             {
02027               if (_S_right(__pos._M_node) == 0)
02028                 return _Res(0, __pos._M_node);
02029               else
02030                 return _Res(__after._M_node, __after._M_node);
02031             }
02032           else
02033             return _Res(0, 0);
02034         }
02035     }
02036 
02037   template<typename _Key, typename _Val, typename _KeyOfValue,
02038            typename _Compare, typename _Alloc>
02039 #if __cplusplus >= 201103L
02040     template<typename _Arg, typename _NodeGen>
02041 #else
02042     template<typename _NodeGen>
02043 #endif
02044       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02045       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02046       _M_insert_equal_(const_iterator __position,
02047 #if __cplusplus >= 201103L
02048                        _Arg&& __v,
02049 #else
02050                        const _Val& __v,
02051 #endif
02052                        _NodeGen& __node_gen)
02053       {
02054         pair<_Base_ptr, _Base_ptr> __res
02055           = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
02056 
02057         if (__res.second)
02058           return _M_insert_(__res.first, __res.second,
02059                             _GLIBCXX_FORWARD(_Arg, __v),
02060                             __node_gen);
02061 
02062         return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
02063       }
02064 
02065 #if __cplusplus >= 201103L
02066   template<typename _Key, typename _Val, typename _KeyOfValue,
02067            typename _Compare, typename _Alloc>
02068     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02069     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02070     _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
02071     {
02072       bool __insert_left = (__x != 0 || __p == _M_end()
02073                             || _M_impl._M_key_compare(_S_key(__z),
02074                                                       _S_key(__p)));
02075 
02076       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
02077                                     this->_M_impl._M_header);
02078       ++_M_impl._M_node_count;
02079       return iterator(__z);
02080     }
02081 
02082   template<typename _Key, typename _Val, typename _KeyOfValue,
02083            typename _Compare, typename _Alloc>
02084     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02085     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02086     _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
02087     {
02088       bool __insert_left = (__p == _M_end()
02089                             || !_M_impl._M_key_compare(_S_key(__p),
02090                                                        _S_key(__z)));
02091 
02092       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
02093                                     this->_M_impl._M_header);
02094       ++_M_impl._M_node_count;
02095       return iterator(__z);
02096     }
02097 
02098   template<typename _Key, typename _Val, typename _KeyOfValue,
02099            typename _Compare, typename _Alloc>
02100     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02101     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02102     _M_insert_equal_lower_node(_Link_type __z)
02103     {
02104       _Link_type __x = _M_begin();
02105       _Link_type __y = _M_end();
02106       while (__x != 0)
02107         {
02108           __y = __x;
02109           __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
02110                 _S_left(__x) : _S_right(__x);
02111         }
02112       return _M_insert_lower_node(__y, __z);
02113     }
02114 
02115   template<typename _Key, typename _Val, typename _KeyOfValue,
02116            typename _Compare, typename _Alloc>
02117     template<typename... _Args>
02118       pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
02119                              _Compare, _Alloc>::iterator, bool>
02120       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02121       _M_emplace_unique(_Args&&... __args)
02122       {
02123         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02124 
02125         __try
02126           {
02127             typedef pair<iterator, bool> _Res;
02128             auto __res = _M_get_insert_unique_pos(_S_key(__z));
02129             if (__res.second)
02130               return _Res(_M_insert_node(__res.first, __res.second, __z), true);
02131         
02132             _M_drop_node(__z);
02133             return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
02134           }
02135         __catch(...)
02136           {
02137             _M_drop_node(__z);
02138             __throw_exception_again;
02139           }
02140       }
02141 
02142   template<typename _Key, typename _Val, typename _KeyOfValue,
02143            typename _Compare, typename _Alloc>
02144     template<typename... _Args>
02145       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02146       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02147       _M_emplace_equal(_Args&&... __args)
02148       {
02149         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02150 
02151         __try
02152           {
02153             auto __res = _M_get_insert_equal_pos(_S_key(__z));
02154             return _M_insert_node(__res.first, __res.second, __z);
02155           }
02156         __catch(...)
02157           {
02158             _M_drop_node(__z);
02159             __throw_exception_again;
02160           }
02161       }
02162 
02163   template<typename _Key, typename _Val, typename _KeyOfValue,
02164            typename _Compare, typename _Alloc>
02165     template<typename... _Args>
02166       typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
02167       _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02168       _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
02169       {
02170         _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
02171 
02172         __try
02173           {
02174             auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
02175 
02176             if (__res.second)
02177               return _M_insert_node(__res.first, __res.second, __z);
02178 
02179             _M_drop_node(__z);
02180             return iterator(static_cast<_Link_type>(__res.first));
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_equal(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_equal_pos(__pos, _S_key(__z));
02201 
02202             if (__res.second)
02203               return _M_insert_node(__res.first, __res.second, __z);
02204 
02205             return _M_insert_equal_lower_node(__z);
02206           }
02207         __catch(...)
02208           {
02209             _M_drop_node(__z);
02210             __throw_exception_again;
02211           }
02212       }
02213 #endif
02214 
02215   template<typename _Key, typename _Val, typename _KoV,
02216            typename _Cmp, typename _Alloc>
02217     template<class _II>
02218       void
02219       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
02220       _M_insert_unique(_II __first, _II __last)
02221       {
02222         _Alloc_node __an(*this);
02223         for (; __first != __last; ++__first)
02224           _M_insert_unique_(end(), *__first, __an);
02225       }
02226 
02227   template<typename _Key, typename _Val, typename _KoV,
02228            typename _Cmp, typename _Alloc>
02229     template<class _II>
02230       void
02231       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
02232       _M_insert_equal(_II __first, _II __last)
02233       {
02234         _Alloc_node __an(*this);
02235         for (; __first != __last; ++__first)
02236           _M_insert_equal_(end(), *__first, __an);
02237       }
02238 
02239   template<typename _Key, typename _Val, typename _KeyOfValue,
02240            typename _Compare, typename _Alloc>
02241     void
02242     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02243     _M_erase_aux(const_iterator __position)
02244     {
02245       _Link_type __y =
02246         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
02247                                 (const_cast<_Base_ptr>(__position._M_node),
02248                                  this->_M_impl._M_header));
02249       _M_drop_node(__y);
02250       --_M_impl._M_node_count;
02251     }
02252 
02253   template<typename _Key, typename _Val, typename _KeyOfValue,
02254            typename _Compare, typename _Alloc>
02255     void
02256     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02257     _M_erase_aux(const_iterator __first, const_iterator __last)
02258     {
02259       if (__first == begin() && __last == end())
02260         clear();
02261       else
02262         while (__first != __last)
02263           erase(__first++);
02264     }
02265 
02266   template<typename _Key, typename _Val, typename _KeyOfValue,
02267            typename _Compare, typename _Alloc>
02268     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
02269     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02270     erase(const _Key& __x)
02271     {
02272       pair<iterator, iterator> __p = equal_range(__x);
02273       const size_type __old_size = size();
02274       erase(__p.first, __p.second);
02275       return __old_size - size();
02276     }
02277 
02278   template<typename _Key, typename _Val, typename _KeyOfValue,
02279            typename _Compare, typename _Alloc>
02280     void
02281     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02282     erase(const _Key* __first, const _Key* __last)
02283     {
02284       while (__first != __last)
02285         erase(*__first++);
02286     }
02287 
02288   template<typename _Key, typename _Val, typename _KeyOfValue,
02289            typename _Compare, typename _Alloc>
02290     typename _Rb_tree<_Key, _Val, _KeyOfValue,
02291                       _Compare, _Alloc>::iterator
02292     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02293     find(const _Key& __k)
02294     {
02295       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
02296       return (__j == end()
02297               || _M_impl._M_key_compare(__k,
02298                                         _S_key(__j._M_node))) ? end() : __j;
02299     }
02300 
02301   template<typename _Key, typename _Val, typename _KeyOfValue,
02302            typename _Compare, typename _Alloc>
02303     typename _Rb_tree<_Key, _Val, _KeyOfValue,
02304                       _Compare, _Alloc>::const_iterator
02305     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02306     find(const _Key& __k) const
02307     {
02308       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
02309       return (__j == end()
02310               || _M_impl._M_key_compare(__k, 
02311                                         _S_key(__j._M_node))) ? end() : __j;
02312     }
02313 
02314   template<typename _Key, typename _Val, typename _KeyOfValue,
02315            typename _Compare, typename _Alloc>
02316     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
02317     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
02318     count(const _Key& __k) const
02319     {
02320       pair<const_iterator, const_iterator> __p = equal_range(__k);
02321       const size_type __n = std::distance(__p.first, __p.second);
02322       return __n;
02323     }
02324 
02325   _GLIBCXX_PURE unsigned int
02326   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
02327                        const _Rb_tree_node_base* __root) throw ();
02328 
02329   template<typename _Key, typename _Val, typename _KeyOfValue,
02330            typename _Compare, typename _Alloc>
02331     bool
02332     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
02333     {
02334       if (_M_impl._M_node_count == 0 || begin() == end())
02335         return _M_impl._M_node_count == 0 && begin() == end()
02336                && this->_M_impl._M_header._M_left == _M_end()
02337                && this->_M_impl._M_header._M_right == _M_end();
02338 
02339       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
02340       for (const_iterator __it = begin(); __it != end(); ++__it)
02341         {
02342           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
02343           _Const_Link_type __L = _S_left(__x);
02344           _Const_Link_type __R = _S_right(__x);
02345 
02346           if (__x->_M_color == _S_red)
02347             if ((__L && __L->_M_color == _S_red)
02348                 || (__R && __R->_M_color == _S_red))
02349               return false;
02350 
02351           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
02352             return false;
02353           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
02354             return false;
02355 
02356           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
02357             return false;
02358         }
02359 
02360       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
02361         return false;
02362       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
02363         return false;
02364       return true;
02365     }
02366 
02367 _GLIBCXX_END_NAMESPACE_VERSION
02368 } // namespace
02369 
02370 #endif