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