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