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