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