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<_Const_Link_type>(this->_M_impl._M_header._M_parent); } 00465 00466 _Link_type 00467 _M_end() 00468 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 00469 00470 _Const_Link_type 00471 _M_end() const 00472 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 00473 00474 static const_reference 00475 _S_value(_Const_Link_type __x) 00476 { return __x->_M_value_field; } 00477 00478 static const _Key& 00479 _S_key(_Const_Link_type __x) 00480 { return _KeyOfValue()(_S_value(__x)); } 00481 00482 static _Link_type 00483 _S_left(_Base_ptr __x) 00484 { return static_cast<_Link_type>(__x->_M_left); } 00485 00486 static _Const_Link_type 00487 _S_left(_Const_Base_ptr __x) 00488 { return static_cast<_Const_Link_type>(__x->_M_left); } 00489 00490 static _Link_type 00491 _S_right(_Base_ptr __x) 00492 { return static_cast<_Link_type>(__x->_M_right); } 00493 00494 static _Const_Link_type 00495 _S_right(_Const_Base_ptr __x) 00496 { return static_cast<_Const_Link_type>(__x->_M_right); } 00497 00498 static const_reference 00499 _S_value(_Const_Base_ptr __x) 00500 { return static_cast<_Const_Link_type>(__x)->_M_value_field; } 00501 00502 static const _Key& 00503 _S_key(_Const_Base_ptr __x) 00504 { return _KeyOfValue()(_S_value(__x)); } 00505 00506 static _Base_ptr 00507 _S_minimum(_Base_ptr __x) 00508 { return _Rb_tree_node_base::_S_minimum(__x); } 00509 00510 static _Const_Base_ptr 00511 _S_minimum(_Const_Base_ptr __x) 00512 { return _Rb_tree_node_base::_S_minimum(__x); } 00513 00514 static _Base_ptr 00515 _S_maximum(_Base_ptr __x) 00516 { return _Rb_tree_node_base::_S_maximum(__x); } 00517 00518 static _Const_Base_ptr 00519 _S_maximum(_Const_Base_ptr __x) 00520 { return _Rb_tree_node_base::_S_maximum(__x); } 00521 00522 public: 00523 typedef _Rb_tree_iterator<value_type> iterator; 00524 typedef _Rb_tree_const_iterator<value_type> const_iterator; 00525 00526 typedef std::reverse_iterator<iterator> reverse_iterator; 00527 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00528 00529 private: 00530 iterator 00531 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); 00532 00533 _Link_type 00534 _M_copy(_Const_Link_type __x, _Link_type __p); 00535 00536 void 00537 _M_erase(_Link_type __x); 00538 00539 public: 00540 // allocation/deallocation 00541 _Rb_tree() 00542 { } 00543 00544 _Rb_tree(const _Compare& __comp) 00545 : _M_impl(allocator_type(), __comp) 00546 { } 00547 00548 _Rb_tree(const _Compare& __comp, const allocator_type& __a) 00549 : _M_impl(__a, __comp) 00550 { } 00551 00552 _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 00553 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare) 00554 { 00555 if (__x._M_root() != 0) 00556 { 00557 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00558 _M_leftmost() = _S_minimum(_M_root()); 00559 _M_rightmost() = _S_maximum(_M_root()); 00560 _M_impl._M_node_count = __x._M_impl._M_node_count; 00561 } 00562 } 00563 00564 ~_Rb_tree() 00565 { _M_erase(_M_begin()); } 00566 00567 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 00568 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x); 00569 00570 // Accessors. 00571 _Compare 00572 key_comp() const 00573 { return _M_impl._M_key_compare; } 00574 00575 iterator 00576 begin() 00577 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); } 00578 00579 const_iterator 00580 begin() const 00581 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); } 00582 00583 iterator 00584 end() 00585 { return static_cast<_Link_type>(&this->_M_impl._M_header); } 00586 00587 const_iterator 00588 end() const 00589 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } 00590 00591 reverse_iterator 00592 rbegin() 00593 { return reverse_iterator(end()); } 00594 00595 const_reverse_iterator 00596 rbegin() const 00597 { return const_reverse_iterator(end()); } 00598 00599 reverse_iterator 00600 rend() 00601 { return reverse_iterator(begin()); } 00602 00603 const_reverse_iterator 00604 rend() const 00605 { return const_reverse_iterator(begin()); } 00606 00607 bool 00608 empty() const 00609 { return _M_impl._M_node_count == 0; } 00610 00611 size_type 00612 size() const 00613 { return _M_impl._M_node_count; } 00614 00615 size_type 00616 max_size() const 00617 { return size_type(-1); } 00618 00619 void 00620 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t); 00621 00622 // Insert/erase. 00623 pair<iterator,bool> 00624 insert_unique(const value_type& __x); 00625 00626 iterator 00627 insert_equal(const value_type& __x); 00628 00629 iterator 00630 insert_unique(iterator __position, const value_type& __x); 00631 00632 iterator 00633 insert_equal(iterator __position, const value_type& __x); 00634 00635 template<typename _InputIterator> 00636 void 00637 insert_unique(_InputIterator __first, _InputIterator __last); 00638 00639 template<typename _InputIterator> 00640 void 00641 insert_equal(_InputIterator __first, _InputIterator __last); 00642 00643 void 00644 erase(iterator __position); 00645 00646 size_type 00647 erase(const key_type& __x); 00648 00649 void 00650 erase(iterator __first, iterator __last); 00651 00652 void 00653 erase(const key_type* __first, const key_type* __last); 00654 00655 void 00656 clear() 00657 { 00658 _M_erase(_M_begin()); 00659 _M_leftmost() = _M_end(); 00660 _M_root() = 0; 00661 _M_rightmost() = _M_end(); 00662 _M_impl._M_node_count = 0; 00663 } 00664 00665 // Set operations. 00666 iterator 00667 find(const key_type& __x); 00668 00669 const_iterator 00670 find(const key_type& __x) const; 00671 00672 size_type 00673 count(const key_type& __x) const; 00674 00675 iterator 00676 lower_bound(const key_type& __x); 00677 00678 const_iterator 00679 lower_bound(const key_type& __x) const; 00680 00681 iterator 00682 upper_bound(const key_type& __x); 00683 00684 const_iterator 00685 upper_bound(const key_type& __x) const; 00686 00687 pair<iterator,iterator> 00688 equal_range(const key_type& __x); 00689 00690 pair<const_iterator, const_iterator> 00691 equal_range(const key_type& __x) const; 00692 00693 // Debugging. 00694 bool 00695 __rb_verify() const; 00696 }; 00697 00698 template<typename _Key, typename _Val, typename _KeyOfValue, 00699 typename _Compare, typename _Alloc> 00700 inline bool 00701 operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00702 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00703 { 00704 return __x.size() == __y.size() 00705 && equal(__x.begin(), __x.end(), __y.begin()); 00706 } 00707 00708 template<typename _Key, typename _Val, typename _KeyOfValue, 00709 typename _Compare, typename _Alloc> 00710 inline bool 00711 operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00712 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00713 { 00714 return lexicographical_compare(__x.begin(), __x.end(), 00715 __y.begin(), __y.end()); 00716 } 00717 00718 template<typename _Key, typename _Val, typename _KeyOfValue, 00719 typename _Compare, typename _Alloc> 00720 inline bool 00721 operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00722 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00723 { return !(__x == __y); } 00724 00725 template<typename _Key, typename _Val, typename _KeyOfValue, 00726 typename _Compare, typename _Alloc> 00727 inline bool 00728 operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00729 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00730 { return __y < __x; } 00731 00732 template<typename _Key, typename _Val, typename _KeyOfValue, 00733 typename _Compare, typename _Alloc> 00734 inline bool 00735 operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00736 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00737 { return !(__y < __x); } 00738 00739 template<typename _Key, typename _Val, typename _KeyOfValue, 00740 typename _Compare, typename _Alloc> 00741 inline bool 00742 operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00743 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00744 { return !(__x < __y); } 00745 00746 template<typename _Key, typename _Val, typename _KeyOfValue, 00747 typename _Compare, typename _Alloc> 00748 inline void 00749 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x, 00750 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y) 00751 { __x.swap(__y); } 00752 00753 template<typename _Key, typename _Val, typename _KeyOfValue, 00754 typename _Compare, typename _Alloc> 00755 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& 00756 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 00757 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x) 00758 { 00759 if (this != &__x) 00760 { 00761 // Note that _Key may be a constant type. 00762 clear(); 00763 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 00764 if (__x._M_root() != 0) 00765 { 00766 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00767 _M_leftmost() = _S_minimum(_M_root()); 00768 _M_rightmost() = _S_maximum(_M_root()); 00769 _M_impl._M_node_count = __x._M_impl._M_node_count; 00770 } 00771 } 00772 return *this; 00773 } 00774 00775 template<typename _Key, typename _Val, typename _KeyOfValue, 00776 typename _Compare, typename _Alloc> 00777 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 00778 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 00779 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 00780 { 00781 _Link_type __z = _M_create_node(__v); 00782 bool __insert_left; 00783 00784 __insert_left = __x != 0 || __p == _M_end() 00785 || _M_impl._M_key_compare(_KeyOfValue()(__v), 00786 _S_key(__p)); 00787 00788 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 00789 this->_M_impl._M_header); 00790 ++_M_impl._M_node_count; 00791 return iterator(__z); 00792 } 00793 00794 template<typename _Key, typename _Val, typename _KeyOfValue, 00795 typename _Compare, typename _Alloc> 00796 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 00797 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 00798 insert_equal(const _Val& __v) 00799 { 00800 _Link_type __x = _M_begin(); 00801 _Link_type __y = _M_end(); 00802 while (__x != 0) 00803 { 00804 __y = __x; 00805 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 00806 _S_left(__x) : _S_right(__x); 00807 } 00808 return _M_insert(__x, __y, __v); 00809 } 00810 00811 template<typename _Key, typename _Val, typename _KeyOfValue, 00812 typename _Compare, typename _Alloc> 00813 void 00814 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 00815 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 00816 { 00817 if (_M_root() == 0) 00818 { 00819 if (__t._M_root() != 0) 00820 { 00821 _M_root() = __t._M_root(); 00822 _M_leftmost() = __t._M_leftmost(); 00823 _M_rightmost() = __t._M_rightmost(); 00824 _M_root()->_M_parent = _M_end(); 00825 00826 __t._M_root() = 0; 00827 __t._M_leftmost() = __t._M_end(); 00828 __t._M_rightmost() = __t._M_end(); 00829 } 00830 } 00831 else if (__t._M_root() == 0) 00832 { 00833 __t._M_root() = _M_root(); 00834 __t._M_leftmost() = _M_leftmost(); 00835 __t._M_rightmost() = _M_rightmost(); 00836 __t._M_root()->_M_parent = __t._M_end(); 00837 00838 _M_root() = 0; 00839 _M_leftmost() = _M_end(); 00840 _M_rightmost() = _M_end(); 00841 } 00842 else 00843 { 00844 std::swap(_M_root(),__t._M_root()); 00845 std::swap(_M_leftmost(),__t._M_leftmost()); 00846 std::swap(_M_rightmost(),__t._M_rightmost()); 00847 00848 _M_root()->_M_parent = _M_end(); 00849 __t._M_root()->_M_parent = __t._M_end(); 00850 } 00851 // No need to swap header's color as it does not change. 00852 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 00853 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 00854 } 00855 00856 template<typename _Key, typename _Val, typename _KeyOfValue, 00857 typename _Compare, typename _Alloc> 00858 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 00859 bool> 00860 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 00861 insert_unique(const _Val& __v) 00862 { 00863 _Link_type __x = _M_begin(); 00864 _Link_type __y = _M_end(); 00865 bool __comp = true; 00866 while (__x != 0) 00867 { 00868 __y = __x; 00869 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); 00870 __x = __comp ? _S_left(__x) : _S_right(__x); 00871 } 00872 iterator __j = iterator(__y); 00873 if (__comp) 00874 if (__j == begin()) 00875 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 00876 else 00877 --__j; 00878 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) 00879 return pair<iterator,bool>(_M_insert(__x, __y, __v), true); 00880 return pair<iterator,bool>(__j, false); 00881 } 00882 00883 template<typename _Key, typename _Val, typename _KeyOfValue, 00884 typename _Compare, typename _Alloc> 00885 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 00886 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00887 insert_unique(iterator __position, const _Val& __v) 00888 { 00889 if (__position._M_node == _M_leftmost()) 00890 { 00891 // begin() 00892 if (size() > 0 00893 && _M_impl._M_key_compare(_KeyOfValue()(__v), 00894 _S_key(__position._M_node))) 00895 return _M_insert(__position._M_node, __position._M_node, __v); 00896 // First argument just needs to be non-null. 00897 else 00898 return insert_unique(__v).first; 00899 } 00900 else if (__position._M_node == _M_end()) 00901 { 00902 // end() 00903 if (_M_impl._M_key_compare(_S_key(_M_rightmost()), 00904 _KeyOfValue()(__v))) 00905 return _M_insert(0, _M_rightmost(), __v); 00906 else 00907 return insert_unique(__v).first; 00908 } 00909 else 00910 { 00911 iterator __before = __position; 00912 --__before; 00913 if (_M_impl._M_key_compare(_S_key(__before._M_node), 00914 _KeyOfValue()(__v)) 00915 && _M_impl._M_key_compare(_KeyOfValue()(__v), 00916 _S_key(__position._M_node))) 00917 { 00918 if (_S_right(__before._M_node) == 0) 00919 return _M_insert(0, __before._M_node, __v); 00920 else 00921 return _M_insert(__position._M_node, __position._M_node, __v); 00922 // First argument just needs to be non-null. 00923 } 00924 else 00925 return insert_unique(__v).first; 00926 } 00927 } 00928 00929 template<typename _Key, typename _Val, typename _KeyOfValue, 00930 typename _Compare, typename _Alloc> 00931 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 00932 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 00933 insert_equal(iterator __position, const _Val& __v) 00934 { 00935 if (__position._M_node == _M_leftmost()) 00936 { 00937 // begin() 00938 if (size() > 0 00939 && !_M_impl._M_key_compare(_S_key(__position._M_node), 00940 _KeyOfValue()(__v))) 00941 return _M_insert(__position._M_node, __position._M_node, __v); 00942 // first argument just needs to be non-null 00943 else 00944 return insert_equal(__v); 00945 } 00946 else if (__position._M_node == _M_end()) 00947 { 00948 // end() 00949 if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 00950 _S_key(_M_rightmost()))) 00951 return _M_insert(0, _M_rightmost(), __v); 00952 else 00953 return insert_equal(__v); 00954 } 00955 else 00956 { 00957 iterator __before = __position; 00958 --__before; 00959 if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 00960 _S_key(__before._M_node)) 00961 && !_M_impl._M_key_compare(_S_key(__position._M_node), 00962 _KeyOfValue()(__v))) 00963 { 00964 if (_S_right(__before._M_node) == 0) 00965 return _M_insert(0, __before._M_node, __v); 00966 else 00967 return _M_insert(__position._M_node, __position._M_node, __v); 00968 // First argument just needs to be non-null. 00969 } 00970 else 00971 return insert_equal(__v); 00972 } 00973 } 00974 00975 template<typename _Key, typename _Val, typename _KoV, 00976 typename _Cmp, typename _Alloc> 00977 template<class _II> 00978 void 00979 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 00980 insert_equal(_II __first, _II __last) 00981 { 00982 for ( ; __first != __last; ++__first) 00983 insert_equal(*__first); 00984 } 00985 00986 template<typename _Key, typename _Val, typename _KoV, 00987 typename _Cmp, typename _Alloc> 00988 template<class _II> 00989 void 00990 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>:: 00991 insert_unique(_II __first, _II __last) 00992 { 00993 for ( ; __first != __last; ++__first) 00994 insert_unique(*__first); 00995 } 00996 00997 template<typename _Key, typename _Val, typename _KeyOfValue, 00998 typename _Compare, typename _Alloc> 00999 inline void 01000 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) 01001 { 01002 _Link_type __y = 01003 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node, 01004 this->_M_impl._M_header)); 01005 destroy_node(__y); 01006 --_M_impl._M_node_count; 01007 } 01008 01009 template<typename _Key, typename _Val, typename _KeyOfValue, 01010 typename _Compare, typename _Alloc> 01011 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 01012 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) 01013 { 01014 pair<iterator,iterator> __p = equal_range(__x); 01015 size_type __n = std::distance(__p.first, __p.second); 01016 erase(__p.first, __p.second); 01017 return __n; 01018 } 01019 01020 template<typename _Key, typename _Val, typename _KoV, 01021 typename _Compare, typename _Alloc> 01022 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01023 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: 01024 _M_copy(_Const_Link_type __x, _Link_type __p) 01025 { 01026 // Structural copy. __x and __p must be non-null. 01027 _Link_type __top = _M_clone_node(__x); 01028 __top->_M_parent = __p; 01029 01030 try 01031 { 01032 if (__x->_M_right) 01033 __top->_M_right = _M_copy(_S_right(__x), __top); 01034 __p = __top; 01035 __x = _S_left(__x); 01036 01037 while (__x != 0) 01038 { 01039 _Link_type __y = _M_clone_node(__x); 01040 __p->_M_left = __y; 01041 __y->_M_parent = __p; 01042 if (__x->_M_right) 01043 __y->_M_right = _M_copy(_S_right(__x), __y); 01044 __p = __y; 01045 __x = _S_left(__x); 01046 } 01047 } 01048 catch(...) 01049 { 01050 _M_erase(__top); 01051 __throw_exception_again; 01052 } 01053 return __top; 01054 } 01055 01056 template<typename _Key, typename _Val, typename _KeyOfValue, 01057 typename _Compare, typename _Alloc> 01058 void 01059 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_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 destroy_node(__x); 01067 __x = __y; 01068 } 01069 } 01070 01071 template<typename _Key, typename _Val, typename _KeyOfValue, 01072 typename _Compare, typename _Alloc> 01073 void 01074 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01075 erase(iterator __first, iterator __last) 01076 { 01077 if (__first == begin() && __last == end()) 01078 clear(); 01079 else 01080 while (__first != __last) erase(__first++); 01081 } 01082 01083 template<typename _Key, typename _Val, typename _KeyOfValue, 01084 typename _Compare, typename _Alloc> 01085 void 01086 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01087 erase(const _Key* __first, const _Key* __last) 01088 { 01089 while (__first != __last) 01090 erase(*__first++); 01091 } 01092 01093 template<typename _Key, typename _Val, typename _KeyOfValue, 01094 typename _Compare, typename _Alloc> 01095 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 01096 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) 01097 { 01098 _Link_type __x = _M_begin(); // Current node. 01099 _Link_type __y = _M_end(); // Last node which is not less than __k. 01100 01101 while (__x != 0) 01102 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01103 __y = __x, __x = _S_left(__x); 01104 else 01105 __x = _S_right(__x); 01106 01107 iterator __j = iterator(__y); 01108 return (__j == end() 01109 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 01110 } 01111 01112 template<typename _Key, typename _Val, typename _KeyOfValue, 01113 typename _Compare, typename _Alloc> 01114 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 01115 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01116 find(const _Key& __k) const 01117 { 01118 _Const_Link_type __x = _M_begin(); // Current node. 01119 _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 01120 01121 while (__x != 0) 01122 { 01123 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01124 __y = __x, __x = _S_left(__x); 01125 else 01126 __x = _S_right(__x); 01127 } 01128 const_iterator __j = const_iterator(__y); 01129 return (__j == end() 01130 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j; 01131 } 01132 01133 template<typename _Key, typename _Val, typename _KeyOfValue, 01134 typename _Compare, typename _Alloc> 01135 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type 01136 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01137 count(const _Key& __k) const 01138 { 01139 pair<const_iterator, const_iterator> __p = equal_range(__k); 01140 const size_type __n = std::distance(__p.first, __p.second); 01141 return __n; 01142 } 01143 01144 template<typename _Key, typename _Val, typename _KeyOfValue, 01145 typename _Compare, typename _Alloc> 01146 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 01147 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01148 lower_bound(const _Key& __k) 01149 { 01150 _Link_type __x = _M_begin(); // Current node. 01151 _Link_type __y = _M_end(); // Last node which is not less than __k. 01152 01153 while (__x != 0) 01154 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01155 __y = __x, __x = _S_left(__x); 01156 else 01157 __x = _S_right(__x); 01158 01159 return iterator(__y); 01160 } 01161 01162 template<typename _Key, typename _Val, typename _KeyOfValue, 01163 typename _Compare, typename _Alloc> 01164 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 01165 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01166 lower_bound(const _Key& __k) const 01167 { 01168 _Const_Link_type __x = _M_begin(); // Current node. 01169 _Const_Link_type __y = _M_end(); // Last node which is not less than __k. 01170 01171 while (__x != 0) 01172 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01173 __y = __x, __x = _S_left(__x); 01174 else 01175 __x = _S_right(__x); 01176 01177 return const_iterator(__y); 01178 } 01179 01180 template<typename _Key, typename _Val, typename _KeyOfValue, 01181 typename _Compare, typename _Alloc> 01182 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 01183 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01184 upper_bound(const _Key& __k) 01185 { 01186 _Link_type __x = _M_begin(); // Current node. 01187 _Link_type __y = _M_end(); // Last node which is greater than __k. 01188 01189 while (__x != 0) 01190 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01191 __y = __x, __x = _S_left(__x); 01192 else 01193 __x = _S_right(__x); 01194 01195 return iterator(__y); 01196 } 01197 01198 template<typename _Key, typename _Val, typename _KeyOfValue, 01199 typename _Compare, typename _Alloc> 01200 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator 01201 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01202 upper_bound(const _Key& __k) const 01203 { 01204 _Const_Link_type __x = _M_begin(); // Current node. 01205 _Const_Link_type __y = _M_end(); // Last node which is greater than __k. 01206 01207 while (__x != 0) 01208 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01209 __y = __x, __x = _S_left(__x); 01210 else 01211 __x = _S_right(__x); 01212 01213 return const_iterator(__y); 01214 } 01215 01216 template<typename _Key, typename _Val, typename _KeyOfValue, 01217 typename _Compare, typename _Alloc> 01218 inline 01219 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue, 01220 _Compare,_Alloc>::iterator, 01221 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator> 01222 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: 01223 equal_range(const _Key& __k) 01224 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); } 01225 01226 template<typename _Key, typename _Val, typename _KoV, 01227 typename _Compare, typename _Alloc> 01228 inline 01229 pair<typename _Rb_tree<_Key, _Val, _KoV, 01230 _Compare, _Alloc>::const_iterator, 01231 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> 01232 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01233 equal_range(const _Key& __k) const 01234 { return pair<const_iterator, const_iterator>(lower_bound(__k), 01235 upper_bound(__k)); } 01236 01237 unsigned int 01238 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 01239 const _Rb_tree_node_base* __root); 01240 01241 template<typename _Key, typename _Val, typename _KeyOfValue, 01242 typename _Compare, typename _Alloc> 01243 bool 01244 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 01245 { 01246 if (_M_impl._M_node_count == 0 || begin() == end()) 01247 return _M_impl._M_node_count == 0 && begin() == end() 01248 && this->_M_impl._M_header._M_left == _M_end() 01249 && this->_M_impl._M_header._M_right == _M_end(); 01250 01251 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 01252 for (const_iterator __it = begin(); __it != end(); ++__it) 01253 { 01254 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 01255 _Const_Link_type __L = _S_left(__x); 01256 _Const_Link_type __R = _S_right(__x); 01257 01258 if (__x->_M_color == _S_red) 01259 if ((__L && __L->_M_color == _S_red) 01260 || (__R && __R->_M_color == _S_red)) 01261 return false; 01262 01263 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 01264 return false; 01265 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 01266 return false; 01267 01268 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 01269 return false; 01270 } 01271 01272 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 01273 return false; 01274 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 01275 return false; 01276 return true; 01277 } 01278 } // namespace std 01279 01280 #endif 01281

Generated on Tue Sep 7 10:05:21 2004 for libstdc++-v3 Source by doxygen 1.3.8