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 26template <class _Tp, class _Compare, class _Allocator> class __tree; 27template <class _Tp, class _NodePtr, class _DiffType> 28 class _LIBCPP_TYPE_VIS_ONLY __tree_iterator; 29template <class _Tp, class _ConstNodePtr, class _DiffType> 30 class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator; 31template <class _Key, class _Tp, class _Compare, class _Allocator> 32 class _LIBCPP_TYPE_VIS_ONLY map; 33template <class _Key, class _Tp, class _Compare, class _Allocator> 34 class _LIBCPP_TYPE_VIS_ONLY multimap; 35template <class _Key, class _Compare, class _Allocator> 36 class _LIBCPP_TYPE_VIS_ONLY set; 37template <class _Key, class _Compare, class _Allocator> 38 class _LIBCPP_TYPE_VIS_ONLY multiset; 39 40/* 41 42_NodePtr algorithms 43 44The algorithms taking _NodePtr are red black tree algorithms. Those 45algorithms taking a parameter named __root should assume that __root 46points to a proper red black tree (unless otherwise specified). 47 48Each algorithm herein assumes that __root->__parent_ points to a non-null 49structure which has a member __left_ which points back to __root. No other 50member is read or written to at __root->__parent_. 51 52__root->__parent_ will be referred to below (in comments only) as end_node. 53end_node->__left_ is an externably accessible lvalue for __root, and can be 54changed by node insertion and removal (without explicit reference to end_node). 55 56All 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. 63template <class _NodePtr> 64inline _LIBCPP_INLINE_VISIBILITY 65bool 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. 74template <class _NodePtr> 75unsigned 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. 109template <class _NodePtr> 110bool 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. 129template <class _NodePtr> 130inline _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. 141template <class _NodePtr> 142inline _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. 153template <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. 166template <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. 179template <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 203template <class _NodePtr> 204void 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 223template <class _NodePtr> 224void 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. 248template <class _NodePtr> 249void 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. 318template <class _NodePtr> 319void 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 505template <class _Allocator> class __map_node_destructor; 506 507template <class _Allocator> 508class __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; 513public: 514 typedef typename __alloc_traits::pointer pointer; 515private: 516 517 allocator_type& __na_; 518 519 __tree_node_destructor& operator=(const __tree_node_destructor&); 520 521public: 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 544template <class _Pointer> 545class __tree_end_node 546{ 547public: 548 typedef _Pointer pointer; 549 pointer __left_; 550 551 _LIBCPP_INLINE_VISIBILITY 552 __tree_end_node() _NOEXCEPT : __left_() {} 553}; 554 555template <class _VoidPtr> 556class __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&); 569public: 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 595template <class _Tp, class _VoidPtr> 596class __tree_node 597 : public __tree_node_base<_VoidPtr> 598{ 599public: 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 617template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator; 618template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; 619 620template <class _Tp, class _NodePtr, class _DiffType> 621class _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; 629public: 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 679private: 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 691template <class _Tp, class _ConstNodePtr, class _DiffType> 692class _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; 700public: 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 719private: 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; 730public: 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 784private: 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 796template <class _Tp, class _Compare, class _Allocator> 797class __tree 798{ 799public: 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; 825private: 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 846public: 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();} 865private: 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_;} 873public: 874 _LIBCPP_INLINE_VISIBILITY 875 allocator_type __alloc() const _NOEXCEPT 876 {return allocator_type(__node_alloc());} 877private: 878 _LIBCPP_INLINE_VISIBILITY 879 size_type& size() _NOEXCEPT {return __pair3_.first();} 880public: 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();} 888public: 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; 1057private: 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 1139template <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 1149template <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 1158template <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 1169template <class _Tp, class _Compare, class _Allocator> 1170typename __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 1190template <class _Tp, class _Compare, class _Allocator> 1191typename __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 1212template <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 1225template <class _Tp, class _Compare, class _Allocator> 1226template <class _InputIterator> 1227void 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 1265template <class _Tp, class _Compare, class _Allocator> 1266template <class _InputIterator> 1267void 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 1305template <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 1316template <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 1336template <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 1362template <class _Tp, class _Compare, class _Allocator> 1363void 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 1384template <class _Tp, class _Compare, class _Allocator> 1385void 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 1430template <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 1446template <class _Tp, class _Compare, class _Allocator> 1447__tree<_Tp, _Compare, _Allocator>::~__tree() 1448{ 1449 destroy(__root()); 1450} 1451 1452template <class _Tp, class _Compare, class _Allocator> 1453void 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 1466template <class _Tp, class _Compare, class _Allocator> 1467void 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 1489template <class _Tp, class _Compare, class _Allocator> 1490void 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 1502template <class _Tp, class _Compare, class _Allocator> 1503typename __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 1541template <class _Tp, class _Compare, class _Allocator> 1542typename __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 1583template <class _Tp, class _Compare, class _Allocator> 1584typename __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 1618template <class _Tp, class _Compare, class _Allocator> 1619template <class _Key> 1620typename __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 1667template <class _Tp, class _Compare, class _Allocator> 1668template <class _Key> 1669typename __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 1721template <class _Tp, class _Compare, class _Allocator> 1722void 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 1740template <class _Tp, class _Compare, class _Allocator> 1741template <class ..._Args> 1742typename __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 1752template <class _Tp, class _Compare, class _Allocator> 1753template <class... _Args> 1754pair<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 1771template <class _Tp, class _Compare, class _Allocator> 1772template <class... _Args> 1773typename __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 1788template <class _Tp, class _Compare, class _Allocator> 1789template <class... _Args> 1790typename __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 1800template <class _Tp, class _Compare, class _Allocator> 1801template <class... _Args> 1802typename __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 1815template <class _Tp, class _Compare, class _Allocator> 1816template <class _Vp> 1817pair<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 1827template <class _Tp, class _Compare, class _Allocator> 1828template <class _Vp> 1829typename __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 1839template <class _Tp, class _Compare, class _Allocator> 1840template <class _Vp> 1841typename __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 1851template <class _Tp, class _Compare, class _Allocator> 1852template <class _Vp> 1853typename __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 1865template <class _Tp, class _Compare, class _Allocator> 1866typename __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 1878template <class _Tp, class _Compare, class _Allocator> 1879pair<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 1896template <class _Tp, class _Compare, class _Allocator> 1897typename __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 1912template <class _Tp, class _Compare, class _Allocator> 1913typename __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 1923template <class _Tp, class _Compare, class _Allocator> 1924typename __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 1934template <class _Tp, class _Compare, class _Allocator> 1935pair<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 1951template <class _Tp, class _Compare, class _Allocator> 1952typename __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 1967template <class _Tp, class _Compare, class _Allocator> 1968typename __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 1977template <class _Tp, class _Compare, class _Allocator> 1978typename __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 1988template <class _Tp, class _Compare, class _Allocator> 1989typename __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 2006template <class _Tp, class _Compare, class _Allocator> 2007typename __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 2015template <class _Tp, class _Compare, class _Allocator> 2016template <class _Key> 2017typename __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 2027template <class _Tp, class _Compare, class _Allocator> 2028template <class _Key> 2029typename __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 2039template <class _Tp, class _Compare, class _Allocator> 2040template <class _Key> 2041typename __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 2050template <class _Tp, class _Compare, class _Allocator> 2051template <class _Key> 2052typename __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 2061template <class _Tp, class _Compare, class _Allocator> 2062template <class _Key> 2063typename __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 2083template <class _Tp, class _Compare, class _Allocator> 2084template <class _Key> 2085typename __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 2109template <class _Tp, class _Compare, class _Allocator> 2110template <class _Key> 2111typename __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 2129template <class _Tp, class _Compare, class _Allocator> 2130template <class _Key> 2131typename __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 2149template <class _Tp, class _Compare, class _Allocator> 2150template <class _Key> 2151typename __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 2169template <class _Tp, class _Compare, class _Allocator> 2170template <class _Key> 2171typename __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 2189template <class _Tp, class _Compare, class _Allocator> 2190template <class _Key> 2191pair<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 2217template <class _Tp, class _Compare, class _Allocator> 2218template <class _Key> 2219pair<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 2245template <class _Tp, class _Compare, class _Allocator> 2246template <class _Key> 2247pair<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 2270template <class _Tp, class _Compare, class _Allocator> 2271template <class _Key> 2272pair<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 2295template <class _Tp, class _Compare, class _Allocator> 2296typename __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 2313template <class _Tp, class _Compare, class _Allocator> 2314inline _LIBCPP_INLINE_VISIBILITY 2315void 2316swap(__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