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 654 ~__tree_node_base() = delete; 655 __tree_node_base(__tree_node_base const&) = delete; 656 __tree_node_base& operator=(__tree_node_base const&) = delete; 657}; 658 659template <class _Tp, class _VoidPtr> 660class _LIBCPP_STANDALONE_DEBUG __tree_node : public __tree_node_base<_VoidPtr> { 661public: 662 typedef _Tp __node_value_type; 663 664 __node_value_type __value_; 665 666 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; } 667 668 ~__tree_node() = delete; 669 __tree_node(__tree_node const&) = delete; 670 __tree_node& operator=(__tree_node const&) = delete; 671}; 672 673template <class _Allocator> 674class __tree_node_destructor { 675 typedef _Allocator allocator_type; 676 typedef allocator_traits<allocator_type> __alloc_traits; 677 678public: 679 typedef typename __alloc_traits::pointer pointer; 680 681private: 682 typedef __tree_node_types<pointer> _NodeTypes; 683 allocator_type& __na_; 684 685public: 686 bool __value_constructed; 687 688 _LIBCPP_HIDE_FROM_ABI __tree_node_destructor(const __tree_node_destructor&) = default; 689 __tree_node_destructor& operator=(const __tree_node_destructor&) = delete; 690 691 _LIBCPP_HIDE_FROM_ABI explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT 692 : __na_(__na), 693 __value_constructed(__val) {} 694 695 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 696 if (__value_constructed) 697 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 698 if (__p) 699 __alloc_traits::deallocate(__na_, __p, 1); 700 } 701 702 template <class> 703 friend class __map_node_destructor; 704}; 705 706#if _LIBCPP_STD_VER >= 17 707template <class _NodeType, class _Alloc> 708struct __generic_container_node_destructor; 709template <class _Tp, class _VoidPtr, class _Alloc> 710struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> : __tree_node_destructor<_Alloc> { 711 using __tree_node_destructor<_Alloc>::__tree_node_destructor; 712}; 713#endif 714 715template <class _Tp, class _NodePtr, class _DiffType> 716class _LIBCPP_TEMPLATE_VIS __tree_iterator { 717 typedef __tree_node_types<_NodePtr> _NodeTypes; 718 typedef _NodePtr __node_pointer; 719 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 720 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 721 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 722 typedef pointer_traits<__node_pointer> __pointer_traits; 723 724 __iter_pointer __ptr_; 725 726public: 727 typedef bidirectional_iterator_tag iterator_category; 728 typedef _Tp value_type; 729 typedef _DiffType difference_type; 730 typedef value_type& reference; 731 typedef typename _NodeTypes::__node_value_type_pointer pointer; 732 733 _LIBCPP_HIDE_FROM_ABI __tree_iterator() _NOEXCEPT 734#if _LIBCPP_STD_VER >= 14 735 : __ptr_(nullptr) 736#endif 737 { 738 } 739 740 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; } 741 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); } 742 743 _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator++() { 744 __ptr_ = static_cast<__iter_pointer>( 745 std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 746 return *this; 747 } 748 _LIBCPP_HIDE_FROM_ABI __tree_iterator operator++(int) { 749 __tree_iterator __t(*this); 750 ++(*this); 751 return __t; 752 } 753 754 _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator--() { 755 __ptr_ = static_cast<__iter_pointer>( 756 std::__tree_prev_iter<__node_base_pointer>(static_cast<__end_node_pointer>(__ptr_))); 757 return *this; 758 } 759 _LIBCPP_HIDE_FROM_ABI __tree_iterator operator--(int) { 760 __tree_iterator __t(*this); 761 --(*this); 762 return __t; 763 } 764 765 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) { 766 return __x.__ptr_ == __y.__ptr_; 767 } 768 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) { 769 return !(__x == __y); 770 } 771 772private: 773 _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 774 _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 775 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 776 template <class, class, class> 777 friend class __tree; 778 template <class, class, class> 779 friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 780 template <class> 781 friend class _LIBCPP_TEMPLATE_VIS __map_iterator; 782 template <class, class, class, class> 783 friend class _LIBCPP_TEMPLATE_VIS map; 784 template <class, class, class, class> 785 friend class _LIBCPP_TEMPLATE_VIS multimap; 786 template <class, class, class> 787 friend class _LIBCPP_TEMPLATE_VIS set; 788 template <class, class, class> 789 friend class _LIBCPP_TEMPLATE_VIS multiset; 790}; 791 792template <class _Tp, class _NodePtr, class _DiffType> 793class _LIBCPP_TEMPLATE_VIS __tree_const_iterator { 794 typedef __tree_node_types<_NodePtr> _NodeTypes; 795 typedef typename _NodeTypes::__node_pointer __node_pointer; 796 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 797 typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 798 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 799 typedef pointer_traits<__node_pointer> __pointer_traits; 800 801 __iter_pointer __ptr_; 802 803public: 804 typedef bidirectional_iterator_tag iterator_category; 805 typedef _Tp value_type; 806 typedef _DiffType difference_type; 807 typedef const value_type& reference; 808 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 809 810 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator() _NOEXCEPT 811#if _LIBCPP_STD_VER >= 14 812 : __ptr_(nullptr) 813#endif 814 { 815 } 816 817private: 818 typedef __tree_iterator<value_type, __node_pointer, difference_type> __non_const_iterator; 819 820public: 821 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT : __ptr_(__p.__ptr_) {} 822 823 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; } 824 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); } 825 826 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator++() { 827 __ptr_ = static_cast<__iter_pointer>( 828 std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 829 return *this; 830 } 831 832 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator++(int) { 833 __tree_const_iterator __t(*this); 834 ++(*this); 835 return __t; 836 } 837 838 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator--() { 839 __ptr_ = static_cast<__iter_pointer>( 840 std::__tree_prev_iter<__node_base_pointer>(static_cast<__end_node_pointer>(__ptr_))); 841 return *this; 842 } 843 844 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator--(int) { 845 __tree_const_iterator __t(*this); 846 --(*this); 847 return __t; 848 } 849 850 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) { 851 return __x.__ptr_ == __y.__ptr_; 852 } 853 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) { 854 return !(__x == __y); 855 } 856 857private: 858 _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 859 _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 860 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 861 862 template <class, class, class> 863 friend class __tree; 864 template <class, class, class, class> 865 friend class _LIBCPP_TEMPLATE_VIS map; 866 template <class, class, class, class> 867 friend class _LIBCPP_TEMPLATE_VIS multimap; 868 template <class, class, class> 869 friend class _LIBCPP_TEMPLATE_VIS set; 870 template <class, class, class> 871 friend class _LIBCPP_TEMPLATE_VIS multiset; 872 template <class> 873 friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 874}; 875 876template <class _Tp, class _Compare> 877#ifndef _LIBCPP_CXX03_LANG 878_LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, 879 "the specified comparator type does not provide a viable const call operator") 880#endif 881int __diagnose_non_const_comparator(); 882 883template <class _Tp, class _Compare, class _Allocator> 884class __tree { 885public: 886 typedef _Tp value_type; 887 typedef _Compare value_compare; 888 typedef _Allocator allocator_type; 889 890private: 891 typedef allocator_traits<allocator_type> __alloc_traits; 892 typedef typename __make_tree_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes; 893 typedef typename _NodeTypes::key_type key_type; 894 895public: 896 typedef typename _NodeTypes::__node_value_type __node_value_type; 897 typedef typename _NodeTypes::__container_value_type __container_value_type; 898 899 typedef typename __alloc_traits::pointer pointer; 900 typedef typename __alloc_traits::const_pointer const_pointer; 901 typedef typename __alloc_traits::size_type size_type; 902 typedef typename __alloc_traits::difference_type difference_type; 903 904public: 905 typedef typename _NodeTypes::__void_pointer __void_pointer; 906 907 typedef typename _NodeTypes::__node_type __node; 908 typedef typename _NodeTypes::__node_pointer __node_pointer; 909 910 typedef typename _NodeTypes::__node_base_type __node_base; 911 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 912 913 typedef typename _NodeTypes::__end_node_type __end_node_t; 914 typedef typename _NodeTypes::__end_node_pointer __end_node_ptr; 915 916 typedef typename _NodeTypes::__parent_pointer __parent_pointer; 917 typedef typename _NodeTypes::__iter_pointer __iter_pointer; 918 919 typedef __rebind_alloc<__alloc_traits, __node> __node_allocator; 920 typedef allocator_traits<__node_allocator> __node_traits; 921 922private: 923 // check for sane allocator pointer rebinding semantics. Rebinding the 924 // allocator for a new pointer type should be exactly the same as rebinding 925 // the pointer using 'pointer_traits'. 926 static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value, 927 "Allocator does not rebind pointers in a sane manner."); 928 typedef __rebind_alloc<__node_traits, __node_base> __node_base_allocator; 929 typedef allocator_traits<__node_base_allocator> __node_base_traits; 930 static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value, 931 "Allocator does not rebind pointers in a sane manner."); 932 933private: 934 __iter_pointer __begin_node_; 935 _LIBCPP_COMPRESSED_PAIR(__end_node_t, __end_node_, __node_allocator, __node_alloc_); 936 _LIBCPP_COMPRESSED_PAIR(size_type, __size_, value_compare, __value_comp_); 937 938public: 939 _LIBCPP_HIDE_FROM_ABI __iter_pointer __end_node() _NOEXCEPT { 940 return static_cast<__iter_pointer>(pointer_traits<__end_node_ptr>::pointer_to(__end_node_)); 941 } 942 _LIBCPP_HIDE_FROM_ABI __iter_pointer __end_node() const _NOEXCEPT { 943 return static_cast<__iter_pointer>( 944 pointer_traits<__end_node_ptr>::pointer_to(const_cast<__end_node_t&>(__end_node_))); 945 } 946 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __node_alloc_; } 947 948private: 949 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __node_alloc_; } 950 _LIBCPP_HIDE_FROM_ABI __iter_pointer& __begin_node() _NOEXCEPT { return __begin_node_; } 951 _LIBCPP_HIDE_FROM_ABI const __iter_pointer& __begin_node() const _NOEXCEPT { return __begin_node_; } 952 953public: 954 _LIBCPP_HIDE_FROM_ABI allocator_type __alloc() const _NOEXCEPT { return allocator_type(__node_alloc()); } 955 956private: 957 _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; } 958 959public: 960 _LIBCPP_HIDE_FROM_ABI const size_type& size() const _NOEXCEPT { return __size_; } 961 _LIBCPP_HIDE_FROM_ABI value_compare& value_comp() _NOEXCEPT { return __value_comp_; } 962 _LIBCPP_HIDE_FROM_ABI const value_compare& value_comp() const _NOEXCEPT { return __value_comp_; } 963 964public: 965 _LIBCPP_HIDE_FROM_ABI __node_pointer __root() const _NOEXCEPT { 966 return static_cast<__node_pointer>(__end_node()->__left_); 967 } 968 969 _LIBCPP_HIDE_FROM_ABI __node_base_pointer* __root_ptr() const _NOEXCEPT { 970 return std::addressof(__end_node()->__left_); 971 } 972 973 typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 974 typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 975 976 _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp) _NOEXCEPT_( 977 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value); 978 _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a); 979 _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a); 980 _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t); 981 _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t); 982 template <class _ForwardIterator> 983 _LIBCPP_HIDE_FROM_ABI void __assign_unique(_ForwardIterator __first, _ForwardIterator __last); 984 template <class _InputIterator> 985 _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last); 986 _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t) _NOEXCEPT_( 987 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value); 988 _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a); 989 _LIBCPP_HIDE_FROM_ABI __tree& operator=(__tree&& __t) _NOEXCEPT_( 990 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<value_compare>::value&& 991 is_nothrow_move_assignable<__node_allocator>::value); 992 _LIBCPP_HIDE_FROM_ABI ~__tree(); 993 994 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__begin_node()); } 995 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__begin_node()); } 996 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_node()); } 997 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_node()); } 998 999 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { 1000 return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max()); 1001 } 1002 1003 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT; 1004 1005 _LIBCPP_HIDE_FROM_ABI void swap(__tree& __t) 1006#if _LIBCPP_STD_VER <= 11 1007 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> && 1008 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)); 1009#else 1010 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>); 1011#endif 1012 1013 template <class _Key, class... _Args> 1014 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args); 1015 template <class _Key, class... _Args> 1016 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); 1017 1018 template <class... _Args> 1019 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 1020 1021 template <class... _Args> 1022 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); 1023 1024 template <class... _Args> 1025 _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args); 1026 1027 template <class... _Args> 1028 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 1029 1030 template <class _Pp> 1031 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) { 1032 return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); 1033 } 1034 1035 template <class _First, 1036 class _Second, 1037 __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0> 1038 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) { 1039 return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s)); 1040 } 1041 1042 template <class... _Args> 1043 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) { 1044 return __emplace_unique_impl(std::forward<_Args>(__args)...); 1045 } 1046 1047 template <class _Pp> 1048 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 1049 return __emplace_unique_impl(std::forward<_Pp>(__x)); 1050 } 1051 1052 template <class _Pp> 1053 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 1054 return __emplace_unique_key_args(__x, std::forward<_Pp>(__x)); 1055 } 1056 1057 template <class _Pp> 1058 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 1059 return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x)); 1060 } 1061 1062 template <class _Pp> 1063 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { 1064 return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); 1065 } 1066 1067 template <class _First, 1068 class _Second, 1069 __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0> 1070 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { 1071 return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first; 1072 } 1073 1074 template <class... _Args> 1075 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { 1076 return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...); 1077 } 1078 1079 template <class _Pp> 1080 _LIBCPP_HIDE_FROM_ABI iterator 1081 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { 1082 return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x)); 1083 } 1084 1085 template <class _Pp> 1086 _LIBCPP_HIDE_FROM_ABI iterator 1087 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { 1088 return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first; 1089 } 1090 1091 template <class _Pp> 1092 _LIBCPP_HIDE_FROM_ABI iterator 1093 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { 1094 return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first; 1095 } 1096 1097 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __v) { 1098 return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); 1099 } 1100 1101 _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { 1102 return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first; 1103 } 1104 1105 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __v) { 1106 return __emplace_unique_key_args(_NodeTypes::__get_key(__v), std::move(__v)); 1107 } 1108 1109 _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { 1110 return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), std::move(__v)).first; 1111 } 1112 1113 template <class _Vp, __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value, int> = 0> 1114 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Vp&& __v) { 1115 return __emplace_unique(std::forward<_Vp>(__v)); 1116 } 1117 1118 template <class _Vp, __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value, int> = 0> 1119 _LIBCPP_HIDE_FROM_ABI iterator __insert_unique(const_iterator __p, _Vp&& __v) { 1120 return __emplace_hint_unique(__p, std::forward<_Vp>(__v)); 1121 } 1122 1123 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(__container_value_type&& __v) { 1124 return __emplace_multi(std::move(__v)); 1125 } 1126 1127 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, __container_value_type&& __v) { 1128 return __emplace_hint_multi(__p, std::move(__v)); 1129 } 1130 1131 template <class _Vp> 1132 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Vp&& __v) { 1133 return __emplace_multi(std::forward<_Vp>(__v)); 1134 } 1135 1136 template <class _Vp> 1137 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Vp&& __v) { 1138 return __emplace_hint_multi(__p, std::forward<_Vp>(__v)); 1139 } 1140 1141 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> 1142 __node_assign_unique(const __container_value_type& __v, __node_pointer __dest); 1143 1144 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd); 1145 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 1146 1147 _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT; 1148 1149#if _LIBCPP_STD_VER >= 17 1150 template <class _NodeHandle, class _InsertReturnType> 1151 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); 1152 template <class _NodeHandle> 1153 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); 1154 template <class _Tree> 1155 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Tree& __source); 1156 1157 template <class _NodeHandle> 1158 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&&); 1159 template <class _NodeHandle> 1160 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); 1161 template <class _Tree> 1162 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Tree& __source); 1163 1164 template <class _NodeHandle> 1165 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const&); 1166 template <class _NodeHandle> 1167 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator); 1168#endif 1169 1170 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p); 1171 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l); 1172 template <class _Key> 1173 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k); 1174 template <class _Key> 1175 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k); 1176 1177 _LIBCPP_HIDE_FROM_ABI void 1178 __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT; 1179 1180 template <class _Key> 1181 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __v); 1182 template <class _Key> 1183 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __v) const; 1184 1185 template <class _Key> 1186 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const; 1187 template <class _Key> 1188 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const; 1189 1190 template <class _Key> 1191 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Key& __v) { 1192 return __lower_bound(__v, __root(), __end_node()); 1193 } 1194 template <class _Key> 1195 _LIBCPP_HIDE_FROM_ABI iterator __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result); 1196 template <class _Key> 1197 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Key& __v) const { 1198 return __lower_bound(__v, __root(), __end_node()); 1199 } 1200 template <class _Key> 1201 _LIBCPP_HIDE_FROM_ABI const_iterator 1202 __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const; 1203 template <class _Key> 1204 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Key& __v) { 1205 return __upper_bound(__v, __root(), __end_node()); 1206 } 1207 template <class _Key> 1208 _LIBCPP_HIDE_FROM_ABI iterator __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result); 1209 template <class _Key> 1210 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Key& __v) const { 1211 return __upper_bound(__v, __root(), __end_node()); 1212 } 1213 template <class _Key> 1214 _LIBCPP_HIDE_FROM_ABI const_iterator 1215 __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const; 1216 template <class _Key> 1217 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k); 1218 template <class _Key> 1219 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const; 1220 1221 template <class _Key> 1222 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k); 1223 template <class _Key> 1224 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const; 1225 1226 typedef __tree_node_destructor<__node_allocator> _Dp; 1227 typedef unique_ptr<__node, _Dp> __node_holder; 1228 1229 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT; 1230 1231private: 1232 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_low(__parent_pointer& __parent, const key_type& __v); 1233 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_high(__parent_pointer& __parent, const key_type& __v); 1234 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& 1235 __find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v); 1236 // FIXME: Make this function const qualified. Unfortunately doing so 1237 // breaks existing code which uses non-const callable comparators. 1238 template <class _Key> 1239 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v); 1240 template <class _Key> 1241 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v) const { 1242 return const_cast<__tree*>(this)->__find_equal(__parent, __v); 1243 } 1244 template <class _Key> 1245 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& 1246 __find_equal(const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v); 1247 1248 template <class... _Args> 1249 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args); 1250 1251 // TODO: Make this _LIBCPP_HIDE_FROM_ABI 1252 _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT; 1253 1254 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t) { 1255 __copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>()); 1256 } 1257 1258 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t, true_type) { 1259 if (__node_alloc() != __t.__node_alloc()) 1260 clear(); 1261 __node_alloc() = __t.__node_alloc(); 1262 } 1263 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree&, false_type) {} 1264 1265 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type); 1266 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type) _NOEXCEPT_( 1267 is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value); 1268 1269 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t) 1270 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value || 1271 is_nothrow_move_assignable<__node_allocator>::value) { 1272 __move_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); 1273 } 1274 1275 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t, true_type) 1276 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) { 1277 __node_alloc() = std::move(__t.__node_alloc()); 1278 } 1279 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {} 1280 1281 struct _DetachedTreeCache { 1282 _LIBCPP_HIDE_FROM_ABI explicit _DetachedTreeCache(__tree* __t) _NOEXCEPT 1283 : __t_(__t), 1284 __cache_root_(__detach_from_tree(__t)) { 1285 __advance(); 1286 } 1287 1288 _LIBCPP_HIDE_FROM_ABI __node_pointer __get() const _NOEXCEPT { return __cache_elem_; } 1289 1290 _LIBCPP_HIDE_FROM_ABI void __advance() _NOEXCEPT { 1291 __cache_elem_ = __cache_root_; 1292 if (__cache_root_) { 1293 __cache_root_ = __detach_next(__cache_root_); 1294 } 1295 } 1296 1297 _LIBCPP_HIDE_FROM_ABI ~_DetachedTreeCache() { 1298 __t_->destroy(__cache_elem_); 1299 if (__cache_root_) { 1300 while (__cache_root_->__parent_ != nullptr) 1301 __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_); 1302 __t_->destroy(__cache_root_); 1303 } 1304 } 1305 1306 _DetachedTreeCache(_DetachedTreeCache const&) = delete; 1307 _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete; 1308 1309 private: 1310 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_from_tree(__tree* __t) _NOEXCEPT; 1311 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_next(__node_pointer) _NOEXCEPT; 1312 1313 __tree* __t_; 1314 __node_pointer __cache_root_; 1315 __node_pointer __cache_elem_; 1316 }; 1317 1318 template <class, class, class, class> 1319 friend class _LIBCPP_TEMPLATE_VIS map; 1320 template <class, class, class, class> 1321 friend class _LIBCPP_TEMPLATE_VIS multimap; 1322}; 1323 1324template <class _Tp, class _Compare, class _Allocator> 1325__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) _NOEXCEPT_( 1326 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value) 1327 : __size_(0), __value_comp_(__comp) { 1328 __begin_node() = __end_node(); 1329} 1330 1331template <class _Tp, class _Compare, class _Allocator> 1332__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1333 : __begin_node_(__iter_pointer()), __node_alloc_(__node_allocator(__a)), __size_(0) { 1334 __begin_node() = __end_node(); 1335} 1336 1337template <class _Tp, class _Compare, class _Allocator> 1338__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a) 1339 : __begin_node_(__iter_pointer()), __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(__comp) { 1340 __begin_node() = __end_node(); 1341} 1342 1343// Precondition: size() != 0 1344template <class _Tp, class _Compare, class _Allocator> 1345typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1346__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT { 1347 __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node()); 1348 __t->__begin_node() = __t->__end_node(); 1349 __t->__end_node()->__left_->__parent_ = nullptr; 1350 __t->__end_node()->__left_ = nullptr; 1351 __t->size() = 0; 1352 // __cache->__left_ == nullptr 1353 if (__cache->__right_ != nullptr) 1354 __cache = static_cast<__node_pointer>(__cache->__right_); 1355 // __cache->__left_ == nullptr 1356 // __cache->__right_ == nullptr 1357 return __cache; 1358} 1359 1360// Precondition: __cache != nullptr 1361// __cache->left_ == nullptr 1362// __cache->right_ == nullptr 1363// This is no longer a red-black tree 1364template <class _Tp, class _Compare, class _Allocator> 1365typename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1366__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT { 1367 if (__cache->__parent_ == nullptr) 1368 return nullptr; 1369 if (std::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) { 1370 __cache->__parent_->__left_ = nullptr; 1371 __cache = static_cast<__node_pointer>(__cache->__parent_); 1372 if (__cache->__right_ == nullptr) 1373 return __cache; 1374 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__right_)); 1375 } 1376 // __cache is right child 1377 __cache->__parent_unsafe()->__right_ = nullptr; 1378 __cache = static_cast<__node_pointer>(__cache->__parent_); 1379 if (__cache->__left_ == nullptr) 1380 return __cache; 1381 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__left_)); 1382} 1383 1384template <class _Tp, class _Compare, class _Allocator> 1385__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) { 1386 if (this != std::addressof(__t)) { 1387 value_comp() = __t.value_comp(); 1388 __copy_assign_alloc(__t); 1389 __assign_multi(__t.begin(), __t.end()); 1390 } 1391 return *this; 1392} 1393 1394template <class _Tp, class _Compare, class _Allocator> 1395template <class _ForwardIterator> 1396void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) { 1397 typedef iterator_traits<_ForwardIterator> _ITraits; 1398 typedef typename _ITraits::value_type _ItValueType; 1399 static_assert(is_same<_ItValueType, __container_value_type>::value, 1400 "__assign_unique may only be called with the containers value type"); 1401 static_assert( 1402 __has_forward_iterator_category<_ForwardIterator>::value, "__assign_unique requires a forward iterator"); 1403 if (size() != 0) { 1404 _DetachedTreeCache __cache(this); 1405 for (; __cache.__get() != nullptr && __first != __last; ++__first) { 1406 if (__node_assign_unique(*__first, __cache.__get()).second) 1407 __cache.__advance(); 1408 } 1409 } 1410 for (; __first != __last; ++__first) 1411 __insert_unique(*__first); 1412} 1413 1414template <class _Tp, class _Compare, class _Allocator> 1415template <class _InputIterator> 1416void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) { 1417 typedef iterator_traits<_InputIterator> _ITraits; 1418 typedef typename _ITraits::value_type _ItValueType; 1419 static_assert( 1420 (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value), 1421 "__assign_multi may only be called with the containers value type" 1422 " or the nodes value type"); 1423 if (size() != 0) { 1424 _DetachedTreeCache __cache(this); 1425 for (; __cache.__get() && __first != __last; ++__first) { 1426 __cache.__get()->__value_ = *__first; 1427 __node_insert_multi(__cache.__get()); 1428 __cache.__advance(); 1429 } 1430 } 1431 for (; __first != __last; ++__first) 1432 __insert_multi(_NodeTypes::__get_value(*__first)); 1433} 1434 1435template <class _Tp, class _Compare, class _Allocator> 1436__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1437 : __begin_node_(__iter_pointer()), 1438 __node_alloc_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1439 __size_(0), 1440 __value_comp_(__t.value_comp()) { 1441 __begin_node() = __end_node(); 1442} 1443 1444template <class _Tp, class _Compare, class _Allocator> 1445__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_( 1446 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value) 1447 : __begin_node_(std::move(__t.__begin_node_)), 1448 __end_node_(std::move(__t.__end_node_)), 1449 __node_alloc_(std::move(__t.__node_alloc_)), 1450 __size_(__t.__size_), 1451 __value_comp_(std::move(__t.__value_comp_)) { 1452 if (size() == 0) 1453 __begin_node() = __end_node(); 1454 else { 1455 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1456 __t.__begin_node() = __t.__end_node(); 1457 __t.__end_node()->__left_ = nullptr; 1458 __t.size() = 0; 1459 } 1460} 1461 1462template <class _Tp, class _Compare, class _Allocator> 1463__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1464 : __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(std::move(__t.value_comp())) { 1465 if (__a == __t.__alloc()) { 1466 if (__t.size() == 0) 1467 __begin_node() = __end_node(); 1468 else { 1469 __begin_node() = __t.__begin_node(); 1470 __end_node()->__left_ = __t.__end_node()->__left_; 1471 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1472 size() = __t.size(); 1473 __t.__begin_node() = __t.__end_node(); 1474 __t.__end_node()->__left_ = nullptr; 1475 __t.size() = 0; 1476 } 1477 } else { 1478 __begin_node() = __end_node(); 1479 } 1480} 1481 1482template <class _Tp, class _Compare, class _Allocator> 1483void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1484 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value) { 1485 destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1486 __begin_node_ = __t.__begin_node_; 1487 __end_node_ = __t.__end_node_; 1488 __move_assign_alloc(__t); 1489 __size_ = __t.__size_; 1490 __value_comp_ = std::move(__t.__value_comp_); 1491 if (size() == 0) 1492 __begin_node() = __end_node(); 1493 else { 1494 __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 1495 __t.__begin_node() = __t.__end_node(); 1496 __t.__end_node()->__left_ = nullptr; 1497 __t.size() = 0; 1498 } 1499} 1500 1501template <class _Tp, class _Compare, class _Allocator> 1502void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) { 1503 if (__node_alloc() == __t.__node_alloc()) 1504 __move_assign(__t, true_type()); 1505 else { 1506 value_comp() = std::move(__t.value_comp()); 1507 const_iterator __e = end(); 1508 if (size() != 0) { 1509 _DetachedTreeCache __cache(this); 1510 while (__cache.__get() != nullptr && __t.size() != 0) { 1511 __cache.__get()->__value_ = std::move(__t.remove(__t.begin())->__value_); 1512 __node_insert_multi(__cache.__get()); 1513 __cache.__advance(); 1514 } 1515 } 1516 while (__t.size() != 0) 1517 __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_)); 1518 } 1519} 1520 1521template <class _Tp, class _Compare, class _Allocator> 1522__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) _NOEXCEPT_( 1523 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<value_compare>::value&& 1524 is_nothrow_move_assignable<__node_allocator>::value) 1525 1526{ 1527 __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); 1528 return *this; 1529} 1530 1531template <class _Tp, class _Compare, class _Allocator> 1532__tree<_Tp, _Compare, _Allocator>::~__tree() { 1533 static_assert(is_copy_constructible<value_compare>::value, "Comparator must be copy-constructible."); 1534 destroy(__root()); 1535} 1536 1537template <class _Tp, class _Compare, class _Allocator> 1538void __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT { 1539 if (__nd != nullptr) { 1540 destroy(static_cast<__node_pointer>(__nd->__left_)); 1541 destroy(static_cast<__node_pointer>(__nd->__right_)); 1542 __node_allocator& __na = __node_alloc(); 1543 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_)); 1544 __node_traits::deallocate(__na, __nd, 1); 1545 } 1546} 1547 1548template <class _Tp, class _Compare, class _Allocator> 1549void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1550#if _LIBCPP_STD_VER <= 11 1551 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> && 1552 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)) 1553#else 1554 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>) 1555#endif 1556{ 1557 using std::swap; 1558 swap(__begin_node_, __t.__begin_node_); 1559 swap(__end_node_, __t.__end_node_); 1560 std::__swap_allocator(__node_alloc(), __t.__node_alloc()); 1561 swap(__size_, __t.__size_); 1562 swap(__value_comp_, __t.__value_comp_); 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