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