libstdc++
|
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