libstdc++
|
00001 // RB tree implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2019 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 #pragma GCC system_header 00062 00063 #include <bits/stl_algobase.h> 00064 #include <bits/allocator.h> 00065 #include <bits/stl_function.h> 00066 #include <bits/cpp_type_traits.h> 00067 #include <ext/alloc_traits.h> 00068 #if __cplusplus >= 201103L 00069 # include <ext/aligned_buffer.h> 00070 #endif 00071 #if __cplusplus > 201402L 00072 # include <bits/node_handle.h> 00073 #endif 00074 00075 namespace std _GLIBCXX_VISIBILITY(default) 00076 { 00077 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00078 00079 #if __cplusplus > 201103L 00080 # define __cpp_lib_generic_associative_lookup 201304 00081 #endif 00082 00083 // Red-black tree class, designed for use in implementing STL 00084 // associative containers (set, multiset, map, and multimap). The 00085 // insertion and deletion algorithms are based on those in Cormen, 00086 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 00087 // 1990), except that 00088 // 00089 // (1) the header cell is maintained with links not only to the root 00090 // but also to the leftmost node of the tree, to enable constant 00091 // time begin(), and to the rightmost node of the tree, to enable 00092 // linear time performance when used with the generic set algorithms 00093 // (set_union, etc.) 00094 // 00095 // (2) when a node being deleted has two children its successor node 00096 // is relinked into its place, rather than copied, so that the only 00097 // iterators invalidated are those referring to the deleted node. 00098 00099 enum _Rb_tree_color { _S_red = false, _S_black = true }; 00100 00101 struct _Rb_tree_node_base 00102 { 00103 typedef _Rb_tree_node_base* _Base_ptr; 00104 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00105 00106 _Rb_tree_color _M_color; 00107 _Base_ptr _M_parent; 00108 _Base_ptr _M_left; 00109 _Base_ptr _M_right; 00110 00111 static _Base_ptr 00112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00113 { 00114 while (__x->_M_left != 0) __x = __x->_M_left; 00115 return __x; 00116 } 00117 00118 static _Const_Base_ptr 00119 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00120 { 00121 while (__x->_M_left != 0) __x = __x->_M_left; 00122 return __x; 00123 } 00124 00125 static _Base_ptr 00126 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00127 { 00128 while (__x->_M_right != 0) __x = __x->_M_right; 00129 return __x; 00130 } 00131 00132 static _Const_Base_ptr 00133 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00134 { 00135 while (__x->_M_right != 0) __x = __x->_M_right; 00136 return __x; 00137 } 00138 }; 00139 00140 // Helper type offering value initialization guarantee on the compare functor. 00141 template<typename _Key_compare> 00142 struct _Rb_tree_key_compare 00143 { 00144 _Key_compare _M_key_compare; 00145 00146 _Rb_tree_key_compare() 00147 _GLIBCXX_NOEXCEPT_IF( 00148 is_nothrow_default_constructible<_Key_compare>::value) 00149 : _M_key_compare() 00150 { } 00151 00152 _Rb_tree_key_compare(const _Key_compare& __comp) 00153 : _M_key_compare(__comp) 00154 { } 00155 00156 #if __cplusplus >= 201103L 00157 // Copy constructor added for consistency with C++98 mode. 00158 _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default; 00159 00160 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x) 00161 noexcept(is_nothrow_copy_constructible<_Key_compare>::value) 00162 : _M_key_compare(__x._M_key_compare) 00163 { } 00164 #endif 00165 }; 00166 00167 // Helper type to manage default initialization of node count and header. 00168 struct _Rb_tree_header 00169 { 00170 _Rb_tree_node_base _M_header; 00171 size_t _M_node_count; // Keeps track of size of tree. 00172 00173 _Rb_tree_header() _GLIBCXX_NOEXCEPT 00174 { 00175 _M_header._M_color = _S_red; 00176 _M_reset(); 00177 } 00178 00179 #if __cplusplus >= 201103L 00180 _Rb_tree_header(_Rb_tree_header&& __x) noexcept 00181 { 00182 if (__x._M_header._M_parent != nullptr) 00183 _M_move_data(__x); 00184 else 00185 { 00186 _M_header._M_color = _S_red; 00187 _M_reset(); 00188 } 00189 } 00190 #endif 00191 00192 void 00193 _M_move_data(_Rb_tree_header& __from) 00194 { 00195 _M_header._M_color = __from._M_header._M_color; 00196 _M_header._M_parent = __from._M_header._M_parent; 00197 _M_header._M_left = __from._M_header._M_left; 00198 _M_header._M_right = __from._M_header._M_right; 00199 _M_header._M_parent->_M_parent = &_M_header; 00200 _M_node_count = __from._M_node_count; 00201 00202 __from._M_reset(); 00203 } 00204 00205 void 00206 _M_reset() 00207 { 00208 _M_header._M_parent = 0; 00209 _M_header._M_left = &_M_header; 00210 _M_header._M_right = &_M_header; 00211 _M_node_count = 0; 00212 } 00213 }; 00214 00215 template<typename _Val> 00216 struct _Rb_tree_node : public _Rb_tree_node_base 00217 { 00218 typedef _Rb_tree_node<_Val>* _Link_type; 00219 00220 #if __cplusplus < 201103L 00221 _Val _M_value_field; 00222 00223 _Val* 00224 _M_valptr() 00225 { return std::__addressof(_M_value_field); } 00226 00227 const _Val* 00228 _M_valptr() const 00229 { return std::__addressof(_M_value_field); } 00230 #else 00231 __gnu_cxx::__aligned_membuf<_Val> _M_storage; 00232 00233 _Val* 00234 _M_valptr() 00235 { return _M_storage._M_ptr(); } 00236 00237 const _Val* 00238 _M_valptr() const 00239 { return _M_storage._M_ptr(); } 00240 #endif 00241 }; 00242 00243 _GLIBCXX_PURE _Rb_tree_node_base* 00244 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 00245 00246 _GLIBCXX_PURE const _Rb_tree_node_base* 00247 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); 00248 00249 _GLIBCXX_PURE _Rb_tree_node_base* 00250 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 00251 00252 _GLIBCXX_PURE const _Rb_tree_node_base* 00253 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); 00254 00255 template<typename _Tp> 00256 struct _Rb_tree_iterator 00257 { 00258 typedef _Tp value_type; 00259 typedef _Tp& reference; 00260 typedef _Tp* pointer; 00261 00262 typedef bidirectional_iterator_tag iterator_category; 00263 typedef ptrdiff_t difference_type; 00264 00265 typedef _Rb_tree_iterator<_Tp> _Self; 00266 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 00267 typedef _Rb_tree_node<_Tp>* _Link_type; 00268 00269 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 00270 : _M_node() { } 00271 00272 explicit 00273 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00274 : _M_node(__x) { } 00275 00276 reference 00277 operator*() const _GLIBCXX_NOEXCEPT 00278 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 00279 00280 pointer 00281 operator->() const _GLIBCXX_NOEXCEPT 00282 { return static_cast<_Link_type> (_M_node)->_M_valptr(); } 00283 00284 _Self& 00285 operator++() _GLIBCXX_NOEXCEPT 00286 { 00287 _M_node = _Rb_tree_increment(_M_node); 00288 return *this; 00289 } 00290 00291 _Self 00292 operator++(int) _GLIBCXX_NOEXCEPT 00293 { 00294 _Self __tmp = *this; 00295 _M_node = _Rb_tree_increment(_M_node); 00296 return __tmp; 00297 } 00298 00299 _Self& 00300 operator--() _GLIBCXX_NOEXCEPT 00301 { 00302 _M_node = _Rb_tree_decrement(_M_node); 00303 return *this; 00304 } 00305 00306 _Self 00307 operator--(int) _GLIBCXX_NOEXCEPT 00308 { 00309 _Self __tmp = *this; 00310 _M_node = _Rb_tree_decrement(_M_node); 00311 return __tmp; 00312 } 00313 00314 friend bool 00315 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT 00316 { return __x._M_node == __y._M_node; } 00317 00318 friend bool 00319 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT 00320 { return __x._M_node != __y._M_node; } 00321 00322 _Base_ptr _M_node; 00323 }; 00324 00325 template<typename _Tp> 00326 struct _Rb_tree_const_iterator 00327 { 00328 typedef _Tp value_type; 00329 typedef const _Tp& reference; 00330 typedef const _Tp* pointer; 00331 00332 typedef _Rb_tree_iterator<_Tp> iterator; 00333 00334 typedef bidirectional_iterator_tag iterator_category; 00335 typedef ptrdiff_t difference_type; 00336 00337 typedef _Rb_tree_const_iterator<_Tp> _Self; 00338 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 00339 typedef const _Rb_tree_node<_Tp>* _Link_type; 00340 00341 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 00342 : _M_node() { } 00343 00344 explicit 00345 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00346 : _M_node(__x) { } 00347 00348 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 00349 : _M_node(__it._M_node) { } 00350 00351 iterator 00352 _M_const_cast() const _GLIBCXX_NOEXCEPT 00353 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); } 00354 00355 reference 00356 operator*() const _GLIBCXX_NOEXCEPT 00357 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 00358 00359 pointer 00360 operator->() const _GLIBCXX_NOEXCEPT 00361 { return static_cast<_Link_type>(_M_node)->_M_valptr(); } 00362 00363 _Self& 00364 operator++() _GLIBCXX_NOEXCEPT 00365 { 00366 _M_node = _Rb_tree_increment(_M_node); 00367 return *this; 00368 } 00369 00370 _Self 00371 operator++(int) _GLIBCXX_NOEXCEPT 00372 { 00373 _Self __tmp = *this; 00374 _M_node = _Rb_tree_increment(_M_node); 00375 return __tmp; 00376 } 00377 00378 _Self& 00379 operator--() _GLIBCXX_NOEXCEPT 00380 { 00381 _M_node = _Rb_tree_decrement(_M_node); 00382 return *this; 00383 } 00384 00385 _Self 00386 operator--(int) _GLIBCXX_NOEXCEPT 00387 { 00388 _Self __tmp = *this; 00389 _M_node = _Rb_tree_decrement(_M_node); 00390 return __tmp; 00391 } 00392 00393 friend bool 00394 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT 00395 { return __x._M_node == __y._M_node; } 00396 00397 friend bool 00398 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT 00399 { return __x._M_node != __y._M_node; } 00400 00401 _Base_ptr _M_node; 00402 }; 00403 00404 void 00405 _Rb_tree_insert_and_rebalance(const bool __insert_left, 00406 _Rb_tree_node_base* __x, 00407 _Rb_tree_node_base* __p, 00408 _Rb_tree_node_base& __header) throw (); 00409 00410 _Rb_tree_node_base* 00411 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 00412 _Rb_tree_node_base& __header) throw (); 00413 00414 #if __cplusplus >= 201402L 00415 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>> 00416 struct __has_is_transparent 00417 { }; 00418 00419 template<typename _Cmp, typename _SfinaeType> 00420 struct __has_is_transparent<_Cmp, _SfinaeType, 00421 __void_t<typename _Cmp::is_transparent>> 00422 { typedef void type; }; 00423 00424 template<typename _Cmp, typename _SfinaeType> 00425 using __has_is_transparent_t 00426 = typename __has_is_transparent<_Cmp, _SfinaeType>::type; 00427 #endif 00428 00429 #if __cplusplus > 201402L 00430 template<typename _Tree1, typename _Cmp2> 00431 struct _Rb_tree_merge_helper { }; 00432 #endif 00433 00434 template<typename _Key, typename _Val, typename _KeyOfValue, 00435 typename _Compare, typename _Alloc = allocator<_Val> > 00436 class _Rb_tree 00437 { 00438 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00439 rebind<_Rb_tree_node<_Val> >::other _Node_allocator; 00440 00441 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; 00442 00443 protected: 00444 typedef _Rb_tree_node_base* _Base_ptr; 00445 typedef const _Rb_tree_node_base* _Const_Base_ptr; 00446 typedef _Rb_tree_node<_Val>* _Link_type; 00447 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 00448 00449 private: 00450 // Functor recycling a pool of nodes and using allocation once the pool 00451 // is empty. 00452 struct _Reuse_or_alloc_node 00453 { 00454 _Reuse_or_alloc_node(_Rb_tree& __t) 00455 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t) 00456 { 00457 if (_M_root) 00458 { 00459 _M_root->_M_parent = 0; 00460 00461 if (_M_nodes->_M_left) 00462 _M_nodes = _M_nodes->_M_left; 00463 } 00464 else 00465 _M_nodes = 0; 00466 } 00467 00468 #if __cplusplus >= 201103L 00469 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; 00470 #endif 00471 00472 ~_Reuse_or_alloc_node() 00473 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } 00474 00475 template<typename _Arg> 00476 _Link_type 00477 #if __cplusplus < 201103L 00478 operator()(const _Arg& __arg) 00479 #else 00480 operator()(_Arg&& __arg) 00481 #endif 00482 { 00483 _Link_type __node = static_cast<_Link_type>(_M_extract()); 00484 if (__node) 00485 { 00486 _M_t._M_destroy_node(__node); 00487 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)); 00488 return __node; 00489 } 00490 00491 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); 00492 } 00493 00494 private: 00495 _Base_ptr 00496 _M_extract() 00497 { 00498 if (!_M_nodes) 00499 return _M_nodes; 00500 00501 _Base_ptr __node = _M_nodes; 00502 _M_nodes = _M_nodes->_M_parent; 00503 if (_M_nodes) 00504 { 00505 if (_M_nodes->_M_right == __node) 00506 { 00507 _M_nodes->_M_right = 0; 00508 00509 if (_M_nodes->_M_left) 00510 { 00511 _M_nodes = _M_nodes->_M_left; 00512 00513 while (_M_nodes->_M_right) 00514 _M_nodes = _M_nodes->_M_right; 00515 00516 if (_M_nodes->_M_left) 00517 _M_nodes = _M_nodes->_M_left; 00518 } 00519 } 00520 else // __node is on the left. 00521 _M_nodes->_M_left = 0; 00522 } 00523 else 00524 _M_root = 0; 00525 00526 return __node; 00527 } 00528 00529 _Base_ptr _M_root; 00530 _Base_ptr _M_nodes; 00531 _Rb_tree& _M_t; 00532 }; 00533 00534 // Functor similar to the previous one but without any pool of nodes to 00535 // recycle. 00536 struct _Alloc_node 00537 { 00538 _Alloc_node(_Rb_tree& __t) 00539 : _M_t(__t) { } 00540 00541 template<typename _Arg> 00542 _Link_type 00543 #if __cplusplus < 201103L 00544 operator()(const _Arg& __arg) const 00545 #else 00546 operator()(_Arg&& __arg) const 00547 #endif 00548 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } 00549 00550 private: 00551 _Rb_tree& _M_t; 00552 }; 00553 00554 public: 00555 typedef _Key key_type; 00556 typedef _Val value_type; 00557 typedef value_type* pointer; 00558 typedef const value_type* const_pointer; 00559 typedef value_type& reference; 00560 typedef const value_type& const_reference; 00561 typedef size_t size_type; 00562 typedef ptrdiff_t difference_type; 00563 typedef _Alloc allocator_type; 00564 00565 _Node_allocator& 00566 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 00567 { return this->_M_impl; } 00568 00569 const _Node_allocator& 00570 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 00571 { return this->_M_impl; } 00572 00573 allocator_type 00574 get_allocator() const _GLIBCXX_NOEXCEPT 00575 { return allocator_type(_M_get_Node_allocator()); } 00576 00577 protected: 00578 _Link_type 00579 _M_get_node() 00580 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } 00581 00582 void 00583 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT 00584 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 00585 00586 #if __cplusplus < 201103L 00587 void 00588 _M_construct_node(_Link_type __node, const value_type& __x) 00589 { 00590 __try 00591 { get_allocator().construct(__node->_M_valptr(), __x); } 00592 __catch(...) 00593 { 00594 _M_put_node(__node); 00595 __throw_exception_again; 00596 } 00597 } 00598 00599 _Link_type 00600 _M_create_node(const value_type& __x) 00601 { 00602 _Link_type __tmp = _M_get_node(); 00603 _M_construct_node(__tmp, __x); 00604 return __tmp; 00605 } 00606 #else 00607 template<typename... _Args> 00608 void 00609 _M_construct_node(_Link_type __node, _Args&&... __args) 00610 { 00611 __try 00612 { 00613 ::new(__node) _Rb_tree_node<_Val>; 00614 _Alloc_traits::construct(_M_get_Node_allocator(), 00615 __node->_M_valptr(), 00616 std::forward<_Args>(__args)...); 00617 } 00618 __catch(...) 00619 { 00620 __node->~_Rb_tree_node<_Val>(); 00621 _M_put_node(__node); 00622 __throw_exception_again; 00623 } 00624 } 00625 00626 template<typename... _Args> 00627 _Link_type 00628 _M_create_node(_Args&&... __args) 00629 { 00630 _Link_type __tmp = _M_get_node(); 00631 _M_construct_node(__tmp, std::forward<_Args>(__args)...); 00632 return __tmp; 00633 } 00634 #endif 00635 00636 void 00637 _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT 00638 { 00639 #if __cplusplus < 201103L 00640 get_allocator().destroy(__p->_M_valptr()); 00641 #else 00642 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 00643 __p->~_Rb_tree_node<_Val>(); 00644 #endif 00645 } 00646 00647 void 00648 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT 00649 { 00650 _M_destroy_node(__p); 00651 _M_put_node(__p); 00652 } 00653 00654 template<typename _NodeGen> 00655 _Link_type 00656 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) 00657 { 00658 _Link_type __tmp = __node_gen(*__x->_M_valptr()); 00659 __tmp->_M_color = __x->_M_color; 00660 __tmp->_M_left = 0; 00661 __tmp->_M_right = 0; 00662 return __tmp; 00663 } 00664 00665 protected: 00666 #if _GLIBCXX_INLINE_VERSION 00667 template<typename _Key_compare> 00668 #else 00669 // Unused _Is_pod_comparator is kept as it is part of mangled name. 00670 template<typename _Key_compare, 00671 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)> 00672 #endif 00673 struct _Rb_tree_impl 00674 : public _Node_allocator 00675 , public _Rb_tree_key_compare<_Key_compare> 00676 , public _Rb_tree_header 00677 { 00678 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare; 00679 00680 _Rb_tree_impl() 00681 _GLIBCXX_NOEXCEPT_IF( 00682 is_nothrow_default_constructible<_Node_allocator>::value 00683 && is_nothrow_default_constructible<_Base_key_compare>::value ) 00684 : _Node_allocator() 00685 { } 00686 00687 _Rb_tree_impl(const _Rb_tree_impl& __x) 00688 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x)) 00689 , _Base_key_compare(__x._M_key_compare) 00690 { } 00691 00692 #if __cplusplus < 201103L 00693 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 00694 : _Node_allocator(__a), _Base_key_compare(__comp) 00695 { } 00696 #else 00697 _Rb_tree_impl(_Rb_tree_impl&&) = default; 00698 00699 explicit 00700 _Rb_tree_impl(_Node_allocator&& __a) 00701 : _Node_allocator(std::move(__a)) 00702 { } 00703 00704 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) 00705 : _Node_allocator(std::move(__a)), 00706 _Base_key_compare(std::move(__x)), 00707 _Rb_tree_header(std::move(__x)) 00708 { } 00709 00710 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 00711 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp) 00712 { } 00713 #endif 00714 }; 00715 00716 _Rb_tree_impl<_Compare> _M_impl; 00717 00718 protected: 00719 _Base_ptr& 00720 _M_root() _GLIBCXX_NOEXCEPT 00721 { return this->_M_impl._M_header._M_parent; } 00722 00723 _Const_Base_ptr 00724 _M_root() const _GLIBCXX_NOEXCEPT 00725 { return this->_M_impl._M_header._M_parent; } 00726 00727 _Base_ptr& 00728 _M_leftmost() _GLIBCXX_NOEXCEPT 00729 { return this->_M_impl._M_header._M_left; } 00730 00731 _Const_Base_ptr 00732 _M_leftmost() const _GLIBCXX_NOEXCEPT 00733 { return this->_M_impl._M_header._M_left; } 00734 00735 _Base_ptr& 00736 _M_rightmost() _GLIBCXX_NOEXCEPT 00737 { return this->_M_impl._M_header._M_right; } 00738 00739 _Const_Base_ptr 00740 _M_rightmost() const _GLIBCXX_NOEXCEPT 00741 { return this->_M_impl._M_header._M_right; } 00742 00743 _Link_type 00744 _M_begin() _GLIBCXX_NOEXCEPT 00745 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 00746 00747 _Const_Link_type 00748 _M_begin() const _GLIBCXX_NOEXCEPT 00749 { 00750 return static_cast<_Const_Link_type> 00751 (this->_M_impl._M_header._M_parent); 00752 } 00753 00754 _Base_ptr 00755 _M_end() _GLIBCXX_NOEXCEPT 00756 { return &this->_M_impl._M_header; } 00757 00758 _Const_Base_ptr 00759 _M_end() const _GLIBCXX_NOEXCEPT 00760 { return &this->_M_impl._M_header; } 00761 00762 static const_reference 00763 _S_value(_Const_Link_type __x) 00764 { return *__x->_M_valptr(); } 00765 00766 static const _Key& 00767 _S_key(_Const_Link_type __x) 00768 { 00769 #if __cplusplus >= 201103L 00770 // If we're asking for the key we're presumably using the comparison 00771 // object, and so this is a good place to sanity check it. 00772 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{}, 00773 "comparison object must be invocable " 00774 "with two arguments of key type"); 00775 # if __cplusplus >= 201703L 00776 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00777 // 2542. Missing const requirements for associative containers 00778 if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{}) 00779 static_assert( 00780 is_invocable_v<const _Compare&, const _Key&, const _Key&>, 00781 "comparison object must be invocable as const"); 00782 # endif // C++17 00783 #endif // C++11 00784 00785 return _KeyOfValue()(*__x->_M_valptr()); 00786 } 00787 00788 static _Link_type 00789 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00790 { return static_cast<_Link_type>(__x->_M_left); } 00791 00792 static _Const_Link_type 00793 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00794 { return static_cast<_Const_Link_type>(__x->_M_left); } 00795 00796 static _Link_type 00797 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00798 { return static_cast<_Link_type>(__x->_M_right); } 00799 00800 static _Const_Link_type 00801 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00802 { return static_cast<_Const_Link_type>(__x->_M_right); } 00803 00804 static const_reference 00805 _S_value(_Const_Base_ptr __x) 00806 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); } 00807 00808 static const _Key& 00809 _S_key(_Const_Base_ptr __x) 00810 { return _S_key(static_cast<_Const_Link_type>(__x)); } 00811 00812 static _Base_ptr 00813 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00814 { return _Rb_tree_node_base::_S_minimum(__x); } 00815 00816 static _Const_Base_ptr 00817 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00818 { return _Rb_tree_node_base::_S_minimum(__x); } 00819 00820 static _Base_ptr 00821 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 00822 { return _Rb_tree_node_base::_S_maximum(__x); } 00823 00824 static _Const_Base_ptr 00825 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 00826 { return _Rb_tree_node_base::_S_maximum(__x); } 00827 00828 public: 00829 typedef _Rb_tree_iterator<value_type> iterator; 00830 typedef _Rb_tree_const_iterator<value_type> const_iterator; 00831 00832 typedef std::reverse_iterator<iterator> reverse_iterator; 00833 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00834 00835 #if __cplusplus > 201402L 00836 using node_type = _Node_handle<_Key, _Val, _Node_allocator>; 00837 using insert_return_type = _Node_insert_return< 00838 conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>, 00839 node_type>; 00840 #endif 00841 00842 pair<_Base_ptr, _Base_ptr> 00843 _M_get_insert_unique_pos(const key_type& __k); 00844 00845 pair<_Base_ptr, _Base_ptr> 00846 _M_get_insert_equal_pos(const key_type& __k); 00847 00848 pair<_Base_ptr, _Base_ptr> 00849 _M_get_insert_hint_unique_pos(const_iterator __pos, 00850 const key_type& __k); 00851 00852 pair<_Base_ptr, _Base_ptr> 00853 _M_get_insert_hint_equal_pos(const_iterator __pos, 00854 const key_type& __k); 00855 00856 private: 00857 #if __cplusplus >= 201103L 00858 template<typename _Arg, typename _NodeGen> 00859 iterator 00860 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); 00861 00862 iterator 00863 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); 00864 00865 template<typename _Arg> 00866 iterator 00867 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 00868 00869 template<typename _Arg> 00870 iterator 00871 _M_insert_equal_lower(_Arg&& __x); 00872 00873 iterator 00874 _M_insert_lower_node(_Base_ptr __p, _Link_type __z); 00875 00876 iterator 00877 _M_insert_equal_lower_node(_Link_type __z); 00878 #else 00879 template<typename _NodeGen> 00880 iterator 00881 _M_insert_(_Base_ptr __x, _Base_ptr __y, 00882 const value_type& __v, _NodeGen&); 00883 00884 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00885 // 233. Insertion hints in associative containers. 00886 iterator 00887 _M_insert_lower(_Base_ptr __y, const value_type& __v); 00888 00889 iterator 00890 _M_insert_equal_lower(const value_type& __x); 00891 #endif 00892 00893 template<typename _NodeGen> 00894 _Link_type 00895 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); 00896 00897 template<typename _NodeGen> 00898 _Link_type 00899 _M_copy(const _Rb_tree& __x, _NodeGen& __gen) 00900 { 00901 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen); 00902 _M_leftmost() = _S_minimum(__root); 00903 _M_rightmost() = _S_maximum(__root); 00904 _M_impl._M_node_count = __x._M_impl._M_node_count; 00905 return __root; 00906 } 00907 00908 _Link_type 00909 _M_copy(const _Rb_tree& __x) 00910 { 00911 _Alloc_node __an(*this); 00912 return _M_copy(__x, __an); 00913 } 00914 00915 void 00916 _M_erase(_Link_type __x); 00917 00918 iterator 00919 _M_lower_bound(_Link_type __x, _Base_ptr __y, 00920 const _Key& __k); 00921 00922 const_iterator 00923 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 00924 const _Key& __k) const; 00925 00926 iterator 00927 _M_upper_bound(_Link_type __x, _Base_ptr __y, 00928 const _Key& __k); 00929 00930 const_iterator 00931 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 00932 const _Key& __k) const; 00933 00934 public: 00935 // allocation/deallocation 00936 #if __cplusplus < 201103L 00937 _Rb_tree() { } 00938 #else 00939 _Rb_tree() = default; 00940 #endif 00941 00942 _Rb_tree(const _Compare& __comp, 00943 const allocator_type& __a = allocator_type()) 00944 : _M_impl(__comp, _Node_allocator(__a)) { } 00945 00946 _Rb_tree(const _Rb_tree& __x) 00947 : _M_impl(__x._M_impl) 00948 { 00949 if (__x._M_root() != 0) 00950 _M_root() = _M_copy(__x); 00951 } 00952 00953 #if __cplusplus >= 201103L 00954 _Rb_tree(const allocator_type& __a) 00955 : _M_impl(_Node_allocator(__a)) 00956 { } 00957 00958 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 00959 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 00960 { 00961 if (__x._M_root() != nullptr) 00962 _M_root() = _M_copy(__x); 00963 } 00964 00965 _Rb_tree(_Rb_tree&&) = default; 00966 00967 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 00968 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 00969 { } 00970 00971 private: 00972 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type) 00973 noexcept(is_nothrow_default_constructible<_Compare>::value) 00974 : _M_impl(std::move(__x._M_impl), std::move(__a)) 00975 { } 00976 00977 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type) 00978 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 00979 { 00980 if (__x._M_root() != nullptr) 00981 _M_move_data(__x, false_type{}); 00982 } 00983 00984 public: 00985 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 00986 noexcept( noexcept( 00987 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(), 00988 std::declval<typename _Alloc_traits::is_always_equal>())) ) 00989 : _Rb_tree(std::move(__x), std::move(__a), 00990 typename _Alloc_traits::is_always_equal{}) 00991 { } 00992 #endif 00993 00994 ~_Rb_tree() _GLIBCXX_NOEXCEPT 00995 { _M_erase(_M_begin()); } 00996 00997 _Rb_tree& 00998 operator=(const _Rb_tree& __x); 00999 01000 // Accessors. 01001 _Compare 01002 key_comp() const 01003 { return _M_impl._M_key_compare; } 01004 01005 iterator 01006 begin() _GLIBCXX_NOEXCEPT 01007 { return iterator(this->_M_impl._M_header._M_left); } 01008 01009 const_iterator 01010 begin() const _GLIBCXX_NOEXCEPT 01011 { return const_iterator(this->_M_impl._M_header._M_left); } 01012 01013 iterator 01014 end() _GLIBCXX_NOEXCEPT 01015 { return iterator(&this->_M_impl._M_header); } 01016 01017 const_iterator 01018 end() const _GLIBCXX_NOEXCEPT 01019 { return const_iterator(&this->_M_impl._M_header); } 01020 01021 reverse_iterator 01022 rbegin() _GLIBCXX_NOEXCEPT 01023 { return reverse_iterator(end()); } 01024 01025 const_reverse_iterator 01026 rbegin() const _GLIBCXX_NOEXCEPT 01027 { return const_reverse_iterator(end()); } 01028 01029 reverse_iterator 01030 rend() _GLIBCXX_NOEXCEPT 01031 { return reverse_iterator(begin()); } 01032 01033 const_reverse_iterator 01034 rend() const _GLIBCXX_NOEXCEPT 01035 { return const_reverse_iterator(begin()); } 01036 01037 _GLIBCXX_NODISCARD bool 01038 empty() const _GLIBCXX_NOEXCEPT 01039 { return _M_impl._M_node_count == 0; } 01040 01041 size_type 01042 size() const _GLIBCXX_NOEXCEPT 01043 { return _M_impl._M_node_count; } 01044 01045 size_type 01046 max_size() const _GLIBCXX_NOEXCEPT 01047 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 01048 01049 void 01050 swap(_Rb_tree& __t) 01051 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value); 01052 01053 // Insert/erase. 01054 #if __cplusplus >= 201103L 01055 template<typename _Arg> 01056 pair<iterator, bool> 01057 _M_insert_unique(_Arg&& __x); 01058 01059 template<typename _Arg> 01060 iterator 01061 _M_insert_equal(_Arg&& __x); 01062 01063 template<typename _Arg, typename _NodeGen> 01064 iterator 01065 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); 01066 01067 template<typename _Arg> 01068 iterator 01069 _M_insert_unique_(const_iterator __pos, _Arg&& __x) 01070 { 01071 _Alloc_node __an(*this); 01072 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); 01073 } 01074 01075 template<typename _Arg, typename _NodeGen> 01076 iterator 01077 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); 01078 01079 template<typename _Arg> 01080 iterator 01081 _M_insert_equal_(const_iterator __pos, _Arg&& __x) 01082 { 01083 _Alloc_node __an(*this); 01084 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); 01085 } 01086 01087 template<typename... _Args> 01088 pair<iterator, bool> 01089 _M_emplace_unique(_Args&&... __args); 01090 01091 template<typename... _Args> 01092 iterator 01093 _M_emplace_equal(_Args&&... __args); 01094 01095 template<typename... _Args> 01096 iterator 01097 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 01098 01099 template<typename... _Args> 01100 iterator 01101 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 01102 01103 template<typename _Iter> 01104 using __same_value_type 01105 = is_same<value_type, typename iterator_traits<_Iter>::value_type>; 01106 01107 template<typename _InputIterator> 01108 __enable_if_t<__same_value_type<_InputIterator>::value> 01109 _M_insert_range_unique(_InputIterator __first, _InputIterator __last) 01110 { 01111 _Alloc_node __an(*this); 01112 for (; __first != __last; ++__first) 01113 _M_insert_unique_(end(), *__first, __an); 01114 } 01115 01116 template<typename _InputIterator> 01117 __enable_if_t<!__same_value_type<_InputIterator>::value> 01118 _M_insert_range_unique(_InputIterator __first, _InputIterator __last) 01119 { 01120 for (; __first != __last; ++__first) 01121 _M_emplace_unique(*__first); 01122 } 01123 01124 template<typename _InputIterator> 01125 __enable_if_t<__same_value_type<_InputIterator>::value> 01126 _M_insert_range_equal(_InputIterator __first, _InputIterator __last) 01127 { 01128 _Alloc_node __an(*this); 01129 for (; __first != __last; ++__first) 01130 _M_insert_equal_(end(), *__first, __an); 01131 } 01132 01133 template<typename _InputIterator> 01134 __enable_if_t<!__same_value_type<_InputIterator>::value> 01135 _M_insert_range_equal(_InputIterator __first, _InputIterator __last) 01136 { 01137 _Alloc_node __an(*this); 01138 for (; __first != __last; ++__first) 01139 _M_emplace_equal(*__first); 01140 } 01141 #else 01142 pair<iterator, bool> 01143 _M_insert_unique(const value_type& __x); 01144 01145 iterator 01146 _M_insert_equal(const value_type& __x); 01147 01148 template<typename _NodeGen> 01149 iterator 01150 _M_insert_unique_(const_iterator __pos, const value_type& __x, 01151 _NodeGen&); 01152 01153 iterator 01154 _M_insert_unique_(const_iterator __pos, const value_type& __x) 01155 { 01156 _Alloc_node __an(*this); 01157 return _M_insert_unique_(__pos, __x, __an); 01158 } 01159 01160 template<typename _NodeGen> 01161 iterator 01162 _M_insert_equal_(const_iterator __pos, const value_type& __x, 01163 _NodeGen&); 01164 iterator 01165 _M_insert_equal_(const_iterator __pos, const value_type& __x) 01166 { 01167 _Alloc_node __an(*this); 01168 return _M_insert_equal_(__pos, __x, __an); 01169 } 01170 01171 template<typename _InputIterator> 01172 void 01173 _M_insert_range_unique(_InputIterator __first, _InputIterator __last) 01174 { 01175 _Alloc_node __an(*this); 01176 for (; __first != __last; ++__first) 01177 _M_insert_unique_(end(), *__first, __an); 01178 } 01179 01180 template<typename _InputIterator> 01181 void 01182 _M_insert_range_equal(_InputIterator __first, _InputIterator __last) 01183 { 01184 _Alloc_node __an(*this); 01185 for (; __first != __last; ++__first) 01186 _M_insert_equal_(end(), *__first, __an); 01187 } 01188 #endif 01189 01190 private: 01191 void 01192 _M_erase_aux(const_iterator __position); 01193 01194 void 01195 _M_erase_aux(const_iterator __first, const_iterator __last); 01196 01197 public: 01198 #if __cplusplus >= 201103L 01199 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01200 // DR 130. Associative erase should return an iterator. 01201 _GLIBCXX_ABI_TAG_CXX11 01202 iterator 01203 erase(const_iterator __position) 01204 { 01205 __glibcxx_assert(__position != end()); 01206 const_iterator __result = __position; 01207 ++__result; 01208 _M_erase_aux(__position); 01209 return __result._M_const_cast(); 01210 } 01211 01212 // LWG 2059. 01213 _GLIBCXX_ABI_TAG_CXX11 01214 iterator 01215 erase(iterator __position) 01216 { 01217 __glibcxx_assert(__position != end()); 01218 iterator __result = __position; 01219 ++__result; 01220 _M_erase_aux(__position); 01221 return __result; 01222 } 01223 #else 01224 void 01225 erase(iterator __position) 01226 { 01227 __glibcxx_assert(__position != end()); 01228 _M_erase_aux(__position); 01229 } 01230 01231 void 01232 erase(const_iterator __position) 01233 { 01234 __glibcxx_assert(__position != end()); 01235 _M_erase_aux(__position); 01236 } 01237 #endif 01238 size_type 01239 erase(const key_type& __x); 01240 01241 #if __cplusplus >= 201103L 01242 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01243 // DR 130. Associative erase should return an iterator. 01244 _GLIBCXX_ABI_TAG_CXX11 01245 iterator 01246 erase(const_iterator __first, const_iterator __last) 01247 { 01248 _M_erase_aux(__first, __last); 01249 return __last._M_const_cast(); 01250 } 01251 #else 01252 void 01253 erase(iterator __first, iterator __last) 01254 { _M_erase_aux(__first, __last); } 01255 01256 void 01257 erase(const_iterator __first, const_iterator __last) 01258 { _M_erase_aux(__first, __last); } 01259 #endif 01260 void 01261 erase(const key_type* __first, const key_type* __last); 01262 01263 void 01264 clear() _GLIBCXX_NOEXCEPT 01265 { 01266 _M_erase(_M_begin()); 01267 _M_impl._M_reset(); 01268 } 01269 01270 // Set operations. 01271 iterator 01272 find(const key_type& __k); 01273 01274 const_iterator 01275 find(const key_type& __k) const; 01276 01277 size_type 01278 count(const key_type& __k) const; 01279 01280 iterator 01281 lower_bound(const key_type& __k) 01282 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 01283 01284 const_iterator 01285 lower_bound(const key_type& __k) const 01286 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 01287 01288 iterator 01289 upper_bound(const key_type& __k) 01290 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 01291 01292 const_iterator 01293 upper_bound(const key_type& __k) const 01294 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 01295 01296 pair<iterator, iterator> 01297 equal_range(const key_type& __k); 01298 01299 pair<const_iterator, const_iterator> 01300 equal_range(const key_type& __k) const; 01301 01302 #if __cplusplus >= 201402L 01303 template<typename _Kt, 01304 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01305 iterator 01306 _M_find_tr(const _Kt& __k) 01307 { 01308 const _Rb_tree* __const_this = this; 01309 return __const_this->_M_find_tr(__k)._M_const_cast(); 01310 } 01311 01312 template<typename _Kt, 01313 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01314 const_iterator 01315 _M_find_tr(const _Kt& __k) const 01316 { 01317 auto __j = _M_lower_bound_tr(__k); 01318 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node))) 01319 __j = end(); 01320 return __j; 01321 } 01322 01323 template<typename _Kt, 01324 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01325 size_type 01326 _M_count_tr(const _Kt& __k) const 01327 { 01328 auto __p = _M_equal_range_tr(__k); 01329 return std::distance(__p.first, __p.second); 01330 } 01331 01332 template<typename _Kt, 01333 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01334 iterator 01335 _M_lower_bound_tr(const _Kt& __k) 01336 { 01337 const _Rb_tree* __const_this = this; 01338 return __const_this->_M_lower_bound_tr(__k)._M_const_cast(); 01339 } 01340 01341 template<typename _Kt, 01342 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01343 const_iterator 01344 _M_lower_bound_tr(const _Kt& __k) const 01345 { 01346 auto __x = _M_begin(); 01347 auto __y = _M_end(); 01348 while (__x != 0) 01349 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01350 { 01351 __y = __x; 01352 __x = _S_left(__x); 01353 } 01354 else 01355 __x = _S_right(__x); 01356 return const_iterator(__y); 01357 } 01358 01359 template<typename _Kt, 01360 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01361 iterator 01362 _M_upper_bound_tr(const _Kt& __k) 01363 { 01364 const _Rb_tree* __const_this = this; 01365 return __const_this->_M_upper_bound_tr(__k)._M_const_cast(); 01366 } 01367 01368 template<typename _Kt, 01369 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01370 const_iterator 01371 _M_upper_bound_tr(const _Kt& __k) const 01372 { 01373 auto __x = _M_begin(); 01374 auto __y = _M_end(); 01375 while (__x != 0) 01376 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01377 { 01378 __y = __x; 01379 __x = _S_left(__x); 01380 } 01381 else 01382 __x = _S_right(__x); 01383 return const_iterator(__y); 01384 } 01385 01386 template<typename _Kt, 01387 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01388 pair<iterator, iterator> 01389 _M_equal_range_tr(const _Kt& __k) 01390 { 01391 const _Rb_tree* __const_this = this; 01392 auto __ret = __const_this->_M_equal_range_tr(__k); 01393 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() }; 01394 } 01395 01396 template<typename _Kt, 01397 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 01398 pair<const_iterator, const_iterator> 01399 _M_equal_range_tr(const _Kt& __k) const 01400 { 01401 auto __low = _M_lower_bound_tr(__k); 01402 auto __high = __low; 01403 auto& __cmp = _M_impl._M_key_compare; 01404 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 01405 ++__high; 01406 return { __low, __high }; 01407 } 01408 #endif 01409 01410 // Debugging. 01411 bool 01412 __rb_verify() const; 01413 01414 #if __cplusplus >= 201103L 01415 _Rb_tree& 01416 operator=(_Rb_tree&&) 01417 noexcept(_Alloc_traits::_S_nothrow_move() 01418 && is_nothrow_move_assignable<_Compare>::value); 01419 01420 template<typename _Iterator> 01421 void 01422 _M_assign_unique(_Iterator, _Iterator); 01423 01424 template<typename _Iterator> 01425 void 01426 _M_assign_equal(_Iterator, _Iterator); 01427 01428 private: 01429 // Move elements from container with equal allocator. 01430 void 01431 _M_move_data(_Rb_tree& __x, true_type) 01432 { _M_impl._M_move_data(__x._M_impl); } 01433 01434 // Move elements from container with possibly non-equal allocator, 01435 // which might result in a copy not a move. 01436 void 01437 _M_move_data(_Rb_tree&, false_type); 01438 01439 // Move assignment from container with equal allocator. 01440 void 01441 _M_move_assign(_Rb_tree&, true_type); 01442 01443 // Move assignment from container with possibly non-equal allocator, 01444 // which might result in a copy not a move. 01445 void 01446 _M_move_assign(_Rb_tree&, false_type); 01447 #endif 01448 01449 #if __cplusplus > 201402L 01450 public: 01451 /// Re-insert an extracted node. 01452 insert_return_type 01453 _M_reinsert_node_unique(node_type&& __nh) 01454 { 01455 insert_return_type __ret; 01456 if (__nh.empty()) 01457 __ret.position = end(); 01458 else 01459 { 01460 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 01461 01462 auto __res = _M_get_insert_unique_pos(__nh._M_key()); 01463 if (__res.second) 01464 { 01465 __ret.position 01466 = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 01467 __nh._M_ptr = nullptr; 01468 __ret.inserted = true; 01469 } 01470 else 01471 { 01472 __ret.node = std::move(__nh); 01473 __ret.position = iterator(__res.first); 01474 __ret.inserted = false; 01475 } 01476 } 01477 return __ret; 01478 } 01479 01480 /// Re-insert an extracted node. 01481 iterator 01482 _M_reinsert_node_equal(node_type&& __nh) 01483 { 01484 iterator __ret; 01485 if (__nh.empty()) 01486 __ret = end(); 01487 else 01488 { 01489 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 01490 auto __res = _M_get_insert_equal_pos(__nh._M_key()); 01491 if (__res.second) 01492 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 01493 else 01494 __ret = _M_insert_equal_lower_node(__nh._M_ptr); 01495 __nh._M_ptr = nullptr; 01496 } 01497 return __ret; 01498 } 01499 01500 /// Re-insert an extracted node. 01501 iterator 01502 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh) 01503 { 01504 iterator __ret; 01505 if (__nh.empty()) 01506 __ret = end(); 01507 else 01508 { 01509 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 01510 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key()); 01511 if (__res.second) 01512 { 01513 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 01514 __nh._M_ptr = nullptr; 01515 } 01516 else 01517 __ret = iterator(__res.first); 01518 } 01519 return __ret; 01520 } 01521 01522 /// Re-insert an extracted node. 01523 iterator 01524 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh) 01525 { 01526 iterator __ret; 01527 if (__nh.empty()) 01528 __ret = end(); 01529 else 01530 { 01531 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 01532 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key()); 01533 if (__res.second) 01534 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 01535 else 01536 __ret = _M_insert_equal_lower_node(__nh._M_ptr); 01537 __nh._M_ptr = nullptr; 01538 } 01539 return __ret; 01540 } 01541 01542 /// Extract a node. 01543 node_type 01544 extract(const_iterator __pos) 01545 { 01546 auto __ptr = _Rb_tree_rebalance_for_erase( 01547 __pos._M_const_cast()._M_node, _M_impl._M_header); 01548 --_M_impl._M_node_count; 01549 return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() }; 01550 } 01551 01552 /// Extract a node. 01553 node_type 01554 extract(const key_type& __k) 01555 { 01556 node_type __nh; 01557 auto __pos = find(__k); 01558 if (__pos != end()) 01559 __nh = extract(const_iterator(__pos)); 01560 return __nh; 01561 } 01562 01563 template<typename _Compare2> 01564 using _Compatible_tree 01565 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>; 01566 01567 template<typename, typename> 01568 friend class _Rb_tree_merge_helper; 01569 01570 /// Merge from a compatible container into one with unique keys. 01571 template<typename _Compare2> 01572 void 01573 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept 01574 { 01575 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; 01576 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 01577 { 01578 auto __pos = __i++; 01579 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos)); 01580 if (__res.second) 01581 { 01582 auto& __src_impl = _Merge_helper::_S_get_impl(__src); 01583 auto __ptr = _Rb_tree_rebalance_for_erase( 01584 __pos._M_node, __src_impl._M_header); 01585 --__src_impl._M_node_count; 01586 _M_insert_node(__res.first, __res.second, 01587 static_cast<_Link_type>(__ptr)); 01588 } 01589 } 01590 } 01591 01592 /// Merge from a compatible container into one with equivalent keys. 01593 template<typename _Compare2> 01594 void 01595 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept 01596 { 01597 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; 01598 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 01599 { 01600 auto __pos = __i++; 01601 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos)); 01602 if (__res.second) 01603 { 01604 auto& __src_impl = _Merge_helper::_S_get_impl(__src); 01605 auto __ptr = _Rb_tree_rebalance_for_erase( 01606 __pos._M_node, __src_impl._M_header); 01607 --__src_impl._M_node_count; 01608 _M_insert_node(__res.first, __res.second, 01609 static_cast<_Link_type>(__ptr)); 01610 } 01611 } 01612 } 01613 #endif // C++17 01614 01615 friend bool 01616 operator==(const _Rb_tree& __x, const _Rb_tree& __y) 01617 { 01618 return __x.size() == __y.size() 01619 && std::equal(__x.begin(), __x.end(), __y.begin()); 01620 } 01621 01622 friend bool 01623 operator<(const _Rb_tree& __x, const _Rb_tree& __y) 01624 { 01625 return std::lexicographical_compare(__x.begin(), __x.end(), 01626 __y.begin(), __y.end()); 01627 } 01628 01629 friend bool _GLIBCXX_DEPRECATED 01630 operator!=(const _Rb_tree& __x, const _Rb_tree& __y) 01631 { return !(__x == __y); } 01632 01633 friend bool _GLIBCXX_DEPRECATED 01634 operator>(const _Rb_tree& __x, const _Rb_tree& __y) 01635 { return __y < __x; } 01636 01637 friend bool _GLIBCXX_DEPRECATED 01638 operator<=(const _Rb_tree& __x, const _Rb_tree& __y) 01639 { return !(__y < __x); } 01640 01641 friend bool _GLIBCXX_DEPRECATED 01642 operator>=(const _Rb_tree& __x, const _Rb_tree& __y) 01643 { return !(__x < __y); } 01644 }; 01645 01646 template<typename _Key, typename _Val, typename _KeyOfValue, 01647 typename _Compare, typename _Alloc> 01648 inline void 01649 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 01650 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 01651 { __x.swap(__y); } 01652 01653 #if __cplusplus >= 201103L 01654 template<typename _Key, typename _Val, typename _KeyOfValue, 01655 typename _Compare, typename _Alloc> 01656 void 01657 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01658 _M_move_data(_Rb_tree& __x, false_type) 01659 { 01660 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 01661 _M_move_data(__x, true_type()); 01662 else 01663 { 01664 _Alloc_node __an(*this); 01665 auto __lbd = 01666 [&__an](const value_type& __cval) 01667 { 01668 auto& __val = const_cast<value_type&>(__cval); 01669 return __an(std::move_if_noexcept(__val)); 01670 }; 01671 _M_root() = _M_copy(__x, __lbd); 01672 } 01673 } 01674 01675 template<typename _Key, typename _Val, typename _KeyOfValue, 01676 typename _Compare, typename _Alloc> 01677 inline void 01678 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01679 _M_move_assign(_Rb_tree& __x, true_type) 01680 { 01681 clear(); 01682 if (__x._M_root() != nullptr) 01683 _M_move_data(__x, true_type()); 01684 std::__alloc_on_move(_M_get_Node_allocator(), 01685 __x._M_get_Node_allocator()); 01686 } 01687 01688 template<typename _Key, typename _Val, typename _KeyOfValue, 01689 typename _Compare, typename _Alloc> 01690 void 01691 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01692 _M_move_assign(_Rb_tree& __x, false_type) 01693 { 01694 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 01695 return _M_move_assign(__x, true_type{}); 01696 01697 // Try to move each node reusing existing nodes and copying __x nodes 01698 // structure. 01699 _Reuse_or_alloc_node __roan(*this); 01700 _M_impl._M_reset(); 01701 if (__x._M_root() != nullptr) 01702 { 01703 auto __lbd = 01704 [&__roan](const value_type& __cval) 01705 { 01706 auto& __val = const_cast<value_type&>(__cval); 01707 return __roan(std::move_if_noexcept(__val)); 01708 }; 01709 _M_root() = _M_copy(__x, __lbd); 01710 __x.clear(); 01711 } 01712 } 01713 01714 template<typename _Key, typename _Val, typename _KeyOfValue, 01715 typename _Compare, typename _Alloc> 01716 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01717 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01718 operator=(_Rb_tree&& __x) 01719 noexcept(_Alloc_traits::_S_nothrow_move() 01720 && is_nothrow_move_assignable<_Compare>::value) 01721 { 01722 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare); 01723 _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>()); 01724 return *this; 01725 } 01726 01727 template<typename _Key, typename _Val, typename _KeyOfValue, 01728 typename _Compare, typename _Alloc> 01729 template<typename _Iterator> 01730 void 01731 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01732 _M_assign_unique(_Iterator __first, _Iterator __last) 01733 { 01734 _Reuse_or_alloc_node __roan(*this); 01735 _M_impl._M_reset(); 01736 for (; __first != __last; ++__first) 01737 _M_insert_unique_(end(), *__first, __roan); 01738 } 01739 01740 template<typename _Key, typename _Val, typename _KeyOfValue, 01741 typename _Compare, typename _Alloc> 01742 template<typename _Iterator> 01743 void 01744 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01745 _M_assign_equal(_Iterator __first, _Iterator __last) 01746 { 01747 _Reuse_or_alloc_node __roan(*this); 01748 _M_impl._M_reset(); 01749 for (; __first != __last; ++__first) 01750 _M_insert_equal_(end(), *__first, __roan); 01751 } 01752 #endif 01753 01754 template<typename _Key, typename _Val, typename _KeyOfValue, 01755 typename _Compare, typename _Alloc> 01756 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 01757 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01758 operator=(const _Rb_tree& __x) 01759 { 01760 if (this != &__x) 01761 { 01762 // Note that _Key may be a constant type. 01763 #if __cplusplus >= 201103L 01764 if (_Alloc_traits::_S_propagate_on_copy_assign()) 01765 { 01766 auto& __this_alloc = this->_M_get_Node_allocator(); 01767 auto& __that_alloc = __x._M_get_Node_allocator(); 01768 if (!_Alloc_traits::_S_always_equal() 01769 && __this_alloc != __that_alloc) 01770 { 01771 // Replacement allocator cannot free existing storage, we need 01772 // to erase nodes first. 01773 clear(); 01774 std::__alloc_on_copy(__this_alloc, __that_alloc); 01775 } 01776 } 01777 #endif 01778 01779 _Reuse_or_alloc_node __roan(*this); 01780 _M_impl._M_reset(); 01781 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 01782 if (__x._M_root() != 0) 01783 _M_root() = _M_copy(__x, __roan); 01784 } 01785 01786 return *this; 01787 } 01788 01789 template<typename _Key, typename _Val, typename _KeyOfValue, 01790 typename _Compare, typename _Alloc> 01791 #if __cplusplus >= 201103L 01792 template<typename _Arg, typename _NodeGen> 01793 #else 01794 template<typename _NodeGen> 01795 #endif 01796 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01797 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01798 _M_insert_(_Base_ptr __x, _Base_ptr __p, 01799 #if __cplusplus >= 201103L 01800 _Arg&& __v, 01801 #else 01802 const _Val& __v, 01803 #endif 01804 _NodeGen& __node_gen) 01805 { 01806 bool __insert_left = (__x != 0 || __p == _M_end() 01807 || _M_impl._M_key_compare(_KeyOfValue()(__v), 01808 _S_key(__p))); 01809 01810 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); 01811 01812 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01813 this->_M_impl._M_header); 01814 ++_M_impl._M_node_count; 01815 return iterator(__z); 01816 } 01817 01818 template<typename _Key, typename _Val, typename _KeyOfValue, 01819 typename _Compare, typename _Alloc> 01820 #if __cplusplus >= 201103L 01821 template<typename _Arg> 01822 #endif 01823 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01824 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01825 #if __cplusplus >= 201103L 01826 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 01827 #else 01828 _M_insert_lower(_Base_ptr __p, const _Val& __v) 01829 #endif 01830 { 01831 bool __insert_left = (__p == _M_end() 01832 || !_M_impl._M_key_compare(_S_key(__p), 01833 _KeyOfValue()(__v))); 01834 01835 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 01836 01837 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 01838 this->_M_impl._M_header); 01839 ++_M_impl._M_node_count; 01840 return iterator(__z); 01841 } 01842 01843 template<typename _Key, typename _Val, typename _KeyOfValue, 01844 typename _Compare, typename _Alloc> 01845 #if __cplusplus >= 201103L 01846 template<typename _Arg> 01847 #endif 01848 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 01849 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01850 #if __cplusplus >= 201103L 01851 _M_insert_equal_lower(_Arg&& __v) 01852 #else 01853 _M_insert_equal_lower(const _Val& __v) 01854 #endif 01855 { 01856 _Link_type __x = _M_begin(); 01857 _Base_ptr __y = _M_end(); 01858 while (__x != 0) 01859 { 01860 __y = __x; 01861 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 01862 _S_left(__x) : _S_right(__x); 01863 } 01864 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 01865 } 01866 01867 template<typename _Key, typename _Val, typename _KoV, 01868 typename _Compare, typename _Alloc> 01869 template<typename _NodeGen> 01870 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 01871 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 01872 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) 01873 { 01874 // Structural copy. __x and __p must be non-null. 01875 _Link_type __top = _M_clone_node(__x, __node_gen); 01876 __top->_M_parent = __p; 01877 01878 __try 01879 { 01880 if (__x->_M_right) 01881 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); 01882 __p = __top; 01883 __x = _S_left(__x); 01884 01885 while (__x != 0) 01886 { 01887 _Link_type __y = _M_clone_node(__x, __node_gen); 01888 __p->_M_left = __y; 01889 __y->_M_parent = __p; 01890 if (__x->_M_right) 01891 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); 01892 __p = __y; 01893 __x = _S_left(__x); 01894 } 01895 } 01896 __catch(...) 01897 { 01898 _M_erase(__top); 01899 __throw_exception_again; 01900 } 01901 return __top; 01902 } 01903 01904 template<typename _Key, typename _Val, typename _KeyOfValue, 01905 typename _Compare, typename _Alloc> 01906 void 01907 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01908 _M_erase(_Link_type __x) 01909 { 01910 // Erase without rebalancing. 01911 while (__x != 0) 01912 { 01913 _M_erase(_S_right(__x)); 01914 _Link_type __y = _S_left(__x); 01915 _M_drop_node(__x); 01916 __x = __y; 01917 } 01918 } 01919 01920 template<typename _Key, typename _Val, typename _KeyOfValue, 01921 typename _Compare, typename _Alloc> 01922 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01923 _Compare, _Alloc>::iterator 01924 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01925 _M_lower_bound(_Link_type __x, _Base_ptr __y, 01926 const _Key& __k) 01927 { 01928 while (__x != 0) 01929 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01930 __y = __x, __x = _S_left(__x); 01931 else 01932 __x = _S_right(__x); 01933 return iterator(__y); 01934 } 01935 01936 template<typename _Key, typename _Val, typename _KeyOfValue, 01937 typename _Compare, typename _Alloc> 01938 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01939 _Compare, _Alloc>::const_iterator 01940 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01941 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 01942 const _Key& __k) const 01943 { 01944 while (__x != 0) 01945 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 01946 __y = __x, __x = _S_left(__x); 01947 else 01948 __x = _S_right(__x); 01949 return const_iterator(__y); 01950 } 01951 01952 template<typename _Key, typename _Val, typename _KeyOfValue, 01953 typename _Compare, typename _Alloc> 01954 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01955 _Compare, _Alloc>::iterator 01956 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01957 _M_upper_bound(_Link_type __x, _Base_ptr __y, 01958 const _Key& __k) 01959 { 01960 while (__x != 0) 01961 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01962 __y = __x, __x = _S_left(__x); 01963 else 01964 __x = _S_right(__x); 01965 return iterator(__y); 01966 } 01967 01968 template<typename _Key, typename _Val, typename _KeyOfValue, 01969 typename _Compare, typename _Alloc> 01970 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01971 _Compare, _Alloc>::const_iterator 01972 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01973 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 01974 const _Key& __k) const 01975 { 01976 while (__x != 0) 01977 if (_M_impl._M_key_compare(__k, _S_key(__x))) 01978 __y = __x, __x = _S_left(__x); 01979 else 01980 __x = _S_right(__x); 01981 return const_iterator(__y); 01982 } 01983 01984 template<typename _Key, typename _Val, typename _KeyOfValue, 01985 typename _Compare, typename _Alloc> 01986 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 01987 _Compare, _Alloc>::iterator, 01988 typename _Rb_tree<_Key, _Val, _KeyOfValue, 01989 _Compare, _Alloc>::iterator> 01990 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 01991 equal_range(const _Key& __k) 01992 { 01993 _Link_type __x = _M_begin(); 01994 _Base_ptr __y = _M_end(); 01995 while (__x != 0) 01996 { 01997 if (_M_impl._M_key_compare(_S_key(__x), __k)) 01998 __x = _S_right(__x); 01999 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 02000 __y = __x, __x = _S_left(__x); 02001 else 02002 { 02003 _Link_type __xu(__x); 02004 _Base_ptr __yu(__y); 02005 __y = __x, __x = _S_left(__x); 02006 __xu = _S_right(__xu); 02007 return pair<iterator, 02008 iterator>(_M_lower_bound(__x, __y, __k), 02009 _M_upper_bound(__xu, __yu, __k)); 02010 } 02011 } 02012 return pair<iterator, iterator>(iterator(__y), 02013 iterator(__y)); 02014 } 02015 02016 template<typename _Key, typename _Val, typename _KeyOfValue, 02017 typename _Compare, typename _Alloc> 02018 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02019 _Compare, _Alloc>::const_iterator, 02020 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02021 _Compare, _Alloc>::const_iterator> 02022 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02023 equal_range(const _Key& __k) const 02024 { 02025 _Const_Link_type __x = _M_begin(); 02026 _Const_Base_ptr __y = _M_end(); 02027 while (__x != 0) 02028 { 02029 if (_M_impl._M_key_compare(_S_key(__x), __k)) 02030 __x = _S_right(__x); 02031 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 02032 __y = __x, __x = _S_left(__x); 02033 else 02034 { 02035 _Const_Link_type __xu(__x); 02036 _Const_Base_ptr __yu(__y); 02037 __y = __x, __x = _S_left(__x); 02038 __xu = _S_right(__xu); 02039 return pair<const_iterator, 02040 const_iterator>(_M_lower_bound(__x, __y, __k), 02041 _M_upper_bound(__xu, __yu, __k)); 02042 } 02043 } 02044 return pair<const_iterator, const_iterator>(const_iterator(__y), 02045 const_iterator(__y)); 02046 } 02047 02048 template<typename _Key, typename _Val, typename _KeyOfValue, 02049 typename _Compare, typename _Alloc> 02050 void 02051 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02052 swap(_Rb_tree& __t) 02053 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 02054 { 02055 if (_M_root() == 0) 02056 { 02057 if (__t._M_root() != 0) 02058 _M_impl._M_move_data(__t._M_impl); 02059 } 02060 else if (__t._M_root() == 0) 02061 __t._M_impl._M_move_data(_M_impl); 02062 else 02063 { 02064 std::swap(_M_root(),__t._M_root()); 02065 std::swap(_M_leftmost(),__t._M_leftmost()); 02066 std::swap(_M_rightmost(),__t._M_rightmost()); 02067 02068 _M_root()->_M_parent = _M_end(); 02069 __t._M_root()->_M_parent = __t._M_end(); 02070 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 02071 } 02072 // No need to swap header's color as it does not change. 02073 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 02074 02075 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 02076 __t._M_get_Node_allocator()); 02077 } 02078 02079 template<typename _Key, typename _Val, typename _KeyOfValue, 02080 typename _Compare, typename _Alloc> 02081 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02082 _Compare, _Alloc>::_Base_ptr, 02083 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02084 _Compare, _Alloc>::_Base_ptr> 02085 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02086 _M_get_insert_unique_pos(const key_type& __k) 02087 { 02088 typedef pair<_Base_ptr, _Base_ptr> _Res; 02089 _Link_type __x = _M_begin(); 02090 _Base_ptr __y = _M_end(); 02091 bool __comp = true; 02092 while (__x != 0) 02093 { 02094 __y = __x; 02095 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 02096 __x = __comp ? _S_left(__x) : _S_right(__x); 02097 } 02098 iterator __j = iterator(__y); 02099 if (__comp) 02100 { 02101 if (__j == begin()) 02102 return _Res(__x, __y); 02103 else 02104 --__j; 02105 } 02106 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 02107 return _Res(__x, __y); 02108 return _Res(__j._M_node, 0); 02109 } 02110 02111 template<typename _Key, typename _Val, typename _KeyOfValue, 02112 typename _Compare, typename _Alloc> 02113 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02114 _Compare, _Alloc>::_Base_ptr, 02115 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02116 _Compare, _Alloc>::_Base_ptr> 02117 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02118 _M_get_insert_equal_pos(const key_type& __k) 02119 { 02120 typedef pair<_Base_ptr, _Base_ptr> _Res; 02121 _Link_type __x = _M_begin(); 02122 _Base_ptr __y = _M_end(); 02123 while (__x != 0) 02124 { 02125 __y = __x; 02126 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 02127 _S_left(__x) : _S_right(__x); 02128 } 02129 return _Res(__x, __y); 02130 } 02131 02132 template<typename _Key, typename _Val, typename _KeyOfValue, 02133 typename _Compare, typename _Alloc> 02134 #if __cplusplus >= 201103L 02135 template<typename _Arg> 02136 #endif 02137 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02138 _Compare, _Alloc>::iterator, bool> 02139 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02140 #if __cplusplus >= 201103L 02141 _M_insert_unique(_Arg&& __v) 02142 #else 02143 _M_insert_unique(const _Val& __v) 02144 #endif 02145 { 02146 typedef pair<iterator, bool> _Res; 02147 pair<_Base_ptr, _Base_ptr> __res 02148 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 02149 02150 if (__res.second) 02151 { 02152 _Alloc_node __an(*this); 02153 return _Res(_M_insert_(__res.first, __res.second, 02154 _GLIBCXX_FORWARD(_Arg, __v), __an), 02155 true); 02156 } 02157 02158 return _Res(iterator(__res.first), false); 02159 } 02160 02161 template<typename _Key, typename _Val, typename _KeyOfValue, 02162 typename _Compare, typename _Alloc> 02163 #if __cplusplus >= 201103L 02164 template<typename _Arg> 02165 #endif 02166 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02167 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02168 #if __cplusplus >= 201103L 02169 _M_insert_equal(_Arg&& __v) 02170 #else 02171 _M_insert_equal(const _Val& __v) 02172 #endif 02173 { 02174 pair<_Base_ptr, _Base_ptr> __res 02175 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 02176 _Alloc_node __an(*this); 02177 return _M_insert_(__res.first, __res.second, 02178 _GLIBCXX_FORWARD(_Arg, __v), __an); 02179 } 02180 02181 template<typename _Key, typename _Val, typename _KeyOfValue, 02182 typename _Compare, typename _Alloc> 02183 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02184 _Compare, _Alloc>::_Base_ptr, 02185 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02186 _Compare, _Alloc>::_Base_ptr> 02187 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02188 _M_get_insert_hint_unique_pos(const_iterator __position, 02189 const key_type& __k) 02190 { 02191 iterator __pos = __position._M_const_cast(); 02192 typedef pair<_Base_ptr, _Base_ptr> _Res; 02193 02194 // end() 02195 if (__pos._M_node == _M_end()) 02196 { 02197 if (size() > 0 02198 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 02199 return _Res(0, _M_rightmost()); 02200 else 02201 return _M_get_insert_unique_pos(__k); 02202 } 02203 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 02204 { 02205 // First, try before... 02206 iterator __before = __pos; 02207 if (__pos._M_node == _M_leftmost()) // begin() 02208 return _Res(_M_leftmost(), _M_leftmost()); 02209 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 02210 { 02211 if (_S_right(__before._M_node) == 0) 02212 return _Res(0, __before._M_node); 02213 else 02214 return _Res(__pos._M_node, __pos._M_node); 02215 } 02216 else 02217 return _M_get_insert_unique_pos(__k); 02218 } 02219 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 02220 { 02221 // ... then try after. 02222 iterator __after = __pos; 02223 if (__pos._M_node == _M_rightmost()) 02224 return _Res(0, _M_rightmost()); 02225 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 02226 { 02227 if (_S_right(__pos._M_node) == 0) 02228 return _Res(0, __pos._M_node); 02229 else 02230 return _Res(__after._M_node, __after._M_node); 02231 } 02232 else 02233 return _M_get_insert_unique_pos(__k); 02234 } 02235 else 02236 // Equivalent keys. 02237 return _Res(__pos._M_node, 0); 02238 } 02239 02240 template<typename _Key, typename _Val, typename _KeyOfValue, 02241 typename _Compare, typename _Alloc> 02242 #if __cplusplus >= 201103L 02243 template<typename _Arg, typename _NodeGen> 02244 #else 02245 template<typename _NodeGen> 02246 #endif 02247 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02248 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02249 _M_insert_unique_(const_iterator __position, 02250 #if __cplusplus >= 201103L 02251 _Arg&& __v, 02252 #else 02253 const _Val& __v, 02254 #endif 02255 _NodeGen& __node_gen) 02256 { 02257 pair<_Base_ptr, _Base_ptr> __res 02258 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 02259 02260 if (__res.second) 02261 return _M_insert_(__res.first, __res.second, 02262 _GLIBCXX_FORWARD(_Arg, __v), 02263 __node_gen); 02264 return iterator(__res.first); 02265 } 02266 02267 template<typename _Key, typename _Val, typename _KeyOfValue, 02268 typename _Compare, typename _Alloc> 02269 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02270 _Compare, _Alloc>::_Base_ptr, 02271 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02272 _Compare, _Alloc>::_Base_ptr> 02273 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02274 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 02275 { 02276 iterator __pos = __position._M_const_cast(); 02277 typedef pair<_Base_ptr, _Base_ptr> _Res; 02278 02279 // end() 02280 if (__pos._M_node == _M_end()) 02281 { 02282 if (size() > 0 02283 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 02284 return _Res(0, _M_rightmost()); 02285 else 02286 return _M_get_insert_equal_pos(__k); 02287 } 02288 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 02289 { 02290 // First, try before... 02291 iterator __before = __pos; 02292 if (__pos._M_node == _M_leftmost()) // begin() 02293 return _Res(_M_leftmost(), _M_leftmost()); 02294 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 02295 { 02296 if (_S_right(__before._M_node) == 0) 02297 return _Res(0, __before._M_node); 02298 else 02299 return _Res(__pos._M_node, __pos._M_node); 02300 } 02301 else 02302 return _M_get_insert_equal_pos(__k); 02303 } 02304 else 02305 { 02306 // ... then try after. 02307 iterator __after = __pos; 02308 if (__pos._M_node == _M_rightmost()) 02309 return _Res(0, _M_rightmost()); 02310 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 02311 { 02312 if (_S_right(__pos._M_node) == 0) 02313 return _Res(0, __pos._M_node); 02314 else 02315 return _Res(__after._M_node, __after._M_node); 02316 } 02317 else 02318 return _Res(0, 0); 02319 } 02320 } 02321 02322 template<typename _Key, typename _Val, typename _KeyOfValue, 02323 typename _Compare, typename _Alloc> 02324 #if __cplusplus >= 201103L 02325 template<typename _Arg, typename _NodeGen> 02326 #else 02327 template<typename _NodeGen> 02328 #endif 02329 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02330 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02331 _M_insert_equal_(const_iterator __position, 02332 #if __cplusplus >= 201103L 02333 _Arg&& __v, 02334 #else 02335 const _Val& __v, 02336 #endif 02337 _NodeGen& __node_gen) 02338 { 02339 pair<_Base_ptr, _Base_ptr> __res 02340 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 02341 02342 if (__res.second) 02343 return _M_insert_(__res.first, __res.second, 02344 _GLIBCXX_FORWARD(_Arg, __v), 02345 __node_gen); 02346 02347 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 02348 } 02349 02350 #if __cplusplus >= 201103L 02351 template<typename _Key, typename _Val, typename _KeyOfValue, 02352 typename _Compare, typename _Alloc> 02353 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02354 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02355 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 02356 { 02357 bool __insert_left = (__x != 0 || __p == _M_end() 02358 || _M_impl._M_key_compare(_S_key(__z), 02359 _S_key(__p))); 02360 02361 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 02362 this->_M_impl._M_header); 02363 ++_M_impl._M_node_count; 02364 return iterator(__z); 02365 } 02366 02367 template<typename _Key, typename _Val, typename _KeyOfValue, 02368 typename _Compare, typename _Alloc> 02369 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02370 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02371 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 02372 { 02373 bool __insert_left = (__p == _M_end() 02374 || !_M_impl._M_key_compare(_S_key(__p), 02375 _S_key(__z))); 02376 02377 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 02378 this->_M_impl._M_header); 02379 ++_M_impl._M_node_count; 02380 return iterator(__z); 02381 } 02382 02383 template<typename _Key, typename _Val, typename _KeyOfValue, 02384 typename _Compare, typename _Alloc> 02385 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02386 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02387 _M_insert_equal_lower_node(_Link_type __z) 02388 { 02389 _Link_type __x = _M_begin(); 02390 _Base_ptr __y = _M_end(); 02391 while (__x != 0) 02392 { 02393 __y = __x; 02394 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 02395 _S_left(__x) : _S_right(__x); 02396 } 02397 return _M_insert_lower_node(__y, __z); 02398 } 02399 02400 template<typename _Key, typename _Val, typename _KeyOfValue, 02401 typename _Compare, typename _Alloc> 02402 template<typename... _Args> 02403 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 02404 _Compare, _Alloc>::iterator, bool> 02405 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02406 _M_emplace_unique(_Args&&... __args) 02407 { 02408 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02409 02410 __try 02411 { 02412 typedef pair<iterator, bool> _Res; 02413 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 02414 if (__res.second) 02415 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 02416 02417 _M_drop_node(__z); 02418 return _Res(iterator(__res.first), false); 02419 } 02420 __catch(...) 02421 { 02422 _M_drop_node(__z); 02423 __throw_exception_again; 02424 } 02425 } 02426 02427 template<typename _Key, typename _Val, typename _KeyOfValue, 02428 typename _Compare, typename _Alloc> 02429 template<typename... _Args> 02430 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02431 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02432 _M_emplace_equal(_Args&&... __args) 02433 { 02434 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02435 02436 __try 02437 { 02438 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 02439 return _M_insert_node(__res.first, __res.second, __z); 02440 } 02441 __catch(...) 02442 { 02443 _M_drop_node(__z); 02444 __throw_exception_again; 02445 } 02446 } 02447 02448 template<typename _Key, typename _Val, typename _KeyOfValue, 02449 typename _Compare, typename _Alloc> 02450 template<typename... _Args> 02451 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02452 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02453 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 02454 { 02455 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02456 02457 __try 02458 { 02459 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 02460 02461 if (__res.second) 02462 return _M_insert_node(__res.first, __res.second, __z); 02463 02464 _M_drop_node(__z); 02465 return iterator(__res.first); 02466 } 02467 __catch(...) 02468 { 02469 _M_drop_node(__z); 02470 __throw_exception_again; 02471 } 02472 } 02473 02474 template<typename _Key, typename _Val, typename _KeyOfValue, 02475 typename _Compare, typename _Alloc> 02476 template<typename... _Args> 02477 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 02478 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02479 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 02480 { 02481 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 02482 02483 __try 02484 { 02485 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 02486 02487 if (__res.second) 02488 return _M_insert_node(__res.first, __res.second, __z); 02489 02490 return _M_insert_equal_lower_node(__z); 02491 } 02492 __catch(...) 02493 { 02494 _M_drop_node(__z); 02495 __throw_exception_again; 02496 } 02497 } 02498 #endif 02499 02500 02501 template<typename _Key, typename _Val, typename _KeyOfValue, 02502 typename _Compare, typename _Alloc> 02503 void 02504 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02505 _M_erase_aux(const_iterator __position) 02506 { 02507 _Link_type __y = 02508 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 02509 (const_cast<_Base_ptr>(__position._M_node), 02510 this->_M_impl._M_header)); 02511 _M_drop_node(__y); 02512 --_M_impl._M_node_count; 02513 } 02514 02515 template<typename _Key, typename _Val, typename _KeyOfValue, 02516 typename _Compare, typename _Alloc> 02517 void 02518 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02519 _M_erase_aux(const_iterator __first, const_iterator __last) 02520 { 02521 if (__first == begin() && __last == end()) 02522 clear(); 02523 else 02524 while (__first != __last) 02525 _M_erase_aux(__first++); 02526 } 02527 02528 template<typename _Key, typename _Val, typename _KeyOfValue, 02529 typename _Compare, typename _Alloc> 02530 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 02531 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02532 erase(const _Key& __x) 02533 { 02534 pair<iterator, iterator> __p = equal_range(__x); 02535 const size_type __old_size = size(); 02536 _M_erase_aux(__p.first, __p.second); 02537 return __old_size - size(); 02538 } 02539 02540 template<typename _Key, typename _Val, typename _KeyOfValue, 02541 typename _Compare, typename _Alloc> 02542 void 02543 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02544 erase(const _Key* __first, const _Key* __last) 02545 { 02546 while (__first != __last) 02547 erase(*__first++); 02548 } 02549 02550 template<typename _Key, typename _Val, typename _KeyOfValue, 02551 typename _Compare, typename _Alloc> 02552 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02553 _Compare, _Alloc>::iterator 02554 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02555 find(const _Key& __k) 02556 { 02557 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 02558 return (__j == end() 02559 || _M_impl._M_key_compare(__k, 02560 _S_key(__j._M_node))) ? end() : __j; 02561 } 02562 02563 template<typename _Key, typename _Val, typename _KeyOfValue, 02564 typename _Compare, typename _Alloc> 02565 typename _Rb_tree<_Key, _Val, _KeyOfValue, 02566 _Compare, _Alloc>::const_iterator 02567 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02568 find(const _Key& __k) const 02569 { 02570 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 02571 return (__j == end() 02572 || _M_impl._M_key_compare(__k, 02573 _S_key(__j._M_node))) ? end() : __j; 02574 } 02575 02576 template<typename _Key, typename _Val, typename _KeyOfValue, 02577 typename _Compare, typename _Alloc> 02578 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 02579 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 02580 count(const _Key& __k) const 02581 { 02582 pair<const_iterator, const_iterator> __p = equal_range(__k); 02583 const size_type __n = std::distance(__p.first, __p.second); 02584 return __n; 02585 } 02586 02587 _GLIBCXX_PURE unsigned int 02588 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 02589 const _Rb_tree_node_base* __root) throw (); 02590 02591 template<typename _Key, typename _Val, typename _KeyOfValue, 02592 typename _Compare, typename _Alloc> 02593 bool 02594 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 02595 { 02596 if (_M_impl._M_node_count == 0 || begin() == end()) 02597 return _M_impl._M_node_count == 0 && begin() == end() 02598 && this->_M_impl._M_header._M_left == _M_end() 02599 && this->_M_impl._M_header._M_right == _M_end(); 02600 02601 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 02602 for (const_iterator __it = begin(); __it != end(); ++__it) 02603 { 02604 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 02605 _Const_Link_type __L = _S_left(__x); 02606 _Const_Link_type __R = _S_right(__x); 02607 02608 if (__x->_M_color == _S_red) 02609 if ((__L && __L->_M_color == _S_red) 02610 || (__R && __R->_M_color == _S_red)) 02611 return false; 02612 02613 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 02614 return false; 02615 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 02616 return false; 02617 02618 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 02619 return false; 02620 } 02621 02622 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 02623 return false; 02624 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 02625 return false; 02626 return true; 02627 } 02628 02629 #if __cplusplus > 201402L 02630 // Allow access to internals of compatible _Rb_tree specializations. 02631 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1, 02632 typename _Alloc, typename _Cmp2> 02633 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>, 02634 _Cmp2> 02635 { 02636 private: 02637 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>; 02638 02639 static auto& 02640 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree) 02641 { return __tree._M_impl; } 02642 }; 02643 #endif // C++17 02644 02645 _GLIBCXX_END_NAMESPACE_VERSION 02646 } // namespace 02647 02648 #endif