__tree revision 303975
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 __rebind_pointer<_VoidPtr, __tree_node_base<_VoidPtr> >::type 552 > 553{ 554 __tree_node_base(const __tree_node_base&); 555 __tree_node_base& operator=(const __tree_node_base&); 556public: 557 typedef typename __rebind_pointer<_VoidPtr, __tree_node_base>::type pointer; 558 typedef typename __rebind_pointer<_VoidPtr, const __tree_node_base>::type const_pointer; 559 560 typedef __tree_end_node<pointer> base; 561 562 pointer __right_; 563 pointer __parent_; 564 bool __is_black_; 565 566 _LIBCPP_INLINE_VISIBILITY 567 __tree_node_base() _NOEXCEPT 568 : __right_(), __parent_(), __is_black_(false) {} 569}; 570 571template <class _Tp, class _VoidPtr> 572class __tree_node 573 : public __tree_node_base<_VoidPtr> 574{ 575public: 576 typedef __tree_node_base<_VoidPtr> base; 577 typedef _Tp value_type; 578 579 value_type __value_; 580 581#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 582 template <class ..._Args> 583 _LIBCPP_INLINE_VISIBILITY 584 explicit __tree_node(_Args&& ...__args) 585 : __value_(_VSTD::forward<_Args>(__args)...) {} 586#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 587 _LIBCPP_INLINE_VISIBILITY 588 explicit __tree_node(const value_type& __v) 589 : __value_(__v) {} 590#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 591}; 592 593template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator; 594template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; 595 596template <class _Tp, class _NodePtr, class _DiffType> 597class _LIBCPP_TYPE_VIS_ONLY __tree_iterator 598{ 599 typedef _NodePtr __node_pointer; 600 typedef typename pointer_traits<__node_pointer>::element_type __node; 601 602 __node_pointer __ptr_; 603 604 typedef pointer_traits<__node_pointer> __pointer_traits; 605public: 606 typedef bidirectional_iterator_tag iterator_category; 607 typedef _Tp value_type; 608 typedef _DiffType difference_type; 609 typedef value_type& reference; 610 typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; 611 612 _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT 613#if _LIBCPP_STD_VER > 11 614 : __ptr_(nullptr) 615#endif 616 {} 617 618 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 619 _LIBCPP_INLINE_VISIBILITY pointer operator->() const 620 {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 621 622 _LIBCPP_INLINE_VISIBILITY 623 __tree_iterator& operator++() { 624 __ptr_ = static_cast<__node_pointer>( 625 __tree_next(static_cast<typename __node::base::pointer>(__ptr_))); 626 return *this; 627 } 628 _LIBCPP_INLINE_VISIBILITY 629 __tree_iterator operator++(int) 630 {__tree_iterator __t(*this); ++(*this); return __t;} 631 632 _LIBCPP_INLINE_VISIBILITY 633 __tree_iterator& operator--() { 634 __ptr_ = static_cast<__node_pointer>( 635 __tree_prev(static_cast<typename __node::base::pointer>(__ptr_))); 636 return *this; 637 } 638 _LIBCPP_INLINE_VISIBILITY 639 __tree_iterator operator--(int) 640 {__tree_iterator __t(*this); --(*this); return __t;} 641 642 friend _LIBCPP_INLINE_VISIBILITY 643 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 644 {return __x.__ptr_ == __y.__ptr_;} 645 friend _LIBCPP_INLINE_VISIBILITY 646 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 647 {return !(__x == __y);} 648 649private: 650 _LIBCPP_INLINE_VISIBILITY 651 explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 652 template <class, class, class> friend class __tree; 653 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator; 654 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator; 655 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 656 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 657 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set; 658 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset; 659}; 660 661template <class _Tp, class _ConstNodePtr, class _DiffType> 662class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator 663{ 664 typedef _ConstNodePtr __node_pointer; 665 typedef typename pointer_traits<__node_pointer>::element_type __node; 666 667 __node_pointer __ptr_; 668 669 typedef pointer_traits<__node_pointer> __pointer_traits; 670public: 671 typedef bidirectional_iterator_tag iterator_category; 672 typedef _Tp value_type; 673 typedef _DiffType difference_type; 674 typedef const value_type& reference; 675 typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer; 676 677 _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT 678#if _LIBCPP_STD_VER > 11 679 : __ptr_(nullptr) 680#endif 681 {} 682 683private: 684 typedef typename remove_const<__node>::type __non_const_node; 685 typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type 686 __non_const_node_pointer; 687 typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> 688 __non_const_iterator; 689public: 690 _LIBCPP_INLINE_VISIBILITY 691 __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 692 : __ptr_(__p.__ptr_) {} 693 694 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 695 _LIBCPP_INLINE_VISIBILITY pointer operator->() const 696 {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 697 698 _LIBCPP_INLINE_VISIBILITY 699 __tree_const_iterator& operator++() { 700 typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type 701 __node_base_pointer; 702 __ptr_ = static_cast<__node_pointer>( 703 __tree_next(static_cast<__node_base_pointer>(__ptr_))); 704 return *this; 705 } 706 707 _LIBCPP_INLINE_VISIBILITY 708 __tree_const_iterator operator++(int) 709 {__tree_const_iterator __t(*this); ++(*this); return __t;} 710 711 _LIBCPP_INLINE_VISIBILITY 712 __tree_const_iterator& operator--() { 713 typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type 714 __node_base_pointer; 715 __ptr_ = static_cast<__node_pointer>( 716 __tree_prev(static_cast<__node_base_pointer>(__ptr_))); 717 return *this; 718 } 719 720 _LIBCPP_INLINE_VISIBILITY 721 __tree_const_iterator operator--(int) 722 {__tree_const_iterator __t(*this); --(*this); return __t;} 723 724 friend _LIBCPP_INLINE_VISIBILITY 725 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 726 {return __x.__ptr_ == __y.__ptr_;} 727 friend _LIBCPP_INLINE_VISIBILITY 728 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 729 {return !(__x == __y);} 730 731private: 732 _LIBCPP_INLINE_VISIBILITY 733 explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 734 : __ptr_(__p) {} 735 template <class, class, class> friend class __tree; 736 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 737 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 738 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set; 739 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset; 740 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; 741}; 742 743template <class _Tp, class _Compare, class _Allocator> 744class __tree 745{ 746public: 747 typedef _Tp value_type; 748 typedef _Compare value_compare; 749 typedef _Allocator allocator_type; 750 typedef allocator_traits<allocator_type> __alloc_traits; 751 typedef typename __alloc_traits::pointer pointer; 752 typedef typename __alloc_traits::const_pointer const_pointer; 753 typedef typename __alloc_traits::size_type size_type; 754 typedef typename __alloc_traits::difference_type difference_type; 755 756 typedef typename __alloc_traits::void_pointer __void_pointer; 757 758 typedef __tree_node<value_type, __void_pointer> __node; 759 typedef __tree_node_base<__void_pointer> __node_base; 760 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 761 typedef allocator_traits<__node_allocator> __node_traits; 762 typedef typename __node_traits::pointer __node_pointer; 763 typedef typename __node_traits::pointer __node_const_pointer; 764 typedef typename __node_base::pointer __node_base_pointer; 765 typedef typename __node_base::pointer __node_base_const_pointer; 766private: 767 typedef typename __node_base::base __end_node_t; 768 typedef typename __rebind_pointer<__node_pointer, __end_node_t>::type 769 __end_node_ptr; 770 typedef __end_node_ptr __end_node_const_ptr; 771 772 __node_pointer __begin_node_; 773 __compressed_pair<__end_node_t, __node_allocator> __pair1_; 774 __compressed_pair<size_type, value_compare> __pair3_; 775 776public: 777 _LIBCPP_INLINE_VISIBILITY 778 __node_pointer __end_node() _NOEXCEPT 779 { 780 return static_cast<__node_pointer> 781 ( 782 pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 783 ); 784 } 785 _LIBCPP_INLINE_VISIBILITY 786 __node_const_pointer __end_node() const _NOEXCEPT 787 { 788 return static_cast<__node_const_pointer> 789 ( 790 pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first())) 791 ); 792 } 793 _LIBCPP_INLINE_VISIBILITY 794 __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 795private: 796 _LIBCPP_INLINE_VISIBILITY 797 const __node_allocator& __node_alloc() const _NOEXCEPT 798 {return __pair1_.second();} 799 _LIBCPP_INLINE_VISIBILITY 800 __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 801 _LIBCPP_INLINE_VISIBILITY 802 const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 803public: 804 _LIBCPP_INLINE_VISIBILITY 805 allocator_type __alloc() const _NOEXCEPT 806 {return allocator_type(__node_alloc());} 807private: 808 _LIBCPP_INLINE_VISIBILITY 809 size_type& size() _NOEXCEPT {return __pair3_.first();} 810public: 811 _LIBCPP_INLINE_VISIBILITY 812 const size_type& size() const _NOEXCEPT {return __pair3_.first();} 813 _LIBCPP_INLINE_VISIBILITY 814 value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 815 _LIBCPP_INLINE_VISIBILITY 816 const value_compare& value_comp() const _NOEXCEPT 817 {return __pair3_.second();} 818public: 819 _LIBCPP_INLINE_VISIBILITY 820 __node_pointer __root() _NOEXCEPT 821 {return static_cast<__node_pointer> (__end_node()->__left_);} 822 _LIBCPP_INLINE_VISIBILITY 823 __node_const_pointer __root() const _NOEXCEPT 824 {return static_cast<__node_const_pointer>(__end_node()->__left_);} 825 826 typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 827 typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 828 829 explicit __tree(const value_compare& __comp) 830 _NOEXCEPT_( 831 is_nothrow_default_constructible<__node_allocator>::value && 832 is_nothrow_copy_constructible<value_compare>::value); 833 explicit __tree(const allocator_type& __a); 834 __tree(const value_compare& __comp, const allocator_type& __a); 835 __tree(const __tree& __t); 836 __tree& operator=(const __tree& __t); 837 template <class _InputIterator> 838 void __assign_unique(_InputIterator __first, _InputIterator __last); 839 template <class _InputIterator> 840 void __assign_multi(_InputIterator __first, _InputIterator __last); 841#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 842 __tree(__tree&& __t) 843 _NOEXCEPT_( 844 is_nothrow_move_constructible<__node_allocator>::value && 845 is_nothrow_move_constructible<value_compare>::value); 846 __tree(__tree&& __t, const allocator_type& __a); 847 __tree& operator=(__tree&& __t) 848 _NOEXCEPT_( 849 __node_traits::propagate_on_container_move_assignment::value && 850 is_nothrow_move_assignable<value_compare>::value && 851 is_nothrow_move_assignable<__node_allocator>::value); 852#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 853 854 ~__tree(); 855 856 _LIBCPP_INLINE_VISIBILITY 857 iterator begin() _NOEXCEPT {return iterator(__begin_node());} 858 _LIBCPP_INLINE_VISIBILITY 859 const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 860 _LIBCPP_INLINE_VISIBILITY 861 iterator end() _NOEXCEPT {return iterator(__end_node());} 862 _LIBCPP_INLINE_VISIBILITY 863 const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 864 865 _LIBCPP_INLINE_VISIBILITY 866 size_type max_size() const _NOEXCEPT 867 {return __node_traits::max_size(__node_alloc());} 868 869 void clear() _NOEXCEPT; 870 871 void swap(__tree& __t) 872 _NOEXCEPT_( 873 __is_nothrow_swappable<value_compare>::value 874#if _LIBCPP_STD_VER <= 11 875 && (!__node_traits::propagate_on_container_swap::value || 876 __is_nothrow_swappable<__node_allocator>::value) 877#endif 878 ); 879 880#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 881#ifndef _LIBCPP_HAS_NO_VARIADICS 882 template <class... _Args> 883 pair<iterator, bool> 884 __emplace_unique(_Args&&... __args); 885 template <class... _Args> 886 iterator 887 __emplace_multi(_Args&&... __args); 888 889 template <class... _Args> 890 iterator 891 __emplace_hint_unique(const_iterator __p, _Args&&... __args); 892 template <class... _Args> 893 iterator 894 __emplace_hint_multi(const_iterator __p, _Args&&... __args); 895#endif // _LIBCPP_HAS_NO_VARIADICS 896 897 template <class _Vp> 898 pair<iterator, bool> __insert_unique(_Vp&& __v); 899 template <class _Vp> 900 iterator __insert_unique(const_iterator __p, _Vp&& __v); 901 template <class _Vp> 902 iterator __insert_multi(_Vp&& __v); 903 template <class _Vp> 904 iterator __insert_multi(const_iterator __p, _Vp&& __v); 905#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 906 907 pair<iterator, bool> __insert_unique(const value_type& __v); 908 iterator __insert_unique(const_iterator __p, const value_type& __v); 909 iterator __insert_multi(const value_type& __v); 910 iterator __insert_multi(const_iterator __p, const value_type& __v); 911 912#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 913 pair<iterator, bool> __insert_unique( value_type&& __v); 914 iterator __insert_unique(const_iterator __p, value_type&& __v); 915 iterator __insert_multi( value_type&& __v); 916 iterator __insert_multi(const_iterator __p, value_type&& __v); 917#endif 918 919 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 920 iterator __node_insert_unique(const_iterator __p, 921 __node_pointer __nd); 922 923 iterator __node_insert_multi(__node_pointer __nd); 924 iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 925 926 iterator erase(const_iterator __p); 927 iterator erase(const_iterator __f, const_iterator __l); 928 template <class _Key> 929 size_type __erase_unique(const _Key& __k); 930 template <class _Key> 931 size_type __erase_multi(const _Key& __k); 932 933 void __insert_node_at(__node_base_pointer __parent, 934 __node_base_pointer& __child, 935 __node_base_pointer __new_node); 936 937 template <class _Key> 938 iterator find(const _Key& __v); 939 template <class _Key> 940 const_iterator find(const _Key& __v) const; 941 942 template <class _Key> 943 size_type __count_unique(const _Key& __k) const; 944 template <class _Key> 945 size_type __count_multi(const _Key& __k) const; 946 947 template <class _Key> 948 _LIBCPP_INLINE_VISIBILITY 949 iterator lower_bound(const _Key& __v) 950 {return __lower_bound(__v, __root(), __end_node());} 951 template <class _Key> 952 iterator __lower_bound(const _Key& __v, 953 __node_pointer __root, 954 __node_pointer __result); 955 template <class _Key> 956 _LIBCPP_INLINE_VISIBILITY 957 const_iterator lower_bound(const _Key& __v) const 958 {return __lower_bound(__v, __root(), __end_node());} 959 template <class _Key> 960 const_iterator __lower_bound(const _Key& __v, 961 __node_const_pointer __root, 962 __node_const_pointer __result) const; 963 template <class _Key> 964 _LIBCPP_INLINE_VISIBILITY 965 iterator upper_bound(const _Key& __v) 966 {return __upper_bound(__v, __root(), __end_node());} 967 template <class _Key> 968 iterator __upper_bound(const _Key& __v, 969 __node_pointer __root, 970 __node_pointer __result); 971 template <class _Key> 972 _LIBCPP_INLINE_VISIBILITY 973 const_iterator upper_bound(const _Key& __v) const 974 {return __upper_bound(__v, __root(), __end_node());} 975 template <class _Key> 976 const_iterator __upper_bound(const _Key& __v, 977 __node_const_pointer __root, 978 __node_const_pointer __result) const; 979 template <class _Key> 980 pair<iterator, iterator> 981 __equal_range_unique(const _Key& __k); 982 template <class _Key> 983 pair<const_iterator, const_iterator> 984 __equal_range_unique(const _Key& __k) const; 985 986 template <class _Key> 987 pair<iterator, iterator> 988 __equal_range_multi(const _Key& __k); 989 template <class _Key> 990 pair<const_iterator, const_iterator> 991 __equal_range_multi(const _Key& __k) const; 992 993 typedef __tree_node_destructor<__node_allocator> _Dp; 994 typedef unique_ptr<__node, _Dp> __node_holder; 995 996 __node_holder remove(const_iterator __p) _NOEXCEPT; 997private: 998 typename __node_base::pointer& 999 __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v); 1000 typename __node_base::pointer& 1001 __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v); 1002 typename __node_base::pointer& 1003 __find_leaf(const_iterator __hint, 1004 typename __node_base::pointer& __parent, const value_type& __v); 1005 template <class _Key> 1006 typename __node_base::pointer& 1007 __find_equal(typename __node_base::pointer& __parent, const _Key& __v); 1008 template <class _Key> 1009 typename __node_base::pointer& 1010 __find_equal(const_iterator __hint, typename __node_base::pointer& __parent, 1011 const _Key& __v); 1012 1013#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1014 template <class ..._Args> 1015 __node_holder __construct_node(_Args&& ...__args); 1016#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1017 __node_holder __construct_node(const value_type& __v); 1018#endif 1019 1020 void destroy(__node_pointer __nd) _NOEXCEPT; 1021 1022 _LIBCPP_INLINE_VISIBILITY 1023 void __copy_assign_alloc(const __tree& __t) 1024 {__copy_assign_alloc(__t, integral_constant<bool, 1025 __node_traits::propagate_on_container_copy_assignment::value>());} 1026 1027 _LIBCPP_INLINE_VISIBILITY 1028 void __copy_assign_alloc(const __tree& __t, true_type) 1029 {__node_alloc() = __t.__node_alloc();} 1030 _LIBCPP_INLINE_VISIBILITY 1031 void __copy_assign_alloc(const __tree& __t, false_type) {} 1032 1033 void __move_assign(__tree& __t, false_type); 1034 void __move_assign(__tree& __t, true_type) 1035 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1036 is_nothrow_move_assignable<__node_allocator>::value); 1037 1038 _LIBCPP_INLINE_VISIBILITY 1039 void __move_assign_alloc(__tree& __t) 1040 _NOEXCEPT_( 1041 !__node_traits::propagate_on_container_move_assignment::value || 1042 is_nothrow_move_assignable<__node_allocator>::value) 1043 {__move_assign_alloc(__t, integral_constant<bool, 1044 __node_traits::propagate_on_container_move_assignment::value>());} 1045 1046 _LIBCPP_INLINE_VISIBILITY 1047 void __move_assign_alloc(__tree& __t, true_type) 1048 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1049 {__node_alloc() = _VSTD::move(__t.__node_alloc());} 1050 _LIBCPP_INLINE_VISIBILITY 1051 void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {} 1052 1053 __node_pointer __detach(); 1054 static __node_pointer __detach(__node_pointer); 1055 1056 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map; 1057 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap; 1058}; 1059 1060template <class _Tp, class _Compare, class _Allocator> 1061__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 1062 _NOEXCEPT_( 1063 is_nothrow_default_constructible<__node_allocator>::value && 1064 is_nothrow_copy_constructible<value_compare>::value) 1065 : __pair3_(0, __comp) 1066{ 1067 __begin_node() = __end_node(); 1068} 1069 1070template <class _Tp, class _Compare, class _Allocator> 1071__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1072 : __begin_node_(__node_pointer()), 1073 __pair1_(__node_allocator(__a)), 1074 __pair3_(0) 1075{ 1076 __begin_node() = __end_node(); 1077} 1078 1079template <class _Tp, class _Compare, class _Allocator> 1080__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 1081 const allocator_type& __a) 1082 : __begin_node_(__node_pointer()), 1083 __pair1_(__node_allocator(__a)), 1084 __pair3_(0, __comp) 1085{ 1086 __begin_node() = __end_node(); 1087} 1088 1089// Precondition: size() != 0 1090template <class _Tp, class _Compare, class _Allocator> 1091typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1092__tree<_Tp, _Compare, _Allocator>::__detach() 1093{ 1094 __node_pointer __cache = __begin_node(); 1095 __begin_node() = __end_node(); 1096 __end_node()->__left_->__parent_ = nullptr; 1097 __end_node()->__left_ = nullptr; 1098 size() = 0; 1099 // __cache->__left_ == nullptr 1100 if (__cache->__right_ != nullptr) 1101 __cache = static_cast<__node_pointer>(__cache->__right_); 1102 // __cache->__left_ == nullptr 1103 // __cache->__right_ == nullptr 1104 return __cache; 1105} 1106 1107// Precondition: __cache != nullptr 1108// __cache->left_ == nullptr 1109// __cache->right_ == nullptr 1110// This is no longer a red-black tree 1111template <class _Tp, class _Compare, class _Allocator> 1112typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1113__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache) 1114{ 1115 if (__cache->__parent_ == nullptr) 1116 return nullptr; 1117 if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 1118 { 1119 __cache->__parent_->__left_ = nullptr; 1120 __cache = static_cast<__node_pointer>(__cache->__parent_); 1121 if (__cache->__right_ == nullptr) 1122 return __cache; 1123 return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); 1124 } 1125 // __cache is right child 1126 __cache->__parent_->__right_ = nullptr; 1127 __cache = static_cast<__node_pointer>(__cache->__parent_); 1128 if (__cache->__left_ == nullptr) 1129 return __cache; 1130 return static_cast<__node_pointer>(__tree_leaf(__cache->__left_)); 1131} 1132 1133template <class _Tp, class _Compare, class _Allocator> 1134__tree<_Tp, _Compare, _Allocator>& 1135__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 1136{ 1137 if (this != &__t) 1138 { 1139 value_comp() = __t.value_comp(); 1140 __copy_assign_alloc(__t); 1141 __assign_multi(__t.begin(), __t.end()); 1142 } 1143 return *this; 1144} 1145 1146template <class _Tp, class _Compare, class _Allocator> 1147template <class _InputIterator> 1148void 1149__tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last) 1150{ 1151 if (size() != 0) 1152 { 1153 __node_pointer __cache = __detach(); 1154#ifndef _LIBCPP_NO_EXCEPTIONS 1155 try 1156 { 1157#endif // _LIBCPP_NO_EXCEPTIONS 1158 for (; __cache != nullptr && __first != __last; ++__first) 1159 { 1160 __cache->__value_ = *__first; 1161 __node_pointer __next = __detach(__cache); 1162 __node_insert_unique(__cache); 1163 __cache = __next; 1164 } 1165#ifndef _LIBCPP_NO_EXCEPTIONS 1166 } 1167 catch (...) 1168 { 1169 while (__cache->__parent_ != nullptr) 1170 __cache = static_cast<__node_pointer>(__cache->__parent_); 1171 destroy(__cache); 1172 throw; 1173 } 1174#endif // _LIBCPP_NO_EXCEPTIONS 1175 if (__cache != nullptr) 1176 { 1177 while (__cache->__parent_ != nullptr) 1178 __cache = static_cast<__node_pointer>(__cache->__parent_); 1179 destroy(__cache); 1180 } 1181 } 1182 for (; __first != __last; ++__first) 1183 __insert_unique(*__first); 1184} 1185 1186template <class _Tp, class _Compare, class _Allocator> 1187template <class _InputIterator> 1188void 1189__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 1190{ 1191 if (size() != 0) 1192 { 1193 __node_pointer __cache = __detach(); 1194#ifndef _LIBCPP_NO_EXCEPTIONS 1195 try 1196 { 1197#endif // _LIBCPP_NO_EXCEPTIONS 1198 for (; __cache != nullptr && __first != __last; ++__first) 1199 { 1200 __cache->__value_ = *__first; 1201 __node_pointer __next = __detach(__cache); 1202 __node_insert_multi(__cache); 1203 __cache = __next; 1204 } 1205#ifndef _LIBCPP_NO_EXCEPTIONS 1206 } 1207 catch (...) 1208 { 1209 while (__cache->__parent_ != nullptr) 1210 __cache = static_cast<__node_pointer>(__cache->__parent_); 1211 destroy(__cache); 1212 throw; 1213 } 1214#endif // _LIBCPP_NO_EXCEPTIONS 1215 if (__cache != nullptr) 1216 { 1217 while (__cache->__parent_ != nullptr) 1218 __cache = static_cast<__node_pointer>(__cache->__parent_); 1219 destroy(__cache); 1220 } 1221 } 1222 for (; __first != __last; ++__first) 1223 __insert_multi(*__first); 1224} 1225 1226template <class _Tp, class _Compare, class _Allocator> 1227__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1228 : __begin_node_(__node_pointer()), 1229 __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1230 __pair3_(0, __t.value_comp()) 1231{ 1232 __begin_node() = __end_node(); 1233} 1234 1235#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1236 1237template <class _Tp, class _Compare, class _Allocator> 1238__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 1239 _NOEXCEPT_( 1240 is_nothrow_move_constructible<__node_allocator>::value && 1241 is_nothrow_move_constructible<value_compare>::value) 1242 : __begin_node_(_VSTD::move(__t.__begin_node_)), 1243 __pair1_(_VSTD::move(__t.__pair1_)), 1244 __pair3_(_VSTD::move(__t.__pair3_)) 1245{ 1246 if (size() == 0) 1247 __begin_node() = __end_node(); 1248 else 1249 { 1250 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1251 __t.__begin_node() = __t.__end_node(); 1252 __t.__end_node()->__left_ = nullptr; 1253 __t.size() = 0; 1254 } 1255} 1256 1257template <class _Tp, class _Compare, class _Allocator> 1258__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1259 : __pair1_(__node_allocator(__a)), 1260 __pair3_(0, _VSTD::move(__t.value_comp())) 1261{ 1262 if (__a == __t.__alloc()) 1263 { 1264 if (__t.size() == 0) 1265 __begin_node() = __end_node(); 1266 else 1267 { 1268 __begin_node() = __t.__begin_node(); 1269 __end_node()->__left_ = __t.__end_node()->__left_; 1270 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1271 size() = __t.size(); 1272 __t.__begin_node() = __t.__end_node(); 1273 __t.__end_node()->__left_ = nullptr; 1274 __t.size() = 0; 1275 } 1276 } 1277 else 1278 { 1279 __begin_node() = __end_node(); 1280 } 1281} 1282 1283template <class _Tp, class _Compare, class _Allocator> 1284void 1285__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1286 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1287 is_nothrow_move_assignable<__node_allocator>::value) 1288{ 1289 destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1290 __begin_node_ = __t.__begin_node_; 1291 __pair1_.first() = __t.__pair1_.first(); 1292 __move_assign_alloc(__t); 1293 __pair3_ = _VSTD::move(__t.__pair3_); 1294 if (size() == 0) 1295 __begin_node() = __end_node(); 1296 else 1297 { 1298 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1299 __t.__begin_node() = __t.__end_node(); 1300 __t.__end_node()->__left_ = nullptr; 1301 __t.size() = 0; 1302 } 1303} 1304 1305template <class _Tp, class _Compare, class _Allocator> 1306void 1307__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 1308{ 1309 if (__node_alloc() == __t.__node_alloc()) 1310 __move_assign(__t, true_type()); 1311 else 1312 { 1313 value_comp() = _VSTD::move(__t.value_comp()); 1314 const_iterator __e = end(); 1315 if (size() != 0) 1316 { 1317 __node_pointer __cache = __detach(); 1318#ifndef _LIBCPP_NO_EXCEPTIONS 1319 try 1320 { 1321#endif // _LIBCPP_NO_EXCEPTIONS 1322 while (__cache != nullptr && __t.size() != 0) 1323 { 1324 __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 1325 __node_pointer __next = __detach(__cache); 1326 __node_insert_multi(__cache); 1327 __cache = __next; 1328 } 1329#ifndef _LIBCPP_NO_EXCEPTIONS 1330 } 1331 catch (...) 1332 { 1333 while (__cache->__parent_ != nullptr) 1334 __cache = static_cast<__node_pointer>(__cache->__parent_); 1335 destroy(__cache); 1336 throw; 1337 } 1338#endif // _LIBCPP_NO_EXCEPTIONS 1339 if (__cache != nullptr) 1340 { 1341 while (__cache->__parent_ != nullptr) 1342 __cache = static_cast<__node_pointer>(__cache->__parent_); 1343 destroy(__cache); 1344 } 1345 } 1346 while (__t.size() != 0) 1347 __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_)); 1348 } 1349} 1350 1351template <class _Tp, class _Compare, class _Allocator> 1352__tree<_Tp, _Compare, _Allocator>& 1353__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 1354 _NOEXCEPT_( 1355 __node_traits::propagate_on_container_move_assignment::value && 1356 is_nothrow_move_assignable<value_compare>::value && 1357 is_nothrow_move_assignable<__node_allocator>::value) 1358 1359{ 1360 __move_assign(__t, integral_constant<bool, 1361 __node_traits::propagate_on_container_move_assignment::value>()); 1362 return *this; 1363} 1364 1365#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1366 1367template <class _Tp, class _Compare, class _Allocator> 1368__tree<_Tp, _Compare, _Allocator>::~__tree() 1369{ 1370 destroy(__root()); 1371} 1372 1373template <class _Tp, class _Compare, class _Allocator> 1374void 1375__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 1376{ 1377 if (__nd != nullptr) 1378 { 1379 destroy(static_cast<__node_pointer>(__nd->__left_)); 1380 destroy(static_cast<__node_pointer>(__nd->__right_)); 1381 __node_allocator& __na = __node_alloc(); 1382 __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_)); 1383 __node_traits::deallocate(__na, __nd, 1); 1384 } 1385} 1386 1387template <class _Tp, class _Compare, class _Allocator> 1388void 1389__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1390 _NOEXCEPT_( 1391 __is_nothrow_swappable<value_compare>::value 1392#if _LIBCPP_STD_VER <= 11 1393 && (!__node_traits::propagate_on_container_swap::value || 1394 __is_nothrow_swappable<__node_allocator>::value) 1395#endif 1396 ) 1397{ 1398 using _VSTD::swap; 1399 swap(__begin_node_, __t.__begin_node_); 1400 swap(__pair1_.first(), __t.__pair1_.first()); 1401 __swap_allocator(__node_alloc(), __t.__node_alloc()); 1402 __pair3_.swap(__t.__pair3_); 1403 if (size() == 0) 1404 __begin_node() = __end_node(); 1405 else 1406 __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1407 if (__t.size() == 0) 1408 __t.__begin_node() = __t.__end_node(); 1409 else 1410 __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node()); 1411} 1412 1413template <class _Tp, class _Compare, class _Allocator> 1414void 1415__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 1416{ 1417 destroy(__root()); 1418 size() = 0; 1419 __begin_node() = __end_node(); 1420 __end_node()->__left_ = nullptr; 1421} 1422 1423// Find lower_bound place to insert 1424// Set __parent to parent of null leaf 1425// Return reference to null leaf 1426template <class _Tp, class _Compare, class _Allocator> 1427typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1428__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent, 1429 const value_type& __v) 1430{ 1431 __node_pointer __nd = __root(); 1432 if (__nd != nullptr) 1433 { 1434 while (true) 1435 { 1436 if (value_comp()(__nd->__value_, __v)) 1437 { 1438 if (__nd->__right_ != nullptr) 1439 __nd = static_cast<__node_pointer>(__nd->__right_); 1440 else 1441 { 1442 __parent = static_cast<__node_base_pointer>(__nd); 1443 return __parent->__right_; 1444 } 1445 } 1446 else 1447 { 1448 if (__nd->__left_ != nullptr) 1449 __nd = static_cast<__node_pointer>(__nd->__left_); 1450 else 1451 { 1452 __parent = static_cast<__node_base_pointer>(__nd); 1453 return __parent->__left_; 1454 } 1455 } 1456 } 1457 } 1458 __parent = static_cast<__node_base_pointer>(__end_node()); 1459 return __parent->__left_; 1460} 1461 1462// Find upper_bound place to insert 1463// Set __parent to parent of null leaf 1464// Return reference to null leaf 1465template <class _Tp, class _Compare, class _Allocator> 1466typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1467__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent, 1468 const value_type& __v) 1469{ 1470 __node_pointer __nd = __root(); 1471 if (__nd != nullptr) 1472 { 1473 while (true) 1474 { 1475 if (value_comp()(__v, __nd->__value_)) 1476 { 1477 if (__nd->__left_ != nullptr) 1478 __nd = static_cast<__node_pointer>(__nd->__left_); 1479 else 1480 { 1481 __parent = static_cast<__node_base_pointer>(__nd); 1482 return __parent->__left_; 1483 } 1484 } 1485 else 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 } 1496 } 1497 __parent = static_cast<__node_base_pointer>(__end_node()); 1498 return __parent->__left_; 1499} 1500 1501// Find leaf place to insert closest to __hint 1502// First check prior to __hint. 1503// Next check after __hint. 1504// Next do O(log N) search. 1505// Set __parent to parent of null leaf 1506// Return reference to null leaf 1507template <class _Tp, class _Compare, class _Allocator> 1508typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1509__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 1510 typename __node_base::pointer& __parent, 1511 const value_type& __v) 1512{ 1513 if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1514 { 1515 // __v <= *__hint 1516 const_iterator __prior = __hint; 1517 if (__prior == begin() || !value_comp()(__v, *--__prior)) 1518 { 1519 // *prev(__hint) <= __v <= *__hint 1520 if (__hint.__ptr_->__left_ == nullptr) 1521 { 1522 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1523 return __parent->__left_; 1524 } 1525 else 1526 { 1527 __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1528 return __parent->__right_; 1529 } 1530 } 1531 // __v < *prev(__hint) 1532 return __find_leaf_high(__parent, __v); 1533 } 1534 // else __v > *__hint 1535 return __find_leaf_low(__parent, __v); 1536} 1537 1538// Find place to insert if __v doesn't exist 1539// Set __parent to parent of null leaf 1540// Return reference to null leaf 1541// If __v exists, set parent to node of __v and return reference to node of __v 1542template <class _Tp, class _Compare, class _Allocator> 1543template <class _Key> 1544typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1545__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent, 1546 const _Key& __v) 1547{ 1548 __node_pointer __nd = __root(); 1549 if (__nd != nullptr) 1550 { 1551 while (true) 1552 { 1553 if (value_comp()(__v, __nd->__value_)) 1554 { 1555 if (__nd->__left_ != nullptr) 1556 __nd = static_cast<__node_pointer>(__nd->__left_); 1557 else 1558 { 1559 __parent = static_cast<__node_base_pointer>(__nd); 1560 return __parent->__left_; 1561 } 1562 } 1563 else if (value_comp()(__nd->__value_, __v)) 1564 { 1565 if (__nd->__right_ != nullptr) 1566 __nd = static_cast<__node_pointer>(__nd->__right_); 1567 else 1568 { 1569 __parent = static_cast<__node_base_pointer>(__nd); 1570 return __parent->__right_; 1571 } 1572 } 1573 else 1574 { 1575 __parent = static_cast<__node_base_pointer>(__nd); 1576 return __parent; 1577 } 1578 } 1579 } 1580 __parent = static_cast<__node_base_pointer>(__end_node()); 1581 return __parent->__left_; 1582} 1583 1584// Find place to insert if __v doesn't exist 1585// First check prior to __hint. 1586// Next check after __hint. 1587// Next do O(log N) search. 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(const_iterator __hint, 1595 typename __node_base::pointer& __parent, 1596 const _Key& __v) 1597{ 1598 if (__hint == end() || value_comp()(__v, *__hint)) // check before 1599 { 1600 // __v < *__hint 1601 const_iterator __prior = __hint; 1602 if (__prior == begin() || value_comp()(*--__prior, __v)) 1603 { 1604 // *prev(__hint) < __v < *__hint 1605 if (__hint.__ptr_->__left_ == nullptr) 1606 { 1607 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1608 return __parent->__left_; 1609 } 1610 else 1611 { 1612 __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1613 return __parent->__right_; 1614 } 1615 } 1616 // __v <= *prev(__hint) 1617 return __find_equal(__parent, __v); 1618 } 1619 else if (value_comp()(*__hint, __v)) // check after 1620 { 1621 // *__hint < __v 1622 const_iterator __next = _VSTD::next(__hint); 1623 if (__next == end() || value_comp()(__v, *__next)) 1624 { 1625 // *__hint < __v < *_VSTD::next(__hint) 1626 if (__hint.__ptr_->__right_ == nullptr) 1627 { 1628 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1629 return __parent->__right_; 1630 } 1631 else 1632 { 1633 __parent = static_cast<__node_base_pointer>(__next.__ptr_); 1634 return __parent->__left_; 1635 } 1636 } 1637 // *next(__hint) <= __v 1638 return __find_equal(__parent, __v); 1639 } 1640 // else __v == *__hint 1641 __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1642 return __parent; 1643} 1644 1645template <class _Tp, class _Compare, class _Allocator> 1646void 1647__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent, 1648 __node_base_pointer& __child, 1649 __node_base_pointer __new_node) 1650{ 1651 __new_node->__left_ = nullptr; 1652 __new_node->__right_ = nullptr; 1653 __new_node->__parent_ = __parent; 1654 __child = __new_node; 1655 if (__begin_node()->__left_ != nullptr) 1656 __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_); 1657 __tree_balance_after_insert(__end_node()->__left_, __child); 1658 ++size(); 1659} 1660 1661#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1662#ifndef _LIBCPP_HAS_NO_VARIADICS 1663 1664template <class _Tp, class _Compare, class _Allocator> 1665template <class ..._Args> 1666typename __tree<_Tp, _Compare, _Allocator>::__node_holder 1667__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 1668{ 1669 __node_allocator& __na = __node_alloc(); 1670 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1671 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1672 __h.get_deleter().__value_constructed = true; 1673 return __h; 1674} 1675 1676template <class _Tp, class _Compare, class _Allocator> 1677template <class... _Args> 1678pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1679__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args) 1680{ 1681 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1682 __node_base_pointer __parent; 1683 __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 1684 __node_pointer __r = static_cast<__node_pointer>(__child); 1685 bool __inserted = false; 1686 if (__child == nullptr) 1687 { 1688 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1689 __r = __h.release(); 1690 __inserted = true; 1691 } 1692 return pair<iterator, bool>(iterator(__r), __inserted); 1693} 1694 1695template <class _Tp, class _Compare, class _Allocator> 1696template <class... _Args> 1697typename __tree<_Tp, _Compare, _Allocator>::iterator 1698__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args) 1699{ 1700 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1701 __node_base_pointer __parent; 1702 __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_); 1703 __node_pointer __r = static_cast<__node_pointer>(__child); 1704 if (__child == nullptr) 1705 { 1706 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1707 __r = __h.release(); 1708 } 1709 return iterator(__r); 1710} 1711 1712template <class _Tp, class _Compare, class _Allocator> 1713template <class... _Args> 1714typename __tree<_Tp, _Compare, _Allocator>::iterator 1715__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 1716{ 1717 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1718 __node_base_pointer __parent; 1719 __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1720 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1721 return iterator(static_cast<__node_pointer>(__h.release())); 1722} 1723 1724template <class _Tp, class _Compare, class _Allocator> 1725template <class... _Args> 1726typename __tree<_Tp, _Compare, _Allocator>::iterator 1727__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 1728 _Args&&... __args) 1729{ 1730 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1731 __node_base_pointer __parent; 1732 __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1733 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1734 return iterator(static_cast<__node_pointer>(__h.release())); 1735} 1736 1737#endif // _LIBCPP_HAS_NO_VARIADICS 1738 1739template <class _Tp, class _Compare, class _Allocator> 1740pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1741__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v) 1742{ 1743 __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); 1744 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1745 if (__r.second) 1746 __h.release(); 1747 return __r; 1748} 1749 1750template <class _Tp, class _Compare, class _Allocator> 1751typename __tree<_Tp, _Compare, _Allocator>::iterator 1752__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v) 1753{ 1754 __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); 1755 iterator __r = __node_insert_unique(__p, __h.get()); 1756 if (__r.__ptr_ == __h.get()) 1757 __h.release(); 1758 return __r; 1759} 1760 1761template <class _Tp, class _Compare, class _Allocator> 1762template <class _Vp> 1763pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1764__tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) 1765{ 1766 __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1767 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1768 if (__r.second) 1769 __h.release(); 1770 return __r; 1771} 1772 1773template <class _Tp, class _Compare, class _Allocator> 1774template <class _Vp> 1775typename __tree<_Tp, _Compare, _Allocator>::iterator 1776__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v) 1777{ 1778 __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1779 iterator __r = __node_insert_unique(__p, __h.get()); 1780 if (__r.__ptr_ == __h.get()) 1781 __h.release(); 1782 return __r; 1783} 1784 1785template <class _Tp, class _Compare, class _Allocator> 1786typename __tree<_Tp, _Compare, _Allocator>::iterator 1787__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v) 1788{ 1789 __node_base_pointer __parent; 1790 __node_base_pointer& __child = __find_leaf_high(__parent, __v); 1791 __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); 1792 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1793 return iterator(__h.release()); 1794} 1795 1796template <class _Tp, class _Compare, class _Allocator> 1797typename __tree<_Tp, _Compare, _Allocator>::iterator 1798__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v) 1799{ 1800 __node_base_pointer __parent; 1801 __node_base_pointer& __child = __find_leaf(__p, __parent, __v); 1802 __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); 1803 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1804 return iterator(__h.release()); 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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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 _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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, static_cast<__node_base_pointer>(__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 = __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 __tree_remove(__end_node()->__left_, 1968 static_cast<__node_base_pointer>(__np)); 1969 __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p))); 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(__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 __node_const_pointer __result = __end_node(); 2057 __node_const_pointer __rt = __root(); 2058 while (__rt != nullptr) 2059 { 2060 if (value_comp()(__k, __rt->__value_)) 2061 { 2062 __result = __rt; 2063 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2064 } 2065 else if (value_comp()(__rt->__value_, __k)) 2066 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2067 else 2068 return _VSTD::distance( 2069 __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2070 __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result) 2071 ); 2072 } 2073 return 0; 2074} 2075 2076template <class _Tp, class _Compare, class _Allocator> 2077template <class _Key> 2078typename __tree<_Tp, _Compare, _Allocator>::iterator 2079__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2080 __node_pointer __root, 2081 __node_pointer __result) 2082{ 2083 while (__root != nullptr) 2084 { 2085 if (!value_comp()(__root->__value_, __v)) 2086 { 2087 __result = __root; 2088 __root = static_cast<__node_pointer>(__root->__left_); 2089 } 2090 else 2091 __root = static_cast<__node_pointer>(__root->__right_); 2092 } 2093 return iterator(__result); 2094} 2095 2096template <class _Tp, class _Compare, class _Allocator> 2097template <class _Key> 2098typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2099__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2100 __node_const_pointer __root, 2101 __node_const_pointer __result) const 2102{ 2103 while (__root != nullptr) 2104 { 2105 if (!value_comp()(__root->__value_, __v)) 2106 { 2107 __result = __root; 2108 __root = static_cast<__node_const_pointer>(__root->__left_); 2109 } 2110 else 2111 __root = static_cast<__node_const_pointer>(__root->__right_); 2112 } 2113 return const_iterator(__result); 2114} 2115 2116template <class _Tp, class _Compare, class _Allocator> 2117template <class _Key> 2118typename __tree<_Tp, _Compare, _Allocator>::iterator 2119__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2120 __node_pointer __root, 2121 __node_pointer __result) 2122{ 2123 while (__root != nullptr) 2124 { 2125 if (value_comp()(__v, __root->__value_)) 2126 { 2127 __result = __root; 2128 __root = static_cast<__node_pointer>(__root->__left_); 2129 } 2130 else 2131 __root = static_cast<__node_pointer>(__root->__right_); 2132 } 2133 return iterator(__result); 2134} 2135 2136template <class _Tp, class _Compare, class _Allocator> 2137template <class _Key> 2138typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2139__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2140 __node_const_pointer __root, 2141 __node_const_pointer __result) const 2142{ 2143 while (__root != nullptr) 2144 { 2145 if (value_comp()(__v, __root->__value_)) 2146 { 2147 __result = __root; 2148 __root = static_cast<__node_const_pointer>(__root->__left_); 2149 } 2150 else 2151 __root = static_cast<__node_const_pointer>(__root->__right_); 2152 } 2153 return const_iterator(__result); 2154} 2155 2156template <class _Tp, class _Compare, class _Allocator> 2157template <class _Key> 2158pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2159 typename __tree<_Tp, _Compare, _Allocator>::iterator> 2160__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 2161{ 2162 typedef pair<iterator, iterator> _Pp; 2163 __node_pointer __result = __end_node(); 2164 __node_pointer __rt = __root(); 2165 while (__rt != nullptr) 2166 { 2167 if (value_comp()(__k, __rt->__value_)) 2168 { 2169 __result = __rt; 2170 __rt = static_cast<__node_pointer>(__rt->__left_); 2171 } 2172 else if (value_comp()(__rt->__value_, __k)) 2173 __rt = static_cast<__node_pointer>(__rt->__right_); 2174 else 2175 return _Pp(iterator(__rt), 2176 iterator( 2177 __rt->__right_ != nullptr ? 2178 static_cast<__node_pointer>(__tree_min(__rt->__right_)) 2179 : __result)); 2180 } 2181 return _Pp(iterator(__result), iterator(__result)); 2182} 2183 2184template <class _Tp, class _Compare, class _Allocator> 2185template <class _Key> 2186pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2187 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2188__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 2189{ 2190 typedef pair<const_iterator, const_iterator> _Pp; 2191 __node_const_pointer __result = __end_node(); 2192 __node_const_pointer __rt = __root(); 2193 while (__rt != nullptr) 2194 { 2195 if (value_comp()(__k, __rt->__value_)) 2196 { 2197 __result = __rt; 2198 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2199 } 2200 else if (value_comp()(__rt->__value_, __k)) 2201 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2202 else 2203 return _Pp(const_iterator(__rt), 2204 const_iterator( 2205 __rt->__right_ != nullptr ? 2206 static_cast<__node_const_pointer>(__tree_min(__rt->__right_)) 2207 : __result)); 2208 } 2209 return _Pp(const_iterator(__result), const_iterator(__result)); 2210} 2211 2212template <class _Tp, class _Compare, class _Allocator> 2213template <class _Key> 2214pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2215 typename __tree<_Tp, _Compare, _Allocator>::iterator> 2216__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 2217{ 2218 typedef pair<iterator, iterator> _Pp; 2219 __node_pointer __result = __end_node(); 2220 __node_pointer __rt = __root(); 2221 while (__rt != nullptr) 2222 { 2223 if (value_comp()(__k, __rt->__value_)) 2224 { 2225 __result = __rt; 2226 __rt = static_cast<__node_pointer>(__rt->__left_); 2227 } 2228 else if (value_comp()(__rt->__value_, __k)) 2229 __rt = static_cast<__node_pointer>(__rt->__right_); 2230 else 2231 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt), 2232 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2233 } 2234 return _Pp(iterator(__result), iterator(__result)); 2235} 2236 2237template <class _Tp, class _Compare, class _Allocator> 2238template <class _Key> 2239pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2240 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2241__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 2242{ 2243 typedef pair<const_iterator, const_iterator> _Pp; 2244 __node_const_pointer __result = __end_node(); 2245 __node_const_pointer __rt = __root(); 2246 while (__rt != nullptr) 2247 { 2248 if (value_comp()(__k, __rt->__value_)) 2249 { 2250 __result = __rt; 2251 __rt = static_cast<__node_const_pointer>(__rt->__left_); 2252 } 2253 else if (value_comp()(__rt->__value_, __k)) 2254 __rt = static_cast<__node_const_pointer>(__rt->__right_); 2255 else 2256 return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2257 __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)); 2258 } 2259 return _Pp(const_iterator(__result), const_iterator(__result)); 2260} 2261 2262template <class _Tp, class _Compare, class _Allocator> 2263typename __tree<_Tp, _Compare, _Allocator>::__node_holder 2264__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 2265{ 2266 __node_pointer __np = __p.__ptr_; 2267 if (__begin_node() == __np) 2268 { 2269 if (__np->__right_ != nullptr) 2270 __begin_node() = static_cast<__node_pointer>(__np->__right_); 2271 else 2272 __begin_node() = static_cast<__node_pointer>(__np->__parent_); 2273 } 2274 --size(); 2275 __tree_remove(__end_node()->__left_, 2276 static_cast<__node_base_pointer>(__np)); 2277 return __node_holder(__np, _Dp(__node_alloc(), true)); 2278} 2279 2280template <class _Tp, class _Compare, class _Allocator> 2281inline _LIBCPP_INLINE_VISIBILITY 2282void 2283swap(__tree<_Tp, _Compare, _Allocator>& __x, 2284 __tree<_Tp, _Compare, _Allocator>& __y) 2285 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2286{ 2287 __x.swap(__y); 2288} 2289 2290_LIBCPP_END_NAMESPACE_STD 2291 2292#endif // _LIBCPP___TREE 2293