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