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