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