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