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