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