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