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 _GLIBCXX_ABI_TAG_CXX11 00804 iterator 00805 erase(const_iterator __position) 00806 { 00807 const_iterator __result = __position; 00808 ++__result; 00809 _M_erase_aux(__position); 00810 return __result._M_const_cast(); 00811 } 00812 00813 // LWG 2059. 00814 _GLIBCXX_ABI_TAG_CXX11 00815 iterator 00816 erase(iterator __position) 00817 { 00818 iterator __result = __position; 00819 ++__result; 00820 _M_erase_aux(__position); 00821 return __result; 00822 } 00823 #else 00824 void 00825 erase(iterator __position) 00826 { _M_erase_aux(__position); } 00827 00828 void 00829 erase(const_iterator __position) 00830 { _M_erase_aux(__position); } 00831 #endif 00832 size_type 00833 erase(const key_type& __x); 00834 00835 #if __cplusplus >= 201103L 00836 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00837 // DR 130. Associative erase should return an iterator. 00838 _GLIBCXX_ABI_TAG_CXX11 00839 iterator 00840 erase(const_iterator __first, const_iterator __last) 00841 { 00842 _M_erase_aux(__first, __last); 00843 return __last._M_const_cast(); 00844 } 00845 #else 00846 void 00847 erase(iterator __first, iterator __last) 00848 { _M_erase_aux(__first, __last); } 00849 00850 void 00851 erase(const_iterator __first, const_iterator __last) 00852 { _M_erase_aux(__first, __last); } 00853 #endif 00854 void 00855 erase(const key_type* __first, const key_type* __last); 00856 00857 void 00858 clear() _GLIBCXX_NOEXCEPT 00859 { 00860 _M_erase(_M_begin()); 00861 _M_leftmost() = _M_end(); 00862 _M_root() = 0; 00863 _M_rightmost() = _M_end(); 00864 _M_impl._M_node_count = 0; 00865 } 00866 00867 // Set operations. 00868 iterator 00869 find(const key_type& __k); 00870 00871 const_iterator 00872 find(const key_type& __k) const; 00873 00874 size_type 00875 count(const key_type& __k) const; 00876 00877 iterator 00878 lower_bound(const key_type& __k) 00879 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 00880 00881 const_iterator 00882 lower_bound(const key_type& __k) const 00883 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 00884 00885 iterator 00886 upper_bound(const key_type& __k) 00887 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 00888 00889 const_iterator 00890 upper_bound(const key_type& __k) const 00891 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 00892 00893 pair<iterator, iterator> 00894 equal_range(const key_type& __k); 00895 00896 pair<const_iterator, const_iterator> 00897 equal_range(const key_type& __k) const; 00898 00899 // Debugging. 00900 bool 00901 __rb_verify() const; 00902 }; 00903 00904 template<typename _Key, typename _Val, typename _KeyOfValue, 00905 typename _Compare, typename _Alloc> 00906 inline bool 00907 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00908 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00909 { 00910 return __x.size() == __y.size() 00911 && std::equal(__x.begin(), __x.end(), __y.begin()); 00912 } 00913 00914 template<typename _Key, typename _Val, typename _KeyOfValue, 00915 typename _Compare, typename _Alloc> 00916 inline bool 00917 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00918 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00919 { 00920 return std::lexicographical_compare(__x.begin(), __x.end(), 00921 __y.begin(), __y.end()); 00922 } 00923 00924 template<typename _Key, typename _Val, typename _KeyOfValue, 00925 typename _Compare, typename _Alloc> 00926 inline bool 00927 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00928 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00929 { return !(__x == __y); } 00930 00931 template<typename _Key, typename _Val, typename _KeyOfValue, 00932 typename _Compare, typename _Alloc> 00933 inline bool 00934 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00935 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00936 { return __y < __x; } 00937 00938 template<typename _Key, typename _Val, typename _KeyOfValue, 00939 typename _Compare, typename _Alloc> 00940 inline bool 00941 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00942 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00943 { return !(__y < __x); } 00944 00945 template<typename _Key, typename _Val, typename _KeyOfValue, 00946 typename _Compare, typename _Alloc> 00947 inline bool 00948 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00949 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00950 { return !(__x < __y); } 00951 00952 template<typename _Key, typename _Val, typename _KeyOfValue, 00953 typename _Compare, typename _Alloc> 00954 inline void 00955 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 00956 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 00957 { __x.swap(__y); } 00958 00959 #if __cplusplus >= 201103L 00960 template<typename _Key, typename _Val, typename _KeyOfValue, 00961 typename _Compare, typename _Alloc> 00962 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00963 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) 00964 : _M_impl(__x._M_impl._M_key_compare, 00965 std::move(__x._M_get_Node_allocator())) 00966 { 00967 if (__x._M_root() != 0) 00968 { 00969 _M_root() = __x._M_root(); 00970 _M_leftmost() = __x._M_leftmost(); 00971 _M_rightmost() = __x._M_rightmost(); 00972 _M_root()->_M_parent = _M_end(); 00973 00974 __x._M_root() = 0; 00975 __x._M_leftmost() = __x._M_end(); 00976 __x._M_rightmost() = __x._M_end(); 00977 00978 this->_M_impl._M_node_count = __x._M_impl._M_node_count; 00979 __x._M_impl._M_node_count = 0; 00980 } 00981 } 00982 #endif 00983 00984 template<typename _Key, typename _Val, typename _KeyOfValue, 00985 typename _Compare, typename _Alloc> 00986 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 00987 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 00988 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) 00989 { 00990 if (this != &__x) 00991 { 00992 // Note that _Key may be a constant type. 00993 clear(); 00994 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 00995 if (__x._M_root() != 0) 00996 { 00997 _M_root() = _M_copy(__x._M_begin(), _M_end()); 00998 _M_leftmost() = _S_minimum(_M_root()); 00999 _M_rightmost() = _S_maximum(_M_root()); 01000 _M_impl._M_node_count = __x._M_impl._M_node_count; 01001 } 01002 } 01003 return *this; 01004 } 01005 01006 template<typename _Key, typename _Val, typename _KeyOfValue, 01007 typename _Compare, typename _Alloc> 01008 #if __cplusplus >= 201103L 01009 template<typename _Arg> 01010 #endif 01011 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01012 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01013 #if __cplusplus >= 201103L 01014 _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) 01015 #else 01016 _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) 01017 #endif 01018 { 01019 bool __insert_left = (__x != 0 || __p == _M_end() 01020 || _M_impl._M_key_compare(_KeyOfValue()(__v), 01021 _S_key(__p))); 01022 01023 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01024 01025 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01026 this->_M_impl._M_header); 01027 ++_M_impl._M_node_count; 01028 return iterator(__z); 01029 } 01030 01031 template<typename _Key, typename _Val, typename _KeyOfValue, 01032 typename _Compare, typename _Alloc> 01033 #if __cplusplus >= 201103L 01034 template<typename _Arg> 01035 #endif 01036 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01037 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01038 #if __cplusplus >= 201103L 01039 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 01040 #else 01041 _M_insert_lower(_Base_ptr __p, const _Val& __v) 01042 #endif 01043 { 01044 bool __insert_left = (__p == _M_end() 01045 || !_M_impl._M_key_compare(_S_key(__p), 01046 _KeyOfValue()(__v))); 01047 01048 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01049 01050 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01051 this->_M_impl._M_header); 01052 ++_M_impl._M_node_count; 01053 return iterator(__z); 01054 } 01055 01056 template<typename _Key, typename _Val, typename _KeyOfValue, 01057 typename _Compare, typename _Alloc> 01058 #if __cplusplus >= 201103L 01059 template<typename _Arg> 01060 #endif 01061 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01062 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01063 #if __cplusplus >= 201103L 01064 _M_insert_equal_lower(_Arg&& __v) 01065 #else 01066 _M_insert_equal_lower(const _Val& __v) 01067 #endif 01068 { 01069 _Link_type __x = _M_begin(); 01070 _Link_type __y = _M_end(); 01071 while (__x != 0) 01072 { 01073 __y = __x; 01074 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 01075 _S_left(__x) : _S_right(__x); 01076 } 01077 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 01078 } 01079 01080 template<typename _Key, typename _Val, typename _KoV, 01081 typename _Compare, typename _Alloc> 01082 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01083 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01084 _M_copy(_Const_Link_type __x, _Link_type __p) 01085 { 01086 // Structural copy. __x and __p must be non-null. 01087 _Link_type __top = _M_clone_node(__x); 01088 __top->_M_parent = __p; 01089 01090 __try 01091 { 01092 if (__x->_M_right) 01093 __top->_M_right = _M_copy(_S_right(__x), __top); 01094 __p = __top; 01095 __x = _S_left(__x); 01096 01097 while (__x != 0) 01098 { 01099 _Link_type __y = _M_clone_node(__x); 01100 __p->_M_left = __y; 01101 __y->_M_parent = __p; 01102 if (__x->_M_right) 01103 __y->_M_right = _M_copy(_S_right(__x), __y); 01104 __p = __y; 01105 __x = _S_left(__x); 01106 } 01107 } 01108 __catch(...) 01109 { 01110 _M_erase(__top); 01111 __throw_exception_again; 01112 } 01113 return __top; 01114 } 01115 01116 template<typename _Key, typename _Val, typename _KeyOfValue, 01117 typename _Compare, typename _Alloc> 01118 void 01119 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01120 _M_erase(_Link_type __x) 01121 { 01122 // Erase without rebalancing. 01123 while (__x != 0) 01124 { 01125 _M_erase(_S_right(__x)); 01126 _Link_type __y = _S_left(__x); 01127 _M_destroy_node(__x); 01128 __x = __y; 01129 } 01130 } 01131 01132 template<typename _Key, typename _Val, typename _KeyOfValue, 01133 typename _Compare, typename _Alloc> 01134 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01135 _Compare, _Alloc>::iterator 01136 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01137 _M_lower_bound(_Link_type __x, _Link_type __y, 01138 const _Key& __k) 01139 { 01140 while (__x != 0) 01141 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01142 __y = __x, __x = _S_left(__x); 01143 else 01144 __x = _S_right(__x); 01145 return iterator(__y); 01146 } 01147 01148 template<typename _Key, typename _Val, typename _KeyOfValue, 01149 typename _Compare, typename _Alloc> 01150 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01151 _Compare, _Alloc>::const_iterator 01152 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01153 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, 01154 const _Key& __k) const 01155 { 01156 while (__x != 0) 01157 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01158 __y = __x, __x = _S_left(__x); 01159 else 01160 __x = _S_right(__x); 01161 return const_iterator(__y); 01162 } 01163 01164 template<typename _Key, typename _Val, typename _KeyOfValue, 01165 typename _Compare, typename _Alloc> 01166 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01167 _Compare, _Alloc>::iterator 01168 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01169 _M_upper_bound(_Link_type __x, _Link_type __y, 01170 const _Key& __k) 01171 { 01172 while (__x != 0) 01173 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01174 __y = __x, __x = _S_left(__x); 01175 else 01176 __x = _S_right(__x); 01177 return iterator(__y); 01178 } 01179 01180 template<typename _Key, typename _Val, typename _KeyOfValue, 01181 typename _Compare, typename _Alloc> 01182 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01183 _Compare, _Alloc>::const_iterator 01184 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01185 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, 01186 const _Key& __k) const 01187 { 01188 while (__x != 0) 01189 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01190 __y = __x, __x = _S_left(__x); 01191 else 01192 __x = _S_right(__x); 01193 return const_iterator(__y); 01194 } 01195 01196 template<typename _Key, typename _Val, typename _KeyOfValue, 01197 typename _Compare, typename _Alloc> 01198 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01199 _Compare, _Alloc>::iterator, 01200 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01201 _Compare, _Alloc>::iterator> 01202 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01203 equal_range(const _Key& __k) 01204 { 01205 _Link_type __x = _M_begin(); 01206 _Link_type __y = _M_end(); 01207 while (__x != 0) 01208 { 01209 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01210 __x = _S_right(__x); 01211 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01212 __y = __x, __x = _S_left(__x); 01213 else 01214 { 01215 _Link_type __xu(__x), __yu(__y); 01216 __y = __x, __x = _S_left(__x); 01217 __xu = _S_right(__xu); 01218 return pair<iterator, 01219 iterator>(_M_lower_bound(__x, __y, __k), 01220 _M_upper_bound(__xu, __yu, __k)); 01221 } 01222 } 01223 return pair<iterator, iterator>(iterator(__y), 01224 iterator(__y)); 01225 } 01226 01227 template<typename _Key, typename _Val, typename _KeyOfValue, 01228 typename _Compare, typename _Alloc> 01229 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01230 _Compare, _Alloc>::const_iterator, 01231 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01232 _Compare, _Alloc>::const_iterator> 01233 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01234 equal_range(const _Key& __k) const 01235 { 01236 _Const_Link_type __x = _M_begin(); 01237 _Const_Link_type __y = _M_end(); 01238 while (__x != 0) 01239 { 01240 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01241 __x = _S_right(__x); 01242 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 01243 __y = __x, __x = _S_left(__x); 01244 else 01245 { 01246 _Const_Link_type __xu(__x), __yu(__y); 01247 __y = __x, __x = _S_left(__x); 01248 __xu = _S_right(__xu); 01249 return pair<const_iterator, 01250 const_iterator>(_M_lower_bound(__x, __y, __k), 01251 _M_upper_bound(__xu, __yu, __k)); 01252 } 01253 } 01254 return pair<const_iterator, const_iterator>(const_iterator(__y), 01255 const_iterator(__y)); 01256 } 01257 01258 template<typename _Key, typename _Val, typename _KeyOfValue, 01259 typename _Compare, typename _Alloc> 01260 void 01261 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01262 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) 01263 { 01264 if (_M_root() == 0) 01265 { 01266 if (__t._M_root() != 0) 01267 { 01268 _M_root() = __t._M_root(); 01269 _M_leftmost() = __t._M_leftmost(); 01270 _M_rightmost() = __t._M_rightmost(); 01271 _M_root()->_M_parent = _M_end(); 01272 01273 __t._M_root() = 0; 01274 __t._M_leftmost() = __t._M_end(); 01275 __t._M_rightmost() = __t._M_end(); 01276 } 01277 } 01278 else if (__t._M_root() == 0) 01279 { 01280 __t._M_root() = _M_root(); 01281 __t._M_leftmost() = _M_leftmost(); 01282 __t._M_rightmost() = _M_rightmost(); 01283 __t._M_root()->_M_parent = __t._M_end(); 01284 01285 _M_root() = 0; 01286 _M_leftmost() = _M_end(); 01287 _M_rightmost() = _M_end(); 01288 } 01289 else 01290 { 01291 std::swap(_M_root(),__t._M_root()); 01292 std::swap(_M_leftmost(),__t._M_leftmost()); 01293 std::swap(_M_rightmost(),__t._M_rightmost()); 01294 01295 _M_root()->_M_parent = _M_end(); 01296 __t._M_root()->_M_parent = __t._M_end(); 01297 } 01298 // No need to swap header's color as it does not change. 01299 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 01300 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 01301 01302 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01303 // 431. Swapping containers with unequal allocators. 01304 std::__alloc_swap<_Node_allocator>:: 01305 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); 01306 } 01307 01308 template<typename _Key, typename _Val, typename _KeyOfValue, 01309 typename _Compare, typename _Alloc> 01310 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01311 _Compare, _Alloc>::_Base_ptr, 01312 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01313 _Compare, _Alloc>::_Base_ptr> 01314 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01315 _M_get_insert_unique_pos(const key_type& __k) 01316 { 01317 typedef pair<_Base_ptr, _Base_ptr> _Res; 01318 _Link_type __x = _M_begin(); 01319 _Link_type __y = _M_end(); 01320 bool __comp = true; 01321 while (__x != 0) 01322 { 01323 __y = __x; 01324 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 01325 __x = __comp ? _S_left(__x) : _S_right(__x); 01326 } 01327 iterator __j = iterator(__y); 01328 if (__comp) 01329 { 01330 if (__j == begin()) 01331 return _Res(__x, __y); 01332 else 01333 --__j; 01334 } 01335 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 01336 return _Res(__x, __y); 01337 return _Res(__j._M_node, 0); 01338 } 01339 01340 template<typename _Key, typename _Val, typename _KeyOfValue, 01341 typename _Compare, typename _Alloc> 01342 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01343 _Compare, _Alloc>::_Base_ptr, 01344 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01345 _Compare, _Alloc>::_Base_ptr> 01346 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01347 _M_get_insert_equal_pos(const key_type& __k) 01348 { 01349 typedef pair<_Base_ptr, _Base_ptr> _Res; 01350 _Link_type __x = _M_begin(); 01351 _Link_type __y = _M_end(); 01352 while (__x != 0) 01353 { 01354 __y = __x; 01355 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 01356 _S_left(__x) : _S_right(__x); 01357 } 01358 return _Res(__x, __y); 01359 } 01360 01361 template<typename _Key, typename _Val, typename _KeyOfValue, 01362 typename _Compare, typename _Alloc> 01363 #if __cplusplus >= 201103L 01364 template<typename _Arg> 01365 #endif 01366 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01367 _Compare, _Alloc>::iterator, bool> 01368 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01369 #if __cplusplus >= 201103L 01370 _M_insert_unique(_Arg&& __v) 01371 #else 01372 _M_insert_unique(const _Val& __v) 01373 #endif 01374 { 01375 typedef pair<iterator, bool> _Res; 01376 pair<_Base_ptr, _Base_ptr> __res 01377 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 01378 01379 if (__res.second) 01380 return _Res(_M_insert_(__res.first, __res.second, 01381 _GLIBCXX_FORWARD(_Arg, __v)), 01382 true); 01383 01384 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 01385 } 01386 01387 template<typename _Key, typename _Val, typename _KeyOfValue, 01388 typename _Compare, typename _Alloc> 01389 #if __cplusplus >= 201103L 01390 template<typename _Arg> 01391 #endif 01392 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01393 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01394 #if __cplusplus >= 201103L 01395 _M_insert_equal(_Arg&& __v) 01396 #else 01397 _M_insert_equal(const _Val& __v) 01398 #endif 01399 { 01400 pair<_Base_ptr, _Base_ptr> __res 01401 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 01402 return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); 01403 } 01404 01405 template<typename _Key, typename _Val, typename _KeyOfValue, 01406 typename _Compare, typename _Alloc> 01407 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01408 _Compare, _Alloc>::_Base_ptr, 01409 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01410 _Compare, _Alloc>::_Base_ptr> 01411 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01412 _M_get_insert_hint_unique_pos(const_iterator __position, 01413 const key_type& __k) 01414 { 01415 iterator __pos = __position._M_const_cast(); 01416 typedef pair<_Base_ptr, _Base_ptr> _Res; 01417 01418 // end() 01419 if (__pos._M_node == _M_end()) 01420 { 01421 if (size() > 0 01422 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 01423 return _Res(0, _M_rightmost()); 01424 else 01425 return _M_get_insert_unique_pos(__k); 01426 } 01427 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 01428 { 01429 // First, try before... 01430 iterator __before = __pos; 01431 if (__pos._M_node == _M_leftmost()) // begin() 01432 return _Res(_M_leftmost(), _M_leftmost()); 01433 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 01434 { 01435 if (_S_right(__before._M_node) == 0) 01436 return _Res(0, __before._M_node); 01437 else 01438 return _Res(__pos._M_node, __pos._M_node); 01439 } 01440 else 01441 return _M_get_insert_unique_pos(__k); 01442 } 01443 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 01444 { 01445 // ... then try after. 01446 iterator __after = __pos; 01447 if (__pos._M_node == _M_rightmost()) 01448 return _Res(0, _M_rightmost()); 01449 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 01450 { 01451 if (_S_right(__pos._M_node) == 0) 01452 return _Res(0, __pos._M_node); 01453 else 01454 return _Res(__after._M_node, __after._M_node); 01455 } 01456 else 01457 return _M_get_insert_unique_pos(__k); 01458 } 01459 else 01460 // Equivalent keys. 01461 return _Res(__pos._M_node, 0); 01462 } 01463 01464 template<typename _Key, typename _Val, typename _KeyOfValue, 01465 typename _Compare, typename _Alloc> 01466 #if __cplusplus >= 201103L 01467 template<typename _Arg> 01468 #endif 01469 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01470 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01471 #if __cplusplus >= 201103L 01472 _M_insert_unique_(const_iterator __position, _Arg&& __v) 01473 #else 01474 _M_insert_unique_(const_iterator __position, const _Val& __v) 01475 #endif 01476 { 01477 pair<_Base_ptr, _Base_ptr> __res 01478 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 01479 01480 if (__res.second) 01481 return _M_insert_(__res.first, __res.second, 01482 _GLIBCXX_FORWARD(_Arg, __v)); 01483 return iterator(static_cast<_Link_type>(__res.first)); 01484 } 01485 01486 template<typename _Key, typename _Val, typename _KeyOfValue, 01487 typename _Compare, typename _Alloc> 01488 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01489 _Compare, _Alloc>::_Base_ptr, 01490 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01491 _Compare, _Alloc>::_Base_ptr> 01492 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01493 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 01494 { 01495 iterator __pos = __position._M_const_cast(); 01496 typedef pair<_Base_ptr, _Base_ptr> _Res; 01497 01498 // end() 01499 if (__pos._M_node == _M_end()) 01500 { 01501 if (size() > 0 01502 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 01503 return _Res(0, _M_rightmost()); 01504 else 01505 return _M_get_insert_equal_pos(__k); 01506 } 01507 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 01508 { 01509 // First, try before... 01510 iterator __before = __pos; 01511 if (__pos._M_node == _M_leftmost()) // begin() 01512 return _Res(_M_leftmost(), _M_leftmost()); 01513 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 01514 { 01515 if (_S_right(__before._M_node) == 0) 01516 return _Res(0, __before._M_node); 01517 else 01518 return _Res(__pos._M_node, __pos._M_node); 01519 } 01520 else 01521 return _M_get_insert_equal_pos(__k); 01522 } 01523 else 01524 { 01525 // ... then try after. 01526 iterator __after = __pos; 01527 if (__pos._M_node == _M_rightmost()) 01528 return _Res(0, _M_rightmost()); 01529 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 01530 { 01531 if (_S_right(__pos._M_node) == 0) 01532 return _Res(0, __pos._M_node); 01533 else 01534 return _Res(__after._M_node, __after._M_node); 01535 } 01536 else 01537 return _Res(0, 0); 01538 } 01539 } 01540 01541 template<typename _Key, typename _Val, typename _KeyOfValue, 01542 typename _Compare, typename _Alloc> 01543 #if __cplusplus >= 201103L 01544 template<typename _Arg> 01545 #endif 01546 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01547 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01548 #if __cplusplus >= 201103L 01549 _M_insert_equal_(const_iterator __position, _Arg&& __v) 01550 #else 01551 _M_insert_equal_(const_iterator __position, const _Val& __v) 01552 #endif 01553 { 01554 pair<_Base_ptr, _Base_ptr> __res 01555 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 01556 01557 if (__res.second) 01558 return _M_insert_(__res.first, __res.second, 01559 _GLIBCXX_FORWARD(_Arg, __v)); 01560 01561 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 01562 } 01563 01564 #if __cplusplus >= 201103L 01565 template<typename _Key, typename _Val, typename _KeyOfValue, 01566 typename _Compare, typename _Alloc> 01567 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01568 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01569 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 01570 { 01571 bool __insert_left = (__x != 0 || __p == _M_end() 01572 || _M_impl._M_key_compare(_S_key(__z), 01573 _S_key(__p))); 01574 01575 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01576 this->_M_impl._M_header); 01577 ++_M_impl._M_node_count; 01578 return iterator(__z); 01579 } 01580 01581 template<typename _Key, typename _Val, typename _KeyOfValue, 01582 typename _Compare, typename _Alloc> 01583 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01584 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01585 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 01586 { 01587 bool __insert_left = (__p == _M_end() 01588 || !_M_impl._M_key_compare(_S_key(__p), 01589 _S_key(__z))); 01590 01591 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01592 this->_M_impl._M_header); 01593 ++_M_impl._M_node_count; 01594 return iterator(__z); 01595 } 01596 01597 template<typename _Key, typename _Val, typename _KeyOfValue, 01598 typename _Compare, typename _Alloc> 01599 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01600 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01601 _M_insert_equal_lower_node(_Link_type __z) 01602 { 01603 _Link_type __x = _M_begin(); 01604 _Link_type __y = _M_end(); 01605 while (__x != 0) 01606 { 01607 __y = __x; 01608 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 01609 _S_left(__x) : _S_right(__x); 01610 } 01611 return _M_insert_lower_node(__y, __z); 01612 } 01613 01614 template<typename _Key, typename _Val, typename _KeyOfValue, 01615 typename _Compare, typename _Alloc> 01616 template<typename... _Args> 01617 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01618 _Compare, _Alloc>::iterator, bool> 01619 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01620 _M_emplace_unique(_Args&&... __args) 01621 { 01622 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01623 01624 __try 01625 { 01626 typedef pair<iterator, bool> _Res; 01627 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 01628 if (__res.second) 01629 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 01630 01631 _M_destroy_node(__z); 01632 return _Res(iterator(static_cast<_Link_type>(__res.first)), false); 01633 } 01634 __catch(...) 01635 { 01636 _M_destroy_node(__z); 01637 __throw_exception_again; 01638 } 01639 } 01640 01641 template<typename _Key, typename _Val, typename _KeyOfValue, 01642 typename _Compare, typename _Alloc> 01643 template<typename... _Args> 01644 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01645 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01646 _M_emplace_equal(_Args&&... __args) 01647 { 01648 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01649 01650 __try 01651 { 01652 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 01653 return _M_insert_node(__res.first, __res.second, __z); 01654 } 01655 __catch(...) 01656 { 01657 _M_destroy_node(__z); 01658 __throw_exception_again; 01659 } 01660 } 01661 01662 template<typename _Key, typename _Val, typename _KeyOfValue, 01663 typename _Compare, typename _Alloc> 01664 template<typename... _Args> 01665 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01666 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01667 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 01668 { 01669 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01670 01671 __try 01672 { 01673 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 01674 01675 if (__res.second) 01676 return _M_insert_node(__res.first, __res.second, __z); 01677 01678 _M_destroy_node(__z); 01679 return iterator(static_cast<_Link_type>(__res.first)); 01680 } 01681 __catch(...) 01682 { 01683 _M_destroy_node(__z); 01684 __throw_exception_again; 01685 } 01686 } 01687 01688 template<typename _Key, typename _Val, typename _KeyOfValue, 01689 typename _Compare, typename _Alloc> 01690 template<typename... _Args> 01691 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01692 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01693 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 01694 { 01695 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 01696 01697 __try 01698 { 01699 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 01700 01701 if (__res.second) 01702 return _M_insert_node(__res.first, __res.second, __z); 01703 01704 return _M_insert_equal_lower_node(__z); 01705 } 01706 __catch(...) 01707 { 01708 _M_destroy_node(__z); 01709 __throw_exception_again; 01710 } 01711 } 01712 #endif 01713 01714 template<typename _Key, typename _Val, typename _KoV, 01715 typename _Cmp, typename _Alloc> 01716 template<class _II> 01717 void 01718 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 01719 _M_insert_unique(_II __first, _II __last) 01720 { 01721 for (; __first != __last; ++__first) 01722 _M_insert_unique_(end(), *__first); 01723 } 01724 01725 template<typename _Key, typename _Val, typename _KoV, 01726 typename _Cmp, typename _Alloc> 01727 template<class _II> 01728 void 01729 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 01730 _M_insert_equal(_II __first, _II __last) 01731 { 01732 for (; __first != __last; ++__first) 01733 _M_insert_equal_(end(), *__first); 01734 } 01735 01736 template<typename _Key, typename _Val, typename _KeyOfValue, 01737 typename _Compare, typename _Alloc> 01738 void 01739 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01740 _M_erase_aux(const_iterator __position) 01741 { 01742 _Link_type __y = 01743 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 01744 (const_cast<_Base_ptr>(__position._M_node), 01745 this->_M_impl._M_header)); 01746 _M_destroy_node(__y); 01747 --_M_impl._M_node_count; 01748 } 01749 01750 template<typename _Key, typename _Val, typename _KeyOfValue, 01751 typename _Compare, typename _Alloc> 01752 void 01753 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01754 _M_erase_aux(const_iterator __first, const_iterator __last) 01755 { 01756 if (__first == begin() && __last == end()) 01757 clear(); 01758 else 01759 while (__first != __last) 01760 erase(__first++); 01761 } 01762 01763 template<typename _Key, typename _Val, typename _KeyOfValue, 01764 typename _Compare, typename _Alloc> 01765 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 01766 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01767 erase(const _Key& __x) 01768 { 01769 pair<iterator, iterator> __p = equal_range(__x); 01770 const size_type __old_size = size(); 01771 erase(__p.first, __p.second); 01772 return __old_size - size(); 01773 } 01774 01775 template<typename _Key, typename _Val, typename _KeyOfValue, 01776 typename _Compare, typename _Alloc> 01777 void 01778 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01779 erase(const _Key* __first, const _Key* __last) 01780 { 01781 while (__first != __last) 01782 erase(*__first++); 01783 } 01784 01785 template<typename _Key, typename _Val, typename _KeyOfValue, 01786 typename _Compare, typename _Alloc> 01787 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01788 _Compare, _Alloc>::iterator 01789 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01790 find(const _Key& __k) 01791 { 01792 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 01793 return (__j == end() 01794 || _M_impl._M_key_compare(__k, 01795 _S_key(__j._M_node))) ? end() : __j; 01796 } 01797 01798 template<typename _Key, typename _Val, typename _KeyOfValue, 01799 typename _Compare, typename _Alloc> 01800 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01801 _Compare, _Alloc>::const_iterator 01802 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01803 find(const _Key& __k) const 01804 { 01805 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 01806 return (__j == end() 01807 || _M_impl._M_key_compare(__k, 01808 _S_key(__j._M_node))) ? end() : __j; 01809 } 01810 01811 template<typename _Key, typename _Val, typename _KeyOfValue, 01812 typename _Compare, typename _Alloc> 01813 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 01814 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01815 count(const _Key& __k) const 01816 { 01817 pair<const_iterator, const_iterator> __p = equal_range(__k); 01818 const size_type __n = std::distance(__p.first, __p.second); 01819 return __n; 01820 } 01821 01822 _GLIBCXX_PURE unsigned int 01823 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 01824 const _Rb_tree_node_base* __root) throw (); 01825 01826 template<typename _Key, typename _Val, typename _KeyOfValue, 01827 typename _Compare, typename _Alloc> 01828 bool 01829 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 01830 { 01831 if (_M_impl._M_node_count == 0 || begin() == end()) 01832 return _M_impl._M_node_count == 0 && begin() == end() 01833 && this->_M_impl._M_header._M_left == _M_end() 01834 && this->_M_impl._M_header._M_right == _M_end(); 01835 01836 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 01837 for (const_iterator __it = begin(); __it != end(); ++__it) 01838 { 01839 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 01840 _Const_Link_type __L = _S_left(__x); 01841 _Const_Link_type __R = _S_right(__x); 01842 01843 if (__x->_M_color == _S_red) 01844 if ((__L && __L->_M_color == _S_red) 01845 || (__R && __R->_M_color == _S_red)) 01846 return false; 01847 01848 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 01849 return false; 01850 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 01851 return false; 01852 01853 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 01854 return false; 01855 } 01856 01857 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 01858 return false; 01859 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 01860 return false; 01861 return true; 01862 } 01863 01864 _GLIBCXX_END_NAMESPACE_VERSION 01865 } // namespace 01866 01867 #endif