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