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