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