stl_tree.h

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

Generated on Wed Jun 9 11:19:15 2004 for libstdc++-v3 Source by doxygen 1.3.7