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