Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/stl_tree.h
1 // RB tree implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2025 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 #ifdef _GLIBCXX_SYSHDR 62 #pragma GCC system_header 63 #endif 64 65 #include <bits/stl_algobase.h> 66 #include <bits/allocator.h> 67 #include <bits/stl_function.h> 68 #include <bits/cpp_type_traits.h> 69 #include <bits/ptr_traits.h> 70 #include <ext/alloc_traits.h> 71 #if __cplusplus >= 201103L 72 # include <ext/aligned_buffer.h> 73 #endif 74 #ifdef __glibcxx_node_extract // >= C++17 75 # include <bits/node_handle.h> 76 #endif 77 78 #if __cplusplus < 201103L 79 # undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 80 # define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 0 81 #elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 82 # define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1 83 #endif 84 85 namespace std _GLIBCXX_VISIBILITY(default) 86 { 87 _GLIBCXX_BEGIN_NAMESPACE_VERSION 88 89 // Red-black tree class, designed for use in implementing STL 90 // associative containers (set, multiset, map, and multimap). The 91 // insertion and deletion algorithms are based on those in Cormen, 92 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 93 // 1990), except that 94 // 95 // (1) the header cell is maintained with links not only to the root 96 // but also to the leftmost node of the tree, to enable constant 97 // time begin(), and to the rightmost node of the tree, to enable 98 // linear time performance when used with the generic set algorithms 99 // (set_union, etc.) 100 // 101 // (2) when a node being deleted has two children its successor node 102 // is relinked into its place, rather than copied, so that the only 103 // iterators invalidated are those referring to the deleted node. 104 105 enum _Rb_tree_color { _S_red = false, _S_black = true }; 106 107 struct _Rb_tree_node_base 108 { 109 typedef _Rb_tree_node_base* _Base_ptr; 110 111 _Rb_tree_color _M_color; 112 _Base_ptr _M_parent; 113 _Base_ptr _M_left; 114 _Base_ptr _M_right; 115 116 static _Base_ptr 117 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 118 { 119 while (__x->_M_left != 0) __x = __x->_M_left; 120 return __x; 121 } 122 123 static _Base_ptr 124 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 125 { 126 while (__x->_M_right != 0) __x = __x->_M_right; 127 return __x; 128 } 129 130 // This is not const-correct, but it's only used in a const access path 131 // by std::_Rb_tree::_M_end() where the pointer is used to initialize a 132 // const_iterator and so constness is restored. 133 _Base_ptr 134 _M_base_ptr() const _GLIBCXX_NOEXCEPT 135 { return const_cast<_Rb_tree_node_base*>(this); } 136 }; 137 138 // Helper type offering value initialization guarantee on the compare functor. 139 template<typename _Key_compare> 140 struct _Rb_tree_key_compare 141 { 142 _Key_compare _M_key_compare; 143 144 _Rb_tree_key_compare() 145 _GLIBCXX_NOEXCEPT_IF( 146 is_nothrow_default_constructible<_Key_compare>::value) 147 : _M_key_compare() 148 { } 149 150 _Rb_tree_key_compare(const _Key_compare& __comp) 151 : _M_key_compare(__comp) 152 { } 153 154 #if __cplusplus >= 201103L 155 // Copy constructor added for consistency with C++98 mode. 156 _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default; 157 158 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x) 159 noexcept(is_nothrow_copy_constructible<_Key_compare>::value) 160 : _M_key_compare(__x._M_key_compare) 161 { } 162 #endif 163 }; 164 165 // Helper type to manage default initialization of node count and header. 166 struct _Rb_tree_header 167 { 168 _Rb_tree_node_base _M_header; 169 size_t _M_node_count; // Keeps track of size of tree. 170 171 _Rb_tree_header() _GLIBCXX_NOEXCEPT 172 { 173 _M_header._M_color = _S_red; 174 _M_reset(); 175 } 176 177 #if __cplusplus >= 201103L 178 _Rb_tree_header(_Rb_tree_header&& __x) noexcept 179 { 180 if (__x._M_header._M_parent != nullptr) 181 _M_move_data(__x); 182 else 183 { 184 _M_header._M_color = _S_red; 185 _M_reset(); 186 } 187 } 188 #endif 189 190 void 191 _M_move_data(_Rb_tree_header& __from) 192 { 193 _M_header._M_color = __from._M_header._M_color; 194 _M_header._M_parent = __from._M_header._M_parent; 195 _M_header._M_left = __from._M_header._M_left; 196 _M_header._M_right = __from._M_header._M_right; 197 _M_header._M_parent->_M_parent = &_M_header; 198 _M_node_count = __from._M_node_count; 199 200 __from._M_reset(); 201 } 202 203 void 204 _M_reset() 205 { 206 _M_header._M_parent = 0; 207 _M_header._M_left = &_M_header; 208 _M_header._M_right = &_M_header; 209 _M_node_count = 0; 210 } 211 }; 212 213 template<typename _Val> 214 struct _Rb_tree_node : public _Rb_tree_node_base 215 { 216 #if __cplusplus < 201103L 217 _Val _M_value_field; 218 219 _Val* 220 _M_valptr() 221 { return std::__addressof(_M_value_field); } 222 223 const _Val* 224 _M_valptr() const 225 { return std::__addressof(_M_value_field); } 226 #else 227 __gnu_cxx::__aligned_membuf<_Val> _M_storage; 228 229 _Val* 230 _M_valptr() 231 { return _M_storage._M_ptr(); } 232 233 const _Val* 234 _M_valptr() const 235 { return _M_storage._M_ptr(); } 236 #endif 237 238 _Rb_tree_node* 239 _M_node_ptr() _GLIBCXX_NOEXCEPT 240 { return this; } 241 }; 242 243 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 244 namespace __rb_tree 245 { 246 template<typename _VoidPtr> 247 struct _Node_base 248 { 249 using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>; 250 251 _Rb_tree_color _M_color; 252 _Base_ptr _M_parent; 253 _Base_ptr _M_left; 254 _Base_ptr _M_right; 255 256 static _Base_ptr 257 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 258 { 259 while (__x->_M_left) __x = __x->_M_left; 260 return __x; 261 } 262 263 static _Base_ptr 264 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT 265 { 266 while (__x->_M_right) __x = __x->_M_right; 267 return __x; 268 } 269 270 // This is not const-correct, but it's only used in a const access path 271 // by std::_Rb_tree::_M_end() where the pointer is used to initialize a 272 // const_iterator and so constness is restored. 273 _Base_ptr 274 _M_base_ptr() const noexcept 275 { 276 return pointer_traits<_Base_ptr>::pointer_to 277 (*const_cast<_Node_base*>(this)); 278 } 279 }; 280 281 // Helper type to manage default initialization of node count and header. 282 template<typename _NodeBase> 283 struct _Header 284 { 285 private: 286 using _Base_ptr = typename _NodeBase::_Base_ptr; 287 288 public: 289 _NodeBase _M_header; 290 size_t _M_node_count; // Keeps track of size of tree. 291 292 _Header() noexcept 293 { 294 _M_header._M_color = _S_red; 295 _M_reset(); 296 } 297 298 _Header(_Header&& __x) noexcept 299 { 300 if (__x._M_header._M_parent) 301 _M_move_data(__x); 302 else 303 { 304 _M_header._M_color = _S_red; 305 _M_reset(); 306 } 307 } 308 309 void 310 _M_move_data(_Header& __from) 311 { 312 _M_header._M_color = __from._M_header._M_color; 313 _M_header._M_parent = __from._M_header._M_parent; 314 _M_header._M_left = __from._M_header._M_left; 315 _M_header._M_right = __from._M_header._M_right; 316 _M_header._M_parent->_M_parent = _M_header._M_base_ptr(); 317 _M_node_count = __from._M_node_count; 318 319 __from._M_reset(); 320 } 321 322 void 323 _M_reset() 324 { 325 _M_header._M_parent = nullptr; 326 _M_header._M_left = _M_header._M_right = _M_header._M_base_ptr(); 327 _M_node_count = 0; 328 } 329 }; 330 331 template<typename _ValPtr> 332 struct _Node : public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>> 333 { 334 using value_type = typename pointer_traits<_ValPtr>::element_type; 335 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>; 336 337 _Node() noexcept { } 338 ~_Node() { } 339 _Node(_Node&&) = delete; 340 341 union _Uninit_storage 342 { 343 _Uninit_storage() noexcept { } 344 ~_Uninit_storage() { } 345 346 value_type _M_data; 347 }; 348 _Uninit_storage _M_u; 349 350 value_type* 351 _M_valptr() 352 { return std::addressof(_M_u._M_data); } 353 354 value_type const* 355 _M_valptr() const 356 { return std::addressof(_M_u._M_data); } 357 358 _Node_ptr 359 _M_node_ptr() noexcept 360 { return pointer_traits<_Node_ptr>::pointer_to(*this); } 361 }; 362 } // namespace __rb_tree 363 #endif // _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 364 365 _GLIBCXX_PURE _Rb_tree_node_base* 366 _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); 367 368 _GLIBCXX_PURE _Rb_tree_node_base* 369 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); 370 371 template<typename _Tp> 372 struct _Rb_tree_iterator 373 { 374 typedef _Tp value_type; 375 typedef _Tp& reference; 376 typedef _Tp* pointer; 377 378 typedef bidirectional_iterator_tag iterator_category; 379 typedef ptrdiff_t difference_type; 380 381 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 382 typedef _Rb_tree_node<_Tp>* _Node_ptr; 383 384 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT 385 : _M_node() { } 386 387 explicit 388 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 389 : _M_node(__x) { } 390 391 reference 392 operator*() const _GLIBCXX_NOEXCEPT 393 { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); } 394 395 pointer 396 operator->() const _GLIBCXX_NOEXCEPT 397 { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); } 398 399 _Rb_tree_iterator& 400 operator++() _GLIBCXX_NOEXCEPT 401 { 402 _M_node = _Rb_tree_increment(_M_node); 403 return *this; 404 } 405 406 _Rb_tree_iterator 407 operator++(int) _GLIBCXX_NOEXCEPT 408 { 409 _Rb_tree_iterator __tmp = *this; 410 _M_node = _Rb_tree_increment(_M_node); 411 return __tmp; 412 } 413 414 _Rb_tree_iterator& 415 operator--() _GLIBCXX_NOEXCEPT 416 { 417 _M_node = _Rb_tree_decrement(_M_node); 418 return *this; 419 } 420 421 _Rb_tree_iterator 422 operator--(int) _GLIBCXX_NOEXCEPT 423 { 424 _Rb_tree_iterator __tmp = *this; 425 _M_node = _Rb_tree_decrement(_M_node); 426 return __tmp; 427 } 428 429 friend bool 430 operator==(const _Rb_tree_iterator& __x, 431 const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT 432 { return __x._M_node == __y._M_node; } 433 434 #if ! __cpp_lib_three_way_comparison 435 friend bool 436 operator!=(const _Rb_tree_iterator& __x, 437 const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT 438 { return __x._M_node != __y._M_node; } 439 #endif 440 441 _Base_ptr _M_node; 442 }; 443 444 template<typename _Tp> 445 struct _Rb_tree_const_iterator 446 { 447 typedef _Tp value_type; 448 typedef const _Tp& reference; 449 typedef const _Tp* pointer; 450 451 typedef _Rb_tree_iterator<_Tp> iterator; 452 453 typedef bidirectional_iterator_tag iterator_category; 454 typedef ptrdiff_t difference_type; 455 456 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; 457 typedef const _Rb_tree_node<_Tp>* _Node_ptr; 458 459 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT 460 : _M_node() { } 461 462 explicit 463 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT 464 : _M_node(__x) { } 465 466 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT 467 : _M_node(__it._M_node) { } 468 469 reference 470 operator*() const _GLIBCXX_NOEXCEPT 471 { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); } 472 473 pointer 474 operator->() const _GLIBCXX_NOEXCEPT 475 { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); } 476 477 _Rb_tree_const_iterator& 478 operator++() _GLIBCXX_NOEXCEPT 479 { 480 _M_node = _Rb_tree_increment(_M_node); 481 return *this; 482 } 483 484 _Rb_tree_const_iterator 485 operator++(int) _GLIBCXX_NOEXCEPT 486 { 487 _Rb_tree_const_iterator __tmp = *this; 488 _M_node = _Rb_tree_increment(_M_node); 489 return __tmp; 490 } 491 492 _Rb_tree_const_iterator& 493 operator--() _GLIBCXX_NOEXCEPT 494 { 495 _M_node = _Rb_tree_decrement(_M_node); 496 return *this; 497 } 498 499 _Rb_tree_const_iterator 500 operator--(int) _GLIBCXX_NOEXCEPT 501 { 502 _Rb_tree_const_iterator __tmp = *this; 503 _M_node = _Rb_tree_decrement(_M_node); 504 return __tmp; 505 } 506 507 friend bool 508 operator==(const _Rb_tree_const_iterator& __x, 509 const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT 510 { return __x._M_node == __y._M_node; } 511 512 #if ! __cpp_lib_three_way_comparison 513 friend bool 514 operator!=(const _Rb_tree_const_iterator& __x, 515 const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT 516 { return __x._M_node != __y._M_node; } 517 #endif 518 519 _Base_ptr _M_node; 520 }; 521 522 __attribute__((__nonnull__)) 523 void 524 _Rb_tree_insert_and_rebalance(const bool __insert_left, 525 _Rb_tree_node_base* __x, 526 _Rb_tree_node_base* __p, 527 _Rb_tree_node_base& __header) throw (); 528 529 __attribute__((__nonnull__,__returns_nonnull__)) 530 _Rb_tree_node_base* 531 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 532 _Rb_tree_node_base& __header) throw (); 533 534 namespace __rb_tree 535 { 536 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 537 template<bool _Const, typename _ValPtr> 538 struct _Iterator 539 { 540 template<typename _Tp> 541 using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>; 542 543 using __ptr_traits = pointer_traits<_ValPtr>; 544 using value_type = typename __ptr_traits::element_type; 545 using reference = __maybe_const<value_type>&; 546 using pointer = __maybe_const<value_type>*; 547 548 using iterator_category = bidirectional_iterator_tag; 549 using difference_type = ptrdiff_t; 550 551 using _Node = __rb_tree::_Node<_ValPtr>; 552 using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>; 553 using _Base_ptr = typename _Node_base::_Base_ptr; 554 555 _Iterator() noexcept 556 : _M_node() { } 557 558 constexpr explicit 559 _Iterator(_Base_ptr __x) noexcept 560 : _M_node(__x) { } 561 562 _Iterator(const _Iterator&) = default; 563 _Iterator& operator=(const _Iterator&) = default; 564 565 #ifdef __glibcxx_concepts 566 constexpr 567 _Iterator(const _Iterator<false, _ValPtr>& __it) requires _Const 568 #else 569 template<bool _OtherConst, 570 typename = __enable_if_t<_Const && !_OtherConst>> 571 constexpr 572 _Iterator(const _Iterator<_OtherConst, _ValPtr>& __it) 573 #endif 574 : _M_node(__it._M_node) { } 575 576 [[__nodiscard__]] 577 reference 578 operator*() const noexcept 579 { return *static_cast<_Node&>(*_M_node)._M_valptr(); } 580 581 [[__nodiscard__]] 582 pointer 583 operator->() const noexcept 584 { return static_cast<_Node&>(*_M_node)._M_valptr(); } 585 586 _GLIBCXX14_CONSTEXPR _Iterator& 587 operator++() noexcept 588 { 589 if (_M_node->_M_right) 590 { 591 _M_node = _M_node->_M_right; 592 while (_M_node->_M_left) 593 _M_node = _M_node->_M_left; 594 } 595 else 596 { 597 _Base_ptr __y = _M_node->_M_parent; 598 while (_M_node == __y->_M_right) 599 { 600 _M_node = __y; 601 __y = __y->_M_parent; 602 } 603 if (_M_node->_M_right != __y) 604 _M_node = __y; 605 } 606 607 return *this; 608 } 609 610 _GLIBCXX14_CONSTEXPR _Iterator 611 operator++(int) noexcept 612 { 613 _Iterator __tmp(this->_M_node); 614 ++*this; 615 return __tmp; 616 } 617 618 _GLIBCXX14_CONSTEXPR _Iterator& 619 operator--() noexcept 620 { 621 if (_M_node->_M_color == _S_red 622 && _M_node->_M_parent->_M_parent == _M_node) 623 _M_node = _M_node->_M_right; 624 else if (_M_node->_M_left) 625 { 626 _Base_ptr __y = _M_node->_M_left; 627 while (__y->_M_right) 628 __y = __y->_M_right; 629 _M_node = __y; 630 } 631 else 632 { 633 _Base_ptr __y = _M_node->_M_parent; 634 while (_M_node == __y->_M_left) 635 { 636 _M_node = __y; 637 __y = __y->_M_parent; 638 } 639 _M_node = __y; 640 } 641 return *this; 642 } 643 644 _GLIBCXX14_CONSTEXPR _Iterator 645 operator--(int) noexcept 646 { 647 _Iterator __tmp(this->_M_node); 648 --*this; 649 return __tmp; 650 } 651 652 [[__nodiscard__]] 653 friend bool 654 operator==(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT 655 { return __x._M_node == __y._M_node; } 656 657 #if ! __cpp_lib_three_way_comparison 658 [[__nodiscard__]] 659 friend bool 660 operator!=(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT 661 { return __x._M_node != __y._M_node; } 662 #endif 663 664 _Base_ptr _M_node; 665 }; 666 #endif // USE_ALLOC_PTR_FOR_RB_TREE 667 668 // Determine the node and iterator types used by std::_Rb_tree. 669 template<typename _Val, typename _Ptr> 670 struct _Node_traits; 671 672 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000 673 // Specialization for the simple case where the allocator's pointer type 674 // is the same type as value_type*. 675 // For ABI compatibility we can't change the types used for this case. 676 template<typename _Val> 677 struct _Node_traits<_Val, _Val*> 678 { 679 typedef _Rb_tree_node<_Val> _Node; 680 typedef _Node* _Node_ptr; 681 typedef _Rb_tree_node_base _Node_base; 682 typedef _Node_base* _Base_ptr; 683 typedef _Rb_tree_header _Header_t; 684 typedef _Rb_tree_iterator<_Val> _Iterator; 685 typedef _Rb_tree_const_iterator<_Val> _Const_iterator; 686 687 __attribute__((__nonnull__)) 688 static void 689 _S_insert_and_rebalance(const bool __insert_left, 690 _Node_base* __x, _Node_base* __p, 691 _Node_base& __header) _GLIBCXX_USE_NOEXCEPT 692 { 693 return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header); 694 } 695 696 __attribute__((__nonnull__,__returns_nonnull__)) 697 static _Node_base* 698 _S_rebalance_for_erase(_Node_base* const __z, 699 _Node_base& __header) _GLIBCXX_USE_NOEXCEPT 700 { return _Rb_tree_rebalance_for_erase(__z, __header); } 701 }; 702 #endif 703 704 #if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 705 // Always use the T* specialization. 706 template<typename _Val, typename _Ptr> 707 struct _Node_traits 708 : _Node_traits<_Val, _Val*> 709 { }; 710 #else 711 // Primary template used when the allocator uses fancy pointers. 712 template<typename _Val, typename _ValPtr> 713 struct _Node_traits 714 { 715 using _Node = __rb_tree::_Node<_ValPtr>; 716 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>; 717 using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>; 718 using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>; 719 using _Header_t = __rb_tree::_Header<_Node_base>; 720 using _Iterator = __rb_tree::_Iterator<false, _ValPtr>; 721 using _Const_iterator = __rb_tree::_Iterator<true, _ValPtr>; 722 723 static void 724 _Rotate_left(_Base_ptr __x, _Base_ptr& __root) 725 { 726 const _Base_ptr __y = __x->_M_right; 727 728 __x->_M_right = __y->_M_left; 729 if (__y->_M_left) 730 __y->_M_left->_M_parent = __x; 731 __y->_M_parent = __x->_M_parent; 732 733 if (__x == __root) 734 __root = __y; 735 else if (__x == __x->_M_parent->_M_left) 736 __x->_M_parent->_M_left = __y; 737 else 738 __x->_M_parent->_M_right = __y; 739 __y->_M_left = __x; 740 __x->_M_parent = __y; 741 } 742 743 static void 744 _Rotate_right(_Base_ptr __x, _Base_ptr& __root) 745 { 746 const _Base_ptr __y = __x->_M_left; 747 748 __x->_M_left = __y->_M_right; 749 if (__y->_M_right) 750 __y->_M_right->_M_parent = __x; 751 __y->_M_parent = __x->_M_parent; 752 753 if (__x == __root) 754 __root = __y; 755 else if (__x == __x->_M_parent->_M_right) 756 __x->_M_parent->_M_right = __y; 757 else 758 __x->_M_parent->_M_left = __y; 759 __y->_M_right = __x; 760 __x->_M_parent = __y; 761 } 762 763 static void 764 _S_insert_and_rebalance(const bool __insert_left, 765 _Base_ptr __x, _Base_ptr __p, 766 _Node_base& __header) 767 { 768 _Base_ptr& __root = __header._M_parent; 769 770 // Initialize fields in new node to insert. 771 __x->_M_parent = __p; 772 __x->_M_left = __x->_M_right = nullptr; 773 __x->_M_color = _S_red; 774 775 // Insert. 776 // Make new node child of parent and maintain root, leftmost and 777 // rightmost nodes. 778 // N.B. First node is always inserted left. 779 if (__insert_left) 780 { 781 __p->_M_left = __x; // also makes leftmost = __x when __p == &__header 782 783 if (std::__to_address(__p) == std::addressof(__header)) 784 { 785 __header._M_parent = __x; 786 __header._M_right = __x; 787 } 788 else if (__p == __header._M_left) 789 __header._M_left = __x; // maintain leftmost pointing to min node 790 } 791 else 792 { 793 __p->_M_right = __x; 794 795 if (__p == __header._M_right) 796 __header._M_right = __x; // maintain rightmost pointing to max node 797 } 798 // Rebalance. 799 while (__x != __root 800 && __x->_M_parent->_M_color == _S_red) 801 { 802 const _Base_ptr __xpp = __x->_M_parent->_M_parent; 803 804 if (__x->_M_parent == __xpp->_M_left) 805 { 806 const _Base_ptr __y = __xpp->_M_right; 807 if (__y && __y->_M_color == _S_red) 808 { 809 __x->_M_parent->_M_color = _S_black; 810 __y->_M_color = _S_black; 811 __xpp->_M_color = _S_red; 812 __x = __xpp; 813 } 814 else 815 { 816 if (__x == __x->_M_parent->_M_right) 817 { 818 __x = __x->_M_parent; 819 _Rotate_left(__x, __root); 820 } 821 __x->_M_parent->_M_color = _S_black; 822 __xpp->_M_color = _S_red; 823 _Rotate_right(__xpp, __root); 824 } 825 } 826 else 827 { 828 const _Base_ptr __y = __xpp->_M_left; 829 if (__y && __y->_M_color == _S_red) 830 { 831 __x->_M_parent->_M_color = _S_black; 832 __y->_M_color = _S_black; 833 __xpp->_M_color = _S_red; 834 __x = __xpp; 835 } 836 else 837 { 838 if (__x == __x->_M_parent->_M_left) 839 { 840 __x = __x->_M_parent; 841 _Rotate_right(__x, __root); 842 } 843 __x->_M_parent->_M_color = _S_black; 844 __xpp->_M_color = _S_red; 845 _Rotate_left(__xpp, __root); 846 } 847 } 848 } 849 __root->_M_color = _S_black; 850 } 851 852 static _Base_ptr 853 _S_rebalance_for_erase(_Base_ptr __z, _Node_base& __header) 854 { 855 _Base_ptr& __root = __header._M_parent; 856 _Base_ptr& __leftmost = __header._M_left; 857 _Base_ptr& __rightmost = __header._M_right; 858 _Base_ptr __y = __z; 859 _Base_ptr __x{}; 860 _Base_ptr __x_parent{}; 861 862 if (!__y->_M_left) // __z has at most one non-null child. y == z. 863 __x = __y->_M_right; // __x might be null. 864 else 865 if (!__y->_M_right) // __z has exactly one non-null child. y == z. 866 __x = __y->_M_left; // __x is not null. 867 else 868 { 869 // __z has two non-null children. Set __y to 870 __y = __y->_M_right; // __z's successor. __x might be null. 871 while (__y->_M_left) 872 __y = __y->_M_left; 873 __x = __y->_M_right; 874 } 875 if (__y != __z) 876 { 877 // relink y in place of z. y is z's successor 878 __z->_M_left->_M_parent = __y; 879 __y->_M_left = __z->_M_left; 880 if (__y != __z->_M_right) 881 { 882 __x_parent = __y->_M_parent; 883 if (__x) 884 __x->_M_parent = __y->_M_parent; 885 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 886 __y->_M_right = __z->_M_right; 887 __z->_M_right->_M_parent = __y; 888 } 889 else 890 __x_parent = __y; 891 if (__root == __z) 892 __root = __y; 893 else if (__z->_M_parent->_M_left == __z) 894 __z->_M_parent->_M_left = __y; 895 else 896 __z->_M_parent->_M_right = __y; 897 __y->_M_parent = __z->_M_parent; 898 std::swap(__y->_M_color, __z->_M_color); 899 __y = __z; 900 // __y now points to node to be actually deleted 901 } 902 else 903 { // __y == __z 904 __x_parent = __y->_M_parent; 905 if (__x) 906 __x->_M_parent = __y->_M_parent; 907 if (__root == __z) 908 __root = __x; 909 else 910 if (__z->_M_parent->_M_left == __z) 911 __z->_M_parent->_M_left = __x; 912 else 913 __z->_M_parent->_M_right = __x; 914 if (__leftmost == __z) 915 { 916 if (!__z->_M_right) // __z->_M_left must be null also 917 __leftmost = __z->_M_parent; 918 // makes __leftmost == _M_header if __z == __root 919 else 920 __leftmost = _Node_base::_S_minimum(__x); 921 } 922 if (__rightmost == __z) 923 { 924 if (__z->_M_left == 0) // __z->_M_right must be null also 925 __rightmost = __z->_M_parent; 926 // makes __rightmost == _M_header if __z == __root 927 else // __x == __z->_M_left 928 __rightmost = _Node_base::_S_maximum(__x); 929 } 930 } 931 if (__y->_M_color != _S_red) 932 { 933 while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) 934 if (__x == __x_parent->_M_left) 935 { 936 _Base_ptr __w = __x_parent->_M_right; 937 if (__w->_M_color == _S_red) 938 { 939 __w->_M_color = _S_black; 940 __x_parent->_M_color = _S_red; 941 _Rotate_left(__x_parent, __root); 942 __w = __x_parent->_M_right; 943 } 944 if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) && 945 (!__w->_M_right || __w->_M_right->_M_color == _S_black)) 946 { 947 __w->_M_color = _S_red; 948 __x = __x_parent; 949 __x_parent = __x_parent->_M_parent; 950 } 951 else 952 { 953 if (!__w->_M_right || __w->_M_right->_M_color == _S_black) 954 { 955 __w->_M_left->_M_color = _S_black; 956 __w->_M_color = _S_red; 957 _Rotate_right(__w, __root); 958 __w = __x_parent->_M_right; 959 } 960 __w->_M_color = __x_parent->_M_color; 961 __x_parent->_M_color = _S_black; 962 if (__w->_M_right) 963 __w->_M_right->_M_color = _S_black; 964 _Rotate_left(__x_parent, __root); 965 break; 966 } 967 } 968 else 969 { 970 // same as above, with _M_right <-> _M_left. 971 _Base_ptr __w = __x_parent->_M_left; 972 if (__w->_M_color == _S_red) 973 { 974 __w->_M_color = _S_black; 975 __x_parent->_M_color = _S_red; 976 _Rotate_right(__x_parent, __root); 977 __w = __x_parent->_M_left; 978 } 979 if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) && 980 (!__w->_M_left || __w->_M_left->_M_color == _S_black)) 981 { 982 __w->_M_color = _S_red; 983 __x = __x_parent; 984 __x_parent = __x_parent->_M_parent; 985 } 986 else 987 { 988 if (!__w->_M_left || __w->_M_left->_M_color == _S_black) 989 { 990 __w->_M_right->_M_color = _S_black; 991 __w->_M_color = _S_red; 992 _Rotate_left(__w, __root); 993 __w = __x_parent->_M_left; 994 } 995 __w->_M_color = __x_parent->_M_color; 996 __x_parent->_M_color = _S_black; 997 if (__w->_M_left) 998 __w->_M_left->_M_color = _S_black; 999 _Rotate_right(__x_parent, __root); 1000 break; 1001 } 1002 } 1003 if (__x) 1004 __x->_M_color = _S_black; 1005 } 1006 1007 return __y; 1008 } 1009 }; 1010 #endif 1011 } // namespace __rb_tree 1012 1013 #ifdef __glibcxx_node_extract // >= C++17 1014 template<typename _Tree1, typename _Cmp2> 1015 struct _Rb_tree_merge_helper { }; 1016 #endif 1017 1018 template<typename _Key, typename _Val, typename _KeyOfValue, 1019 typename _Compare, typename _Alloc = allocator<_Val> > 1020 class _Rb_tree 1021 { 1022 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 1023 rebind<_Val>::other _Val_alloc_type; 1024 1025 typedef __gnu_cxx::__alloc_traits<_Val_alloc_type> _Val_alloc_traits; 1026 typedef typename _Val_alloc_traits::pointer _ValPtr; 1027 typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits; 1028 1029 typedef typename _Node_traits::_Node_base _Node_base; 1030 typedef typename _Node_traits::_Node _Node; 1031 1032 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 1033 rebind<_Node>::other _Node_allocator; 1034 1035 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Node_alloc_traits; 1036 1037 protected: 1038 typedef typename _Node_traits::_Base_ptr _Base_ptr; 1039 typedef typename _Node_traits::_Node_ptr _Node_ptr; 1040 1041 private: 1042 // Functor recycling a pool of nodes and using allocation once the pool 1043 // is empty. 1044 struct _Reuse_or_alloc_node 1045 { 1046 _Reuse_or_alloc_node(_Rb_tree& __t) 1047 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t) 1048 { 1049 if (_M_root) 1050 { 1051 _M_root->_M_parent = _Base_ptr(); 1052 1053 if (_M_nodes->_M_left) 1054 _M_nodes = _M_nodes->_M_left; 1055 } 1056 else 1057 _M_nodes = _Base_ptr(); 1058 } 1059 1060 #if __cplusplus >= 201103L 1061 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete; 1062 #endif 1063 1064 ~_Reuse_or_alloc_node() 1065 { 1066 if (_M_root) 1067 _M_t._M_erase(static_cast<_Node&>(*_M_root)._M_node_ptr()); 1068 } 1069 1070 template<typename _Arg> 1071 _Node_ptr 1072 operator()(_GLIBCXX_FWDREF(_Arg) __arg) 1073 { 1074 _Base_ptr __base = _M_extract(); 1075 if (__base) 1076 { 1077 _Node_ptr __node = static_cast<_Node&>(*__base)._M_node_ptr(); 1078 _M_t._M_destroy_node(__node); 1079 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)); 1080 return __node; 1081 } 1082 1083 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); 1084 } 1085 1086 private: 1087 _Base_ptr 1088 _M_extract() 1089 { 1090 if (!_M_nodes) 1091 return _M_nodes; 1092 1093 _Base_ptr __node = _M_nodes; 1094 _M_nodes = _M_nodes->_M_parent; 1095 if (_M_nodes) 1096 { 1097 if (_M_nodes->_M_right == __node) 1098 { 1099 _M_nodes->_M_right = _Base_ptr(); 1100 1101 if (_M_nodes->_M_left) 1102 { 1103 _M_nodes = _M_nodes->_M_left; 1104 1105 while (_M_nodes->_M_right) 1106 _M_nodes = _M_nodes->_M_right; 1107 1108 if (_M_nodes->_M_left) 1109 _M_nodes = _M_nodes->_M_left; 1110 } 1111 } 1112 else // __node is on the left. 1113 _M_nodes->_M_left = _Base_ptr(); 1114 } 1115 else 1116 _M_root = _Base_ptr(); 1117 1118 return __node; 1119 } 1120 1121 _Base_ptr _M_root; 1122 _Base_ptr _M_nodes; 1123 _Rb_tree& _M_t; 1124 }; 1125 1126 // Functor similar to the previous one but without any pool of nodes to 1127 // recycle. 1128 struct _Alloc_node 1129 { 1130 _Alloc_node(_Rb_tree& __t) 1131 : _M_t(__t) { } 1132 1133 template<typename _Arg> 1134 _Node_ptr 1135 operator()(_GLIBCXX_FWDREF(_Arg) __arg) const 1136 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } 1137 1138 private: 1139 _Rb_tree& _M_t; 1140 }; 1141 1142 public: 1143 typedef _Key key_type; 1144 typedef _Val value_type; 1145 typedef value_type* pointer; 1146 typedef const value_type* const_pointer; 1147 typedef value_type& reference; 1148 typedef const value_type& const_reference; 1149 typedef size_t size_type; 1150 typedef ptrdiff_t difference_type; 1151 typedef _Alloc allocator_type; 1152 1153 _Node_allocator& 1154 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT 1155 { return this->_M_impl; } 1156 1157 const _Node_allocator& 1158 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT 1159 { return this->_M_impl; } 1160 1161 allocator_type 1162 get_allocator() const _GLIBCXX_NOEXCEPT 1163 { return allocator_type(_M_get_Node_allocator()); } 1164 1165 protected: 1166 _Node_ptr 1167 _M_get_node() 1168 { 1169 #if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1170 return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); 1171 #else 1172 #pragma GCC diagnostic push 1173 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 1174 using __alloc_pointer = typename _Node_alloc_traits::pointer; 1175 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value) 1176 return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); 1177 else 1178 { 1179 auto __ptr = 1180 _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); 1181 return std::__to_address(__ptr); 1182 } 1183 #pragma GCC diagnostic pop 1184 #endif 1185 } 1186 1187 void 1188 _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT 1189 { 1190 #if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1191 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); 1192 #else 1193 #pragma GCC diagnostic push 1194 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 1195 using __alloc_pointer = typename _Node_alloc_traits::pointer; 1196 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value) 1197 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); 1198 else 1199 { 1200 // When not using the allocator's pointer type internally we must 1201 // convert __p to __alloc_pointer so it can be deallocated. 1202 auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p); 1203 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ap, 1); 1204 } 1205 #pragma GCC diagnostic pop 1206 #endif 1207 } 1208 1209 #if __cplusplus < 201103L 1210 void 1211 _M_construct_node(_Node_ptr __node, const value_type& __x) 1212 { 1213 __try 1214 { get_allocator().construct(__node->_M_valptr(), __x); } 1215 __catch(...) 1216 { 1217 _M_put_node(__node); 1218 __throw_exception_again; 1219 } 1220 } 1221 1222 _Node_ptr 1223 _M_create_node(const value_type& __x) 1224 { 1225 _Node_ptr __tmp = _M_get_node(); 1226 _M_construct_node(__tmp, __x); 1227 return __tmp; 1228 } 1229 #else 1230 template<typename... _Args> 1231 void 1232 _M_construct_node(_Node_ptr __node, _Args&&... __args) 1233 { 1234 __try 1235 { 1236 ::new(std::addressof(*__node)) _Node; 1237 _Node_alloc_traits::construct(_M_get_Node_allocator(), 1238 __node->_M_valptr(), 1239 std::forward<_Args>(__args)...); 1240 } 1241 __catch(...) 1242 { 1243 __node->~_Node(); 1244 _M_put_node(__node); 1245 __throw_exception_again; 1246 } 1247 } 1248 1249 template<typename... _Args> 1250 _Node_ptr 1251 _M_create_node(_Args&&... __args) 1252 { 1253 _Node_ptr __tmp = _M_get_node(); 1254 _M_construct_node(__tmp, std::forward<_Args>(__args)...); 1255 return __tmp; 1256 } 1257 #endif 1258 1259 void 1260 _M_destroy_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT 1261 { 1262 #if __cplusplus < 201103L 1263 get_allocator().destroy(__p->_M_valptr()); 1264 #else 1265 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); 1266 __p->~_Node(); 1267 #endif 1268 } 1269 1270 void 1271 _M_drop_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT 1272 { 1273 _M_destroy_node(__p); 1274 _M_put_node(__p); 1275 } 1276 1277 template<bool _MoveValue, typename _NodeGen> 1278 _Node_ptr 1279 _M_clone_node(_Node_ptr __x, _NodeGen& __node_gen) 1280 { 1281 #if __cplusplus >= 201103L 1282 using _Vp = __conditional_t<_MoveValue, 1283 value_type&&, 1284 const value_type&>; 1285 #endif 1286 _Node_ptr __tmp 1287 = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr())); 1288 __tmp->_M_color = __x->_M_color; 1289 __tmp->_M_left = __tmp->_M_right = _Base_ptr(); 1290 return __tmp; 1291 } 1292 1293 protected: 1294 typedef typename _Node_traits::_Header_t _Header_t; 1295 1296 #if _GLIBCXX_INLINE_VERSION 1297 template<typename _Key_compare> 1298 #else 1299 // Unused _Is_pod_comparator is kept as it is part of mangled name. 1300 template<typename _Key_compare, 1301 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)> 1302 #endif 1303 struct _Rb_tree_impl 1304 : public _Node_allocator 1305 , public _Rb_tree_key_compare<_Key_compare> 1306 , public _Header_t 1307 { 1308 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare; 1309 1310 _Rb_tree_impl() 1311 _GLIBCXX_NOEXCEPT_IF( 1312 is_nothrow_default_constructible<_Node_allocator>::value 1313 && is_nothrow_default_constructible<_Base_key_compare>::value ) 1314 : _Node_allocator() 1315 { } 1316 1317 _Rb_tree_impl(const _Rb_tree_impl& __x) 1318 : _Node_allocator(_Node_alloc_traits::_S_select_on_copy(__x)) 1319 , _Base_key_compare(__x._M_key_compare) 1320 , _Header_t() 1321 { } 1322 1323 #if __cplusplus < 201103L 1324 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) 1325 : _Node_allocator(__a), _Base_key_compare(__comp) 1326 { } 1327 #else 1328 _Rb_tree_impl(_Rb_tree_impl&&) 1329 noexcept( is_nothrow_move_constructible<_Base_key_compare>::value ) 1330 = default; 1331 1332 explicit 1333 _Rb_tree_impl(_Node_allocator&& __a) 1334 : _Node_allocator(std::move(__a)) 1335 { } 1336 1337 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) 1338 : _Node_allocator(std::move(__a)), 1339 _Base_key_compare(std::move(__x)), 1340 _Header_t(std::move(__x)) 1341 { } 1342 1343 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) 1344 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp) 1345 { } 1346 #endif 1347 }; 1348 1349 _Rb_tree_impl<_Compare> _M_impl; 1350 1351 protected: 1352 _Base_ptr& 1353 _M_root() _GLIBCXX_NOEXCEPT 1354 { return this->_M_impl._M_header._M_parent; } 1355 1356 _Base_ptr 1357 _M_root() const _GLIBCXX_NOEXCEPT 1358 { return this->_M_impl._M_header._M_parent; } 1359 1360 _Base_ptr& 1361 _M_leftmost() _GLIBCXX_NOEXCEPT 1362 { return this->_M_impl._M_header._M_left; } 1363 1364 _Base_ptr 1365 _M_leftmost() const _GLIBCXX_NOEXCEPT 1366 { return this->_M_impl._M_header._M_left; } 1367 1368 _Base_ptr& 1369 _M_rightmost() _GLIBCXX_NOEXCEPT 1370 { return this->_M_impl._M_header._M_right; } 1371 1372 _Base_ptr 1373 _M_rightmost() const _GLIBCXX_NOEXCEPT 1374 { return this->_M_impl._M_header._M_right; } 1375 1376 _Base_ptr 1377 _M_begin() const _GLIBCXX_NOEXCEPT 1378 { return this->_M_impl._M_header._M_parent; } 1379 1380 _Node_ptr 1381 _M_begin_node() const _GLIBCXX_NOEXCEPT 1382 { 1383 _Base_ptr __begin = this->_M_impl._M_header._M_parent; 1384 return __begin 1385 ? static_cast<_Node&>(*__begin)._M_node_ptr() 1386 : _Node_ptr(); 1387 } 1388 1389 _Base_ptr 1390 _M_end() const _GLIBCXX_NOEXCEPT 1391 { return this->_M_impl._M_header._M_base_ptr(); } 1392 1393 static const _Key& 1394 _S_key(const _Node& __node) 1395 { 1396 #if __cplusplus >= 201103L 1397 // If we're asking for the key we're presumably using the comparison 1398 // object, and so this is a good place to sanity check it. 1399 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{}, 1400 "comparison object must be invocable " 1401 "with two arguments of key type"); 1402 # if __cplusplus >= 201703L 1403 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1404 // 2542. Missing const requirements for associative containers 1405 if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{}) 1406 static_assert( 1407 is_invocable_v<const _Compare&, const _Key&, const _Key&>, 1408 "comparison object must be invocable as const"); 1409 # endif // C++17 1410 #endif // C++11 1411 1412 return _KeyOfValue()(*__node._M_valptr()); 1413 } 1414 1415 static const _Key& 1416 _S_key(_Base_ptr __x) 1417 { return _S_key(static_cast<const _Node&>(*__x)); } 1418 1419 static const _Key& 1420 _S_key(_Node_ptr __x) 1421 { return _S_key(*__x); } 1422 1423 static _Base_ptr 1424 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT 1425 { return __x->_M_left; } 1426 1427 static _Node_ptr 1428 _S_left(_Node_ptr __x) 1429 { 1430 return __x->_M_left 1431 ? static_cast<_Node&>(*__x->_M_left)._M_node_ptr() 1432 : _Node_ptr(); 1433 } 1434 1435 static _Base_ptr 1436 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT 1437 { return __x->_M_right; } 1438 1439 static _Node_ptr 1440 _S_right(_Node_ptr __x) _GLIBCXX_NOEXCEPT 1441 { 1442 return __x->_M_right 1443 ? static_cast<_Node&>(*__x->_M_right)._M_node_ptr() 1444 : _Node_ptr(); 1445 } 1446 1447 public: 1448 typedef typename _Node_traits::_Iterator iterator; 1449 typedef typename _Node_traits::_Const_iterator const_iterator; 1450 1451 typedef std::reverse_iterator<iterator> reverse_iterator; 1452 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1453 1454 #ifdef __glibcxx_node_extract // >= C++17 1455 using node_type = _Node_handle<_Key, _Val, _Node_allocator>; 1456 using insert_return_type = _Node_insert_return< 1457 __conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>, 1458 node_type>; 1459 #endif 1460 1461 pair<_Base_ptr, _Base_ptr> 1462 _M_get_insert_unique_pos(const key_type& __k); 1463 1464 pair<_Base_ptr, _Base_ptr> 1465 _M_get_insert_equal_pos(const key_type& __k); 1466 1467 pair<_Base_ptr, _Base_ptr> 1468 _M_get_insert_hint_unique_pos(const_iterator __pos, 1469 const key_type& __k); 1470 1471 pair<_Base_ptr, _Base_ptr> 1472 _M_get_insert_hint_equal_pos(const_iterator __pos, 1473 const key_type& __k); 1474 1475 private: 1476 #if __cplusplus >= 201103L 1477 template<typename _Arg, typename _NodeGen> 1478 iterator 1479 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); 1480 1481 iterator 1482 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Node_ptr __z); 1483 1484 template<typename _Arg> 1485 iterator 1486 _M_insert_lower(_Base_ptr __y, _Arg&& __v); 1487 1488 template<typename _Arg> 1489 iterator 1490 _M_insert_equal_lower(_Arg&& __x); 1491 1492 iterator 1493 _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z); 1494 1495 iterator 1496 _M_insert_equal_lower_node(_Node_ptr __z); 1497 #else 1498 template<typename _NodeGen> 1499 iterator 1500 _M_insert_(_Base_ptr __x, _Base_ptr __y, 1501 const value_type& __v, _NodeGen&); 1502 1503 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1504 // 233. Insertion hints in associative containers. 1505 iterator 1506 _M_insert_lower(_Base_ptr __y, const value_type& __v); 1507 1508 iterator 1509 _M_insert_equal_lower(const value_type& __x); 1510 #endif 1511 1512 enum { __as_lvalue, __as_rvalue }; 1513 1514 template<bool _MoveValues, typename _NodeGen> 1515 _Base_ptr 1516 _M_copy(_Node_ptr, _Base_ptr, _NodeGen&); 1517 1518 template<bool _MoveValues, typename _NodeGen> 1519 _Base_ptr 1520 _M_copy(const _Rb_tree& __x, _NodeGen& __gen) 1521 { 1522 _Base_ptr __root = 1523 _M_copy<_MoveValues>(__x._M_begin_node(), _M_end(), __gen); 1524 _M_leftmost() = _Node_base::_S_minimum(__root); 1525 _M_rightmost() = _Node_base::_S_maximum(__root); 1526 _M_impl._M_node_count = __x._M_impl._M_node_count; 1527 return __root; 1528 } 1529 1530 _Base_ptr 1531 _M_copy(const _Rb_tree& __x) 1532 { 1533 _Alloc_node __an(*this); 1534 return _M_copy<__as_lvalue>(__x, __an); 1535 } 1536 1537 void 1538 _M_erase(_Node_ptr __x); 1539 1540 _Base_ptr 1541 _M_lower_bound(_Base_ptr __x, _Base_ptr __y, 1542 const _Key& __k) const; 1543 1544 _Base_ptr 1545 _M_upper_bound(_Base_ptr __x, _Base_ptr __y, 1546 const _Key& __k) const; 1547 1548 public: 1549 // allocation/deallocation 1550 #if __cplusplus < 201103L 1551 _Rb_tree() { } 1552 #else 1553 _Rb_tree() = default; 1554 #endif 1555 1556 _Rb_tree(const _Compare& __comp, 1557 const allocator_type& __a = allocator_type()) 1558 : _M_impl(__comp, _Node_allocator(__a)) { } 1559 1560 _Rb_tree(const _Rb_tree& __x) 1561 : _M_impl(__x._M_impl) 1562 { 1563 if (__x._M_root()) 1564 _M_root() = _M_copy(__x); 1565 } 1566 1567 #if __cplusplus >= 201103L 1568 _Rb_tree(const allocator_type& __a) 1569 : _M_impl(_Node_allocator(__a)) 1570 { } 1571 1572 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) 1573 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) 1574 { 1575 if (__x._M_root()) 1576 _M_root() = _M_copy(__x); 1577 } 1578 1579 _Rb_tree(_Rb_tree&&) = default; 1580 1581 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a) 1582 : _Rb_tree(std::move(__x), _Node_allocator(__a)) 1583 { } 1584 1585 private: 1586 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type) 1587 noexcept(is_nothrow_default_constructible<_Compare>::value) 1588 : _M_impl(std::move(__x._M_impl), std::move(__a)) 1589 { } 1590 1591 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type) 1592 : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) 1593 { 1594 if (__x._M_root()) 1595 _M_move_data(__x, false_type{}); 1596 } 1597 1598 public: 1599 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) 1600 noexcept( noexcept( 1601 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(), 1602 std::declval<typename _Node_alloc_traits::is_always_equal>())) ) 1603 : _Rb_tree(std::move(__x), std::move(__a), 1604 typename _Node_alloc_traits::is_always_equal{}) 1605 { } 1606 #endif 1607 1608 ~_Rb_tree() _GLIBCXX_NOEXCEPT 1609 { _M_erase(_M_begin_node()); } 1610 1611 _Rb_tree& 1612 operator=(const _Rb_tree& __x); 1613 1614 // Accessors. 1615 _Compare 1616 key_comp() const 1617 { return _M_impl._M_key_compare; } 1618 1619 iterator 1620 begin() _GLIBCXX_NOEXCEPT 1621 { return iterator(this->_M_impl._M_header._M_left); } 1622 1623 const_iterator 1624 begin() const _GLIBCXX_NOEXCEPT 1625 { return const_iterator(this->_M_impl._M_header._M_left); } 1626 1627 iterator 1628 end() _GLIBCXX_NOEXCEPT 1629 { return iterator(_M_end()); } 1630 1631 const_iterator 1632 end() const _GLIBCXX_NOEXCEPT 1633 { return const_iterator(_M_end()); } 1634 1635 reverse_iterator 1636 rbegin() _GLIBCXX_NOEXCEPT 1637 { return reverse_iterator(end()); } 1638 1639 const_reverse_iterator 1640 rbegin() const _GLIBCXX_NOEXCEPT 1641 { return const_reverse_iterator(end()); } 1642 1643 reverse_iterator 1644 rend() _GLIBCXX_NOEXCEPT 1645 { return reverse_iterator(begin()); } 1646 1647 const_reverse_iterator 1648 rend() const _GLIBCXX_NOEXCEPT 1649 { return const_reverse_iterator(begin()); } 1650 1651 _GLIBCXX_NODISCARD bool 1652 empty() const _GLIBCXX_NOEXCEPT 1653 { return _M_impl._M_node_count == 0; } 1654 1655 size_type 1656 size() const _GLIBCXX_NOEXCEPT 1657 { return _M_impl._M_node_count; } 1658 1659 size_type 1660 max_size() const _GLIBCXX_NOEXCEPT 1661 { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); } 1662 1663 void 1664 swap(_Rb_tree& __t) 1665 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value); 1666 1667 // Insert/erase. 1668 #if __cplusplus >= 201103L 1669 template<typename _Arg> 1670 pair<iterator, bool> 1671 _M_insert_unique(_Arg&& __x); 1672 1673 template<typename _Arg> 1674 iterator 1675 _M_insert_equal(_Arg&& __x); 1676 1677 template<typename _Arg, typename _NodeGen> 1678 iterator 1679 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&); 1680 1681 template<typename _Arg> 1682 iterator 1683 _M_insert_unique_(const_iterator __pos, _Arg&& __x) 1684 { 1685 _Alloc_node __an(*this); 1686 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an); 1687 } 1688 1689 template<typename _Arg, typename _NodeGen> 1690 iterator 1691 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&); 1692 1693 template<typename _Arg> 1694 iterator 1695 _M_insert_equal_(const_iterator __pos, _Arg&& __x) 1696 { 1697 _Alloc_node __an(*this); 1698 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an); 1699 } 1700 1701 template<typename... _Args> 1702 pair<iterator, bool> 1703 _M_emplace_unique(_Args&&... __args); 1704 1705 template<typename... _Args> 1706 iterator 1707 _M_emplace_equal(_Args&&... __args); 1708 1709 template<typename... _Args> 1710 iterator 1711 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); 1712 1713 template<typename... _Args> 1714 iterator 1715 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); 1716 1717 template<typename _Iter> 1718 using __same_value_type 1719 = is_same<value_type, typename iterator_traits<_Iter>::value_type>; 1720 1721 template<typename _InputIterator> 1722 __enable_if_t<__same_value_type<_InputIterator>::value> 1723 _M_insert_range_unique(_InputIterator __first, _InputIterator __last) 1724 { 1725 _Alloc_node __an(*this); 1726 for (; __first != __last; ++__first) 1727 _M_insert_unique_(end(), *__first, __an); 1728 } 1729 1730 template<typename _InputIterator> 1731 __enable_if_t<!__same_value_type<_InputIterator>::value> 1732 _M_insert_range_unique(_InputIterator __first, _InputIterator __last) 1733 { 1734 for (; __first != __last; ++__first) 1735 _M_emplace_unique(*__first); 1736 } 1737 1738 template<typename _InputIterator> 1739 __enable_if_t<__same_value_type<_InputIterator>::value> 1740 _M_insert_range_equal(_InputIterator __first, _InputIterator __last) 1741 { 1742 _Alloc_node __an(*this); 1743 for (; __first != __last; ++__first) 1744 _M_insert_equal_(end(), *__first, __an); 1745 } 1746 1747 template<typename _InputIterator> 1748 __enable_if_t<!__same_value_type<_InputIterator>::value> 1749 _M_insert_range_equal(_InputIterator __first, _InputIterator __last) 1750 { 1751 for (; __first != __last; ++__first) 1752 _M_emplace_equal(*__first); 1753 } 1754 #else 1755 pair<iterator, bool> 1756 _M_insert_unique(const value_type& __x); 1757 1758 iterator 1759 _M_insert_equal(const value_type& __x); 1760 1761 template<typename _NodeGen> 1762 iterator 1763 _M_insert_unique_(const_iterator __pos, const value_type& __x, 1764 _NodeGen&); 1765 1766 iterator 1767 _M_insert_unique_(const_iterator __pos, const value_type& __x) 1768 { 1769 _Alloc_node __an(*this); 1770 return _M_insert_unique_(__pos, __x, __an); 1771 } 1772 1773 template<typename _NodeGen> 1774 iterator 1775 _M_insert_equal_(const_iterator __pos, const value_type& __x, 1776 _NodeGen&); 1777 iterator 1778 _M_insert_equal_(const_iterator __pos, const value_type& __x) 1779 { 1780 _Alloc_node __an(*this); 1781 return _M_insert_equal_(__pos, __x, __an); 1782 } 1783 1784 template<typename _InputIterator> 1785 void 1786 _M_insert_range_unique(_InputIterator __first, _InputIterator __last) 1787 { 1788 _Alloc_node __an(*this); 1789 for (; __first != __last; ++__first) 1790 _M_insert_unique_(end(), *__first, __an); 1791 } 1792 1793 template<typename _InputIterator> 1794 void 1795 _M_insert_range_equal(_InputIterator __first, _InputIterator __last) 1796 { 1797 _Alloc_node __an(*this); 1798 for (; __first != __last; ++__first) 1799 _M_insert_equal_(end(), *__first, __an); 1800 } 1801 #endif 1802 1803 private: 1804 void 1805 _M_erase_aux(const_iterator __position); 1806 1807 void 1808 _M_erase_aux(const_iterator __first, const_iterator __last); 1809 1810 public: 1811 #if __cplusplus >= 201103L 1812 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1813 // DR 130. Associative erase should return an iterator. 1814 _GLIBCXX_ABI_TAG_CXX11 1815 iterator 1816 erase(const_iterator __position) 1817 { 1818 __glibcxx_assert(__position != end()); 1819 const_iterator __result = __position; 1820 ++__result; 1821 _M_erase_aux(__position); 1822 return iterator(__result._M_node); 1823 } 1824 1825 // LWG 2059. 1826 _GLIBCXX_ABI_TAG_CXX11 1827 iterator 1828 erase(iterator __position) 1829 { 1830 __glibcxx_assert(__position != end()); 1831 iterator __result = __position; 1832 ++__result; 1833 _M_erase_aux(__position); 1834 return __result; 1835 } 1836 #else 1837 void 1838 erase(iterator __position) 1839 { 1840 __glibcxx_assert(__position != end()); 1841 _M_erase_aux(__position); 1842 } 1843 1844 void 1845 erase(const_iterator __position) 1846 { 1847 __glibcxx_assert(__position != end()); 1848 _M_erase_aux(__position); 1849 } 1850 #endif 1851 1852 size_type 1853 erase(const key_type& __x); 1854 1855 #if __cplusplus >= 201103L 1856 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1857 // DR 130. Associative erase should return an iterator. 1858 _GLIBCXX_ABI_TAG_CXX11 1859 iterator 1860 erase(const_iterator __first, const_iterator __last) 1861 { 1862 _M_erase_aux(__first, __last); 1863 return iterator(__last._M_node); 1864 } 1865 #else 1866 void 1867 erase(iterator __first, iterator __last) 1868 { _M_erase_aux(__first, __last); } 1869 1870 void 1871 erase(const_iterator __first, const_iterator __last) 1872 { _M_erase_aux(__first, __last); } 1873 #endif 1874 1875 void 1876 clear() _GLIBCXX_NOEXCEPT 1877 { 1878 _M_erase(_M_begin_node()); 1879 _M_impl._M_reset(); 1880 } 1881 1882 // Set operations. 1883 iterator 1884 find(const key_type& __k); 1885 1886 const_iterator 1887 find(const key_type& __k) const; 1888 1889 size_type 1890 count(const key_type& __k) const; 1891 1892 iterator 1893 lower_bound(const key_type& __k) 1894 { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); } 1895 1896 const_iterator 1897 lower_bound(const key_type& __k) const 1898 { 1899 return const_iterator 1900 (_M_lower_bound(_M_begin(), _M_end(), __k)); 1901 } 1902 1903 iterator 1904 upper_bound(const key_type& __k) 1905 { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); } 1906 1907 const_iterator 1908 upper_bound(const key_type& __k) const 1909 { 1910 return const_iterator 1911 (_M_upper_bound(_M_begin(), _M_end(), __k)); 1912 } 1913 1914 pair<iterator, iterator> 1915 equal_range(const key_type& __k); 1916 1917 pair<const_iterator, const_iterator> 1918 equal_range(const key_type& __k) const; 1919 1920 #if __cplusplus >= 201402L 1921 template<typename _Kt, 1922 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1923 iterator 1924 _M_find_tr(const _Kt& __k) 1925 { 1926 const _Rb_tree* __const_this = this; 1927 return iterator(__const_this->_M_find_tr(__k)._M_node); 1928 } 1929 1930 template<typename _Kt, 1931 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1932 const_iterator 1933 _M_find_tr(const _Kt& __k) const 1934 { 1935 const_iterator __j(_M_lower_bound_tr(__k)); 1936 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node))) 1937 __j = end(); 1938 return __j; 1939 } 1940 1941 template<typename _Kt, 1942 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1943 size_type 1944 _M_count_tr(const _Kt& __k) const 1945 { 1946 auto __p = _M_equal_range_tr(__k); 1947 return std::distance(__p.first, __p.second); 1948 } 1949 1950 template<typename _Kt, 1951 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1952 _Base_ptr 1953 _M_lower_bound_tr(const _Kt& __k) const 1954 { 1955 auto __x = _M_begin(); 1956 auto __y = _M_end(); 1957 while (__x) 1958 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 1959 { 1960 __y = __x; 1961 __x = _S_left(__x); 1962 } 1963 else 1964 __x = _S_right(__x); 1965 return __y; 1966 } 1967 1968 template<typename _Kt, 1969 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1970 _Base_ptr 1971 _M_upper_bound_tr(const _Kt& __k) const 1972 { 1973 auto __x = _M_begin(); 1974 auto __y = _M_end(); 1975 while (__x) 1976 if (_M_impl._M_key_compare(__k, _S_key(__x))) 1977 { 1978 __y = __x; 1979 __x = _S_left(__x); 1980 } 1981 else 1982 __x = _S_right(__x); 1983 return __y; 1984 } 1985 1986 template<typename _Kt, 1987 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1988 pair<iterator, iterator> 1989 _M_equal_range_tr(const _Kt& __k) 1990 { 1991 const _Rb_tree* __const_this = this; 1992 auto __ret = __const_this->_M_equal_range_tr(__k); 1993 return 1994 { iterator(__ret.first._M_node), iterator(__ret.second._M_node) }; 1995 } 1996 1997 template<typename _Kt, 1998 typename _Req = __has_is_transparent_t<_Compare, _Kt>> 1999 pair<const_iterator, const_iterator> 2000 _M_equal_range_tr(const _Kt& __k) const 2001 { 2002 const_iterator __low(_M_lower_bound_tr(__k)); 2003 auto __high = __low; 2004 auto& __cmp = _M_impl._M_key_compare; 2005 while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) 2006 ++__high; 2007 return { __low, __high }; 2008 } 2009 #endif 2010 2011 // Debugging. 2012 bool 2013 __rb_verify() const; 2014 2015 #if __cplusplus >= 201103L 2016 _Rb_tree& 2017 operator=(_Rb_tree&&) 2018 noexcept(_Node_alloc_traits::_S_nothrow_move() 2019 && is_nothrow_move_assignable<_Compare>::value); 2020 2021 template<typename _Iterator> 2022 void 2023 _M_assign_unique(_Iterator, _Iterator); 2024 2025 template<typename _Iterator> 2026 void 2027 _M_assign_equal(_Iterator, _Iterator); 2028 2029 private: 2030 // Move elements from container with equal allocator. 2031 void 2032 _M_move_data(_Rb_tree& __x, true_type) 2033 { _M_impl._M_move_data(__x._M_impl); } 2034 2035 // Move elements from container with possibly non-equal allocator, 2036 // which might result in a copy not a move. 2037 void 2038 _M_move_data(_Rb_tree&, false_type); 2039 2040 // Move assignment from container with equal allocator. 2041 void 2042 _M_move_assign(_Rb_tree&, true_type); 2043 2044 // Move assignment from container with possibly non-equal allocator, 2045 // which might result in a copy not a move. 2046 void 2047 _M_move_assign(_Rb_tree&, false_type); 2048 #endif 2049 2050 #if __glibcxx_node_extract // >= C++17 2051 static _Node_ptr 2052 _S_adapt(typename _Node_alloc_traits::pointer __ptr) 2053 { 2054 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 2055 return __ptr; 2056 #else 2057 #pragma GCC diagnostic push 2058 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 2059 using __alloc_ptr = typename _Node_alloc_traits::pointer; 2060 if constexpr (is_same<_Node_ptr, __alloc_ptr>::value) 2061 return __ptr; 2062 else 2063 return std::__to_address(__ptr); 2064 #pragma GCC diagnostic pop 2065 #endif 2066 } 2067 2068 public: 2069 /// Re-insert an extracted node. 2070 insert_return_type 2071 _M_reinsert_node_unique(node_type&& __nh) 2072 { 2073 insert_return_type __ret; 2074 if (__nh.empty()) 2075 __ret.position = end(); 2076 else 2077 { 2078 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 2079 2080 auto __res = _M_get_insert_unique_pos(__nh._M_key()); 2081 if (__res.second) 2082 { 2083 __ret.position 2084 = _M_insert_node(__res.first, __res.second, 2085 _S_adapt(__nh._M_ptr)); 2086 __nh.release(); 2087 __ret.inserted = true; 2088 } 2089 else 2090 { 2091 __ret.node = std::move(__nh); 2092 __ret.position = iterator(__res.first); 2093 __ret.inserted = false; 2094 } 2095 } 2096 return __ret; 2097 } 2098 2099 /// Re-insert an extracted node. 2100 iterator 2101 _M_reinsert_node_equal(node_type&& __nh) 2102 { 2103 iterator __ret; 2104 if (__nh.empty()) 2105 __ret = end(); 2106 else 2107 { 2108 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 2109 auto __res = _M_get_insert_equal_pos(__nh._M_key()); 2110 if (__res.second) 2111 __ret = _M_insert_node(__res.first, __res.second, 2112 _S_adapt(__nh._M_ptr)); 2113 else 2114 __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr)); 2115 __nh.release(); 2116 } 2117 return __ret; 2118 } 2119 2120 /// Re-insert an extracted node. 2121 iterator 2122 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh) 2123 { 2124 iterator __ret; 2125 if (__nh.empty()) 2126 __ret = end(); 2127 else 2128 { 2129 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 2130 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key()); 2131 if (__res.second) 2132 { 2133 __ret = _M_insert_node(__res.first, __res.second, 2134 _S_adapt(__nh._M_ptr)); 2135 __nh.release(); 2136 } 2137 else 2138 __ret = iterator(__res.first); 2139 } 2140 return __ret; 2141 } 2142 2143 /// Re-insert an extracted node. 2144 iterator 2145 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh) 2146 { 2147 iterator __ret; 2148 if (__nh.empty()) 2149 __ret = end(); 2150 else 2151 { 2152 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); 2153 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key()); 2154 if (__res.second) 2155 __ret = _M_insert_node(__res.first, __res.second, 2156 _S_adapt(__nh._M_ptr)); 2157 else 2158 __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr)); 2159 __nh.release(); 2160 } 2161 return __ret; 2162 } 2163 2164 /// Extract a node. 2165 node_type 2166 extract(const_iterator __pos) 2167 { 2168 auto __ptr = _Node_traits::_S_rebalance_for_erase 2169 (__pos._M_node, _M_impl._M_header); 2170 --_M_impl._M_node_count; 2171 auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr(); 2172 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 2173 return { __node_ptr, _M_get_Node_allocator() }; 2174 #else 2175 #pragma GCC diagnostic push 2176 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 2177 using __alloc_ptr = typename _Node_alloc_traits::pointer; 2178 if constexpr (is_same<_Node_ptr, __alloc_ptr>::value) 2179 return { __node_ptr, _M_get_Node_allocator() }; 2180 else 2181 { 2182 auto __ap = pointer_traits<__alloc_ptr>::pointer_to(*__node_ptr); 2183 return { __ap, _M_get_Node_allocator() }; 2184 } 2185 #pragma GCC diagnostic pop 2186 #endif 2187 } 2188 2189 /// Extract a node. 2190 node_type 2191 extract(const key_type& __k) 2192 { 2193 node_type __nh; 2194 auto __pos = find(__k); 2195 if (__pos != end()) 2196 __nh = extract(const_iterator(__pos)); 2197 return __nh; 2198 } 2199 2200 template<typename _Compare2> 2201 using _Compatible_tree 2202 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>; 2203 2204 template<typename, typename> 2205 friend struct _Rb_tree_merge_helper; 2206 2207 /// Merge from a compatible container into one with unique keys. 2208 template<typename _Compare2> 2209 void 2210 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept 2211 { 2212 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; 2213 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 2214 { 2215 auto __pos = __i++; 2216 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos)); 2217 if (__res.second) 2218 { 2219 auto& __src_impl = _Merge_helper::_S_get_impl(__src); 2220 auto __ptr = _Node_traits::_S_rebalance_for_erase 2221 (__pos._M_node, __src_impl._M_header); 2222 --__src_impl._M_node_count; 2223 auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr(); 2224 _M_insert_node(__res.first, __res.second, __node_ptr); 2225 } 2226 } 2227 } 2228 2229 /// Merge from a compatible container into one with equivalent keys. 2230 template<typename _Compare2> 2231 void 2232 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept 2233 { 2234 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>; 2235 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 2236 { 2237 auto __pos = __i++; 2238 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos)); 2239 if (__res.second) 2240 { 2241 auto& __src_impl = _Merge_helper::_S_get_impl(__src); 2242 auto __ptr = _Node_traits::_S_rebalance_for_erase 2243 (__pos._M_node, __src_impl._M_header); 2244 --__src_impl._M_node_count; 2245 auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr(); 2246 _M_insert_node(__res.first, __res.second, __node_ptr); 2247 } 2248 } 2249 } 2250 #endif // C++17 node_extract 2251 2252 friend bool 2253 operator==(const _Rb_tree& __x, const _Rb_tree& __y) 2254 { 2255 return __x.size() == __y.size() 2256 && std::equal(__x.begin(), __x.end(), __y.begin()); 2257 } 2258 2259 #if __cpp_lib_three_way_comparison 2260 friend auto 2261 operator<=>(const _Rb_tree& __x, const _Rb_tree& __y) 2262 { 2263 if constexpr (requires { typename __detail::__synth3way_t<_Val>; }) 2264 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), 2265 __y.begin(), __y.end(), 2266 __detail::__synth3way); 2267 } 2268 #else 2269 friend bool 2270 operator<(const _Rb_tree& __x, const _Rb_tree& __y) 2271 { 2272 return std::lexicographical_compare(__x.begin(), __x.end(), 2273 __y.begin(), __y.end()); 2274 } 2275 #endif 2276 2277 private: 2278 #if __cplusplus >= 201103L 2279 // An RAII _Node handle 2280 struct _Auto_node 2281 { 2282 template<typename... _Args> 2283 _Auto_node(_Rb_tree& __t, _Args&&... __args) 2284 : _M_t(__t), 2285 _M_node(__t._M_create_node(std::forward<_Args>(__args)...)) 2286 { } 2287 2288 ~_Auto_node() 2289 { 2290 if (_M_node) 2291 _M_t._M_drop_node(_M_node); 2292 } 2293 2294 _Auto_node(_Auto_node&& __n) 2295 : _M_t(__n._M_t), _M_node(__n._M_node) 2296 { __n._M_node = nullptr; } 2297 2298 const _Key& 2299 _M_key() const 2300 { return _S_key(_M_node); } 2301 2302 iterator 2303 _M_insert(pair<_Base_ptr, _Base_ptr> __p) 2304 { 2305 auto __it = _M_t._M_insert_node(__p.first, __p.second, _M_node); 2306 _M_node = nullptr; 2307 return __it; 2308 } 2309 2310 iterator 2311 _M_insert_equal_lower() 2312 { 2313 auto __it = _M_t._M_insert_equal_lower_node(_M_node); 2314 _M_node = nullptr; 2315 return __it; 2316 } 2317 2318 _Rb_tree& _M_t; 2319 _Node_ptr _M_node; 2320 }; 2321 #endif // C++11 2322 }; 2323 2324 template<typename _Key, typename _Val, typename _KeyOfValue, 2325 typename _Compare, typename _Alloc> 2326 inline void 2327 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, 2328 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) 2329 { __x.swap(__y); } 2330 2331 #if __cplusplus >= 201103L 2332 template<typename _Key, typename _Val, typename _KeyOfValue, 2333 typename _Compare, typename _Alloc> 2334 void 2335 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2336 _M_move_data(_Rb_tree& __x, false_type) 2337 { 2338 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 2339 _M_move_data(__x, true_type()); 2340 else 2341 { 2342 constexpr bool __move = !__move_if_noexcept_cond<value_type>::value; 2343 _Alloc_node __an(*this); 2344 _M_root() = _M_copy<__move>(__x, __an); 2345 if _GLIBCXX17_CONSTEXPR (__move) 2346 __x.clear(); 2347 } 2348 } 2349 2350 template<typename _Key, typename _Val, typename _KeyOfValue, 2351 typename _Compare, typename _Alloc> 2352 inline void 2353 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2354 _M_move_assign(_Rb_tree& __x, true_type) 2355 { 2356 clear(); 2357 if (__x._M_root()) 2358 _M_move_data(__x, true_type()); 2359 std::__alloc_on_move(_M_get_Node_allocator(), 2360 __x._M_get_Node_allocator()); 2361 } 2362 2363 template<typename _Key, typename _Val, typename _KeyOfValue, 2364 typename _Compare, typename _Alloc> 2365 void 2366 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2367 _M_move_assign(_Rb_tree& __x, false_type) 2368 { 2369 if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) 2370 return _M_move_assign(__x, true_type{}); 2371 2372 // Try to move each node reusing existing nodes and copying __x nodes 2373 // structure. 2374 _Reuse_or_alloc_node __roan(*this); 2375 _M_impl._M_reset(); 2376 if (__x._M_root()) 2377 { 2378 _M_root() = _M_copy<__as_rvalue>(__x, __roan); 2379 __x.clear(); 2380 } 2381 } 2382 2383 template<typename _Key, typename _Val, typename _KeyOfValue, 2384 typename _Compare, typename _Alloc> 2385 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 2386 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2387 operator=(_Rb_tree&& __x) 2388 noexcept(_Node_alloc_traits::_S_nothrow_move() 2389 && is_nothrow_move_assignable<_Compare>::value) 2390 { 2391 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare); 2392 _M_move_assign(__x, 2393 __bool_constant<_Node_alloc_traits::_S_nothrow_move()>()); 2394 return *this; 2395 } 2396 2397 template<typename _Key, typename _Val, typename _KeyOfValue, 2398 typename _Compare, typename _Alloc> 2399 template<typename _Iterator> 2400 void 2401 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2402 _M_assign_unique(_Iterator __first, _Iterator __last) 2403 { 2404 _Reuse_or_alloc_node __roan(*this); 2405 _M_impl._M_reset(); 2406 for (; __first != __last; ++__first) 2407 _M_insert_unique_(end(), *__first, __roan); 2408 } 2409 2410 template<typename _Key, typename _Val, typename _KeyOfValue, 2411 typename _Compare, typename _Alloc> 2412 template<typename _Iterator> 2413 void 2414 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2415 _M_assign_equal(_Iterator __first, _Iterator __last) 2416 { 2417 _Reuse_or_alloc_node __roan(*this); 2418 _M_impl._M_reset(); 2419 for (; __first != __last; ++__first) 2420 _M_insert_equal_(end(), *__first, __roan); 2421 } 2422 #endif 2423 2424 template<typename _Key, typename _Val, typename _KeyOfValue, 2425 typename _Compare, typename _Alloc> 2426 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& 2427 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2428 operator=(const _Rb_tree& __x) 2429 { 2430 if (this != std::__addressof(__x)) 2431 { 2432 // Note that _Key may be a constant type. 2433 #if __cplusplus >= 201103L 2434 if (_Node_alloc_traits::_S_propagate_on_copy_assign()) 2435 { 2436 auto& __this_alloc = this->_M_get_Node_allocator(); 2437 auto& __that_alloc = __x._M_get_Node_allocator(); 2438 if (!_Node_alloc_traits::_S_always_equal() 2439 && __this_alloc != __that_alloc) 2440 { 2441 // Replacement allocator cannot free existing storage, we need 2442 // to erase nodes first. 2443 clear(); 2444 std::__alloc_on_copy(__this_alloc, __that_alloc); 2445 } 2446 } 2447 #endif 2448 2449 _Reuse_or_alloc_node __roan(*this); 2450 _M_impl._M_reset(); 2451 _M_impl._M_key_compare = __x._M_impl._M_key_compare; 2452 if (__x._M_root()) 2453 _M_root() = _M_copy<__as_lvalue>(__x, __roan); 2454 } 2455 2456 return *this; 2457 } 2458 2459 template<typename _Key, typename _Val, typename _KeyOfValue, 2460 typename _Compare, typename _Alloc> 2461 #if __cplusplus >= 201103L 2462 template<typename _Arg, typename _NodeGen> 2463 #else 2464 template<typename _NodeGen> 2465 #endif 2466 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2468 _M_insert_(_Base_ptr __x, _Base_ptr __p, 2469 #if __cplusplus >= 201103L 2470 _Arg&& __v, 2471 #else 2472 const _Val& __v, 2473 #endif 2474 _NodeGen& __node_gen) 2475 { 2476 bool __insert_left = (__x || __p == _M_end() 2477 || _M_impl._M_key_compare(_KeyOfValue()(__v), 2478 _S_key(__p))); 2479 2480 _Base_ptr __z = 2481 __node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr(); 2482 2483 _Node_traits::_S_insert_and_rebalance 2484 (__insert_left, __z, __p, this->_M_impl._M_header); 2485 ++_M_impl._M_node_count; 2486 return iterator(__z); 2487 } 2488 2489 template<typename _Key, typename _Val, typename _KeyOfValue, 2490 typename _Compare, typename _Alloc> 2491 #if __cplusplus >= 201103L 2492 template<typename _Arg> 2493 #endif 2494 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2495 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2496 #if __cplusplus >= 201103L 2497 _M_insert_lower(_Base_ptr __p, _Arg&& __v) 2498 #else 2499 _M_insert_lower(_Base_ptr __p, const _Val& __v) 2500 #endif 2501 { 2502 bool __insert_left = (__p == _M_end() 2503 || !_M_impl._M_key_compare(_S_key(__p), 2504 _KeyOfValue()(__v))); 2505 2506 _Base_ptr __z = 2507 _M_create_node(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr(); 2508 _Node_traits::_S_insert_and_rebalance 2509 (__insert_left, __z, __p, this->_M_impl._M_header); 2510 ++_M_impl._M_node_count; 2511 return iterator(__z); 2512 } 2513 2514 template<typename _Key, typename _Val, typename _KeyOfValue, 2515 typename _Compare, typename _Alloc> 2516 #if __cplusplus >= 201103L 2517 template<typename _Arg> 2518 #endif 2519 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2520 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2521 #if __cplusplus >= 201103L 2522 _M_insert_equal_lower(_Arg&& __v) 2523 #else 2524 _M_insert_equal_lower(const _Val& __v) 2525 #endif 2526 { 2527 _Base_ptr __x = _M_begin(); 2528 _Base_ptr __y = _M_end(); 2529 while (__x) 2530 { 2531 __y = __x; 2532 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? 2533 _S_left(__x) : _S_right(__x); 2534 } 2535 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); 2536 } 2537 2538 template<typename _Key, typename _Val, typename _KoV, 2539 typename _Compare, typename _Alloc> 2540 template<bool _MoveValues, typename _NodeGen> 2541 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Base_ptr 2542 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: 2543 _M_copy(_Node_ptr __x, _Base_ptr __p, _NodeGen& __node_gen) 2544 { 2545 // Structural copy. __x and __p must be non-null. 2546 _Node_ptr __top = _M_clone_node<_MoveValues>(__x, __node_gen); 2547 _Base_ptr __top_base = __top->_M_base_ptr(); 2548 __top->_M_parent = __p; 2549 2550 __try 2551 { 2552 if (__x->_M_right) 2553 __top->_M_right = 2554 _M_copy<_MoveValues>(_S_right(__x), __top_base, __node_gen); 2555 __p = __top_base; 2556 __x = _S_left(__x); 2557 2558 while (__x) 2559 { 2560 _Base_ptr __y = 2561 _M_clone_node<_MoveValues>(__x, __node_gen)->_M_base_ptr(); 2562 __p->_M_left = __y; 2563 __y->_M_parent = __p; 2564 if (__x->_M_right) 2565 __y->_M_right = _M_copy<_MoveValues>(_S_right(__x), 2566 __y, __node_gen); 2567 __p = __y; 2568 __x = _S_left(__x); 2569 } 2570 } 2571 __catch(...) 2572 { 2573 _M_erase(__top); 2574 __throw_exception_again; 2575 } 2576 return __top_base; 2577 } 2578 2579 template<typename _Key, typename _Val, typename _KeyOfValue, 2580 typename _Compare, typename _Alloc> 2581 void 2582 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2583 _M_erase(_Node_ptr __x) 2584 { 2585 // Erase without rebalancing. 2586 while (__x) 2587 { 2588 _M_erase(_S_right(__x)); 2589 _Node_ptr __y = _S_left(__x); 2590 _M_drop_node(__x); 2591 __x = __y; 2592 } 2593 } 2594 2595 template<typename _Key, typename _Val, typename _KeyOfValue, 2596 typename _Compare, typename _Alloc> 2597 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2598 _Compare, _Alloc>::_Base_ptr 2599 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2600 _M_lower_bound(_Base_ptr __x, _Base_ptr __y, 2601 const _Key& __k) const 2602 { 2603 while (__x) 2604 if (!_M_impl._M_key_compare(_S_key(__x), __k)) 2605 __y = __x, __x = _S_left(__x); 2606 else 2607 __x = _S_right(__x); 2608 return __y; 2609 } 2610 2611 template<typename _Key, typename _Val, typename _KeyOfValue, 2612 typename _Compare, typename _Alloc> 2613 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2614 _Compare, _Alloc>::_Base_ptr 2615 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2616 _M_upper_bound(_Base_ptr __x, _Base_ptr __y, 2617 const _Key& __k) const 2618 { 2619 while (__x) 2620 if (_M_impl._M_key_compare(__k, _S_key(__x))) 2621 __y = __x, __x = _S_left(__x); 2622 else 2623 __x = _S_right(__x); 2624 return __y; 2625 } 2626 2627 template<typename _Key, typename _Val, typename _KeyOfValue, 2628 typename _Compare, typename _Alloc> 2629 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2630 _Compare, _Alloc>::iterator, 2631 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2632 _Compare, _Alloc>::iterator> 2633 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2634 equal_range(const _Key& __k) 2635 { 2636 typedef pair<iterator, iterator> _Ret; 2637 2638 _Base_ptr __x = _M_begin(); 2639 _Base_ptr __y = _M_end(); 2640 while (__x) 2641 { 2642 if (_M_impl._M_key_compare(_S_key(__x), __k)) 2643 __x = _S_right(__x); 2644 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 2645 __y = __x, __x = _S_left(__x); 2646 else 2647 { 2648 _Base_ptr __xu(__x); 2649 _Base_ptr __yu(__y); 2650 __y = __x, __x = _S_left(__x); 2651 __xu = _S_right(__xu); 2652 return _Ret(iterator(_M_lower_bound(__x, __y, __k)), 2653 iterator(_M_upper_bound(__xu, __yu, __k))); 2654 } 2655 } 2656 return _Ret(iterator(__y), iterator(__y)); 2657 } 2658 2659 template<typename _Key, typename _Val, typename _KeyOfValue, 2660 typename _Compare, typename _Alloc> 2661 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2662 _Compare, _Alloc>::const_iterator, 2663 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2664 _Compare, _Alloc>::const_iterator> 2665 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2666 equal_range(const _Key& __k) const 2667 { 2668 typedef pair<const_iterator, const_iterator> _Ret; 2669 2670 _Base_ptr __x = _M_begin(); 2671 _Base_ptr __y = _M_end(); 2672 while (__x) 2673 { 2674 if (_M_impl._M_key_compare(_S_key(__x), __k)) 2675 __x = _S_right(__x); 2676 else if (_M_impl._M_key_compare(__k, _S_key(__x))) 2677 __y = __x, __x = _S_left(__x); 2678 else 2679 { 2680 _Base_ptr __xu(__x); 2681 _Base_ptr __yu(__y); 2682 __y = __x, __x = _S_left(__x); 2683 __xu = _S_right(__xu); 2684 return _Ret(const_iterator(_M_lower_bound(__x, __y, __k)), 2685 const_iterator(_M_upper_bound(__xu, __yu, __k))); 2686 } 2687 } 2688 return _Ret(const_iterator(__y), const_iterator(__y)); 2689 } 2690 2691 template<typename _Key, typename _Val, typename _KeyOfValue, 2692 typename _Compare, typename _Alloc> 2693 void 2694 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2695 swap(_Rb_tree& __t) 2696 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) 2697 { 2698 if (!_M_root()) 2699 { 2700 if (__t._M_root()) 2701 _M_impl._M_move_data(__t._M_impl); 2702 } 2703 else if (!__t._M_root()) 2704 __t._M_impl._M_move_data(_M_impl); 2705 else 2706 { 2707 std::swap(_M_root(),__t._M_root()); 2708 std::swap(_M_leftmost(),__t._M_leftmost()); 2709 std::swap(_M_rightmost(),__t._M_rightmost()); 2710 2711 _M_root()->_M_parent = _M_end(); 2712 __t._M_root()->_M_parent = __t._M_end(); 2713 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); 2714 } 2715 // No need to swap header's color as it does not change. 2716 2717 using std::swap; 2718 swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); 2719 2720 _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(), 2721 __t._M_get_Node_allocator()); 2722 } 2723 2724 template<typename _Key, typename _Val, typename _KeyOfValue, 2725 typename _Compare, typename _Alloc> 2726 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2727 _Compare, _Alloc>::_Base_ptr, 2728 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2729 _Compare, _Alloc>::_Base_ptr> 2730 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2731 _M_get_insert_unique_pos(const key_type& __k) 2732 { 2733 typedef pair<_Base_ptr, _Base_ptr> _Res; 2734 _Base_ptr __x = _M_begin(); 2735 _Base_ptr __y = _M_end(); 2736 bool __comp = true; 2737 while (__x) 2738 { 2739 __y = __x; 2740 __comp = _M_impl._M_key_compare(__k, _S_key(__x)); 2741 __x = __comp ? _S_left(__x) : _S_right(__x); 2742 } 2743 iterator __j = iterator(__y); 2744 if (__comp) 2745 { 2746 if (__j == begin()) 2747 return _Res(__x, __y); 2748 else 2749 --__j; 2750 } 2751 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) 2752 return _Res(__x, __y); 2753 return _Res(__j._M_node, _Base_ptr()); 2754 } 2755 2756 template<typename _Key, typename _Val, typename _KeyOfValue, 2757 typename _Compare, typename _Alloc> 2758 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2759 _Compare, _Alloc>::_Base_ptr, 2760 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2761 _Compare, _Alloc>::_Base_ptr> 2762 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2763 _M_get_insert_equal_pos(const key_type& __k) 2764 { 2765 typedef pair<_Base_ptr, _Base_ptr> _Res; 2766 _Base_ptr __x = _M_begin(); 2767 _Base_ptr __y = _M_end(); 2768 while (__x) 2769 { 2770 __y = __x; 2771 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? 2772 _S_left(__x) : _S_right(__x); 2773 } 2774 return _Res(__x, __y); 2775 } 2776 2777 template<typename _Key, typename _Val, typename _KeyOfValue, 2778 typename _Compare, typename _Alloc> 2779 #if __cplusplus >= 201103L 2780 template<typename _Arg> 2781 #endif 2782 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2783 _Compare, _Alloc>::iterator, bool> 2784 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2785 #if __cplusplus >= 201103L 2786 _M_insert_unique(_Arg&& __v) 2787 #else 2788 _M_insert_unique(const _Val& __v) 2789 #endif 2790 { 2791 typedef pair<iterator, bool> _Res; 2792 pair<_Base_ptr, _Base_ptr> __res 2793 = _M_get_insert_unique_pos(_KeyOfValue()(__v)); 2794 2795 if (__res.second) 2796 { 2797 _Alloc_node __an(*this); 2798 return _Res(_M_insert_(__res.first, __res.second, 2799 _GLIBCXX_FORWARD(_Arg, __v), __an), 2800 true); 2801 } 2802 2803 return _Res(iterator(__res.first), false); 2804 } 2805 2806 template<typename _Key, typename _Val, typename _KeyOfValue, 2807 typename _Compare, typename _Alloc> 2808 #if __cplusplus >= 201103L 2809 template<typename _Arg> 2810 #endif 2811 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2812 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2813 #if __cplusplus >= 201103L 2814 _M_insert_equal(_Arg&& __v) 2815 #else 2816 _M_insert_equal(const _Val& __v) 2817 #endif 2818 { 2819 pair<_Base_ptr, _Base_ptr> __res 2820 = _M_get_insert_equal_pos(_KeyOfValue()(__v)); 2821 _Alloc_node __an(*this); 2822 return _M_insert_(__res.first, __res.second, 2823 _GLIBCXX_FORWARD(_Arg, __v), __an); 2824 } 2825 2826 template<typename _Key, typename _Val, typename _KeyOfValue, 2827 typename _Compare, typename _Alloc> 2828 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2829 _Compare, _Alloc>::_Base_ptr, 2830 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2831 _Compare, _Alloc>::_Base_ptr> 2832 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2833 _M_get_insert_hint_unique_pos(const_iterator __position, 2834 const key_type& __k) 2835 { 2836 typedef pair<_Base_ptr, _Base_ptr> _Res; 2837 2838 // end() 2839 if (__position._M_node == _M_end()) 2840 { 2841 if (size() > 0 2842 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) 2843 return _Res(_Base_ptr(), _M_rightmost()); 2844 else 2845 return _M_get_insert_unique_pos(__k); 2846 } 2847 else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node))) 2848 { 2849 // First, try before... 2850 iterator __before(__position._M_node); 2851 if (__position._M_node == _M_leftmost()) // begin() 2852 return _Res(_M_leftmost(), _M_leftmost()); 2853 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) 2854 { 2855 if (!_S_right(__before._M_node)) 2856 return _Res(_Base_ptr(), __before._M_node); 2857 else 2858 return _Res(__position._M_node, __position._M_node); 2859 } 2860 else 2861 return _M_get_insert_unique_pos(__k); 2862 } 2863 else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k)) 2864 { 2865 // ... then try after. 2866 iterator __after(__position._M_node); 2867 if (__position._M_node == _M_rightmost()) 2868 return _Res(_Base_ptr(), _M_rightmost()); 2869 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) 2870 { 2871 if (!_S_right(__position._M_node)) 2872 return _Res(_Base_ptr(), __position._M_node); 2873 else 2874 return _Res(__after._M_node, __after._M_node); 2875 } 2876 else 2877 return _M_get_insert_unique_pos(__k); 2878 } 2879 else 2880 // Equivalent keys. 2881 return _Res(__position._M_node, _Base_ptr()); 2882 } 2883 2884 template<typename _Key, typename _Val, typename _KeyOfValue, 2885 typename _Compare, typename _Alloc> 2886 #if __cplusplus >= 201103L 2887 template<typename _Arg, typename _NodeGen> 2888 #else 2889 template<typename _NodeGen> 2890 #endif 2891 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2892 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2893 _M_insert_unique_(const_iterator __position, 2894 #if __cplusplus >= 201103L 2895 _Arg&& __v, 2896 #else 2897 const _Val& __v, 2898 #endif 2899 _NodeGen& __node_gen) 2900 { 2901 pair<_Base_ptr, _Base_ptr> __res 2902 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); 2903 2904 if (__res.second) 2905 return _M_insert_(__res.first, __res.second, 2906 _GLIBCXX_FORWARD(_Arg, __v), 2907 __node_gen); 2908 return iterator(__res.first); 2909 } 2910 2911 template<typename _Key, typename _Val, typename _KeyOfValue, 2912 typename _Compare, typename _Alloc> 2913 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, 2914 _Compare, _Alloc>::_Base_ptr, 2915 typename _Rb_tree<_Key, _Val, _KeyOfValue, 2916 _Compare, _Alloc>::_Base_ptr> 2917 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2918 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) 2919 { 2920 typedef pair<_Base_ptr, _Base_ptr> _Res; 2921 2922 // end() 2923 if (__position._M_node == _M_end()) 2924 { 2925 if (size() > 0 2926 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) 2927 return _Res(_Base_ptr(), _M_rightmost()); 2928 else 2929 return _M_get_insert_equal_pos(__k); 2930 } 2931 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k)) 2932 { 2933 // First, try before... 2934 iterator __before(__position._M_node); 2935 if (__position._M_node == _M_leftmost()) // begin() 2936 return _Res(_M_leftmost(), _M_leftmost()); 2937 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) 2938 { 2939 if (!_S_right(__before._M_node)) 2940 return _Res(_Base_ptr(), __before._M_node); 2941 else 2942 return _Res(__position._M_node, __position._M_node); 2943 } 2944 else 2945 return _M_get_insert_equal_pos(__k); 2946 } 2947 else 2948 { 2949 // ... then try after. 2950 iterator __after(__position._M_node); 2951 if (__position._M_node == _M_rightmost()) 2952 return _Res(_Base_ptr(), _M_rightmost()); 2953 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) 2954 { 2955 if (!_S_right(__position._M_node)) 2956 return _Res(_Base_ptr(), __position._M_node); 2957 else 2958 return _Res(__after._M_node, __after._M_node); 2959 } 2960 else 2961 return _Res(_Base_ptr(), _Base_ptr()); 2962 } 2963 } 2964 2965 template<typename _Key, typename _Val, typename _KeyOfValue, 2966 typename _Compare, typename _Alloc> 2967 #if __cplusplus >= 201103L 2968 template<typename _Arg, typename _NodeGen> 2969 #else 2970 template<typename _NodeGen> 2971 #endif 2972 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator 2973 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2974 _M_insert_equal_(const_iterator __position, 2975 #if __cplusplus >= 201103L 2976 _Arg&& __v, 2977 #else 2978 const _Val& __v, 2979 #endif 2980 _NodeGen& __node_gen) 2981 { 2982 pair<_Base_ptr, _Base_ptr> __res 2983 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); 2984 2985 if (__res.second) 2986 return _M_insert_(__res.first, __res.second, 2987 _GLIBCXX_FORWARD(_Arg, __v), 2988 __node_gen); 2989 2990 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); 2991 } 2992 2993 #if __cplusplus >= 201103L 2994 template<typename _Key, typename _Val, typename _KeyOfValue, 2995 typename _Compare, typename _Alloc> 2996 auto 2997 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 2998 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Node_ptr __z) 2999 -> iterator 3000 { 3001 bool __insert_left = (__x || __p == _M_end() 3002 || _M_impl._M_key_compare(_S_key(__z), 3003 _S_key(__p))); 3004 3005 _Base_ptr __base_z = __z->_M_base_ptr(); 3006 _Node_traits::_S_insert_and_rebalance 3007 (__insert_left, __base_z, __p, this->_M_impl._M_header); 3008 ++_M_impl._M_node_count; 3009 return iterator(__base_z); 3010 } 3011 3012 template<typename _Key, typename _Val, typename _KeyOfValue, 3013 typename _Compare, typename _Alloc> 3014 auto 3015 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3016 _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z) 3017 -> iterator 3018 { 3019 bool __insert_left = (__p == _M_end() 3020 || !_M_impl._M_key_compare(_S_key(__p), 3021 _S_key(__z))); 3022 3023 _Base_ptr __base_z = __z->_M_base_ptr(); 3024 _Node_traits::_S_insert_and_rebalance 3025 (__insert_left, __base_z, __p, this->_M_impl._M_header); 3026 ++_M_impl._M_node_count; 3027 return iterator(__base_z); 3028 } 3029 3030 template<typename _Key, typename _Val, typename _KeyOfValue, 3031 typename _Compare, typename _Alloc> 3032 auto 3033 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3034 _M_insert_equal_lower_node(_Node_ptr __z) 3035 -> iterator 3036 { 3037 _Base_ptr __x = _M_begin(); 3038 _Base_ptr __y = _M_end(); 3039 while (__x) 3040 { 3041 __y = __x; 3042 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? 3043 _S_left(__x) : _S_right(__x); 3044 } 3045 return _M_insert_lower_node(__y, __z); 3046 } 3047 3048 template<typename _Key, typename _Val, typename _KeyOfValue, 3049 typename _Compare, typename _Alloc> 3050 template<typename... _Args> 3051 auto 3052 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3053 _M_emplace_unique(_Args&&... __args) 3054 -> pair<iterator, bool> 3055 { 3056 _Auto_node __z(*this, std::forward<_Args>(__args)...); 3057 auto __res = _M_get_insert_unique_pos(__z._M_key()); 3058 if (__res.second) 3059 return {__z._M_insert(__res), true}; 3060 return {iterator(__res.first), false}; 3061 } 3062 3063 template<typename _Key, typename _Val, typename _KeyOfValue, 3064 typename _Compare, typename _Alloc> 3065 template<typename... _Args> 3066 auto 3067 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3068 _M_emplace_equal(_Args&&... __args) 3069 -> iterator 3070 { 3071 _Auto_node __z(*this, std::forward<_Args>(__args)...); 3072 auto __res = _M_get_insert_equal_pos(__z._M_key()); 3073 return __z._M_insert(__res); 3074 } 3075 3076 template<typename _Key, typename _Val, typename _KeyOfValue, 3077 typename _Compare, typename _Alloc> 3078 template<typename... _Args> 3079 auto 3080 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3081 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) 3082 -> iterator 3083 { 3084 _Auto_node __z(*this, std::forward<_Args>(__args)...); 3085 auto __res = _M_get_insert_hint_unique_pos(__pos, __z._M_key()); 3086 if (__res.second) 3087 return __z._M_insert(__res); 3088 return iterator(__res.first); 3089 } 3090 3091 template<typename _Key, typename _Val, typename _KeyOfValue, 3092 typename _Compare, typename _Alloc> 3093 template<typename... _Args> 3094 auto 3095 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3096 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) 3097 -> iterator 3098 { 3099 _Auto_node __z(*this, std::forward<_Args>(__args)...); 3100 auto __res = _M_get_insert_hint_equal_pos(__pos, __z._M_key()); 3101 if (__res.second) 3102 return __z._M_insert(__res); 3103 return __z._M_insert_equal_lower(); 3104 } 3105 #endif 3106 3107 3108 template<typename _Key, typename _Val, typename _KeyOfValue, 3109 typename _Compare, typename _Alloc> 3110 void 3111 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3112 _M_erase_aux(const_iterator __position) 3113 { 3114 _Base_ptr __y = _Node_traits::_S_rebalance_for_erase 3115 (__position._M_node, this->_M_impl._M_header); 3116 _M_drop_node(static_cast<_Node&>(*__y)._M_node_ptr()); 3117 --_M_impl._M_node_count; 3118 } 3119 3120 template<typename _Key, typename _Val, typename _KeyOfValue, 3121 typename _Compare, typename _Alloc> 3122 void 3123 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3124 _M_erase_aux(const_iterator __first, const_iterator __last) 3125 { 3126 if (__first == begin() && __last == end()) 3127 clear(); 3128 else 3129 while (__first != __last) 3130 _M_erase_aux(__first++); 3131 } 3132 3133 template<typename _Key, typename _Val, typename _KeyOfValue, 3134 typename _Compare, typename _Alloc> 3135 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 3136 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3137 erase(const _Key& __x) 3138 { 3139 pair<iterator, iterator> __p = equal_range(__x); 3140 const size_type __old_size = size(); 3141 _M_erase_aux(__p.first, __p.second); 3142 return __old_size - size(); 3143 } 3144 3145 template<typename _Key, typename _Val, typename _KeyOfValue, 3146 typename _Compare, typename _Alloc> 3147 typename _Rb_tree<_Key, _Val, _KeyOfValue, 3148 _Compare, _Alloc>::iterator 3149 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3150 find(const _Key& __k) 3151 { 3152 iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k)); 3153 return (__j == end() 3154 || _M_impl._M_key_compare(__k, 3155 _S_key(__j._M_node))) ? end() : __j; 3156 } 3157 3158 template<typename _Key, typename _Val, typename _KeyOfValue, 3159 typename _Compare, typename _Alloc> 3160 typename _Rb_tree<_Key, _Val, _KeyOfValue, 3161 _Compare, _Alloc>::const_iterator 3162 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3163 find(const _Key& __k) const 3164 { 3165 const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k)); 3166 return (__j == end() 3167 || _M_impl._M_key_compare(__k, 3168 _S_key(__j._M_node))) ? end() : __j; 3169 } 3170 3171 template<typename _Key, typename _Val, typename _KeyOfValue, 3172 typename _Compare, typename _Alloc> 3173 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type 3174 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: 3175 count(const _Key& __k) const 3176 { 3177 pair<const_iterator, const_iterator> __p = equal_range(__k); 3178 const size_type __n = std::distance(__p.first, __p.second); 3179 return __n; 3180 } 3181 3182 _GLIBCXX_PURE unsigned int 3183 _Rb_tree_black_count(const _Rb_tree_node_base* __node, 3184 const _Rb_tree_node_base* __root) throw (); 3185 3186 template<typename _Key, typename _Val, typename _KeyOfValue, 3187 typename _Compare, typename _Alloc> 3188 bool 3189 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const 3190 { 3191 if (_M_impl._M_node_count == 0 || begin() == end()) 3192 return _M_impl._M_node_count == 0 && begin() == end() 3193 && this->_M_impl._M_header._M_left == _M_end() 3194 && this->_M_impl._M_header._M_right == _M_end(); 3195 3196 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); 3197 for (const_iterator __it = begin(); __it != end(); ++__it) 3198 { 3199 _Base_ptr __x = __it._M_node; 3200 _Base_ptr __L = _S_left(__x); 3201 _Base_ptr __R = _S_right(__x); 3202 3203 if (__x->_M_color == _S_red) 3204 if ((__L && __L->_M_color == _S_red) 3205 || (__R && __R->_M_color == _S_red)) 3206 return false; 3207 3208 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) 3209 return false; 3210 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) 3211 return false; 3212 3213 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) 3214 return false; 3215 } 3216 3217 if (_M_leftmost() != _Node_base::_S_minimum(_M_root())) 3218 return false; 3219 if (_M_rightmost() != _Node_base::_S_maximum(_M_root())) 3220 return false; 3221 return true; 3222 } 3223 3224 #ifdef __glibcxx_node_extract // >= C++17 3225 // Allow access to internals of compatible _Rb_tree specializations. 3226 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1, 3227 typename _Alloc, typename _Cmp2> 3228 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>, 3229 _Cmp2> 3230 { 3231 private: 3232 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>; 3233 3234 static auto& 3235 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree) 3236 { return __tree._M_impl; } 3237 }; 3238 #endif // C++17 3239 3240 _GLIBCXX_END_NAMESPACE_VERSION 3241 } // namespace 3242 3243 #endif
