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