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