1 // RB tree implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2018 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1996,1997 28 * Silicon Graphics Computer Systems, Inc. 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Silicon Graphics makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1994 40 * Hewlett-Packard Company 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Hewlett-Packard Company makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 * 50 * 51 */ 52 53 /** @file bits/stl_tree.h 54 * This is an internal header file, included by other library headers. 55 * Do not attempt to use it directly. @headername{map,set} 56 */ 57 58 #ifndef _STL_TREE_H 59 #define _STL_TREE_H 1 60 61 #pragma GCC system_header 62 63 #include <bits/stl_algobase.h> 64 #include <bits/allocator.h> 65 #include <bits/stl_function.h> 66 #include <bits/cpp_type_traits.h> 67 #include <ext/alloc_traits.h> 68 #if __cplusplus >= 201103L 69 # include <ext/aligned_buffer.h> 70 #endif 71 #if __cplusplus > 201402L 72 # include <bits/node_handle.h> 73 #endif 74 75 namespace std _GLIBCXX_VISIBILITY(default) 76 { 77 _GLIBCXX_BEGIN_NAMESPACE_VERSION 78 79 #if __cplusplus > 201103L 80 # define __cpp_lib_generic_associative_lookup 201304 81 #endif 82 83 // Red-black tree class, designed for use in implementing STL 84 // associative containers (set, multiset, map, and multimap). The 85 // insertion and deletion algorithms are based on those in Cormen, 86 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 87 // 1990), except that 88 // 89 // (1) the header cell is maintained with links not only to the root 90 // but also to the leftmost node of the tree, to enable constant 91 // time begin(), and to the rightmost node of the tree, to enable 92 // linear time performance when used with the generic set algorithms 93 // (set_union, etc.) 94 // 95 // (2) when a node being deleted has two children its successor node 96 // is relinked into its place, rather than copied, so that the only 97 // iterators invalidated are those referring to the deleted node. 98 99 enum _Rb_tree_color { _S_red = false, _S_black = true }; 100 101 struct _Rb_tree_node_base 102 { 103 typedef _Rb_tree_node_base* _Base_ptr; 104 typedef const _Rb_tree_node_base* _Const_Base_ptr; 105 106 _Rb_tree_color _M_color; 107 _Base_ptr _M_parent; 108 _Base_ptr _M_left; 109 _Base_ptr _M_right; 110 111 static _Base_ptr 112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 113 { 114 while (__x->_M_left != 0) __x = __x->_M_left; 115 return __x; 116 } 117 118 static _Const_Base_ptr 119 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 120 { 121 while (__x->_M_left != 0) __x = __x->_M_left; 122 return __x; 123 } 124 125 static _Base_ptr 126 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 127 { 128 while (__x->_M_right != 0) __x = __x->_M_right; 129 return __x; 130 } 131 132 static _Const_Base_ptr 133 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 134 { 135 while (__x->_M_right != 0) __x = __x->_M_right; 136 return __x; 137 } 138 }; 139 140 // Helper type offering value initialization guarantee on the compare functor. 141 template<typename _Key_compare> 142 struct _Rb_tree_key_compare 143 { 144 _Key_compare _M_key_compare; 145 146 _Rb_tree_key_compare() 147 _GLIBCXX_NOEXCEPT_IF( 148 is_nothrow_default_constructible<_Key_compare>::value) 149 : _M_key_compare() 150 { } 151 152 _Rb_tree_key_compare(const _Key_compare& __comp) 153 : _M_key_compare(__comp) 154 { } 155 156 #if __cplusplus >= 201103L 157 // Copy constructor added for consistency with C++98 mode. 158 _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default; 159 160 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x) 161 noexcept(is_nothrow_copy_constructible<_Key_compare>::value) 162 : _M_key_compare(__x._M_key_compare) 163 { } 164 #endif 165 }; 166 167 // Helper type to manage default initialization of node count and header. 168 struct _Rb_tree_header 169 { 170 _Rb_tree_node_base _M_header; 171 size_t _M_node_count; // Keeps track of size of tree. 172 173 _Rb_tree_header() _GLIBCXX_NOEXCEPT 174 { 175 _M_header._M_color = _S_red; 176 _M_reset(); 177 } 178 179 #if __cplusplus >= 201103L 180 _Rb_tree_header(_Rb_tree_header&& __x) noexcept 181 { 182 if (__x._M_header._M_parent != nullptr) 183 _M_move_data(__x); 184 else 185 { 186 _M_header._M_color = _S_red; 187 _M_reset(); 188 } 189 } 190 #endif 191 192 void 193 _M_move_data(_Rb_tree_header& __from) 194 { 195 _M_header._M_color = __from._M_header._M_color; 196 _M_header._M_parent = __from._M_header._M_parent; 197 _M_header._M_left = __from._M_header._M_left; 198 _M_header._M_right = __from._M_header._M_right; 199 _M_header._M_parent->_M_parent = &_M_header; 200 _M_node_count = __from._M_node_count; 201 202 __from._M_reset(); 203 } 204 205 void 206 _M_reset() 207 { 208 _M_header._M_parent = 0; 209 _M_header._M_left = &_M_header; 210 _M_header._M_right = &_M_header; 211 _M_node_count = 0; 212 } 213 }; 214 215 template<typename _Val> 216 struct _Rb_tree_node : public _Rb_tree_node_base 217 { 218 typedef _Rb_tree_node<_Val>* _Link_type; 219 220 #if __cplusplus < 201103L 221 _Val _M_value_field; 222 223 _Val* 224 _M_valptr() 225 { return std::__addressof(_M_value_field); } 226 227 const _Val* 228 _M_valptr() const 229 { return std::__addressof(_M_value_field); } 230 #else 231 __gnu_cxx::__aligned_membuf<_Val> _M_storage; 232 233 _Val* 234 _M_valptr() 235 { return _M_storage._M_ptr(); } 236 237 const _Val* 238 _M_valptr() const 239 { return _M_storage._M_ptr(); } 240 #endif 241 }; 242 243 _GLIBCXX_PURE _Rb_tree_node_base* 244 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 245 246 _GLIBCXX_PURE const _Rb_tree_node_base* 247 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); 248 249 _GLIBCXX_PURE _Rb_tree_node_base* 250 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 251 252 _GLIBCXX_PURE const _Rb_tree_node_base* 253 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); 254 255 template<typename _Tp> 256 struct _Rb_tree_iterator 257 { 258 typedef _Tp value_type; 259 typedef _Tp& reference; 260 typedef _Tp* pointer; 261 262 typedef bidirectional_iterator_tag iterator_category; 263 typedef ptrdiff_t difference_type; 264 265 typedef _Rb_tree_iterator<_Tp> _Self; 266 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 267 typedef _Rb_tree_node<_Tp>* _Link_type; 268 269 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 270 : _M_node() { } 271 272 explicit 273 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 274 : _M_node(__x) { } 275 276 reference 277 operator*() const _GLIBCXX_NOEXCEPT 278 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 279 280 pointer 281 operator->() const _GLIBCXX_NOEXCEPT 282 { return static_cast<_Link_type> (_M_node)->_M_valptr(); } 283 284 _Self& 285 operator++() _GLIBCXX_NOEXCEPT 286 { 287 _M_node = _Rb_tree_increment(_M_node); 288 return *this; 289 } 290 291 _Self 292 operator++(int) _GLIBCXX_NOEXCEPT 293 { 294 _Self __tmp = *this; 295 _M_node = _Rb_tree_increment(_M_node); 296 return __tmp; 297 } 298 299 _Self& 300 operator--() _GLIBCXX_NOEXCEPT 301 { 302 _M_node = _Rb_tree_decrement(_M_node); 303 return *this; 304 } 305 306 _Self 307 operator--(int) _GLIBCXX_NOEXCEPT 308 { 309 _Self __tmp = *this; 310 _M_node = _Rb_tree_decrement(_M_node); 311 return __tmp; 312 } 313 314 bool 315 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 316 { return _M_node == __x._M_node; } 317 318 bool 319 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 320 { return _M_node != __x._M_node; } 321 322 _Base_ptr _M_node; 323 }; 324 325 template<typename _Tp> 326 struct _Rb_tree_const_iterator 327 { 328 typedef _Tp value_type; 329 typedef const _Tp& reference; 330 typedef const _Tp* pointer; 331 332 typedef _Rb_tree_iterator<_Tp> iterator; 333 334 typedef bidirectional_iterator_tag iterator_category; 335 typedef ptrdiff_t difference_type; 336 337 typedef _Rb_tree_const_iterator<_Tp> _Self; 338 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; 339 typedef const _Rb_tree_node<_Tp>* _Link_type; 340 341 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 342 : _M_node() { } 343 344 explicit 345 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 346 : _M_node(__x) { } 347 348 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 349 : _M_node(__it._M_node) { } 350 351 iterator 352 _M_const_cast() const _GLIBCXX_NOEXCEPT 353 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); } 354 355 reference 356 operator*() const _GLIBCXX_NOEXCEPT 357 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } 358 359 pointer 360 operator->() const _GLIBCXX_NOEXCEPT 361 { return static_cast<_Link_type>(_M_node)->_M_valptr(); } 362 363 _Self& 364 operator++() _GLIBCXX_NOEXCEPT 365 { 366 _M_node = _Rb_tree_increment(_M_node); 367 return *this; 368 } 369 370 _Self 371 operator++(int) _GLIBCXX_NOEXCEPT 372 { 373 _Self __tmp = *this; 374 _M_node = _Rb_tree_increment(_M_node); 375 return __tmp; 376 } 377 378 _Self& 379 operator--() _GLIBCXX_NOEXCEPT 380 { 381 _M_node = _Rb_tree_decrement(_M_node); 382 return *this; 383 } 384 385 _Self 386 operator--(int) _GLIBCXX_NOEXCEPT 387 { 388 _Self __tmp = *this; 389 _M_node = _Rb_tree_decrement(_M_node); 390 return __tmp; 391 } 392 393 bool 394 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT 395 { return _M_node == __x._M_node; } 396 397 bool 398 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT 399 { return _M_node != __x._M_node; } 400 401 _Base_ptr _M_node; 402 }; 403 404 template<typename _Val> 405 inline bool 406 operator==(const _Rb_tree_iterator<_Val>& __x, 407 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 408 { return __x._M_node == __y._M_node; } 409 410 template<typename _Val> 411 inline bool 412 operator!=(const _Rb_tree_iterator<_Val>& __x, 413 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT 414 { return __x._M_node != __y._M_node; } 415 416 void 417 _Rb_tree_insert_and_rebalance(const bool __insert_left, 418 _Rb_tree_node_base* __x, 419 _Rb_tree_node_base* __p, 420 _Rb_tree_node_base& __header) throw (); 421 422 _Rb_tree_node_base* 423 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 424 _Rb_tree_node_base& __header) throw (); 425 426 #if __cplusplus > 201103L 427 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>> 428 struct __has_is_transparent 429 { }; 430 431 template<typename _Cmp, typename _SfinaeType> 432 struct __has_is_transparent<_Cmp, _SfinaeType, 433 __void_t<typename _Cmp::is_transparent>> 434 { typedef void type; }; 435 #endif 436 437 #if __cplusplus > 201402L 438 template<typename _Tree1, typename _Cmp2> 439 struct _Rb_tree_merge_helper { }; 440 #endif 441 442 template<typename _Key, typename _Val, typename _KeyOfValue, 443 typename _Compare, typename _Alloc = allocator<_Val> > 444 class _Rb_tree 445 { 446 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 447 rebind<_Rb_tree_node<_Val> >::other _Node_allocator; 448 449 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; 450 451 #if __cplusplus >= 201103L 452 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{}, 453 "comparison object must be invocable with two arguments of key type"); 454 # if __cplusplus >= 201703L 455 // _GLIBCXX_RESOLVE_LIB_DEFECTS 456 // 2542. Missing const requirements for associative containers 457 static_assert(is_invocable_v<const _Compare&, const _Key&, const _Key&>, 458 "comparison object must be invocable as const"); 459 # endif // C++17 460 #endif // C++11 461 462 protected: 463 typedef _Rb_tree_node_base* _Base_ptr; 464 typedef const _Rb_tree_node_base* _Const_Base_ptr; 465 typedef _Rb_tree_node<_Val>* _Link_type; 466 typedef const _Rb_tree_node<_Val>* _Const_Link_type; 467 468 private: 469 // Functor recycling a pool of nodes and using allocation once the pool 470 // is empty. 471 struct _Reuse_or_alloc_node 472 { 473 _Reuse_or_alloc_node(_Rb_tree& __t) 474 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t) 475 { 476 if (_M_root) 477 { 478 _M_root->_M_parent = 0; 479 480 if (_M_nodes->_M_left) 481 _M_nodes = _M_nodes->_M_left; 482 } 483 else 484 _M_nodes = 0; 485 } 486 487 #if __cplusplus >= 201103L 488 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; 489 #endif 490 491 ~_Reuse_or_alloc_node() 492 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } 493 494 template<typename _Arg> 495 _Link_type 496 #if __cplusplus < 201103L 497 operator()(const _Arg& __arg) 498 #else 499 operator()(_Arg&& __arg) 500 #endif 501 { 502 _Link_type __node = static_cast<_Link_type>(_M_extract()); 503 if (__node) 504 { 505 _M_t._M_destroy_node(__node); 506 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)); 507 return __node; 508 } 509 510 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); 511 } 512 513 private: 514 _Base_ptr 515 _M_extract() 516 { 517 if (!_M_nodes) 518 return _M_nodes; 519 520 _Base_ptr __node = _M_nodes; 521 _M_nodes = _M_nodes->_M_parent; 522 if (_M_nodes) 523 { 524 if (_M_nodes->_M_right == __node) 525 { 526 _M_nodes->_M_right = 0; 527 528 if (_M_nodes->_M_left) 529 { 530 _M_nodes = _M_nodes->_M_left; 531 532 while (_M_nodes->_M_right) 533 _M_nodes = _M_nodes->_M_right; 534 535 if (_M_nodes->_M_left) 536 _M_nodes = _M_nodes->_M_left; 537 } 538 } 539 else // __node is on the left. 540 _M_nodes->_M_left = 0; 541 } 542 else 543 _M_root = 0; 544 545 return __node; 546 } 547 548 _Base_ptr _M_root; 549 _Base_ptr _M_nodes; 550 _Rb_tree& _M_t; 551 }; 552 553 // Functor similar to the previous one but without any pool of nodes to 554 // recycle. 555 struct _Alloc_node 556 { 557 _Alloc_node(_Rb_tree& __t) 558 : _M_t(__t) { } 559 560 template<typename _Arg> 561 _Link_type 562 #if __cplusplus < 201103L 563 operator()(const _Arg& __arg) const 564 #else 565 operator()(_Arg&& __arg) const 566 #endif 567 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } 568 569 private: 570 _Rb_tree& _M_t; 571 }; 572 573 public: 574 typedef _Key key_type; 575 typedef _Val value_type; 576 typedef value_type* pointer; 577 typedef const value_type* const_pointer; 578 typedef value_type& reference; 579 typedef const value_type& const_reference; 580 typedef size_t size_type; 581 typedef ptrdiff_t difference_type; 582 typedef _Alloc allocator_type; 583 584 _Node_allocator& 585 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 586 { return this->_M_impl; } 587 588 const _Node_allocator& 589 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 590 { return this->_M_impl; } 591 592 allocator_type 593 get_allocator() const _GLIBCXX_NOEXCEPT 594 { return allocator_type(_M_get_Node_allocator()); } 595 596 protected: 597 _Link_type 598 _M_get_node() 599 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } 600 601 void 602 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT 603 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } 604 605 #if __cplusplus < 201103L 606 void 607 _M_construct_node(_Link_type __node, const value_type& __x) 608 { 609 __try 610 { get_allocator().construct(__node->_M_valptr(), __x); } 611 __catch(...) 612 { 613 _M_put_node(__node); 614 __throw_exception_again; 615 } 616 } 617 618 _Link_type 619 _M_create_node(const value_type& __x) 620 { 621 _Link_type __tmp = _M_get_node(); 622 _M_construct_node(__tmp, __x); 623 return __tmp; 624 } 625 626 void 627 _M_destroy_node(_Link_type __p) 628 { get_allocator().destroy(__p->_M_valptr()); } 629 #else 630 template<typename... _Args> 631 void 632 _M_construct_node(_Link_type __node, _Args&&... __args) 633 { 634 __try 635 { 636 ::new(__node) _Rb_tree_node<_Val>; 637 _Alloc_traits::construct(_M_get_Node_allocator(), 638 __node->_M_valptr(), 639 std::forward<_Args>(__args)...); 640 } 641 __catch(...) 642 { 643 __node->~_Rb_tree_node<_Val>(); 644 _M_put_node(__node); 645 __throw_exception_again; 646 } 647 } 648 649 template<typename... _Args> 650 _Link_type 651 _M_create_node(_Args&&... __args) 652 { 653 _Link_type __tmp = _M_get_node(); 654 _M_construct_node(__tmp, std::forward<_Args>(__args)...); 655 return __tmp; 656 } 657 658 void 659 _M_destroy_node(_Link_type __p) noexcept 660 { 661 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 662 __p->~_Rb_tree_node<_Val>(); 663 } 664 #endif 665 666 void 667 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT 668 { 669 _M_destroy_node(__p); 670 _M_put_node(__p); 671 } 672 673 template<typename _NodeGen> 674 _Link_type 675 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) 676 { 677 _Link_type __tmp = __node_gen(*__x->_M_valptr()); 678 __tmp->_M_color = __x->_M_color; 679 __tmp->_M_left = 0; 680 __tmp->_M_right = 0; 681 return __tmp; 682 } 683 684 protected: 685 #if _GLIBCXX_INLINE_VERSION 686 template<typename _Key_compare> 687 #else 688 // Unused _Is_pod_comparator is kept as it is part of mangled name. 689 template<typename _Key_compare, 690 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)> 691 #endif 692 struct _Rb_tree_impl 693 : public _Node_allocator 694 , public _Rb_tree_key_compare<_Key_compare> 695 , public _Rb_tree_header 696 { 697 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare; 698 699 _Rb_tree_impl() 700 _GLIBCXX_NOEXCEPT_IF( 701 is_nothrow_default_constructible<_Node_allocator>::value 702 && is_nothrow_default_constructible<_Base_key_compare>::value ) 703 : _Node_allocator() 704 { } 705 706 _Rb_tree_impl(const _Rb_tree_impl& __x) 707 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x)) 708 , _Base_key_compare(__x._M_key_compare) 709 { } 710 711 #if __cplusplus < 201103L 712 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 713 : _Node_allocator(__a), _Base_key_compare(__comp) 714 { } 715 #else 716 _Rb_tree_impl(_Rb_tree_impl&&) = default; 717 718 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 719 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp) 720 { } 721 #endif 722 }; 723 724 _Rb_tree_impl<_Compare> _M_impl; 725 726 protected: 727 _Base_ptr& 728 _M_root() _GLIBCXX_NOEXCEPT 729 { return this->_M_impl._M_header._M_parent; } 730 731 _Const_Base_ptr 732 _M_root() const _GLIBCXX_NOEXCEPT 733 { return this->_M_impl._M_header._M_parent; } 734 735 _Base_ptr& 736 _M_leftmost() _GLIBCXX_NOEXCEPT 737 { return this->_M_impl._M_header._M_left; } 738 739 _Const_Base_ptr 740 _M_leftmost() const _GLIBCXX_NOEXCEPT 741 { return this->_M_impl._M_header._M_left; } 742 743 _Base_ptr& 744 _M_rightmost() _GLIBCXX_NOEXCEPT 745 { return this->_M_impl._M_header._M_right; } 746 747 _Const_Base_ptr 748 _M_rightmost() const _GLIBCXX_NOEXCEPT 749 { return this->_M_impl._M_header._M_right; } 750 751 _Link_type 752 _M_begin() _GLIBCXX_NOEXCEPT 753 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } 754 755 _Const_Link_type 756 _M_begin() const _GLIBCXX_NOEXCEPT 757 { 758 return static_cast<_Const_Link_type> 759 (this->_M_impl._M_header._M_parent); 760 } 761 762 _Base_ptr 763 _M_end() _GLIBCXX_NOEXCEPT 764 { return &this->_M_impl._M_header; } 765 766 _Const_Base_ptr 767 _M_end() const _GLIBCXX_NOEXCEPT 768 { return &this->_M_impl._M_header; } 769 770 static const_reference 771 _S_value(_Const_Link_type __x) 772 { return *__x->_M_valptr(); } 773 774 static const _Key& 775 _S_key(_Const_Link_type __x) 776 { return _KeyOfValue()(_S_value(__x)); } 777 778 static _Link_type 779 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 780 { return static_cast<_Link_type>(__x->_M_left); } 781 782 static _Const_Link_type 783 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 784 { return static_cast<_Const_Link_type>(__x->_M_left); } 785 786 static _Link_type 787 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 788 { return static_cast<_Link_type>(__x->_M_right); } 789 790 static _Const_Link_type 791 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 792 { return static_cast<_Const_Link_type>(__x->_M_right); } 793 794 static const_reference 795 _S_value(_Const_Base_ptr __x) 796 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); } 797 798 static const _Key& 799 _S_key(_Const_Base_ptr __x) 800 { return _KeyOfValue()(_S_value(__x)); } 801 802 static _Base_ptr 803 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 804 { return _Rb_tree_node_base::_S_minimum(__x); } 805 806 static _Const_Base_ptr 807 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 808 { return _Rb_tree_node_base::_S_minimum(__x); } 809 810 static _Base_ptr 811 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 812 { return _Rb_tree_node_base::_S_maximum(__x); } 813 814 static _Const_Base_ptr 815 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT 816 { return _Rb_tree_node_base::_S_maximum(__x); } 817 818 public: 819 typedef _Rb_tree_iterator<value_type> iterator; 820 typedef _Rb_tree_const_iterator<value_type> const_iterator; 821 822 typedef std::reverse_iterator<iterator> reverse_iterator; 823 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 824 825 #if __cplusplus > 201402L 826 using node_type = _Node_handle<_Key, _Val, _Node_allocator>; 827 using insert_return_type = _Node_insert_return< 828 conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>, 829 node_type>; 830 #endif 831 832 pair<_Base_ptr, _Base_ptr> 833 _M_get_insert_unique_pos(const key_type& __k); 834 835 pair<_Base_ptr, _Base_ptr> 836 _M_get_insert_equal_pos(const key_type& __k); 837 838 pair<_Base_ptr, _Base_ptr> 839 _M_get_insert_hint_unique_pos(const_iterator __pos, 840 const key_type& __k); 841 842 pair<_Base_ptr, _Base_ptr> 843 _M_get_insert_hint_equal_pos(const_iterator __pos, 844 const key_type& __k); 845 846 private: 847 #if __cplusplus >= 201103L 848 template<typename _Arg, typename _NodeGen> 849 iterator 850 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); 851 852 iterator 853 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); 854 855 template<typename _Arg> 856 iterator 857 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 858 859 template<typename _Arg> 860 iterator 861 _M_insert_equal_lower(_Arg&& __x); 862 863 iterator 864 _M_insert_lower_node(_Base_ptr __p, _Link_type __z); 865 866 iterator 867 _M_insert_equal_lower_node(_Link_type __z); 868 #else 869 template<typename _NodeGen> 870 iterator 871 _M_insert_(_Base_ptr __x, _Base_ptr __y, 872 const value_type& __v, _NodeGen&); 873 874 // _GLIBCXX_RESOLVE_LIB_DEFECTS 875 // 233. Insertion hints in associative containers. 876 iterator 877 _M_insert_lower(_Base_ptr __y, const value_type& __v); 878 879 iterator 880 _M_insert_equal_lower(const value_type& __x); 881 #endif 882 883 template<typename _NodeGen> 884 _Link_type 885 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); 886 887 template<typename _NodeGen> 888 _Link_type 889 _M_copy(const _Rb_tree& __x, _NodeGen& __gen) 890 { 891 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen); 892 _M_leftmost() = _S_minimum(__root); 893 _M_rightmost() = _S_maximum(__root); 894 _M_impl._M_node_count = __x._M_impl._M_node_count; 895 return __root; 896 } 897 898 _Link_type 899 _M_copy(const _Rb_tree& __x) 900 { 901 _Alloc_node __an(*this); 902 return _M_copy(__x, __an); 903 } 904 905 void 906 _M_erase(_Link_type __x); 907 908 iterator 909 _M_lower_bound(_Link_type __x, _Base_ptr __y, 910 const _Key& __k); 911 912 const_iterator 913 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 914 const _Key& __k) const; 915 916 iterator 917 _M_upper_bound(_Link_type __x, _Base_ptr __y, 918 const _Key& __k); 919 920 const_iterator 921 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 922 const _Key& __k) const; 923 924 public: 925 // allocation/deallocation 926 #if __cplusplus < 201103L 927 _Rb_tree() { } 928 #else 929 _Rb_tree() = default; 930 #endif 931 932 _Rb_tree(const _Compare& __comp, 933 const allocator_type& __a = allocator_type()) 934 : _M_impl(__comp, _Node_allocator(__a)) { } 935 936 _Rb_tree(const _Rb_tree& __x) 937 : _M_impl(__x._M_impl) 938 { 939 if (__x._M_root() != 0) 940 _M_root() = _M_copy(__x); 941 } 942 943 #if __cplusplus >= 201103L 944 _Rb_tree(const allocator_type& __a) 945 : _M_impl(_Compare(), _Node_allocator(__a)) 946 { } 947 948 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 949 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 950 { 951 if (__x._M_root() != nullptr) 952 _M_root() = _M_copy(__x); 953 } 954 955 _Rb_tree(_Rb_tree&&) = default; 956 957 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 958 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 959 { } 960 961 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); 962 #endif 963 964 ~_Rb_tree() _GLIBCXX_NOEXCEPT 965 { _M_erase(_M_begin()); } 966 967 _Rb_tree& 968 operator=(const _Rb_tree& __x); 969 970 // Accessors. 971 _Compare 972 key_comp() const 973 { return _M_impl._M_key_compare; } 974 975 iterator 976 begin() _GLIBCXX_NOEXCEPT 977 { return iterator(this->_M_impl._M_header._M_left); } 978 979 const_iterator 980 begin() const _GLIBCXX_NOEXCEPT 981 { return const_iterator(this->_M_impl._M_header._M_left); } 982 983 iterator 984 end() _GLIBCXX_NOEXCEPT 985 { return iterator(&this->_M_impl._M_header); } 986 987 const_iterator 988 end() const _GLIBCXX_NOEXCEPT 989 { return const_iterator(&this->_M_impl._M_header); } 990 991 reverse_iterator 992 rbegin() _GLIBCXX_NOEXCEPT 993 { return reverse_iterator(end()); } 994 995 const_reverse_iterator 996 rbegin() const _GLIBCXX_NOEXCEPT 997 { return const_reverse_iterator(end()); } 998 999 reverse_iterator 1000 rend() _GLIBCXX_NOEXCEPT 1001 { return reverse_iterator(begin()); } 1002 1003 const_reverse_iterator 1004 rend() const _GLIBCXX_NOEXCEPT 1005 { return const_reverse_iterator(begin()); } 1006 1007 bool 1008 empty() const _GLIBCXX_NOEXCEPT 1009 { return _M_impl._M_node_count == 0; } 1010 1011 size_type 1012 size() const _GLIBCXX_NOEXCEPT 1013 { return _M_impl._M_node_count; } 1014 1015 size_type 1016 max_size() const _GLIBCXX_NOEXCEPT 1017 { return _Alloc_traits::max_size(_M_get_Node_allocator()); } 1018 1019 void 1020 swap(_Rb_tree& __t) 1021 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value); 1022 1023 // Insert/erase. 1024 #if __cplusplus >= 201103L 1025 template<typename _Arg> 1026 pair<iterator, bool> 1027 _M_insert_unique(_Arg&& __x); 1028 1029 template<typename _Arg> 1030 iterator 1031 _M_insert_equal(_Arg&& __x); 1032 1033 template<typename _Arg, typename _NodeGen> 1034 iterator 1035 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); 1036 1037 template<typename _Arg> 1038 iterator 1039 _M_insert_unique_(const_iterator __pos, _Arg&& __x) 1040 { 1041 _Alloc_node __an(*this); 1042 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); 1043 } 1044 1045 template<typename _Arg, typename _NodeGen> 1046 iterator 1047 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); 1048 1049 template<typename _Arg> 1050 iterator 1051 _M_insert_equal_(const_iterator __pos, _Arg&& __x) 1052 { 1053 _Alloc_node __an(*this); 1054 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); 1055 } 1056 1057 template<typename... _Args> 1058 pair<iterator, bool> 1059 _M_emplace_unique(_Args&&... __args); 1060 1061 template<typename... _Args> 1062 iterator 1063 _M_emplace_equal(_Args&&... __args); 1064 1065 template<typename... _Args> 1066 iterator 1067 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 1068 1069 template<typename... _Args> 1070 iterator 1071 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 1072 #else 1073 pair<iterator, bool> 1074 _M_insert_unique(const value_type& __x); 1075 1076 iterator 1077 _M_insert_equal(const value_type& __x); 1078 1079 template<typename _NodeGen> 1080 iterator 1081 _M_insert_unique_(const_iterator __pos, const value_type& __x, 1082 _NodeGen&); 1083 1084 iterator 1085 _M_insert_unique_(const_iterator __pos, const value_type& __x) 1086 { 1087 _Alloc_node __an(*this); 1088 return _M_insert_unique_(__pos, __x, __an); 1089 } 1090 1091 template<typename _NodeGen> 1092 iterator 1093 _M_insert_equal_(const_iterator __pos, const value_type& __x, 1094 _NodeGen&); 1095 iterator 1096 _M_insert_equal_(const_iterator __pos, const value_type& __x) 1097 { 1098 _Alloc_node __an(*this); 1099 return _M_insert_equal_(__pos, __x, __an); 1100 } 1101 #endif 1102 1103 template<typename _InputIterator> 1104 void 1105 _M_insert_unique(_InputIterator __first, _InputIterator __last); 1106 1107 template<typename _InputIterator> 1108 void 1109 _M_insert_equal(_InputIterator __first, _InputIterator __last); 1110 1111 private: 1112 void 1113 _M_erase_aux(const_iterator __position); 1114 1115 void 1116 _M_erase_aux(const_iterator __first, const_iterator __last); 1117 1118 public: 1119 #if __cplusplus >= 201103L 1120 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1121 // DR 130. Associative erase should return an iterator. 1122 _GLIBCXX_ABI_TAG_CXX11 1123 iterator 1124 erase(const_iterator __position) 1125 { 1126 __glibcxx_assert(__position != end()); 1127 const_iterator __result = __position; 1128 ++__result; 1129 _M_erase_aux(__position); 1130 return __result._M_const_cast(); 1131 } 1132 1133 // LWG 2059. 1134 _GLIBCXX_ABI_TAG_CXX11 1135 iterator 1136 erase(iterator __position) 1137 { 1138 __glibcxx_assert(__position != end()); 1139 iterator __result = __position; 1140 ++__result; 1141 _M_erase_aux(__position); 1142 return __result; 1143 } 1144 #else 1145 void 1146 erase(iterator __position) 1147 { 1148 __glibcxx_assert(__position != end()); 1149 _M_erase_aux(__position); 1150 } 1151 1152 void 1153 erase(const_iterator __position) 1154 { 1155 __glibcxx_assert(__position != end()); 1156 _M_erase_aux(__position); 1157 } 1158 #endif 1159 size_type 1160 erase(const key_type& __x); 1161 1162 #if __cplusplus >= 201103L 1163 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1164 // DR 130. Associative erase should return an iterator. 1165 _GLIBCXX_ABI_TAG_CXX11 1166 iterator 1167 erase(const_iterator __first, const_iterator __last) 1168 { 1169 _M_erase_aux(__first, __last); 1170 return __last._M_const_cast(); 1171 } 1172 #else 1173 void 1174 erase(iterator __first, iterator __last) 1175 { _M_erase_aux(__first, __last); } 1176 1177 void 1178 erase(const_iterator __first, const_iterator __last) 1179 { _M_erase_aux(__first, __last); } 1180 #endif 1181 void 1182 erase(const key_type* __first, const key_type* __last); 1183 1184 void 1185 clear() _GLIBCXX_NOEXCEPT 1186 { 1187 _M_erase(_M_begin()); 1188 _M_impl._M_reset(); 1189 } 1190 1191 // Set operations. 1192 iterator 1193 find(const key_type& __k); 1194 1195 const_iterator 1196 find(const key_type& __k) const; 1197 1198 size_type 1199 count(const key_type& __k) const; 1200 1201 iterator 1202 lower_bound(const key_type& __k) 1203 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 1204 1205 const_iterator 1206 lower_bound(const key_type& __k) const 1207 { return _M_lower_bound(_M_begin(), _M_end(), __k); } 1208 1209 iterator 1210 upper_bound(const key_type& __k) 1211 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 1212 1213 const_iterator 1214 upper_bound(const key_type& __k) const 1215 { return _M_upper_bound(_M_begin(), _M_end(), __k); } 1216 1217 pair<iterator, iterator> 1218 equal_range(const key_type& __k); 1219 1220 pair<const_iterator, const_iterator> 1221 equal_range(const key_type& __k) const; 1222 1223 #if __cplusplus > 201103L 1224 template<typename _Kt, 1225 typename _Req = 1226 typename __has_is_transparent<_Compare, _Kt>::type> 1227 iterator 1228 _M_find_tr(const _Kt& __k) 1229 { 1230 const _Rb_tree* __const_this = this; 1231 return __const_this->_M_find_tr(__k)._M_const_cast(); 1232 } 1233 1234 template<typename _Kt, 1235 typename _Req = 1236 typename __has_is_transparent<_Compare, _Kt>::type> 1237 const_iterator 1238 _M_find_tr(const _Kt& __k) const 1239 { 1240 auto __j = _M_lower_bound_tr(__k); 1241 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node))) 1242 __j = end(); 1243 return __j; 1244 } 1245 1246 template<typename _Kt, 1247 typename _Req = 1248 typename __has_is_transparent<_Compare, _Kt>::type> 1249 size_type 1250 _M_count_tr(const _Kt& __k) const 1251 { 1252 auto __p = _M_equal_range_tr(__k); 1253 return std::distance(__p.first, __p.second); 1254 } 1255 1256 template<typename _Kt, 1257 typename _Req = 1258 typename __has_is_transparent<_Compare, _Kt>::type> 1259 iterator 1260 _M_lower_bound_tr(const _Kt& __k) 1261 { 1262 const _Rb_tree* __const_this = this; 1263 return __const_this->_M_lower_bound_tr(__k)._M_const_cast(); 1264 } 1265 1266 template<typename _Kt, 1267 typename _Req = 1268 typename __has_is_transparent<_Compare, _Kt>::type> 1269 const_iterator 1270 _M_lower_bound_tr(const _Kt& __k) const 1271 { 1272 auto __x = _M_begin(); 1273 auto __y = _M_end(); 1274 while (__x != 0) 1275 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1276 { 1277 __y = __x; 1278 __x = _S_left(__x); 1279 } 1280 else 1281 __x = _S_right(__x); 1282 return const_iterator(__y); 1283 } 1284 1285 template<typename _Kt, 1286 typename _Req = 1287 typename __has_is_transparent<_Compare, _Kt>::type> 1288 iterator 1289 _M_upper_bound_tr(const _Kt& __k) 1290 { 1291 const _Rb_tree* __const_this = this; 1292 return __const_this->_M_upper_bound_tr(__k)._M_const_cast(); 1293 } 1294 1295 template<typename _Kt, 1296 typename _Req = 1297 typename __has_is_transparent<_Compare, _Kt>::type> 1298 const_iterator 1299 _M_upper_bound_tr(const _Kt& __k) const 1300 { 1301 auto __x = _M_begin(); 1302 auto __y = _M_end(); 1303 while (__x != 0) 1304 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1305 { 1306 __y = __x; 1307 __x = _S_left(__x); 1308 } 1309 else 1310 __x = _S_right(__x); 1311 return const_iterator(__y); 1312 } 1313 1314 template<typename _Kt, 1315 typename _Req = 1316 typename __has_is_transparent<_Compare, _Kt>::type> 1317 pair<iterator, iterator> 1318 _M_equal_range_tr(const _Kt& __k) 1319 { 1320 const _Rb_tree* __const_this = this; 1321 auto __ret = __const_this->_M_equal_range_tr(__k); 1322 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() }; 1323 } 1324 1325 template<typename _Kt, 1326 typename _Req = 1327 typename __has_is_transparent<_Compare, _Kt>::type> 1328 pair<const_iterator, const_iterator> 1329 _M_equal_range_tr(const _Kt& __k) const 1330 { 1331 auto __low = _M_lower_bound_tr(__k); 1332 auto __high = __low; 1333 auto& __cmp = _M_impl._M_key_compare; 1334 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 1335 ++__high; 1336 return { __low, __high }; 1337 } 1338 #endif 1339 1340 // Debugging. 1341 bool 1342 __rb_verify() const; 1343 1344 #if __cplusplus >= 201103L 1345 _Rb_tree& 1346 operator=(_Rb_tree&&) 1347 noexcept(_Alloc_traits::_S_nothrow_move() 1348 && is_nothrow_move_assignable<_Compare>::value); 1349 1350 template<typename _Iterator> 1351 void 1352 _M_assign_unique(_Iterator, _Iterator); 1353 1354 template<typename _Iterator> 1355 void 1356 _M_assign_equal(_Iterator, _Iterator); 1357 1358 private: 1359 // Move elements from container with equal allocator. 1360 void 1361 _M_move_data(_Rb_tree& __x, std::true_type) 1362 { _M_impl._M_move_data(__x._M_impl); } 1363 1364 // Move elements from container with possibly non-equal allocator, 1365 // which might result in a copy not a move. 1366 void 1367 _M_move_data(_Rb_tree&, std::false_type); 1368 1369 // Move assignment from container with equal allocator. 1370 void 1371 _M_move_assign(_Rb_tree&, std::true_type); 1372 1373 // Move assignment from container with possibly non-equal allocator, 1374 // which might result in a copy not a move. 1375 void 1376 _M_move_assign(_Rb_tree&, std::false_type); 1377 #endif 1378 1379 #if __cplusplus > 201402L 1380 public: 1381 /// Re-insert an extracted node. 1382 insert_return_type 1383 _M_reinsert_node_unique(node_type&& __nh) 1384 { 1385 insert_return_type __ret; 1386 if (__nh.empty()) 1387 __ret.position = end(); 1388 else 1389 { 1390 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 1391 1392 auto __res = _M_get_insert_unique_pos(__nh._M_key()); 1393 if (__res.second) 1394 { 1395 __ret.position 1396 = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 1397 __nh._M_ptr = nullptr; 1398 __ret.inserted = true; 1399 } 1400 else 1401 { 1402 __ret.node = std::move(__nh); 1403 __ret.position = iterator(__res.first); 1404 __ret.inserted = false; 1405 } 1406 } 1407 return __ret; 1408 } 1409 1410 /// Re-insert an extracted node. 1411 iterator 1412 _M_reinsert_node_equal(node_type&& __nh) 1413 { 1414 iterator __ret; 1415 if (__nh.empty()) 1416 __ret = end(); 1417 else 1418 { 1419 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 1420 auto __res = _M_get_insert_equal_pos(__nh._M_key()); 1421 if (__res.second) 1422 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 1423 else 1424 __ret = _M_insert_equal_lower_node(__nh._M_ptr); 1425 __nh._M_ptr = nullptr; 1426 } 1427 return __ret; 1428 } 1429 1430 /// Re-insert an extracted node. 1431 iterator 1432 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh) 1433 { 1434 iterator __ret; 1435 if (__nh.empty()) 1436 __ret = end(); 1437 else 1438 { 1439 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 1440 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key()); 1441 if (__res.second) 1442 { 1443 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 1444 __nh._M_ptr = nullptr; 1445 } 1446 else 1447 __ret = iterator(__res.first); 1448 } 1449 return __ret; 1450 } 1451 1452 /// Re-insert an extracted node. 1453 iterator 1454 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh) 1455 { 1456 iterator __ret; 1457 if (__nh.empty()) 1458 __ret = end(); 1459 else 1460 { 1461 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 1462 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key()); 1463 if (__res.second) 1464 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); 1465 else 1466 __ret = _M_insert_equal_lower_node(__nh._M_ptr); 1467 __nh._M_ptr = nullptr; 1468 } 1469 return __ret; 1470 } 1471 1472 /// Extract a node. 1473 node_type 1474 extract(const_iterator __pos) 1475 { 1476 auto __ptr = _Rb_tree_rebalance_for_erase( 1477 __pos._M_const_cast()._M_node, _M_impl._M_header); 1478 --_M_impl._M_node_count; 1479 return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() }; 1480 } 1481 1482 /// Extract a node. 1483 node_type 1484 extract(const key_type& __k) 1485 { 1486 node_type __nh; 1487 auto __pos = find(__k); 1488 if (__pos != end()) 1489 __nh = extract(const_iterator(__pos)); 1490 return __nh; 1491 } 1492 1493 template<typename _Compare2> 1494 using _Compatible_tree 1495 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>; 1496 1497 template<typename, typename> 1498 friend class _Rb_tree_merge_helper; 1499 1500 /// Merge from a compatible container into one with unique keys. 1501 template<typename _Compare2> 1502 void 1503 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept 1504 { 1505 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; 1506 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 1507 { 1508 auto __pos = __i++; 1509 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos)); 1510 if (__res.second) 1511 { 1512 auto& __src_impl = _Merge_helper::_S_get_impl(__src); 1513 auto __ptr = _Rb_tree_rebalance_for_erase( 1514 __pos._M_node, __src_impl._M_header); 1515 --__src_impl._M_node_count; 1516 _M_insert_node(__res.first, __res.second, 1517 static_cast<_Link_type>(__ptr)); 1518 } 1519 } 1520 } 1521 1522 /// Merge from a compatible container into one with equivalent keys. 1523 template<typename _Compare2> 1524 void 1525 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept 1526 { 1527 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; 1528 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 1529 { 1530 auto __pos = __i++; 1531 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos)); 1532 if (__res.second) 1533 { 1534 auto& __src_impl = _Merge_helper::_S_get_impl(__src); 1535 auto __ptr = _Rb_tree_rebalance_for_erase( 1536 __pos._M_node, __src_impl._M_header); 1537 --__src_impl._M_node_count; 1538 _M_insert_node(__res.first, __res.second, 1539 static_cast<_Link_type>(__ptr)); 1540 } 1541 } 1542 } 1543 #endif // C++17 1544 }; 1545 1546 template<typename _Key, typename _Val, typename _KeyOfValue, 1547 typename _Compare, typename _Alloc> 1548 inline bool 1549 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1550 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1551 { 1552 return __x.size() == __y.size() 1553 && std::equal(__x.begin(), __x.end(), __y.begin()); 1554 } 1555 1556 template<typename _Key, typename _Val, typename _KeyOfValue, 1557 typename _Compare, typename _Alloc> 1558 inline bool 1559 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1560 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1561 { 1562 return std::lexicographical_compare(__x.begin(), __x.end(), 1563 __y.begin(), __y.end()); 1564 } 1565 1566 template<typename _Key, typename _Val, typename _KeyOfValue, 1567 typename _Compare, typename _Alloc> 1568 inline bool 1569 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1570 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1571 { return !(__x == __y); } 1572 1573 template<typename _Key, typename _Val, typename _KeyOfValue, 1574 typename _Compare, typename _Alloc> 1575 inline bool 1576 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1577 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1578 { return __y < __x; } 1579 1580 template<typename _Key, typename _Val, typename _KeyOfValue, 1581 typename _Compare, typename _Alloc> 1582 inline bool 1583 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1584 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1585 { return !(__y < __x); } 1586 1587 template<typename _Key, typename _Val, typename _KeyOfValue, 1588 typename _Compare, typename _Alloc> 1589 inline bool 1590 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1591 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1592 { return !(__x < __y); } 1593 1594 template<typename _Key, typename _Val, typename _KeyOfValue, 1595 typename _Compare, typename _Alloc> 1596 inline void 1597 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 1598 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 1599 { __x.swap(__y); } 1600 1601 #if __cplusplus >= 201103L 1602 template<typename _Key, typename _Val, typename _KeyOfValue, 1603 typename _Compare, typename _Alloc> 1604 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1605 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 1606 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 1607 { 1608 using __eq = typename _Alloc_traits::is_always_equal; 1609 if (__x._M_root() != nullptr) 1610 _M_move_data(__x, __eq()); 1611 } 1612 1613 template<typename _Key, typename _Val, typename _KeyOfValue, 1614 typename _Compare, typename _Alloc> 1615 void 1616 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1617 _M_move_data(_Rb_tree& __x, std::false_type) 1618 { 1619 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1620 _M_move_data(__x, std::true_type()); 1621 else 1622 { 1623 _Alloc_node __an(*this); 1624 auto __lbd = 1625 [&__an](const value_type& __cval) 1626 { 1627 auto& __val = const_cast<value_type&>(__cval); 1628 return __an(std::move_if_noexcept(__val)); 1629 }; 1630 _M_root() = _M_copy(__x, __lbd); 1631 } 1632 } 1633 1634 template<typename _Key, typename _Val, typename _KeyOfValue, 1635 typename _Compare, typename _Alloc> 1636 inline void 1637 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1638 _M_move_assign(_Rb_tree& __x, true_type) 1639 { 1640 clear(); 1641 if (__x._M_root() != nullptr) 1642 _M_move_data(__x, std::true_type()); 1643 std::__alloc_on_move(_M_get_Node_allocator(), 1644 __x._M_get_Node_allocator()); 1645 } 1646 1647 template<typename _Key, typename _Val, typename _KeyOfValue, 1648 typename _Compare, typename _Alloc> 1649 void 1650 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1651 _M_move_assign(_Rb_tree& __x, false_type) 1652 { 1653 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 1654 return _M_move_assign(__x, true_type{}); 1655 1656 // Try to move each node reusing existing nodes and copying __x nodes 1657 // structure. 1658 _Reuse_or_alloc_node __roan(*this); 1659 _M_impl._M_reset(); 1660 if (__x._M_root() != nullptr) 1661 { 1662 auto __lbd = 1663 [&__roan](const value_type& __cval) 1664 { 1665 auto& __val = const_cast<value_type&>(__cval); 1666 return __roan(std::move_if_noexcept(__val)); 1667 }; 1668 _M_root() = _M_copy(__x, __lbd); 1669 __x.clear(); 1670 } 1671 } 1672 1673 template<typename _Key, typename _Val, typename _KeyOfValue, 1674 typename _Compare, typename _Alloc> 1675 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1676 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1677 operator=(_Rb_tree&& __x) 1678 noexcept(_Alloc_traits::_S_nothrow_move() 1679 && is_nothrow_move_assignable<_Compare>::value) 1680 { 1681 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare); 1682 _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>()); 1683 return *this; 1684 } 1685 1686 template<typename _Key, typename _Val, typename _KeyOfValue, 1687 typename _Compare, typename _Alloc> 1688 template<typename _Iterator> 1689 void 1690 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1691 _M_assign_unique(_Iterator __first, _Iterator __last) 1692 { 1693 _Reuse_or_alloc_node __roan(*this); 1694 _M_impl._M_reset(); 1695 for (; __first != __last; ++__first) 1696 _M_insert_unique_(end(), *__first, __roan); 1697 } 1698 1699 template<typename _Key, typename _Val, typename _KeyOfValue, 1700 typename _Compare, typename _Alloc> 1701 template<typename _Iterator> 1702 void 1703 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1704 _M_assign_equal(_Iterator __first, _Iterator __last) 1705 { 1706 _Reuse_or_alloc_node __roan(*this); 1707 _M_impl._M_reset(); 1708 for (; __first != __last; ++__first) 1709 _M_insert_equal_(end(), *__first, __roan); 1710 } 1711 #endif 1712 1713 template<typename _Key, typename _Val, typename _KeyOfValue, 1714 typename _Compare, typename _Alloc> 1715 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 1716 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1717 operator=(const _Rb_tree& __x) 1718 { 1719 if (this != &__x) 1720 { 1721 // Note that _Key may be a constant type. 1722 #if __cplusplus >= 201103L 1723 if (_Alloc_traits::_S_propagate_on_copy_assign()) 1724 { 1725 auto& __this_alloc = this->_M_get_Node_allocator(); 1726 auto& __that_alloc = __x._M_get_Node_allocator(); 1727 if (!_Alloc_traits::_S_always_equal() 1728 && __this_alloc != __that_alloc) 1729 { 1730 // Replacement allocator cannot free existing storage, we need 1731 // to erase nodes first. 1732 clear(); 1733 std::__alloc_on_copy(__this_alloc, __that_alloc); 1734 } 1735 } 1736 #endif 1737 1738 _Reuse_or_alloc_node __roan(*this); 1739 _M_impl._M_reset(); 1740 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 1741 if (__x._M_root() != 0) 1742 _M_root() = _M_copy(__x, __roan); 1743 } 1744 1745 return *this; 1746 } 1747 1748 template<typename _Key, typename _Val, typename _KeyOfValue, 1749 typename _Compare, typename _Alloc> 1750 #if __cplusplus >= 201103L 1751 template<typename _Arg, typename _NodeGen> 1752 #else 1753 template<typename _NodeGen> 1754 #endif 1755 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1756 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1757 _M_insert_(_Base_ptr __x, _Base_ptr __p, 1758 #if __cplusplus >= 201103L 1759 _Arg&& __v, 1760 #else 1761 const _Val& __v, 1762 #endif 1763 _NodeGen& __node_gen) 1764 { 1765 bool __insert_left = (__x != 0 || __p == _M_end() 1766 || _M_impl._M_key_compare(_KeyOfValue()(__v), 1767 _S_key(__p))); 1768 1769 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); 1770 1771 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1772 this->_M_impl._M_header); 1773 ++_M_impl._M_node_count; 1774 return iterator(__z); 1775 } 1776 1777 template<typename _Key, typename _Val, typename _KeyOfValue, 1778 typename _Compare, typename _Alloc> 1779 #if __cplusplus >= 201103L 1780 template<typename _Arg> 1781 #endif 1782 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1783 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1784 #if __cplusplus >= 201103L 1785 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 1786 #else 1787 _M_insert_lower(_Base_ptr __p, const _Val& __v) 1788 #endif 1789 { 1790 bool __insert_left = (__p == _M_end() 1791 || !_M_impl._M_key_compare(_S_key(__p), 1792 _KeyOfValue()(__v))); 1793 1794 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); 1795 1796 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 1797 this->_M_impl._M_header); 1798 ++_M_impl._M_node_count; 1799 return iterator(__z); 1800 } 1801 1802 template<typename _Key, typename _Val, typename _KeyOfValue, 1803 typename _Compare, typename _Alloc> 1804 #if __cplusplus >= 201103L 1805 template<typename _Arg> 1806 #endif 1807 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 1808 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1809 #if __cplusplus >= 201103L 1810 _M_insert_equal_lower(_Arg&& __v) 1811 #else 1812 _M_insert_equal_lower(const _Val& __v) 1813 #endif 1814 { 1815 _Link_type __x = _M_begin(); 1816 _Base_ptr __y = _M_end(); 1817 while (__x != 0) 1818 { 1819 __y = __x; 1820 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 1821 _S_left(__x) : _S_right(__x); 1822 } 1823 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 1824 } 1825 1826 template<typename _Key, typename _Val, typename _KoV, 1827 typename _Compare, typename _Alloc> 1828 template<typename _NodeGen> 1829 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 1830 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 1831 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) 1832 { 1833 // Structural copy. __x and __p must be non-null. 1834 _Link_type __top = _M_clone_node(__x, __node_gen); 1835 __top->_M_parent = __p; 1836 1837 __try 1838 { 1839 if (__x->_M_right) 1840 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); 1841 __p = __top; 1842 __x = _S_left(__x); 1843 1844 while (__x != 0) 1845 { 1846 _Link_type __y = _M_clone_node(__x, __node_gen); 1847 __p->_M_left = __y; 1848 __y->_M_parent = __p; 1849 if (__x->_M_right) 1850 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); 1851 __p = __y; 1852 __x = _S_left(__x); 1853 } 1854 } 1855 __catch(...) 1856 { 1857 _M_erase(__top); 1858 __throw_exception_again; 1859 } 1860 return __top; 1861 } 1862 1863 template<typename _Key, typename _Val, typename _KeyOfValue, 1864 typename _Compare, typename _Alloc> 1865 void 1866 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1867 _M_erase(_Link_type __x) 1868 { 1869 // Erase without rebalancing. 1870 while (__x != 0) 1871 { 1872 _M_erase(_S_right(__x)); 1873 _Link_type __y = _S_left(__x); 1874 _M_drop_node(__x); 1875 __x = __y; 1876 } 1877 } 1878 1879 template<typename _Key, typename _Val, typename _KeyOfValue, 1880 typename _Compare, typename _Alloc> 1881 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1882 _Compare, _Alloc>::iterator 1883 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1884 _M_lower_bound(_Link_type __x, _Base_ptr __y, 1885 const _Key& __k) 1886 { 1887 while (__x != 0) 1888 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1889 __y = __x, __x = _S_left(__x); 1890 else 1891 __x = _S_right(__x); 1892 return iterator(__y); 1893 } 1894 1895 template<typename _Key, typename _Val, typename _KeyOfValue, 1896 typename _Compare, typename _Alloc> 1897 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1898 _Compare, _Alloc>::const_iterator 1899 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1900 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, 1901 const _Key& __k) const 1902 { 1903 while (__x != 0) 1904 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1905 __y = __x, __x = _S_left(__x); 1906 else 1907 __x = _S_right(__x); 1908 return const_iterator(__y); 1909 } 1910 1911 template<typename _Key, typename _Val, typename _KeyOfValue, 1912 typename _Compare, typename _Alloc> 1913 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1914 _Compare, _Alloc>::iterator 1915 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1916 _M_upper_bound(_Link_type __x, _Base_ptr __y, 1917 const _Key& __k) 1918 { 1919 while (__x != 0) 1920 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1921 __y = __x, __x = _S_left(__x); 1922 else 1923 __x = _S_right(__x); 1924 return iterator(__y); 1925 } 1926 1927 template<typename _Key, typename _Val, typename _KeyOfValue, 1928 typename _Compare, typename _Alloc> 1929 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1930 _Compare, _Alloc>::const_iterator 1931 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1932 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, 1933 const _Key& __k) const 1934 { 1935 while (__x != 0) 1936 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1937 __y = __x, __x = _S_left(__x); 1938 else 1939 __x = _S_right(__x); 1940 return const_iterator(__y); 1941 } 1942 1943 template<typename _Key, typename _Val, typename _KeyOfValue, 1944 typename _Compare, typename _Alloc> 1945 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1946 _Compare, _Alloc>::iterator, 1947 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1948 _Compare, _Alloc>::iterator> 1949 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1950 equal_range(const _Key& __k) 1951 { 1952 _Link_type __x = _M_begin(); 1953 _Base_ptr __y = _M_end(); 1954 while (__x != 0) 1955 { 1956 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1957 __x = _S_right(__x); 1958 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1959 __y = __x, __x = _S_left(__x); 1960 else 1961 { 1962 _Link_type __xu(__x); 1963 _Base_ptr __yu(__y); 1964 __y = __x, __x = _S_left(__x); 1965 __xu = _S_right(__xu); 1966 return pair<iterator, 1967 iterator>(_M_lower_bound(__x, __y, __k), 1968 _M_upper_bound(__xu, __yu, __k)); 1969 } 1970 } 1971 return pair<iterator, iterator>(iterator(__y), 1972 iterator(__y)); 1973 } 1974 1975 template<typename _Key, typename _Val, typename _KeyOfValue, 1976 typename _Compare, typename _Alloc> 1977 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 1978 _Compare, _Alloc>::const_iterator, 1979 typename _Rb_tree<_Key, _Val, _KeyOfValue, 1980 _Compare, _Alloc>::const_iterator> 1981 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 1982 equal_range(const _Key& __k) const 1983 { 1984 _Const_Link_type __x = _M_begin(); 1985 _Const_Base_ptr __y = _M_end(); 1986 while (__x != 0) 1987 { 1988 if (_M_impl._M_key_compare(_S_key(__x), __k)) 1989 __x = _S_right(__x); 1990 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 1991 __y = __x, __x = _S_left(__x); 1992 else 1993 { 1994 _Const_Link_type __xu(__x); 1995 _Const_Base_ptr __yu(__y); 1996 __y = __x, __x = _S_left(__x); 1997 __xu = _S_right(__xu); 1998 return pair<const_iterator, 1999 const_iterator>(_M_lower_bound(__x, __y, __k), 2000 _M_upper_bound(__xu, __yu, __k)); 2001 } 2002 } 2003 return pair<const_iterator, const_iterator>(const_iterator(__y), 2004 const_iterator(__y)); 2005 } 2006 2007 template<typename _Key, typename _Val, typename _KeyOfValue, 2008 typename _Compare, typename _Alloc> 2009 void 2010 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2011 swap(_Rb_tree& __t) 2012 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 2013 { 2014 if (_M_root() == 0) 2015 { 2016 if (__t._M_root() != 0) 2017 _M_impl._M_move_data(__t._M_impl); 2018 } 2019 else if (__t._M_root() == 0) 2020 __t._M_impl._M_move_data(_M_impl); 2021 else 2022 { 2023 std::swap(_M_root(),__t._M_root()); 2024 std::swap(_M_leftmost(),__t._M_leftmost()); 2025 std::swap(_M_rightmost(),__t._M_rightmost()); 2026 2027 _M_root()->_M_parent = _M_end(); 2028 __t._M_root()->_M_parent = __t._M_end(); 2029 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 2030 } 2031 // No need to swap header's color as it does not change. 2032 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 2033 2034 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), 2035 __t._M_get_Node_allocator()); 2036 } 2037 2038 template<typename _Key, typename _Val, typename _KeyOfValue, 2039 typename _Compare, typename _Alloc> 2040 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2041 _Compare, _Alloc>::_Base_ptr, 2042 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2043 _Compare, _Alloc>::_Base_ptr> 2044 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2045 _M_get_insert_unique_pos(const key_type& __k) 2046 { 2047 typedef pair<_Base_ptr, _Base_ptr> _Res; 2048 _Link_type __x = _M_begin(); 2049 _Base_ptr __y = _M_end(); 2050 bool __comp = true; 2051 while (__x != 0) 2052 { 2053 __y = __x; 2054 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 2055 __x = __comp ? _S_left(__x) : _S_right(__x); 2056 } 2057 iterator __j = iterator(__y); 2058 if (__comp) 2059 { 2060 if (__j == begin()) 2061 return _Res(__x, __y); 2062 else 2063 --__j; 2064 } 2065 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 2066 return _Res(__x, __y); 2067 return _Res(__j._M_node, 0); 2068 } 2069 2070 template<typename _Key, typename _Val, typename _KeyOfValue, 2071 typename _Compare, typename _Alloc> 2072 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2073 _Compare, _Alloc>::_Base_ptr, 2074 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2075 _Compare, _Alloc>::_Base_ptr> 2076 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2077 _M_get_insert_equal_pos(const key_type& __k) 2078 { 2079 typedef pair<_Base_ptr, _Base_ptr> _Res; 2080 _Link_type __x = _M_begin(); 2081 _Base_ptr __y = _M_end(); 2082 while (__x != 0) 2083 { 2084 __y = __x; 2085 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 2086 _S_left(__x) : _S_right(__x); 2087 } 2088 return _Res(__x, __y); 2089 } 2090 2091 template<typename _Key, typename _Val, typename _KeyOfValue, 2092 typename _Compare, typename _Alloc> 2093 #if __cplusplus >= 201103L 2094 template<typename _Arg> 2095 #endif 2096 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2097 _Compare, _Alloc>::iterator, bool> 2098 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2099 #if __cplusplus >= 201103L 2100 _M_insert_unique(_Arg&& __v) 2101 #else 2102 _M_insert_unique(const _Val& __v) 2103 #endif 2104 { 2105 typedef pair<iterator, bool> _Res; 2106 pair<_Base_ptr, _Base_ptr> __res 2107 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 2108 2109 if (__res.second) 2110 { 2111 _Alloc_node __an(*this); 2112 return _Res(_M_insert_(__res.first, __res.second, 2113 _GLIBCXX_FORWARD(_Arg, __v), __an), 2114 true); 2115 } 2116 2117 return _Res(iterator(__res.first), false); 2118 } 2119 2120 template<typename _Key, typename _Val, typename _KeyOfValue, 2121 typename _Compare, typename _Alloc> 2122 #if __cplusplus >= 201103L 2123 template<typename _Arg> 2124 #endif 2125 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2126 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2127 #if __cplusplus >= 201103L 2128 _M_insert_equal(_Arg&& __v) 2129 #else 2130 _M_insert_equal(const _Val& __v) 2131 #endif 2132 { 2133 pair<_Base_ptr, _Base_ptr> __res 2134 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 2135 _Alloc_node __an(*this); 2136 return _M_insert_(__res.first, __res.second, 2137 _GLIBCXX_FORWARD(_Arg, __v), __an); 2138 } 2139 2140 template<typename _Key, typename _Val, typename _KeyOfValue, 2141 typename _Compare, typename _Alloc> 2142 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2143 _Compare, _Alloc>::_Base_ptr, 2144 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2145 _Compare, _Alloc>::_Base_ptr> 2146 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2147 _M_get_insert_hint_unique_pos(const_iterator __position, 2148 const key_type& __k) 2149 { 2150 iterator __pos = __position._M_const_cast(); 2151 typedef pair<_Base_ptr, _Base_ptr> _Res; 2152 2153 // end() 2154 if (__pos._M_node == _M_end()) 2155 { 2156 if (size() > 0 2157 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 2158 return _Res(0, _M_rightmost()); 2159 else 2160 return _M_get_insert_unique_pos(__k); 2161 } 2162 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) 2163 { 2164 // First, try before... 2165 iterator __before = __pos; 2166 if (__pos._M_node == _M_leftmost()) // begin() 2167 return _Res(_M_leftmost(), _M_leftmost()); 2168 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 2169 { 2170 if (_S_right(__before._M_node) == 0) 2171 return _Res(0, __before._M_node); 2172 else 2173 return _Res(__pos._M_node, __pos._M_node); 2174 } 2175 else 2176 return _M_get_insert_unique_pos(__k); 2177 } 2178 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 2179 { 2180 // ... then try after. 2181 iterator __after = __pos; 2182 if (__pos._M_node == _M_rightmost()) 2183 return _Res(0, _M_rightmost()); 2184 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 2185 { 2186 if (_S_right(__pos._M_node) == 0) 2187 return _Res(0, __pos._M_node); 2188 else 2189 return _Res(__after._M_node, __after._M_node); 2190 } 2191 else 2192 return _M_get_insert_unique_pos(__k); 2193 } 2194 else 2195 // Equivalent keys. 2196 return _Res(__pos._M_node, 0); 2197 } 2198 2199 template<typename _Key, typename _Val, typename _KeyOfValue, 2200 typename _Compare, typename _Alloc> 2201 #if __cplusplus >= 201103L 2202 template<typename _Arg, typename _NodeGen> 2203 #else 2204 template<typename _NodeGen> 2205 #endif 2206 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2207 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2208 _M_insert_unique_(const_iterator __position, 2209 #if __cplusplus >= 201103L 2210 _Arg&& __v, 2211 #else 2212 const _Val& __v, 2213 #endif 2214 _NodeGen& __node_gen) 2215 { 2216 pair<_Base_ptr, _Base_ptr> __res 2217 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 2218 2219 if (__res.second) 2220 return _M_insert_(__res.first, __res.second, 2221 _GLIBCXX_FORWARD(_Arg, __v), 2222 __node_gen); 2223 return iterator(__res.first); 2224 } 2225 2226 template<typename _Key, typename _Val, typename _KeyOfValue, 2227 typename _Compare, typename _Alloc> 2228 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2229 _Compare, _Alloc>::_Base_ptr, 2230 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2231 _Compare, _Alloc>::_Base_ptr> 2232 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2233 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 2234 { 2235 iterator __pos = __position._M_const_cast(); 2236 typedef pair<_Base_ptr, _Base_ptr> _Res; 2237 2238 // end() 2239 if (__pos._M_node == _M_end()) 2240 { 2241 if (size() > 0 2242 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 2243 return _Res(0, _M_rightmost()); 2244 else 2245 return _M_get_insert_equal_pos(__k); 2246 } 2247 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) 2248 { 2249 // First, try before... 2250 iterator __before = __pos; 2251 if (__pos._M_node == _M_leftmost()) // begin() 2252 return _Res(_M_leftmost(), _M_leftmost()); 2253 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 2254 { 2255 if (_S_right(__before._M_node) == 0) 2256 return _Res(0, __before._M_node); 2257 else 2258 return _Res(__pos._M_node, __pos._M_node); 2259 } 2260 else 2261 return _M_get_insert_equal_pos(__k); 2262 } 2263 else 2264 { 2265 // ... then try after. 2266 iterator __after = __pos; 2267 if (__pos._M_node == _M_rightmost()) 2268 return _Res(0, _M_rightmost()); 2269 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 2270 { 2271 if (_S_right(__pos._M_node) == 0) 2272 return _Res(0, __pos._M_node); 2273 else 2274 return _Res(__after._M_node, __after._M_node); 2275 } 2276 else 2277 return _Res(0, 0); 2278 } 2279 } 2280 2281 template<typename _Key, typename _Val, typename _KeyOfValue, 2282 typename _Compare, typename _Alloc> 2283 #if __cplusplus >= 201103L 2284 template<typename _Arg, typename _NodeGen> 2285 #else 2286 template<typename _NodeGen> 2287 #endif 2288 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2289 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2290 _M_insert_equal_(const_iterator __position, 2291 #if __cplusplus >= 201103L 2292 _Arg&& __v, 2293 #else 2294 const _Val& __v, 2295 #endif 2296 _NodeGen& __node_gen) 2297 { 2298 pair<_Base_ptr, _Base_ptr> __res 2299 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 2300 2301 if (__res.second) 2302 return _M_insert_(__res.first, __res.second, 2303 _GLIBCXX_FORWARD(_Arg, __v), 2304 __node_gen); 2305 2306 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 2307 } 2308 2309 #if __cplusplus >= 201103L 2310 template<typename _Key, typename _Val, typename _KeyOfValue, 2311 typename _Compare, typename _Alloc> 2312 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2313 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2314 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) 2315 { 2316 bool __insert_left = (__x != 0 || __p == _M_end() 2317 || _M_impl._M_key_compare(_S_key(__z), 2318 _S_key(__p))); 2319 2320 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 2321 this->_M_impl._M_header); 2322 ++_M_impl._M_node_count; 2323 return iterator(__z); 2324 } 2325 2326 template<typename _Key, typename _Val, typename _KeyOfValue, 2327 typename _Compare, typename _Alloc> 2328 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2329 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2330 _M_insert_lower_node(_Base_ptr __p, _Link_type __z) 2331 { 2332 bool __insert_left = (__p == _M_end() 2333 || !_M_impl._M_key_compare(_S_key(__p), 2334 _S_key(__z))); 2335 2336 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, 2337 this->_M_impl._M_header); 2338 ++_M_impl._M_node_count; 2339 return iterator(__z); 2340 } 2341 2342 template<typename _Key, typename _Val, typename _KeyOfValue, 2343 typename _Compare, typename _Alloc> 2344 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2345 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2346 _M_insert_equal_lower_node(_Link_type __z) 2347 { 2348 _Link_type __x = _M_begin(); 2349 _Base_ptr __y = _M_end(); 2350 while (__x != 0) 2351 { 2352 __y = __x; 2353 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 2354 _S_left(__x) : _S_right(__x); 2355 } 2356 return _M_insert_lower_node(__y, __z); 2357 } 2358 2359 template<typename _Key, typename _Val, typename _KeyOfValue, 2360 typename _Compare, typename _Alloc> 2361 template<typename... _Args> 2362 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2363 _Compare, _Alloc>::iterator, bool> 2364 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2365 _M_emplace_unique(_Args&&... __args) 2366 { 2367 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2368 2369 __try 2370 { 2371 typedef pair<iterator, bool> _Res; 2372 auto __res = _M_get_insert_unique_pos(_S_key(__z)); 2373 if (__res.second) 2374 return _Res(_M_insert_node(__res.first, __res.second, __z), true); 2375 2376 _M_drop_node(__z); 2377 return _Res(iterator(__res.first), false); 2378 } 2379 __catch(...) 2380 { 2381 _M_drop_node(__z); 2382 __throw_exception_again; 2383 } 2384 } 2385 2386 template<typename _Key, typename _Val, typename _KeyOfValue, 2387 typename _Compare, typename _Alloc> 2388 template<typename... _Args> 2389 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2390 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2391 _M_emplace_equal(_Args&&... __args) 2392 { 2393 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2394 2395 __try 2396 { 2397 auto __res = _M_get_insert_equal_pos(_S_key(__z)); 2398 return _M_insert_node(__res.first, __res.second, __z); 2399 } 2400 __catch(...) 2401 { 2402 _M_drop_node(__z); 2403 __throw_exception_again; 2404 } 2405 } 2406 2407 template<typename _Key, typename _Val, typename _KeyOfValue, 2408 typename _Compare, typename _Alloc> 2409 template<typename... _Args> 2410 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2411 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2412 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 2413 { 2414 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2415 2416 __try 2417 { 2418 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); 2419 2420 if (__res.second) 2421 return _M_insert_node(__res.first, __res.second, __z); 2422 2423 _M_drop_node(__z); 2424 return iterator(__res.first); 2425 } 2426 __catch(...) 2427 { 2428 _M_drop_node(__z); 2429 __throw_exception_again; 2430 } 2431 } 2432 2433 template<typename _Key, typename _Val, typename _KeyOfValue, 2434 typename _Compare, typename _Alloc> 2435 template<typename... _Args> 2436 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2437 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2438 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 2439 { 2440 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); 2441 2442 __try 2443 { 2444 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); 2445 2446 if (__res.second) 2447 return _M_insert_node(__res.first, __res.second, __z); 2448 2449 return _M_insert_equal_lower_node(__z); 2450 } 2451 __catch(...) 2452 { 2453 _M_drop_node(__z); 2454 __throw_exception_again; 2455 } 2456 } 2457 #endif 2458 2459 template<typename _Key, typename _Val, typename _KoV, 2460 typename _Cmp, typename _Alloc> 2461 template<class _II> 2462 void 2463 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 2464 _M_insert_unique(_II __first, _II __last) 2465 { 2466 _Alloc_node __an(*this); 2467 for (; __first != __last; ++__first) 2468 _M_insert_unique_(end(), *__first, __an); 2469 } 2470 2471 template<typename _Key, typename _Val, typename _KoV, 2472 typename _Cmp, typename _Alloc> 2473 template<class _II> 2474 void 2475 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: 2476 _M_insert_equal(_II __first, _II __last) 2477 { 2478 _Alloc_node __an(*this); 2479 for (; __first != __last; ++__first) 2480 _M_insert_equal_(end(), *__first, __an); 2481 } 2482 2483 template<typename _Key, typename _Val, typename _KeyOfValue, 2484 typename _Compare, typename _Alloc> 2485 void 2486 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2487 _M_erase_aux(const_iterator __position) 2488 { 2489 _Link_type __y = 2490 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase 2491 (const_cast<_Base_ptr>(__position._M_node), 2492 this->_M_impl._M_header)); 2493 _M_drop_node(__y); 2494 --_M_impl._M_node_count; 2495 } 2496 2497 template<typename _Key, typename _Val, typename _KeyOfValue, 2498 typename _Compare, typename _Alloc> 2499 void 2500 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2501 _M_erase_aux(const_iterator __first, const_iterator __last) 2502 { 2503 if (__first == begin() && __last == end()) 2504 clear(); 2505 else 2506 while (__first != __last) 2507 _M_erase_aux(__first++); 2508 } 2509 2510 template<typename _Key, typename _Val, typename _KeyOfValue, 2511 typename _Compare, typename _Alloc> 2512 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 2513 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2514 erase(const _Key& __x) 2515 { 2516 pair<iterator, iterator> __p = equal_range(__x); 2517 const size_type __old_size = size(); 2518 _M_erase_aux(__p.first, __p.second); 2519 return __old_size - size(); 2520 } 2521 2522 template<typename _Key, typename _Val, typename _KeyOfValue, 2523 typename _Compare, typename _Alloc> 2524 void 2525 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2526 erase(const _Key* __first, const _Key* __last) 2527 { 2528 while (__first != __last) 2529 erase(*__first++); 2530 } 2531 2532 template<typename _Key, typename _Val, typename _KeyOfValue, 2533 typename _Compare, typename _Alloc> 2534 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2535 _Compare, _Alloc>::iterator 2536 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2537 find(const _Key& __k) 2538 { 2539 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 2540 return (__j == end() 2541 || _M_impl._M_key_compare(__k, 2542 _S_key(__j._M_node))) ? end() : __j; 2543 } 2544 2545 template<typename _Key, typename _Val, typename _KeyOfValue, 2546 typename _Compare, typename _Alloc> 2547 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2548 _Compare, _Alloc>::const_iterator 2549 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2550 find(const _Key& __k) const 2551 { 2552 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); 2553 return (__j == end() 2554 || _M_impl._M_key_compare(__k, 2555 _S_key(__j._M_node))) ? end() : __j; 2556 } 2557 2558 template<typename _Key, typename _Val, typename _KeyOfValue, 2559 typename _Compare, typename _Alloc> 2560 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 2561 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2562 count(const _Key& __k) const 2563 { 2564 pair<const_iterator, const_iterator> __p = equal_range(__k); 2565 const size_type __n = std::distance(__p.first, __p.second); 2566 return __n; 2567 } 2568 2569 _GLIBCXX_PURE unsigned int 2570 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 2571 const _Rb_tree_node_base* __root) throw (); 2572 2573 template<typename _Key, typename _Val, typename _KeyOfValue, 2574 typename _Compare, typename _Alloc> 2575 bool 2576 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 2577 { 2578 if (_M_impl._M_node_count == 0 || begin() == end()) 2579 return _M_impl._M_node_count == 0 && begin() == end() 2580 && this->_M_impl._M_header._M_left == _M_end() 2581 && this->_M_impl._M_header._M_right == _M_end(); 2582 2583 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 2584 for (const_iterator __it = begin(); __it != end(); ++__it) 2585 { 2586 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); 2587 _Const_Link_type __L = _S_left(__x); 2588 _Const_Link_type __R = _S_right(__x); 2589 2590 if (__x->_M_color == _S_red) 2591 if ((__L && __L->_M_color == _S_red) 2592 || (__R && __R->_M_color == _S_red)) 2593 return false; 2594 2595 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 2596 return false; 2597 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 2598 return false; 2599 2600 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 2601 return false; 2602 } 2603 2604 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 2605 return false; 2606 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 2607 return false; 2608 return true; 2609 } 2610 2611 #if __cplusplus > 201402L 2612 // Allow access to internals of compatible _Rb_tree specializations. 2613 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1, 2614 typename _Alloc, typename _Cmp2> 2615 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>, 2616 _Cmp2> 2617 { 2618 private: 2619 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>; 2620 2621 static auto& 2622 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree) 2623 { return __tree._M_impl; } 2624 }; 2625 #endif // C++17 2626 2627 _GLIBCXX_END_NAMESPACE_VERSION 2628 } // namespace 2629 2630 #endif 2631