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