libstdc++
|
00001 // RB tree implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 00004 // 2009, 2010, 2011 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(iterator __position) 00766 { _M_erase_aux(__position); } 00767 00768 void 00769 erase(const_iterator __position) 00770 { _M_erase_aux(__position); } 00771 #endif 00772 size_type 00773 erase(const key_type& __x); 00774 00775 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00776 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00777 // DR 130. Associative erase should return an iterator. 00778 iterator 00779 erase(const_iterator __first, const_iterator __last) 00780 { 00781 _M_erase_aux(__first, __last); 00782 return __last._M_const_cast(); 00783 } 00784 #else 00785 void 00786 erase(iterator __first, iterator __last) 00787 { _M_erase_aux(__first, __last); } 00788 00789 void 00790 erase(const_iterator __first, const_iterator __last) 00791 { _M_erase_aux(__first, __last); } 00792 #endif 00793 void 00794 erase(const key_type* __first, const key_type* __last); 00795 00796 void 00797 clear() 00798 { 00799 _M_erase(_M_begin()); 00800 _M_leftmost() = _M_end(); 00801 _M_root() = 0; 00802 _M_rightmost() = _M_end(); 00803 _M_impl._M_node_count = 0; 00804 } 00805 00806 // Set operations. 00807 iterator 00808 find(const key_type& __k); 00809 00810 const_iterator 00811 find(const key_type& __k) const; 00812 00813 size_type 00814 count(const key_type& __k) const; 00815 00816 iterator 00817 lower_bound(const key_type& __k) 00818 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 00819 00820 const_iterator 00821 lower_bound(const key_type& __k) const 00822 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 00823 00824 iterator 00825 upper_bound(const key_type& __k) 00826 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 00827 00828 const_iterator 00829 upper_bound(const key_type& __k) const 00830 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 00831 00832 pair<iterator, iterator> 00833 equal_range(const key_type& __k); 00834 00835 pair<const_iterator, const_iterator> 00836 equal_range(const key_type& __k) const; 00837 00838 // Debugging. 00839 bool 00840 __rb_verify() const; 00841 }; 00842 00843 template<typename _Key, typename _Val, typename _KeyOfValue, 00844 typename _Compare, typename _Alloc> 00845 inline bool 00846 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00847 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00848 { 00849 return __x.size() == __y.size() 00850 && std::equal(__x.begin(), __x.end(), __y.begin()); 00851 } 00852 00853 template<typename _Key, typename _Val, typename _KeyOfValue, 00854 typename _Compare, typename _Alloc> 00855 inline bool 00856 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00857 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00858 { 00859 return std::lexicographical_compare(__x.begin(), __x.end(), 00860 __y.begin(), __y.end()); 00861 } 00862 00863 template<typename _Key, typename _Val, typename _KeyOfValue, 00864 typename _Compare, typename _Alloc> 00865 inline bool 00866 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00867 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00868 { return !(__x == __y); } 00869 00870 template<typename _Key, typename _Val, typename _KeyOfValue, 00871 typename _Compare, typename _Alloc> 00872 inline bool 00873 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00874 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00875 { return __y < __x; } 00876 00877 template<typename _Key, typename _Val, typename _KeyOfValue, 00878 typename _Compare, typename _Alloc> 00879 inline bool 00880 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00881 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00882 { return !(__y < __x); } 00883 00884 template<typename _Key, typename _Val, typename _KeyOfValue, 00885 typename _Compare, typename _Alloc> 00886 inline bool 00887 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00888 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00889 { return !(__x < __y); } 00890 00891 template<typename _Key, typename _Val, typename _KeyOfValue, 00892 typename _Compare, typename _Alloc> 00893 inline void 00894 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00895 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00896 { __x.swap(__y); } 00897 00898 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00899 template<typename _Key, typename _Val, typename _KeyOfValue, 00900 typename _Compare, typename _Alloc> 00901 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00902 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) 00903 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) 00904 { 00905 if (__x._M_root() != 0) 00906 { 00907 _M_root() = __x._M_root(); 00908 _M_leftmost() = __x._M_leftmost(); 00909 _M_rightmost() = __x._M_rightmost(); 00910 _M_root()->_M_parent = _M_end(); 00911 00912 __x._M_root() = 0; 00913 __x._M_leftmost() = __x._M_end(); 00914 __x._M_rightmost() = __x._M_end(); 00915 00916 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 00917 __x._M_impl._M_node_count = 0; 00918 } 00919 } 00920 #endif 00921 00922 template<typename _Key, typename _Val, typename _KeyOfValue, 00923 typename _Compare, typename _Alloc> 00924 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 00925 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00926 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 00927 { 00928 if (this != &__x) 00929 { 00930 // Note that _Key may be a constant type. 00931 clear(); 00932 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 00933 if (__x._M_root() != 0) 00934 { 00935 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00936 _M_leftmost() = _S_minimum(_M_root()); 00937 _M_rightmost() = _S_maximum(_M_root()); 00938 _M_impl._M_node_count = __x._M_impl._M_node_count; 00939 } 00940 } 00941 return *this; 00942 } 00943 00944 template<typename _Key, typename _Val, typename _KeyOfValue, 00945 typename _Compare, typename _Alloc> 00946 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00947 template<typename _Arg> 00948 #endif 00949 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 00950 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00951 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00952 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v) 00953 #else 00954 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) 00955 #endif 00956 { 00957 bool __insert_left = (__x != 0 || __p == _M_end() 00958 || _M_impl._M_key_compare(_KeyOfValue()(__v), 00959 _S_key(__p))); 00960 00961 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 00962 00963 _Rb_tree_insert_and_rebalance(__insert_left, __z, 00964 const_cast<_Base_ptr>(__p), 00965 this->_M_impl._M_header); 00966 ++_M_impl._M_node_count; 00967 return iterator(__z); 00968 } 00969 00970 template<typename _Key, typename _Val, typename _KeyOfValue, 00971 typename _Compare, typename _Alloc> 00972 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00973 template<typename _Arg> 00974 #endif 00975 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 00976 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00977 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00978 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) 00979 #else 00980 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 00981 #endif 00982 { 00983 bool __insert_left = (__x != 0 || __p == _M_end() 00984 || !_M_impl._M_key_compare(_S_key(__p), 00985 _KeyOfValue()(__v))); 00986 00987 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 00988 00989 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 00990 this->_M_impl._M_header); 00991 ++_M_impl._M_node_count; 00992 return iterator(__z); 00993 } 00994 00995 template<typename _Key, typename _Val, typename _KeyOfValue, 00996 typename _Compare, typename _Alloc> 00997 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00998 template<typename _Arg> 00999 #endif 01000 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01001 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01002 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01003 _M_insert_equal_lower(_Arg&& __v) 01004 #else 01005 _M_insert_equal_lower(const _Val& __v) 01006 #endif 01007 { 01008 _Link_type __x = _M_begin(); 01009 _Link_type __y = _M_end(); 01010 while (__x != 0) 01011 { 01012 __y = __x; 01013 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 01014 _S_left(__x) : _S_right(__x); 01015 } 01016 return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)); 01017 } 01018 01019 template<typename _Key, typename _Val, typename _KoV, 01020 typename _Compare, typename _Alloc> 01021 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01022 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01023 _M_copy(_Const_Link_type __x, _Link_type __p) 01024 { 01025 // Structural copy. __x and __p must be non-null. 01026 _Link_type __top = _M_clone_node(__x); 01027 __top->_M_parent = __p; 01028 01029 __try 01030 { 01031 if (__x->_M_right) 01032 __top->_M_right = _M_copy(_S_right(__x), __top); 01033 __p = __top; 01034 __x = _S_left(__x); 01035 01036 while (__x != 0) 01037 { 01038 _Link_type __y = _M_clone_node(__x); 01039 __p->_M_left = __y; 01040 __y->_M_parent = __p; 01041 if (__x->_M_right) 01042 __y->_M_right = _M_copy(_S_right(__x), __y); 01043 __p = __y; 01044 __x = _S_left(__x); 01045 } 01046 } 01047 __catch(...) 01048 { 01049 _M_erase(__top); 01050 __throw_exception_again; 01051 } 01052 return __top; 01053 } 01054 01055 template<typename _Key, typename _Val, typename _KeyOfValue, 01056 typename _Compare, typename _Alloc> 01057 void 01058 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01059 _M_erase(_Link_type __x) 01060 { 01061 // Erase without rebalancing. 01062 while (__x != 0) 01063 { 01064 _M_erase(_S_right(__x)); 01065 _Link_type __y = _S_left(__x); 01066 _M_destroy_node(__x); 01067 __x = __y; 01068 } 01069 } 01070 01071 template<typename _Key, typename _Val, typename _KeyOfValue, 01072 typename _Compare, typename _Alloc> 01073 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01074 _Compare, _Alloc>::iterator 01075 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01076 _M_lower_bound(_Link_type __x, _Link_type __y, 01077 const _Key& __k) 01078 { 01079 while (__x != 0) 01080 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01081 __y = __x, __x = _S_left(__x); 01082 else 01083 __x = _S_right(__x); 01084 return iterator(__y); 01085 } 01086 01087 template<typename _Key, typename _Val, typename _KeyOfValue, 01088 typename _Compare, typename _Alloc> 01089 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01090 _Compare, _Alloc>::const_iterator 01091 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01092 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 01093 const _Key& __k) const 01094 { 01095 while (__x != 0) 01096 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01097 __y = __x, __x = _S_left(__x); 01098 else 01099 __x = _S_right(__x); 01100 return const_iterator(__y); 01101 } 01102 01103 template<typename _Key, typename _Val, typename _KeyOfValue, 01104 typename _Compare, typename _Alloc> 01105 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01106 _Compare, _Alloc>::iterator 01107 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01108 _M_upper_bound(_Link_type __x, _Link_type __y, 01109 const _Key& __k) 01110 { 01111 while (__x != 0) 01112 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01113 __y = __x, __x = _S_left(__x); 01114 else 01115 __x = _S_right(__x); 01116 return iterator(__y); 01117 } 01118 01119 template<typename _Key, typename _Val, typename _KeyOfValue, 01120 typename _Compare, typename _Alloc> 01121 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01122 _Compare, _Alloc>::const_iterator 01123 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01124 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 01125 const _Key& __k) const 01126 { 01127 while (__x != 0) 01128 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01129 __y = __x, __x = _S_left(__x); 01130 else 01131 __x = _S_right(__x); 01132 return const_iterator(__y); 01133 } 01134 01135 template<typename _Key, typename _Val, typename _KeyOfValue, 01136 typename _Compare, typename _Alloc> 01137 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01138 _Compare, _Alloc>::iterator, 01139 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01140 _Compare, _Alloc>::iterator> 01141 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01142 equal_range(const _Key& __k) 01143 { 01144 _Link_type __x = _M_begin(); 01145 _Link_type __y = _M_end(); 01146 while (__x != 0) 01147 { 01148 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01149 __x = _S_right(__x); 01150 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01151 __y = __x, __x = _S_left(__x); 01152 else 01153 { 01154 _Link_type __xu(__x), __yu(__y); 01155 __y = __x, __x = _S_left(__x); 01156 __xu = _S_right(__xu); 01157 return pair<iterator, 01158 iterator>(_M_lower_bound(__x, __y, __k), 01159 _M_upper_bound(__xu, __yu, __k)); 01160 } 01161 } 01162 return pair<iterator, iterator>(iterator(__y), 01163 iterator(__y)); 01164 } 01165 01166 template<typename _Key, typename _Val, typename _KeyOfValue, 01167 typename _Compare, typename _Alloc> 01168 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01169 _Compare, _Alloc>::const_iterator, 01170 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01171 _Compare, _Alloc>::const_iterator> 01172 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01173 equal_range(const _Key& __k) const 01174 { 01175 _Const_Link_type __x = _M_begin(); 01176 _Const_Link_type __y = _M_end(); 01177 while (__x != 0) 01178 { 01179 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01180 __x = _S_right(__x); 01181 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01182 __y = __x, __x = _S_left(__x); 01183 else 01184 { 01185 _Const_Link_type __xu(__x), __yu(__y); 01186 __y = __x, __x = _S_left(__x); 01187 __xu = _S_right(__xu); 01188 return pair<const_iterator, 01189 const_iterator>(_M_lower_bound(__x, __y, __k), 01190 _M_upper_bound(__xu, __yu, __k)); 01191 } 01192 } 01193 return pair<const_iterator, const_iterator>(const_iterator(__y), 01194 const_iterator(__y)); 01195 } 01196 01197 template<typename _Key, typename _Val, typename _KeyOfValue, 01198 typename _Compare, typename _Alloc> 01199 void 01200 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01201 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 01202 { 01203 if (_M_root() == 0) 01204 { 01205 if (__t._M_root() != 0) 01206 { 01207 _M_root() = __t._M_root(); 01208 _M_leftmost() = __t._M_leftmost(); 01209 _M_rightmost() = __t._M_rightmost(); 01210 _M_root()->_M_parent = _M_end(); 01211 01212 __t._M_root() = 0; 01213 __t._M_leftmost() = __t._M_end(); 01214 __t._M_rightmost() = __t._M_end(); 01215 } 01216 } 01217 else if (__t._M_root() == 0) 01218 { 01219 __t._M_root() = _M_root(); 01220 __t._M_leftmost() = _M_leftmost(); 01221 __t._M_rightmost() = _M_rightmost(); 01222 __t._M_root()->_M_parent = __t._M_end(); 01223 01224 _M_root() = 0; 01225 _M_leftmost() = _M_end(); 01226 _M_rightmost() = _M_end(); 01227 } 01228 else 01229 { 01230 std::swap(_M_root(),__t._M_root()); 01231 std::swap(_M_leftmost(),__t._M_leftmost()); 01232 std::swap(_M_rightmost(),__t._M_rightmost()); 01233 01234 _M_root()->_M_parent = _M_end(); 01235 __t._M_root()->_M_parent = __t._M_end(); 01236 } 01237 // No need to swap header's color as it does not change. 01238 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 01239 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 01240 01241 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01242 // 431. Swapping containers with unequal allocators. 01243 std::__alloc_swap<_Node_allocator>:: 01244 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 01245 } 01246 01247 template<typename _Key, typename _Val, typename _KeyOfValue, 01248 typename _Compare, typename _Alloc> 01249 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01250 template<typename _Arg> 01251 #endif 01252 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01253 _Compare, _Alloc>::iterator, bool> 01254 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01255 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01256 _M_insert_unique(_Arg&& __v) 01257 #else 01258 _M_insert_unique(const _Val& __v) 01259 #endif 01260 { 01261 _Link_type __x = _M_begin(); 01262 _Link_type __y = _M_end(); 01263 bool __comp = true; 01264 while (__x != 0) 01265 { 01266 __y = __x; 01267 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 01268 __x = __comp ? _S_left(__x) : _S_right(__x); 01269 } 01270 iterator __j = iterator(__y); 01271 if (__comp) 01272 { 01273 if (__j == begin()) 01274 return pair<iterator, bool> 01275 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true); 01276 else 01277 --__j; 01278 } 01279 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 01280 return pair<iterator, bool> 01281 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true); 01282 return pair<iterator, bool>(__j, false); 01283 } 01284 01285 template<typename _Key, typename _Val, typename _KeyOfValue, 01286 typename _Compare, typename _Alloc> 01287 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01288 template<typename _Arg> 01289 #endif 01290 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01291 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01292 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01293 _M_insert_equal(_Arg&& __v) 01294 #else 01295 _M_insert_equal(const _Val& __v) 01296 #endif 01297 { 01298 _Link_type __x = _M_begin(); 01299 _Link_type __y = _M_end(); 01300 while (__x != 0) 01301 { 01302 __y = __x; 01303 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 01304 _S_left(__x) : _S_right(__x); 01305 } 01306 return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)); 01307 } 01308 01309 template<typename _Key, typename _Val, typename _KeyOfValue, 01310 typename _Compare, typename _Alloc> 01311 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01312 template<typename _Arg> 01313 #endif 01314 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01315 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01316 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01317 _M_insert_unique_(const_iterator __position, _Arg&& __v) 01318 #else 01319 _M_insert_unique_(const_iterator __position, const _Val& __v) 01320 #endif 01321 { 01322 // end() 01323 if (__position._M_node == _M_end()) 01324 { 01325 if (size() > 0 01326 && _M_impl._M_key_compare(_S_key(_M_rightmost()), 01327 _KeyOfValue()(__v))) 01328 return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v)); 01329 else 01330 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; 01331 } 01332 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 01333 _S_key(__position._M_node))) 01334 { 01335 // First, try before... 01336 const_iterator __before = __position; 01337 if (__position._M_node == _M_leftmost()) // begin() 01338 return _M_insert_(_M_leftmost(), _M_leftmost(), 01339 _GLIBCXX_FORWARD(_Arg, __v)); 01340 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 01341 _KeyOfValue()(__v))) 01342 { 01343 if (_S_right(__before._M_node) == 0) 01344 return _M_insert_(0, __before._M_node, 01345 _GLIBCXX_FORWARD(_Arg, __v)); 01346 else 01347 return _M_insert_(__position._M_node, 01348 __position._M_node, 01349 _GLIBCXX_FORWARD(_Arg, __v)); 01350 } 01351 else 01352 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; 01353 } 01354 else if (_M_impl._M_key_compare(_S_key(__position._M_node), 01355 _KeyOfValue()(__v))) 01356 { 01357 // ... then try after. 01358 const_iterator __after = __position; 01359 if (__position._M_node == _M_rightmost()) 01360 return _M_insert_(0, _M_rightmost(), 01361 _GLIBCXX_FORWARD(_Arg, __v)); 01362 else if (_M_impl._M_key_compare(_KeyOfValue()(__v), 01363 _S_key((++__after)._M_node))) 01364 { 01365 if (_S_right(__position._M_node) == 0) 01366 return _M_insert_(0, __position._M_node, 01367 _GLIBCXX_FORWARD(_Arg, __v)); 01368 else 01369 return _M_insert_(__after._M_node, __after._M_node, 01370 _GLIBCXX_FORWARD(_Arg, __v)); 01371 } 01372 else 01373 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; 01374 } 01375 else 01376 // Equivalent keys. 01377 return __position._M_const_cast(); 01378 } 01379 01380 template<typename _Key, typename _Val, typename _KeyOfValue, 01381 typename _Compare, typename _Alloc> 01382 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01383 template<typename _Arg> 01384 #endif 01385 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01386 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01387 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01388 _M_insert_equal_(const_iterator __position, _Arg&& __v) 01389 #else 01390 _M_insert_equal_(const_iterator __position, const _Val& __v) 01391 #endif 01392 { 01393 // end() 01394 if (__position._M_node == _M_end()) 01395 { 01396 if (size() > 0 01397 && !_M_impl._M_key_compare(_KeyOfValue()(__v), 01398 _S_key(_M_rightmost()))) 01399 return _M_insert_(0, _M_rightmost(), 01400 _GLIBCXX_FORWARD(_Arg, __v)); 01401 else 01402 return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v)); 01403 } 01404 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), 01405 _KeyOfValue()(__v))) 01406 { 01407 // First, try before... 01408 const_iterator __before = __position; 01409 if (__position._M_node == _M_leftmost()) // begin() 01410 return _M_insert_(_M_leftmost(), _M_leftmost(), 01411 _GLIBCXX_FORWARD(_Arg, __v)); 01412 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 01413 _S_key((--__before)._M_node))) 01414 { 01415 if (_S_right(__before._M_node) == 0) 01416 return _M_insert_(0, __before._M_node, 01417 _GLIBCXX_FORWARD(_Arg, __v)); 01418 else 01419 return _M_insert_(__position._M_node, 01420 __position._M_node, 01421 _GLIBCXX_FORWARD(_Arg, __v)); 01422 } 01423 else 01424 return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v)); 01425 } 01426 else 01427 { 01428 // ... then try after. 01429 const_iterator __after = __position; 01430 if (__position._M_node == _M_rightmost()) 01431 return _M_insert_(0, _M_rightmost(), 01432 _GLIBCXX_FORWARD(_Arg, __v)); 01433 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), 01434 _KeyOfValue()(__v))) 01435 { 01436 if (_S_right(__position._M_node) == 0) 01437 return _M_insert_(0, __position._M_node, 01438 _GLIBCXX_FORWARD(_Arg, __v)); 01439 else 01440 return _M_insert_(__after._M_node, __after._M_node, 01441 _GLIBCXX_FORWARD(_Arg, __v)); 01442 } 01443 else 01444 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 01445 } 01446 } 01447 01448 template<typename _Key, typename _Val, typename _KoV, 01449 typename _Cmp, typename _Alloc> 01450 template<class _II> 01451 void 01452 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 01453 _M_insert_unique(_II __first, _II __last) 01454 { 01455 for (; __first != __last; ++__first) 01456 _M_insert_unique_(end(), *__first); 01457 } 01458 01459 template<typename _Key, typename _Val, typename _KoV, 01460 typename _Cmp, typename _Alloc> 01461 template<class _II> 01462 void 01463 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 01464 _M_insert_equal(_II __first, _II __last) 01465 { 01466 for (; __first != __last; ++__first) 01467 _M_insert_equal_(end(), *__first); 01468 } 01469 01470 template<typename _Key, typename _Val, typename _KeyOfValue, 01471 typename _Compare, typename _Alloc> 01472 void 01473 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01474 _M_erase_aux(const_iterator __position) 01475 { 01476 _Link_type __y = 01477 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 01478 (const_cast<_Base_ptr>(__position._M_node), 01479 this->_M_impl._M_header)); 01480 _M_destroy_node(__y); 01481 --_M_impl._M_node_count; 01482 } 01483 01484 template<typename _Key, typename _Val, typename _KeyOfValue, 01485 typename _Compare, typename _Alloc> 01486 void 01487 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01488 _M_erase_aux(const_iterator __first, const_iterator __last) 01489 { 01490 if (__first == begin() && __last == end()) 01491 clear(); 01492 else 01493 while (__first != __last) 01494 erase(__first++); 01495 } 01496 01497 template<typename _Key, typename _Val, typename _KeyOfValue, 01498 typename _Compare, typename _Alloc> 01499 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 01500 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01501 erase(const _Key& __x) 01502 { 01503 pair<iterator, iterator> __p = equal_range(__x); 01504 const size_type __old_size = size(); 01505 erase(__p.first, __p.second); 01506 return __old_size - size(); 01507 } 01508 01509 template<typename _Key, typename _Val, typename _KeyOfValue, 01510 typename _Compare, typename _Alloc> 01511 void 01512 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01513 erase(const _Key* __first, const _Key* __last) 01514 { 01515 while (__first != __last) 01516 erase(*__first++); 01517 } 01518 01519 template<typename _Key, typename _Val, typename _KeyOfValue, 01520 typename _Compare, typename _Alloc> 01521 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01522 _Compare, _Alloc>::iterator 01523 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01524 find(const _Key& __k) 01525 { 01526 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 01527 return (__j == end() 01528 || _M_impl._M_key_compare(__k, 01529 _S_key(__j._M_node))) ? end() : __j; 01530 } 01531 01532 template<typename _Key, typename _Val, typename _KeyOfValue, 01533 typename _Compare, typename _Alloc> 01534 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01535 _Compare, _Alloc>::const_iterator 01536 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01537 find(const _Key& __k) const 01538 { 01539 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 01540 return (__j == end() 01541 || _M_impl._M_key_compare(__k, 01542 _S_key(__j._M_node))) ? end() : __j; 01543 } 01544 01545 template<typename _Key, typename _Val, typename _KeyOfValue, 01546 typename _Compare, typename _Alloc> 01547 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 01548 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01549 count(const _Key& __k) const 01550 { 01551 pair<const_iterator, const_iterator> __p = equal_range(__k); 01552 const size_type __n = std::distance(__p.first, __p.second); 01553 return __n; 01554 } 01555 01556 _GLIBCXX_PURE unsigned int 01557 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 01558 const _Rb_tree_node_base* __root) throw (); 01559 01560 template<typename _Key, typename _Val, typename _KeyOfValue, 01561 typename _Compare, typename _Alloc> 01562 bool 01563 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 01564 { 01565 if (_M_impl._M_node_count == 0 || begin() == end()) 01566 return _M_impl._M_node_count == 0 && begin() == end() 01567 && this->_M_impl._M_header._M_left == _M_end() 01568 && this->_M_impl._M_header._M_right == _M_end(); 01569 01570 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 01571 for (const_iterator __it = begin(); __it != end(); ++__it) 01572 { 01573 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 01574 _Const_Link_type __L = _S_left(__x); 01575 _Const_Link_type __R = _S_right(__x); 01576 01577 if (__x->_M_color == _S_red) 01578 if ((__L && __L->_M_color == _S_red) 01579 || (__R && __R->_M_color == _S_red)) 01580 return false; 01581 01582 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 01583 return false; 01584 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 01585 return false; 01586 01587 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 01588 return false; 01589 } 01590 01591 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 01592 return false; 01593 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 01594 return false; 01595 return true; 01596 } 01597 01598 _GLIBCXX_END_NAMESPACE_VERSION 01599 } // namespace 01600 01601 #endif