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, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0> 551 _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) { 552 return __t; 553 } 554 555 _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { 556 return std::addressof(__n.__get_value()); 557 } 558 559 _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); } 560}; 561 562template <class _VoidPtr> 563struct __tree_node_base_types { 564 typedef _VoidPtr __void_pointer; 565 566 typedef __tree_node_base<__void_pointer> __node_base_type; 567 typedef __rebind_pointer_t<_VoidPtr, __node_base_type> __node_base_pointer; 568 569 typedef __tree_end_node<__node_base_pointer> __end_node_type; 570 typedef __rebind_pointer_t<_VoidPtr, __end_node_type> __end_node_pointer; 571#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) 572 typedef __end_node_pointer __parent_pointer; 573#else 574 typedef __conditional_t< is_pointer<__end_node_pointer>::value, __end_node_pointer, __node_base_pointer> 575 __parent_pointer; 576#endif 577 578private: 579 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value), 580 "_VoidPtr does not point to unqualified void type"); 581}; 582 583template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>, bool = _KVTypes::__is_map> 584struct __tree_map_pointer_types {}; 585 586template <class _Tp, class _AllocPtr, class _KVTypes> 587struct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> { 588 typedef typename _KVTypes::__map_value_type _Mv; 589 typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer; 590 typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer; 591}; 592 593template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type> 594struct __tree_node_types; 595 596template <class _NodePtr, class _Tp, class _VoidPtr> 597struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> > 598 : public __tree_node_base_types<_VoidPtr>, __tree_key_value_types<_Tp>, __tree_map_pointer_types<_Tp, _VoidPtr> { 599 typedef __tree_node_base_types<_VoidPtr> __base; 600 typedef __tree_key_value_types<_Tp> __key_base; 601 typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base; 602 603public: 604 typedef typename pointer_traits<_NodePtr>::element_type __node_type; 605 typedef _NodePtr __node_pointer; 606 607 typedef _Tp __node_value_type; 608 typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer; 609 typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer; 610#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) 611 typedef typename __base::__end_node_pointer __iter_pointer; 612#else 613 typedef __conditional_t< is_pointer<__node_pointer>::value, typename __base::__end_node_pointer, __node_pointer> 614 __iter_pointer; 615#endif 616 617private: 618 static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const"); 619 static_assert((is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value), 620 "_VoidPtr does not rebind to _NodePtr."); 621}; 622 623template <class _ValueTp, class _VoidPtr> 624struct __make_tree_node_types { 625 typedef __rebind_pointer_t<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> > _NodePtr; 626 typedef __tree_node_types<_NodePtr> type; 627}; 628 629// node 630 631template <class _Pointer> 632class __tree_end_node { 633public: 634 typedef _Pointer pointer; 635 pointer __left_; 636 637 _LIBCPP_HIDE_FROM_ABI __tree_end_node() _NOEXCEPT : __left_() {} 638}; 639 640template <class _VoidPtr> 641class _LIBCPP_STANDALONE_DEBUG __tree_node_base : public __tree_node_base_types<_VoidPtr>::__end_node_type { 642 typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes; 643 644public: 645 typedef typename _NodeBaseTypes::__node_base_pointer pointer; 646 typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer; 647 648 pointer __right_; 649 __parent_pointer __parent_; 650 bool __is_black_; 651 652 _LIBCPP_HIDE_FROM_ABI pointer __parent_unsafe() const { return static_cast<pointer>(__parent_); } 653 654 _LIBCPP_HIDE_FROM_ABI void __set_parent(pointer __p) { __parent_ = static_cast<__parent_pointer>(__p); } 655 656private: 657 ~__tree_node_base() = delete; 658 __tree_node_base(__tree_node_base const&) = delete; 659 __tree_node_base& operator=(__tree_node_base const&) = delete; 660}; 661 662template <class _Tp, class _VoidPtr> 663class _LIBCPP_STANDALONE_DEBUG __tree_node : public __tree_node_base<_VoidPtr> { 664public: 665 typedef _Tp __node_value_type; 666 667 __node_value_type __value_; 668 669 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; } 670 671private: 672 ~__tree_node() = delete; 673 __tree_node(__tree_node const&) = delete; 674 __tree_node& operator=(__tree_node const&) = delete; 675}; 676 677template <class _Allocator> 678class __tree_node_destructor { 679 typedef _Allocator allocator_type; 680 typedef allocator_traits<allocator_type> __alloc_traits; 681 682public: 683 typedef typename __alloc_traits::pointer pointer; 684 685private: 686 typedef __tree_node_types<pointer> _NodeTypes; 687 allocator_type& __na_; 688 689public: 690 bool __value_constructed; 691 692 _LIBCPP_HIDE_FROM_ABI __tree_node_destructor(const __tree_node_destructor&) = default; 693 __tree_node_destructor& operator=(const __tree_node_destructor&) = delete; 694 695 _LIBCPP_HIDE_FROM_ABI explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT 696 : __na_(__na), 697 __value_constructed(__val) {} 698 699 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 700 if (__value_constructed) 701 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 702 if (__p) 703 __alloc_traits::deallocate(__na_, __p, 1); 704 } 705 706 template <class> 707 friend class __map_node_destructor; 708}; 709 710#if _LIBCPP_STD_VER >= 17 711template <class _NodeType, class _Alloc> 712struct __generic_container_node_destructor; 713template <class _Tp, class _VoidPtr, class _Alloc> 714struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> : __tree_node_destructor<_Alloc> { 715 using __tree_node_destructor<_Alloc>::__tree_node_destructor; 716}; 717#endif 718 719template <class _Tp, class _NodePtr, class _DiffType> 720class _LIBCPP_TEMPLATE_VIS __tree_iterator { 721 typedef __tree_node_types<_NodePtr> _NodeTypes; 722 typedef _NodePtr __node_pointer; 723 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 724 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 725 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 726 typedef pointer_traits<__node_pointer> __pointer_traits; 727 728 __iter_pointer __ptr_; 729 730public: 731 typedef bidirectional_iterator_tag iterator_category; 732 typedef _Tp value_type; 733 typedef _DiffType difference_type; 734 typedef value_type& reference; 735 typedef typename _NodeTypes::__node_value_type_pointer pointer; 736 737 _LIBCPP_HIDE_FROM_ABI __tree_iterator() _NOEXCEPT 738#if _LIBCPP_STD_VER >= 14 739 : __ptr_(nullptr) 740#endif 741 { 742 } 743 744 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; } 745 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); } 746 747 _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator++() { 748 __ptr_ = static_cast<__iter_pointer>( 749 std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 750 return *this; 751 } 752 _LIBCPP_HIDE_FROM_ABI __tree_iterator operator++(int) { 753 __tree_iterator __t(*this); 754 ++(*this); 755 return __t; 756 } 757 758 _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator--() { 759 __ptr_ = static_cast<__iter_pointer>( 760 std::__tree_prev_iter<__node_base_pointer>(static_cast<__end_node_pointer>(__ptr_))); 761 return *this; 762 } 763 _LIBCPP_HIDE_FROM_ABI __tree_iterator operator--(int) { 764 __tree_iterator __t(*this); 765 --(*this); 766 return __t; 767 } 768 769 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) { 770 return __x.__ptr_ == __y.__ptr_; 771 } 772 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) { 773 return !(__x == __y); 774 } 775 776private: 777 _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 778 _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 779 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 780 template <class, class, class> 781 friend class __tree; 782 template <class, class, class> 783 friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 784 template <class> 785 friend class _LIBCPP_TEMPLATE_VIS __map_iterator; 786 template <class, class, class, class> 787 friend class _LIBCPP_TEMPLATE_VIS map; 788 template <class, class, class, class> 789 friend class _LIBCPP_TEMPLATE_VIS multimap; 790 template <class, class, class> 791 friend class _LIBCPP_TEMPLATE_VIS set; 792 template <class, class, class> 793 friend class _LIBCPP_TEMPLATE_VIS multiset; 794}; 795 796template <class _Tp, class _NodePtr, class _DiffType> 797class _LIBCPP_TEMPLATE_VIS __tree_const_iterator { 798 typedef __tree_node_types<_NodePtr> _NodeTypes; 799 typedef typename _NodeTypes::__node_pointer __node_pointer; 800 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 801 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 802 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 803 typedef pointer_traits<__node_pointer> __pointer_traits; 804 805 __iter_pointer __ptr_; 806 807public: 808 typedef bidirectional_iterator_tag iterator_category; 809 typedef _Tp value_type; 810 typedef _DiffType difference_type; 811 typedef const value_type& reference; 812 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 813 814 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator() _NOEXCEPT 815#if _LIBCPP_STD_VER >= 14 816 : __ptr_(nullptr) 817#endif 818 { 819 } 820 821private: 822 typedef __tree_iterator<value_type, __node_pointer, difference_type> __non_const_iterator; 823 824public: 825 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT : __ptr_(__p.__ptr_) {} 826 827 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; } 828 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); } 829 830 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator++() { 831 __ptr_ = static_cast<__iter_pointer>( 832 std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 833 return *this; 834 } 835 836 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator++(int) { 837 __tree_const_iterator __t(*this); 838 ++(*this); 839 return __t; 840 } 841 842 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator--() { 843 __ptr_ = static_cast<__iter_pointer>( 844 std::__tree_prev_iter<__node_base_pointer>(static_cast<__end_node_pointer>(__ptr_))); 845 return *this; 846 } 847 848 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator--(int) { 849 __tree_const_iterator __t(*this); 850 --(*this); 851 return __t; 852 } 853 854 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) { 855 return __x.__ptr_ == __y.__ptr_; 856 } 857 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) { 858 return !(__x == __y); 859 } 860 861private: 862 _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 863 _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 864 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 865 866 template <class, class, class> 867 friend class __tree; 868 template <class, class, class, class> 869 friend class _LIBCPP_TEMPLATE_VIS map; 870 template <class, class, class, class> 871 friend class _LIBCPP_TEMPLATE_VIS multimap; 872 template <class, class, class> 873 friend class _LIBCPP_TEMPLATE_VIS set; 874 template <class, class, class> 875 friend class _LIBCPP_TEMPLATE_VIS multiset; 876 template <class> 877 friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 878}; 879 880template <class _Tp, class _Compare> 881#ifndef _LIBCPP_CXX03_LANG 882_LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, 883 "the specified comparator type does not provide a viable const call operator") 884#endif 885int __diagnose_non_const_comparator(); 886 887template <class _Tp, class _Compare, class _Allocator> 888class __tree { 889public: 890 typedef _Tp value_type; 891 typedef _Compare value_compare; 892 typedef _Allocator allocator_type; 893 894private: 895 typedef allocator_traits<allocator_type> __alloc_traits; 896 typedef typename __make_tree_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes; 897 typedef typename _NodeTypes::key_type key_type; 898 899public: 900 typedef typename _NodeTypes::__node_value_type __node_value_type; 901 typedef typename _NodeTypes::__container_value_type __container_value_type; 902 903 typedef typename __alloc_traits::pointer pointer; 904 typedef typename __alloc_traits::const_pointer const_pointer; 905 typedef typename __alloc_traits::size_type size_type; 906 typedef typename __alloc_traits::difference_type difference_type; 907 908public: 909 typedef typename _NodeTypes::__void_pointer __void_pointer; 910 911 typedef typename _NodeTypes::__node_type __node; 912 typedef typename _NodeTypes::__node_pointer __node_pointer; 913 914 typedef typename _NodeTypes::__node_base_type __node_base; 915 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 916 917 typedef typename _NodeTypes::__end_node_type __end_node_t; 918 typedef typename _NodeTypes::__end_node_pointer __end_node_ptr; 919 920 typedef typename _NodeTypes::__parent_pointer __parent_pointer; 921 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 922 923 typedef __rebind_alloc<__alloc_traits, __node> __node_allocator; 924 typedef allocator_traits<__node_allocator> __node_traits; 925 926private: 927 // check for sane allocator pointer rebinding semantics. Rebinding the 928 // allocator for a new pointer type should be exactly the same as rebinding 929 // the pointer using 'pointer_traits'. 930 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), 931 "Allocator does not rebind pointers in a sane manner."); 932 typedef __rebind_alloc<__node_traits, __node_base> __node_base_allocator; 933 typedef allocator_traits<__node_base_allocator> __node_base_traits; 934 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), 935 "Allocator does not rebind pointers in a sane manner."); 936 937private: 938 __iter_pointer __begin_node_; 939 __compressed_pair<__end_node_t, __node_allocator> __pair1_; 940 __compressed_pair<size_type, value_compare> __pair3_; 941 942public: 943 _LIBCPP_HIDE_FROM_ABI __iter_pointer __end_node() _NOEXCEPT { 944 return static_cast<__iter_pointer>(pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())); 945 } 946 _LIBCPP_HIDE_FROM_ABI __iter_pointer __end_node() const _NOEXCEPT { 947 return static_cast<__iter_pointer>( 948 pointer_traits<__end_node_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first()))); 949 } 950 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __pair1_.second(); } 951 952private: 953 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __pair1_.second(); } 954 _LIBCPP_HIDE_FROM_ABI __iter_pointer& __begin_node() _NOEXCEPT { return __begin_node_; } 955 _LIBCPP_HIDE_FROM_ABI const __iter_pointer& __begin_node() const _NOEXCEPT { return __begin_node_; } 956 957public: 958 _LIBCPP_HIDE_FROM_ABI allocator_type __alloc() const _NOEXCEPT { return allocator_type(__node_alloc()); } 959 960private: 961 _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __pair3_.first(); } 962 963public: 964 _LIBCPP_HIDE_FROM_ABI const size_type& size() const _NOEXCEPT { return __pair3_.first(); } 965 _LIBCPP_HIDE_FROM_ABI value_compare& value_comp() _NOEXCEPT { return __pair3_.second(); } 966 _LIBCPP_HIDE_FROM_ABI const value_compare& value_comp() const _NOEXCEPT { return __pair3_.second(); } 967 968public: 969 _LIBCPP_HIDE_FROM_ABI __node_pointer __root() const _NOEXCEPT { 970 return static_cast<__node_pointer>(__end_node()->__left_); 971 } 972 973 _LIBCPP_HIDE_FROM_ABI __node_base_pointer* __root_ptr() const _NOEXCEPT { 974 return std::addressof(__end_node()->__left_); 975 } 976 977 typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 978 typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 979 980 _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp) _NOEXCEPT_( 981 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value); 982 _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a); 983 _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a); 984 _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t); 985 _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t); 986 template <class _ForwardIterator> 987 _LIBCPP_HIDE_FROM_ABI void __assign_unique(_ForwardIterator __first, _ForwardIterator __last); 988 template <class _InputIterator> 989 _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last); 990 _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t) _NOEXCEPT_( 991 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value); 992 _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a); 993 _LIBCPP_HIDE_FROM_ABI __tree& operator=(__tree&& __t) _NOEXCEPT_( 994 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<value_compare>::value&& 995 is_nothrow_move_assignable<__node_allocator>::value); 996 _LIBCPP_HIDE_FROM_ABI ~__tree(); 997 998 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__begin_node()); } 999 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__begin_node()); } 1000 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_node()); } 1001 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_node()); } 1002 1003 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { 1004 return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max()); 1005 } 1006 1007 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; 1008 1009 _LIBCPP_HIDE_FROM_ABI void swap(__tree& __t) 1010#if _LIBCPP_STD_VER <= 11 1011 _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value && 1012 (!__node_traits::propagate_on_container_swap::value || 1013 __is_nothrow_swappable<__node_allocator>::value)); 1014#else 1015 _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value); 1016#endif 1017 1018 template <class _Key, class... _Args> 1019 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args); 1020 template <class _Key, class... _Args> 1021 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); 1022 1023 template <class... _Args> 1024 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 1025 1026 template <class... _Args> 1027 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); 1028 1029 template <class... _Args> 1030 _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args); 1031 1032 template <class... _Args> 1033 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 1034 1035 template <class _Pp> 1036 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) { 1037 return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); 1038 } 1039 1040 template <class _First, 1041 class _Second, 1042 __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0> 1043 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) { 1044 return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s)); 1045 } 1046 1047 template <class... _Args> 1048 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) { 1049 return __emplace_unique_impl(std::forward<_Args>(__args)...); 1050 } 1051 1052 template <class _Pp> 1053 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 1054 return __emplace_unique_impl(std::forward<_Pp>(__x)); 1055 } 1056 1057 template <class _Pp> 1058 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 1059 return __emplace_unique_key_args(__x, std::forward<_Pp>(__x)); 1060 } 1061 1062 template <class _Pp> 1063 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 1064 return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x)); 1065 } 1066 1067 template <class _Pp> 1068 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { 1069 return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); 1070 } 1071 1072 template <class _First, 1073 class _Second, 1074 __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0> 1075 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { 1076 return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first; 1077 } 1078 1079 template <class... _Args> 1080 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { 1081 return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...); 1082 } 1083 1084 template <class _Pp> 1085 _LIBCPP_HIDE_FROM_ABI iterator 1086 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { 1087 return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x)); 1088 } 1089 1090 template <class _Pp> 1091 _LIBCPP_HIDE_FROM_ABI iterator 1092 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { 1093 return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first; 1094 } 1095 1096 template <class _Pp> 1097 _LIBCPP_HIDE_FROM_ABI iterator 1098 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { 1099 return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first; 1100 } 1101 1102 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __v) { 1103 return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); 1104 } 1105 1106 _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { 1107 return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first; 1108 } 1109 1110 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __v) { 1111 return __emplace_unique_key_args(_NodeTypes::__get_key(__v), std::move(__v)); 1112 } 1113 1114 _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { 1115 return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), std::move(__v)).first; 1116 } 1117 1118 template <class _Vp, __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value, int> = 0> 1119 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Vp&& __v) { 1120 return __emplace_unique(std::forward<_Vp>(__v)); 1121 } 1122 1123 template <class _Vp, __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value, int> = 0> 1124 _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, _Vp&& __v) { 1125 return __emplace_hint_unique(__p, std::forward<_Vp>(__v)); 1126 } 1127 1128 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(__container_value_type&& __v) { 1129 return __emplace_multi(std::move(__v)); 1130 } 1131 1132 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, __container_value_type&& __v) { 1133 return __emplace_hint_multi(__p, std::move(__v)); 1134 } 1135 1136 template <class _Vp> 1137 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Vp&& __v) { 1138 return __emplace_multi(std::forward<_Vp>(__v)); 1139 } 1140 1141 template <class _Vp> 1142 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Vp&& __v) { 1143 return __emplace_hint_multi(__p, std::forward<_Vp>(__v)); 1144 } 1145 1146 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> 1147 __node_assign_unique(const __container_value_type& __v, __node_pointer __dest); 1148 1149 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd); 1150 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 1151 1152 _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT; 1153 1154#if _LIBCPP_STD_VER >= 17 1155 template <class _NodeHandle, class _InsertReturnType> 1156 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); 1157 template <class _NodeHandle> 1158 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); 1159 template <class _Tree> 1160 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Tree& __source); 1161 1162 template <class _NodeHandle> 1163 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&&); 1164 template <class _NodeHandle> 1165 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); 1166 template <class _Tree> 1167 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Tree& __source); 1168 1169 template <class _NodeHandle> 1170 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const&); 1171 template <class _NodeHandle> 1172 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator); 1173#endif 1174 1175 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p); 1176 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l); 1177 template <class _Key> 1178 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k); 1179 template <class _Key> 1180 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k); 1181 1182 _LIBCPP_HIDE_FROM_ABI void 1183 __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT; 1184 1185 template <class _Key> 1186 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __v); 1187 template <class _Key> 1188 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __v) const; 1189 1190 template <class _Key> 1191 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const; 1192 template <class _Key> 1193 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const; 1194 1195 template <class _Key> 1196 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Key& __v) { 1197 return __lower_bound(__v, __root(), __end_node()); 1198 } 1199 template <class _Key> 1200 _LIBCPP_HIDE_FROM_ABI iterator __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result); 1201 template <class _Key> 1202 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Key& __v) const { 1203 return __lower_bound(__v, __root(), __end_node()); 1204 } 1205 template <class _Key> 1206 _LIBCPP_HIDE_FROM_ABI const_iterator 1207 __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const; 1208 template <class _Key> 1209 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Key& __v) { 1210 return __upper_bound(__v, __root(), __end_node()); 1211 } 1212 template <class _Key> 1213 _LIBCPP_HIDE_FROM_ABI iterator __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result); 1214 template <class _Key> 1215 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Key& __v) const { 1216 return __upper_bound(__v, __root(), __end_node()); 1217 } 1218 template <class _Key> 1219 _LIBCPP_HIDE_FROM_ABI const_iterator 1220 __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const; 1221 template <class _Key> 1222 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k); 1223 template <class _Key> 1224 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const; 1225 1226 template <class _Key> 1227 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k); 1228 template <class _Key> 1229 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const; 1230 1231 typedef __tree_node_destructor<__node_allocator> _Dp; 1232 typedef unique_ptr<__node, _Dp> __node_holder; 1233 1234 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT; 1235 1236private: 1237 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_low(__parent_pointer& __parent, const key_type& __v); 1238 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_high(__parent_pointer& __parent, const key_type& __v); 1239 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& 1240 __find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v); 1241 // FIXME: Make this function const qualified. Unfortunately doing so 1242 // breaks existing code which uses non-const callable comparators. 1243 template <class _Key> 1244 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v); 1245 template <class _Key> 1246 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v) const { 1247 return const_cast<__tree*>(this)->__find_equal(__parent, __v); 1248 } 1249 template <class _Key> 1250 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& 1251 __find_equal(const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v); 1252 1253 template <class... _Args> 1254 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args); 1255 1256 // TODO: Make this _LIBCPP_HIDE_FROM_ABI 1257 _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT; 1258 1259 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t) { 1260 __copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>()); 1261 } 1262 1263 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t, true_type) { 1264 if (__node_alloc() != __t.__node_alloc()) 1265 clear(); 1266 __node_alloc() = __t.__node_alloc(); 1267 } 1268 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree&, false_type) {} 1269 1270 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type); 1271 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type) _NOEXCEPT_( 1272 is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value); 1273 1274 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t) 1275 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 1276 is_nothrow_move_assignable<__node_allocator>::value) { 1277 __move_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); 1278 } 1279 1280 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t, true_type) 1281 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) { 1282 __node_alloc() = std::move(__t.__node_alloc()); 1283 } 1284 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {} 1285 1286 struct _DetachedTreeCache { 1287 _LIBCPP_HIDE_FROM_ABI explicit _DetachedTreeCache(__tree* __t) _NOEXCEPT 1288 : __t_(__t), 1289 __cache_root_(__detach_from_tree(__t)) { 1290 __advance(); 1291 } 1292 1293 _LIBCPP_HIDE_FROM_ABI __node_pointer __get() const _NOEXCEPT { return __cache_elem_; } 1294 1295 _LIBCPP_HIDE_FROM_ABI void __advance() _NOEXCEPT { 1296 __cache_elem_ = __cache_root_; 1297 if (__cache_root_) { 1298 __cache_root_ = __detach_next(__cache_root_); 1299 } 1300 } 1301 1302 _LIBCPP_HIDE_FROM_ABI ~_DetachedTreeCache() { 1303 __t_->destroy(__cache_elem_); 1304 if (__cache_root_) { 1305 while (__cache_root_->__parent_ != nullptr) 1306 __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_); 1307 __t_->destroy(__cache_root_); 1308 } 1309 } 1310 1311 _DetachedTreeCache(_DetachedTreeCache const&) = delete; 1312 _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete; 1313 1314 private: 1315 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_from_tree(__tree* __t) _NOEXCEPT; 1316 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_next(__node_pointer) _NOEXCEPT; 1317 1318 __tree* __t_; 1319 __node_pointer __cache_root_; 1320 __node_pointer __cache_elem_; 1321 }; 1322 1323 template <class, class, class, class> 1324 friend class _LIBCPP_TEMPLATE_VIS map; 1325 template <class, class, class, class> 1326 friend class _LIBCPP_TEMPLATE_VIS multimap; 1327}; 1328 1329template <class _Tp, class _Compare, class _Allocator> 1330__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) _NOEXCEPT_( 1331 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value) 1332 : __pair3_(0, __comp) { 1333 __begin_node() = __end_node(); 1334} 1335 1336template <class _Tp, class _Compare, class _Allocator> 1337__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1338 : __begin_node_(__iter_pointer()), 1339 __pair1_(__default_init_tag(), __node_allocator(__a)), 1340 __pair3_(0, __default_init_tag()) { 1341 __begin_node() = __end_node(); 1342} 1343 1344template <class _Tp, class _Compare, class _Allocator> 1345__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a) 1346 : __begin_node_(__iter_pointer()), __pair1_(__default_init_tag(), __node_allocator(__a)), __pair3_(0, __comp) { 1347 __begin_node() = __end_node(); 1348} 1349 1350// Precondition: size() != 0 1351template <class _Tp, class _Compare, class _Allocator> 1352typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1353__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT { 1354 __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node()); 1355 __t->__begin_node() = __t->__end_node(); 1356 __t->__end_node()->__left_->__parent_ = nullptr; 1357 __t->__end_node()->__left_ = nullptr; 1358 __t->size() = 0; 1359 // __cache->__left_ == nullptr 1360 if (__cache->__right_ != nullptr) 1361 __cache = static_cast<__node_pointer>(__cache->__right_); 1362 // __cache->__left_ == nullptr 1363 // __cache->__right_ == nullptr 1364 return __cache; 1365} 1366 1367// Precondition: __cache != nullptr 1368// __cache->left_ == nullptr 1369// __cache->right_ == nullptr 1370// This is no longer a red-black tree 1371template <class _Tp, class _Compare, class _Allocator> 1372typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1373__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT { 1374 if (__cache->__parent_ == nullptr) 1375 return nullptr; 1376 if (std::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) { 1377 __cache->__parent_->__left_ = nullptr; 1378 __cache = static_cast<__node_pointer>(__cache->__parent_); 1379 if (__cache->__right_ == nullptr) 1380 return __cache; 1381 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__right_)); 1382 } 1383 // __cache is right child 1384 __cache->__parent_unsafe()->__right_ = nullptr; 1385 __cache = static_cast<__node_pointer>(__cache->__parent_); 1386 if (__cache->__left_ == nullptr) 1387 return __cache; 1388 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__left_)); 1389} 1390 1391template <class _Tp, class _Compare, class _Allocator> 1392__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) { 1393 if (this != std::addressof(__t)) { 1394 value_comp() = __t.value_comp(); 1395 __copy_assign_alloc(__t); 1396 __assign_multi(__t.begin(), __t.end()); 1397 } 1398 return *this; 1399} 1400 1401template <class _Tp, class _Compare, class _Allocator> 1402template <class _ForwardIterator> 1403void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) { 1404 typedef iterator_traits<_ForwardIterator> _ITraits; 1405 typedef typename _ITraits::value_type _ItValueType; 1406 static_assert((is_same<_ItValueType, __container_value_type>::value), 1407 "__assign_unique may only be called with the containers value type"); 1408 static_assert( 1409 __has_forward_iterator_category<_ForwardIterator>::value, "__assign_unique requires a forward iterator"); 1410 if (size() != 0) { 1411 _DetachedTreeCache __cache(this); 1412 for (; __cache.__get() != nullptr && __first != __last; ++__first) { 1413 if (__node_assign_unique(*__first, __cache.__get()).second) 1414 __cache.__advance(); 1415 } 1416 } 1417 for (; __first != __last; ++__first) 1418 __insert_unique(*__first); 1419} 1420 1421template <class _Tp, class _Compare, class _Allocator> 1422template <class _InputIterator> 1423void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) { 1424 typedef iterator_traits<_InputIterator> _ITraits; 1425 typedef typename _ITraits::value_type _ItValueType; 1426 static_assert( 1427 (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value), 1428 "__assign_multi may only be called with the containers value type" 1429 " or the nodes value type"); 1430 if (size() != 0) { 1431 _DetachedTreeCache __cache(this); 1432 for (; __cache.__get() && __first != __last; ++__first) { 1433 __cache.__get()->__value_ = *__first; 1434 __node_insert_multi(__cache.__get()); 1435 __cache.__advance(); 1436 } 1437 } 1438 for (; __first != __last; ++__first) 1439 __insert_multi(_NodeTypes::__get_value(*__first)); 1440} 1441 1442template <class _Tp, class _Compare, class _Allocator> 1443__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1444 : __begin_node_(__iter_pointer()), 1445 __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1446 __pair3_(0, __t.value_comp()) { 1447 __begin_node() = __end_node(); 1448} 1449 1450template <class _Tp, class _Compare, class _Allocator> 1451__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_( 1452 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value) 1453 : __begin_node_(std::move(__t.__begin_node_)), 1454 __pair1_(std::move(__t.__pair1_)), 1455 __pair3_(std::move(__t.__pair3_)) { 1456 if (size() == 0) 1457 __begin_node() = __end_node(); 1458 else { 1459 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1460 __t.__begin_node() = __t.__end_node(); 1461 __t.__end_node()->__left_ = nullptr; 1462 __t.size() = 0; 1463 } 1464} 1465 1466template <class _Tp, class _Compare, class _Allocator> 1467__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1468 : __pair1_(__default_init_tag(), __node_allocator(__a)), __pair3_(0, std::move(__t.value_comp())) { 1469 if (__a == __t.__alloc()) { 1470 if (__t.size() == 0) 1471 __begin_node() = __end_node(); 1472 else { 1473 __begin_node() = __t.__begin_node(); 1474 __end_node()->__left_ = __t.__end_node()->__left_; 1475 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1476 size() = __t.size(); 1477 __t.__begin_node() = __t.__end_node(); 1478 __t.__end_node()->__left_ = nullptr; 1479 __t.size() = 0; 1480 } 1481 } else { 1482 __begin_node() = __end_node(); 1483 } 1484} 1485 1486template <class _Tp, class _Compare, class _Allocator> 1487void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1488 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value) { 1489 destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1490 __begin_node_ = __t.__begin_node_; 1491 __pair1_.first() = __t.__pair1_.first(); 1492 __move_assign_alloc(__t); 1493 __pair3_ = std::move(__t.__pair3_); 1494 if (size() == 0) 1495 __begin_node() = __end_node(); 1496 else { 1497 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1498 __t.__begin_node() = __t.__end_node(); 1499 __t.__end_node()->__left_ = nullptr; 1500 __t.size() = 0; 1501 } 1502} 1503 1504template <class _Tp, class _Compare, class _Allocator> 1505void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) { 1506 if (__node_alloc() == __t.__node_alloc()) 1507 __move_assign(__t, true_type()); 1508 else { 1509 value_comp() = std::move(__t.value_comp()); 1510 const_iterator __e = end(); 1511 if (size() != 0) { 1512 _DetachedTreeCache __cache(this); 1513 while (__cache.__get() != nullptr && __t.size() != 0) { 1514 __cache.__get()->__value_ = std::move(__t.remove(__t.begin())->__value_); 1515 __node_insert_multi(__cache.__get()); 1516 __cache.__advance(); 1517 } 1518 } 1519 while (__t.size() != 0) 1520 __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_)); 1521 } 1522} 1523 1524template <class _Tp, class _Compare, class _Allocator> 1525__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) _NOEXCEPT_( 1526 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<value_compare>::value&& 1527 is_nothrow_move_assignable<__node_allocator>::value) 1528 1529{ 1530 __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); 1531 return *this; 1532} 1533 1534template <class _Tp, class _Compare, class _Allocator> 1535__tree<_Tp, _Compare, _Allocator>::~__tree() { 1536 static_assert((is_copy_constructible<value_compare>::value), "Comparator must be copy-constructible."); 1537 destroy(__root()); 1538} 1539 1540template <class _Tp, class _Compare, class _Allocator> 1541void __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT { 1542 if (__nd != nullptr) { 1543 destroy(static_cast<__node_pointer>(__nd->__left_)); 1544 destroy(static_cast<__node_pointer>(__nd->__right_)); 1545 __node_allocator& __na = __node_alloc(); 1546 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_)); 1547 __node_traits::deallocate(__na, __nd, 1); 1548 } 1549} 1550 1551template <class _Tp, class _Compare, class _Allocator> 1552void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1553#if _LIBCPP_STD_VER <= 11 1554 _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value && 1555 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable<__node_allocator>::value)) 1556#else 1557 _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value) 1558#endif 1559{ 1560 using std::swap; 1561 swap(__begin_node_, __t.__begin_node_); 1562 swap(__pair1_.first(), __t.__pair1_.first()); 1563 std::__swap_allocator(__node_alloc(), __t.__node_alloc()); 1564 __pair3_.swap(__t.__pair3_); 1565 if (size() == 0) 1566 __begin_node() = __end_node(); 1567 else 1568 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1569 if (__t.size() == 0) 1570 __t.__begin_node() = __t.__end_node(); 1571 else 1572 __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node()); 1573} 1574 1575template <class _Tp, class _Compare, class _Allocator> 1576void __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT { 1577 destroy(__root()); 1578 size() = 0; 1579 __begin_node() = __end_node(); 1580 __end_node()->__left_ = nullptr; 1581} 1582 1583// Find lower_bound place to insert 1584// Set __parent to parent of null leaf 1585// Return reference to null leaf 1586template <class _Tp, class _Compare, class _Allocator> 1587typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1588__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent, const key_type& __v) { 1589 __node_pointer __nd = __root(); 1590 if (__nd != nullptr) { 1591 while (true) { 1592 if (value_comp()(__nd->__value_, __v)) { 1593 if (__nd->__right_ != nullptr) 1594 __nd = static_cast<__node_pointer>(__nd->__right_); 1595 else { 1596 __parent = static_cast<__parent_pointer>(__nd); 1597 return __nd->__right_; 1598 } 1599 } else { 1600 if (__nd->__left_ != nullptr) 1601 __nd = static_cast<__node_pointer>(__nd->__left_); 1602 else { 1603 __parent = static_cast<__parent_pointer>(__nd); 1604 return __parent->__left_; 1605 } 1606 } 1607 } 1608 } 1609 __parent = static_cast<__parent_pointer>(__end_node()); 1610 return __parent->__left_; 1611} 1612 1613// Find upper_bound place to insert 1614// Set __parent to parent of null leaf 1615// Return reference to null leaf 1616template <class _Tp, class _Compare, class _Allocator> 1617typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1618__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent, const key_type& __v) { 1619 __node_pointer __nd = __root(); 1620 if (__nd != nullptr) { 1621 while (true) { 1622 if (value_comp()(__v, __nd->__value_)) { 1623 if (__nd->__left_ != nullptr) 1624 __nd = static_cast<__node_pointer>(__nd->__left_); 1625 else { 1626 __parent = static_cast<__parent_pointer>(__nd); 1627 return __parent->__left_; 1628 } 1629 } else { 1630 if (__nd->__right_ != nullptr) 1631 __nd = static_cast<__node_pointer>(__nd->__right_); 1632 else { 1633 __parent = static_cast<__parent_pointer>(__nd); 1634 return __nd->__right_; 1635 } 1636 } 1637 } 1638 } 1639 __parent = static_cast<__parent_pointer>(__end_node()); 1640 return __parent->__left_; 1641} 1642 1643// Find leaf place to insert closest to __hint 1644// First check prior to __hint. 1645// Next check after __hint. 1646// Next do O(log N) search. 1647// Set __parent to parent of null leaf 1648// Return reference to null leaf 1649template <class _Tp, class _Compare, class _Allocator> 1650typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1651__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v) { 1652 if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1653 { 1654 // __v <= *__hint 1655 const_iterator __prior = __hint; 1656 if (__prior == begin() || !value_comp()(__v, *--__prior)) { 1657 // *prev(__hint) <= __v <= *__hint 1658 if (__hint.__ptr_->__left_ == nullptr) { 1659 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 1660 return __parent->__left_; 1661 } else { 1662 __parent = static_cast<__parent_pointer>(__prior.__ptr_); 1663 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; 1664 } 1665 } 1666 // __v < *prev(__hint) 1667 return __find_leaf_high(__parent, __v); 1668 } 1669 // else __v > *__hint 1670 return __find_leaf_low(__parent, __v); 1671} 1672 1673// Find place to insert if __v doesn't exist 1674// Set __parent to parent of null leaf 1675// Return reference to null leaf 1676// If __v exists, set parent to node of __v and return reference to node of __v 1677template <class _Tp, class _Compare, class _Allocator> 1678template <class _Key> 1679typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 1680__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent, const _Key& __v) { 1681 __node_pointer __nd = __root(); 1682 __node_base_pointer* __nd_ptr = __root_ptr(); 1683 if (__nd != nullptr) { 1684 while (true) { 1685 if (value_comp()(__v, __nd->__value_)) { 1686 if (__nd->__left_ != nullptr) { 1687 __nd_ptr = std::addressof(__nd->__left_); 1688 __nd = static_cast<__node_pointer>(__nd->__left_); 1689 } else { 1690 __parent = static_cast<__parent_pointer>(__nd); 1691 return __parent->__left_; 1692 } 1693 } else if (value_comp()(__nd->__value_, __v)) { 1694 if (__nd->__right_ != nullptr) { 1695 __nd_ptr = std::addressof(__nd->__right_); 1696 __nd = static_cast<__node_pointer>(__nd->__right_); 1697 } else { 1698 __parent = static_cast<__parent_pointer>(__nd); 1699 return __nd->__right_; 1700 } 1701 } else { 1702 __parent = static_cast<__parent_pointer>(__nd); 1703 return *__nd_ptr; 1704 } 1705 } 1706 } 1707 __parent = static_cast<__parent_pointer>(__end_node()); 1708 return __parent->__left_; 1709} 1710 1711// Find place to insert if __v doesn't exist 1712// First check prior to __hint. 1713// Next check after __hint. 1714// Next do O(log N) search. 1715// Set __parent to parent of null leaf 1716// Return reference to null leaf 1717// If __v exists, set parent to node of __v and return reference to node of __v 1718template <class _Tp, class _Compare, class _Allocator> 1719template <class _Key> 1720typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_equal( 1721 const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v) { 1722 if (__hint == end() || value_comp()(__v, *__hint)) // check before 1723 { 1724 // __v < *__hint 1725 const_iterator __prior = __hint; 1726 if (__prior == begin() || value_comp()(*--__prior, __v)) { 1727 // *prev(__hint) < __v < *__hint 1728 if (__hint.__ptr_->__left_ == nullptr) { 1729 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 1730 return __parent->__left_; 1731 } else { 1732 __parent = static_cast<__parent_pointer>(__prior.__ptr_); 1733 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; 1734 } 1735 } 1736 // __v <= *prev(__hint) 1737 return __find_equal(__parent, __v); 1738 } else if (value_comp()(*__hint, __v)) // check after 1739 { 1740 // *__hint < __v 1741 const_iterator __next = std::next(__hint); 1742 if (__next == end() || value_comp()(__v, *__next)) { 1743 // *__hint < __v < *std::next(__hint) 1744 if (__hint.__get_np()->__right_ == nullptr) { 1745 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 1746 return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_; 1747 } else { 1748 __parent = static_cast<__parent_pointer>(__next.__ptr_); 1749 return __parent->__left_; 1750 } 1751 } 1752 // *next(__hint) <= __v 1753 return __find_equal(__parent, __v); 1754 } 1755 // else __v == *__hint 1756 __parent = static_cast<__parent_pointer>(__hint.__ptr_); 1757 __dummy = static_cast<__node_base_pointer>(__hint.__ptr_); 1758 return __dummy; 1759} 1760 1761template <class _Tp, class _Compare, class _Allocator> 1762void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( 1763 __parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT { 1764 __new_node->__left_ = nullptr; 1765 __new_node->__right_ = nullptr; 1766 __new_node->__parent_ = __parent; 1767 // __new_node->__is_black_ is initialized in __tree_balance_after_insert 1768 __child = __new_node; 1769 if (__begin_node()->__left_ != nullptr) 1770 __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_); 1771 std::__tree_balance_after_insert(__end_node()->__left_, __child); 1772 ++size(); 1773} 1774 1775template <class _Tp, class _Compare, class _Allocator> 1776template <class _Key, class... _Args> 1777pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1778__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) { 1779 __parent_pointer __parent; 1780 __node_base_pointer& __child = __find_equal(__parent, __k); 1781 __node_pointer __r = static_cast<__node_pointer>(__child); 1782 bool __inserted = false; 1783 if (__child == nullptr) { 1784 __node_holder __h = __construct_node(std::forward<_Args>(__args)...); 1785 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1786 __r = __h.release(); 1787 __inserted = true; 1788 } 1789 return pair<iterator, bool>(iterator(__r), __inserted); 1790} 1791 1792template <class _Tp, class _Compare, class _Allocator> 1793template <class _Key, class... _Args> 1794pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1795__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( 1796 const_iterator __p, _Key const& __k, _Args&&... __args) { 1797 __parent_pointer __parent; 1798 __node_base_pointer __dummy; 1799 __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); 1800 __node_pointer __r = static_cast<__node_pointer>(__child); 1801 bool __inserted = false; 1802 if (__child == nullptr) { 1803 __node_holder __h = __construct_node(std::forward<_Args>(__args)...); 1804 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1805 __r = __h.release(); 1806 __inserted = true; 1807 } 1808 return pair<iterator, bool>(iterator(__r), __inserted); 1809} 1810 1811template <class _Tp, class _Compare, class _Allocator> 1812template <class... _Args> 1813typename __tree<_Tp, _Compare, _Allocator>::__node_holder 1814__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) { 1815 static_assert(!__is_tree_value_type<_Args...>::value, "Cannot construct from __value_type"); 1816 __node_allocator& __na = __node_alloc(); 1817 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1818 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), std::forward<_Args>(__args)...); 1819 __h.get_deleter().__value_constructed = true; 1820 return __h; 1821} 1822 1823template <class _Tp, class _Compare, class _Allocator> 1824template <class... _Args> 1825pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1826__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) { 1827 __node_holder __h = __construct_node(std::forward<_Args>(__args)...); 1828 __parent_pointer __parent; 1829 __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 1830 __node_pointer __r = static_cast<__node_pointer>(__child); 1831 bool __inserted = false; 1832 if (__child == nullptr) { 1833 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1834 __r = __h.release(); 1835 __inserted = true; 1836 } 1837 return pair<iterator, bool>(iterator(__r), __inserted); 1838} 1839 1840template <class _Tp, class _Compare, class _Allocator> 1841template <class... _Args> 1842typename __tree<_Tp, _Compare, _Allocator>::iterator 1843__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) { 1844 __node_holder __h = __construct_node(std::forward<_Args>(__args)...); 1845 __parent_pointer __parent; 1846 __node_base_pointer __dummy; 1847 __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_); 1848 __node_pointer __r = static_cast<__node_pointer>(__child); 1849 if (__child == nullptr) { 1850 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1851 __r = __h.release(); 1852 } 1853 return iterator(__r); 1854} 1855 1856template <class _Tp, class _Compare, class _Allocator> 1857template <class... _Args> 1858typename __tree<_Tp, _Compare, _Allocator>::iterator 1859__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) { 1860 __node_holder __h = __construct_node(std::forward<_Args>(__args)...); 1861 __parent_pointer __parent; 1862 __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_)); 1863 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1864 return iterator(static_cast<__node_pointer>(__h.release())); 1865} 1866 1867template <class _Tp, class _Compare, class _Allocator> 1868template <class... _Args> 1869typename __tree<_Tp, _Compare, _Allocator>::iterator 1870__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) { 1871 __node_holder __h = __construct_node(std::forward<_Args>(__args)...); 1872 __parent_pointer __parent; 1873 __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_)); 1874 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1875 return iterator(static_cast<__node_pointer>(__h.release())); 1876} 1877 1878template <class _Tp, class _Compare, class _Allocator> 1879pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1880__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd) { 1881 __parent_pointer __parent; 1882 __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__v)); 1883 __node_pointer __r = static_cast<__node_pointer>(__child); 1884 bool __inserted = false; 1885 if (__child == nullptr) { 1886 __nd->__value_ = __v; 1887 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1888 __r = __nd; 1889 __inserted = true; 1890 } 1891 return pair<iterator, bool>(iterator(__r), __inserted); 1892} 1893 1894template <class _Tp, class _Compare, class _Allocator> 1895typename __tree<_Tp, _Compare, _Allocator>::iterator 1896__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) { 1897 __parent_pointer __parent; 1898 __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_)); 1899 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1900 return iterator(__nd); 1901} 1902 1903template <class _Tp, class _Compare, class _Allocator> 1904typename __tree<_Tp, _Compare, _Allocator>::iterator 1905__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) { 1906 __parent_pointer __parent; 1907 __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_)); 1908 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1909 return iterator(__nd); 1910} 1911 1912template <class _Tp, class _Compare, class _Allocator> 1913typename __tree<_Tp, _Compare, _Allocator>::iterator 1914__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT { 1915 iterator __r(__ptr); 1916 ++__r; 1917 if (__begin_node() == __ptr) 1918 __begin_node() = __r.__ptr_; 1919 --size(); 1920 std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__ptr)); 1921 return __r; 1922} 1923 1924#if _LIBCPP_STD_VER >= 17 1925template <class _Tp, class _Compare, class _Allocator> 1926template <class _NodeHandle, class _InsertReturnType> 1927_LIBCPP_HIDE_FROM_ABI _InsertReturnType 1928__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(_NodeHandle&& __nh) { 1929 if (__nh.empty()) 1930 return _InsertReturnType{end(), false, _NodeHandle()}; 1931 1932 __node_pointer __ptr = __nh.__ptr_; 1933 __parent_pointer __parent; 1934 __node_base_pointer& __child = __find_equal(__parent, __ptr->__value_); 1935 if (__child != nullptr) 1936 return _InsertReturnType{iterator(static_cast<__node_pointer>(__child)), false, std::move(__nh)}; 1937 1938 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 1939 __nh.__release_ptr(); 1940 return _InsertReturnType{iterator(__ptr), true, _NodeHandle()}; 1941} 1942 1943template <class _Tp, class _Compare, class _Allocator> 1944template <class _NodeHandle> 1945_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator 1946__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh) { 1947 if (__nh.empty()) 1948 return end(); 1949 1950 __node_pointer __ptr = __nh.__ptr_; 1951 __parent_pointer __parent; 1952 __node_base_pointer __dummy; 1953 __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, __ptr->__value_); 1954 __node_pointer __r = static_cast<__node_pointer>(__child); 1955 if (__child == nullptr) { 1956 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 1957 __r = __ptr; 1958 __nh.__release_ptr(); 1959 } 1960 return iterator(__r); 1961} 1962 1963template <class _Tp, class _Compare, class _Allocator> 1964template <class _NodeHandle> 1965_LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) { 1966 iterator __it = find(__key); 1967 if (__it == end()) 1968 return _NodeHandle(); 1969 return __node_handle_extract<_NodeHandle>(__it); 1970} 1971 1972template <class _Tp, class _Compare, class _Allocator> 1973template <class _NodeHandle> 1974_LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) { 1975 __node_pointer __np = __p.__get_np(); 1976 __remove_node_pointer(__np); 1977 return _NodeHandle(__np, __alloc()); 1978} 1979 1980template <class _Tp, class _Compare, class _Allocator> 1981template <class _Tree> 1982_LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) { 1983 static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); 1984 1985 for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { 1986 __node_pointer __src_ptr = __i.__get_np(); 1987 __parent_pointer __parent; 1988 __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); 1989 ++__i; 1990 if (__child != nullptr) 1991 continue; 1992 __source.__remove_node_pointer(__src_ptr); 1993 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr)); 1994 } 1995} 1996 1997template <class _Tp, class _Compare, class _Allocator> 1998template <class _NodeHandle> 1999_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator 2000__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) { 2001 if (__nh.empty()) 2002 return end(); 2003 __node_pointer __ptr = __nh.__ptr_; 2004 __parent_pointer __parent; 2005 __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__ptr->__value_)); 2006 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 2007 __nh.__release_ptr(); 2008 return iterator(__ptr); 2009} 2010 2011template <class _Tp, class _Compare, class _Allocator> 2012template <class _NodeHandle> 2013_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator 2014__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) { 2015 if (__nh.empty()) 2016 return end(); 2017 2018 __node_pointer __ptr = __nh.__ptr_; 2019 __parent_pointer __parent; 2020 __node_base_pointer& __child = __find_leaf(__hint, __parent, _NodeTypes::__get_key(__ptr->__value_)); 2021 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 2022 __nh.__release_ptr(); 2023 return iterator(__ptr); 2024} 2025 2026template <class _Tp, class _Compare, class _Allocator> 2027template <class _Tree> 2028_LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) { 2029 static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); 2030 2031 for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { 2032 __node_pointer __src_ptr = __i.__get_np(); 2033 __parent_pointer __parent; 2034 __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); 2035 ++__i; 2036 __source.__remove_node_pointer(__src_ptr); 2037 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr)); 2038 } 2039} 2040 2041#endif // _LIBCPP_STD_VER >= 17 2042 2043template <class _Tp, class _Compare, class _Allocator> 2044typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) { 2045 __node_pointer __np = __p.__get_np(); 2046 iterator __r = __remove_node_pointer(__np); 2047 __node_allocator& __na = __node_alloc(); 2048 __node_traits::destroy(__na, _NodeTypes::__get_ptr(const_cast<__node_value_type&>(*__p))); 2049 __node_traits::deallocate(__na, __np, 1); 2050 return __r; 2051} 2052 2053template <class _Tp, class _Compare, class _Allocator> 2054typename __tree<_Tp, _Compare, _Allocator>::iterator 2055__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) { 2056 while (__f != __l) 2057 __f = erase(__f); 2058 return iterator(__l.__ptr_); 2059} 2060 2061template <class _Tp, class _Compare, class _Allocator> 2062template <class _Key> 2063typename __tree<_Tp, _Compare, _Allocator>::size_type 2064__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) { 2065 iterator __i = find(__k); 2066 if (__i == end()) 2067 return 0; 2068 erase(__i); 2069 return 1; 2070} 2071 2072template <class _Tp, class _Compare, class _Allocator> 2073template <class _Key> 2074typename __tree<_Tp, _Compare, _Allocator>::size_type 2075__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) { 2076 pair<iterator, iterator> __p = __equal_range_multi(__k); 2077 size_type __r = 0; 2078 for (; __p.first != __p.second; ++__r) 2079 __p.first = erase(__p.first); 2080 return __r; 2081} 2082 2083template <class _Tp, class _Compare, class _Allocator> 2084template <class _Key> 2085typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) { 2086 iterator __p = __lower_bound(__v, __root(), __end_node()); 2087 if (__p != end() && !value_comp()(__v, *__p)) 2088 return __p; 2089 return end(); 2090} 2091 2092template <class _Tp, class _Compare, class _Allocator> 2093template <class _Key> 2094typename __tree<_Tp, _Compare, _Allocator>::const_iterator 2095__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const { 2096 const_iterator __p = __lower_bound(__v, __root(), __end_node()); 2097 if (__p != end() && !value_comp()(__v, *__p)) 2098 return __p; 2099 return end(); 2100} 2101 2102template <class _Tp, class _Compare, class _Allocator> 2103template <class _Key> 2104typename __tree<_Tp, _Compare, _Allocator>::size_type 2105__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const { 2106 __node_pointer __rt = __root(); 2107 while (__rt != nullptr) { 2108 if (value_comp()(__k, __rt->__value_)) { 2109 __rt = static_cast<__node_pointer>(__rt->__left_); 2110 } else if (value_comp()(__rt->__value_, __k)) 2111 __rt = static_cast<__node_pointer>(__rt->__right_); 2112 else 2113 return 1; 2114 } 2115 return 0; 2116} 2117 2118template <class _Tp, class _Compare, class _Allocator> 2119template <class _Key> 2120typename __tree<_Tp, _Compare, _Allocator>::size_type 2121__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const { 2122 __iter_pointer __result = __end_node(); 2123 __node_pointer __rt = __root(); 2124 while (__rt != nullptr) { 2125 if (value_comp()(__k, __rt->__value_)) { 2126 __result = static_cast<__iter_pointer>(__rt); 2127 __rt = static_cast<__node_pointer>(__rt->__left_); 2128 } else if (value_comp()(__rt->__value_, __k)) 2129 __rt = static_cast<__node_pointer>(__rt->__right_); 2130 else 2131 return std::distance( 2132 __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 2133 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2134 } 2135 return 0; 2136} 2137 2138template <class _Tp, class _Compare, class _Allocator> 2139template <class _Key> 2140typename __tree<_Tp, _Compare, _Allocator>::iterator 2141__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) { 2142 while (__root != nullptr) { 2143 if (!value_comp()(__root->__value_, __v)) { 2144 __result = static_cast<__iter_pointer>(__root); 2145 __root = static_cast<__node_pointer>(__root->__left_); 2146 } else 2147 __root = static_cast<__node_pointer>(__root->__right_); 2148 } 2149 return iterator(__result); 2150} 2151 2152template <class _Tp, class _Compare, class _Allocator> 2153template <class _Key> 2154typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound( 2155 const _Key& __v, __node_pointer __root, __iter_pointer __result) const { 2156 while (__root != nullptr) { 2157 if (!value_comp()(__root->__value_, __v)) { 2158 __result = static_cast<__iter_pointer>(__root); 2159 __root = static_cast<__node_pointer>(__root->__left_); 2160 } else 2161 __root = static_cast<__node_pointer>(__root->__right_); 2162 } 2163 return const_iterator(__result); 2164} 2165 2166template <class _Tp, class _Compare, class _Allocator> 2167template <class _Key> 2168typename __tree<_Tp, _Compare, _Allocator>::iterator 2169__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) { 2170 while (__root != nullptr) { 2171 if (value_comp()(__v, __root->__value_)) { 2172 __result = static_cast<__iter_pointer>(__root); 2173 __root = static_cast<__node_pointer>(__root->__left_); 2174 } else 2175 __root = static_cast<__node_pointer>(__root->__right_); 2176 } 2177 return iterator(__result); 2178} 2179 2180template <class _Tp, class _Compare, class _Allocator> 2181template <class _Key> 2182typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound( 2183 const _Key& __v, __node_pointer __root, __iter_pointer __result) const { 2184 while (__root != nullptr) { 2185 if (value_comp()(__v, __root->__value_)) { 2186 __result = static_cast<__iter_pointer>(__root); 2187 __root = static_cast<__node_pointer>(__root->__left_); 2188 } else 2189 __root = static_cast<__node_pointer>(__root->__right_); 2190 } 2191 return const_iterator(__result); 2192} 2193 2194template <class _Tp, class _Compare, class _Allocator> 2195template <class _Key> 2196pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator> 2197__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) { 2198 typedef pair<iterator, iterator> _Pp; 2199 __iter_pointer __result = __end_node(); 2200 __node_pointer __rt = __root(); 2201 while (__rt != nullptr) { 2202 if (value_comp()(__k, __rt->__value_)) { 2203 __result = static_cast<__iter_pointer>(__rt); 2204 __rt = static_cast<__node_pointer>(__rt->__left_); 2205 } else if (value_comp()(__rt->__value_, __k)) 2206 __rt = static_cast<__node_pointer>(__rt->__right_); 2207 else 2208 return _Pp(iterator(__rt), 2209 iterator(__rt->__right_ != nullptr ? static_cast<__iter_pointer>(std::__tree_min(__rt->__right_)) 2210 : __result)); 2211 } 2212 return _Pp(iterator(__result), iterator(__result)); 2213} 2214 2215template <class _Tp, class _Compare, class _Allocator> 2216template <class _Key> 2217pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2218 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2219__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const { 2220 typedef pair<const_iterator, const_iterator> _Pp; 2221 __iter_pointer __result = __end_node(); 2222 __node_pointer __rt = __root(); 2223 while (__rt != nullptr) { 2224 if (value_comp()(__k, __rt->__value_)) { 2225 __result = static_cast<__iter_pointer>(__rt); 2226 __rt = static_cast<__node_pointer>(__rt->__left_); 2227 } else if (value_comp()(__rt->__value_, __k)) 2228 __rt = static_cast<__node_pointer>(__rt->__right_); 2229 else 2230 return _Pp( 2231 const_iterator(__rt), 2232 const_iterator( 2233 __rt->__right_ != nullptr ? static_cast<__iter_pointer>(std::__tree_min(__rt->__right_)) : __result)); 2234 } 2235 return _Pp(const_iterator(__result), const_iterator(__result)); 2236} 2237 2238template <class _Tp, class _Compare, class _Allocator> 2239template <class _Key> 2240pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator> 2241__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) { 2242 typedef pair<iterator, iterator> _Pp; 2243 __iter_pointer __result = __end_node(); 2244 __node_pointer __rt = __root(); 2245 while (__rt != nullptr) { 2246 if (value_comp()(__k, __rt->__value_)) { 2247 __result = static_cast<__iter_pointer>(__rt); 2248 __rt = static_cast<__node_pointer>(__rt->__left_); 2249 } else if (value_comp()(__rt->__value_, __k)) 2250 __rt = static_cast<__node_pointer>(__rt->__right_); 2251 else 2252 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 2253 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2254 } 2255 return _Pp(iterator(__result), iterator(__result)); 2256} 2257 2258template <class _Tp, class _Compare, class _Allocator> 2259template <class _Key> 2260pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2261 typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2262__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const { 2263 typedef pair<const_iterator, const_iterator> _Pp; 2264 __iter_pointer __result = __end_node(); 2265 __node_pointer __rt = __root(); 2266 while (__rt != nullptr) { 2267 if (value_comp()(__k, __rt->__value_)) { 2268 __result = static_cast<__iter_pointer>(__rt); 2269 __rt = static_cast<__node_pointer>(__rt->__left_); 2270 } else if (value_comp()(__rt->__value_, __k)) 2271 __rt = static_cast<__node_pointer>(__rt->__right_); 2272 else 2273 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 2274 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2275 } 2276 return _Pp(const_iterator(__result), const_iterator(__result)); 2277} 2278 2279template <class _Tp, class _Compare, class _Allocator> 2280typename __tree<_Tp, _Compare, _Allocator>::__node_holder 2281__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT { 2282 __node_pointer __np = __p.__get_np(); 2283 if (__begin_node() == __p.__ptr_) { 2284 if (__np->__right_ != nullptr) 2285 __begin_node() = static_cast<__iter_pointer>(__np->__right_); 2286 else 2287 __begin_node() = static_cast<__iter_pointer>(__np->__parent_); 2288 } 2289 --size(); 2290 std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np)); 2291 return __node_holder(__np, _Dp(__node_alloc(), true)); 2292} 2293 2294template <class _Tp, class _Compare, class _Allocator> 2295inline _LIBCPP_HIDE_FROM_ABI void swap(__tree<_Tp, _Compare, _Allocator>& __x, __tree<_Tp, _Compare, _Allocator>& __y) 2296 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 2297 __x.swap(__y); 2298} 2299 2300_LIBCPP_END_NAMESPACE_STD 2301 2302_LIBCPP_POP_MACROS 2303 2304#endif // _LIBCPP___TREE 2305