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