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