libcxx/include/__tree

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