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