1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___TREE 11#define _LIBCPP___TREE 12 13#include <__config> 14#include <iterator> 15#include <memory> 16#include <stdexcept> 17#include <algorithm> 18 19#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 20#pragma GCC system_header 21#endif 22 23_LIBCPP_PUSH_MACROS 24#include <__undef_macros> 25 26 27_LIBCPP_BEGIN_NAMESPACE_STD 28 29#if defined(__GNUC__) && !defined(__clang__) // gcc.gnu.org/PR37804 30template <class, class, class, class> class _LIBCPP_TEMPLATE_VIS map; 31template <class, class, class, class> class _LIBCPP_TEMPLATE_VIS multimap; 32template <class, class, class> class _LIBCPP_TEMPLATE_VIS set; 33template <class, class, class> class _LIBCPP_TEMPLATE_VIS multiset; 34#endif 35 36template <class _Tp, class _Compare, class _Allocator> class __tree; 37template <class _Tp, class _NodePtr, class _DiffType> 38 class _LIBCPP_TEMPLATE_VIS __tree_iterator; 39template <class _Tp, class _ConstNodePtr, class _DiffType> 40 class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 41 42template <class _Pointer> class __tree_end_node; 43template <class _VoidPtr> class __tree_node_base; 44template <class _Tp, class _VoidPtr> class __tree_node; 45 46template <class _Key, class _Value> 47struct __value_type; 48 49template <class _Allocator> class __map_node_destructor; 50template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator; 51template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 52 53/* 54 55_NodePtr algorithms 56 57The algorithms taking _NodePtr are red black tree algorithms. Those 58algorithms taking a parameter named __root should assume that __root 59points to a proper red black tree (unless otherwise specified). 60 61Each algorithm herein assumes that __root->__parent_ points to a non-null 62structure which has a member __left_ which points back to __root. No other 63member is read or written to at __root->__parent_. 64 65__root->__parent_ will be referred to below (in comments only) as end_node. 66end_node->__left_ is an externably accessible lvalue for __root, and can be 67changed by node insertion and removal (without explicit reference to end_node). 68 69All nodes (with the exception of end_node), even the node referred to as 70__root, have a non-null __parent_ field. 71 72*/ 73 74// Returns: true if __x is a left child of its parent, else false 75// Precondition: __x != nullptr. 76template <class _NodePtr> 77inline _LIBCPP_INLINE_VISIBILITY 78bool 79__tree_is_left_child(_NodePtr __x) _NOEXCEPT 80{ 81 return __x == __x->__parent_->__left_; 82} 83 84// Determines if the subtree rooted at __x is a proper red black subtree. If 85// __x is a proper subtree, returns the black height (null counts as 1). If 86// __x is an improper subtree, returns 0. 87template <class _NodePtr> 88unsigned 89__tree_sub_invariant(_NodePtr __x) 90{ 91 if (__x == nullptr) 92 return 1; 93 // parent consistency checked by caller 94 // check __x->__left_ consistency 95 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x) 96 return 0; 97 // check __x->__right_ consistency 98 if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x) 99 return 0; 100 // check __x->__left_ != __x->__right_ unless both are nullptr 101 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) 102 return 0; 103 // If this is red, neither child can be red 104 if (!__x->__is_black_) 105 { 106 if (__x->__left_ && !__x->__left_->__is_black_) 107 return 0; 108 if (__x->__right_ && !__x->__right_->__is_black_) 109 return 0; 110 } 111 unsigned __h = _VSTD::__tree_sub_invariant(__x->__left_); 112 if (__h == 0) 113 return 0; // invalid left subtree 114 if (__h != _VSTD::__tree_sub_invariant(__x->__right_)) 115 return 0; // invalid or different height right subtree 116 return __h + __x->__is_black_; // return black height of this node 117} 118 119// Determines if the red black tree rooted at __root is a proper red black tree. 120// __root == nullptr is a proper tree. Returns true is __root is a proper 121// red black tree, else returns false. 122template <class _NodePtr> 123bool 124__tree_invariant(_NodePtr __root) 125{ 126 if (__root == nullptr) 127 return true; 128 // check __x->__parent_ consistency 129 if (__root->__parent_ == nullptr) 130 return false; 131 if (!_VSTD::__tree_is_left_child(__root)) 132 return false; 133 // root must be black 134 if (!__root->__is_black_) 135 return false; 136 // do normal node checks 137 return _VSTD::__tree_sub_invariant(__root) != 0; 138} 139 140// Returns: pointer to the left-most node under __x. 141// Precondition: __x != nullptr. 142template <class _NodePtr> 143inline _LIBCPP_INLINE_VISIBILITY 144_NodePtr 145__tree_min(_NodePtr __x) _NOEXCEPT 146{ 147 while (__x->__left_ != nullptr) 148 __x = __x->__left_; 149 return __x; 150} 151 152// Returns: pointer to the right-most node under __x. 153// Precondition: __x != nullptr. 154template <class _NodePtr> 155inline _LIBCPP_INLINE_VISIBILITY 156_NodePtr 157__tree_max(_NodePtr __x) _NOEXCEPT 158{ 159 while (__x->__right_ != nullptr) 160 __x = __x->__right_; 161 return __x; 162} 163 164// Returns: pointer to the next in-order node after __x. 165// Precondition: __x != nullptr. 166template <class _NodePtr> 167_NodePtr 168__tree_next(_NodePtr __x) _NOEXCEPT 169{ 170 if (__x->__right_ != nullptr) 171 return _VSTD::__tree_min(__x->__right_); 172 while (!_VSTD::__tree_is_left_child(__x)) 173 __x = __x->__parent_unsafe(); 174 return __x->__parent_unsafe(); 175} 176 177template <class _EndNodePtr, class _NodePtr> 178inline _LIBCPP_INLINE_VISIBILITY 179_EndNodePtr 180__tree_next_iter(_NodePtr __x) _NOEXCEPT 181{ 182 if (__x->__right_ != nullptr) 183 return static_cast<_EndNodePtr>(_VSTD::__tree_min(__x->__right_)); 184 while (!_VSTD::__tree_is_left_child(__x)) 185 __x = __x->__parent_unsafe(); 186 return static_cast<_EndNodePtr>(__x->__parent_); 187} 188 189// Returns: pointer to the previous in-order node before __x. 190// Precondition: __x != nullptr. 191// Note: __x may be the end node. 192template <class _NodePtr, class _EndNodePtr> 193inline _LIBCPP_INLINE_VISIBILITY 194_NodePtr 195__tree_prev_iter(_EndNodePtr __x) _NOEXCEPT 196{ 197 if (__x->__left_ != nullptr) 198 return _VSTD::__tree_max(__x->__left_); 199 _NodePtr __xx = static_cast<_NodePtr>(__x); 200 while (_VSTD::__tree_is_left_child(__xx)) 201 __xx = __xx->__parent_unsafe(); 202 return __xx->__parent_unsafe(); 203} 204 205// Returns: pointer to a node which has no children 206// Precondition: __x != nullptr. 207template <class _NodePtr> 208_NodePtr 209__tree_leaf(_NodePtr __x) _NOEXCEPT 210{ 211 while (true) 212 { 213 if (__x->__left_ != nullptr) 214 { 215 __x = __x->__left_; 216 continue; 217 } 218 if (__x->__right_ != nullptr) 219 { 220 __x = __x->__right_; 221 continue; 222 } 223 break; 224 } 225 return __x; 226} 227 228// Effects: Makes __x->__right_ the subtree root with __x as its left child 229// while preserving in-order order. 230// Precondition: __x->__right_ != nullptr 231template <class _NodePtr> 232void 233__tree_left_rotate(_NodePtr __x) _NOEXCEPT 234{ 235 _NodePtr __y = __x->__right_; 236 __x->__right_ = __y->__left_; 237 if (__x->__right_ != nullptr) 238 __x->__right_->__set_parent(__x); 239 __y->__parent_ = __x->__parent_; 240 if (_VSTD::__tree_is_left_child(__x)) 241 __x->__parent_->__left_ = __y; 242 else 243 __x->__parent_unsafe()->__right_ = __y; 244 __y->__left_ = __x; 245 __x->__set_parent(__y); 246} 247 248// Effects: Makes __x->__left_ the subtree root with __x as its right child 249// while preserving in-order order. 250// Precondition: __x->__left_ != nullptr 251template <class _NodePtr> 252void 253__tree_right_rotate(_NodePtr __x) _NOEXCEPT 254{ 255 _NodePtr __y = __x->__left_; 256 __x->__left_ = __y->__right_; 257 if (__x->__left_ != nullptr) 258 __x->__left_->__set_parent(__x); 259 __y->__parent_ = __x->__parent_; 260 if (_VSTD::__tree_is_left_child(__x)) 261 __x->__parent_->__left_ = __y; 262 else 263 __x->__parent_unsafe()->__right_ = __y; 264 __y->__right_ = __x; 265 __x->__set_parent(__y); 266} 267 268// Effects: Rebalances __root after attaching __x to a leaf. 269// Precondition: __root != nulptr && __x != nullptr. 270// __x has no children. 271// __x == __root or == a direct or indirect child of __root. 272// If __x were to be unlinked from __root (setting __root to 273// nullptr if __root == __x), __tree_invariant(__root) == true. 274// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_ 275// may be different than the value passed in as __root. 276template <class _NodePtr> 277void 278__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT 279{ 280 __x->__is_black_ = __x == __root; 281 while (__x != __root && !__x->__parent_unsafe()->__is_black_) 282 { 283 // __x->__parent_ != __root because __x->__parent_->__is_black == false 284 if (_VSTD::__tree_is_left_child(__x->__parent_unsafe())) 285 { 286 _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_; 287 if (__y != nullptr && !__y->__is_black_) 288 { 289 __x = __x->__parent_unsafe(); 290 __x->__is_black_ = true; 291 __x = __x->__parent_unsafe(); 292 __x->__is_black_ = __x == __root; 293 __y->__is_black_ = true; 294 } 295 else 296 { 297 if (!_VSTD::__tree_is_left_child(__x)) 298 { 299 __x = __x->__parent_unsafe(); 300 _VSTD::__tree_left_rotate(__x); 301 } 302 __x = __x->__parent_unsafe(); 303 __x->__is_black_ = true; 304 __x = __x->__parent_unsafe(); 305 __x->__is_black_ = false; 306 _VSTD::__tree_right_rotate(__x); 307 break; 308 } 309 } 310 else 311 { 312 _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_; 313 if (__y != nullptr && !__y->__is_black_) 314 { 315 __x = __x->__parent_unsafe(); 316 __x->__is_black_ = true; 317 __x = __x->__parent_unsafe(); 318 __x->__is_black_ = __x == __root; 319 __y->__is_black_ = true; 320 } 321 else 322 { 323 if (_VSTD::__tree_is_left_child(__x)) 324 { 325 __x = __x->__parent_unsafe(); 326 _VSTD::__tree_right_rotate(__x); 327 } 328 __x = __x->__parent_unsafe(); 329 __x->__is_black_ = true; 330 __x = __x->__parent_unsafe(); 331 __x->__is_black_ = false; 332 _VSTD::__tree_left_rotate(__x); 333 break; 334 } 335 } 336 } 337} 338 339// Precondition: __root != nullptr && __z != nullptr. 340// __tree_invariant(__root) == true. 341// __z == __root or == a direct or indirect child of __root. 342// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed. 343// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_ 344// nor any of its children refer to __z. end_node->__left_ 345// may be different than the value passed in as __root. 346template <class _NodePtr> 347void 348__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT 349{ 350 // __z will be removed from the tree. Client still needs to destruct/deallocate it 351 // __y is either __z, or if __z has two children, __tree_next(__z). 352 // __y will have at most one child. 353 // __y will be the initial hole in the tree (make the hole at a leaf) 354 _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? 355 __z : _VSTD::__tree_next(__z); 356 // __x is __y's possibly null single child 357 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; 358 // __w is __x's possibly null uncle (will become __x's sibling) 359 _NodePtr __w = nullptr; 360 // link __x to __y's parent, and find __w 361 if (__x != nullptr) 362 __x->__parent_ = __y->__parent_; 363 if (_VSTD::__tree_is_left_child(__y)) 364 { 365 __y->__parent_->__left_ = __x; 366 if (__y != __root) 367 __w = __y->__parent_unsafe()->__right_; 368 else 369 __root = __x; // __w == nullptr 370 } 371 else 372 { 373 __y->__parent_unsafe()->__right_ = __x; 374 // __y can't be root if it is a right child 375 __w = __y->__parent_->__left_; 376 } 377 bool __removed_black = __y->__is_black_; 378 // If we didn't remove __z, do so now by splicing in __y for __z, 379 // but copy __z's color. This does not impact __x or __w. 380 if (__y != __z) 381 { 382 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr 383 __y->__parent_ = __z->__parent_; 384 if (_VSTD::__tree_is_left_child(__z)) 385 __y->__parent_->__left_ = __y; 386 else 387 __y->__parent_unsafe()->__right_ = __y; 388 __y->__left_ = __z->__left_; 389 __y->__left_->__set_parent(__y); 390 __y->__right_ = __z->__right_; 391 if (__y->__right_ != nullptr) 392 __y->__right_->__set_parent(__y); 393 __y->__is_black_ = __z->__is_black_; 394 if (__root == __z) 395 __root = __y; 396 } 397 // There is no need to rebalance if we removed a red, or if we removed 398 // the last node. 399 if (__removed_black && __root != nullptr) 400 { 401 // Rebalance: 402 // __x has an implicit black color (transferred from the removed __y) 403 // associated with it, no matter what its color is. 404 // If __x is __root (in which case it can't be null), it is supposed 405 // to be black anyway, and if it is doubly black, then the double 406 // can just be ignored. 407 // If __x is red (in which case it can't be null), then it can absorb 408 // the implicit black just by setting its color to black. 409 // Since __y was black and only had one child (which __x points to), __x 410 // is either red with no children, else null, otherwise __y would have 411 // different black heights under left and right pointers. 412 // if (__x == __root || __x != nullptr && !__x->__is_black_) 413 if (__x != nullptr) 414 __x->__is_black_ = true; 415 else 416 { 417 // Else __x isn't root, and is "doubly black", even though it may 418 // be null. __w can not be null here, else the parent would 419 // see a black height >= 2 on the __x side and a black height 420 // of 1 on the __w side (__w must be a non-null black or a red 421 // with a non-null black child). 422 while (true) 423 { 424 if (!_VSTD::__tree_is_left_child(__w)) // if x is left child 425 { 426 if (!__w->__is_black_) 427 { 428 __w->__is_black_ = true; 429 __w->__parent_unsafe()->__is_black_ = false; 430 _VSTD::__tree_left_rotate(__w->__parent_unsafe()); 431 // __x is still valid 432 // reset __root only if necessary 433 if (__root == __w->__left_) 434 __root = __w; 435 // reset sibling, and it still can't be null 436 __w = __w->__left_->__right_; 437 } 438 // __w->__is_black_ is now true, __w may have null children 439 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 440 (__w->__right_ == nullptr || __w->__right_->__is_black_)) 441 { 442 __w->__is_black_ = false; 443 __x = __w->__parent_unsafe(); 444 // __x can no longer be null 445 if (__x == __root || !__x->__is_black_) 446 { 447 __x->__is_black_ = true; 448 break; 449 } 450 // reset sibling, and it still can't be null 451 __w = _VSTD::__tree_is_left_child(__x) ? 452 __x->__parent_unsafe()->__right_ : 453 __x->__parent_->__left_; 454 // continue; 455 } 456 else // __w has a red child 457 { 458 if (__w->__right_ == nullptr || __w->__right_->__is_black_) 459 { 460 // __w left child is non-null and red 461 __w->__left_->__is_black_ = true; 462 __w->__is_black_ = false; 463 _VSTD::__tree_right_rotate(__w); 464 // __w is known not to be root, so root hasn't changed 465 // reset sibling, and it still can't be null 466 __w = __w->__parent_unsafe(); 467 } 468 // __w has a right red child, left child may be null 469 __w->__is_black_ = __w->__parent_unsafe()->__is_black_; 470 __w->__parent_unsafe()->__is_black_ = true; 471 __w->__right_->__is_black_ = true; 472 _VSTD::__tree_left_rotate(__w->__parent_unsafe()); 473 break; 474 } 475 } 476 else 477 { 478 if (!__w->__is_black_) 479 { 480 __w->__is_black_ = true; 481 __w->__parent_unsafe()->__is_black_ = false; 482 _VSTD::__tree_right_rotate(__w->__parent_unsafe()); 483 // __x is still valid 484 // reset __root only if necessary 485 if (__root == __w->__right_) 486 __root = __w; 487 // reset sibling, and it still can't be null 488 __w = __w->__right_->__left_; 489 } 490 // __w->__is_black_ is now true, __w may have null children 491 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 492 (__w->__right_ == nullptr || __w->__right_->__is_black_)) 493 { 494 __w->__is_black_ = false; 495 __x = __w->__parent_unsafe(); 496 // __x can no longer be null 497 if (!__x->__is_black_ || __x == __root) 498 { 499 __x->__is_black_ = true; 500 break; 501 } 502 // reset sibling, and it still can't be null 503 __w = _VSTD::__tree_is_left_child(__x) ? 504 __x->__parent_unsafe()->__right_ : 505 __x->__parent_->__left_; 506 // continue; 507 } 508 else // __w has a red child 509 { 510 if (__w->__left_ == nullptr || __w->__left_->__is_black_) 511 { 512 // __w right child is non-null and red 513 __w->__right_->__is_black_ = true; 514 __w->__is_black_ = false; 515 _VSTD::__tree_left_rotate(__w); 516 // __w is known not to be root, so root hasn't changed 517 // reset sibling, and it still can't be null 518 __w = __w->__parent_unsafe(); 519 } 520 // __w has a left red child, right child may be null 521 __w->__is_black_ = __w->__parent_unsafe()->__is_black_; 522 __w->__parent_unsafe()->__is_black_ = true; 523 __w->__left_->__is_black_ = true; 524 _VSTD::__tree_right_rotate(__w->__parent_unsafe()); 525 break; 526 } 527 } 528 } 529 } 530 } 531} 532 533// node traits 534 535 536template <class _Tp> 537struct __is_tree_value_type_imp : false_type {}; 538 539template <class _Key, class _Value> 540struct __is_tree_value_type_imp<__value_type<_Key, _Value> > : true_type {}; 541 542template <class ..._Args> 543struct __is_tree_value_type : false_type {}; 544 545template <class _One> 546struct __is_tree_value_type<_One> : __is_tree_value_type_imp<typename __uncvref<_One>::type> {}; 547 548template <class _Tp> 549struct __tree_key_value_types { 550 typedef _Tp key_type; 551 typedef _Tp __node_value_type; 552 typedef _Tp __container_value_type; 553 static const bool __is_map = false; 554 555 _LIBCPP_INLINE_VISIBILITY 556 static key_type const& __get_key(_Tp const& __v) { 557 return __v; 558 } 559 _LIBCPP_INLINE_VISIBILITY 560 static __container_value_type const& __get_value(__node_value_type const& __v) { 561 return __v; 562 } 563 _LIBCPP_INLINE_VISIBILITY 564 static __container_value_type* __get_ptr(__node_value_type& __n) { 565 return _VSTD::addressof(__n); 566 } 567 _LIBCPP_INLINE_VISIBILITY 568 static __container_value_type&& __move(__node_value_type& __v) { 569 return _VSTD::move(__v); 570 } 571}; 572 573template <class _Key, class _Tp> 574struct __tree_key_value_types<__value_type<_Key, _Tp> > { 575 typedef _Key key_type; 576 typedef _Tp mapped_type; 577 typedef __value_type<_Key, _Tp> __node_value_type; 578 typedef pair<const _Key, _Tp> __container_value_type; 579 typedef __container_value_type __map_value_type; 580 static const bool __is_map = true; 581 582 _LIBCPP_INLINE_VISIBILITY 583 static key_type const& 584 __get_key(__node_value_type const& __t) { 585 return __t.__get_value().first; 586 } 587 588 template <class _Up> 589 _LIBCPP_INLINE_VISIBILITY 590 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, 591 key_type const&>::type 592 __get_key(_Up& __t) { 593 return __t.first; 594 } 595 596 _LIBCPP_INLINE_VISIBILITY 597 static __container_value_type const& 598 __get_value(__node_value_type const& __t) { 599 return __t.__get_value(); 600 } 601 602 template <class _Up> 603 _LIBCPP_INLINE_VISIBILITY 604 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, 605 __container_value_type const&>::type 606 __get_value(_Up& __t) { 607 return __t; 608 } 609 610 _LIBCPP_INLINE_VISIBILITY 611 static __container_value_type* __get_ptr(__node_value_type& __n) { 612 return _VSTD::addressof(__n.__get_value()); 613 } 614 615 _LIBCPP_INLINE_VISIBILITY 616 static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { 617 return __v.__move(); 618 } 619}; 620 621template <class _VoidPtr> 622struct __tree_node_base_types { 623 typedef _VoidPtr __void_pointer; 624 625 typedef __tree_node_base<__void_pointer> __node_base_type; 626 typedef typename __rebind_pointer<_VoidPtr, __node_base_type>::type 627 __node_base_pointer; 628 629 typedef __tree_end_node<__node_base_pointer> __end_node_type; 630 typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type 631 __end_node_pointer; 632#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) 633 typedef __end_node_pointer __parent_pointer; 634#else 635 typedef typename conditional< 636 is_pointer<__end_node_pointer>::value, 637 __end_node_pointer, 638 __node_base_pointer>::type __parent_pointer; 639#endif 640 641private: 642 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value), 643 "_VoidPtr does not point to unqualified void type"); 644}; 645 646template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>, 647 bool = _KVTypes::__is_map> 648struct __tree_map_pointer_types {}; 649 650template <class _Tp, class _AllocPtr, class _KVTypes> 651struct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> { 652 typedef typename _KVTypes::__map_value_type _Mv; 653 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type 654 __map_value_type_pointer; 655 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type 656 __const_map_value_type_pointer; 657}; 658 659template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type> 660struct __tree_node_types; 661 662template <class _NodePtr, class _Tp, class _VoidPtr> 663struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> > 664 : public __tree_node_base_types<_VoidPtr>, 665 __tree_key_value_types<_Tp>, 666 __tree_map_pointer_types<_Tp, _VoidPtr> 667{ 668 typedef __tree_node_base_types<_VoidPtr> __base; 669 typedef __tree_key_value_types<_Tp> __key_base; 670 typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base; 671public: 672 673 typedef typename pointer_traits<_NodePtr>::element_type __node_type; 674 typedef _NodePtr __node_pointer; 675 676 typedef _Tp __node_value_type; 677 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type 678 __node_value_type_pointer; 679 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type 680 __const_node_value_type_pointer; 681#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) 682 typedef typename __base::__end_node_pointer __iter_pointer; 683#else 684 typedef typename conditional< 685 is_pointer<__node_pointer>::value, 686 typename __base::__end_node_pointer, 687 __node_pointer>::type __iter_pointer; 688#endif 689private: 690 static_assert(!is_const<__node_type>::value, 691 "_NodePtr should never be a pointer to const"); 692 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type, 693 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr."); 694}; 695 696template <class _ValueTp, class _VoidPtr> 697struct __make_tree_node_types { 698 typedef typename __rebind_pointer<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> >::type 699 _NodePtr; 700 typedef __tree_node_types<_NodePtr> type; 701}; 702 703// node 704 705template <class _Pointer> 706class __tree_end_node 707{ 708public: 709 typedef _Pointer pointer; 710 pointer __left_; 711 712 _LIBCPP_INLINE_VISIBILITY 713 __tree_end_node() _NOEXCEPT : __left_() {} 714}; 715 716template <class _VoidPtr> 717class __tree_node_base 718 : public __tree_node_base_types<_VoidPtr>::__end_node_type 719{ 720 typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes; 721 722public: 723 typedef typename _NodeBaseTypes::__node_base_pointer pointer; 724 typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer; 725 726 pointer __right_; 727 __parent_pointer __parent_; 728 bool __is_black_; 729 730 _LIBCPP_INLINE_VISIBILITY 731 pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);} 732 733 _LIBCPP_INLINE_VISIBILITY 734 void __set_parent(pointer __p) { 735 __parent_ = static_cast<__parent_pointer>(__p); 736 } 737 738private: 739 ~__tree_node_base() _LIBCPP_EQUAL_DELETE; 740 __tree_node_base(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; 741 __tree_node_base& operator=(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; 742}; 743 744template <class _Tp, class _VoidPtr> 745class __tree_node 746 : public __tree_node_base<_VoidPtr> 747{ 748public: 749 typedef _Tp __node_value_type; 750 751 __node_value_type __value_; 752 753private: 754 ~__tree_node() _LIBCPP_EQUAL_DELETE; 755 __tree_node(__tree_node const&) _LIBCPP_EQUAL_DELETE; 756 __tree_node& operator=(__tree_node const&) _LIBCPP_EQUAL_DELETE; 757}; 758 759 760template <class _Allocator> 761class __tree_node_destructor 762{ 763 typedef _Allocator allocator_type; 764 typedef allocator_traits<allocator_type> __alloc_traits; 765 766public: 767 typedef typename __alloc_traits::pointer pointer; 768private: 769 typedef __tree_node_types<pointer> _NodeTypes; 770 allocator_type& __na_; 771 772 773public: 774 bool __value_constructed; 775 776 777 __tree_node_destructor(const __tree_node_destructor &) = default; 778 __tree_node_destructor& operator=(const __tree_node_destructor&) = delete; 779 780 _LIBCPP_INLINE_VISIBILITY 781 explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT 782 : __na_(__na), 783 __value_constructed(__val) 784 {} 785 786 _LIBCPP_INLINE_VISIBILITY 787 void operator()(pointer __p) _NOEXCEPT 788 { 789 if (__value_constructed) 790 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 791 if (__p) 792 __alloc_traits::deallocate(__na_, __p, 1); 793 } 794 795 template <class> friend class __map_node_destructor; 796}; 797 798#if _LIBCPP_STD_VER > 14 799template <class _NodeType, class _Alloc> 800struct __generic_container_node_destructor; 801template <class _Tp, class _VoidPtr, class _Alloc> 802struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> 803 : __tree_node_destructor<_Alloc> 804{ 805 using __tree_node_destructor<_Alloc>::__tree_node_destructor; 806}; 807#endif 808 809template <class _Tp, class _NodePtr, class _DiffType> 810class _LIBCPP_TEMPLATE_VIS __tree_iterator 811{ 812 typedef __tree_node_types<_NodePtr> _NodeTypes; 813 typedef _NodePtr __node_pointer; 814 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 815 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 816 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 817 typedef pointer_traits<__node_pointer> __pointer_traits; 818 819 __iter_pointer __ptr_; 820 821public: 822 typedef bidirectional_iterator_tag iterator_category; 823 typedef _Tp value_type; 824 typedef _DiffType difference_type; 825 typedef value_type& reference; 826 typedef typename _NodeTypes::__node_value_type_pointer pointer; 827 828 _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT 829#if _LIBCPP_STD_VER > 11 830 : __ptr_(nullptr) 831#endif 832 {} 833 834 _LIBCPP_INLINE_VISIBILITY reference operator*() const 835 {return __get_np()->__value_;} 836 _LIBCPP_INLINE_VISIBILITY pointer operator->() const 837 {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);} 838 839 _LIBCPP_INLINE_VISIBILITY 840 __tree_iterator& operator++() { 841 __ptr_ = static_cast<__iter_pointer>( 842 _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 843 return *this; 844 } 845 _LIBCPP_INLINE_VISIBILITY 846 __tree_iterator operator++(int) 847 {__tree_iterator __t(*this); ++(*this); return __t;} 848 849 _LIBCPP_INLINE_VISIBILITY 850 __tree_iterator& operator--() { 851 __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>( 852 static_cast<__end_node_pointer>(__ptr_))); 853 return *this; 854 } 855 _LIBCPP_INLINE_VISIBILITY 856 __tree_iterator operator--(int) 857 {__tree_iterator __t(*this); --(*this); return __t;} 858 859 friend _LIBCPP_INLINE_VISIBILITY 860 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 861 {return __x.__ptr_ == __y.__ptr_;} 862 friend _LIBCPP_INLINE_VISIBILITY 863 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 864 {return !(__x == __y);} 865 866private: 867 _LIBCPP_INLINE_VISIBILITY 868 explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 869 _LIBCPP_INLINE_VISIBILITY 870 explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 871 _LIBCPP_INLINE_VISIBILITY 872 __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 873 template <class, class, class> friend class __tree; 874 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 875 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_iterator; 876 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 877 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 878 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set; 879 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset; 880}; 881 882template <class _Tp, class _NodePtr, class _DiffType> 883class _LIBCPP_TEMPLATE_VIS __tree_const_iterator 884{ 885 typedef __tree_node_types<_NodePtr> _NodeTypes; 886 typedef typename _NodeTypes::__node_pointer __node_pointer; 887 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 888 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 889 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 890 typedef pointer_traits<__node_pointer> __pointer_traits; 891 892 __iter_pointer __ptr_; 893 894public: 895 typedef bidirectional_iterator_tag iterator_category; 896 typedef _Tp value_type; 897 typedef _DiffType difference_type; 898 typedef const value_type& reference; 899 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 900 901 _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT 902#if _LIBCPP_STD_VER > 11 903 : __ptr_(nullptr) 904#endif 905 {} 906 907private: 908 typedef __tree_iterator<value_type, __node_pointer, difference_type> 909 __non_const_iterator; 910public: 911 _LIBCPP_INLINE_VISIBILITY 912 __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 913 : __ptr_(__p.__ptr_) {} 914 915 _LIBCPP_INLINE_VISIBILITY reference operator*() const 916 {return __get_np()->__value_;} 917 _LIBCPP_INLINE_VISIBILITY pointer operator->() const 918 {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);} 919 920 _LIBCPP_INLINE_VISIBILITY 921 __tree_const_iterator& operator++() { 922 __ptr_ = static_cast<__iter_pointer>( 923 _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 924 return *this; 925 } 926 927 _LIBCPP_INLINE_VISIBILITY 928 __tree_const_iterator operator++(int) 929 {__tree_const_iterator __t(*this); ++(*this); return __t;} 930 931 _LIBCPP_INLINE_VISIBILITY 932 __tree_const_iterator& operator--() { 933 __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>( 934 static_cast<__end_node_pointer>(__ptr_))); 935 return *this; 936 } 937 938 _LIBCPP_INLINE_VISIBILITY 939 __tree_const_iterator operator--(int) 940 {__tree_const_iterator __t(*this); --(*this); return __t;} 941 942 friend _LIBCPP_INLINE_VISIBILITY 943 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 944 {return __x.__ptr_ == __y.__ptr_;} 945 friend _LIBCPP_INLINE_VISIBILITY 946 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 947 {return !(__x == __y);} 948 949private: 950 _LIBCPP_INLINE_VISIBILITY 951 explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 952 : __ptr_(__p) {} 953 _LIBCPP_INLINE_VISIBILITY 954 explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT 955 : __ptr_(__p) {} 956 _LIBCPP_INLINE_VISIBILITY 957 __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 958 959 template <class, class, class> friend class __tree; 960 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 961 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 962 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set; 963 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset; 964 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 965 966}; 967 968template<class _Tp, class _Compare> 969#ifndef _LIBCPP_CXX03_LANG 970 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, 971 "the specified comparator type does not provide a viable const call operator") 972#endif 973int __diagnose_non_const_comparator(); 974 975template <class _Tp, class _Compare, class _Allocator> 976class __tree 977{ 978public: 979 typedef _Tp value_type; 980 typedef _Compare value_compare; 981 typedef _Allocator allocator_type; 982 983private: 984 typedef allocator_traits<allocator_type> __alloc_traits; 985 typedef typename __make_tree_node_types<value_type, 986 typename __alloc_traits::void_pointer>::type 987 _NodeTypes; 988 typedef typename _NodeTypes::key_type key_type; 989public: 990 typedef typename _NodeTypes::__node_value_type __node_value_type; 991 typedef typename _NodeTypes::__container_value_type __container_value_type; 992 993 typedef typename __alloc_traits::pointer pointer; 994 typedef typename __alloc_traits::const_pointer const_pointer; 995 typedef typename __alloc_traits::size_type size_type; 996 typedef typename __alloc_traits::difference_type difference_type; 997 998public: 999 typedef typename _NodeTypes::__void_pointer __void_pointer; 1000 1001 typedef typename _NodeTypes::__node_type __node; 1002 typedef typename _NodeTypes::__node_pointer __node_pointer; 1003 1004 typedef typename _NodeTypes::__node_base_type __node_base; 1005 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 1006 1007 typedef typename _NodeTypes::__end_node_type __end_node_t; 1008 typedef typename _NodeTypes::__end_node_pointer __end_node_ptr; 1009 1010 typedef typename _NodeTypes::__parent_pointer __parent_pointer; 1011 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 1012 1013 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 1014 typedef allocator_traits<__node_allocator> __node_traits; 1015 1016private: 1017 // check for sane allocator pointer rebinding semantics. Rebinding the 1018 // allocator for a new pointer type should be exactly the same as rebinding 1019 // the pointer using 'pointer_traits'. 1020 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), 1021 "Allocator does not rebind pointers in a sane manner."); 1022 typedef typename __rebind_alloc_helper<__node_traits, __node_base>::type 1023 __node_base_allocator; 1024 typedef allocator_traits<__node_base_allocator> __node_base_traits; 1025 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), 1026 "Allocator does not rebind pointers in a sane manner."); 1027 1028private: 1029 __iter_pointer __begin_node_; 1030 __compressed_pair<__end_node_t, __node_allocator> __pair1_; 1031 __compressed_pair<size_type, value_compare> __pair3_; 1032 1033public: 1034 _LIBCPP_INLINE_VISIBILITY 1035 __iter_pointer __end_node() _NOEXCEPT 1036 { 1037 return static_cast<__iter_pointer>( 1038 pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 1039 ); 1040 } 1041 _LIBCPP_INLINE_VISIBILITY 1042 __iter_pointer __end_node() const _NOEXCEPT 1043 { 1044 return static_cast<__iter_pointer>( 1045 pointer_traits<__end_node_ptr>::pointer_to( 1046 const_cast<__end_node_t&>(__pair1_.first()) 1047 ) 1048 ); 1049 } 1050 _LIBCPP_INLINE_VISIBILITY 1051 __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 1052private: 1053 _LIBCPP_INLINE_VISIBILITY 1054 const __node_allocator& __node_alloc() const _NOEXCEPT 1055 {return __pair1_.second();} 1056 _LIBCPP_INLINE_VISIBILITY 1057 __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 1058 _LIBCPP_INLINE_VISIBILITY 1059 const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 1060public: 1061 _LIBCPP_INLINE_VISIBILITY 1062 allocator_type __alloc() const _NOEXCEPT 1063 {return allocator_type(__node_alloc());} 1064private: 1065 _LIBCPP_INLINE_VISIBILITY 1066 size_type& size() _NOEXCEPT {return __pair3_.first();} 1067public: 1068 _LIBCPP_INLINE_VISIBILITY 1069 const size_type& size() const _NOEXCEPT {return __pair3_.first();} 1070 _LIBCPP_INLINE_VISIBILITY 1071 value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 1072 _LIBCPP_INLINE_VISIBILITY 1073 const value_compare& value_comp() const _NOEXCEPT 1074 {return __pair3_.second();} 1075public: 1076 1077 _LIBCPP_INLINE_VISIBILITY 1078 __node_pointer __root() const _NOEXCEPT 1079 {return static_cast<__node_pointer>(__end_node()->__left_);} 1080 1081 __node_base_pointer* __root_ptr() const _NOEXCEPT { 1082 return _VSTD::addressof(__end_node()->__left_); 1083 } 1084 1085 typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 1086 typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 1087 1088 explicit __tree(const value_compare& __comp) 1089 _NOEXCEPT_( 1090 is_nothrow_default_constructible<__node_allocator>::value && 1091 is_nothrow_copy_constructible<value_compare>::value); 1092 explicit __tree(const allocator_type& __a); 1093 __tree(const value_compare& __comp, const allocator_type& __a); 1094 __tree(const __tree& __t); 1095 __tree& operator=(const __tree& __t); 1096 template <class _ForwardIterator> 1097 void __assign_unique(_ForwardIterator __first, _ForwardIterator __last); 1098 template <class _InputIterator> 1099 void __assign_multi(_InputIterator __first, _InputIterator __last); 1100 __tree(__tree&& __t) 1101 _NOEXCEPT_( 1102 is_nothrow_move_constructible<__node_allocator>::value && 1103 is_nothrow_move_constructible<value_compare>::value); 1104 __tree(__tree&& __t, const allocator_type& __a); 1105 __tree& operator=(__tree&& __t) 1106 _NOEXCEPT_( 1107 __node_traits::propagate_on_container_move_assignment::value && 1108 is_nothrow_move_assignable<value_compare>::value && 1109 is_nothrow_move_assignable<__node_allocator>::value); 1110 ~__tree(); 1111 1112 _LIBCPP_INLINE_VISIBILITY 1113 iterator begin() _NOEXCEPT {return iterator(__begin_node());} 1114 _LIBCPP_INLINE_VISIBILITY 1115 const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 1116 _LIBCPP_INLINE_VISIBILITY 1117 iterator end() _NOEXCEPT {return iterator(__end_node());} 1118 _LIBCPP_INLINE_VISIBILITY 1119 const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 1120 1121 _LIBCPP_INLINE_VISIBILITY 1122 size_type max_size() const _NOEXCEPT 1123 {return _VSTD::min<size_type>( 1124 __node_traits::max_size(__node_alloc()), 1125 numeric_limits<difference_type >::max());} 1126 1127 void clear() _NOEXCEPT; 1128 1129 void swap(__tree& __t) 1130#if _LIBCPP_STD_VER <= 11 1131 _NOEXCEPT_( 1132 __is_nothrow_swappable<value_compare>::value 1133 && (!__node_traits::propagate_on_container_swap::value || 1134 __is_nothrow_swappable<__node_allocator>::value) 1135 ); 1136#else 1137 _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value); 1138#endif 1139 1140 template <class _Key, class ..._Args> 1141 pair<iterator, bool> 1142 __emplace_unique_key_args(_Key const&, _Args&&... __args); 1143 template <class _Key, class ..._Args> 1144 pair<iterator, bool> 1145 __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); 1146 1147 template <class... _Args> 1148 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 1149 1150 template <class... _Args> 1151 iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); 1152 1153 template <class... _Args> 1154 iterator __emplace_multi(_Args&&... __args); 1155 1156 template <class... _Args> 1157 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 1158 1159 template <class _Pp> 1160 _LIBCPP_INLINE_VISIBILITY 1161 pair<iterator, bool> __emplace_unique(_Pp&& __x) { 1162 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), 1163 __can_extract_key<_Pp, key_type>()); 1164 } 1165 1166 template <class _First, class _Second> 1167 _LIBCPP_INLINE_VISIBILITY 1168 typename enable_if< 1169 __can_extract_map_key<_First, key_type, __container_value_type>::value, 1170 pair<iterator, bool> 1171 >::type __emplace_unique(_First&& __f, _Second&& __s) { 1172 return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), 1173 _VSTD::forward<_Second>(__s)); 1174 } 1175 1176 template <class... _Args> 1177 _LIBCPP_INLINE_VISIBILITY 1178 pair<iterator, bool> __emplace_unique(_Args&&... __args) { 1179 return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); 1180 } 1181 1182 template <class _Pp> 1183 _LIBCPP_INLINE_VISIBILITY 1184 pair<iterator, bool> 1185 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 1186 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); 1187 } 1188 1189 template <class _Pp> 1190 _LIBCPP_INLINE_VISIBILITY 1191 pair<iterator, bool> 1192 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 1193 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); 1194 } 1195 1196 template <class _Pp> 1197 _LIBCPP_INLINE_VISIBILITY 1198 pair<iterator, bool> 1199 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 1200 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); 1201 } 1202 1203 template <class _Pp> 1204 _LIBCPP_INLINE_VISIBILITY 1205 iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { 1206 return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x), 1207 __can_extract_key<_Pp, key_type>()); 1208 } 1209 1210 template <class _First, class _Second> 1211 _LIBCPP_INLINE_VISIBILITY 1212 typename enable_if< 1213 __can_extract_map_key<_First, key_type, __container_value_type>::value, 1214 iterator 1215 >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { 1216 return __emplace_hint_unique_key_args(__p, __f, 1217 _VSTD::forward<_First>(__f), 1218 _VSTD::forward<_Second>(__s)).first; 1219 } 1220 1221 template <class... _Args> 1222 _LIBCPP_INLINE_VISIBILITY 1223 iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { 1224 return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...); 1225 } 1226 1227 template <class _Pp> 1228 _LIBCPP_INLINE_VISIBILITY 1229 iterator 1230 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { 1231 return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x)); 1232 } 1233 1234 template <class _Pp> 1235 _LIBCPP_INLINE_VISIBILITY 1236 iterator 1237 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { 1238 return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first; 1239 } 1240 1241 template <class _Pp> 1242 _LIBCPP_INLINE_VISIBILITY 1243 iterator 1244 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { 1245 return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first; 1246 } 1247 1248 _LIBCPP_INLINE_VISIBILITY 1249 pair<iterator, bool> __insert_unique(const __container_value_type& __v) { 1250 return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); 1251 } 1252 1253 _LIBCPP_INLINE_VISIBILITY 1254 iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { 1255 return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first; 1256 } 1257 1258 _LIBCPP_INLINE_VISIBILITY 1259 pair<iterator, bool> __insert_unique(__container_value_type&& __v) { 1260 return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v)); 1261 } 1262 1263 _LIBCPP_INLINE_VISIBILITY 1264 iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { 1265 return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first; 1266 } 1267 1268 template <class _Vp, class = typename enable_if< 1269 !is_same<typename __unconstref<_Vp>::type, 1270 __container_value_type 1271 >::value 1272 >::type> 1273 _LIBCPP_INLINE_VISIBILITY 1274 pair<iterator, bool> __insert_unique(_Vp&& __v) { 1275 return __emplace_unique(_VSTD::forward<_Vp>(__v)); 1276 } 1277 1278 template <class _Vp, class = typename enable_if< 1279 !is_same<typename __unconstref<_Vp>::type, 1280 __container_value_type 1281 >::value 1282 >::type> 1283 _LIBCPP_INLINE_VISIBILITY 1284 iterator __insert_unique(const_iterator __p, _Vp&& __v) { 1285 return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v)); 1286 } 1287 1288 _LIBCPP_INLINE_VISIBILITY 1289 iterator __insert_multi(__container_value_type&& __v) { 1290 return __emplace_multi(_VSTD::move(__v)); 1291 } 1292 1293 _LIBCPP_INLINE_VISIBILITY 1294 iterator __insert_multi(const_iterator __p, __container_value_type&& __v) { 1295 return __emplace_hint_multi(__p, _VSTD::move(__v)); 1296 } 1297 1298 template <class _Vp> 1299 _LIBCPP_INLINE_VISIBILITY 1300 iterator __insert_multi(_Vp&& __v) { 1301 return __emplace_multi(_VSTD::forward<_Vp>(__v)); 1302 } 1303 1304 template <class _Vp> 1305 _LIBCPP_INLINE_VISIBILITY 1306 iterator __insert_multi(const_iterator __p, _Vp&& __v) { 1307 return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v)); 1308 } 1309 1310 _LIBCPP_INLINE_VISIBILITY 1311 pair<iterator, bool> __node_assign_unique(const __container_value_type& __v, __node_pointer __dest); 1312 1313 _LIBCPP_INLINE_VISIBILITY 1314 iterator __node_insert_multi(__node_pointer __nd); 1315 _LIBCPP_INLINE_VISIBILITY 1316 iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 1317 1318 1319 _LIBCPP_INLINE_VISIBILITY iterator 1320 __remove_node_pointer(__node_pointer) _NOEXCEPT; 1321 1322#if _LIBCPP_STD_VER > 14 1323 template <class _NodeHandle, class _InsertReturnType> 1324 _LIBCPP_INLINE_VISIBILITY 1325 _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); 1326 template <class _NodeHandle> 1327 _LIBCPP_INLINE_VISIBILITY 1328 iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); 1329 template <class _Tree> 1330 _LIBCPP_INLINE_VISIBILITY 1331 void __node_handle_merge_unique(_Tree& __source); 1332 1333 template <class _NodeHandle> 1334 _LIBCPP_INLINE_VISIBILITY 1335 iterator __node_handle_insert_multi(_NodeHandle&&); 1336 template <class _NodeHandle> 1337 _LIBCPP_INLINE_VISIBILITY 1338 iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); 1339 template <class _Tree> 1340 _LIBCPP_INLINE_VISIBILITY 1341 void __node_handle_merge_multi(_Tree& __source); 1342 1343 1344 template <class _NodeHandle> 1345 _LIBCPP_INLINE_VISIBILITY 1346 _NodeHandle __node_handle_extract(key_type const&); 1347 template <class _NodeHandle> 1348 _LIBCPP_INLINE_VISIBILITY 1349 _NodeHandle __node_handle_extract(const_iterator); 1350#endif 1351 1352 iterator erase(const_iterator __p); 1353 iterator erase(const_iterator __f, const_iterator __l); 1354 template <class _Key> 1355 size_type __erase_unique(const _Key& __k); 1356 template <class _Key> 1357 size_type __erase_multi(const _Key& __k); 1358 1359 void __insert_node_at(__parent_pointer __parent, 1360 __node_base_pointer& __child, 1361 __node_base_pointer __new_node) _NOEXCEPT; 1362 1363 template <class _Key> 1364 iterator find(const _Key& __v); 1365 template <class _Key> 1366 const_iterator find(const _Key& __v) const; 1367 1368 template <class _Key> 1369 size_type __count_unique(const _Key& __k) const; 1370 template <class _Key> 1371 size_type __count_multi(const _Key& __k) const; 1372 1373 template <class _Key> 1374 _LIBCPP_INLINE_VISIBILITY 1375 iterator lower_bound(const _Key& __v) 1376 {return __lower_bound(__v, __root(), __end_node());} 1377 template <class _Key> 1378 iterator __lower_bound(const _Key& __v, 1379 __node_pointer __root, 1380 __iter_pointer __result); 1381 template <class _Key> 1382 _LIBCPP_INLINE_VISIBILITY 1383 const_iterator lower_bound(const _Key& __v) const 1384 {return __lower_bound(__v, __root(), __end_node());} 1385 template <class _Key> 1386 const_iterator __lower_bound(const _Key& __v, 1387 __node_pointer __root, 1388 __iter_pointer __result) const; 1389 template <class _Key> 1390 _LIBCPP_INLINE_VISIBILITY 1391 iterator upper_bound(const _Key& __v) 1392 {return __upper_bound(__v, __root(), __end_node());} 1393 template <class _Key> 1394 iterator __upper_bound(const _Key& __v, 1395 __node_pointer __root, 1396 __iter_pointer __result); 1397 template <class _Key> 1398 _LIBCPP_INLINE_VISIBILITY 1399 const_iterator upper_bound(const _Key& __v) const 1400 {return __upper_bound(__v, __root(), __end_node());} 1401 template <class _Key> 1402 const_iterator __upper_bound(const _Key& __v, 1403 __node_pointer __root, 1404 __iter_pointer __result) const; 1405 template <class _Key> 1406 pair<iterator, iterator> 1407 __equal_range_unique(const _Key& __k); 1408 template <class _Key> 1409 pair<const_iterator, const_iterator> 1410 __equal_range_unique(const _Key& __k) const; 1411 1412 template <class _Key> 1413 pair<iterator, iterator> 1414 __equal_range_multi(const _Key& __k); 1415 template <class _Key> 1416 pair<const_iterator, const_iterator> 1417 __equal_range_multi(const _Key& __k) const; 1418 1419 typedef __tree_node_destructor<__node_allocator> _Dp; 1420 typedef unique_ptr<__node, _Dp> __node_holder; 1421 1422 __node_holder remove(const_iterator __p) _NOEXCEPT; 1423private: 1424 __node_base_pointer& 1425 __find_leaf_low(__parent_pointer& __parent, const key_type& __v); 1426 __node_base_pointer& 1427 __find_leaf_high(__parent_pointer& __parent, const key_type& __v); 1428 __node_base_pointer& 1429 __find_leaf(const_iterator __hint, 1430 __parent_pointer& __parent, const key_type& __v); 1431 // FIXME: Make this function const qualified. Unfortunately doing so 1432 // breaks existing code which uses non-const callable comparators. 1433 template <class _Key> 1434 __node_base_pointer& 1435 __find_equal(__parent_pointer& __parent, const _Key& __v); 1436 template <class _Key> 1437 _LIBCPP_INLINE_VISIBILITY __node_base_pointer& 1438 __find_equal(__parent_pointer& __parent, const _Key& __v) const { 1439 return const_cast<__tree*>(this)->__find_equal(__parent, __v); 1440 } 1441 template <class _Key> 1442 __node_base_pointer& 1443 __find_equal(const_iterator __hint, __parent_pointer& __parent, 1444 __node_base_pointer& __dummy, 1445 const _Key& __v); 1446 1447 template <class ..._Args> 1448 __node_holder __construct_node(_Args&& ...__args); 1449 1450 void destroy(__node_pointer __nd) _NOEXCEPT; 1451 1452 _LIBCPP_INLINE_VISIBILITY 1453 void __copy_assign_alloc(const __tree& __t) 1454 {__copy_assign_alloc(__t, integral_constant<bool, 1455 __node_traits::propagate_on_container_copy_assignment::value>());} 1456 1457 _LIBCPP_INLINE_VISIBILITY 1458 void __copy_assign_alloc(const __tree& __t, true_type) 1459 { 1460 if (__node_alloc() != __t.__node_alloc()) 1461 clear(); 1462 __node_alloc() = __t.__node_alloc(); 1463 } 1464 _LIBCPP_INLINE_VISIBILITY 1465 void __copy_assign_alloc(const __tree&, false_type) {} 1466 1467 void __move_assign(__tree& __t, false_type); 1468 void __move_assign(__tree& __t, true_type) 1469 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1470 is_nothrow_move_assignable<__node_allocator>::value); 1471 1472 _LIBCPP_INLINE_VISIBILITY 1473 void __move_assign_alloc(__tree& __t) 1474 _NOEXCEPT_( 1475 !__node_traits::propagate_on_container_move_assignment::value || 1476 is_nothrow_move_assignable<__node_allocator>::value) 1477 {__move_assign_alloc(__t, integral_constant<bool, 1478 __node_traits::propagate_on_container_move_assignment::value>());} 1479 1480 _LIBCPP_INLINE_VISIBILITY 1481 void __move_assign_alloc(__tree& __t, true_type) 1482 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1483 {__node_alloc() = _VSTD::move(__t.__node_alloc());} 1484 _LIBCPP_INLINE_VISIBILITY 1485 void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {} 1486 1487 struct _DetachedTreeCache { 1488 _LIBCPP_INLINE_VISIBILITY 1489 explicit _DetachedTreeCache(__tree *__t) _NOEXCEPT : __t_(__t), 1490 __cache_root_(__detach_from_tree(__t)) { 1491 __advance(); 1492 } 1493 1494 _LIBCPP_INLINE_VISIBILITY 1495 __node_pointer __get() const _NOEXCEPT { 1496 return __cache_elem_; 1497 } 1498 1499 _LIBCPP_INLINE_VISIBILITY 1500 void __advance() _NOEXCEPT { 1501 __cache_elem_ = __cache_root_; 1502 if (__cache_root_) { 1503 __cache_root_ = __detach_next(__cache_root_); 1504 } 1505 } 1506 1507 _LIBCPP_INLINE_VISIBILITY 1508 ~_DetachedTreeCache() { 1509 __t_->destroy(__cache_elem_); 1510 if (__cache_root_) { 1511 while (__cache_root_->__parent_ != nullptr) 1512 __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_); 1513 __t_->destroy(__cache_root_); 1514 } 1515 } 1516 1517 _DetachedTreeCache(_DetachedTreeCache const&) = delete; 1518 _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete; 1519 1520 private: 1521 _LIBCPP_INLINE_VISIBILITY 1522 static __node_pointer __detach_from_tree(__tree *__t) _NOEXCEPT; 1523 _LIBCPP_INLINE_VISIBILITY 1524 static __node_pointer __detach_next(__node_pointer) _NOEXCEPT; 1525 1526 __tree *__t_; 1527 __node_pointer __cache_root_; 1528 __node_pointer __cache_elem_; 1529 }; 1530 1531 1532 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 1533 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 1534}; 1535 1536template <class _Tp, class _Compare, class _Allocator> 1537__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 1538 _NOEXCEPT_( 1539 is_nothrow_default_constructible<__node_allocator>::value && 1540 is_nothrow_copy_constructible<value_compare>::value) 1541 : __pair3_(0, __comp) 1542{ 1543 __begin_node() = __end_node(); 1544} 1545 1546template <class _Tp, class _Compare, class _Allocator> 1547__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1548 : __begin_node_(__iter_pointer()), 1549 __pair1_(__default_init_tag(), __node_allocator(__a)), 1550 __pair3_(0, __default_init_tag()) 1551{ 1552 __begin_node() = __end_node(); 1553} 1554 1555template <class _Tp, class _Compare, class _Allocator> 1556__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 1557 const allocator_type& __a) 1558 : __begin_node_(__iter_pointer()), 1559 __pair1_(__default_init_tag(), __node_allocator(__a)), 1560 __pair3_(0, __comp) 1561{ 1562 __begin_node() = __end_node(); 1563} 1564 1565// Precondition: size() != 0 1566template <class _Tp, class _Compare, class _Allocator> 1567typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1568__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree *__t) _NOEXCEPT 1569{ 1570 __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node()); 1571 __t->__begin_node() = __t->__end_node(); 1572 __t->__end_node()->__left_->__parent_ = nullptr; 1573 __t->__end_node()->__left_ = nullptr; 1574 __t->size() = 0; 1575 // __cache->__left_ == nullptr 1576 if (__cache->__right_ != nullptr) 1577 __cache = static_cast<__node_pointer>(__cache->__right_); 1578 // __cache->__left_ == nullptr 1579 // __cache->__right_ == nullptr 1580 return __cache; 1581} 1582 1583// Precondition: __cache != nullptr 1584// __cache->left_ == nullptr 1585// __cache->right_ == nullptr 1586// This is no longer a red-black tree 1587template <class _Tp, class _Compare, class _Allocator> 1588typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1589__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT 1590{ 1591 if (__cache->__parent_ == nullptr) 1592 return nullptr; 1593 if (_VSTD::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 1594 { 1595 __cache->__parent_->__left_ = nullptr; 1596 __cache = static_cast<__node_pointer>(__cache->__parent_); 1597 if (__cache->__right_ == nullptr) 1598 return __cache; 1599 return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__right_)); 1600 } 1601 // __cache is right child 1602 __cache->__parent_unsafe()->__right_ = nullptr; 1603 __cache = static_cast<__node_pointer>(__cache->__parent_); 1604 if (__cache->__left_ == nullptr) 1605 return __cache; 1606 return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_)); 1607} 1608 1609template <class _Tp, class _Compare, class _Allocator> 1610__tree<_Tp, _Compare, _Allocator>& 1611__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 1612{ 1613 if (this != &__t) 1614 { 1615 value_comp() = __t.value_comp(); 1616 __copy_assign_alloc(__t); 1617 __assign_multi(__t.begin(), __t.end()); 1618 } 1619 return *this; 1620} 1621 1622template <class _Tp, class _Compare, class _Allocator> 1623template <class _ForwardIterator> 1624void 1625__tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) 1626{ 1627 typedef iterator_traits<_ForwardIterator> _ITraits; 1628 typedef typename _ITraits::value_type _ItValueType; 1629 static_assert((is_same<_ItValueType, __container_value_type>::value), 1630 "__assign_unique may only be called with the containers value type"); 1631 static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, 1632 "__assign_unique requires a forward iterator"); 1633 if (size() != 0) 1634 { 1635 _DetachedTreeCache __cache(this); 1636 for (; __cache.__get() != nullptr && __first != __last; ++__first) { 1637 if (__node_assign_unique(*__first, __cache.__get()).second) 1638 __cache.__advance(); 1639 } 1640 } 1641 for (; __first != __last; ++__first) 1642 __insert_unique(*__first); 1643} 1644 1645template <class _Tp, class _Compare, class _Allocator> 1646template <class _InputIterator> 1647void 1648__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 1649{ 1650 typedef iterator_traits<_InputIterator> _ITraits; 1651 typedef typename _ITraits::value_type _ItValueType; 1652 static_assert((is_same<_ItValueType, __container_value_type>::value || 1653 is_same<_ItValueType, __node_value_type>::value), 1654 "__assign_multi may only be called with the containers value type" 1655 " or the nodes value type"); 1656 if (size() != 0) 1657 { 1658 _DetachedTreeCache __cache(this); 1659 for (; __cache.__get() && __first != __last; ++__first) { 1660 __cache.__get()->__value_ = *__first; 1661 __node_insert_multi(__cache.__get()); 1662 __cache.__advance(); 1663 } 1664 } 1665 for (; __first != __last; ++__first) 1666 __insert_multi(_NodeTypes::__get_value(*__first)); 1667} 1668 1669template <class _Tp, class _Compare, class _Allocator> 1670__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1671 : __begin_node_(__iter_pointer()), 1672 __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1673 __pair3_(0, __t.value_comp()) 1674{ 1675 __begin_node() = __end_node(); 1676} 1677 1678template <class _Tp, class _Compare, class _Allocator> 1679__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 1680 _NOEXCEPT_( 1681 is_nothrow_move_constructible<__node_allocator>::value && 1682 is_nothrow_move_constructible<value_compare>::value) 1683 : __begin_node_(_VSTD::move(__t.__begin_node_)), 1684 __pair1_(_VSTD::move(__t.__pair1_)), 1685 __pair3_(_VSTD::move(__t.__pair3_)) 1686{ 1687 if (size() == 0) 1688 __begin_node() = __end_node(); 1689 else 1690 { 1691 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1692 __t.__begin_node() = __t.__end_node(); 1693 __t.__end_node()->__left_ = nullptr; 1694 __t.size() = 0; 1695 } 1696} 1697 1698template <class _Tp, class _Compare, class _Allocator> 1699__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1700 : __pair1_(__default_init_tag(), __node_allocator(__a)), 1701 __pair3_(0, _VSTD::move(__t.value_comp())) 1702{ 1703 if (__a == __t.__alloc()) 1704 { 1705 if (__t.size() == 0) 1706 __begin_node() = __end_node(); 1707 else 1708 { 1709 __begin_node() = __t.__begin_node(); 1710 __end_node()->__left_ = __t.__end_node()->__left_; 1711 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1712 size() = __t.size(); 1713 __t.__begin_node() = __t.__end_node(); 1714 __t.__end_node()->__left_ = nullptr; 1715 __t.size() = 0; 1716 } 1717 } 1718 else 1719 { 1720 __begin_node() = __end_node(); 1721 } 1722} 1723 1724template <class _Tp, class _Compare, class _Allocator> 1725void 1726__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1727 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1728 is_nothrow_move_assignable<__node_allocator>::value) 1729{ 1730 destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1731 __begin_node_ = __t.__begin_node_; 1732 __pair1_.first() = __t.__pair1_.first(); 1733 __move_assign_alloc(__t); 1734 __pair3_ = _VSTD::move(__t.__pair3_); 1735 if (size() == 0) 1736 __begin_node() = __end_node(); 1737 else 1738 { 1739 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1740 __t.__begin_node() = __t.__end_node(); 1741 __t.__end_node()->__left_ = nullptr; 1742 __t.size() = 0; 1743 } 1744} 1745 1746template <class _Tp, class _Compare, class _Allocator> 1747void 1748__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 1749{ 1750 if (__node_alloc() == __t.__node_alloc()) 1751 __move_assign(__t, true_type()); 1752 else 1753 { 1754 value_comp() = _VSTD::move(__t.value_comp()); 1755 const_iterator __e = end(); 1756 if (size() != 0) 1757 { 1758 _DetachedTreeCache __cache(this); 1759 while (__cache.__get() != nullptr && __t.size() != 0) { 1760 __cache.__get()->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 1761 __node_insert_multi(__cache.__get()); 1762 __cache.__advance(); 1763 } 1764 } 1765 while (__t.size() != 0) 1766 __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_)); 1767 } 1768} 1769 1770template <class _Tp, class _Compare, class _Allocator> 1771__tree<_Tp, _Compare, _Allocator>& 1772__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 1773 _NOEXCEPT_( 1774 __node_traits::propagate_on_container_move_assignment::value && 1775 is_nothrow_move_assignable<value_compare>::value && 1776 is_nothrow_move_assignable<__node_allocator>::value) 1777 1778{ 1779 __move_assign(__t, integral_constant<bool, 1780 __node_traits::propagate_on_container_move_assignment::value>()); 1781 return *this; 1782} 1783 1784template <class _Tp, class _Compare, class _Allocator> 1785__tree<_Tp, _Compare, _Allocator>::~__tree() 1786{ 1787 static_assert((is_copy_constructible<value_compare>::value), 1788 "Comparator must be copy-constructible."); 1789 destroy(__root()); 1790} 1791 1792template <class _Tp, class _Compare, class _Allocator> 1793void 1794__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 1795{ 1796 if (__nd != nullptr) 1797 { 1798 destroy(static_cast<__node_pointer>(__nd->__left_)); 1799 destroy(static_cast<__node_pointer>(__nd->__right_)); 1800 __node_allocator& __na = __node_alloc(); 1801 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_)); 1802 __node_traits::deallocate(__na, __nd, 1); 1803 } 1804} 1805 1806template <class _Tp, class _Compare, class _Allocator> 1807void 1808__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1809#if _LIBCPP_STD_VER <= 11 1810 _NOEXCEPT_( 1811 __is_nothrow_swappable<value_compare>::value 1812 && (!__node_traits::propagate_on_container_swap::value || 1813 __is_nothrow_swappable<__node_allocator>::value) 1814 ) 1815#else 1816 _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value) 1817#endif 1818{ 1819 using _VSTD::swap; 1820 swap(__begin_node_, __t.__begin_node_); 1821 swap(__pair1_.first(), __t.__pair1_.first()); 1822 _VSTD::__swap_allocator(__node_alloc(), __t.__node_alloc()); 1823 __pair3_.swap(__t.__pair3_); 1824 if (size() == 0) 1825 __begin_node() = __end_node(); 1826 else 1827 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1828 if (__t.size() == 0) 1829 __t.__begin_node() = __t.__end_node(); 1830 else 1831 __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node()); 1832} 1833 1834template <class _Tp, class _Compare, class _Allocator> 1835void 1836__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 1837{ 1838 destroy(__root()); 1839 size() = 0; 1840 __begin_node() = __end_node(); 1841 __end_node()->__left_ = nullptr; 1842} 1843 1844// Find lower_bound place to insert 1845// Set __parent to parent of null leaf 1846// Return reference to null leaf 1847template <class _Tp, class _Compare, class _Allocator> 1848typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1849__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent, 1850 const key_type& __v) 1851{ 1852 __node_pointer __nd = __root(); 1853 if (__nd != nullptr) 1854 { 1855 while (true) 1856 { 1857 if (value_comp()(__nd->__value_, __v)) 1858 { 1859 if (__nd->__right_ != nullptr) 1860 __nd = static_cast<__node_pointer>(__nd->__right_); 1861 else 1862 { 1863 __parent = static_cast<__parent_pointer>(__nd); 1864 return __nd->__right_; 1865 } 1866 } 1867 else 1868 { 1869 if (__nd->__left_ != nullptr) 1870 __nd = static_cast<__node_pointer>(__nd->__left_); 1871 else 1872 { 1873 __parent = static_cast<__parent_pointer>(__nd); 1874 return __parent->__left_; 1875 } 1876 } 1877 } 1878 } 1879 __parent = static_cast<__parent_pointer>(__end_node()); 1880 return __parent->__left_; 1881} 1882 1883// Find upper_bound place to insert 1884// Set __parent to parent of null leaf 1885// Return reference to null leaf 1886template <class _Tp, class _Compare, class _Allocator> 1887typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1888__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent, 1889 const key_type& __v) 1890{ 1891 __node_pointer __nd = __root(); 1892 if (__nd != nullptr) 1893 { 1894 while (true) 1895 { 1896 if (value_comp()(__v, __nd->__value_)) 1897 { 1898 if (__nd->__left_ != nullptr) 1899 __nd = static_cast<__node_pointer>(__nd->__left_); 1900 else 1901 { 1902 __parent = static_cast<__parent_pointer>(__nd); 1903 return __parent->__left_; 1904 } 1905 } 1906 else 1907 { 1908 if (__nd->__right_ != nullptr) 1909 __nd = static_cast<__node_pointer>(__nd->__right_); 1910 else 1911 { 1912 __parent = static_cast<__parent_pointer>(__nd); 1913 return __nd->__right_; 1914 } 1915 } 1916 } 1917 } 1918 __parent = static_cast<__parent_pointer>(__end_node()); 1919 return __parent->__left_; 1920} 1921 1922// Find leaf place to insert closest to __hint 1923// First check prior to __hint. 1924// Next check after __hint. 1925// Next do O(log N) search. 1926// Set __parent to parent of null leaf 1927// Return reference to null leaf 1928template <class _Tp, class _Compare, class _Allocator> 1929typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1930__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 1931 __parent_pointer& __parent, 1932 const key_type& __v) 1933{ 1934 if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1935 { 1936 // __v <= *__hint 1937 const_iterator __prior = __hint; 1938 if (__prior == begin() || !value_comp()(__v, *--__prior)) 1939 { 1940 // *prev(__hint) <= __v <= *__hint 1941 if (__hint.__ptr_->__left_ == nullptr) 1942 { 1943 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 1944 return __parent->__left_; 1945 } 1946 else 1947 { 1948 __parent = static_cast<__parent_pointer>(__prior.__ptr_); 1949 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; 1950 } 1951 } 1952 // __v < *prev(__hint) 1953 return __find_leaf_high(__parent, __v); 1954 } 1955 // else __v > *__hint 1956 return __find_leaf_low(__parent, __v); 1957} 1958 1959// Find place to insert if __v doesn't exist 1960// Set __parent to parent of null leaf 1961// Return reference to null leaf 1962// If __v exists, set parent to node of __v and return reference to node of __v 1963template <class _Tp, class _Compare, class _Allocator> 1964template <class _Key> 1965typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1966__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent, 1967 const _Key& __v) 1968{ 1969 __node_pointer __nd = __root(); 1970 __node_base_pointer* __nd_ptr = __root_ptr(); 1971 if (__nd != nullptr) 1972 { 1973 while (true) 1974 { 1975 if (value_comp()(__v, __nd->__value_)) 1976 { 1977 if (__nd->__left_ != nullptr) { 1978 __nd_ptr = _VSTD::addressof(__nd->__left_); 1979 __nd = static_cast<__node_pointer>(__nd->__left_); 1980 } else { 1981 __parent = static_cast<__parent_pointer>(__nd); 1982 return __parent->__left_; 1983 } 1984 } 1985 else if (value_comp()(__nd->__value_, __v)) 1986 { 1987 if (__nd->__right_ != nullptr) { 1988 __nd_ptr = _VSTD::addressof(__nd->__right_); 1989 __nd = static_cast<__node_pointer>(__nd->__right_); 1990 } else { 1991 __parent = static_cast<__parent_pointer>(__nd); 1992 return __nd->__right_; 1993 } 1994 } 1995 else 1996 { 1997 __parent = static_cast<__parent_pointer>(__nd); 1998 return *__nd_ptr; 1999 } 2000 } 2001 } 2002 __parent = static_cast<__parent_pointer>(__end_node()); 2003 return __parent->__left_; 2004} 2005 2006// Find place to insert if __v doesn't exist 2007// First check prior to __hint. 2008// Next check after __hint. 2009// Next do O(log N) search. 2010// Set __parent to parent of null leaf 2011// Return reference to null leaf 2012// If __v exists, set parent to node of __v and return reference to node of __v 2013template <class _Tp, class _Compare, class _Allocator> 2014template <class _Key> 2015typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 2016__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, 2017 __parent_pointer& __parent, 2018 __node_base_pointer& __dummy, 2019 const _Key& __v) 2020{ 2021 if (__hint == end() || value_comp()(__v, *__hint)) // check before 2022 { 2023 // __v < *__hint 2024 const_iterator __prior = __hint; 2025 if (__prior == begin() || value_comp()(*--__prior, __v)) 2026 { 2027 // *prev(__hint) < __v < *__hint 2028 if (__hint.__ptr_->__left_ == nullptr) 2029 { 2030 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 2031 return __parent->__left_; 2032 } 2033 else 2034 { 2035 __parent = static_cast<__parent_pointer>(__prior.__ptr_); 2036 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; 2037 } 2038 } 2039 // __v <= *prev(__hint) 2040 return __find_equal(__parent, __v); 2041 } 2042 else if (value_comp()(*__hint, __v)) // check after 2043 { 2044 // *__hint < __v 2045 const_iterator __next = _VSTD::next(__hint); 2046 if (__next == end() || value_comp()(__v, *__next)) 2047 { 2048 // *__hint < __v < *_VSTD::next(__hint) 2049 if (__hint.__get_np()->__right_ == nullptr) 2050 { 2051 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 2052 return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_; 2053 } 2054 else 2055 { 2056 __parent = static_cast<__parent_pointer>(__next.__ptr_); 2057 return __parent->__left_; 2058 } 2059 } 2060 // *next(__hint) <= __v 2061 return __find_equal(__parent, __v); 2062 } 2063 // else __v == *__hint 2064 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 2065 __dummy = static_cast<__node_base_pointer>(__hint.__ptr_); 2066 return __dummy; 2067} 2068 2069template <class _Tp, class _Compare, class _Allocator> 2070void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( 2071 __parent_pointer __parent, __node_base_pointer& __child, 2072 __node_base_pointer __new_node) _NOEXCEPT 2073{ 2074 __new_node->__left_ = nullptr; 2075 __new_node->__right_ = nullptr; 2076 __new_node->__parent_ = __parent; 2077 // __new_node->__is_black_ is initialized in __tree_balance_after_insert 2078 __child = __new_node; 2079 if (__begin_node()->__left_ != nullptr) 2080 __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_); 2081 _VSTD::__tree_balance_after_insert(__end_node()->__left_, __child); 2082 ++size(); 2083} 2084 2085template <class _Tp, class _Compare, class _Allocator> 2086template <class _Key, class... _Args> 2087pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 2088__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) 2089{ 2090 __parent_pointer __parent; 2091 __node_base_pointer& __child = __find_equal(__parent, __k); 2092 __node_pointer __r = static_cast<__node_pointer>(__child); 2093 bool __inserted = false; 2094 if (__child == nullptr) 2095 { 2096 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2097 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 2098 __r = __h.release(); 2099 __inserted = true; 2100 } 2101 return pair<iterator, bool>(iterator(__r), __inserted); 2102} 2103 2104template <class _Tp, class _Compare, class _Allocator> 2105template <class _Key, class... _Args> 2106pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 2107__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( 2108 const_iterator __p, _Key const& __k, _Args&&... __args) 2109{ 2110 __parent_pointer __parent; 2111 __node_base_pointer __dummy; 2112 __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); 2113 __node_pointer __r = static_cast<__node_pointer>(__child); 2114 bool __inserted = false; 2115 if (__child == nullptr) 2116 { 2117 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2118 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 2119 __r = __h.release(); 2120 __inserted = true; 2121 } 2122 return pair<iterator, bool>(iterator(__r), __inserted); 2123} 2124 2125template <class _Tp, class _Compare, class _Allocator> 2126template <class ..._Args> 2127typename __tree<_Tp, _Compare, _Allocator>::__node_holder 2128__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 2129{ 2130 static_assert(!__is_tree_value_type<_Args...>::value, 2131 "Cannot construct from __value_type"); 2132 __node_allocator& __na = __node_alloc(); 2133 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2134 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); 2135 __h.get_deleter().__value_constructed = true; 2136 return __h; 2137} 2138 2139 2140template <class _Tp, class _Compare, class _Allocator> 2141template <class... _Args> 2142pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 2143__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) 2144{ 2145 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2146 __parent_pointer __parent; 2147 __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 2148 __node_pointer __r = static_cast<__node_pointer>(__child); 2149 bool __inserted = false; 2150 if (__child == nullptr) 2151 { 2152 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 2153 __r = __h.release(); 2154 __inserted = true; 2155 } 2156 return pair<iterator, bool>(iterator(__r), __inserted); 2157} 2158 2159template <class _Tp, class _Compare, class _Allocator> 2160template <class... _Args> 2161typename __tree<_Tp, _Compare, _Allocator>::iterator 2162__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) 2163{ 2164 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2165 __parent_pointer __parent; 2166 __node_base_pointer __dummy; 2167 __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_); 2168 __node_pointer __r = static_cast<__node_pointer>(__child); 2169 if (__child == nullptr) 2170 { 2171 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 2172 __r = __h.release(); 2173 } 2174 return iterator(__r); 2175} 2176 2177template <class _Tp, class _Compare, class _Allocator> 2178template <class... _Args> 2179typename __tree<_Tp, _Compare, _Allocator>::iterator 2180__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 2181{ 2182 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2183 __parent_pointer __parent; 2184 __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_)); 2185 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 2186 return iterator(static_cast<__node_pointer>(__h.release())); 2187} 2188 2189template <class _Tp, class _Compare, class _Allocator> 2190template <class... _Args> 2191typename __tree<_Tp, _Compare, _Allocator>::iterator 2192__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 2193 _Args&&... __args) 2194{ 2195 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2196 __parent_pointer __parent; 2197 __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_)); 2198 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 2199 return iterator(static_cast<__node_pointer>(__h.release())); 2200} 2201 2202template <class _Tp, class _Compare, class _Allocator> 2203pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 2204__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd) 2205{ 2206 __parent_pointer __parent; 2207 __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__v)); 2208 __node_pointer __r = static_cast<__node_pointer>(__child); 2209 bool __inserted = false; 2210 if (__child == nullptr) 2211 { 2212 __nd->__value_ = __v; 2213 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 2214 __r = __nd; 2215 __inserted = true; 2216 } 2217 return pair<iterator, bool>(iterator(__r), __inserted); 2218} 2219 2220 2221template <class _Tp, class _Compare, class _Allocator> 2222typename __tree<_Tp, _Compare, _Allocator>::iterator 2223__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) 2224{ 2225 __parent_pointer __parent; 2226 __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_)); 2227 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 2228 return iterator(__nd); 2229} 2230 2231template <class _Tp, class _Compare, class _Allocator> 2232typename __tree<_Tp, _Compare, _Allocator>::iterator 2233__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, 2234 __node_pointer __nd) 2235{ 2236 __parent_pointer __parent; 2237 __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_)); 2238 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 2239 return iterator(__nd); 2240} 2241 2242template <class _Tp, class _Compare, class _Allocator> 2243typename __tree<_Tp, _Compare, _Allocator>::iterator 2244__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT 2245{ 2246 iterator __r(__ptr); 2247 ++__r; 2248 if (__begin_node() == __ptr) 2249 __begin_node() = __r.__ptr_; 2250 --size(); 2251 _VSTD::__tree_remove(__end_node()->__left_, 2252 static_cast<__node_base_pointer>(__ptr)); 2253 return __r; 2254} 2255 2256#if _LIBCPP_STD_VER > 14 2257template <class _Tp, class _Compare, class _Allocator> 2258template <class _NodeHandle, class _InsertReturnType> 2259_LIBCPP_INLINE_VISIBILITY 2260_InsertReturnType 2261__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( 2262 _NodeHandle&& __nh) 2263{ 2264 if (__nh.empty()) 2265 return _InsertReturnType{end(), false, _NodeHandle()}; 2266 2267 __node_pointer __ptr = __nh.__ptr_; 2268 __parent_pointer __parent; 2269 __node_base_pointer& __child = __find_equal(__parent, 2270 __ptr->__value_); 2271 if (__child != nullptr) 2272 return _InsertReturnType{ 2273 iterator(static_cast<__node_pointer>(__child)), 2274 false, _VSTD::move(__nh)}; 2275 2276 __insert_node_at(__parent, __child, 2277 static_cast<__node_base_pointer>(__ptr)); 2278 __nh.__release_ptr(); 2279 return _InsertReturnType{iterator(__ptr), true, _NodeHandle()}; 2280} 2281 2282template <class _Tp, class _Compare, class _Allocator> 2283template <class _NodeHandle> 2284_LIBCPP_INLINE_VISIBILITY 2285typename __tree<_Tp, _Compare, _Allocator>::iterator 2286__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( 2287 const_iterator __hint, _NodeHandle&& __nh) 2288{ 2289 if (__nh.empty()) 2290 return end(); 2291 2292 __node_pointer __ptr = __nh.__ptr_; 2293 __parent_pointer __parent; 2294 __node_base_pointer __dummy; 2295 __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, 2296 __ptr->__value_); 2297 __node_pointer __r = static_cast<__node_pointer>(__child); 2298 if (__child == nullptr) 2299 { 2300 __insert_node_at(__parent, __child, 2301 static_cast<__node_base_pointer>(__ptr)); 2302 __r = __ptr; 2303 __nh.__release_ptr(); 2304 } 2305 return iterator(__r); 2306} 2307 2308template <class _Tp, class _Compare, class _Allocator> 2309template <class _NodeHandle> 2310_LIBCPP_INLINE_VISIBILITY 2311_NodeHandle 2312__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) 2313{ 2314 iterator __it = find(__key); 2315 if (__it == end()) 2316 return _NodeHandle(); 2317 return __node_handle_extract<_NodeHandle>(__it); 2318} 2319 2320template <class _Tp, class _Compare, class _Allocator> 2321template <class _NodeHandle> 2322_LIBCPP_INLINE_VISIBILITY 2323_NodeHandle 2324__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) 2325{ 2326 __node_pointer __np = __p.__get_np(); 2327 __remove_node_pointer(__np); 2328 return _NodeHandle(__np, __alloc()); 2329} 2330 2331template <class _Tp, class _Compare, class _Allocator> 2332template <class _Tree> 2333_LIBCPP_INLINE_VISIBILITY 2334void 2335__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) 2336{ 2337 static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); 2338 2339 for (typename _Tree::iterator __i = __source.begin(); 2340 __i != __source.end();) 2341 { 2342 __node_pointer __src_ptr = __i.__get_np(); 2343 __parent_pointer __parent; 2344 __node_base_pointer& __child = 2345 __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); 2346 ++__i; 2347 if (__child != nullptr) 2348 continue; 2349 __source.__remove_node_pointer(__src_ptr); 2350 __insert_node_at(__parent, __child, 2351 static_cast<__node_base_pointer>(__src_ptr)); 2352 } 2353} 2354 2355template <class _Tp, class _Compare, class _Allocator> 2356template <class _NodeHandle> 2357_LIBCPP_INLINE_VISIBILITY 2358typename __tree<_Tp, _Compare, _Allocator>::iterator 2359__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) 2360{ 2361 if (__nh.empty()) 2362 return end(); 2363 __node_pointer __ptr = __nh.__ptr_; 2364 __parent_pointer __parent; 2365 __node_base_pointer& __child = __find_leaf_high( 2366 __parent, _NodeTypes::__get_key(__ptr->__value_)); 2367 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 2368 __nh.__release_ptr(); 2369 return iterator(__ptr); 2370} 2371 2372template <class _Tp, class _Compare, class _Allocator> 2373template <class _NodeHandle> 2374_LIBCPP_INLINE_VISIBILITY 2375typename __tree<_Tp, _Compare, _Allocator>::iterator 2376__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi( 2377 const_iterator __hint, _NodeHandle&& __nh) 2378{ 2379 if (__nh.empty()) 2380 return end(); 2381 2382 __node_pointer __ptr = __nh.__ptr_; 2383 __parent_pointer __parent; 2384 __node_base_pointer& __child = __find_leaf(__hint, __parent, 2385 _NodeTypes::__get_key(__ptr->__value_)); 2386 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 2387 __nh.__release_ptr(); 2388 return iterator(__ptr); 2389} 2390 2391template <class _Tp, class _Compare, class _Allocator> 2392template <class _Tree> 2393_LIBCPP_INLINE_VISIBILITY 2394void 2395__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) 2396{ 2397 static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); 2398 2399 for (typename _Tree::iterator __i = __source.begin(); 2400 __i != __source.end();) 2401 { 2402 __node_pointer __src_ptr = __i.__get_np(); 2403 __parent_pointer __parent; 2404 __node_base_pointer& __child = __find_leaf_high( 2405 __parent, _NodeTypes::__get_key(__src_ptr->__value_)); 2406 ++__i; 2407 __source.__remove_node_pointer(__src_ptr); 2408 __insert_node_at(__parent, __child, 2409 static_cast<__node_base_pointer>(__src_ptr)); 2410 } 2411} 2412 2413#endif // _LIBCPP_STD_VER > 14 2414 2415template <class _Tp, class _Compare, class _Allocator> 2416typename __tree<_Tp, _Compare, _Allocator>::iterator 2417__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) 2418{ 2419 __node_pointer __np = __p.__get_np(); 2420 iterator __r = __remove_node_pointer(__np); 2421 __node_allocator& __na = __node_alloc(); 2422 __node_traits::destroy(__na, _NodeTypes::__get_ptr( 2423 const_cast<__node_value_type&>(*__p))); 2424 __node_traits::deallocate(__na, __np, 1); 2425 return __r; 2426} 2427 2428template <class _Tp, class _Compare, class _Allocator> 2429typename __tree<_Tp, _Compare, _Allocator>::iterator 2430__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) 2431{ 2432 while (__f != __l) 2433 __f = erase(__f); 2434 return iterator(__l.__ptr_); 2435} 2436 2437template <class _Tp, class _Compare, class _Allocator> 2438template <class _Key> 2439typename __tree<_Tp, _Compare, _Allocator>::size_type 2440__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) 2441{ 2442 iterator __i = find(__k); 2443 if (__i == end()) 2444 return 0; 2445 erase(__i); 2446 return 1; 2447} 2448 2449template <class _Tp, class _Compare, class _Allocator> 2450template <class _Key> 2451typename __tree<_Tp, _Compare, _Allocator>::size_type 2452__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) 2453{ 2454 pair<iterator, iterator> __p = __equal_range_multi(__k); 2455 size_type __r = 0; 2456 for (; __p.first != __p.second; ++__r) 2457 __p.first = erase(__p.first); 2458 return __r; 2459} 2460 2461template <class _Tp, class _Compare, class _Allocator> 2462template <class _Key> 2463typename __tree<_Tp, _Compare, _Allocator>::iterator 2464__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) 2465{ 2466 iterator __p = __lower_bound(__v, __root(), __end_node()); 2467 if (__p != end() && !value_comp()(__v, *__p)) 2468 return __p; 2469 return end(); 2470} 2471 2472template <class _Tp, class _Compare, class _Allocator> 2473template <class _Key> 2474typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2475__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const 2476{ 2477 const_iterator __p = __lower_bound(__v, __root(), __end_node()); 2478 if (__p != end() && !value_comp()(__v, *__p)) 2479 return __p; 2480 return end(); 2481} 2482 2483template <class _Tp, class _Compare, class _Allocator> 2484template <class _Key> 2485typename __tree<_Tp, _Compare, _Allocator>::size_type 2486__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const 2487{ 2488 __node_pointer __rt = __root(); 2489 while (__rt != nullptr) 2490 { 2491 if (value_comp()(__k, __rt->__value_)) 2492 { 2493 __rt = static_cast<__node_pointer>(__rt->__left_); 2494 } 2495 else if (value_comp()(__rt->__value_, __k)) 2496 __rt = static_cast<__node_pointer>(__rt->__right_); 2497 else 2498 return 1; 2499 } 2500 return 0; 2501} 2502 2503template <class _Tp, class _Compare, class _Allocator> 2504template <class _Key> 2505typename __tree<_Tp, _Compare, _Allocator>::size_type 2506__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const 2507{ 2508 __iter_pointer __result = __end_node(); 2509 __node_pointer __rt = __root(); 2510 while (__rt != nullptr) 2511 { 2512 if (value_comp()(__k, __rt->__value_)) 2513 { 2514 __result = static_cast<__iter_pointer>(__rt); 2515 __rt = static_cast<__node_pointer>(__rt->__left_); 2516 } 2517 else if (value_comp()(__rt->__value_, __k)) 2518 __rt = static_cast<__node_pointer>(__rt->__right_); 2519 else 2520 return _VSTD::distance( 2521 __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 2522 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result) 2523 ); 2524 } 2525 return 0; 2526} 2527 2528template <class _Tp, class _Compare, class _Allocator> 2529template <class _Key> 2530typename __tree<_Tp, _Compare, _Allocator>::iterator 2531__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2532 __node_pointer __root, 2533 __iter_pointer __result) 2534{ 2535 while (__root != nullptr) 2536 { 2537 if (!value_comp()(__root->__value_, __v)) 2538 { 2539 __result = static_cast<__iter_pointer>(__root); 2540 __root = static_cast<__node_pointer>(__root->__left_); 2541 } 2542 else 2543 __root = static_cast<__node_pointer>(__root->__right_); 2544 } 2545 return iterator(__result); 2546} 2547 2548template <class _Tp, class _Compare, class _Allocator> 2549template <class _Key> 2550typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2551__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2552 __node_pointer __root, 2553 __iter_pointer __result) const 2554{ 2555 while (__root != nullptr) 2556 { 2557 if (!value_comp()(__root->__value_, __v)) 2558 { 2559 __result = static_cast<__iter_pointer>(__root); 2560 __root = static_cast<__node_pointer>(__root->__left_); 2561 } 2562 else 2563 __root = static_cast<__node_pointer>(__root->__right_); 2564 } 2565 return const_iterator(__result); 2566} 2567 2568template <class _Tp, class _Compare, class _Allocator> 2569template <class _Key> 2570typename __tree<_Tp, _Compare, _Allocator>::iterator 2571__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2572 __node_pointer __root, 2573 __iter_pointer __result) 2574{ 2575 while (__root != nullptr) 2576 { 2577 if (value_comp()(__v, __root->__value_)) 2578 { 2579 __result = static_cast<__iter_pointer>(__root); 2580 __root = static_cast<__node_pointer>(__root->__left_); 2581 } 2582 else 2583 __root = static_cast<__node_pointer>(__root->__right_); 2584 } 2585 return iterator(__result); 2586} 2587 2588template <class _Tp, class _Compare, class _Allocator> 2589template <class _Key> 2590typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2591__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2592 __node_pointer __root, 2593 __iter_pointer __result) const 2594{ 2595 while (__root != nullptr) 2596 { 2597 if (value_comp()(__v, __root->__value_)) 2598 { 2599 __result = static_cast<__iter_pointer>(__root); 2600 __root = static_cast<__node_pointer>(__root->__left_); 2601 } 2602 else 2603 __root = static_cast<__node_pointer>(__root->__right_); 2604 } 2605 return const_iterator(__result); 2606} 2607 2608template <class _Tp, class _Compare, class _Allocator> 2609template <class _Key> 2610pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2611 typename __tree<_Tp, _Compare, _Allocator>::iterator> 2612__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 2613{ 2614 typedef pair<iterator, iterator> _Pp; 2615 __iter_pointer __result = __end_node(); 2616 __node_pointer __rt = __root(); 2617 while (__rt != nullptr) 2618 { 2619 if (value_comp()(__k, __rt->__value_)) 2620 { 2621 __result = static_cast<__iter_pointer>(__rt); 2622 __rt = static_cast<__node_pointer>(__rt->__left_); 2623 } 2624 else if (value_comp()(__rt->__value_, __k)) 2625 __rt = static_cast<__node_pointer>(__rt->__right_); 2626 else 2627 return _Pp(iterator(__rt), 2628 iterator( 2629 __rt->__right_ != nullptr ? 2630 static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_)) 2631 : __result)); 2632 } 2633 return _Pp(iterator(__result), iterator(__result)); 2634} 2635 2636template <class _Tp, class _Compare, class _Allocator> 2637template <class _Key> 2638pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2639 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2640__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 2641{ 2642 typedef pair<const_iterator, const_iterator> _Pp; 2643 __iter_pointer __result = __end_node(); 2644 __node_pointer __rt = __root(); 2645 while (__rt != nullptr) 2646 { 2647 if (value_comp()(__k, __rt->__value_)) 2648 { 2649 __result = static_cast<__iter_pointer>(__rt); 2650 __rt = static_cast<__node_pointer>(__rt->__left_); 2651 } 2652 else if (value_comp()(__rt->__value_, __k)) 2653 __rt = static_cast<__node_pointer>(__rt->__right_); 2654 else 2655 return _Pp(const_iterator(__rt), 2656 const_iterator( 2657 __rt->__right_ != nullptr ? 2658 static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_)) 2659 : __result)); 2660 } 2661 return _Pp(const_iterator(__result), const_iterator(__result)); 2662} 2663 2664template <class _Tp, class _Compare, class _Allocator> 2665template <class _Key> 2666pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2667 typename __tree<_Tp, _Compare, _Allocator>::iterator> 2668__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 2669{ 2670 typedef pair<iterator, iterator> _Pp; 2671 __iter_pointer __result = __end_node(); 2672 __node_pointer __rt = __root(); 2673 while (__rt != nullptr) 2674 { 2675 if (value_comp()(__k, __rt->__value_)) 2676 { 2677 __result = static_cast<__iter_pointer>(__rt); 2678 __rt = static_cast<__node_pointer>(__rt->__left_); 2679 } 2680 else if (value_comp()(__rt->__value_, __k)) 2681 __rt = static_cast<__node_pointer>(__rt->__right_); 2682 else 2683 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 2684 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2685 } 2686 return _Pp(iterator(__result), iterator(__result)); 2687} 2688 2689template <class _Tp, class _Compare, class _Allocator> 2690template <class _Key> 2691pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2692 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2693__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 2694{ 2695 typedef pair<const_iterator, const_iterator> _Pp; 2696 __iter_pointer __result = __end_node(); 2697 __node_pointer __rt = __root(); 2698 while (__rt != nullptr) 2699 { 2700 if (value_comp()(__k, __rt->__value_)) 2701 { 2702 __result = static_cast<__iter_pointer>(__rt); 2703 __rt = static_cast<__node_pointer>(__rt->__left_); 2704 } 2705 else if (value_comp()(__rt->__value_, __k)) 2706 __rt = static_cast<__node_pointer>(__rt->__right_); 2707 else 2708 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 2709 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2710 } 2711 return _Pp(const_iterator(__result), const_iterator(__result)); 2712} 2713 2714template <class _Tp, class _Compare, class _Allocator> 2715typename __tree<_Tp, _Compare, _Allocator>::__node_holder 2716__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 2717{ 2718 __node_pointer __np = __p.__get_np(); 2719 if (__begin_node() == __p.__ptr_) 2720 { 2721 if (__np->__right_ != nullptr) 2722 __begin_node() = static_cast<__iter_pointer>(__np->__right_); 2723 else 2724 __begin_node() = static_cast<__iter_pointer>(__np->__parent_); 2725 } 2726 --size(); 2727 _VSTD::__tree_remove(__end_node()->__left_, 2728 static_cast<__node_base_pointer>(__np)); 2729 return __node_holder(__np, _Dp(__node_alloc(), true)); 2730} 2731 2732template <class _Tp, class _Compare, class _Allocator> 2733inline _LIBCPP_INLINE_VISIBILITY 2734void 2735swap(__tree<_Tp, _Compare, _Allocator>& __x, 2736 __tree<_Tp, _Compare, _Allocator>& __y) 2737 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2738{ 2739 __x.swap(__y); 2740} 2741 2742_LIBCPP_END_NAMESPACE_STD 2743 2744_LIBCPP_POP_MACROS 2745 2746#endif // _LIBCPP___TREE 2747