stl_tree.h

Go to the documentation of this file.
00001 // RB tree implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1996,1997
00029  * Silicon Graphics Computer Systems, Inc.
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Silicon Graphics makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1994
00041  * Hewlett-Packard Company
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Hewlett-Packard Company makes no
00048  * representations about the suitability of this software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  *
00051  *
00052  */
00053 
00054 /** @file stl_tree.h
00055  *  This is an internal header file, included by other library headers.
00056  *  You should not attempt to use it directly.
00057  */
00058 
00059 #ifndef _STL_TREE_H
00060 #define _STL_TREE_H 1
00061 
00062 #include <bits/stl_algobase.h>
00063 #include <bits/allocator.h>
00064 #include <bits/stl_function.h>
00065 #include <bits/cpp_type_traits.h>
00066 
00067 _GLIBCXX_BEGIN_NAMESPACE(std)
00068 
00069   // Red-black tree class, designed for use in implementing STL
00070   // associative containers (set, multiset, map, and multimap). The
00071   // insertion and deletion algorithms are based on those in Cormen,
00072   // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
00073   // 1990), except that
00074   //
00075   // (1) the header cell is maintained with links not only to the root
00076   // but also to the leftmost node of the tree, to enable constant
00077   // time begin(), and to the rightmost node of the tree, to enable
00078   // linear time performance when used with the generic set algorithms
00079   // (set_union, etc.)
00080   // 
00081   // (2) when a node being deleted has two children its successor node
00082   // is relinked into its place, rather than copied, so that the only
00083   // iterators invalidated are those referring to the deleted node.
00084 
00085   enum _Rb_tree_color { _S_red = false, _S_black = true };
00086 
00087   struct _Rb_tree_node_base
00088   {
00089     typedef _Rb_tree_node_base* _Base_ptr;
00090     typedef const _Rb_tree_node_base* _Const_Base_ptr;
00091 
00092     _Rb_tree_color  _M_color;
00093     _Base_ptr       _M_parent;
00094     _Base_ptr       _M_left;
00095     _Base_ptr       _M_right;
00096 
00097     static _Base_ptr
00098     _S_minimum(_Base_ptr __x)
00099     {
00100       while (__x->_M_left != 0) __x = __x->_M_left;
00101       return __x;
00102     }
00103 
00104     static _Const_Base_ptr
00105     _S_minimum(_Const_Base_ptr __x)
00106     {
00107       while (__x->_M_left != 0) __x = __x->_M_left;
00108       return __x;
00109     }
00110 
00111     static _Base_ptr
00112     _S_maximum(_Base_ptr __x)
00113     {
00114       while (__x->_M_right != 0) __x = __x->_M_right;
00115       return __x;
00116     }
00117 
00118     static _Const_Base_ptr
00119     _S_maximum(_Const_Base_ptr __x)
00120     {
00121       while (__x->_M_right != 0) __x = __x->_M_right;
00122       return __x;
00123     }
00124   };
00125 
00126   template<typename _Val>
00127     struct _Rb_tree_node : public _Rb_tree_node_base
00128     {
00129       typedef _Rb_tree_node<_Val>* _Link_type;
00130       _Val _M_value_field;
00131 
00132 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00133       template<typename... _Args>
00134         _Rb_tree_node(_Args&&... __args)
00135     : _Rb_tree_node_base(),
00136       _M_value_field(std::forward<_Args>(__args)...) { }
00137 #endif
00138     };
00139 
00140   _Rb_tree_node_base*
00141   _Rb_tree_increment(_Rb_tree_node_base* __x);
00142 
00143   const _Rb_tree_node_base*
00144   _Rb_tree_increment(const _Rb_tree_node_base* __x);
00145 
00146   _Rb_tree_node_base*
00147   _Rb_tree_decrement(_Rb_tree_node_base* __x);
00148 
00149   const _Rb_tree_node_base*
00150   _Rb_tree_decrement(const _Rb_tree_node_base* __x);
00151 
00152   template<typename _Tp>
00153     struct _Rb_tree_iterator
00154     {
00155       typedef _Tp  value_type;
00156       typedef _Tp& reference;
00157       typedef _Tp* pointer;
00158 
00159       typedef bidirectional_iterator_tag iterator_category;
00160       typedef ptrdiff_t                  difference_type;
00161 
00162       typedef _Rb_tree_iterator<_Tp>        _Self;
00163       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
00164       typedef _Rb_tree_node<_Tp>*           _Link_type;
00165 
00166       _Rb_tree_iterator()
00167       : _M_node() { }
00168 
00169       explicit
00170       _Rb_tree_iterator(_Link_type __x)
00171       : _M_node(__x) { }
00172 
00173       reference
00174       operator*() const
00175       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00176 
00177       pointer
00178       operator->() const
00179       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00180 
00181       _Self&
00182       operator++()
00183       {
00184     _M_node = _Rb_tree_increment(_M_node);
00185     return *this;
00186       }
00187 
00188       _Self
00189       operator++(int)
00190       {
00191     _Self __tmp = *this;
00192     _M_node = _Rb_tree_increment(_M_node);
00193     return __tmp;
00194       }
00195 
00196       _Self&
00197       operator--()
00198       {
00199     _M_node = _Rb_tree_decrement(_M_node);
00200     return *this;
00201       }
00202 
00203       _Self
00204       operator--(int)
00205       {
00206     _Self __tmp = *this;
00207     _M_node = _Rb_tree_decrement(_M_node);
00208     return __tmp;
00209       }
00210 
00211       bool
00212       operator==(const _Self& __x) const
00213       { return _M_node == __x._M_node; }
00214 
00215       bool
00216       operator!=(const _Self& __x) const
00217       { return _M_node != __x._M_node; }
00218 
00219       _Base_ptr _M_node;
00220   };
00221 
00222   template<typename _Tp>
00223     struct _Rb_tree_const_iterator
00224     {
00225       typedef _Tp        value_type;
00226       typedef const _Tp& reference;
00227       typedef const _Tp* pointer;
00228 
00229       typedef _Rb_tree_iterator<_Tp> iterator;
00230 
00231       typedef bidirectional_iterator_tag iterator_category;
00232       typedef ptrdiff_t                  difference_type;
00233 
00234       typedef _Rb_tree_const_iterator<_Tp>        _Self;
00235       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
00236       typedef const _Rb_tree_node<_Tp>*           _Link_type;
00237 
00238       _Rb_tree_const_iterator()
00239       : _M_node() { }
00240 
00241       explicit
00242       _Rb_tree_const_iterator(_Link_type __x)
00243       : _M_node(__x) { }
00244 
00245       _Rb_tree_const_iterator(const iterator& __it)
00246       : _M_node(__it._M_node) { }
00247 
00248       reference
00249       operator*() const
00250       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
00251 
00252       pointer
00253       operator->() const
00254       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
00255 
00256       _Self&
00257       operator++()
00258       {
00259     _M_node = _Rb_tree_increment(_M_node);
00260     return *this;
00261       }
00262 
00263       _Self
00264       operator++(int)
00265       {
00266     _Self __tmp = *this;
00267     _M_node = _Rb_tree_increment(_M_node);
00268     return __tmp;
00269       }
00270 
00271       _Self&
00272       operator--()
00273       {
00274     _M_node = _Rb_tree_decrement(_M_node);
00275     return *this;
00276       }
00277 
00278       _Self
00279       operator--(int)
00280       {
00281     _Self __tmp = *this;
00282     _M_node = _Rb_tree_decrement(_M_node);
00283     return __tmp;
00284       }
00285 
00286       bool
00287       operator==(const _Self& __x) const
00288       { return _M_node == __x._M_node; }
00289 
00290       bool
00291       operator!=(const _Self& __x) const
00292       { return _M_node != __x._M_node; }
00293 
00294       _Base_ptr _M_node;
00295     };
00296 
00297   template<typename _Val>
00298     inline bool
00299     operator==(const _Rb_tree_iterator<_Val>& __x,
00300                const _Rb_tree_const_iterator<_Val>& __y)
00301     { return __x._M_node == __y._M_node; }
00302 
00303   template<typename _Val>
00304     inline bool
00305     operator!=(const _Rb_tree_iterator<_Val>& __x,
00306                const _Rb_tree_const_iterator<_Val>& __y)
00307     { return __x._M_node != __y._M_node; }
00308 
00309   void
00310   _Rb_tree_insert_and_rebalance(const bool __insert_left,
00311                                 _Rb_tree_node_base* __x,
00312                                 _Rb_tree_node_base* __p,
00313                                 _Rb_tree_node_base& __header);
00314 
00315   _Rb_tree_node_base*
00316   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
00317                    _Rb_tree_node_base& __header);
00318 
00319 
00320   template<typename _Key, typename _Val, typename _KeyOfValue,
00321            typename _Compare, typename _Alloc = allocator<_Val> >
00322     class _Rb_tree
00323     {
00324       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
00325               _Node_allocator;
00326 
00327     protected:
00328       typedef _Rb_tree_node_base* _Base_ptr;
00329       typedef const _Rb_tree_node_base* _Const_Base_ptr;
00330 
00331     public:
00332       typedef _Key key_type;
00333       typedef _Val value_type;
00334       typedef value_type* pointer;
00335       typedef const value_type* const_pointer;
00336       typedef value_type& reference;
00337       typedef const value_type& const_reference;
00338       typedef _Rb_tree_node<_Val>* _Link_type;
00339       typedef const _Rb_tree_node<_Val>* _Const_Link_type;
00340       typedef size_t size_type;
00341       typedef ptrdiff_t difference_type;
00342       typedef _Alloc allocator_type;
00343 
00344       _Node_allocator&
00345       _M_get_Node_allocator()
00346       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
00347       
00348       const _Node_allocator&
00349       _M_get_Node_allocator() const
00350       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
00351 
00352       allocator_type
00353       get_allocator() const
00354       { return allocator_type(_M_get_Node_allocator()); }
00355 
00356     protected:
00357       _Link_type
00358       _M_get_node()
00359       { return _M_impl._Node_allocator::allocate(1); }
00360 
00361       void
00362       _M_put_node(_Link_type __p)
00363       { _M_impl._Node_allocator::deallocate(__p, 1); }
00364 
00365 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00366       _Link_type
00367       _M_create_node(const value_type& __x)
00368       {
00369     _Link_type __tmp = _M_get_node();
00370     __try
00371       { get_allocator().construct(&__tmp->_M_value_field, __x); }
00372     __catch(...)
00373       {
00374         _M_put_node(__tmp);
00375         __throw_exception_again;
00376       }
00377     return __tmp;
00378       }
00379 
00380       void
00381       _M_destroy_node(_Link_type __p)
00382       {
00383     get_allocator().destroy(&__p->_M_value_field);
00384     _M_put_node(__p);
00385       }
00386 #else
00387       template<typename... _Args>
00388         _Link_type
00389         _M_create_node(_Args&&... __args)
00390     {
00391       _Link_type __tmp = _M_get_node();
00392       __try
00393         {
00394           _M_get_Node_allocator().construct(__tmp,
00395                          std::forward<_Args>(__args)...);
00396         }
00397       __catch(...)
00398         {
00399           _M_put_node(__tmp);
00400           __throw_exception_again;
00401         }
00402       return __tmp;
00403     }
00404 
00405       void
00406       _M_destroy_node(_Link_type __p)
00407       {
00408     _M_get_Node_allocator().destroy(__p);
00409     _M_put_node(__p);
00410       }
00411 #endif
00412 
00413       _Link_type
00414       _M_clone_node(_Const_Link_type __x)
00415       {
00416     _Link_type __tmp = _M_create_node(__x->_M_value_field);
00417     __tmp->_M_color = __x->_M_color;
00418     __tmp->_M_left = 0;
00419     __tmp->_M_right = 0;
00420     return __tmp;
00421       }
00422 
00423     protected:
00424       template<typename _Key_compare, 
00425            bool _Is_pod_comparator = __is_pod(_Key_compare)>
00426         struct _Rb_tree_impl : public _Node_allocator
00427         {
00428       _Key_compare      _M_key_compare;
00429       _Rb_tree_node_base    _M_header;
00430       size_type         _M_node_count; // Keeps track of size of tree.
00431 
00432       _Rb_tree_impl()
00433       : _Node_allocator(), _M_key_compare(), _M_header(),
00434         _M_node_count(0)
00435       { _M_initialize(); }
00436 
00437       _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
00438       : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
00439         _M_node_count(0)
00440       { _M_initialize(); }
00441 
00442     private:
00443       void
00444       _M_initialize()
00445       {
00446         this->_M_header._M_color = _S_red;
00447         this->_M_header._M_parent = 0;
00448         this->_M_header._M_left = &this->_M_header;
00449         this->_M_header._M_right = &this->_M_header;
00450       }     
00451     };
00452 
00453       _Rb_tree_impl<_Compare> _M_impl;
00454 
00455     protected:
00456       _Base_ptr&
00457       _M_root()
00458       { return this->_M_impl._M_header._M_parent; }
00459 
00460       _Const_Base_ptr
00461       _M_root() const
00462       { return this->_M_impl._M_header._M_parent; }
00463 
00464       _Base_ptr&
00465       _M_leftmost()
00466       { return this->_M_impl._M_header._M_left; }
00467 
00468       _Const_Base_ptr
00469       _M_leftmost() const
00470       { return this->_M_impl._M_header._M_left; }
00471 
00472       _Base_ptr&
00473       _M_rightmost()
00474       { return this->_M_impl._M_header._M_right; }
00475 
00476       _Const_Base_ptr
00477       _M_rightmost() const
00478       { return this->_M_impl._M_header._M_right; }
00479 
00480       _Link_type
00481       _M_begin()
00482       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
00483 
00484       _Const_Link_type
00485       _M_begin() const
00486       {
00487     return static_cast<_Const_Link_type>
00488       (this->_M_impl._M_header._M_parent);
00489       }
00490 
00491       _Link_type
00492       _M_end()
00493       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
00494 
00495       _Const_Link_type
00496       _M_end() const
00497       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
00498 
00499       static const_reference
00500       _S_value(_Const_Link_type __x)
00501       { return __x->_M_value_field; }
00502 
00503       static const _Key&
00504       _S_key(_Const_Link_type __x)
00505       { return _KeyOfValue()(_S_value(__x)); }
00506 
00507       static _Link_type
00508       _S_left(_Base_ptr __x)
00509       { return static_cast<_Link_type>(__x->_M_left); }
00510 
00511       static _Const_Link_type
00512       _S_left(_Const_Base_ptr __x)
00513       { return static_cast<_Const_Link_type>(__x->_M_left); }
00514 
00515       static _Link_type
00516       _S_right(_Base_ptr __x)
00517       { return static_cast<_Link_type>(__x->_M_right); }
00518 
00519       static _Const_Link_type
00520       _S_right(_Const_Base_ptr __x)
00521       { return static_cast<_Const_Link_type>(__x->_M_right); }
00522 
00523       static const_reference
00524       _S_value(_Const_Base_ptr __x)
00525       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
00526 
00527       static const _Key&
00528       _S_key(_Const_Base_ptr __x)
00529       { return _KeyOfValue()(_S_value(__x)); }
00530 
00531       static _Base_ptr
00532       _S_minimum(_Base_ptr __x)
00533       { return _Rb_tree_node_base::_S_minimum(__x); }
00534 
00535       static _Const_Base_ptr
00536       _S_minimum(_Const_Base_ptr __x)
00537       { return _Rb_tree_node_base::_S_minimum(__x); }
00538 
00539       static _Base_ptr
00540       _S_maximum(_Base_ptr __x)
00541       { return _Rb_tree_node_base::_S_maximum(__x); }
00542 
00543       static _Const_Base_ptr
00544       _S_maximum(_Const_Base_ptr __x)
00545       { return _Rb_tree_node_base::_S_maximum(__x); }
00546 
00547     public:
00548       typedef _Rb_tree_iterator<value_type>       iterator;
00549       typedef _Rb_tree_const_iterator<value_type> const_iterator;
00550 
00551       typedef std::reverse_iterator<iterator>       reverse_iterator;
00552       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00553 
00554     private:
00555       iterator
00556       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
00557          const value_type& __v);
00558 
00559       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00560       // 233. Insertion hints in associative containers.
00561       iterator
00562       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
00563 
00564       iterator
00565       _M_insert_equal_lower(const value_type& __x);
00566 
00567       _Link_type
00568       _M_copy(_Const_Link_type __x, _Link_type __p);
00569 
00570       void
00571       _M_erase(_Link_type __x);
00572 
00573       iterator
00574       _M_lower_bound(_Link_type __x, _Link_type __y,
00575              const _Key& __k);
00576 
00577       const_iterator
00578       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
00579              const _Key& __k) const;
00580 
00581       iterator
00582       _M_upper_bound(_Link_type __x, _Link_type __y,
00583              const _Key& __k);
00584 
00585       const_iterator
00586       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
00587              const _Key& __k) const;
00588 
00589     public:
00590       // allocation/deallocation
00591       _Rb_tree() { }
00592 
00593       _Rb_tree(const _Compare& __comp,
00594            const allocator_type& __a = allocator_type())
00595       : _M_impl(__comp, __a) { }
00596 
00597       _Rb_tree(const _Rb_tree& __x)
00598       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
00599       {
00600     if (__x._M_root() != 0)
00601       {
00602         _M_root() = _M_copy(__x._M_begin(), _M_end());
00603         _M_leftmost() = _S_minimum(_M_root());
00604         _M_rightmost() = _S_maximum(_M_root());
00605         _M_impl._M_node_count = __x._M_impl._M_node_count;
00606       }
00607       }
00608 
00609 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00610       _Rb_tree(_Rb_tree&& __x);
00611 #endif
00612 
00613       ~_Rb_tree()
00614       { _M_erase(_M_begin()); }
00615 
00616       _Rb_tree&
00617       operator=(const _Rb_tree& __x);
00618 
00619       // Accessors.
00620       _Compare
00621       key_comp() const
00622       { return _M_impl._M_key_compare; }
00623 
00624       iterator
00625       begin()
00626       { 
00627     return iterator(static_cast<_Link_type>
00628             (this->_M_impl._M_header._M_left));
00629       }
00630 
00631       const_iterator
00632       begin() const
00633       { 
00634     return const_iterator(static_cast<_Const_Link_type>
00635                   (this->_M_impl._M_header._M_left));
00636       }
00637 
00638       iterator
00639       end()
00640       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
00641 
00642       const_iterator
00643       end() const
00644       { 
00645     return const_iterator(static_cast<_Const_Link_type>
00646                   (&this->_M_impl._M_header));
00647       }
00648 
00649       reverse_iterator
00650       rbegin()
00651       { return reverse_iterator(end()); }
00652 
00653       const_reverse_iterator
00654       rbegin() const
00655       { return const_reverse_iterator(end()); }
00656 
00657       reverse_iterator
00658       rend()
00659       { return reverse_iterator(begin()); }
00660 
00661       const_reverse_iterator
00662       rend() const
00663       { return const_reverse_iterator(begin()); }
00664 
00665       bool
00666       empty() const
00667       { return _M_impl._M_node_count == 0; }
00668 
00669       size_type
00670       size() const
00671       { return _M_impl._M_node_count; }
00672 
00673       size_type
00674       max_size() const
00675       { return _M_get_Node_allocator().max_size(); }
00676 
00677       void
00678 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00679       swap(_Rb_tree&& __t);
00680 #else
00681       swap(_Rb_tree& __t);      
00682 #endif
00683 
00684       // Insert/erase.
00685       pair<iterator, bool>
00686       _M_insert_unique(const value_type& __x);
00687 
00688       iterator
00689       _M_insert_equal(const value_type& __x);
00690 
00691       iterator
00692       _M_insert_unique_(const_iterator __position, const value_type& __x);
00693 
00694       iterator
00695       _M_insert_equal_(const_iterator __position, const value_type& __x);
00696 
00697       template<typename _InputIterator>
00698         void
00699         _M_insert_unique(_InputIterator __first, _InputIterator __last);
00700 
00701       template<typename _InputIterator>
00702         void
00703         _M_insert_equal(_InputIterator __first, _InputIterator __last);
00704 
00705       void
00706       erase(iterator __position);
00707 
00708       void
00709       erase(const_iterator __position);
00710 
00711       size_type
00712       erase(const key_type& __x);
00713 
00714       void
00715       erase(iterator __first, iterator __last);
00716 
00717       void
00718       erase(const_iterator __first, const_iterator __last);
00719 
00720       void
00721       erase(const key_type* __first, const key_type* __last);
00722 
00723       void
00724       clear()
00725       {
00726         _M_erase(_M_begin());
00727         _M_leftmost() = _M_end();
00728         _M_root() = 0;
00729         _M_rightmost() = _M_end();
00730         _M_impl._M_node_count = 0;
00731       }
00732 
00733       // Set operations.
00734       iterator
00735       find(const key_type& __k);
00736 
00737       const_iterator
00738       find(const key_type& __k) const;
00739 
00740       size_type
00741       count(const key_type& __k) const;
00742 
00743       iterator
00744       lower_bound(const key_type& __k)
00745       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00746 
00747       const_iterator
00748       lower_bound(const key_type& __k) const
00749       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
00750 
00751       iterator
00752       upper_bound(const key_type& __k)
00753       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00754 
00755       const_iterator
00756       upper_bound(const key_type& __k) const
00757       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
00758 
00759       pair<iterator, iterator>
00760       equal_range(const key_type& __k);
00761 
00762       pair<const_iterator, const_iterator>
00763       equal_range(const key_type& __k) const;
00764 
00765       // Debugging.
00766       bool
00767       __rb_verify() const;
00768     };
00769 
00770   template<typename _Key, typename _Val, typename _KeyOfValue,
00771            typename _Compare, typename _Alloc>
00772     inline bool
00773     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00774            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00775     {
00776       return __x.size() == __y.size()
00777          && std::equal(__x.begin(), __x.end(), __y.begin());
00778     }
00779 
00780   template<typename _Key, typename _Val, typename _KeyOfValue,
00781            typename _Compare, typename _Alloc>
00782     inline bool
00783     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00784           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00785     {
00786       return std::lexicographical_compare(__x.begin(), __x.end(), 
00787                       __y.begin(), __y.end());
00788     }
00789 
00790   template<typename _Key, typename _Val, typename _KeyOfValue,
00791            typename _Compare, typename _Alloc>
00792     inline bool
00793     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00794            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00795     { return !(__x == __y); }
00796 
00797   template<typename _Key, typename _Val, typename _KeyOfValue,
00798            typename _Compare, typename _Alloc>
00799     inline bool
00800     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00801           const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00802     { return __y < __x; }
00803 
00804   template<typename _Key, typename _Val, typename _KeyOfValue,
00805            typename _Compare, typename _Alloc>
00806     inline bool
00807     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00808            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00809     { return !(__y < __x); }
00810 
00811   template<typename _Key, typename _Val, typename _KeyOfValue,
00812            typename _Compare, typename _Alloc>
00813     inline bool
00814     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00815            const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00816     { return !(__x < __y); }
00817 
00818   template<typename _Key, typename _Val, typename _KeyOfValue,
00819            typename _Compare, typename _Alloc>
00820     inline void
00821     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
00822      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
00823     { __x.swap(__y); }
00824 
00825 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00826   template<typename _Key, typename _Val, typename _KeyOfValue,
00827            typename _Compare, typename _Alloc>
00828     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00829     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
00830     : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
00831     {
00832       if (__x._M_root() != 0)
00833     {
00834       _M_root() = __x._M_root();
00835       _M_leftmost() = __x._M_leftmost();
00836       _M_rightmost() = __x._M_rightmost();
00837       _M_root()->_M_parent = _M_end();
00838 
00839       __x._M_root() = 0;
00840       __x._M_leftmost() = __x._M_end();
00841       __x._M_rightmost() = __x._M_end();
00842 
00843       this->_M_impl._M_node_count = __x._M_impl._M_node_count;
00844       __x._M_impl._M_node_count = 0;
00845     }
00846     }
00847 #endif
00848 
00849   template<typename _Key, typename _Val, typename _KeyOfValue,
00850            typename _Compare, typename _Alloc>
00851     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
00852     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00853     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
00854     {
00855       if (this != &__x)
00856     {
00857       // Note that _Key may be a constant type.
00858       clear();
00859       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
00860       if (__x._M_root() != 0)
00861         {
00862           _M_root() = _M_copy(__x._M_begin(), _M_end());
00863           _M_leftmost() = _S_minimum(_M_root());
00864           _M_rightmost() = _S_maximum(_M_root());
00865           _M_impl._M_node_count = __x._M_impl._M_node_count;
00866         }
00867     }
00868       return *this;
00869     }
00870 
00871   template<typename _Key, typename _Val, typename _KeyOfValue,
00872            typename _Compare, typename _Alloc>
00873     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00874     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00875     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
00876     {
00877       bool __insert_left = (__x != 0 || __p == _M_end()
00878                 || _M_impl._M_key_compare(_KeyOfValue()(__v), 
00879                               _S_key(__p)));
00880 
00881       _Link_type __z = _M_create_node(__v);
00882 
00883       _Rb_tree_insert_and_rebalance(__insert_left, __z,
00884                     const_cast<_Base_ptr>(__p),  
00885                     this->_M_impl._M_header);
00886       ++_M_impl._M_node_count;
00887       return iterator(__z);
00888     }
00889 
00890   template<typename _Key, typename _Val, typename _KeyOfValue,
00891            typename _Compare, typename _Alloc>
00892     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00893     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00894     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
00895     {
00896       bool __insert_left = (__x != 0 || __p == _M_end()
00897                 || !_M_impl._M_key_compare(_S_key(__p),
00898                                _KeyOfValue()(__v)));
00899 
00900       _Link_type __z = _M_create_node(__v);
00901 
00902       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
00903                     this->_M_impl._M_header);
00904       ++_M_impl._M_node_count;
00905       return iterator(__z);
00906     }
00907 
00908   template<typename _Key, typename _Val, typename _KeyOfValue,
00909            typename _Compare, typename _Alloc>
00910     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
00911     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00912     _M_insert_equal_lower(const _Val& __v)
00913     {
00914       _Link_type __x = _M_begin();
00915       _Link_type __y = _M_end();
00916       while (__x != 0)
00917     {
00918       __y = __x;
00919       __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
00920             _S_left(__x) : _S_right(__x);
00921     }
00922       return _M_insert_lower(__x, __y, __v);
00923     }
00924 
00925   template<typename _Key, typename _Val, typename _KoV,
00926            typename _Compare, typename _Alloc>
00927     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
00928     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
00929     _M_copy(_Const_Link_type __x, _Link_type __p)
00930     {
00931       // Structural copy.  __x and __p must be non-null.
00932       _Link_type __top = _M_clone_node(__x);
00933       __top->_M_parent = __p;
00934 
00935       __try
00936     {
00937       if (__x->_M_right)
00938         __top->_M_right = _M_copy(_S_right(__x), __top);
00939       __p = __top;
00940       __x = _S_left(__x);
00941 
00942       while (__x != 0)
00943         {
00944           _Link_type __y = _M_clone_node(__x);
00945           __p->_M_left = __y;
00946           __y->_M_parent = __p;
00947           if (__x->_M_right)
00948         __y->_M_right = _M_copy(_S_right(__x), __y);
00949           __p = __y;
00950           __x = _S_left(__x);
00951         }
00952     }
00953       __catch(...)
00954     {
00955       _M_erase(__top);
00956       __throw_exception_again;
00957     }
00958       return __top;
00959     }
00960 
00961   template<typename _Key, typename _Val, typename _KeyOfValue,
00962            typename _Compare, typename _Alloc>
00963     void
00964     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00965     _M_erase(_Link_type __x)
00966     {
00967       // Erase without rebalancing.
00968       while (__x != 0)
00969     {
00970       _M_erase(_S_right(__x));
00971       _Link_type __y = _S_left(__x);
00972       _M_destroy_node(__x);
00973       __x = __y;
00974     }
00975     }
00976 
00977   template<typename _Key, typename _Val, typename _KeyOfValue,
00978            typename _Compare, typename _Alloc>
00979     typename _Rb_tree<_Key, _Val, _KeyOfValue,
00980               _Compare, _Alloc>::iterator
00981     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00982     _M_lower_bound(_Link_type __x, _Link_type __y,
00983            const _Key& __k)
00984     {
00985       while (__x != 0)
00986     if (!_M_impl._M_key_compare(_S_key(__x), __k))
00987       __y = __x, __x = _S_left(__x);
00988     else
00989       __x = _S_right(__x);
00990       return iterator(__y);
00991     }
00992 
00993   template<typename _Key, typename _Val, typename _KeyOfValue,
00994            typename _Compare, typename _Alloc>
00995     typename _Rb_tree<_Key, _Val, _KeyOfValue,
00996               _Compare, _Alloc>::const_iterator
00997     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
00998     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
00999            const _Key& __k) const
01000     {
01001       while (__x != 0)
01002     if (!_M_impl._M_key_compare(_S_key(__x), __k))
01003       __y = __x, __x = _S_left(__x);
01004     else
01005       __x = _S_right(__x);
01006       return const_iterator(__y);
01007     }
01008 
01009   template<typename _Key, typename _Val, typename _KeyOfValue,
01010            typename _Compare, typename _Alloc>
01011     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01012               _Compare, _Alloc>::iterator
01013     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01014     _M_upper_bound(_Link_type __x, _Link_type __y,
01015            const _Key& __k)
01016     {
01017       while (__x != 0)
01018     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01019       __y = __x, __x = _S_left(__x);
01020     else
01021       __x = _S_right(__x);
01022       return iterator(__y);
01023     }
01024 
01025   template<typename _Key, typename _Val, typename _KeyOfValue,
01026            typename _Compare, typename _Alloc>
01027     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01028               _Compare, _Alloc>::const_iterator
01029     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01030     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
01031            const _Key& __k) const
01032     {
01033       while (__x != 0)
01034     if (_M_impl._M_key_compare(__k, _S_key(__x)))
01035       __y = __x, __x = _S_left(__x);
01036     else
01037       __x = _S_right(__x);
01038       return const_iterator(__y);
01039     }
01040 
01041   template<typename _Key, typename _Val, typename _KeyOfValue,
01042            typename _Compare, typename _Alloc>
01043     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01044                _Compare, _Alloc>::iterator,
01045      typename _Rb_tree<_Key, _Val, _KeyOfValue,
01046                _Compare, _Alloc>::iterator>
01047     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01048     equal_range(const _Key& __k)
01049     {
01050       _Link_type __x = _M_begin();
01051       _Link_type __y = _M_end();
01052       while (__x != 0)
01053     {
01054       if (_M_impl._M_key_compare(_S_key(__x), __k))
01055         __x = _S_right(__x);
01056       else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01057         __y = __x, __x = _S_left(__x);
01058       else
01059         {
01060           _Link_type __xu(__x), __yu(__y);
01061           __y = __x, __x = _S_left(__x);
01062           __xu = _S_right(__xu);
01063           return pair<iterator,
01064                   iterator>(_M_lower_bound(__x, __y, __k),
01065                     _M_upper_bound(__xu, __yu, __k));
01066         }
01067     }
01068       return pair<iterator, iterator>(iterator(__y),
01069                       iterator(__y));
01070     }
01071 
01072   template<typename _Key, typename _Val, typename _KeyOfValue,
01073            typename _Compare, typename _Alloc>
01074     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01075                _Compare, _Alloc>::const_iterator,
01076      typename _Rb_tree<_Key, _Val, _KeyOfValue,
01077                _Compare, _Alloc>::const_iterator>
01078     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01079     equal_range(const _Key& __k) const
01080     {
01081       _Const_Link_type __x = _M_begin();
01082       _Const_Link_type __y = _M_end();
01083       while (__x != 0)
01084     {
01085       if (_M_impl._M_key_compare(_S_key(__x), __k))
01086         __x = _S_right(__x);
01087       else if (_M_impl._M_key_compare(__k, _S_key(__x)))
01088         __y = __x, __x = _S_left(__x);
01089       else
01090         {
01091           _Const_Link_type __xu(__x), __yu(__y);
01092           __y = __x, __x = _S_left(__x);
01093           __xu = _S_right(__xu);
01094           return pair<const_iterator,
01095                   const_iterator>(_M_lower_bound(__x, __y, __k),
01096                       _M_upper_bound(__xu, __yu, __k));
01097         }
01098     }
01099       return pair<const_iterator, const_iterator>(const_iterator(__y),
01100                           const_iterator(__y));
01101     }
01102 
01103   template<typename _Key, typename _Val, typename _KeyOfValue,
01104            typename _Compare, typename _Alloc>
01105     void
01106     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01107 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01108     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t)
01109 #else
01110     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
01111 #endif
01112     {
01113       if (_M_root() == 0)
01114     {
01115       if (__t._M_root() != 0)
01116         {
01117           _M_root() = __t._M_root();
01118           _M_leftmost() = __t._M_leftmost();
01119           _M_rightmost() = __t._M_rightmost();
01120           _M_root()->_M_parent = _M_end();
01121           
01122           __t._M_root() = 0;
01123           __t._M_leftmost() = __t._M_end();
01124           __t._M_rightmost() = __t._M_end();
01125         }
01126     }
01127       else if (__t._M_root() == 0)
01128     {
01129       __t._M_root() = _M_root();
01130       __t._M_leftmost() = _M_leftmost();
01131       __t._M_rightmost() = _M_rightmost();
01132       __t._M_root()->_M_parent = __t._M_end();
01133       
01134       _M_root() = 0;
01135       _M_leftmost() = _M_end();
01136       _M_rightmost() = _M_end();
01137     }
01138       else
01139     {
01140       std::swap(_M_root(),__t._M_root());
01141       std::swap(_M_leftmost(),__t._M_leftmost());
01142       std::swap(_M_rightmost(),__t._M_rightmost());
01143       
01144       _M_root()->_M_parent = _M_end();
01145       __t._M_root()->_M_parent = __t._M_end();
01146     }
01147       // No need to swap header's color as it does not change.
01148       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
01149       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
01150       
01151       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01152       // 431. Swapping containers with unequal allocators.
01153       std::__alloc_swap<_Node_allocator>::
01154     _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
01155     }
01156 
01157   template<typename _Key, typename _Val, typename _KeyOfValue,
01158            typename _Compare, typename _Alloc>
01159     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
01160                _Compare, _Alloc>::iterator, bool>
01161     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01162     _M_insert_unique(const _Val& __v)
01163     {
01164       _Link_type __x = _M_begin();
01165       _Link_type __y = _M_end();
01166       bool __comp = true;
01167       while (__x != 0)
01168     {
01169       __y = __x;
01170       __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
01171       __x = __comp ? _S_left(__x) : _S_right(__x);
01172     }
01173       iterator __j = iterator(__y);
01174       if (__comp)
01175     {
01176       if (__j == begin())
01177         return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
01178       else
01179         --__j;
01180     }
01181       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
01182     return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
01183       return pair<iterator, bool>(__j, false);
01184     }
01185 
01186   template<typename _Key, typename _Val, typename _KeyOfValue,
01187            typename _Compare, typename _Alloc>
01188     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01189     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01190     _M_insert_equal(const _Val& __v)
01191     {
01192       _Link_type __x = _M_begin();
01193       _Link_type __y = _M_end();
01194       while (__x != 0)
01195     {
01196       __y = __x;
01197       __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
01198             _S_left(__x) : _S_right(__x);
01199     }
01200       return _M_insert_(__x, __y, __v);
01201     }
01202 
01203   template<typename _Key, typename _Val, typename _KeyOfValue,
01204            typename _Compare, typename _Alloc>
01205     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01206     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01207     _M_insert_unique_(const_iterator __position, const _Val& __v)
01208     {
01209       // end()
01210       if (__position._M_node == _M_end())
01211     {
01212       if (size() > 0
01213           && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
01214                     _KeyOfValue()(__v)))
01215         return _M_insert_(0, _M_rightmost(), __v);
01216       else
01217         return _M_insert_unique(__v).first;
01218     }
01219       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01220                       _S_key(__position._M_node)))
01221     {
01222       // First, try before...
01223       const_iterator __before = __position;
01224       if (__position._M_node == _M_leftmost()) // begin()
01225         return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
01226       else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
01227                       _KeyOfValue()(__v)))
01228         {
01229           if (_S_right(__before._M_node) == 0)
01230         return _M_insert_(0, __before._M_node, __v);
01231           else
01232         return _M_insert_(__position._M_node,
01233                   __position._M_node, __v);
01234         }
01235       else
01236         return _M_insert_unique(__v).first;
01237     }
01238       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
01239                       _KeyOfValue()(__v)))
01240     {
01241       // ... then try after.
01242       const_iterator __after = __position;
01243       if (__position._M_node == _M_rightmost())
01244         return _M_insert_(0, _M_rightmost(), __v);
01245       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
01246                       _S_key((++__after)._M_node)))
01247         {
01248           if (_S_right(__position._M_node) == 0)
01249         return _M_insert_(0, __position._M_node, __v);
01250           else
01251         return _M_insert_(__after._M_node, __after._M_node, __v);
01252         }
01253       else
01254         return _M_insert_unique(__v).first;
01255     }
01256       else
01257     // Equivalent keys.
01258     return iterator(static_cast<_Link_type>
01259             (const_cast<_Base_ptr>(__position._M_node)));
01260     }
01261 
01262   template<typename _Key, typename _Val, typename _KeyOfValue,
01263            typename _Compare, typename _Alloc>
01264     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
01265     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01266     _M_insert_equal_(const_iterator __position, const _Val& __v)
01267     {
01268       // end()
01269       if (__position._M_node == _M_end())
01270     {
01271       if (size() > 0
01272           && !_M_impl._M_key_compare(_KeyOfValue()(__v),
01273                      _S_key(_M_rightmost())))
01274         return _M_insert_(0, _M_rightmost(), __v);
01275       else
01276         return _M_insert_equal(__v);
01277     }
01278       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
01279                        _KeyOfValue()(__v)))
01280     {
01281       // First, try before...
01282       const_iterator __before = __position;
01283       if (__position._M_node == _M_leftmost()) // begin()
01284         return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
01285       else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
01286                        _S_key((--__before)._M_node)))
01287         {
01288           if (_S_right(__before._M_node) == 0)
01289         return _M_insert_(0, __before._M_node, __v);
01290           else
01291         return _M_insert_(__position._M_node,
01292                   __position._M_node, __v);
01293         }
01294       else
01295         return _M_insert_equal(__v);
01296     }
01297       else
01298     {
01299       // ... then try after.  
01300       const_iterator __after = __position;
01301       if (__position._M_node == _M_rightmost())
01302         return _M_insert_(0, _M_rightmost(), __v);
01303       else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
01304                        _KeyOfValue()(__v)))
01305         {
01306           if (_S_right(__position._M_node) == 0)
01307         return _M_insert_(0, __position._M_node, __v);
01308           else
01309         return _M_insert_(__after._M_node, __after._M_node, __v);
01310         }
01311       else
01312         return _M_insert_equal_lower(__v);
01313     }
01314     }
01315 
01316   template<typename _Key, typename _Val, typename _KoV,
01317            typename _Cmp, typename _Alloc>
01318     template<class _II>
01319       void
01320       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01321       _M_insert_unique(_II __first, _II __last)
01322       {
01323     for (; __first != __last; ++__first)
01324       _M_insert_unique_(end(), *__first);
01325       }
01326 
01327   template<typename _Key, typename _Val, typename _KoV,
01328            typename _Cmp, typename _Alloc>
01329     template<class _II>
01330       void
01331       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
01332       _M_insert_equal(_II __first, _II __last)
01333       {
01334     for (; __first != __last; ++__first)
01335       _M_insert_equal_(end(), *__first);
01336       }
01337 
01338   template<typename _Key, typename _Val, typename _KeyOfValue,
01339            typename _Compare, typename _Alloc>
01340     inline void
01341     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01342     erase(iterator __position)
01343     {
01344       _Link_type __y =
01345     static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01346                 (__position._M_node,
01347                  this->_M_impl._M_header));
01348       _M_destroy_node(__y);
01349       --_M_impl._M_node_count;
01350     }
01351 
01352   template<typename _Key, typename _Val, typename _KeyOfValue,
01353            typename _Compare, typename _Alloc>
01354     inline void
01355     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01356     erase(const_iterator __position)
01357     {
01358       _Link_type __y =
01359     static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
01360                 (const_cast<_Base_ptr>(__position._M_node),
01361                  this->_M_impl._M_header));
01362       _M_destroy_node(__y);
01363       --_M_impl._M_node_count;
01364     }
01365 
01366   template<typename _Key, typename _Val, typename _KeyOfValue,
01367            typename _Compare, typename _Alloc>
01368     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01369     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01370     erase(const _Key& __x)
01371     {
01372       pair<iterator, iterator> __p = equal_range(__x);
01373       const size_type __old_size = size();
01374       erase(__p.first, __p.second);
01375       return __old_size - size();
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     erase(iterator __first, iterator __last)
01383     {
01384       if (__first == begin() && __last == end())
01385     clear();
01386       else
01387     while (__first != __last)
01388       erase(__first++);
01389     }
01390 
01391   template<typename _Key, typename _Val, typename _KeyOfValue,
01392            typename _Compare, typename _Alloc>
01393     void
01394     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01395     erase(const_iterator __first, const_iterator __last)
01396     {
01397       if (__first == begin() && __last == end())
01398     clear();
01399       else
01400     while (__first != __last)
01401       erase(__first++);
01402     }
01403 
01404   template<typename _Key, typename _Val, typename _KeyOfValue,
01405            typename _Compare, typename _Alloc>
01406     void
01407     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01408     erase(const _Key* __first, const _Key* __last)
01409     {
01410       while (__first != __last)
01411     erase(*__first++);
01412     }
01413 
01414   template<typename _Key, typename _Val, typename _KeyOfValue,
01415            typename _Compare, typename _Alloc>
01416     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01417               _Compare, _Alloc>::iterator
01418     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01419     find(const _Key& __k)
01420     {
01421       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01422       return (__j == end()
01423           || _M_impl._M_key_compare(__k,
01424                     _S_key(__j._M_node))) ? end() : __j;
01425     }
01426 
01427   template<typename _Key, typename _Val, typename _KeyOfValue,
01428            typename _Compare, typename _Alloc>
01429     typename _Rb_tree<_Key, _Val, _KeyOfValue,
01430               _Compare, _Alloc>::const_iterator
01431     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01432     find(const _Key& __k) const
01433     {
01434       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
01435       return (__j == end()
01436           || _M_impl._M_key_compare(__k, 
01437                     _S_key(__j._M_node))) ? end() : __j;
01438     }
01439 
01440   template<typename _Key, typename _Val, typename _KeyOfValue,
01441            typename _Compare, typename _Alloc>
01442     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
01443     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
01444     count(const _Key& __k) const
01445     {
01446       pair<const_iterator, const_iterator> __p = equal_range(__k);
01447       const size_type __n = std::distance(__p.first, __p.second);
01448       return __n;
01449     }
01450 
01451   unsigned int
01452   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
01453                        const _Rb_tree_node_base* __root);
01454 
01455   template<typename _Key, typename _Val, typename _KeyOfValue,
01456            typename _Compare, typename _Alloc>
01457     bool
01458     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
01459     {
01460       if (_M_impl._M_node_count == 0 || begin() == end())
01461     return _M_impl._M_node_count == 0 && begin() == end()
01462            && this->_M_impl._M_header._M_left == _M_end()
01463            && this->_M_impl._M_header._M_right == _M_end();
01464 
01465       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
01466       for (const_iterator __it = begin(); __it != end(); ++__it)
01467     {
01468       _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
01469       _Const_Link_type __L = _S_left(__x);
01470       _Const_Link_type __R = _S_right(__x);
01471 
01472       if (__x->_M_color == _S_red)
01473         if ((__L && __L->_M_color == _S_red)
01474         || (__R && __R->_M_color == _S_red))
01475           return false;
01476 
01477       if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
01478         return false;
01479       if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
01480         return false;
01481 
01482       if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
01483         return false;
01484     }
01485 
01486       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
01487     return false;
01488       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
01489     return false;
01490       return true;
01491     }
01492 
01493 _GLIBCXX_END_NAMESPACE
01494 
01495 #endif

Generated on Thu Jul 23 21:16:23 2009 for libstdc++ by  doxygen 1.5.8