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, bool __val = false) _NOEXCEPT 526 : __na_(__na), 527 __value_constructed(__val) 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 626 __node_pointer __ptr_; 627 628 typedef pointer_traits<__node_pointer> __pointer_traits; 629 public: 630 typedef bidirectional_iterator_tag iterator_category; 631 typedef _Tp value_type; 632 typedef _DiffType difference_type; 633 typedef value_type& reference; 634 typedef typename pointer_traits<__node_pointer>::template 635 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 636 rebind<value_type> 637 #else 638 rebind<value_type>::other 639 #endif 640 pointer; 641 642 _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT 643 #if _LIBCPP_STD_VER > 11 644 : __ptr_(nullptr) 645 #endif 646 {} 647 648 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 649 _LIBCPP_INLINE_VISIBILITY pointer operator->() const 650 {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 651 652 _LIBCPP_INLINE_VISIBILITY 653 __tree_iterator& operator++() { 654 __ptr_ = static_cast<__node_pointer>( 655 __tree_next(static_cast<typename __node::base::pointer>(__ptr_))); 656 return *this; 657 } 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>( 665 __tree_prev(static_cast<typename __node::base::pointer>(__ptr_))); 666 return *this; 667 } 668 _LIBCPP_INLINE_VISIBILITY 669 __tree_iterator operator--(int) 670 {__tree_iterator __t(*this); --(*this); return __t;} 671 672 friend _LIBCPP_INLINE_VISIBILITY 673 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 674 {return __x.__ptr_ == __y.__ptr_;} 675 friend _LIBCPP_INLINE_VISIBILITY 676 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 677 {return !(__x == __y);} 678 679 private: 680 _LIBCPP_INLINE_VISIBILITY 681 explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 682 template <class, class, class> friend class __tree; 683 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator; 684 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator; 685 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 686 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 687 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set; 688 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset; 689 }; 690 691 template <class _Tp, class _ConstNodePtr, class _DiffType> 692 class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator 693 { 694 typedef _ConstNodePtr __node_pointer; 695 typedef typename pointer_traits<__node_pointer>::element_type __node; 696 697 __node_pointer __ptr_; 698 699 typedef pointer_traits<__node_pointer> __pointer_traits; 700 public: 701 typedef bidirectional_iterator_tag iterator_category; 702 typedef _Tp value_type; 703 typedef _DiffType difference_type; 704 typedef const value_type& reference; 705 typedef typename pointer_traits<__node_pointer>::template 706 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 707 rebind<const value_type> 708 #else 709 rebind<const value_type>::other 710 #endif 711 pointer; 712 713 _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT 714 #if _LIBCPP_STD_VER > 11 715 : __ptr_(nullptr) 716 #endif 717 {} 718 719 private: 720 typedef typename remove_const<__node>::type __non_const_node; 721 typedef typename pointer_traits<__node_pointer>::template 722 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 723 rebind<__non_const_node> 724 #else 725 rebind<__non_const_node>::other 726 #endif 727 __non_const_node_pointer; 728 typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> 729 __non_const_iterator; 730 public: 731 _LIBCPP_INLINE_VISIBILITY 732 __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 733 : __ptr_(__p.__ptr_) {} 734 735 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 736 _LIBCPP_INLINE_VISIBILITY pointer operator->() const 737 {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 738 739 _LIBCPP_INLINE_VISIBILITY 740 __tree_const_iterator& operator++() { 741 typedef typename pointer_traits<__node_pointer>::template 742 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 743 rebind<typename __node::base> 744 #else 745 rebind<typename __node::base>::other 746 #endif 747 __node_base_pointer; 748 749 __ptr_ = static_cast<__node_pointer>( 750 __tree_next(static_cast<__node_base_pointer>(__ptr_))); 751 return *this; 752 } 753 754 _LIBCPP_INLINE_VISIBILITY 755 __tree_const_iterator operator++(int) 756 {__tree_const_iterator __t(*this); ++(*this); return __t;} 757 758 _LIBCPP_INLINE_VISIBILITY 759 __tree_const_iterator& operator--() { 760 typedef typename pointer_traits<__node_pointer>::template 761 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 762 rebind<typename __node::base> 763 #else 764 rebind<typename __node::base>::other 765 #endif 766 __node_base_pointer; 767 768 __ptr_ = static_cast<__node_pointer>( 769 __tree_prev(static_cast<__node_base_pointer>(__ptr_))); 770 return *this; 771 } 772 773 _LIBCPP_INLINE_VISIBILITY 774 __tree_const_iterator operator--(int) 775 {__tree_const_iterator __t(*this); --(*this); return __t;} 776 777 friend _LIBCPP_INLINE_VISIBILITY 778 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 779 {return __x.__ptr_ == __y.__ptr_;} 780 friend _LIBCPP_INLINE_VISIBILITY 781 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 782 {return !(__x == __y);} 783 784 private: 785 _LIBCPP_INLINE_VISIBILITY 786 explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 787 : __ptr_(__p) {} 788 template <class, class, class> friend class __tree; 789 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 790 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 791 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set; 792 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset; 793 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; 794 }; 795 796 template <class _Tp, class _Compare, class _Allocator> 797 class __tree 798 { 799 public: 800 typedef _Tp value_type; 801 typedef _Compare value_compare; 802 typedef _Allocator allocator_type; 803 typedef allocator_traits<allocator_type> __alloc_traits; 804 typedef typename __alloc_traits::pointer pointer; 805 typedef typename __alloc_traits::const_pointer const_pointer; 806 typedef typename __alloc_traits::size_type size_type; 807 typedef typename __alloc_traits::difference_type difference_type; 808 809 typedef typename __alloc_traits::void_pointer __void_pointer; 810 811 typedef __tree_node<value_type, __void_pointer> __node; 812 typedef __tree_node_base<__void_pointer> __node_base; 813 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 814 typedef allocator_traits<__node_allocator> __node_traits; 815 typedef typename __node_traits::pointer __node_pointer; 816 typedef typename __node_traits::pointer __node_const_pointer; 817 typedef typename __node_base::pointer __node_base_pointer; 818 typedef typename __node_base::pointer __node_base_const_pointer; 819 private: 820 typedef typename __node_base::base __end_node_t; 821 typedef typename pointer_traits<__node_pointer>::template 822 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 823 rebind<__end_node_t> 824 #else 825 rebind<__end_node_t>::other 826 #endif 827 __end_node_ptr; 828 typedef typename pointer_traits<__node_pointer>::template 829 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 830 rebind<__end_node_t> 831 #else 832 rebind<__end_node_t>::other 833 #endif 834 __end_node_const_ptr; 835 836 __node_pointer __begin_node_; 837 __compressed_pair<__end_node_t, __node_allocator> __pair1_; 838 __compressed_pair<size_type, value_compare> __pair3_; 839 840 public: 841 _LIBCPP_INLINE_VISIBILITY 842 __node_pointer __end_node() _NOEXCEPT 843 { 844 return static_cast<__node_pointer> 845 ( 846 pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 847 ); 848 } 849 _LIBCPP_INLINE_VISIBILITY 850 __node_const_pointer __end_node() const _NOEXCEPT 851 { 852 return static_cast<__node_const_pointer> 853 ( 854 pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first())) 855 ); 856 } 857 _LIBCPP_INLINE_VISIBILITY 858 __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 859 private: 860 _LIBCPP_INLINE_VISIBILITY 861 const __node_allocator& __node_alloc() const _NOEXCEPT 862 {return __pair1_.second();} 863 _LIBCPP_INLINE_VISIBILITY 864 __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 865 _LIBCPP_INLINE_VISIBILITY 866 const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 867 public: 868 _LIBCPP_INLINE_VISIBILITY 869 allocator_type __alloc() const _NOEXCEPT 870 {return allocator_type(__node_alloc());} 871 private: 872 _LIBCPP_INLINE_VISIBILITY 873 size_type& size() _NOEXCEPT {return __pair3_.first();} 874 public: 875 _LIBCPP_INLINE_VISIBILITY 876 const size_type& size() const _NOEXCEPT {return __pair3_.first();} 877 _LIBCPP_INLINE_VISIBILITY 878 value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 879 _LIBCPP_INLINE_VISIBILITY 880 const value_compare& value_comp() const _NOEXCEPT 881 {return __pair3_.second();} 882 public: 883 _LIBCPP_INLINE_VISIBILITY 884 __node_pointer __root() _NOEXCEPT 885 {return static_cast<__node_pointer> (__end_node()->__left_);} 886 _LIBCPP_INLINE_VISIBILITY 887 __node_const_pointer __root() const _NOEXCEPT 888 {return static_cast<__node_const_pointer>(__end_node()->__left_);} 889 890 typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 891 typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 892 893 explicit __tree(const value_compare& __comp) 894 _NOEXCEPT_( 895 is_nothrow_default_constructible<__node_allocator>::value && 896 is_nothrow_copy_constructible<value_compare>::value); 897 explicit __tree(const allocator_type& __a); 898 __tree(const value_compare& __comp, const allocator_type& __a); 899 __tree(const __tree& __t); 900 __tree& operator=(const __tree& __t); 901 template <class _InputIterator> 902 void __assign_unique(_InputIterator __first, _InputIterator __last); 903 template <class _InputIterator> 904 void __assign_multi(_InputIterator __first, _InputIterator __last); 905 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 906 __tree(__tree&& __t) 907 _NOEXCEPT_( 908 is_nothrow_move_constructible<__node_allocator>::value && 909 is_nothrow_move_constructible<value_compare>::value); 910 __tree(__tree&& __t, const allocator_type& __a); 911 __tree& operator=(__tree&& __t) 912 _NOEXCEPT_( 913 __node_traits::propagate_on_container_move_assignment::value && 914 is_nothrow_move_assignable<value_compare>::value && 915 is_nothrow_move_assignable<__node_allocator>::value); 916 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 917 918 ~__tree(); 919 920 _LIBCPP_INLINE_VISIBILITY 921 iterator begin() _NOEXCEPT {return iterator(__begin_node());} 922 _LIBCPP_INLINE_VISIBILITY 923 const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 924 _LIBCPP_INLINE_VISIBILITY 925 iterator end() _NOEXCEPT {return iterator(__end_node());} 926 _LIBCPP_INLINE_VISIBILITY 927 const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 928 929 _LIBCPP_INLINE_VISIBILITY 930 size_type max_size() const _NOEXCEPT 931 {return __node_traits::max_size(__node_alloc());} 932 933 void clear() _NOEXCEPT; 934 935 void swap(__tree& __t) 936 _NOEXCEPT_( 937 __is_nothrow_swappable<value_compare>::value 938 #if _LIBCPP_STD_VER <= 11 939 && (!__node_traits::propagate_on_container_swap::value || 940 __is_nothrow_swappable<__node_allocator>::value) 941 #endif 942 ); 943 944 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 945 #ifndef _LIBCPP_HAS_NO_VARIADICS 946 template <class... _Args> 947 pair<iterator, bool> 948 __emplace_unique(_Args&&... __args); 949 template <class... _Args> 950 iterator 951 __emplace_multi(_Args&&... __args); 952 953 template <class... _Args> 954 iterator 955 __emplace_hint_unique(const_iterator __p, _Args&&... __args); 956 template <class... _Args> 957 iterator 958 __emplace_hint_multi(const_iterator __p, _Args&&... __args); 959 #endif // _LIBCPP_HAS_NO_VARIADICS 960 961 template <class _Vp> 962 pair<iterator, bool> __insert_unique(_Vp&& __v); 963 template <class _Vp> 964 iterator __insert_unique(const_iterator __p, _Vp&& __v); 965 template <class _Vp> 966 iterator __insert_multi(_Vp&& __v); 967 template <class _Vp> 968 iterator __insert_multi(const_iterator __p, _Vp&& __v); 969 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 970 971 pair<iterator, bool> __insert_unique(const value_type& __v); 972 iterator __insert_unique(const_iterator __p, const value_type& __v); 973 iterator __insert_multi(const value_type& __v); 974 iterator __insert_multi(const_iterator __p, const value_type& __v); 975 976 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 977 iterator __node_insert_unique(const_iterator __p, 978 __node_pointer __nd); 979 980 iterator __node_insert_multi(__node_pointer __nd); 981 iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 982 983 iterator erase(const_iterator __p); 984 iterator erase(const_iterator __f, const_iterator __l); 985 template <class _Key> 986 size_type __erase_unique(const _Key& __k); 987 template <class _Key> 988 size_type __erase_multi(const _Key& __k); 989 990 void __insert_node_at(__node_base_pointer __parent, 991 __node_base_pointer& __child, 992 __node_base_pointer __new_node); 993 994 template <class _Key> 995 iterator find(const _Key& __v); 996 template <class _Key> 997 const_iterator find(const _Key& __v) const; 998 999 template <class _Key> 1000 size_type __count_unique(const _Key& __k) const; 1001 template <class _Key> 1002 size_type __count_multi(const _Key& __k) const; 1003 1004 template <class _Key> 1005 _LIBCPP_INLINE_VISIBILITY 1006 iterator lower_bound(const _Key& __v) 1007 {return __lower_bound(__v, __root(), __end_node());} 1008 template <class _Key> 1009 iterator __lower_bound(const _Key& __v, 1010 __node_pointer __root, 1011 __node_pointer __result); 1012 template <class _Key> 1013 _LIBCPP_INLINE_VISIBILITY 1014 const_iterator lower_bound(const _Key& __v) const 1015 {return __lower_bound(__v, __root(), __end_node());} 1016 template <class _Key> 1017 const_iterator __lower_bound(const _Key& __v, 1018 __node_const_pointer __root, 1019 __node_const_pointer __result) const; 1020 template <class _Key> 1021 _LIBCPP_INLINE_VISIBILITY 1022 iterator upper_bound(const _Key& __v) 1023 {return __upper_bound(__v, __root(), __end_node());} 1024 template <class _Key> 1025 iterator __upper_bound(const _Key& __v, 1026 __node_pointer __root, 1027 __node_pointer __result); 1028 template <class _Key> 1029 _LIBCPP_INLINE_VISIBILITY 1030 const_iterator upper_bound(const _Key& __v) const 1031 {return __upper_bound(__v, __root(), __end_node());} 1032 template <class _Key> 1033 const_iterator __upper_bound(const _Key& __v, 1034 __node_const_pointer __root, 1035 __node_const_pointer __result) const; 1036 template <class _Key> 1037 pair<iterator, iterator> 1038 __equal_range_unique(const _Key& __k); 1039 template <class _Key> 1040 pair<const_iterator, const_iterator> 1041 __equal_range_unique(const _Key& __k) const; 1042 1043 template <class _Key> 1044 pair<iterator, iterator> 1045 __equal_range_multi(const _Key& __k); 1046 template <class _Key> 1047 pair<const_iterator, const_iterator> 1048 __equal_range_multi(const _Key& __k) const; 1049 1050 typedef __tree_node_destructor<__node_allocator> _Dp; 1051 typedef unique_ptr<__node, _Dp> __node_holder; 1052 1053 __node_holder remove(const_iterator __p) _NOEXCEPT; 1054 private: 1055 typename __node_base::pointer& 1056 __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v); 1057 typename __node_base::pointer& 1058 __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v); 1059 typename __node_base::pointer& 1060 __find_leaf(const_iterator __hint, 1061 typename __node_base::pointer& __parent, const value_type& __v); 1062 template <class _Key> 1063 typename __node_base::pointer& 1064 __find_equal(typename __node_base::pointer& __parent, const _Key& __v); 1065 template <class _Key> 1066 typename __node_base::pointer& 1067 __find_equal(const_iterator __hint, typename __node_base::pointer& __parent, 1068 const _Key& __v); 1069 1070 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1071 template <class ..._Args> 1072 __node_holder __construct_node(_Args&& ...__args); 1073 #else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1074 __node_holder __construct_node(const value_type& __v); 1075 #endif 1076 1077 void destroy(__node_pointer __nd) _NOEXCEPT; 1078 1079 _LIBCPP_INLINE_VISIBILITY 1080 void __copy_assign_alloc(const __tree& __t) 1081 {__copy_assign_alloc(__t, integral_constant<bool, 1082 __node_traits::propagate_on_container_copy_assignment::value>());} 1083 1084 _LIBCPP_INLINE_VISIBILITY 1085 void __copy_assign_alloc(const __tree& __t, true_type) 1086 {__node_alloc() = __t.__node_alloc();} 1087 _LIBCPP_INLINE_VISIBILITY 1088 void __copy_assign_alloc(const __tree& __t, false_type) {} 1089 1090 void __move_assign(__tree& __t, false_type); 1091 void __move_assign(__tree& __t, true_type) 1092 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1093 is_nothrow_move_assignable<__node_allocator>::value); 1094 1095 _LIBCPP_INLINE_VISIBILITY 1096 void __move_assign_alloc(__tree& __t) 1097 _NOEXCEPT_( 1098 !__node_traits::propagate_on_container_move_assignment::value || 1099 is_nothrow_move_assignable<__node_allocator>::value) 1100 {__move_assign_alloc(__t, integral_constant<bool, 1101 __node_traits::propagate_on_container_move_assignment::value>());} 1102 1103 _LIBCPP_INLINE_VISIBILITY 1104 void __move_assign_alloc(__tree& __t, true_type) 1105 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1106 {__node_alloc() = _VSTD::move(__t.__node_alloc());} 1107 _LIBCPP_INLINE_VISIBILITY 1108 void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {} 1109 1110 __node_pointer __detach(); 1111 static __node_pointer __detach(__node_pointer); 1112 1113 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 1114 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 1115 }; 1116 1117 template <class _Tp, class _Compare, class _Allocator> 1118 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 1119 _NOEXCEPT_( 1120 is_nothrow_default_constructible<__node_allocator>::value && 1121 is_nothrow_copy_constructible<value_compare>::value) 1122 : __pair3_(0, __comp) 1123 { 1124 __begin_node() = __end_node(); 1125 } 1126 1127 template <class _Tp, class _Compare, class _Allocator> 1128 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1129 : __begin_node_(__node_pointer()), 1130 __pair1_(__node_allocator(__a)), 1131 __pair3_(0) 1132 { 1133 __begin_node() = __end_node(); 1134 } 1135 1136 template <class _Tp, class _Compare, class _Allocator> 1137 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 1138 const allocator_type& __a) 1139 : __begin_node_(__node_pointer()), 1140 __pair1_(__node_allocator(__a)), 1141 __pair3_(0, __comp) 1142 { 1143 __begin_node() = __end_node(); 1144 } 1145 1146 // Precondition: size() != 0 1147 template <class _Tp, class _Compare, class _Allocator> 1148 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1149 __tree<_Tp, _Compare, _Allocator>::__detach() 1150 { 1151 __node_pointer __cache = __begin_node(); 1152 __begin_node() = __end_node(); 1153 __end_node()->__left_->__parent_ = nullptr; 1154 __end_node()->__left_ = nullptr; 1155 size() = 0; 1156 // __cache->__left_ == nullptr 1157 if (__cache->__right_ != nullptr) 1158 __cache = static_cast<__node_pointer>(__cache->__right_); 1159 // __cache->__left_ == nullptr 1160 // __cache->__right_ == nullptr 1161 return __cache; 1162 } 1163 1164 // Precondition: __cache != nullptr 1165 // __cache->left_ == nullptr 1166 // __cache->right_ == nullptr 1167 // This is no longer a red-black tree 1168 template <class _Tp, class _Compare, class _Allocator> 1169 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1170 __tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache) 1171 { 1172 if (__cache->__parent_ == nullptr) 1173 return nullptr; 1174 if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 1175 { 1176 __cache->__parent_->__left_ = nullptr; 1177 __cache = static_cast<__node_pointer>(__cache->__parent_); 1178 if (__cache->__right_ == nullptr) 1179 return __cache; 1180 return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); 1181 } 1182 // __cache is right child 1183 __cache->__parent_->__right_ = nullptr; 1184 __cache = static_cast<__node_pointer>(__cache->__parent_); 1185 if (__cache->__left_ == nullptr) 1186 return __cache; 1187 return static_cast<__node_pointer>(__tree_leaf(__cache->__left_)); 1188 } 1189 1190 template <class _Tp, class _Compare, class _Allocator> 1191 __tree<_Tp, _Compare, _Allocator>& 1192 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 1193 { 1194 if (this != &__t) 1195 { 1196 value_comp() = __t.value_comp(); 1197 __copy_assign_alloc(__t); 1198 __assign_multi(__t.begin(), __t.end()); 1199 } 1200 return *this; 1201 } 1202 1203 template <class _Tp, class _Compare, class _Allocator> 1204 template <class _InputIterator> 1205 void 1206 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last) 1207 { 1208 if (size() != 0) 1209 { 1210 __node_pointer __cache = __detach(); 1211 #ifndef _LIBCPP_NO_EXCEPTIONS 1212 try 1213 { 1214 #endif // _LIBCPP_NO_EXCEPTIONS 1215 for (; __cache != nullptr && __first != __last; ++__first) 1216 { 1217 __cache->__value_ = *__first; 1218 __node_pointer __next = __detach(__cache); 1219 __node_insert_unique(__cache); 1220 __cache = __next; 1221 } 1222 #ifndef _LIBCPP_NO_EXCEPTIONS 1223 } 1224 catch (...) 1225 { 1226 while (__cache->__parent_ != nullptr) 1227 __cache = static_cast<__node_pointer>(__cache->__parent_); 1228 destroy(__cache); 1229 throw; 1230 } 1231 #endif // _LIBCPP_NO_EXCEPTIONS 1232 if (__cache != nullptr) 1233 { 1234 while (__cache->__parent_ != nullptr) 1235 __cache = static_cast<__node_pointer>(__cache->__parent_); 1236 destroy(__cache); 1237 } 1238 } 1239 for (; __first != __last; ++__first) 1240 __insert_unique(*__first); 1241 } 1242 1243 template <class _Tp, class _Compare, class _Allocator> 1244 template <class _InputIterator> 1245 void 1246 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 1247 { 1248 if (size() != 0) 1249 { 1250 __node_pointer __cache = __detach(); 1251 #ifndef _LIBCPP_NO_EXCEPTIONS 1252 try 1253 { 1254 #endif // _LIBCPP_NO_EXCEPTIONS 1255 for (; __cache != nullptr && __first != __last; ++__first) 1256 { 1257 __cache->__value_ = *__first; 1258 __node_pointer __next = __detach(__cache); 1259 __node_insert_multi(__cache); 1260 __cache = __next; 1261 } 1262 #ifndef _LIBCPP_NO_EXCEPTIONS 1263 } 1264 catch (...) 1265 { 1266 while (__cache->__parent_ != nullptr) 1267 __cache = static_cast<__node_pointer>(__cache->__parent_); 1268 destroy(__cache); 1269 throw; 1270 } 1271 #endif // _LIBCPP_NO_EXCEPTIONS 1272 if (__cache != nullptr) 1273 { 1274 while (__cache->__parent_ != nullptr) 1275 __cache = static_cast<__node_pointer>(__cache->__parent_); 1276 destroy(__cache); 1277 } 1278 } 1279 for (; __first != __last; ++__first) 1280 __insert_multi(*__first); 1281 } 1282 1283 template <class _Tp, class _Compare, class _Allocator> 1284 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1285 : __begin_node_(__node_pointer()), 1286 __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1287 __pair3_(0, __t.value_comp()) 1288 { 1289 __begin_node() = __end_node(); 1290 } 1291 1292 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1293 1294 template <class _Tp, class _Compare, class _Allocator> 1295 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 1296 _NOEXCEPT_( 1297 is_nothrow_move_constructible<__node_allocator>::value && 1298 is_nothrow_move_constructible<value_compare>::value) 1299 : __begin_node_(_VSTD::move(__t.__begin_node_)), 1300 __pair1_(_VSTD::move(__t.__pair1_)), 1301 __pair3_(_VSTD::move(__t.__pair3_)) 1302 { 1303 if (size() == 0) 1304 __begin_node() = __end_node(); 1305 else 1306 { 1307 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1308 __t.__begin_node() = __t.__end_node(); 1309 __t.__end_node()->__left_ = nullptr; 1310 __t.size() = 0; 1311 } 1312 } 1313 1314 template <class _Tp, class _Compare, class _Allocator> 1315 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1316 : __pair1_(__node_allocator(__a)), 1317 __pair3_(0, _VSTD::move(__t.value_comp())) 1318 { 1319 if (__a == __t.__alloc()) 1320 { 1321 if (__t.size() == 0) 1322 __begin_node() = __end_node(); 1323 else 1324 { 1325 __begin_node() = __t.__begin_node(); 1326 __end_node()->__left_ = __t.__end_node()->__left_; 1327 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1328 size() = __t.size(); 1329 __t.__begin_node() = __t.__end_node(); 1330 __t.__end_node()->__left_ = nullptr; 1331 __t.size() = 0; 1332 } 1333 } 1334 else 1335 { 1336 __begin_node() = __end_node(); 1337 } 1338 } 1339 1340 template <class _Tp, class _Compare, class _Allocator> 1341 void 1342 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1343 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1344 is_nothrow_move_assignable<__node_allocator>::value) 1345 { 1346 destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1347 __begin_node_ = __t.__begin_node_; 1348 __pair1_.first() = __t.__pair1_.first(); 1349 __move_assign_alloc(__t); 1350 __pair3_ = _VSTD::move(__t.__pair3_); 1351 if (size() == 0) 1352 __begin_node() = __end_node(); 1353 else 1354 { 1355 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1356 __t.__begin_node() = __t.__end_node(); 1357 __t.__end_node()->__left_ = nullptr; 1358 __t.size() = 0; 1359 } 1360 } 1361 1362 template <class _Tp, class _Compare, class _Allocator> 1363 void 1364 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 1365 { 1366 if (__node_alloc() == __t.__node_alloc()) 1367 __move_assign(__t, true_type()); 1368 else 1369 { 1370 value_comp() = _VSTD::move(__t.value_comp()); 1371 const_iterator __e = end(); 1372 if (size() != 0) 1373 { 1374 __node_pointer __cache = __detach(); 1375 #ifndef _LIBCPP_NO_EXCEPTIONS 1376 try 1377 { 1378 #endif // _LIBCPP_NO_EXCEPTIONS 1379 while (__cache != nullptr && __t.size() != 0) 1380 { 1381 __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 1382 __node_pointer __next = __detach(__cache); 1383 __node_insert_multi(__cache); 1384 __cache = __next; 1385 } 1386 #ifndef _LIBCPP_NO_EXCEPTIONS 1387 } 1388 catch (...) 1389 { 1390 while (__cache->__parent_ != nullptr) 1391 __cache = static_cast<__node_pointer>(__cache->__parent_); 1392 destroy(__cache); 1393 throw; 1394 } 1395 #endif // _LIBCPP_NO_EXCEPTIONS 1396 if (__cache != nullptr) 1397 { 1398 while (__cache->__parent_ != nullptr) 1399 __cache = static_cast<__node_pointer>(__cache->__parent_); 1400 destroy(__cache); 1401 } 1402 } 1403 while (__t.size() != 0) 1404 __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_)); 1405 } 1406 } 1407 1408 template <class _Tp, class _Compare, class _Allocator> 1409 __tree<_Tp, _Compare, _Allocator>& 1410 __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 1411 _NOEXCEPT_( 1412 __node_traits::propagate_on_container_move_assignment::value && 1413 is_nothrow_move_assignable<value_compare>::value && 1414 is_nothrow_move_assignable<__node_allocator>::value) 1415 1416 { 1417 __move_assign(__t, integral_constant<bool, 1418 __node_traits::propagate_on_container_move_assignment::value>()); 1419 return *this; 1420 } 1421 1422 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1423 1424 template <class _Tp, class _Compare, class _Allocator> 1425 __tree<_Tp, _Compare, _Allocator>::~__tree() 1426 { 1427 destroy(__root()); 1428 } 1429 1430 template <class _Tp, class _Compare, class _Allocator> 1431 void 1432 __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 1433 { 1434 if (__nd != nullptr) 1435 { 1436 destroy(static_cast<__node_pointer>(__nd->__left_)); 1437 destroy(static_cast<__node_pointer>(__nd->__right_)); 1438 __node_allocator& __na = __node_alloc(); 1439 __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_)); 1440 __node_traits::deallocate(__na, __nd, 1); 1441 } 1442 } 1443 1444 template <class _Tp, class _Compare, class _Allocator> 1445 void 1446 __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1447 _NOEXCEPT_( 1448 __is_nothrow_swappable<value_compare>::value 1449 #if _LIBCPP_STD_VER <= 11 1450 && (!__node_traits::propagate_on_container_swap::value || 1451 __is_nothrow_swappable<__node_allocator>::value) 1452 #endif 1453 ) 1454 { 1455 using _VSTD::swap; 1456 swap(__begin_node_, __t.__begin_node_); 1457 swap(__pair1_.first(), __t.__pair1_.first()); 1458 __swap_allocator(__node_alloc(), __t.__node_alloc()); 1459 __pair3_.swap(__t.__pair3_); 1460 if (size() == 0) 1461 __begin_node() = __end_node(); 1462 else 1463 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1464 if (__t.size() == 0) 1465 __t.__begin_node() = __t.__end_node(); 1466 else 1467 __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node()); 1468 } 1469 1470 template <class _Tp, class _Compare, class _Allocator> 1471 void 1472 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 1473 { 1474 destroy(__root()); 1475 size() = 0; 1476 __begin_node() = __end_node(); 1477 __end_node()->__left_ = nullptr; 1478 } 1479 1480 // Find lower_bound place to insert 1481 // Set __parent to parent of null leaf 1482 // Return reference to null leaf 1483 template <class _Tp, class _Compare, class _Allocator> 1484 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1485 __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent, 1486 const value_type& __v) 1487 { 1488 __node_pointer __nd = __root(); 1489 if (__nd != nullptr) 1490 { 1491 while (true) 1492 { 1493 if (value_comp()(__nd->__value_, __v)) 1494 { 1495 if (__nd->__right_ != nullptr) 1496 __nd = static_cast<__node_pointer>(__nd->__right_); 1497 else 1498 { 1499 __parent = static_cast<__node_base_pointer>(__nd); 1500 return __parent->__right_; 1501 } 1502 } 1503 else 1504 { 1505 if (__nd->__left_ != nullptr) 1506 __nd = static_cast<__node_pointer>(__nd->__left_); 1507 else 1508 { 1509 __parent = static_cast<__node_base_pointer>(__nd); 1510 return __parent->__left_; 1511 } 1512 } 1513 } 1514 } 1515 __parent = static_cast<__node_base_pointer>(__end_node()); 1516 return __parent->__left_; 1517 } 1518 1519 // Find upper_bound place to insert 1520 // Set __parent to parent of null leaf 1521 // Return reference to null leaf 1522 template <class _Tp, class _Compare, class _Allocator> 1523 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1524 __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent, 1525 const value_type& __v) 1526 { 1527 __node_pointer __nd = __root(); 1528 if (__nd != nullptr) 1529 { 1530 while (true) 1531 { 1532 if (value_comp()(__v, __nd->__value_)) 1533 { 1534 if (__nd->__left_ != nullptr) 1535 __nd = static_cast<__node_pointer>(__nd->__left_); 1536 else 1537 { 1538 __parent = static_cast<__node_base_pointer>(__nd); 1539 return __parent->__left_; 1540 } 1541 } 1542 else 1543 { 1544 if (__nd->__right_ != nullptr) 1545 __nd = static_cast<__node_pointer>(__nd->__right_); 1546 else 1547 { 1548 __parent = static_cast<__node_base_pointer>(__nd); 1549 return __parent->__right_; 1550 } 1551 } 1552 } 1553 } 1554 __parent = static_cast<__node_base_pointer>(__end_node()); 1555 return __parent->__left_; 1556 } 1557 1558 // Find leaf place to insert closest to __hint 1559 // First check prior to __hint. 1560 // Next check after __hint. 1561 // Next do O(log N) search. 1562 // Set __parent to parent of null leaf 1563 // Return reference to null leaf 1564 template <class _Tp, class _Compare, class _Allocator> 1565 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1566 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 1567 typename __node_base::pointer& __parent, 1568 const value_type& __v) 1569 { 1570 if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1571 { 1572 // __v <= *__hint 1573 const_iterator __prior = __hint; 1574 if (__prior == begin() || !value_comp()(__v, *--__prior)) 1575 { 1576 // *prev(__hint) <= __v <= *__hint 1577 if (__hint.__ptr_->__left_ == nullptr) 1578 { 1579 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1580 return __parent->__left_; 1581 } 1582 else 1583 { 1584 __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1585 return __parent->__right_; 1586 } 1587 } 1588 // __v < *prev(__hint) 1589 return __find_leaf_high(__parent, __v); 1590 } 1591 // else __v > *__hint 1592 return __find_leaf_low(__parent, __v); 1593 } 1594 1595 // Find place to insert if __v doesn't exist 1596 // Set __parent to parent of null leaf 1597 // Return reference to null leaf 1598 // If __v exists, set parent to node of __v and return reference to node of __v 1599 template <class _Tp, class _Compare, class _Allocator> 1600 template <class _Key> 1601 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1602 __tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent, 1603 const _Key& __v) 1604 { 1605 __node_pointer __nd = __root(); 1606 if (__nd != nullptr) 1607 { 1608 while (true) 1609 { 1610 if (value_comp()(__v, __nd->__value_)) 1611 { 1612 if (__nd->__left_ != nullptr) 1613 __nd = static_cast<__node_pointer>(__nd->__left_); 1614 else 1615 { 1616 __parent = static_cast<__node_base_pointer>(__nd); 1617 return __parent->__left_; 1618 } 1619 } 1620 else if (value_comp()(__nd->__value_, __v)) 1621 { 1622 if (__nd->__right_ != nullptr) 1623 __nd = static_cast<__node_pointer>(__nd->__right_); 1624 else 1625 { 1626 __parent = static_cast<__node_base_pointer>(__nd); 1627 return __parent->__right_; 1628 } 1629 } 1630 else 1631 { 1632 __parent = static_cast<__node_base_pointer>(__nd); 1633 return __parent; 1634 } 1635 } 1636 } 1637 __parent = static_cast<__node_base_pointer>(__end_node()); 1638 return __parent->__left_; 1639 } 1640 1641 // Find place to insert if __v doesn't exist 1642 // First check prior to __hint. 1643 // Next check after __hint. 1644 // Next do O(log N) search. 1645 // Set __parent to parent of null leaf 1646 // Return reference to null leaf 1647 // If __v exists, set parent to node of __v and return reference to node of __v 1648 template <class _Tp, class _Compare, class _Allocator> 1649 template <class _Key> 1650 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1651 __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, 1652 typename __node_base::pointer& __parent, 1653 const _Key& __v) 1654 { 1655 if (__hint == end() || value_comp()(__v, *__hint)) // check before 1656 { 1657 // __v < *__hint 1658 const_iterator __prior = __hint; 1659 if (__prior == begin() || value_comp()(*--__prior, __v)) 1660 { 1661 // *prev(__hint) < __v < *__hint 1662 if (__hint.__ptr_->__left_ == nullptr) 1663 { 1664 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1665 return __parent->__left_; 1666 } 1667 else 1668 { 1669 __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1670 return __parent->__right_; 1671 } 1672 } 1673 // __v <= *prev(__hint) 1674 return __find_equal(__parent, __v); 1675 } 1676 else if (value_comp()(*__hint, __v)) // check after 1677 { 1678 // *__hint < __v 1679 const_iterator __next = _VSTD::next(__hint); 1680 if (__next == end() || value_comp()(__v, *__next)) 1681 { 1682 // *__hint < __v < *_VSTD::next(__hint) 1683 if (__hint.__ptr_->__right_ == nullptr) 1684 { 1685 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1686 return __parent->__right_; 1687 } 1688 else 1689 { 1690 __parent = static_cast<__node_base_pointer>(__next.__ptr_); 1691 return __parent->__left_; 1692 } 1693 } 1694 // *next(__hint) <= __v 1695 return __find_equal(__parent, __v); 1696 } 1697 // else __v == *__hint 1698 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1699 return __parent; 1700 } 1701 1702 template <class _Tp, class _Compare, class _Allocator> 1703 void 1704 __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent, 1705 __node_base_pointer& __child, 1706 __node_base_pointer __new_node) 1707 { 1708 __new_node->__left_ = nullptr; 1709 __new_node->__right_ = nullptr; 1710 __new_node->__parent_ = __parent; 1711 __child = __new_node; 1712 if (__begin_node()->__left_ != nullptr) 1713 __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_); 1714 __tree_balance_after_insert(__end_node()->__left_, __child); 1715 ++size(); 1716 } 1717 1718 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1719 #ifndef _LIBCPP_HAS_NO_VARIADICS 1720 1721 template <class _Tp, class _Compare, class _Allocator> 1722 template <class ..._Args> 1723 typename __tree<_Tp, _Compare, _Allocator>::__node_holder 1724 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 1725 { 1726 __node_allocator& __na = __node_alloc(); 1727 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1728 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1729 __h.get_deleter().__value_constructed = true; 1730 return __h; 1731 } 1732 1733 template <class _Tp, class _Compare, class _Allocator> 1734 template <class... _Args> 1735 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1736 __tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args) 1737 { 1738 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1739 __node_base_pointer __parent; 1740 __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 1741 __node_pointer __r = static_cast<__node_pointer>(__child); 1742 bool __inserted = false; 1743 if (__child == nullptr) 1744 { 1745 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1746 __r = __h.release(); 1747 __inserted = true; 1748 } 1749 return pair<iterator, bool>(iterator(__r), __inserted); 1750 } 1751 1752 template <class _Tp, class _Compare, class _Allocator> 1753 template <class... _Args> 1754 typename __tree<_Tp, _Compare, _Allocator>::iterator 1755 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args) 1756 { 1757 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1758 __node_base_pointer __parent; 1759 __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_); 1760 __node_pointer __r = static_cast<__node_pointer>(__child); 1761 if (__child == nullptr) 1762 { 1763 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1764 __r = __h.release(); 1765 } 1766 return iterator(__r); 1767 } 1768 1769 template <class _Tp, class _Compare, class _Allocator> 1770 template <class... _Args> 1771 typename __tree<_Tp, _Compare, _Allocator>::iterator 1772 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 1773 { 1774 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1775 __node_base_pointer __parent; 1776 __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1777 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1778 return iterator(static_cast<__node_pointer>(__h.release())); 1779 } 1780 1781 template <class _Tp, class _Compare, class _Allocator> 1782 template <class... _Args> 1783 typename __tree<_Tp, _Compare, _Allocator>::iterator 1784 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 1785 _Args&&... __args) 1786 { 1787 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1788 __node_base_pointer __parent; 1789 __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1790 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1791 return iterator(static_cast<__node_pointer>(__h.release())); 1792 } 1793 1794 #endif // _LIBCPP_HAS_NO_VARIADICS 1795 1796 template <class _Tp, class _Compare, class _Allocator> 1797 template <class _Vp> 1798 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1799 __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) 1800 { 1801 __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1802 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1803 if (__r.second) 1804 __h.release(); 1805 return __r; 1806 } 1807 1808 template <class _Tp, class _Compare, class _Allocator> 1809 template <class _Vp> 1810 typename __tree<_Tp, _Compare, _Allocator>::iterator 1811 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v) 1812 { 1813 __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1814 iterator __r = __node_insert_unique(__p, __h.get()); 1815 if (__r.__ptr_ == __h.get()) 1816 __h.release(); 1817 return __r; 1818 } 1819 1820 template <class _Tp, class _Compare, class _Allocator> 1821 template <class _Vp> 1822 typename __tree<_Tp, _Compare, _Allocator>::iterator 1823 __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) 1824 { 1825 __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1826 __node_base_pointer __parent; 1827 __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1828 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1829 return iterator(__h.release()); 1830 } 1831 1832 template <class _Tp, class _Compare, class _Allocator> 1833 template <class _Vp> 1834 typename __tree<_Tp, _Compare, _Allocator>::iterator 1835 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v) 1836 { 1837 __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1838 __node_base_pointer __parent; 1839 __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1840 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1841 return iterator(__h.release()); 1842 } 1843 1844 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1845 1846 template <class _Tp, class _Compare, class _Allocator> 1847 typename __tree<_Tp, _Compare, _Allocator>::__node_holder 1848 __tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v) 1849 { 1850 __node_allocator& __na = __node_alloc(); 1851 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1852 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1853 __h.get_deleter().__value_constructed = true; 1854 return _VSTD::move(__h); // explicitly moved for C++03 1855 } 1856 1857 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1858 1859 template <class _Tp, class _Compare, class _Allocator> 1860 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1861 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v) 1862 { 1863 __node_base_pointer __parent; 1864 __node_base_pointer& __child = __find_equal(__parent, __v); 1865 __node_pointer __r = static_cast<__node_pointer>(__child); 1866 bool __inserted = false; 1867 if (__child == nullptr) 1868 { 1869 __node_holder __h = __construct_node(__v); 1870 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1871 __r = __h.release(); 1872 __inserted = true; 1873 } 1874 return pair<iterator, bool>(iterator(__r), __inserted); 1875 } 1876 1877 template <class _Tp, class _Compare, class _Allocator> 1878 typename __tree<_Tp, _Compare, _Allocator>::iterator 1879 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v) 1880 { 1881 __node_base_pointer __parent; 1882 __node_base_pointer& __child = __find_equal(__p, __parent, __v); 1883 __node_pointer __r = static_cast<__node_pointer>(__child); 1884 if (__child == nullptr) 1885 { 1886 __node_holder __h = __construct_node(__v); 1887 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1888 __r = __h.release(); 1889 } 1890 return iterator(__r); 1891 } 1892 1893 template <class _Tp, class _Compare, class _Allocator> 1894 typename __tree<_Tp, _Compare, _Allocator>::iterator 1895 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v) 1896 { 1897 __node_base_pointer __parent; 1898 __node_base_pointer& __child = __find_leaf_high(__parent, __v); 1899 __node_holder __h = __construct_node(__v); 1900 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1901 return iterator(__h.release()); 1902 } 1903 1904 template <class _Tp, class _Compare, class _Allocator> 1905 typename __tree<_Tp, _Compare, _Allocator>::iterator 1906 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v) 1907 { 1908 __node_base_pointer __parent; 1909 __node_base_pointer& __child = __find_leaf(__p, __parent, __v); 1910 __node_holder __h = __construct_node(__v); 1911 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1912 return iterator(__h.release()); 1913 } 1914 1915 template <class _Tp, class _Compare, class _Allocator> 1916 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1917 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd) 1918 { 1919 __node_base_pointer __parent; 1920 __node_base_pointer& __child = __find_equal(__parent, __nd->__value_); 1921 __node_pointer __r = static_cast<__node_pointer>(__child); 1922 bool __inserted = false; 1923 if (__child == nullptr) 1924 { 1925 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1926 __r = __nd; 1927 __inserted = true; 1928 } 1929 return pair<iterator, bool>(iterator(__r), __inserted); 1930 } 1931 1932 template <class _Tp, class _Compare, class _Allocator> 1933 typename __tree<_Tp, _Compare, _Allocator>::iterator 1934 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p, 1935 __node_pointer __nd) 1936 { 1937 __node_base_pointer __parent; 1938 __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_); 1939 __node_pointer __r = static_cast<__node_pointer>(__child); 1940 if (__child == nullptr) 1941 { 1942 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1943 __r = __nd; 1944 } 1945 return iterator(__r); 1946 } 1947 1948 template <class _Tp, class _Compare, class _Allocator> 1949 typename __tree<_Tp, _Compare, _Allocator>::iterator 1950 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) 1951 { 1952 __node_base_pointer __parent; 1953 __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_); 1954 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1955 return iterator(__nd); 1956 } 1957 1958 template <class _Tp, class _Compare, class _Allocator> 1959 typename __tree<_Tp, _Compare, _Allocator>::iterator 1960 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, 1961 __node_pointer __nd) 1962 { 1963 __node_base_pointer __parent; 1964 __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_); 1965 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1966 return iterator(__nd); 1967 } 1968 1969 template <class _Tp, class _Compare, class _Allocator> 1970 typename __tree<_Tp, _Compare, _Allocator>::iterator 1971 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) 1972 { 1973 __node_pointer __np = __p.__ptr_; 1974 iterator __r(__np); 1975 ++__r; 1976 if (__begin_node() == __np) 1977 __begin_node() = __r.__ptr_; 1978 --size(); 1979 __node_allocator& __na = __node_alloc(); 1980 __tree_remove(__end_node()->__left_, 1981 static_cast<__node_base_pointer>(__np)); 1982 __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p))); 1983 __node_traits::deallocate(__na, __np, 1); 1984 return __r; 1985 } 1986 1987 template <class _Tp, class _Compare, class _Allocator> 1988 typename __tree<_Tp, _Compare, _Allocator>::iterator 1989 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) 1990 { 1991 while (__f != __l) 1992 __f = erase(__f); 1993 return iterator(__l.__ptr_); 1994 } 1995 1996 template <class _Tp, class _Compare, class _Allocator> 1997 template <class _Key> 1998 typename __tree<_Tp, _Compare, _Allocator>::size_type 1999 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) 2000 { 2001 iterator __i = find(__k); 2002 if (__i == end()) 2003 return 0; 2004 erase(__i); 2005 return 1; 2006 } 2007 2008 template <class _Tp, class _Compare, class _Allocator> 2009 template <class _Key> 2010 typename __tree<_Tp, _Compare, _Allocator>::size_type 2011 __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) 2012 { 2013 pair<iterator, iterator> __p = __equal_range_multi(__k); 2014 size_type __r = 0; 2015 for (; __p.first != __p.second; ++__r) 2016 __p.first = erase(__p.first); 2017 return __r; 2018 } 2019 2020 template <class _Tp, class _Compare, class _Allocator> 2021 template <class _Key> 2022 typename __tree<_Tp, _Compare, _Allocator>::iterator 2023 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) 2024 { 2025 iterator __p = __lower_bound(__v, __root(), __end_node()); 2026 if (__p != end() && !value_comp()(__v, *__p)) 2027 return __p; 2028 return end(); 2029 } 2030 2031 template <class _Tp, class _Compare, class _Allocator> 2032 template <class _Key> 2033 typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2034 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const 2035 { 2036 const_iterator __p = __lower_bound(__v, __root(), __end_node()); 2037 if (__p != end() && !value_comp()(__v, *__p)) 2038 return __p; 2039 return end(); 2040 } 2041 2042 template <class _Tp, class _Compare, class _Allocator> 2043 template <class _Key> 2044 typename __tree<_Tp, _Compare, _Allocator>::size_type 2045 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const 2046 { 2047 __node_const_pointer __result = __end_node(); 2048 __node_const_pointer __rt = __root(); 2049 while (__rt != nullptr) 2050 { 2051 if (value_comp()(__k, __rt->__value_)) 2052 { 2053 __result = __rt; 2054 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2055 } 2056 else if (value_comp()(__rt->__value_, __k)) 2057 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2058 else 2059 return 1; 2060 } 2061 return 0; 2062 } 2063 2064 template <class _Tp, class _Compare, class _Allocator> 2065 template <class _Key> 2066 typename __tree<_Tp, _Compare, _Allocator>::size_type 2067 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const 2068 { 2069 __node_const_pointer __result = __end_node(); 2070 __node_const_pointer __rt = __root(); 2071 while (__rt != nullptr) 2072 { 2073 if (value_comp()(__k, __rt->__value_)) 2074 { 2075 __result = __rt; 2076 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2077 } 2078 else if (value_comp()(__rt->__value_, __k)) 2079 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2080 else 2081 return _VSTD::distance( 2082 __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2083 __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result) 2084 ); 2085 } 2086 return 0; 2087 } 2088 2089 template <class _Tp, class _Compare, class _Allocator> 2090 template <class _Key> 2091 typename __tree<_Tp, _Compare, _Allocator>::iterator 2092 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2093 __node_pointer __root, 2094 __node_pointer __result) 2095 { 2096 while (__root != nullptr) 2097 { 2098 if (!value_comp()(__root->__value_, __v)) 2099 { 2100 __result = __root; 2101 __root = static_cast<__node_pointer>(__root->__left_); 2102 } 2103 else 2104 __root = static_cast<__node_pointer>(__root->__right_); 2105 } 2106 return iterator(__result); 2107 } 2108 2109 template <class _Tp, class _Compare, class _Allocator> 2110 template <class _Key> 2111 typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2112 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2113 __node_const_pointer __root, 2114 __node_const_pointer __result) const 2115 { 2116 while (__root != nullptr) 2117 { 2118 if (!value_comp()(__root->__value_, __v)) 2119 { 2120 __result = __root; 2121 __root = static_cast<__node_const_pointer>(__root->__left_); 2122 } 2123 else 2124 __root = static_cast<__node_const_pointer>(__root->__right_); 2125 } 2126 return const_iterator(__result); 2127 } 2128 2129 template <class _Tp, class _Compare, class _Allocator> 2130 template <class _Key> 2131 typename __tree<_Tp, _Compare, _Allocator>::iterator 2132 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2133 __node_pointer __root, 2134 __node_pointer __result) 2135 { 2136 while (__root != nullptr) 2137 { 2138 if (value_comp()(__v, __root->__value_)) 2139 { 2140 __result = __root; 2141 __root = static_cast<__node_pointer>(__root->__left_); 2142 } 2143 else 2144 __root = static_cast<__node_pointer>(__root->__right_); 2145 } 2146 return iterator(__result); 2147 } 2148 2149 template <class _Tp, class _Compare, class _Allocator> 2150 template <class _Key> 2151 typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2152 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2153 __node_const_pointer __root, 2154 __node_const_pointer __result) const 2155 { 2156 while (__root != nullptr) 2157 { 2158 if (value_comp()(__v, __root->__value_)) 2159 { 2160 __result = __root; 2161 __root = static_cast<__node_const_pointer>(__root->__left_); 2162 } 2163 else 2164 __root = static_cast<__node_const_pointer>(__root->__right_); 2165 } 2166 return const_iterator(__result); 2167 } 2168 2169 template <class _Tp, class _Compare, class _Allocator> 2170 template <class _Key> 2171 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2172 typename __tree<_Tp, _Compare, _Allocator>::iterator> 2173 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 2174 { 2175 typedef pair<iterator, iterator> _Pp; 2176 __node_pointer __result = __end_node(); 2177 __node_pointer __rt = __root(); 2178 while (__rt != nullptr) 2179 { 2180 if (value_comp()(__k, __rt->__value_)) 2181 { 2182 __result = __rt; 2183 __rt = static_cast<__node_pointer>(__rt->__left_); 2184 } 2185 else if (value_comp()(__rt->__value_, __k)) 2186 __rt = static_cast<__node_pointer>(__rt->__right_); 2187 else 2188 return _Pp(iterator(__rt), 2189 iterator( 2190 __rt->__right_ != nullptr ? 2191 static_cast<__node_pointer>(__tree_min(__rt->__right_)) 2192 : __result)); 2193 } 2194 return _Pp(iterator(__result), iterator(__result)); 2195 } 2196 2197 template <class _Tp, class _Compare, class _Allocator> 2198 template <class _Key> 2199 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2200 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2201 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 2202 { 2203 typedef pair<const_iterator, const_iterator> _Pp; 2204 __node_const_pointer __result = __end_node(); 2205 __node_const_pointer __rt = __root(); 2206 while (__rt != nullptr) 2207 { 2208 if (value_comp()(__k, __rt->__value_)) 2209 { 2210 __result = __rt; 2211 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2212 } 2213 else if (value_comp()(__rt->__value_, __k)) 2214 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2215 else 2216 return _Pp(const_iterator(__rt), 2217 const_iterator( 2218 __rt->__right_ != nullptr ? 2219 static_cast<__node_const_pointer>(__tree_min(__rt->__right_)) 2220 : __result)); 2221 } 2222 return _Pp(const_iterator(__result), const_iterator(__result)); 2223 } 2224 2225 template <class _Tp, class _Compare, class _Allocator> 2226 template <class _Key> 2227 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2228 typename __tree<_Tp, _Compare, _Allocator>::iterator> 2229 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 2230 { 2231 typedef pair<iterator, iterator> _Pp; 2232 __node_pointer __result = __end_node(); 2233 __node_pointer __rt = __root(); 2234 while (__rt != nullptr) 2235 { 2236 if (value_comp()(__k, __rt->__value_)) 2237 { 2238 __result = __rt; 2239 __rt = static_cast<__node_pointer>(__rt->__left_); 2240 } 2241 else if (value_comp()(__rt->__value_, __k)) 2242 __rt = static_cast<__node_pointer>(__rt->__right_); 2243 else 2244 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt), 2245 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2246 } 2247 return _Pp(iterator(__result), iterator(__result)); 2248 } 2249 2250 template <class _Tp, class _Compare, class _Allocator> 2251 template <class _Key> 2252 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2253 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2254 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 2255 { 2256 typedef pair<const_iterator, const_iterator> _Pp; 2257 __node_const_pointer __result = __end_node(); 2258 __node_const_pointer __rt = __root(); 2259 while (__rt != nullptr) 2260 { 2261 if (value_comp()(__k, __rt->__value_)) 2262 { 2263 __result = __rt; 2264 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2265 } 2266 else if (value_comp()(__rt->__value_, __k)) 2267 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2268 else 2269 return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2270 __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)); 2271 } 2272 return _Pp(const_iterator(__result), const_iterator(__result)); 2273 } 2274 2275 template <class _Tp, class _Compare, class _Allocator> 2276 typename __tree<_Tp, _Compare, _Allocator>::__node_holder 2277 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 2278 { 2279 __node_pointer __np = __p.__ptr_; 2280 if (__begin_node() == __np) 2281 { 2282 if (__np->__right_ != nullptr) 2283 __begin_node() = static_cast<__node_pointer>(__np->__right_); 2284 else 2285 __begin_node() = static_cast<__node_pointer>(__np->__parent_); 2286 } 2287 --size(); 2288 __tree_remove(__end_node()->__left_, 2289 static_cast<__node_base_pointer>(__np)); 2290 return __node_holder(__np, _Dp(__node_alloc(), true)); 2291 } 2292 2293 template <class _Tp, class _Compare, class _Allocator> 2294 inline _LIBCPP_INLINE_VISIBILITY 2295 void 2296 swap(__tree<_Tp, _Compare, _Allocator>& __x, 2297 __tree<_Tp, _Compare, _Allocator>& __y) 2298 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2299 { 2300 __x.swap(__y); 2301 } 2302 2303 _LIBCPP_END_NAMESPACE_STD 2304 2305 #endif // _LIBCPP___TREE 2306
