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