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