2361 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___TREE11#define _LIBCPP___TREE12 13#include <__algorithm/min.h>14#include <__assert>15#include <__config>16#include <__fwd/pair.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/construct_at.h>24#include <__memory/pointer_traits.h>25#include <__memory/swap_allocator.h>26#include <__memory/unique_ptr.h>27#include <__new/launder.h>28#include <__type_traits/copy_cvref.h>29#include <__type_traits/enable_if.h>30#include <__type_traits/invoke.h>31#include <__type_traits/is_constructible.h>32#include <__type_traits/is_nothrow_assignable.h>33#include <__type_traits/is_nothrow_constructible.h>34#include <__type_traits/is_same.h>35#include <__type_traits/is_specialization.h>36#include <__type_traits/is_swappable.h>37#include <__type_traits/make_transparent.h>38#include <__type_traits/remove_const.h>39#include <__utility/forward.h>40#include <__utility/lazy_synth_three_way_comparator.h>41#include <__utility/move.h>42#include <__utility/pair.h>43#include <__utility/swap.h>44#include <__utility/try_key_extraction.h>45#include <limits>46 47#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)48# pragma GCC system_header49#endif50 51_LIBCPP_PUSH_MACROS52#include <__undef_macros>53 54_LIBCPP_DIAGNOSTIC_PUSH55// GCC complains about the backslashes at the end, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=12152856_LIBCPP_GCC_DIAGNOSTIC_IGNORED("-Wcomment")57// __tree is a red-black-tree implementation used for the associative containers (i.e. (multi)map/set). It stores58// - (1) a pointer to the node with the smallest (i.e. leftmost) element, namely __begin_node_59// - (2) the number of nodes in the tree, namely __size_60// - (3) a pointer to the root of the tree, namely __end_node_61//62// Storing (1) and (2) is required to allow for constant time lookups. A tree looks like this in memory:63//64// __end_node_65// |66// root67// / \68// l1 r169// / \ / \70// ... ... ... ...71//72// All nodes except __end_node_ have a __left_ and __right_ pointer as well as a __parent_ pointer.73// __end_node_ only contains a __left_ pointer, which points to the root of the tree.74// This layout allows for iteration through the tree without a need for special handling of the end node. See75// __tree_next_iter and __tree_prev_iter for more details.76_LIBCPP_DIAGNOSTIC_POP77 78_LIBCPP_BEGIN_NAMESPACE_STD79 80template <class _Pointer>81class __tree_end_node;82template <class _VoidPtr>83class __tree_node_base;84template <class _Tp, class _VoidPtr>85class __tree_node;86 87template <class _Key, class _Value>88struct __value_type;89 90/*91 92_NodePtr algorithms93 94The algorithms taking _NodePtr are red black tree algorithms. Those95algorithms taking a parameter named __root should assume that __root96points to a proper red black tree (unless otherwise specified).97 98Each algorithm herein assumes that __root->__parent_ points to a non-null99structure which has a member __left_ which points back to __root. No other100member is read or written to at __root->__parent_.101 102__root->__parent_ will be referred to below (in comments only) as end_node.103end_node->__left_ is an externably accessible lvalue for __root, and can be104changed by node insertion and removal (without explicit reference to end_node).105 106All nodes (with the exception of end_node), even the node referred to as107__root, have a non-null __parent_ field.108 109*/110 111// Returns: true if __x is a left child of its parent, else false112// Precondition: __x != nullptr.113template <class _NodePtr>114inline _LIBCPP_HIDE_FROM_ABI bool __tree_is_left_child(_NodePtr __x) _NOEXCEPT {115 return __x == __x->__parent_->__left_;116}117 118// Determines if the subtree rooted at __x is a proper red black subtree. If119// __x is a proper subtree, returns the black height (null counts as 1). If120// __x is an improper subtree, returns 0.121template <class _NodePtr>122unsigned __tree_sub_invariant(_NodePtr __x) {123 if (__x == nullptr)124 return 1;125 // parent consistency checked by caller126 // check __x->__left_ consistency127 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)128 return 0;129 // check __x->__right_ consistency130 if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)131 return 0;132 // check __x->__left_ != __x->__right_ unless both are nullptr133 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)134 return 0;135 // If this is red, neither child can be red136 if (!__x->__is_black_) {137 if (__x->__left_ && !__x->__left_->__is_black_)138 return 0;139 if (__x->__right_ && !__x->__right_->__is_black_)140 return 0;141 }142 unsigned __h = std::__tree_sub_invariant(__x->__left_);143 if (__h == 0)144 return 0; // invalid left subtree145 if (__h != std::__tree_sub_invariant(__x->__right_))146 return 0; // invalid or different height right subtree147 return __h + __x->__is_black_; // return black height of this node148}149 150// Determines if the red black tree rooted at __root is a proper red black tree.151// __root == nullptr is a proper tree. Returns true if __root is a proper152// red black tree, else returns false.153template <class _NodePtr>154_LIBCPP_HIDE_FROM_ABI bool __tree_invariant(_NodePtr __root) {155 if (__root == nullptr)156 return true;157 // check __x->__parent_ consistency158 if (__root->__parent_ == nullptr)159 return false;160 if (!std::__tree_is_left_child(__root))161 return false;162 // root must be black163 if (!__root->__is_black_)164 return false;165 // do normal node checks166 return std::__tree_sub_invariant(__root) != 0;167}168 169// Returns: pointer to the left-most node under __x.170template <class _NodePtr>171inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_min(_NodePtr __x) _NOEXCEPT {172 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Root node shouldn't be null");173 while (__x->__left_ != nullptr)174 __x = __x->__left_;175 return __x;176}177 178// Returns: pointer to the right-most node under __x.179template <class _NodePtr>180inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_max(_NodePtr __x) _NOEXCEPT {181 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Root node shouldn't be null");182 while (__x->__right_ != nullptr)183 __x = __x->__right_;184 return __x;185}186 187// Returns: pointer to the next in-order node after __x.188template <class _NodePtr>189_LIBCPP_HIDE_FROM_ABI _NodePtr __tree_next(_NodePtr __x) _NOEXCEPT {190 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");191 if (__x->__right_ != nullptr)192 return std::__tree_min(__x->__right_);193 while (!std::__tree_is_left_child(__x))194 __x = __x->__parent_unsafe();195 return __x->__parent_unsafe();196}197 198// __tree_next_iter and __tree_prev_iter implement iteration through the tree. The order is as follows:199// left sub-tree -> node -> right sub-tree. When the right-most node of a sub-tree is reached, we walk up the tree until200// we find a node where we were in the left sub-tree. We are _always_ in a left sub-tree, since the __end_node_ points201// to the actual root of the tree through a __left_ pointer. Incrementing the end() pointer is UB, so we can assume that202// never happens.203template <class _EndNodePtr, class _NodePtr>204inline _LIBCPP_HIDE_FROM_ABI _EndNodePtr __tree_next_iter(_NodePtr __x) _NOEXCEPT {205 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");206 if (__x->__right_ != nullptr)207 return static_cast<_EndNodePtr>(std::__tree_min(__x->__right_));208 while (!std::__tree_is_left_child(__x))209 __x = __x->__parent_unsafe();210 return static_cast<_EndNodePtr>(__x->__parent_);211}212 213// Returns: pointer to the previous in-order node before __x.214// Note: __x may be the end node.215template <class _NodePtr, class _EndNodePtr>216inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT {217 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");218 if (__x->__left_ != nullptr)219 return std::__tree_max(__x->__left_);220 _NodePtr __xx = static_cast<_NodePtr>(__x);221 while (std::__tree_is_left_child(__xx))222 __xx = __xx->__parent_unsafe();223 return __xx->__parent_unsafe();224}225 226// Returns: pointer to a node which has no children227template <class _NodePtr>228_LIBCPP_HIDE_FROM_ABI _NodePtr __tree_leaf(_NodePtr __x) _NOEXCEPT {229 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");230 while (true) {231 if (__x->__left_ != nullptr) {232 __x = __x->__left_;233 continue;234 }235 if (__x->__right_ != nullptr) {236 __x = __x->__right_;237 continue;238 }239 break;240 }241 return __x;242}243 244// Effects: Makes __x->__right_ the subtree root with __x as its left child245// while preserving in-order order.246template <class _NodePtr>247_LIBCPP_HIDE_FROM_ABI void __tree_left_rotate(_NodePtr __x) _NOEXCEPT {248 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");249 _LIBCPP_ASSERT_INTERNAL(__x->__right_ != nullptr, "node should have a right child");250 _NodePtr __y = __x->__right_;251 __x->__right_ = __y->__left_;252 if (__x->__right_ != nullptr)253 __x->__right_->__set_parent(__x);254 __y->__parent_ = __x->__parent_;255 if (std::__tree_is_left_child(__x))256 __x->__parent_->__left_ = __y;257 else258 __x->__parent_unsafe()->__right_ = __y;259 __y->__left_ = __x;260 __x->__set_parent(__y);261}262 263// Effects: Makes __x->__left_ the subtree root with __x as its right child264// while preserving in-order order.265template <class _NodePtr>266_LIBCPP_HIDE_FROM_ABI void __tree_right_rotate(_NodePtr __x) _NOEXCEPT {267 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null");268 _LIBCPP_ASSERT_INTERNAL(__x->__left_ != nullptr, "node should have a left child");269 _NodePtr __y = __x->__left_;270 __x->__left_ = __y->__right_;271 if (__x->__left_ != nullptr)272 __x->__left_->__set_parent(__x);273 __y->__parent_ = __x->__parent_;274 if (std::__tree_is_left_child(__x))275 __x->__parent_->__left_ = __y;276 else277 __x->__parent_unsafe()->__right_ = __y;278 __y->__right_ = __x;279 __x->__set_parent(__y);280}281 282// Effects: Rebalances __root after attaching __x to a leaf.283// Precondition: __x has no children.284// __x == __root or == a direct or indirect child of __root.285// If __x were to be unlinked from __root (setting __root to286// nullptr if __root == __x), __tree_invariant(__root) == true.287// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_288// may be different than the value passed in as __root.289template <class _NodePtr>290_LIBCPP_HIDE_FROM_ABI void __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT {291 _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root of the tree shouldn't be null");292 _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "Can't attach null node to a leaf");293 __x->__is_black_ = __x == __root;294 while (__x != __root && !__x->__parent_unsafe()->__is_black_) {295 // __x->__parent_ != __root because __x->__parent_->__is_black == false296 if (std::__tree_is_left_child(__x->__parent_unsafe())) {297 _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;298 if (__y != nullptr && !__y->__is_black_) {299 __x = __x->__parent_unsafe();300 __x->__is_black_ = true;301 __x = __x->__parent_unsafe();302 __x->__is_black_ = __x == __root;303 __y->__is_black_ = true;304 } else {305 if (!std::__tree_is_left_child(__x)) {306 __x = __x->__parent_unsafe();307 std::__tree_left_rotate(__x);308 }309 __x = __x->__parent_unsafe();310 __x->__is_black_ = true;311 __x = __x->__parent_unsafe();312 __x->__is_black_ = false;313 std::__tree_right_rotate(__x);314 break;315 }316 } else {317 _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;318 if (__y != nullptr && !__y->__is_black_) {319 __x = __x->__parent_unsafe();320 __x->__is_black_ = true;321 __x = __x->__parent_unsafe();322 __x->__is_black_ = __x == __root;323 __y->__is_black_ = true;324 } else {325 if (std::__tree_is_left_child(__x)) {326 __x = __x->__parent_unsafe();327 std::__tree_right_rotate(__x);328 }329 __x = __x->__parent_unsafe();330 __x->__is_black_ = true;331 __x = __x->__parent_unsafe();332 __x->__is_black_ = false;333 std::__tree_left_rotate(__x);334 break;335 }336 }337 }338}339 340// Precondition: __z == __root or == a direct or indirect child of __root.341// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed.342// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_343// nor any of its children refer to __z. end_node->__left_344// may be different than the value passed in as __root.345template <class _NodePtr>346_LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT {347 _LIBCPP_ASSERT_INTERNAL(__root != nullptr, "Root node should not be null");348 _LIBCPP_ASSERT_INTERNAL(__z != nullptr, "The node to remove should not be null");349 _LIBCPP_ASSERT_INTERNAL(std::__tree_invariant(__root), "The tree invariants should hold");350 // __z will be removed from the tree. Client still needs to destruct/deallocate it351 // __y is either __z, or if __z has two children, __tree_next(__z).352 // __y will have at most one child.353 // __y will be the initial hole in the tree (make the hole at a leaf)354 _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? __z : std::__tree_next(__z);355 // __x is __y's possibly null single child356 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;357 // __w is __x's possibly null uncle (will become __x's sibling)358 _NodePtr __w = nullptr;359 // link __x to __y's parent, and find __w360 if (__x != nullptr)361 __x->__parent_ = __y->__parent_;362 if (std::__tree_is_left_child(__y)) {363 __y->__parent_->__left_ = __x;364 if (__y != __root)365 __w = __y->__parent_unsafe()->__right_;366 else367 __root = __x; // __w == nullptr368 } else {369 __y->__parent_unsafe()->__right_ = __x;370 // __y can't be root if it is a right child371 __w = __y->__parent_->__left_;372 }373 bool __removed_black = __y->__is_black_;374 // If we didn't remove __z, do so now by splicing in __y for __z,375 // but copy __z's color. This does not impact __x or __w.376 if (__y != __z) {377 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr378 __y->__parent_ = __z->__parent_;379 if (std::__tree_is_left_child(__z))380 __y->__parent_->__left_ = __y;381 else382 __y->__parent_unsafe()->__right_ = __y;383 __y->__left_ = __z->__left_;384 __y->__left_->__set_parent(__y);385 __y->__right_ = __z->__right_;386 if (__y->__right_ != nullptr)387 __y->__right_->__set_parent(__y);388 __y->__is_black_ = __z->__is_black_;389 if (__root == __z)390 __root = __y;391 }392 // There is no need to rebalance if we removed a red, or if we removed393 // the last node.394 if (__removed_black && __root != nullptr) {395 // Rebalance:396 // __x has an implicit black color (transferred from the removed __y)397 // associated with it, no matter what its color is.398 // If __x is __root (in which case it can't be null), it is supposed399 // to be black anyway, and if it is doubly black, then the double400 // can just be ignored.401 // If __x is red (in which case it can't be null), then it can absorb402 // the implicit black just by setting its color to black.403 // Since __y was black and only had one child (which __x points to), __x404 // is either red with no children, else null, otherwise __y would have405 // different black heights under left and right pointers.406 // if (__x == __root || __x != nullptr && !__x->__is_black_)407 if (__x != nullptr)408 __x->__is_black_ = true;409 else {410 // Else __x isn't root, and is "doubly black", even though it may411 // be null. __w can not be null here, else the parent would412 // see a black height >= 2 on the __x side and a black height413 // of 1 on the __w side (__w must be a non-null black or a red414 // with a non-null black child).415 while (true) {416 if (!std::__tree_is_left_child(__w)) // if x is left child417 {418 if (!__w->__is_black_) {419 __w->__is_black_ = true;420 __w->__parent_unsafe()->__is_black_ = false;421 std::__tree_left_rotate(__w->__parent_unsafe());422 // __x is still valid423 // reset __root only if necessary424 if (__root == __w->__left_)425 __root = __w;426 // reset sibling, and it still can't be null427 __w = __w->__left_->__right_;428 }429 // __w->__is_black_ is now true, __w may have null children430 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&431 (__w->__right_ == nullptr || __w->__right_->__is_black_)) {432 __w->__is_black_ = false;433 __x = __w->__parent_unsafe();434 // __x can no longer be null435 if (__x == __root || !__x->__is_black_) {436 __x->__is_black_ = true;437 break;438 }439 // reset sibling, and it still can't be null440 __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_;441 // continue;442 } else // __w has a red child443 {444 if (__w->__right_ == nullptr || __w->__right_->__is_black_) {445 // __w left child is non-null and red446 __w->__left_->__is_black_ = true;447 __w->__is_black_ = false;448 std::__tree_right_rotate(__w);449 // __w is known not to be root, so root hasn't changed450 // reset sibling, and it still can't be null451 __w = __w->__parent_unsafe();452 }453 // __w has a right red child, left child may be null454 __w->__is_black_ = __w->__parent_unsafe()->__is_black_;455 __w->__parent_unsafe()->__is_black_ = true;456 __w->__right_->__is_black_ = true;457 std::__tree_left_rotate(__w->__parent_unsafe());458 break;459 }460 } else {461 if (!__w->__is_black_) {462 __w->__is_black_ = true;463 __w->__parent_unsafe()->__is_black_ = false;464 std::__tree_right_rotate(__w->__parent_unsafe());465 // __x is still valid466 // reset __root only if necessary467 if (__root == __w->__right_)468 __root = __w;469 // reset sibling, and it still can't be null470 __w = __w->__right_->__left_;471 }472 // __w->__is_black_ is now true, __w may have null children473 if ((__w->__left_ == nullptr || __w->__left_->__is_black_) &&474 (__w->__right_ == nullptr || __w->__right_->__is_black_)) {475 __w->__is_black_ = false;476 __x = __w->__parent_unsafe();477 // __x can no longer be null478 if (!__x->__is_black_ || __x == __root) {479 __x->__is_black_ = true;480 break;481 }482 // reset sibling, and it still can't be null483 __w = std::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_;484 // continue;485 } else // __w has a red child486 {487 if (__w->__left_ == nullptr || __w->__left_->__is_black_) {488 // __w right child is non-null and red489 __w->__right_->__is_black_ = true;490 __w->__is_black_ = false;491 std::__tree_left_rotate(__w);492 // __w is known not to be root, so root hasn't changed493 // reset sibling, and it still can't be null494 __w = __w->__parent_unsafe();495 }496 // __w has a left red child, right child may be null497 __w->__is_black_ = __w->__parent_unsafe()->__is_black_;498 __w->__parent_unsafe()->__is_black_ = true;499 __w->__left_->__is_black_ = true;500 std::__tree_right_rotate(__w->__parent_unsafe());501 break;502 }503 }504 }505 }506 }507}508 509// node traits510 511template <class _Tp>512inline const bool __is_tree_value_type_v = __is_specialization_v<_Tp, __value_type>;513 514template <class _Tp>515struct __get_tree_key_type {516 using type _LIBCPP_NODEBUG = _Tp;517};518 519template <class _Key, class _ValueT>520struct __get_tree_key_type<__value_type<_Key, _ValueT> > {521 using type _LIBCPP_NODEBUG = _Key;522};523 524template <class _Tp>525using __get_tree_key_type_t _LIBCPP_NODEBUG = typename __get_tree_key_type<_Tp>::type;526 527template <class _Tp>528struct __get_node_value_type {529 using type _LIBCPP_NODEBUG = _Tp;530};531 532template <class _Key, class _ValueT>533struct __get_node_value_type<__value_type<_Key, _ValueT> > {534 using type _LIBCPP_NODEBUG = pair<const _Key, _ValueT>;535};536 537template <class _Tp>538using __get_node_value_type_t _LIBCPP_NODEBUG = typename __get_node_value_type<_Tp>::type;539 540template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>541struct __tree_node_types;542 543template <class _NodePtr, class _Tp, class _VoidPtr>544struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> > {545 using __node_base_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<_VoidPtr, __tree_node_base<_VoidPtr> >;546 using __end_node_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<_VoidPtr, __tree_end_node<__node_base_pointer> >;547 548private:549 static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,550 "_VoidPtr does not point to unqualified void type");551};552 553// node554 555template <class _Pointer>556class __tree_end_node {557public:558 using pointer = _Pointer;559 pointer __left_;560 561 _LIBCPP_HIDE_FROM_ABI __tree_end_node() _NOEXCEPT : __left_() {}562};563 564template <class _VoidPtr>565class __tree_node_base : public __tree_end_node<__rebind_pointer_t<_VoidPtr, __tree_node_base<_VoidPtr> > > {566public:567 using pointer = __rebind_pointer_t<_VoidPtr, __tree_node_base>;568 using __end_node_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<_VoidPtr, __tree_end_node<pointer> >;569 570 pointer __right_;571 __end_node_pointer __parent_;572 bool __is_black_;573 574 _LIBCPP_HIDE_FROM_ABI pointer __parent_unsafe() const { return static_cast<pointer>(__parent_); }575 576 _LIBCPP_HIDE_FROM_ABI void __set_parent(pointer __p) { __parent_ = static_cast<__end_node_pointer>(__p); }577 578 _LIBCPP_HIDE_FROM_ABI __tree_node_base() = default;579 __tree_node_base(__tree_node_base const&) = delete;580 __tree_node_base& operator=(__tree_node_base const&) = delete;581};582 583template <class _Tp, class _VoidPtr>584class __tree_node : public __tree_node_base<_VoidPtr> {585public:586 using __node_value_type _LIBCPP_NODEBUG = __get_node_value_type_t<_Tp>;587 588// We use a union to avoid initialization during member initialization, which allows us589// to use the allocator from the container to construct the `__node_value_type` in the590// memory provided by the union member591#ifndef _LIBCPP_CXX03_LANG592 593private:594 union {595 __node_value_type __value_;596 };597 598public:599 _LIBCPP_HIDE_FROM_ABI __node_value_type& __get_value() { return __value_; }600#else601 602private:603 _ALIGNAS_TYPE(__node_value_type) unsigned char __buffer_[sizeof(__node_value_type)];604 605public:606 _LIBCPP_HIDE_FROM_ABI __node_value_type& __get_value() { return *reinterpret_cast<__node_value_type*>(__buffer_); }607#endif608 609 template <class _Alloc, class... _Args>610 _LIBCPP_HIDE_FROM_ABI explicit __tree_node(_Alloc& __na, _Args&&... __args) {611 allocator_traits<_Alloc>::construct(__na, std::addressof(__get_value()), std::forward<_Args>(__args)...);612 }613 ~__tree_node() = delete;614 __tree_node(__tree_node const&) = delete;615 __tree_node& operator=(__tree_node const&) = delete;616};617 618template <class _Allocator>619class __tree_node_destructor {620 using allocator_type = _Allocator;621 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>;622 623public:624 using pointer = typename __alloc_traits::pointer;625 626private:627 allocator_type& __na_;628 629public:630 bool __value_constructed;631 632 _LIBCPP_HIDE_FROM_ABI __tree_node_destructor(const __tree_node_destructor&) = default;633 __tree_node_destructor& operator=(const __tree_node_destructor&) = delete;634 635 _LIBCPP_HIDE_FROM_ABI explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT636 : __na_(__na),637 __value_constructed(__val) {}638 639 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {640 if (__value_constructed)641 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value()));642 if (__p)643 __alloc_traits::deallocate(__na_, __p, 1);644 }645 646 template <class>647 friend class __map_node_destructor;648};649 650#if _LIBCPP_STD_VER >= 17651template <class _NodeType, class _Alloc>652struct __generic_container_node_destructor;653template <class _Tp, class _VoidPtr, class _Alloc>654struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> : __tree_node_destructor<_Alloc> {655 using __tree_node_destructor<_Alloc>::__tree_node_destructor;656};657#endif658 659template <class _Tp, class _NodePtr, class _DiffType>660class __tree_iterator {661 using _NodeTypes _LIBCPP_NODEBUG = __tree_node_types<_NodePtr>;662 // NOLINTNEXTLINE(libcpp-nodebug-on-aliases) lldb relies on this alias for pretty printing663 using __node_pointer = _NodePtr;664 using __node_base_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__node_base_pointer;665 using __end_node_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__end_node_pointer;666 667 __end_node_pointer __ptr_;668 669public:670 using iterator_category = bidirectional_iterator_tag;671 using value_type = __get_node_value_type_t<_Tp>;672 using difference_type = _DiffType;673 using reference = value_type&;674 using pointer = __rebind_pointer_t<_NodePtr, value_type>;675 676 _LIBCPP_HIDE_FROM_ABI __tree_iterator() _NOEXCEPT : __ptr_(nullptr) {}677 678 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__get_value(); }679 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {680 return pointer_traits<pointer>::pointer_to(__get_np()->__get_value());681 }682 683 _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator++() {684 __ptr_ = std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_));685 return *this;686 }687 _LIBCPP_HIDE_FROM_ABI __tree_iterator operator++(int) {688 __tree_iterator __t(*this);689 ++(*this);690 return __t;691 }692 693 _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator--() {694 __ptr_ = static_cast<__end_node_pointer>(std::__tree_prev_iter<__node_base_pointer>(__ptr_));695 return *this;696 }697 _LIBCPP_HIDE_FROM_ABI __tree_iterator operator--(int) {698 __tree_iterator __t(*this);699 --(*this);700 return __t;701 }702 703 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) {704 return __x.__ptr_ == __y.__ptr_;705 }706 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) {707 return !(__x == __y);708 }709 710private:711 _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}712 _LIBCPP_HIDE_FROM_ABI explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}713 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }714 template <class, class, class>715 friend class __tree;716 template <class, class, class>717 friend class __tree_const_iterator;718};719 720template <class _Tp, class _NodePtr, class _DiffType>721class __tree_const_iterator {722 using _NodeTypes _LIBCPP_NODEBUG = __tree_node_types<_NodePtr>;723 // NOLINTNEXTLINE(libcpp-nodebug-on-aliases) lldb relies on this alias for pretty printing724 using __node_pointer = _NodePtr;725 using __node_base_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__node_base_pointer;726 using __end_node_pointer _LIBCPP_NODEBUG = typename _NodeTypes::__end_node_pointer;727 728 __end_node_pointer __ptr_;729 730public:731 using iterator_category = bidirectional_iterator_tag;732 using value_type = __get_node_value_type_t<_Tp>;733 using difference_type = _DiffType;734 using reference = const value_type&;735 using pointer = __rebind_pointer_t<_NodePtr, const value_type>;736 using __non_const_iterator _LIBCPP_NODEBUG = __tree_iterator<_Tp, __node_pointer, difference_type>;737 738 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}739 740 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT : __ptr_(__p.__ptr_) {}741 742 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__get_value(); }743 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {744 return pointer_traits<pointer>::pointer_to(__get_np()->__get_value());745 }746 747 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator++() {748 __ptr_ = std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_));749 return *this;750 }751 752 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator++(int) {753 __tree_const_iterator __t(*this);754 ++(*this);755 return __t;756 }757 758 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator--() {759 __ptr_ = static_cast<__end_node_pointer>(std::__tree_prev_iter<__node_base_pointer>(__ptr_));760 return *this;761 }762 763 _LIBCPP_HIDE_FROM_ABI __tree_const_iterator operator--(int) {764 __tree_const_iterator __t(*this);765 --(*this);766 return __t;767 }768 769 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) {770 return __x.__ptr_ == __y.__ptr_;771 }772 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) {773 return !(__x == __y);774 }775 776private:777 _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}778 _LIBCPP_HIDE_FROM_ABI explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}779 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }780 781 template <class, class, class>782 friend class __tree;783};784 785template <class _Tp, class _Compare>786#ifndef _LIBCPP_CXX03_LANG787_LIBCPP_DIAGNOSE_WARNING(!__is_invocable_v<_Compare const&, _Tp const&, _Tp const&>,788 "the specified comparator type does not provide a viable const call operator")789#endif790int __diagnose_non_const_comparator();791 792template <class _Tp, class _Compare, class _Allocator>793class __tree {794public:795 using value_type = __get_node_value_type_t<_Tp>;796 using value_compare = _Compare;797 using allocator_type = _Allocator;798 799private:800 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<allocator_type>;801 using key_type = __get_tree_key_type_t<_Tp>;802 803public:804 using pointer = typename __alloc_traits::pointer;805 using const_pointer = typename __alloc_traits::const_pointer;806 using size_type = typename __alloc_traits::size_type;807 using difference_type = typename __alloc_traits::difference_type;808 809 using __void_pointer _LIBCPP_NODEBUG = typename __alloc_traits::void_pointer;810 811 using __node _LIBCPP_NODEBUG = __tree_node<_Tp, __void_pointer>;812 // NOLINTNEXTLINE(libcpp-nodebug-on-aliases) lldb relies on this alias for pretty printing813 using __node_pointer = __rebind_pointer_t<__void_pointer, __node>;814 815 using __node_base _LIBCPP_NODEBUG = __tree_node_base<__void_pointer>;816 using __node_base_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<__void_pointer, __node_base>;817 818 using __end_node_t _LIBCPP_NODEBUG = __tree_end_node<__node_base_pointer>;819 using __end_node_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<__void_pointer, __end_node_t>;820 821 using __parent_pointer _LIBCPP_NODEBUG = __end_node_pointer; // TODO: Remove this once the uses in <map> are removed822 823 using __node_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, __node>;824 using __node_traits _LIBCPP_NODEBUG = allocator_traits<__node_allocator>;825 826private:827 // check for sane allocator pointer rebinding semantics. Rebinding the828 // allocator for a new pointer type should be exactly the same as rebinding829 // the pointer using 'pointer_traits'.830 static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,831 "Allocator does not rebind pointers in a sane manner.");832 using __node_base_allocator _LIBCPP_NODEBUG = __rebind_alloc<__node_traits, __node_base>;833 using __node_base_traits _LIBCPP_NODEBUG = allocator_traits<__node_base_allocator>;834 static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,835 "Allocator does not rebind pointers in a sane manner.");836 837private:838 __end_node_pointer __begin_node_;839 _LIBCPP_COMPRESSED_PAIR(__end_node_t, __end_node_, __node_allocator, __node_alloc_);840 _LIBCPP_COMPRESSED_PAIR(size_type, __size_, value_compare, __value_comp_);841 842public:843 _LIBCPP_HIDE_FROM_ABI __end_node_pointer __end_node() _NOEXCEPT {844 return pointer_traits<__end_node_pointer>::pointer_to(__end_node_);845 }846 _LIBCPP_HIDE_FROM_ABI __end_node_pointer __end_node() const _NOEXCEPT {847 return pointer_traits<__end_node_pointer>::pointer_to(const_cast<__end_node_t&>(__end_node_));848 }849 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __node_alloc_; }850 851private:852 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __node_alloc_; }853 854public:855 _LIBCPP_HIDE_FROM_ABI allocator_type __alloc() const _NOEXCEPT { return allocator_type(__node_alloc()); }856 857 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }858 _LIBCPP_HIDE_FROM_ABI value_compare& value_comp() _NOEXCEPT { return __value_comp_; }859 _LIBCPP_HIDE_FROM_ABI const value_compare& value_comp() const _NOEXCEPT { return __value_comp_; }860 861public:862 _LIBCPP_HIDE_FROM_ABI __node_pointer __root() const _NOEXCEPT {863 return static_cast<__node_pointer>(__end_node()->__left_);864 }865 866 _LIBCPP_HIDE_FROM_ABI __node_base_pointer* __root_ptr() const _NOEXCEPT {867 return std::addressof(__end_node()->__left_);868 }869 870 using iterator = __tree_iterator<_Tp, __node_pointer, difference_type>;871 using const_iterator = __tree_const_iterator<_Tp, __node_pointer, difference_type>;872 873 _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp) _NOEXCEPT_(874 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value)875 : __size_(0), __value_comp_(__comp) {876 __begin_node_ = __end_node();877 }878 879 _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a)880 : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0) {881 __begin_node_ = __end_node();882 }883 884 _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a)885 : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(__comp) {886 __begin_node_ = __end_node();887 }888 889 _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t);890 891 _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __other, const allocator_type& __alloc)892 : __begin_node_(__end_node()), __node_alloc_(__alloc), __size_(0), __value_comp_(__other.value_comp()) {893 if (__other.size() == 0)894 return;895 896 *__root_ptr() = static_cast<__node_base_pointer>(__copy_construct_tree(__other.__root()));897 __root()->__parent_ = __end_node();898 __begin_node_ = static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_));899 __size_ = __other.size();900 }901 902 _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t);903 template <class _ForwardIterator>904 _LIBCPP_HIDE_FROM_ABI void __assign_unique(_ForwardIterator __first, _ForwardIterator __last);905 template <class _InputIterator>906 _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);907 _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t) _NOEXCEPT_(908 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value);909 _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a);910 911 _LIBCPP_HIDE_FROM_ABI __tree& operator=(__tree&& __t)912 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&913 ((__node_traits::propagate_on_container_move_assignment::value &&914 is_nothrow_move_assignable<__node_allocator>::value) ||915 allocator_traits<__node_allocator>::is_always_equal::value)) {916 __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());917 return *this;918 }919 920 _LIBCPP_HIDE_FROM_ABI ~__tree() {921 static_assert(is_copy_constructible<value_compare>::value, "Comparator must be copy-constructible.");922 destroy(__root());923 }924 925 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__begin_node_); }926 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return const_iterator(__begin_node_); }927 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(__end_node()); }928 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(__end_node()); }929 930 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {931 return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());932 }933 934 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;935 936 _LIBCPP_HIDE_FROM_ABI void swap(__tree& __t)937#if _LIBCPP_STD_VER <= 11938 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> &&939 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));940#else941 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>);942#endif943 944 template <class... _Args>945 _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);946 947 template <class... _Args>948 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);949 950 template <class... _Args>951 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {952 return std::__try_key_extraction<key_type>(953 [this](const key_type& __key, _Args&&... __args2) {954 auto [__parent, __child] = __find_equal(__key);955 __node_pointer __r = static_cast<__node_pointer>(__child);956 bool __inserted = false;957 if (__child == nullptr) {958 __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);959 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));960 __r = __h.release();961 __inserted = true;962 }963 return pair<iterator, bool>(iterator(__r), __inserted);964 },965 [this](_Args&&... __args2) {966 __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);967 auto [__parent, __child] = __find_equal(__h->__get_value());968 __node_pointer __r = static_cast<__node_pointer>(__child);969 bool __inserted = false;970 if (__child == nullptr) {971 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));972 __r = __h.release();973 __inserted = true;974 }975 return pair<iterator, bool>(iterator(__r), __inserted);976 },977 std::forward<_Args>(__args)...);978 }979 980 template <class... _Args>981 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique(const_iterator __p, _Args&&... __args) {982 return std::__try_key_extraction<key_type>(983 [this, __p](const key_type& __key, _Args&&... __args2) {984 __node_base_pointer __dummy;985 auto [__parent, __child] = __find_equal(__p, __dummy, __key);986 __node_pointer __r = static_cast<__node_pointer>(__child);987 bool __inserted = false;988 if (__child == nullptr) {989 __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);990 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));991 __r = __h.release();992 __inserted = true;993 }994 return pair<iterator, bool>(iterator(__r), __inserted);995 },996 [this, __p](_Args&&... __args2) {997 __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);998 __node_base_pointer __dummy;999 auto [__parent, __child] = __find_equal(__p, __dummy, __h->__get_value());1000 __node_pointer __r = static_cast<__node_pointer>(__child);1001 if (__child == nullptr) {1002 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1003 __r = __h.release();1004 }1005 return pair<iterator, bool>(iterator(__r), __child == nullptr);1006 },1007 std::forward<_Args>(__args)...);1008 }1009 1010 template <class _InIter, class _Sent>1011 _LIBCPP_HIDE_FROM_ABI void __insert_range_multi(_InIter __first, _Sent __last) {1012 if (__first == __last)1013 return;1014 1015 if (__root() == nullptr) { // Make sure we always have a root node1016 __insert_node_at(1017 __end_node(), __end_node()->__left_, static_cast<__node_base_pointer>(__construct_node(*__first).release()));1018 ++__first;1019 }1020 1021 auto __max_node = static_cast<__node_pointer>(std::__tree_max(static_cast<__node_base_pointer>(__root())));1022 1023 for (; __first != __last; ++__first) {1024 __node_holder __nd = __construct_node(*__first);1025 // Always check the max node first. This optimizes for sorted ranges inserted at the end.1026 if (!value_comp()(__nd->__get_value(), __max_node->__get_value())) { // __node >= __max_val1027 __insert_node_at(static_cast<__end_node_pointer>(__max_node),1028 __max_node->__right_,1029 static_cast<__node_base_pointer>(__nd.get()));1030 __max_node = __nd.release();1031 } else {1032 __end_node_pointer __parent;1033 __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__get_value());1034 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release()));1035 }1036 }1037 }1038 1039 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_assign_unique(const value_type& __v, __node_pointer __dest);1040 1041 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);1042 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);1043 1044 template <class _InIter, class _Sent>1045 _LIBCPP_HIDE_FROM_ABI void __insert_range_unique(_InIter __first, _Sent __last) {1046 if (__first == __last)1047 return;1048 1049 if (__root() == nullptr) {1050 __insert_node_at(1051 __end_node(), __end_node()->__left_, static_cast<__node_base_pointer>(__construct_node(*__first).release()));1052 ++__first;1053 }1054 1055 auto __max_node = static_cast<__node_pointer>(std::__tree_max(static_cast<__node_base_pointer>(__root())));1056 1057 using __reference = decltype(*__first);1058 1059 for (; __first != __last; ++__first) {1060 std::__try_key_extraction<key_type>(1061 [this, &__max_node](const key_type& __key, __reference&& __val) {1062 if (value_comp()(__max_node->__get_value(), __key)) { // __key > __max_node1063 __node_holder __nd = __construct_node(std::forward<__reference>(__val));1064 __insert_node_at(static_cast<__end_node_pointer>(__max_node),1065 __max_node->__right_,1066 static_cast<__node_base_pointer>(__nd.get()));1067 __max_node = __nd.release();1068 } else {1069 auto [__parent, __child] = __find_equal(__key);1070 if (__child == nullptr) {1071 __node_holder __nd = __construct_node(std::forward<__reference>(__val));1072 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release()));1073 }1074 }1075 },1076 [this, &__max_node](__reference&& __val) {1077 __node_holder __nd = __construct_node(std::forward<__reference>(__val));1078 if (value_comp()(__max_node->__get_value(), __nd->__get_value())) { // __node > __max_node1079 __insert_node_at(static_cast<__end_node_pointer>(__max_node),1080 __max_node->__right_,1081 static_cast<__node_base_pointer>(__nd.get()));1082 __max_node = __nd.release();1083 } else {1084 auto [__parent, __child] = __find_equal(__nd->__get_value());1085 if (__child == nullptr) {1086 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release()));1087 }1088 }1089 },1090 *__first);1091 }1092 }1093 1094 _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT;1095 1096#if _LIBCPP_STD_VER >= 171097 template <class _NodeHandle, class _InsertReturnType>1098 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);1099 template <class _NodeHandle>1100 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);1101 template <class _Comp2>1102 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(__tree<_Tp, _Comp2, _Allocator>& __source);1103 1104 template <class _NodeHandle>1105 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&&);1106 template <class _NodeHandle>1107 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);1108 template <class _Comp2>1109 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(__tree<_Tp, _Comp2, _Allocator>& __source);1110 1111 template <class _NodeHandle>1112 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const&);1113 template <class _NodeHandle>1114 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator);1115#endif1116 1117 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);1118 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);1119 template <class _Key>1120 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);1121 template <class _Key>1122 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);1123 1124 _LIBCPP_HIDE_FROM_ABI void1125 __insert_node_at(__end_node_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT;1126 1127 template <class _Key>1128 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __key) {1129 auto [__, __match] = __find_equal(__key);1130 if (__match == nullptr)1131 return end();1132 return iterator(static_cast<__node_pointer>(__match));1133 }1134 1135 template <class _Key>1136 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __key) const {1137 auto [__, __match] = __find_equal(__key);1138 if (__match == nullptr)1139 return end();1140 return const_iterator(static_cast<__node_pointer>(__match));1141 }1142 1143 template <class _Key>1144 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;1145 template <class _Key>1146 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;1147 1148 template <bool _LowerBound, class _Key>1149 _LIBCPP_HIDE_FROM_ABI __end_node_pointer __lower_upper_bound_unique_impl(const _Key& __v) const {1150 auto __rt = __root();1151 auto __result = __end_node();1152 auto __comp = __lazy_synth_three_way_comparator<_Compare, _Key, value_type>(value_comp());1153 while (__rt != nullptr) {1154 auto __comp_res = __comp(__v, __rt->__get_value());1155 1156 if (__comp_res.__less()) {1157 __result = static_cast<__end_node_pointer>(__rt);1158 __rt = static_cast<__node_pointer>(__rt->__left_);1159 } else if (__comp_res.__greater()) {1160 __rt = static_cast<__node_pointer>(__rt->__right_);1161 } else if _LIBCPP_CONSTEXPR (_LowerBound) {1162 return static_cast<__end_node_pointer>(__rt);1163 } else {1164 return __rt->__right_ ? static_cast<__end_node_pointer>(std::__tree_min(__rt->__right_)) : __result;1165 }1166 }1167 return __result;1168 }1169 1170 template <class _Key>1171 _LIBCPP_HIDE_FROM_ABI iterator __lower_bound_unique(const _Key& __v) {1172 return iterator(__lower_upper_bound_unique_impl<true>(__v));1173 }1174 1175 template <class _Key>1176 _LIBCPP_HIDE_FROM_ABI const_iterator __lower_bound_unique(const _Key& __v) const {1177 return const_iterator(__lower_upper_bound_unique_impl<true>(__v));1178 }1179 1180 template <class _Key>1181 _LIBCPP_HIDE_FROM_ABI iterator __upper_bound_unique(const _Key& __v) {1182 return iterator(__lower_upper_bound_unique_impl<false>(__v));1183 }1184 1185 template <class _Key>1186 _LIBCPP_HIDE_FROM_ABI const_iterator __upper_bound_unique(const _Key& __v) const {1187 return iterator(__lower_upper_bound_unique_impl<false>(__v));1188 }1189 1190private:1191 template <class _Key>1192 _LIBCPP_HIDE_FROM_ABI iterator1193 __lower_bound_multi(const _Key& __v, __node_pointer __root, __end_node_pointer __result);1194 1195 template <class _Key>1196 _LIBCPP_HIDE_FROM_ABI const_iterator1197 __lower_bound_multi(const _Key& __v, __node_pointer __root, __end_node_pointer __result) const;1198 1199public:1200 template <class _Key>1201 _LIBCPP_HIDE_FROM_ABI iterator __lower_bound_multi(const _Key& __v) {1202 return __lower_bound_multi(__v, __root(), __end_node());1203 }1204 template <class _Key>1205 _LIBCPP_HIDE_FROM_ABI const_iterator __lower_bound_multi(const _Key& __v) const {1206 return __lower_bound_multi(__v, __root(), __end_node());1207 }1208 1209 template <class _Key>1210 _LIBCPP_HIDE_FROM_ABI iterator __upper_bound_multi(const _Key& __v) {1211 return __upper_bound_multi(__v, __root(), __end_node());1212 }1213 1214 template <class _Key>1215 _LIBCPP_HIDE_FROM_ABI const_iterator __upper_bound_multi(const _Key& __v) const {1216 return __upper_bound_multi(__v, __root(), __end_node());1217 }1218 1219private:1220 template <class _Key>1221 _LIBCPP_HIDE_FROM_ABI iterator1222 __upper_bound_multi(const _Key& __v, __node_pointer __root, __end_node_pointer __result);1223 1224 template <class _Key>1225 _LIBCPP_HIDE_FROM_ABI const_iterator1226 __upper_bound_multi(const _Key& __v, __node_pointer __root, __end_node_pointer __result) const;1227 1228public:1229 template <class _Key>1230 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);1231 template <class _Key>1232 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;1233 1234 template <class _Key>1235 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);1236 template <class _Key>1237 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;1238 1239 using _Dp _LIBCPP_NODEBUG = __tree_node_destructor<__node_allocator>;1240 using __node_holder _LIBCPP_NODEBUG = unique_ptr<__node, _Dp>;1241 1242 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;1243 1244 // FIXME: Make this function const qualified. Unfortunately doing so1245 // breaks existing code which uses non-const callable comparators.1246 template <class _Key>1247 _LIBCPP_HIDE_FROM_ABI pair<__end_node_pointer, __node_base_pointer&> __find_equal(const _Key& __v);1248 1249 template <class _Key>1250 _LIBCPP_HIDE_FROM_ABI pair<__end_node_pointer, __node_base_pointer&> __find_equal(const _Key& __v) const {1251 return const_cast<__tree*>(this)->__find_equal(__v);1252 }1253 1254 template <class _Key>1255 _LIBCPP_HIDE_FROM_ABI pair<__end_node_pointer, __node_base_pointer&>1256 __find_equal(const_iterator __hint, __node_base_pointer& __dummy, const _Key& __v);1257 1258 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t) {1259 __copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());1260 }1261 1262 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t, true_type) {1263 if (__node_alloc() != __t.__node_alloc())1264 clear();1265 __node_alloc() = __t.__node_alloc();1266 }1267 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree&, false_type) {}1268 1269private:1270 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_low(__end_node_pointer& __parent, const value_type& __v);1271 1272 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_high(__end_node_pointer& __parent, const value_type& __v);1273 1274 _LIBCPP_HIDE_FROM_ABI __node_base_pointer&1275 __find_leaf(const_iterator __hint, __end_node_pointer& __parent, const value_type& __v);1276 1277 template <class... _Args>1278 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);1279 1280 // TODO: Make this _LIBCPP_HIDE_FROM_ABI1281 _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT { (__tree_deleter(__node_alloc_))(__nd); }1282 1283 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type);1284 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type) _NOEXCEPT_(1285 is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value);1286 1287 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t)1288 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||1289 is_nothrow_move_assignable<__node_allocator>::value) {1290 __move_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());1291 }1292 1293 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t, true_type)1294 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {1295 __node_alloc() = std::move(__t.__node_alloc());1296 }1297 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}1298 1299 template <class _From, class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0>1300 _LIBCPP_HIDE_FROM_ABI static void __assign_value(__get_node_value_type_t<value_type>& __lhs, _From&& __rhs) {1301 using __key_type = __remove_const_t<typename value_type::first_type>;1302 1303 // This is technically UB, since the object was constructed as `const`.1304 // Clang doesn't optimize on this currently though.1305 const_cast<__key_type&>(__lhs.first) = const_cast<__copy_cvref_t<_From, __key_type>&&>(__rhs.first);1306 __lhs.second = std::forward<_From>(__rhs).second;1307 }1308 1309 template <class _To, class _From, class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type_v<_ValueT>, int> = 0>1310 _LIBCPP_HIDE_FROM_ABI static void __assign_value(_To& __lhs, _From&& __rhs) {1311 __lhs = std::forward<_From>(__rhs);1312 }1313 1314 struct _DetachedTreeCache {1315 _LIBCPP_HIDE_FROM_ABI explicit _DetachedTreeCache(__tree* __t) _NOEXCEPT1316 : __t_(__t),1317 __cache_root_(__detach_from_tree(__t)) {1318 __advance();1319 }1320 1321 _LIBCPP_HIDE_FROM_ABI __node_pointer __get() const _NOEXCEPT { return __cache_elem_; }1322 1323 _LIBCPP_HIDE_FROM_ABI void __advance() _NOEXCEPT {1324 __cache_elem_ = __cache_root_;1325 if (__cache_root_) {1326 __cache_root_ = __detach_next(__cache_root_);1327 }1328 }1329 1330 _LIBCPP_HIDE_FROM_ABI ~_DetachedTreeCache() {1331 __t_->destroy(__cache_elem_);1332 if (__cache_root_) {1333 while (__cache_root_->__parent_ != nullptr)1334 __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_);1335 __t_->destroy(__cache_root_);1336 }1337 }1338 1339 _DetachedTreeCache(_DetachedTreeCache const&) = delete;1340 _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete;1341 1342 private:1343 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_from_tree(__tree* __t) _NOEXCEPT;1344 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_next(__node_pointer) _NOEXCEPT;1345 1346 __tree* __t_;1347 __node_pointer __cache_root_;1348 __node_pointer __cache_elem_;1349 };1350 1351 class __tree_deleter {1352 __node_allocator& __alloc_;1353 1354 public:1355 using pointer = __node_pointer;1356 1357 _LIBCPP_HIDE_FROM_ABI __tree_deleter(__node_allocator& __alloc) : __alloc_(__alloc) {}1358 1359#ifdef _LIBCPP_COMPILER_CLANG_BASED // FIXME: GCC complains about not being able to always_inline a recursive function1360 _LIBCPP_HIDE_FROM_ABI1361#endif1362 void1363 operator()(__node_pointer __ptr) {1364 if (!__ptr)1365 return;1366 1367 (*this)(static_cast<__node_pointer>(__ptr->__left_));1368 1369 auto __right = __ptr->__right_;1370 1371 __node_traits::destroy(__alloc_, std::addressof(__ptr->__get_value()));1372 __node_traits::deallocate(__alloc_, __ptr, 1);1373 1374 (*this)(static_cast<__node_pointer>(__right));1375 }1376 };1377 1378 // This copy construction will always produce a correct red-black-tree assuming the incoming tree is correct, since we1379 // copy the exact structure 1:1. Since this is for copy construction _only_ we know that we get a correct tree. If we1380 // didn't get a correct tree, the invariants of __tree are broken and we have a much bigger problem than an improperly1381 // balanced tree.1382 template <class _NodeConstructor>1383#ifdef _LIBCPP_COMPILER_CLANG_BASED // FIXME: GCC complains about not being able to always_inline a recursive function1384 _LIBCPP_HIDE_FROM_ABI1385#endif1386 __node_pointer __construct_from_tree(__node_pointer __src, _NodeConstructor __construct) {1387 if (!__src)1388 return nullptr;1389 1390 __node_holder __new_node = __construct(__src->__get_value());1391 1392 unique_ptr<__node, __tree_deleter> __left(1393 __construct_from_tree(static_cast<__node_pointer>(__src->__left_), __construct), __node_alloc_);1394 __node_pointer __right = __construct_from_tree(static_cast<__node_pointer>(__src->__right_), __construct);1395 1396 __node_pointer __new_node_ptr = __new_node.release();1397 1398 __new_node_ptr->__is_black_ = __src->__is_black_;1399 __new_node_ptr->__left_ = static_cast<__node_base_pointer>(__left.release());1400 __new_node_ptr->__right_ = static_cast<__node_base_pointer>(__right);1401 if (__new_node_ptr->__left_)1402 __new_node_ptr->__left_->__parent_ = static_cast<__end_node_pointer>(__new_node_ptr);1403 if (__new_node_ptr->__right_)1404 __new_node_ptr->__right_->__parent_ = static_cast<__end_node_pointer>(__new_node_ptr);1405 return __new_node_ptr;1406 }1407 1408 _LIBCPP_HIDE_FROM_ABI __node_pointer __copy_construct_tree(__node_pointer __src) {1409 return __construct_from_tree(__src, [this](const value_type& __val) { return __construct_node(__val); });1410 }1411 1412 template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0>1413 _LIBCPP_HIDE_FROM_ABI __node_pointer __move_construct_tree(__node_pointer __src) {1414 return __construct_from_tree(__src, [this](value_type& __val) {1415 return __construct_node(const_cast<key_type&&>(__val.first), std::move(__val.second));1416 });1417 }1418 1419 template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type_v<_ValueT>, int> = 0>1420 _LIBCPP_HIDE_FROM_ABI __node_pointer __move_construct_tree(__node_pointer __src) {1421 return __construct_from_tree(__src, [this](value_type& __val) { return __construct_node(std::move(__val)); });1422 }1423 1424 template <class _Assignment, class _ConstructionAlg>1425 // This copy assignment will always produce a correct red-black-tree assuming the incoming tree is correct, since our1426 // own tree is a red-black-tree and the incoming tree is a red-black-tree. The invariants of a red-black-tree are1427 // temporarily not met until all of the incoming red-black tree is copied.1428#ifdef _LIBCPP_COMPILER_CLANG_BASED // FIXME: GCC complains about not being able to always_inline a recursive function1429 _LIBCPP_HIDE_FROM_ABI1430#endif1431 __node_pointer __assign_from_tree(1432 __node_pointer __dest, __node_pointer __src, _Assignment __assign, _ConstructionAlg __construct_subtree) {1433 if (!__src) {1434 destroy(__dest);1435 return nullptr;1436 }1437 1438 __assign(__dest->__get_value(), __src->__get_value());1439 __dest->__is_black_ = __src->__is_black_;1440 1441 // If we already have a left node in the destination tree, reuse it and copy-assign recursively1442 if (__dest->__left_) {1443 __dest->__left_ = static_cast<__node_base_pointer>(__assign_from_tree(1444 static_cast<__node_pointer>(__dest->__left_),1445 static_cast<__node_pointer>(__src->__left_),1446 __assign,1447 __construct_subtree));1448 1449 // Otherwise, we must create new nodes; copy-construct from here on1450 } else if (__src->__left_) {1451 auto __new_left = __construct_subtree(static_cast<__node_pointer>(__src->__left_));1452 __dest->__left_ = static_cast<__node_base_pointer>(__new_left);1453 __new_left->__parent_ = static_cast<__end_node_pointer>(__dest);1454 }1455 1456 // Identical to the left case above, just for the right nodes1457 if (__dest->__right_) {1458 __dest->__right_ = static_cast<__node_base_pointer>(__assign_from_tree(1459 static_cast<__node_pointer>(__dest->__right_),1460 static_cast<__node_pointer>(__src->__right_),1461 __assign,1462 __construct_subtree));1463 } else if (__src->__right_) {1464 auto __new_right = __construct_subtree(static_cast<__node_pointer>(__src->__right_));1465 __dest->__right_ = static_cast<__node_base_pointer>(__new_right);1466 __new_right->__parent_ = static_cast<__end_node_pointer>(__dest);1467 }1468 1469 return __dest;1470 }1471 1472 _LIBCPP_HIDE_FROM_ABI __node_pointer __copy_assign_tree(__node_pointer __dest, __node_pointer __src) {1473 return __assign_from_tree(1474 __dest,1475 __src,1476 [](value_type& __lhs, const value_type& __rhs) { __assign_value(__lhs, __rhs); },1477 [this](__node_pointer __nd) { return __copy_construct_tree(__nd); });1478 }1479 1480 _LIBCPP_HIDE_FROM_ABI __node_pointer __move_assign_tree(__node_pointer __dest, __node_pointer __src) {1481 return __assign_from_tree(1482 __dest,1483 __src,1484 [](value_type& __lhs, value_type& __rhs) { __assign_value(__lhs, std::move(__rhs)); },1485 [this](__node_pointer __nd) { return __move_construct_tree(__nd); });1486 }1487};1488 1489// Precondition: __size_ != 01490template <class _Tp, class _Compare, class _Allocator>1491typename __tree<_Tp, _Compare, _Allocator>::__node_pointer1492__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT {1493 __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node_);1494 __t->__begin_node_ = __t->__end_node();1495 __t->__end_node()->__left_->__parent_ = nullptr;1496 __t->__end_node()->__left_ = nullptr;1497 __t->__size_ = 0;1498 // __cache->__left_ == nullptr1499 if (__cache->__right_ != nullptr)1500 __cache = static_cast<__node_pointer>(__cache->__right_);1501 // __cache->__left_ == nullptr1502 // __cache->__right_ == nullptr1503 return __cache;1504}1505 1506// Precondition: __cache != nullptr1507// __cache->left_ == nullptr1508// __cache->right_ == nullptr1509// This is no longer a red-black tree1510template <class _Tp, class _Compare, class _Allocator>1511typename __tree<_Tp, _Compare, _Allocator>::__node_pointer1512__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT {1513 if (__cache->__parent_ == nullptr)1514 return nullptr;1515 if (std::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) {1516 __cache->__parent_->__left_ = nullptr;1517 __cache = static_cast<__node_pointer>(__cache->__parent_);1518 if (__cache->__right_ == nullptr)1519 return __cache;1520 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__right_));1521 }1522 // __cache is right child1523 __cache->__parent_unsafe()->__right_ = nullptr;1524 __cache = static_cast<__node_pointer>(__cache->__parent_);1525 if (__cache->__left_ == nullptr)1526 return __cache;1527 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__left_));1528}1529 1530template <class _Tp, class _Compare, class _Allocator>1531__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) {1532 if (this == std::addressof(__t))1533 return *this;1534 1535 value_comp() = __t.value_comp();1536 __copy_assign_alloc(__t);1537 1538 if (__size_ != 0) {1539 *__root_ptr() = static_cast<__node_base_pointer>(__copy_assign_tree(__root(), __t.__root()));1540 } else {1541 *__root_ptr() = static_cast<__node_base_pointer>(__copy_construct_tree(__t.__root()));1542 if (__root())1543 __root()->__parent_ = __end_node();1544 }1545 __begin_node_ =1546 __end_node()->__left_ ? static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_)) : __end_node();1547 __size_ = __t.size();1548 1549 return *this;1550}1551 1552template <class _Tp, class _Compare, class _Allocator>1553template <class _ForwardIterator>1554void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) {1555 using _ITraits = iterator_traits<_ForwardIterator>;1556 using _ItValueType = typename _ITraits::value_type;1557 static_assert(1558 is_same<_ItValueType, value_type>::value, "__assign_unique may only be called with the containers value type");1559 static_assert(1560 __has_forward_iterator_category<_ForwardIterator>::value, "__assign_unique requires a forward iterator");1561 if (__size_ != 0) {1562 _DetachedTreeCache __cache(this);1563 for (; __cache.__get() != nullptr && __first != __last; ++__first) {1564 if (__node_assign_unique(*__first, __cache.__get()).second)1565 __cache.__advance();1566 }1567 }1568 for (; __first != __last; ++__first)1569 __emplace_unique(*__first);1570}1571 1572template <class _Tp, class _Compare, class _Allocator>1573template <class _InputIterator>1574void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) {1575 using _ITraits = iterator_traits<_InputIterator>;1576 using _ItValueType = typename _ITraits::value_type;1577 static_assert(1578 is_same<_ItValueType, value_type>::value, "__assign_multi may only be called with the containers value_type");1579 if (__size_ != 0) {1580 _DetachedTreeCache __cache(this);1581 for (; __cache.__get() && __first != __last; ++__first) {1582 __assign_value(__cache.__get()->__get_value(), *__first);1583 __node_insert_multi(__cache.__get());1584 __cache.__advance();1585 }1586 }1587 const_iterator __e = end();1588 for (; __first != __last; ++__first)1589 __emplace_hint_multi(__e, *__first);1590}1591 1592template <class _Tp, class _Compare, class _Allocator>1593__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)1594 : __begin_node_(__end_node()),1595 __node_alloc_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),1596 __size_(0),1597 __value_comp_(__t.value_comp()) {1598 if (__t.size() == 0)1599 return;1600 1601 *__root_ptr() = static_cast<__node_base_pointer>(__copy_construct_tree(__t.__root()));1602 __root()->__parent_ = __end_node();1603 __begin_node_ = static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_));1604 __size_ = __t.size();1605}1606 1607template <class _Tp, class _Compare, class _Allocator>1608__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_(1609 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value)1610 : __begin_node_(std::move(__t.__begin_node_)),1611 __end_node_(std::move(__t.__end_node_)),1612 __node_alloc_(std::move(__t.__node_alloc_)),1613 __size_(__t.__size_),1614 __value_comp_(std::move(__t.__value_comp_)) {1615 if (__size_ == 0)1616 __begin_node_ = __end_node();1617 else {1618 __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node());1619 __t.__begin_node_ = __t.__end_node();1620 __t.__end_node()->__left_ = nullptr;1621 __t.__size_ = 0;1622 }1623}1624 1625template <class _Tp, class _Compare, class _Allocator>1626__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)1627 : __begin_node_(__end_node()),1628 __node_alloc_(__node_allocator(__a)),1629 __size_(0),1630 __value_comp_(std::move(__t.value_comp())) {1631 if (__t.size() == 0)1632 return;1633 if (__a == __t.__alloc()) {1634 __begin_node_ = __t.__begin_node_;1635 __end_node()->__left_ = __t.__end_node()->__left_;1636 __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node());1637 __size_ = __t.__size_;1638 __t.__begin_node_ = __t.__end_node();1639 __t.__end_node()->__left_ = nullptr;1640 __t.__size_ = 0;1641 } else {1642 *__root_ptr() = static_cast<__node_base_pointer>(__move_construct_tree(__t.__root()));1643 __root()->__parent_ = __end_node();1644 __begin_node_ = static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_));1645 __size_ = __t.size();1646 __t.clear(); // Ensure that __t is in a valid state after moving out the keys1647 }1648}1649 1650template <class _Tp, class _Compare, class _Allocator>1651void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)1652 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value) {1653 destroy(static_cast<__node_pointer>(__end_node()->__left_));1654 __begin_node_ = __t.__begin_node_;1655 __end_node_ = __t.__end_node_;1656 __move_assign_alloc(__t);1657 __size_ = __t.__size_;1658 __value_comp_ = std::move(__t.__value_comp_);1659 if (__size_ == 0)1660 __begin_node_ = __end_node();1661 else {1662 __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node());1663 __t.__begin_node_ = __t.__end_node();1664 __t.__end_node()->__left_ = nullptr;1665 __t.__size_ = 0;1666 }1667}1668 1669template <class _Tp, class _Compare, class _Allocator>1670void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) {1671 if (__node_alloc() == __t.__node_alloc()) {1672 __move_assign(__t, true_type());1673 } else {1674 value_comp() = std::move(__t.value_comp());1675 if (__size_ != 0) {1676 *__root_ptr() = static_cast<__node_base_pointer>(__move_assign_tree(__root(), __t.__root()));1677 } else {1678 *__root_ptr() = static_cast<__node_base_pointer>(__move_construct_tree(__t.__root()));1679 if (__root())1680 __root()->__parent_ = __end_node();1681 }1682 __begin_node_ =1683 __end_node()->__left_ ? static_cast<__end_node_pointer>(std::__tree_min(__end_node()->__left_)) : __end_node();1684 __size_ = __t.size();1685 __t.clear(); // Ensure that __t is in a valid state after moving out the keys1686 }1687}1688 1689template <class _Tp, class _Compare, class _Allocator>1690void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)1691#if _LIBCPP_STD_VER <= 111692 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> &&1693 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))1694#else1695 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>)1696#endif1697{1698 using std::swap;1699 swap(__begin_node_, __t.__begin_node_);1700 swap(__end_node_, __t.__end_node_);1701 std::__swap_allocator(__node_alloc(), __t.__node_alloc());1702 swap(__size_, __t.__size_);1703 swap(__value_comp_, __t.__value_comp_);1704 if (__size_ == 0)1705 __begin_node_ = __end_node();1706 else1707 __end_node()->__left_->__parent_ = __end_node();1708 if (__t.__size_ == 0)1709 __t.__begin_node_ = __t.__end_node();1710 else1711 __t.__end_node()->__left_->__parent_ = __t.__end_node();1712}1713 1714template <class _Tp, class _Compare, class _Allocator>1715void __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT {1716 destroy(__root());1717 __size_ = 0;1718 __begin_node_ = __end_node();1719 __end_node()->__left_ = nullptr;1720}1721 1722// Find lower_bound place to insert1723// Set __parent to parent of null leaf1724// Return reference to null leaf1725template <class _Tp, class _Compare, class _Allocator>1726typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&1727__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__end_node_pointer& __parent, const value_type& __v) {1728 __node_pointer __nd = __root();1729 if (__nd != nullptr) {1730 while (true) {1731 if (value_comp()(__nd->__get_value(), __v)) {1732 if (__nd->__right_ != nullptr)1733 __nd = static_cast<__node_pointer>(__nd->__right_);1734 else {1735 __parent = static_cast<__end_node_pointer>(__nd);1736 return __nd->__right_;1737 }1738 } else {1739 if (__nd->__left_ != nullptr)1740 __nd = static_cast<__node_pointer>(__nd->__left_);1741 else {1742 __parent = static_cast<__end_node_pointer>(__nd);1743 return __parent->__left_;1744 }1745 }1746 }1747 }1748 __parent = __end_node();1749 return __parent->__left_;1750}1751 1752// Find upper_bound place to insert1753// Set __parent to parent of null leaf1754// Return reference to null leaf1755template <class _Tp, class _Compare, class _Allocator>1756typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&1757__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__end_node_pointer& __parent, const value_type& __v) {1758 __node_pointer __nd = __root();1759 if (__nd != nullptr) {1760 while (true) {1761 if (value_comp()(__v, __nd->__get_value())) {1762 if (__nd->__left_ != nullptr)1763 __nd = static_cast<__node_pointer>(__nd->__left_);1764 else {1765 __parent = static_cast<__end_node_pointer>(__nd);1766 return __parent->__left_;1767 }1768 } else {1769 if (__nd->__right_ != nullptr)1770 __nd = static_cast<__node_pointer>(__nd->__right_);1771 else {1772 __parent = static_cast<__end_node_pointer>(__nd);1773 return __nd->__right_;1774 }1775 }1776 }1777 }1778 __parent = __end_node();1779 return __parent->__left_;1780}1781 1782// Find leaf place to insert closest to __hint1783// First check prior to __hint.1784// Next check after __hint.1785// Next do O(log N) search.1786// Set __parent to parent of null leaf1787// Return reference to null leaf1788template <class _Tp, class _Compare, class _Allocator>1789typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf(1790 const_iterator __hint, __end_node_pointer& __parent, const value_type& __v) {1791 if (__hint == end() || !value_comp()(*__hint, __v)) // check before1792 {1793 // __v <= *__hint1794 const_iterator __prior = __hint;1795 if (__prior == begin() || !value_comp()(__v, *--__prior)) {1796 // *prev(__hint) <= __v <= *__hint1797 if (__hint.__ptr_->__left_ == nullptr) {1798 __parent = static_cast<__end_node_pointer>(__hint.__ptr_);1799 return __parent->__left_;1800 } else {1801 __parent = static_cast<__end_node_pointer>(__prior.__ptr_);1802 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;1803 }1804 }1805 // __v < *prev(__hint)1806 return __find_leaf_high(__parent, __v);1807 }1808 // else __v > *__hint1809 return __find_leaf_low(__parent, __v);1810}1811 1812// Find __v1813// If __v exists, return the parent of the node of __v and a reference to the pointer to the node of __v.1814// If __v doesn't exist, return the parent of the null leaf and a reference to the pointer to the null leaf.1815template <class _Tp, class _Compare, class _Allocator>1816template <class _Key>1817_LIBCPP_HIDE_FROM_ABI pair<typename __tree<_Tp, _Compare, _Allocator>::__end_node_pointer,1818 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&>1819__tree<_Tp, _Compare, _Allocator>::__find_equal(const _Key& __v) {1820 using _Pair = pair<__end_node_pointer, __node_base_pointer&>;1821 1822 __node_pointer __nd = __root();1823 1824 if (__nd == nullptr) {1825 auto __end = __end_node();1826 return _Pair(__end, __end->__left_);1827 }1828 1829 __node_base_pointer* __node_ptr = __root_ptr();1830 auto&& __transparent = std::__as_transparent(value_comp());1831 auto __comp = __lazy_synth_three_way_comparator<__make_transparent_t<_Compare>, _Key, value_type>(__transparent);1832 1833 while (true) {1834 auto __comp_res = __comp(__v, __nd->__get_value());1835 1836 if (__comp_res.__less()) {1837 if (__nd->__left_ == nullptr)1838 return _Pair(static_cast<__end_node_pointer>(__nd), __nd->__left_);1839 1840 __node_ptr = std::addressof(__nd->__left_);1841 __nd = static_cast<__node_pointer>(__nd->__left_);1842 } else if (__comp_res.__greater()) {1843 if (__nd->__right_ == nullptr)1844 return _Pair(static_cast<__end_node_pointer>(__nd), __nd->__right_);1845 1846 __node_ptr = std::addressof(__nd->__right_);1847 __nd = static_cast<__node_pointer>(__nd->__right_);1848 } else {1849 return _Pair(static_cast<__end_node_pointer>(__nd), *__node_ptr);1850 }1851 }1852}1853 1854// Find __v1855// First check prior to __hint.1856// Next check after __hint.1857// Next do O(log N) search.1858// If __v exists, return the parent of the node of __v and a reference to the pointer to the node of __v.1859// If __v doesn't exist, return the parent of the null leaf and a reference to the pointer to the null leaf.1860template <class _Tp, class _Compare, class _Allocator>1861template <class _Key>1862_LIBCPP_HIDE_FROM_ABI pair<typename __tree<_Tp, _Compare, _Allocator>::__end_node_pointer,1863 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&>1864__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, __node_base_pointer& __dummy, const _Key& __v) {1865 using _Pair = pair<__end_node_pointer, __node_base_pointer&>;1866 1867 if (__hint == end() || value_comp()(__v, *__hint)) { // check before1868 // __v < *__hint1869 const_iterator __prior = __hint;1870 if (__prior == begin() || value_comp()(*--__prior, __v)) {1871 // *prev(__hint) < __v < *__hint1872 if (__hint.__ptr_->__left_ == nullptr)1873 return _Pair(__hint.__ptr_, __hint.__ptr_->__left_);1874 return _Pair(__prior.__ptr_, static_cast<__node_pointer>(__prior.__ptr_)->__right_);1875 }1876 // __v <= *prev(__hint)1877 return __find_equal(__v);1878 }1879 1880 if (value_comp()(*__hint, __v)) { // check after1881 // *__hint < __v1882 const_iterator __next = std::next(__hint);1883 if (__next == end() || value_comp()(__v, *__next)) {1884 // *__hint < __v < *std::next(__hint)1885 if (__hint.__get_np()->__right_ == nullptr)1886 return _Pair(__hint.__ptr_, static_cast<__node_pointer>(__hint.__ptr_)->__right_);1887 return _Pair(__next.__ptr_, __next.__ptr_->__left_);1888 }1889 // *next(__hint) <= __v1890 return __find_equal(__v);1891 }1892 1893 // else __v == *__hint1894 __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);1895 return _Pair(__hint.__ptr_, __dummy);1896}1897 1898template <class _Tp, class _Compare, class _Allocator>1899void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(1900 __end_node_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT {1901 __new_node->__left_ = nullptr;1902 __new_node->__right_ = nullptr;1903 __new_node->__parent_ = __parent;1904 // __new_node->__is_black_ is initialized in __tree_balance_after_insert1905 __child = __new_node;1906 if (__begin_node_->__left_ != nullptr)1907 __begin_node_ = static_cast<__end_node_pointer>(__begin_node_->__left_);1908 std::__tree_balance_after_insert(__end_node()->__left_, __child);1909 ++__size_;1910}1911 1912template <class _Tp, class _Compare, class _Allocator>1913template <class... _Args>1914typename __tree<_Tp, _Compare, _Allocator>::__node_holder1915__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {1916 __node_allocator& __na = __node_alloc();1917 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1918 std::__construct_at(std::addressof(*__h), __na, std::forward<_Args>(__args)...);1919 __h.get_deleter().__value_constructed = true;1920 return __h;1921}1922 1923template <class _Tp, class _Compare, class _Allocator>1924template <class... _Args>1925typename __tree<_Tp, _Compare, _Allocator>::iterator1926__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) {1927 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1928 __end_node_pointer __parent;1929 __node_base_pointer& __child = __find_leaf_high(__parent, __h->__get_value());1930 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1931 return iterator(static_cast<__node_pointer>(__h.release()));1932}1933 1934template <class _Tp, class _Compare, class _Allocator>1935template <class... _Args>1936typename __tree<_Tp, _Compare, _Allocator>::iterator1937__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {1938 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1939 __end_node_pointer __parent;1940 __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__get_value());1941 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1942 return iterator(static_cast<__node_pointer>(__h.release()));1943}1944 1945template <class _Tp, class _Compare, class _Allocator>1946pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>1947__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const value_type& __v, __node_pointer __nd) {1948 auto [__parent, __child] = __find_equal(__v);1949 __node_pointer __r = static_cast<__node_pointer>(__child);1950 bool __inserted = false;1951 if (__child == nullptr) {1952 __assign_value(__nd->__get_value(), __v);1953 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));1954 __r = __nd;1955 __inserted = true;1956 }1957 return pair<iterator, bool>(iterator(__r), __inserted);1958}1959 1960template <class _Tp, class _Compare, class _Allocator>1961typename __tree<_Tp, _Compare, _Allocator>::iterator1962__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) {1963 __end_node_pointer __parent;1964 __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__get_value());1965 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));1966 return iterator(__nd);1967}1968 1969template <class _Tp, class _Compare, class _Allocator>1970typename __tree<_Tp, _Compare, _Allocator>::iterator1971__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) {1972 __end_node_pointer __parent;1973 __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__get_value());1974 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));1975 return iterator(__nd);1976}1977 1978template <class _Tp, class _Compare, class _Allocator>1979typename __tree<_Tp, _Compare, _Allocator>::iterator1980__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT {1981 iterator __r(__ptr);1982 ++__r;1983 if (__begin_node_ == __ptr)1984 __begin_node_ = __r.__ptr_;1985 --__size_;1986 std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__ptr));1987 return __r;1988}1989 1990#if _LIBCPP_STD_VER >= 171991template <class _Tp, class _Compare, class _Allocator>1992template <class _NodeHandle, class _InsertReturnType>1993_LIBCPP_HIDE_FROM_ABI _InsertReturnType1994__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(_NodeHandle&& __nh) {1995 if (__nh.empty())1996 return _InsertReturnType{end(), false, _NodeHandle()};1997 1998 __node_pointer __ptr = __nh.__ptr_;1999 auto [__parent, __child] = __find_equal(__ptr->__get_value());2000 if (__child != nullptr)2001 return _InsertReturnType{iterator(static_cast<__node_pointer>(__child)), false, std::move(__nh)};2002 2003 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));2004 __nh.__release_ptr();2005 return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};2006}2007 2008template <class _Tp, class _Compare, class _Allocator>2009template <class _NodeHandle>2010_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator2011__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh) {2012 if (__nh.empty())2013 return end();2014 2015 __node_pointer __ptr = __nh.__ptr_;2016 __node_base_pointer __dummy;2017 auto [__parent, __child] = __find_equal(__hint, __dummy, __ptr->__get_value());2018 __node_pointer __r = static_cast<__node_pointer>(__child);2019 if (__child == nullptr) {2020 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));2021 __r = __ptr;2022 __nh.__release_ptr();2023 }2024 return iterator(__r);2025}2026 2027template <class _Tp, class _Compare, class _Allocator>2028template <class _NodeHandle>2029_LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) {2030 iterator __it = find(__key);2031 if (__it == end())2032 return _NodeHandle();2033 return __node_handle_extract<_NodeHandle>(__it);2034}2035 2036template <class _Tp, class _Compare, class _Allocator>2037template <class _NodeHandle>2038_LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) {2039 __node_pointer __np = __p.__get_np();2040 __remove_node_pointer(__np);2041 return _NodeHandle(__np, __alloc());2042}2043 2044template <class _Tp, class _Compare, class _Allocator>2045template <class _Comp2>2046_LIBCPP_HIDE_FROM_ABI void2047__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(__tree<_Tp, _Comp2, _Allocator>& __source) {2048 for (iterator __i = __source.begin(); __i != __source.end();) {2049 __node_pointer __src_ptr = __i.__get_np();2050 auto [__parent, __child] = __find_equal(__src_ptr->__get_value());2051 ++__i;2052 if (__child != nullptr)2053 continue;2054 __source.__remove_node_pointer(__src_ptr);2055 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr));2056 }2057}2058 2059template <class _Tp, class _Compare, class _Allocator>2060template <class _NodeHandle>2061_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator2062__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) {2063 if (__nh.empty())2064 return end();2065 __node_pointer __ptr = __nh.__ptr_;2066 __end_node_pointer __parent;2067 __node_base_pointer& __child = __find_leaf_high(__parent, __ptr->__get_value());2068 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));2069 __nh.__release_ptr();2070 return iterator(__ptr);2071}2072 2073template <class _Tp, class _Compare, class _Allocator>2074template <class _NodeHandle>2075_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator2076__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {2077 if (__nh.empty())2078 return end();2079 2080 __node_pointer __ptr = __nh.__ptr_;2081 __end_node_pointer __parent;2082 __node_base_pointer& __child = __find_leaf(__hint, __parent, __ptr->__get_value());2083 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));2084 __nh.__release_ptr();2085 return iterator(__ptr);2086}2087 2088template <class _Tp, class _Compare, class _Allocator>2089template <class _Comp2>2090_LIBCPP_HIDE_FROM_ABI void2091__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(__tree<_Tp, _Comp2, _Allocator>& __source) {2092 for (iterator __i = __source.begin(); __i != __source.end();) {2093 __node_pointer __src_ptr = __i.__get_np();2094 __end_node_pointer __parent;2095 __node_base_pointer& __child = __find_leaf_high(__parent, __src_ptr->__get_value());2096 ++__i;2097 __source.__remove_node_pointer(__src_ptr);2098 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr));2099 }2100}2101 2102#endif // _LIBCPP_STD_VER >= 172103 2104template <class _Tp, class _Compare, class _Allocator>2105typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) {2106 __node_pointer __np = __p.__get_np();2107 iterator __r = __remove_node_pointer(__np);2108 __node_allocator& __na = __node_alloc();2109 __node_traits::destroy(__na, std::addressof(const_cast<value_type&>(*__p)));2110 __node_traits::deallocate(__na, __np, 1);2111 return __r;2112}2113 2114template <class _Tp, class _Compare, class _Allocator>2115typename __tree<_Tp, _Compare, _Allocator>::iterator2116__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) {2117 while (__f != __l)2118 __f = erase(__f);2119 return iterator(__l.__ptr_);2120}2121 2122template <class _Tp, class _Compare, class _Allocator>2123template <class _Key>2124typename __tree<_Tp, _Compare, _Allocator>::size_type2125__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) {2126 iterator __i = find(__k);2127 if (__i == end())2128 return 0;2129 erase(__i);2130 return 1;2131}2132 2133template <class _Tp, class _Compare, class _Allocator>2134template <class _Key>2135typename __tree<_Tp, _Compare, _Allocator>::size_type2136__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) {2137 pair<iterator, iterator> __p = __equal_range_multi(__k);2138 size_type __r = 0;2139 for (; __p.first != __p.second; ++__r)2140 __p.first = erase(__p.first);2141 return __r;2142}2143 2144template <class _Tp, class _Compare, class _Allocator>2145template <class _Key>2146typename __tree<_Tp, _Compare, _Allocator>::size_type2147__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const {2148 __node_pointer __rt = __root();2149 auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp());2150 while (__rt != nullptr) {2151 auto __comp_res = __comp(__k, __rt->__get_value());2152 if (__comp_res.__less()) {2153 __rt = static_cast<__node_pointer>(__rt->__left_);2154 } else if (__comp_res.__greater())2155 __rt = static_cast<__node_pointer>(__rt->__right_);2156 else2157 return 1;2158 }2159 return 0;2160}2161 2162template <class _Tp, class _Compare, class _Allocator>2163template <class _Key>2164typename __tree<_Tp, _Compare, _Allocator>::size_type2165__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const {2166 __end_node_pointer __result = __end_node();2167 __node_pointer __rt = __root();2168 auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp());2169 while (__rt != nullptr) {2170 auto __comp_res = __comp(__k, __rt->__get_value());2171 if (__comp_res.__less()) {2172 __result = static_cast<__end_node_pointer>(__rt);2173 __rt = static_cast<__node_pointer>(__rt->__left_);2174 } else if (__comp_res.__greater())2175 __rt = static_cast<__node_pointer>(__rt->__right_);2176 else2177 return std::distance(2178 __lower_bound_multi(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)),2179 __upper_bound_multi(__k, static_cast<__node_pointer>(__rt->__right_), __result));2180 }2181 return 0;2182}2183 2184template <class _Tp, class _Compare, class _Allocator>2185template <class _Key>2186typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound_multi(2187 const _Key& __v, __node_pointer __root, __end_node_pointer __result) {2188 while (__root != nullptr) {2189 if (!value_comp()(__root->__get_value(), __v)) {2190 __result = static_cast<__end_node_pointer>(__root);2191 __root = static_cast<__node_pointer>(__root->__left_);2192 } else2193 __root = static_cast<__node_pointer>(__root->__right_);2194 }2195 return iterator(__result);2196}2197 2198template <class _Tp, class _Compare, class _Allocator>2199template <class _Key>2200typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound_multi(2201 const _Key& __v, __node_pointer __root, __end_node_pointer __result) const {2202 while (__root != nullptr) {2203 if (!value_comp()(__root->__get_value(), __v)) {2204 __result = static_cast<__end_node_pointer>(__root);2205 __root = static_cast<__node_pointer>(__root->__left_);2206 } else2207 __root = static_cast<__node_pointer>(__root->__right_);2208 }2209 return const_iterator(__result);2210}2211 2212template <class _Tp, class _Compare, class _Allocator>2213template <class _Key>2214typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound_multi(2215 const _Key& __v, __node_pointer __root, __end_node_pointer __result) {2216 while (__root != nullptr) {2217 if (value_comp()(__v, __root->__get_value())) {2218 __result = static_cast<__end_node_pointer>(__root);2219 __root = static_cast<__node_pointer>(__root->__left_);2220 } else2221 __root = static_cast<__node_pointer>(__root->__right_);2222 }2223 return iterator(__result);2224}2225 2226template <class _Tp, class _Compare, class _Allocator>2227template <class _Key>2228typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound_multi(2229 const _Key& __v, __node_pointer __root, __end_node_pointer __result) const {2230 while (__root != nullptr) {2231 if (value_comp()(__v, __root->__get_value())) {2232 __result = static_cast<__end_node_pointer>(__root);2233 __root = static_cast<__node_pointer>(__root->__left_);2234 } else2235 __root = static_cast<__node_pointer>(__root->__right_);2236 }2237 return const_iterator(__result);2238}2239 2240template <class _Tp, class _Compare, class _Allocator>2241template <class _Key>2242pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>2243__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) {2244 using _Pp = pair<iterator, iterator>;2245 __end_node_pointer __result = __end_node();2246 __node_pointer __rt = __root();2247 auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp());2248 while (__rt != nullptr) {2249 auto __comp_res = __comp(__k, __rt->__get_value());2250 if (__comp_res.__less()) {2251 __result = static_cast<__end_node_pointer>(__rt);2252 __rt = static_cast<__node_pointer>(__rt->__left_);2253 } else if (__comp_res.__greater())2254 __rt = static_cast<__node_pointer>(__rt->__right_);2255 else2256 return _Pp(iterator(__rt),2257 iterator(__rt->__right_ != nullptr ? static_cast<__end_node_pointer>(std::__tree_min(__rt->__right_))2258 : __result));2259 }2260 return _Pp(iterator(__result), iterator(__result));2261}2262 2263template <class _Tp, class _Compare, class _Allocator>2264template <class _Key>2265pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,2266 typename __tree<_Tp, _Compare, _Allocator>::const_iterator>2267__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const {2268 using _Pp = pair<const_iterator, const_iterator>;2269 __end_node_pointer __result = __end_node();2270 __node_pointer __rt = __root();2271 auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp());2272 while (__rt != nullptr) {2273 auto __comp_res = __comp(__k, __rt->__get_value());2274 if (__comp_res.__less()) {2275 __result = static_cast<__end_node_pointer>(__rt);2276 __rt = static_cast<__node_pointer>(__rt->__left_);2277 } else if (__comp_res.__greater())2278 __rt = static_cast<__node_pointer>(__rt->__right_);2279 else2280 return _Pp(2281 const_iterator(__rt),2282 const_iterator(2283 __rt->__right_ != nullptr ? static_cast<__end_node_pointer>(std::__tree_min(__rt->__right_)) : __result));2284 }2285 return _Pp(const_iterator(__result), const_iterator(__result));2286}2287 2288template <class _Tp, class _Compare, class _Allocator>2289template <class _Key>2290pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>2291__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) {2292 using _Pp = pair<iterator, iterator>;2293 __end_node_pointer __result = __end_node();2294 __node_pointer __rt = __root();2295 auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp());2296 while (__rt != nullptr) {2297 auto __comp_res = __comp(__k, __rt->__get_value());2298 if (__comp_res.__less()) {2299 __result = static_cast<__end_node_pointer>(__rt);2300 __rt = static_cast<__node_pointer>(__rt->__left_);2301 } else if (__comp_res.__greater())2302 __rt = static_cast<__node_pointer>(__rt->__right_);2303 else2304 return _Pp(2305 __lower_bound_multi(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)),2306 __upper_bound_multi(__k, static_cast<__node_pointer>(__rt->__right_), __result));2307 }2308 return _Pp(iterator(__result), iterator(__result));2309}2310 2311template <class _Tp, class _Compare, class _Allocator>2312template <class _Key>2313pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,2314 typename __tree<_Tp, _Compare, _Allocator>::const_iterator>2315__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const {2316 using _Pp = pair<const_iterator, const_iterator>;2317 __end_node_pointer __result = __end_node();2318 __node_pointer __rt = __root();2319 auto __comp = __lazy_synth_three_way_comparator<value_compare, _Key, value_type>(value_comp());2320 while (__rt != nullptr) {2321 auto __comp_res = __comp(__k, __rt->__get_value());2322 if (__comp_res.__less()) {2323 __result = static_cast<__end_node_pointer>(__rt);2324 __rt = static_cast<__node_pointer>(__rt->__left_);2325 } else if (__comp_res.__greater())2326 __rt = static_cast<__node_pointer>(__rt->__right_);2327 else2328 return _Pp(2329 __lower_bound_multi(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)),2330 __upper_bound_multi(__k, static_cast<__node_pointer>(__rt->__right_), __result));2331 }2332 return _Pp(const_iterator(__result), const_iterator(__result));2333}2334 2335template <class _Tp, class _Compare, class _Allocator>2336typename __tree<_Tp, _Compare, _Allocator>::__node_holder2337__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT {2338 __node_pointer __np = __p.__get_np();2339 if (__begin_node_ == __p.__ptr_) {2340 if (__np->__right_ != nullptr)2341 __begin_node_ = static_cast<__end_node_pointer>(__np->__right_);2342 else2343 __begin_node_ = static_cast<__end_node_pointer>(__np->__parent_);2344 }2345 --__size_;2346 std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np));2347 return __node_holder(__np, _Dp(__node_alloc(), true));2348}2349 2350template <class _Tp, class _Compare, class _Allocator>2351inline _LIBCPP_HIDE_FROM_ABI void swap(__tree<_Tp, _Compare, _Allocator>& __x, __tree<_Tp, _Compare, _Allocator>& __y)2352 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {2353 __x.swap(__y);2354}2355 2356_LIBCPP_END_NAMESPACE_STD2357 2358_LIBCPP_POP_MACROS2359 2360#endif // _LIBCPP___TREE2361