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