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 private:
 778   ~__tree_node() = delete;
 779   __tree_node(__tree_node const&) = delete;
 780   __tree_node& operator=(__tree_node const&) = delete;
 781 };
 782
 783
 784 template <class _Allocator>
 785 class __tree_node_destructor
 786 {
 787     typedef _Allocator                                      allocator_type;
 788     typedef allocator_traits<allocator_type>                __alloc_traits;
 789
 790 public:
 791     typedef typename __alloc_traits::pointer                pointer;
 792 private:
 793     typedef __tree_node_types<pointer> _NodeTypes;
 794     allocator_type& __na_;
 795
 796
 797 public:
 798     bool __value_constructed;
 799
 800
 801     _LIBCPP_HIDE_FROM_ABI __tree_node_destructor(const __tree_node_destructor &) = default;
 802     __tree_node_destructor& operator=(const __tree_node_destructor&) = delete;
 803
 804     _LIBCPP_INLINE_VISIBILITY
 805     explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT
 806         : __na_(__na),
 807           __value_constructed(__val)
 808         {}
 809
 810     _LIBCPP_INLINE_VISIBILITY
 811     void operator()(pointer __p) _NOEXCEPT
 812     {
 813         if (__value_constructed)
 814             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
 815         if (__p)
 816             __alloc_traits::deallocate(__na_, __p, 1);
 817     }
 818
 819     template <class> friend class __map_node_destructor;
 820 };
 821
 822 #if _LIBCPP_STD_VER >= 17
 823 template <class _NodeType, class _Alloc>
 824 struct __generic_container_node_destructor;
 825 template <class _Tp, class _VoidPtr, class _Alloc>
 826 struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>
 827     : __tree_node_destructor<_Alloc>
 828 {
 829     using __tree_node_destructor<_Alloc>::__tree_node_destructor;
 830 };
 831 #endif
 832
 833 template <class _Tp, class _NodePtr, class _DiffType>
 834 class _LIBCPP_TEMPLATE_VIS __tree_iterator
 835 {
 836     typedef __tree_node_types<_NodePtr>                     _NodeTypes;
 837     typedef _NodePtr                                        __node_pointer;
 838     typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
 839     typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
 840     typedef typename _NodeTypes::__iter_pointer             __iter_pointer;
 841     typedef pointer_traits<__node_pointer> __pointer_traits;
 842
 843     __iter_pointer __ptr_;
 844
 845 public:
 846     typedef bidirectional_iterator_tag                     iterator_category;
 847     typedef _Tp                                            value_type;
 848     typedef _DiffType                                      difference_type;
 849     typedef value_type&                                    reference;
 850     typedef typename _NodeTypes::__node_value_type_pointer pointer;
 851
 852     _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT
 853 #if _LIBCPP_STD_VER >= 14
 854     : __ptr_(nullptr)
 855 #endif
 856     {}
 857
 858     _LIBCPP_INLINE_VISIBILITY reference operator*() const
 859         {return __get_np()->__value_;}
 860     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
 861         {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
 862
 863     _LIBCPP_INLINE_VISIBILITY
 864     __tree_iterator& operator++() {
 865       __ptr_ = static_cast<__iter_pointer>(
 866           _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
 867       return *this;
 868     }
 869     _LIBCPP_INLINE_VISIBILITY
 870     __tree_iterator operator++(int)
 871         {__tree_iterator __t(*this); ++(*this); return __t;}
 872
 873     _LIBCPP_INLINE_VISIBILITY
 874     __tree_iterator& operator--() {
 875       __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>(
 876           static_cast<__end_node_pointer>(__ptr_)));
 877       return *this;
 878     }
 879     _LIBCPP_INLINE_VISIBILITY
 880     __tree_iterator operator--(int)
 881         {__tree_iterator __t(*this); --(*this); return __t;}
 882
 883     friend _LIBCPP_INLINE_VISIBILITY
 884         bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
 885         {return __x.__ptr_ == __y.__ptr_;}
 886     friend _LIBCPP_INLINE_VISIBILITY
 887         bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
 888         {return !(__x == __y);}
 889
 890 private:
 891     _LIBCPP_INLINE_VISIBILITY
 892     explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 893     _LIBCPP_INLINE_VISIBILITY
 894     explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 895     _LIBCPP_INLINE_VISIBILITY
 896     __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
 897     template <class, class, class> friend class __tree;
 898     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
 899     template <class> friend class _LIBCPP_TEMPLATE_VIS __map_iterator;
 900     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
 901     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 902     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
 903     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
 904 };
 905
 906 template <class _Tp, class _NodePtr, class _DiffType>
 907 class _LIBCPP_TEMPLATE_VIS __tree_const_iterator
 908 {
 909     typedef __tree_node_types<_NodePtr>                     _NodeTypes;
 910     typedef typename _NodeTypes::__node_pointer             __node_pointer;
 911     typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
 912     typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
 913     typedef typename _NodeTypes::__iter_pointer             __iter_pointer;
 914     typedef pointer_traits<__node_pointer> __pointer_traits;
 915
 916     __iter_pointer __ptr_;
 917
 918 public:
 919     typedef bidirectional_iterator_tag                           iterator_category;
 920     typedef _Tp                                                  value_type;
 921     typedef _DiffType                                            difference_type;
 922     typedef const value_type&                                    reference;
 923     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 924
 925     _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT
 926 #if _LIBCPP_STD_VER >= 14
 927     : __ptr_(nullptr)
 928 #endif
 929     {}
 930
 931 private:
 932     typedef __tree_iterator<value_type, __node_pointer, difference_type>
 933                                                            __non_const_iterator;
 934 public:
 935     _LIBCPP_INLINE_VISIBILITY
 936     __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
 937         : __ptr_(__p.__ptr_) {}
 938
 939     _LIBCPP_INLINE_VISIBILITY reference operator*() const
 940         {return __get_np()->__value_;}
 941     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
 942         {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
 943
 944     _LIBCPP_INLINE_VISIBILITY
 945     __tree_const_iterator& operator++() {
 946       __ptr_ = static_cast<__iter_pointer>(
 947           _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
 948       return *this;
 949     }
 950
 951     _LIBCPP_INLINE_VISIBILITY
 952     __tree_const_iterator operator++(int)
 953         {__tree_const_iterator __t(*this); ++(*this); return __t;}
 954
 955     _LIBCPP_INLINE_VISIBILITY
 956     __tree_const_iterator& operator--() {
 957       __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>(
 958           static_cast<__end_node_pointer>(__ptr_)));
 959       return *this;
 960     }
 961
 962     _LIBCPP_INLINE_VISIBILITY
 963     __tree_const_iterator operator--(int)
 964         {__tree_const_iterator __t(*this); --(*this); return __t;}
 965
 966     friend _LIBCPP_INLINE_VISIBILITY
 967         bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
 968         {return __x.__ptr_ == __y.__ptr_;}
 969     friend _LIBCPP_INLINE_VISIBILITY
 970         bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
 971         {return !(__x == __y);}
 972
 973 private:
 974     _LIBCPP_INLINE_VISIBILITY
 975     explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
 976         : __ptr_(__p) {}
 977     _LIBCPP_INLINE_VISIBILITY
 978     explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT
 979         : __ptr_(__p) {}
 980     _LIBCPP_INLINE_VISIBILITY
 981     __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
 982
 983     template <class, class, class> friend class __tree;
 984     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
 985     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 986     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
 987     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
 988     template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
 989
 990 };
 991
 992 template<class _Tp, class _Compare>
 993 #ifndef _LIBCPP_CXX03_LANG
 994     _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value,
 995         "the specified comparator type does not provide a viable const call operator")
 996 #endif
 997 int __diagnose_non_const_comparator();
 998
 999 template <class _Tp, class _Compare, class _Allocator>
1000 class __tree
1001 {
1002 public:
1003     typedef _Tp                                      value_type;
1004     typedef _Compare                                 value_compare;
1005     typedef _Allocator                               allocator_type;
1006
1007 private:
1008     typedef allocator_traits<allocator_type>         __alloc_traits;
1009     typedef typename __make_tree_node_types<value_type,
1010         typename __alloc_traits::void_pointer>::type
1011                                                     _NodeTypes;
1012     typedef typename _NodeTypes::key_type           key_type;
1013 public:
1014     typedef typename _NodeTypes::__node_value_type      __node_value_type;
1015     typedef typename _NodeTypes::__container_value_type __container_value_type;
1016
1017     typedef typename __alloc_traits::pointer         pointer;
1018     typedef typename __alloc_traits::const_pointer   const_pointer;
1019     typedef typename __alloc_traits::size_type       size_type;
1020     typedef typename __alloc_traits::difference_type difference_type;
1021
1022 public:
1023     typedef typename _NodeTypes::__void_pointer        __void_pointer;
1024
1025     typedef typename _NodeTypes::__node_type           __node;
1026     typedef typename _NodeTypes::__node_pointer        __node_pointer;
1027
1028     typedef typename _NodeTypes::__node_base_type      __node_base;
1029     typedef typename _NodeTypes::__node_base_pointer   __node_base_pointer;
1030
1031     typedef typename _NodeTypes::__end_node_type       __end_node_t;
1032     typedef typename _NodeTypes::__end_node_pointer    __end_node_ptr;
1033
1034     typedef typename _NodeTypes::__parent_pointer      __parent_pointer;
1035     typedef typename _NodeTypes::__iter_pointer        __iter_pointer;
1036
1037     typedef __rebind_alloc<__alloc_traits, __node> __node_allocator;
1038     typedef allocator_traits<__node_allocator>         __node_traits;
1039
1040 private:
1041     // check for sane allocator pointer rebinding semantics. Rebinding the
1042     // allocator for a new pointer type should be exactly the same as rebinding
1043     // the pointer using 'pointer_traits'.
1044     static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
1045                   "Allocator does not rebind pointers in a sane manner.");
1046     typedef __rebind_alloc<__node_traits, __node_base> __node_base_allocator;
1047     typedef allocator_traits<__node_base_allocator> __node_base_traits;
1048     static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
1049                  "Allocator does not rebind pointers in a sane manner.");
1050
1051 private:
1052     __iter_pointer                                     __begin_node_;
1053     __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
1054     __compressed_pair<size_type, value_compare>        __pair3_;
1055
1056 public:
1057     _LIBCPP_INLINE_VISIBILITY
1058     __iter_pointer __end_node() _NOEXCEPT
1059     {
1060         return static_cast<__iter_pointer>(
1061                 pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
1062         );
1063     }
1064     _LIBCPP_INLINE_VISIBILITY
1065     __iter_pointer __end_node() const _NOEXCEPT
1066     {
1067         return static_cast<__iter_pointer>(
1068             pointer_traits<__end_node_ptr>::pointer_to(
1069                 const_cast<__end_node_t&>(__pair1_.first())
1070             )
1071         );
1072     }
1073     _LIBCPP_INLINE_VISIBILITY
1074           __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}
1075 private:
1076     _LIBCPP_INLINE_VISIBILITY
1077     const __node_allocator& __node_alloc() const _NOEXCEPT
1078         {return __pair1_.second();}
1079     _LIBCPP_INLINE_VISIBILITY
1080           __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
1081     _LIBCPP_INLINE_VISIBILITY
1082     const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
1083 public:
1084     _LIBCPP_INLINE_VISIBILITY
1085     allocator_type __alloc() const _NOEXCEPT
1086         {return allocator_type(__node_alloc());}
1087 private:
1088     _LIBCPP_INLINE_VISIBILITY
1089           size_type& size() _NOEXCEPT {return __pair3_.first();}
1090 public:
1091     _LIBCPP_INLINE_VISIBILITY
1092     const size_type& size() const _NOEXCEPT {return __pair3_.first();}
1093     _LIBCPP_INLINE_VISIBILITY
1094           value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}
1095     _LIBCPP_INLINE_VISIBILITY
1096     const value_compare& value_comp() const _NOEXCEPT
1097         {return __pair3_.second();}
1098 public:
1099
1100     _LIBCPP_INLINE_VISIBILITY
1101     __node_pointer __root() const _NOEXCEPT
1102         {return static_cast<__node_pointer>(__end_node()->__left_);}
1103
1104     _LIBCPP_HIDE_FROM_ABI __node_base_pointer* __root_ptr() const _NOEXCEPT {
1105         return _VSTD::addressof(__end_node()->__left_);
1106     }
1107
1108     typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
1109     typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
1110
1111     _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp)
1112         _NOEXCEPT_(
1113             is_nothrow_default_constructible<__node_allocator>::value &&
1114             is_nothrow_copy_constructible<value_compare>::value);
1115     _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a);
1116     _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a);
1117     _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t);
1118     _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t);
1119     template <class _ForwardIterator>
1120     _LIBCPP_HIDE_FROM_ABI void __assign_unique(_ForwardIterator __first, _ForwardIterator __last);
1121     template <class _InputIterator>
1122     _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
1123     _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t)
1124         _NOEXCEPT_(
1125             is_nothrow_move_constructible<__node_allocator>::value &&
1126             is_nothrow_move_constructible<value_compare>::value);
1127     _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a);
1128     _LIBCPP_HIDE_FROM_ABI __tree& operator=(__tree&& __t)
1129         _NOEXCEPT_(
1130             __node_traits::propagate_on_container_move_assignment::value &&
1131             is_nothrow_move_assignable<value_compare>::value &&
1132             is_nothrow_move_assignable<__node_allocator>::value);
1133     _LIBCPP_HIDE_FROM_ABI ~__tree();
1134
1135     _LIBCPP_INLINE_VISIBILITY
1136           iterator begin()  _NOEXCEPT {return       iterator(__begin_node());}
1137     _LIBCPP_INLINE_VISIBILITY
1138     const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());}
1139     _LIBCPP_INLINE_VISIBILITY
1140           iterator end() _NOEXCEPT {return       iterator(__end_node());}
1141     _LIBCPP_INLINE_VISIBILITY
1142     const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());}
1143
1144     _LIBCPP_INLINE_VISIBILITY
1145     size_type max_size() const _NOEXCEPT
1146         {return _VSTD::min<size_type>(
1147                 __node_traits::max_size(__node_alloc()),
1148                 numeric_limits<difference_type >::max());}
1149
1150     _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
1151
1152     _LIBCPP_HIDE_FROM_ABI void swap(__tree& __t)
1153 #if _LIBCPP_STD_VER <= 11
1154         _NOEXCEPT_(
1155             __is_nothrow_swappable<value_compare>::value
1156             && (!__node_traits::propagate_on_container_swap::value ||
1157                  __is_nothrow_swappable<__node_allocator>::value)
1158             );
1159 #else
1160         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value);
1161 #endif
1162
1163     template <class _Key, class ..._Args>
1164     _LIBCPP_HIDE_FROM_ABI pair<iterator, bool>
1165     __emplace_unique_key_args(_Key const&, _Args&&... __args);
1166     template <class _Key, class ..._Args>
1167     _LIBCPP_HIDE_FROM_ABI pair<iterator, bool>
1168     __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
1169
1170     template <class... _Args>
1171     _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
1172
1173     template <class... _Args>
1174     _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
1175
1176     template <class... _Args>
1177     _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
1178
1179     template <class... _Args>
1180     _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1181
1182     template <class _Pp>
1183     _LIBCPP_INLINE_VISIBILITY
1184     pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1185         return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1186                                             __can_extract_key<_Pp, key_type>());
1187     }
1188
1189     template <class _First, class _Second,
1190               __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
1191     _LIBCPP_INLINE_VISIBILITY
1192     pair<iterator, bool>
1193     __emplace_unique(_First&& __f, _Second&& __s) {
1194         return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
1195                                               _VSTD::forward<_Second>(__s));
1196     }
1197
1198     template <class... _Args>
1199     _LIBCPP_INLINE_VISIBILITY
1200     pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1201         return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1202     }
1203
1204     template <class _Pp>
1205     _LIBCPP_INLINE_VISIBILITY
1206     pair<iterator, bool>
1207     __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1208       return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1209     }
1210
1211     template <class _Pp>
1212     _LIBCPP_INLINE_VISIBILITY
1213     pair<iterator, bool>
1214     __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1215       return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1216     }
1217
1218     template <class _Pp>
1219     _LIBCPP_INLINE_VISIBILITY
1220     pair<iterator, bool>
1221     __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1222       return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1223     }
1224
1225     template <class _Pp>
1226     _LIBCPP_INLINE_VISIBILITY
1227     iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
1228         return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
1229                                             __can_extract_key<_Pp, key_type>());
1230     }
1231
1232     template <class _First, class _Second,
1233               __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
1234     _LIBCPP_INLINE_VISIBILITY
1235     iterator
1236     __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
1237         return __emplace_hint_unique_key_args(__p, __f,
1238                                               _VSTD::forward<_First>(__f),
1239                                               _VSTD::forward<_Second>(__s)).first;
1240     }
1241
1242     template <class... _Args>
1243     _LIBCPP_INLINE_VISIBILITY
1244     iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
1245         return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...);
1246     }
1247
1248     template <class _Pp>
1249     _LIBCPP_INLINE_VISIBILITY
1250     iterator
1251     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
1252       return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
1253     }
1254
1255     template <class _Pp>
1256     _LIBCPP_INLINE_VISIBILITY
1257     iterator
1258     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
1259       return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first;
1260     }
1261
1262     template <class _Pp>
1263     _LIBCPP_INLINE_VISIBILITY
1264     iterator
1265     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
1266       return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first;
1267     }
1268
1269     _LIBCPP_INLINE_VISIBILITY
1270     pair<iterator, bool> __insert_unique(const __container_value_type& __v) {
1271         return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v);
1272     }
1273
1274     _LIBCPP_INLINE_VISIBILITY
1275     iterator __insert_unique(const_iterator __p, const __container_value_type& __v) {
1276         return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first;
1277     }
1278
1279     _LIBCPP_INLINE_VISIBILITY
1280     pair<iterator, bool> __insert_unique(__container_value_type&& __v) {
1281         return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v));
1282     }
1283
1284     _LIBCPP_INLINE_VISIBILITY
1285     iterator __insert_unique(const_iterator __p, __container_value_type&& __v) {
1286         return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first;
1287     }
1288
1289     template <class _Vp,
1290               class = __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value> >
1291     _LIBCPP_INLINE_VISIBILITY
1292     pair<iterator, bool> __insert_unique(_Vp&& __v) {
1293         return __emplace_unique(_VSTD::forward<_Vp>(__v));
1294     }
1295
1296     template <class _Vp,
1297               class = __enable_if_t<!is_same<__remove_const_ref_t<_Vp>, __container_value_type>::value> >
1298     _LIBCPP_INLINE_VISIBILITY
1299     iterator __insert_unique(const_iterator __p, _Vp&& __v) {
1300         return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v));
1301     }
1302
1303     _LIBCPP_INLINE_VISIBILITY
1304     iterator __insert_multi(__container_value_type&& __v) {
1305         return __emplace_multi(_VSTD::move(__v));
1306     }
1307
1308     _LIBCPP_INLINE_VISIBILITY
1309     iterator __insert_multi(const_iterator __p, __container_value_type&& __v) {
1310         return __emplace_hint_multi(__p, _VSTD::move(__v));
1311     }
1312
1313     template <class _Vp>
1314     _LIBCPP_INLINE_VISIBILITY
1315     iterator __insert_multi(_Vp&& __v) {
1316         return __emplace_multi(_VSTD::forward<_Vp>(__v));
1317     }
1318
1319     template <class _Vp>
1320     _LIBCPP_INLINE_VISIBILITY
1321     iterator __insert_multi(const_iterator __p, _Vp&& __v) {
1322         return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v));
1323     }
1324
1325     _LIBCPP_INLINE_VISIBILITY
1326     pair<iterator, bool> __node_assign_unique(const __container_value_type& __v, __node_pointer __dest);
1327
1328     _LIBCPP_INLINE_VISIBILITY
1329     iterator __node_insert_multi(__node_pointer __nd);
1330     _LIBCPP_INLINE_VISIBILITY
1331     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
1332
1333
1334     _LIBCPP_INLINE_VISIBILITY iterator
1335     __remove_node_pointer(__node_pointer) _NOEXCEPT;
1336
1337 #if _LIBCPP_STD_VER >= 17
1338     template <class _NodeHandle, class _InsertReturnType>
1339     _LIBCPP_INLINE_VISIBILITY
1340     _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
1341     template <class _NodeHandle>
1342     _LIBCPP_INLINE_VISIBILITY
1343     iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
1344     template <class _Tree>
1345     _LIBCPP_INLINE_VISIBILITY
1346     void __node_handle_merge_unique(_Tree& __source);
1347
1348     template <class _NodeHandle>
1349     _LIBCPP_INLINE_VISIBILITY
1350     iterator __node_handle_insert_multi(_NodeHandle&&);
1351     template <class _NodeHandle>
1352     _LIBCPP_INLINE_VISIBILITY
1353     iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
1354     template <class _Tree>
1355     _LIBCPP_INLINE_VISIBILITY
1356     void __node_handle_merge_multi(_Tree& __source);
1357
1358
1359     template <class _NodeHandle>
1360     _LIBCPP_INLINE_VISIBILITY
1361     _NodeHandle __node_handle_extract(key_type const&);
1362     template <class _NodeHandle>
1363     _LIBCPP_INLINE_VISIBILITY
1364     _NodeHandle __node_handle_extract(const_iterator);
1365 #endif
1366
1367     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
1368     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
1369     template <class _Key>
1370     _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
1371     template <class _Key>
1372     _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
1373
1374     _LIBCPP_HIDE_FROM_ABI void __insert_node_at(__parent_pointer     __parent,
1375                           __node_base_pointer& __child,
1376                           __node_base_pointer __new_node) _NOEXCEPT;
1377
1378     template <class _Key>
1379     _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __v);
1380     template <class _Key>
1381     _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __v) const;
1382
1383     template <class _Key>
1384     _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
1385     template <class _Key>
1386     _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
1387
1388     template <class _Key>
1389         _LIBCPP_INLINE_VISIBILITY
1390         iterator lower_bound(const _Key& __v)
1391             {return __lower_bound(__v, __root(), __end_node());}
1392     template <class _Key>
1393     _LIBCPP_HIDE_FROM_ABI iterator __lower_bound(const _Key& __v,
1394                                __node_pointer __root,
1395                                __iter_pointer __result);
1396     template <class _Key>
1397         _LIBCPP_INLINE_VISIBILITY
1398         const_iterator lower_bound(const _Key& __v) const
1399             {return __lower_bound(__v, __root(), __end_node());}
1400     template <class _Key>
1401     _LIBCPP_HIDE_FROM_ABI const_iterator __lower_bound(const _Key& __v,
1402                                      __node_pointer __root,
1403                                      __iter_pointer __result) const;
1404     template <class _Key>
1405         _LIBCPP_INLINE_VISIBILITY
1406         iterator upper_bound(const _Key& __v)
1407             {return __upper_bound(__v, __root(), __end_node());}
1408     template <class _Key>
1409     _LIBCPP_HIDE_FROM_ABI iterator __upper_bound(const _Key& __v,
1410                                __node_pointer __root,
1411                                __iter_pointer __result);
1412     template <class _Key>
1413         _LIBCPP_INLINE_VISIBILITY
1414         const_iterator upper_bound(const _Key& __v) const
1415             {return __upper_bound(__v, __root(), __end_node());}
1416     template <class _Key>
1417     _LIBCPP_HIDE_FROM_ABI const_iterator __upper_bound(const _Key& __v,
1418                                      __node_pointer __root,
1419                                      __iter_pointer __result) const;
1420     template <class _Key>
1421     _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator>
1422         __equal_range_unique(const _Key& __k);
1423     template <class _Key>
1424     _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator>
1425         __equal_range_unique(const _Key& __k) const;
1426
1427     template <class _Key>
1428     _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator>
1429         __equal_range_multi(const _Key& __k);
1430     template <class _Key>
1431     _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator>
1432         __equal_range_multi(const _Key& __k) const;
1433
1434     typedef __tree_node_destructor<__node_allocator> _Dp;
1435     typedef unique_ptr<__node, _Dp> __node_holder;
1436
1437     _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
1438 private:
1439     _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_low(__parent_pointer& __parent, const key_type& __v);
1440     _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_high(__parent_pointer& __parent, const key_type& __v);
1441     _LIBCPP_HIDE_FROM_ABI __node_base_pointer&
1442     __find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v);
1443     // FIXME: Make this function const qualified. Unfortunately doing so
1444     // breaks existing code which uses non-const callable comparators.
1445     template <class _Key>
1446     _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v);
1447     template <class _Key>
1448     _LIBCPP_INLINE_VISIBILITY __node_base_pointer&
1449     __find_equal(__parent_pointer& __parent, const _Key& __v) const {
1450       return const_cast<__tree*>(this)->__find_equal(__parent, __v);
1451     }
1452     template <class _Key>
1453     _LIBCPP_HIDE_FROM_ABI __node_base_pointer&
1454         __find_equal(const_iterator __hint, __parent_pointer& __parent,
1455                      __node_base_pointer& __dummy,
1456                      const _Key& __v);
1457
1458     template <class ..._Args>
1459     _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&& ...__args);
1460
1461     // TODO: Make this _LIBCPP_HIDE_FROM_ABI
1462     _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT;
1463
1464     _LIBCPP_INLINE_VISIBILITY
1465     void __copy_assign_alloc(const __tree& __t)
1466         {__copy_assign_alloc(__t, integral_constant<bool,
1467              __node_traits::propagate_on_container_copy_assignment::value>());}
1468
1469     _LIBCPP_INLINE_VISIBILITY
1470     void __copy_assign_alloc(const __tree& __t, true_type)
1471         {
1472         if (__node_alloc() != __t.__node_alloc())
1473             clear();
1474         __node_alloc() = __t.__node_alloc();
1475         }
1476     _LIBCPP_INLINE_VISIBILITY
1477     void __copy_assign_alloc(const __tree&, false_type) {}
1478
1479     _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type);
1480     _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type)
1481         _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1482                    is_nothrow_move_assignable<__node_allocator>::value);
1483
1484     _LIBCPP_INLINE_VISIBILITY
1485     void __move_assign_alloc(__tree& __t)
1486         _NOEXCEPT_(
1487             !__node_traits::propagate_on_container_move_assignment::value ||
1488             is_nothrow_move_assignable<__node_allocator>::value)
1489         {__move_assign_alloc(__t, integral_constant<bool,
1490              __node_traits::propagate_on_container_move_assignment::value>());}
1491
1492     _LIBCPP_INLINE_VISIBILITY
1493     void __move_assign_alloc(__tree& __t, true_type)
1494         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1495         {__node_alloc() = _VSTD::move(__t.__node_alloc());}
1496     _LIBCPP_INLINE_VISIBILITY
1497     void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}
1498
1499     struct _DetachedTreeCache {
1500       _LIBCPP_INLINE_VISIBILITY
1501       explicit _DetachedTreeCache(__tree *__t) _NOEXCEPT : __t_(__t),
1502         __cache_root_(__detach_from_tree(__t)) {
1503           __advance();
1504         }
1505
1506       _LIBCPP_INLINE_VISIBILITY
1507       __node_pointer __get() const _NOEXCEPT {
1508         return __cache_elem_;
1509       }
1510
1511       _LIBCPP_INLINE_VISIBILITY
1512       void __advance() _NOEXCEPT {
1513         __cache_elem_ = __cache_root_;
1514         if (__cache_root_) {
1515           __cache_root_ = __detach_next(__cache_root_);
1516         }
1517       }
1518
1519       _LIBCPP_INLINE_VISIBILITY
1520       ~_DetachedTreeCache() {
1521         __t_->destroy(__cache_elem_);
1522         if (__cache_root_) {
1523           while (__cache_root_->__parent_ != nullptr)
1524             __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_);
1525           __t_->destroy(__cache_root_);
1526         }
1527       }
1528
1529        _DetachedTreeCache(_DetachedTreeCache const&) = delete;
1530        _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete;
1531
1532     private:
1533       _LIBCPP_INLINE_VISIBILITY
1534       static __node_pointer __detach_from_tree(__tree *__t) _NOEXCEPT;
1535       _LIBCPP_INLINE_VISIBILITY
1536       static __node_pointer __detach_next(__node_pointer) _NOEXCEPT;
1537
1538       __tree *__t_;
1539       __node_pointer __cache_root_;
1540       __node_pointer __cache_elem_;
1541     };
1542
1543
1544     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
1545     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
1546 };
1547
1548 template <class _Tp, class _Compare, class _Allocator>
1549 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
1550         _NOEXCEPT_(
1551             is_nothrow_default_constructible<__node_allocator>::value &&
1552             is_nothrow_copy_constructible<value_compare>::value)
1553     : __pair3_(0, __comp)
1554 {
1555     __begin_node() = __end_node();
1556 }
1557
1558 template <class _Tp, class _Compare, class _Allocator>
1559 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1560     : __begin_node_(__iter_pointer()),
1561       __pair1_(__default_init_tag(), __node_allocator(__a)),
1562       __pair3_(0, __default_init_tag())
1563 {
1564     __begin_node() = __end_node();
1565 }
1566
1567 template <class _Tp, class _Compare, class _Allocator>
1568 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
1569                                            const allocator_type& __a)
1570     : __begin_node_(__iter_pointer()),
1571       __pair1_(__default_init_tag(), __node_allocator(__a)),
1572       __pair3_(0, __comp)
1573 {
1574     __begin_node() = __end_node();
1575 }
1576
1577 // Precondition:  size() != 0
1578 template <class _Tp, class _Compare, class _Allocator>
1579 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1580 __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree *__t) _NOEXCEPT
1581 {
1582     __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node());
1583     __t->__begin_node() = __t->__end_node();
1584     __t->__end_node()->__left_->__parent_ = nullptr;
1585     __t->__end_node()->__left_ = nullptr;
1586     __t->size() = 0;
1587     // __cache->__left_ == nullptr
1588     if (__cache->__right_ != nullptr)
1589         __cache = static_cast<__node_pointer>(__cache->__right_);
1590     // __cache->__left_ == nullptr
1591     // __cache->__right_ == nullptr
1592     return __cache;
1593 }
1594
1595 // Precondition:  __cache != nullptr
1596 //    __cache->left_ == nullptr
1597 //    __cache->right_ == nullptr
1598 //    This is no longer a red-black tree
1599 template <class _Tp, class _Compare, class _Allocator>
1600 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1601 __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT
1602 {
1603     if (__cache->__parent_ == nullptr)
1604         return nullptr;
1605     if (_VSTD::__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1606     {
1607         __cache->__parent_->__left_ = nullptr;
1608         __cache = static_cast<__node_pointer>(__cache->__parent_);
1609         if (__cache->__right_ == nullptr)
1610             return __cache;
1611         return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__right_));
1612     }
1613     // __cache is right child
1614     __cache->__parent_unsafe()->__right_ = nullptr;
1615     __cache = static_cast<__node_pointer>(__cache->__parent_);
1616     if (__cache->__left_ == nullptr)
1617         return __cache;
1618     return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_));
1619 }
1620
1621 template <class _Tp, class _Compare, class _Allocator>
1622 __tree<_Tp, _Compare, _Allocator>&
1623 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
1624 {
1625     if (this != _VSTD::addressof(__t))
1626     {
1627         value_comp() = __t.value_comp();
1628         __copy_assign_alloc(__t);
1629         __assign_multi(__t.begin(), __t.end());
1630     }
1631     return *this;
1632 }
1633
1634 template <class _Tp, class _Compare, class _Allocator>
1635 template <class _ForwardIterator>
1636 void
1637 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last)
1638 {
1639     typedef iterator_traits<_ForwardIterator> _ITraits;
1640     typedef typename _ITraits::value_type _ItValueType;
1641     static_assert((is_same<_ItValueType, __container_value_type>::value),
1642                   "__assign_unique may only be called with the containers value type");
1643     static_assert(__has_forward_iterator_category<_ForwardIterator>::value,
1644                   "__assign_unique requires a forward iterator");
1645     if (size() != 0)
1646     {
1647         _DetachedTreeCache __cache(this);
1648           for (; __cache.__get() != nullptr && __first != __last; ++__first) {
1649               if (__node_assign_unique(*__first, __cache.__get()).second)
1650                   __cache.__advance();
1651             }
1652     }
1653     for (; __first != __last; ++__first)
1654         __insert_unique(*__first);
1655 }
1656
1657 template <class _Tp, class _Compare, class _Allocator>
1658 template <class _InputIterator>
1659 void
1660 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
1661 {
1662     typedef iterator_traits<_InputIterator> _ITraits;
1663     typedef typename _ITraits::value_type _ItValueType;
1664     static_assert((is_same<_ItValueType, __container_value_type>::value ||
1665                   is_same<_ItValueType, __node_value_type>::value),
1666                   "__assign_multi may only be called with the containers value type"
1667                   " or the nodes value type");
1668     if (size() != 0)
1669     {
1670         _DetachedTreeCache __cache(this);
1671         for (; __cache.__get() && __first != __last; ++__first) {
1672             __cache.__get()->__value_ = *__first;
1673             __node_insert_multi(__cache.__get());
1674             __cache.__advance();
1675         }
1676     }
1677     for (; __first != __last; ++__first)
1678         __insert_multi(_NodeTypes::__get_value(*__first));
1679 }
1680
1681 template <class _Tp, class _Compare, class _Allocator>
1682 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1683     : __begin_node_(__iter_pointer()),
1684       __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1685       __pair3_(0, __t.value_comp())
1686 {
1687     __begin_node() = __end_node();
1688 }
1689
1690 template <class _Tp, class _Compare, class _Allocator>
1691 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
1692     _NOEXCEPT_(
1693         is_nothrow_move_constructible<__node_allocator>::value &&
1694         is_nothrow_move_constructible<value_compare>::value)
1695     : __begin_node_(_VSTD::move(__t.__begin_node_)),
1696       __pair1_(_VSTD::move(__t.__pair1_)),
1697       __pair3_(_VSTD::move(__t.__pair3_))
1698 {
1699     if (size() == 0)
1700         __begin_node() = __end_node();
1701     else
1702     {
1703         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1704         __t.__begin_node() = __t.__end_node();
1705         __t.__end_node()->__left_ = nullptr;
1706         __t.size() = 0;
1707     }
1708 }
1709
1710 template <class _Tp, class _Compare, class _Allocator>
1711 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1712     : __pair1_(__default_init_tag(), __node_allocator(__a)),
1713       __pair3_(0, _VSTD::move(__t.value_comp()))
1714 {
1715     if (__a == __t.__alloc())
1716     {
1717         if (__t.size() == 0)
1718             __begin_node() = __end_node();
1719         else
1720         {
1721             __begin_node() = __t.__begin_node();
1722             __end_node()->__left_ = __t.__end_node()->__left_;
1723             __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1724             size() = __t.size();
1725             __t.__begin_node() = __t.__end_node();
1726             __t.__end_node()->__left_ = nullptr;
1727             __t.size() = 0;
1728         }
1729     }
1730     else
1731     {
1732         __begin_node() = __end_node();
1733     }
1734 }
1735
1736 template <class _Tp, class _Compare, class _Allocator>
1737 void
1738 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1739     _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1740                is_nothrow_move_assignable<__node_allocator>::value)
1741 {
1742     destroy(static_cast<__node_pointer>(__end_node()->__left_));
1743     __begin_node_ = __t.__begin_node_;
1744     __pair1_.first() = __t.__pair1_.first();
1745     __move_assign_alloc(__t);
1746     __pair3_ = _VSTD::move(__t.__pair3_);
1747     if (size() == 0)
1748         __begin_node() = __end_node();
1749     else
1750     {
1751         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1752         __t.__begin_node() = __t.__end_node();
1753         __t.__end_node()->__left_ = nullptr;
1754         __t.size() = 0;
1755     }
1756 }
1757
1758 template <class _Tp, class _Compare, class _Allocator>
1759 void
1760 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
1761 {
1762     if (__node_alloc() == __t.__node_alloc())
1763         __move_assign(__t, true_type());
1764     else
1765     {
1766         value_comp() = _VSTD::move(__t.value_comp());
1767         const_iterator __e = end();
1768         if (size() != 0)
1769         {
1770             _DetachedTreeCache __cache(this);
1771             while (__cache.__get() != nullptr && __t.size() != 0) {
1772               __cache.__get()->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
1773               __node_insert_multi(__cache.__get());
1774               __cache.__advance();
1775             }
1776         }
1777         while (__t.size() != 0)
1778             __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_));
1779     }
1780 }
1781
1782 template <class _Tp, class _Compare, class _Allocator>
1783 __tree<_Tp, _Compare, _Allocator>&
1784 __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1785     _NOEXCEPT_(
1786         __node_traits::propagate_on_container_move_assignment::value &&
1787         is_nothrow_move_assignable<value_compare>::value &&
1788         is_nothrow_move_assignable<__node_allocator>::value)
1789
1790 {
1791     __move_assign(__t, integral_constant<bool,
1792                   __node_traits::propagate_on_container_move_assignment::value>());
1793     return *this;
1794 }
1795
1796 template <class _Tp, class _Compare, class _Allocator>
1797 __tree<_Tp, _Compare, _Allocator>::~__tree()
1798 {
1799     static_assert((is_copy_constructible<value_compare>::value),
1800                  "Comparator must be copy-constructible.");
1801   destroy(__root());
1802 }
1803
1804 template <class _Tp, class _Compare, class _Allocator>
1805 void
1806 __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
1807 {
1808     if (__nd != nullptr)
1809     {
1810         destroy(static_cast<__node_pointer>(__nd->__left_));
1811         destroy(static_cast<__node_pointer>(__nd->__right_));
1812         __node_allocator& __na = __node_alloc();
1813         __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_));
1814         __node_traits::deallocate(__na, __nd, 1);
1815     }
1816 }
1817
1818 template <class _Tp, class _Compare, class _Allocator>
1819 void
1820 __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1821 #if _LIBCPP_STD_VER <= 11
1822         _NOEXCEPT_(
1823             __is_nothrow_swappable<value_compare>::value
1824             && (!__node_traits::propagate_on_container_swap::value ||
1825                  __is_nothrow_swappable<__node_allocator>::value)
1826             )
1827 #else
1828         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value)
1829 #endif
1830 {
1831     using _VSTD::swap;
1832     swap(__begin_node_, __t.__begin_node_);
1833     swap(__pair1_.first(), __t.__pair1_.first());
1834     _VSTD::__swap_allocator(__node_alloc(), __t.__node_alloc());
1835     __pair3_.swap(__t.__pair3_);
1836     if (size() == 0)
1837         __begin_node() = __end_node();
1838     else
1839         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1840     if (__t.size() == 0)
1841         __t.__begin_node() = __t.__end_node();
1842     else
1843         __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());
1844 }
1845
1846 template <class _Tp, class _Compare, class _Allocator>
1847 void
1848 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
1849 {
1850     destroy(__root());
1851     size() = 0;
1852     __begin_node() = __end_node();
1853     __end_node()->__left_ = nullptr;
1854 }
1855
1856 // Find lower_bound place to insert
1857 // Set __parent to parent of null leaf
1858 // Return reference to null leaf
1859 template <class _Tp, class _Compare, class _Allocator>
1860 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1861 __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent,
1862                                                    const key_type& __v)
1863 {
1864     __node_pointer __nd = __root();
1865     if (__nd != nullptr)
1866     {
1867         while (true)
1868         {
1869             if (value_comp()(__nd->__value_, __v))
1870             {
1871                 if (__nd->__right_ != nullptr)
1872                     __nd = static_cast<__node_pointer>(__nd->__right_);
1873                 else
1874                 {
1875                     __parent = static_cast<__parent_pointer>(__nd);
1876                     return __nd->__right_;
1877                 }
1878             }
1879             else
1880             {
1881                 if (__nd->__left_ != nullptr)
1882                     __nd = static_cast<__node_pointer>(__nd->__left_);
1883                 else
1884                 {
1885                     __parent = static_cast<__parent_pointer>(__nd);
1886                     return __parent->__left_;
1887                 }
1888             }
1889         }
1890     }
1891     __parent = static_cast<__parent_pointer>(__end_node());
1892     return __parent->__left_;
1893 }
1894
1895 // Find upper_bound place to insert
1896 // Set __parent to parent of null leaf
1897 // Return reference to null leaf
1898 template <class _Tp, class _Compare, class _Allocator>
1899 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1900 __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent,
1901                                                     const key_type& __v)
1902 {
1903     __node_pointer __nd = __root();
1904     if (__nd != nullptr)
1905     {
1906         while (true)
1907         {
1908             if (value_comp()(__v, __nd->__value_))
1909             {
1910                 if (__nd->__left_ != nullptr)
1911                     __nd = static_cast<__node_pointer>(__nd->__left_);
1912                 else
1913                 {
1914                     __parent = static_cast<__parent_pointer>(__nd);
1915                     return __parent->__left_;
1916                 }
1917             }
1918             else
1919             {
1920                 if (__nd->__right_ != nullptr)
1921                     __nd = static_cast<__node_pointer>(__nd->__right_);
1922                 else
1923                 {
1924                     __parent = static_cast<__parent_pointer>(__nd);
1925                     return __nd->__right_;
1926                 }
1927             }
1928         }
1929     }
1930     __parent = static_cast<__parent_pointer>(__end_node());
1931     return __parent->__left_;
1932 }
1933
1934 // Find leaf place to insert closest to __hint
1935 // First check prior to __hint.
1936 // Next check after __hint.
1937 // Next do O(log N) search.
1938 // Set __parent to parent of null leaf
1939 // Return reference to null leaf
1940 template <class _Tp, class _Compare, class _Allocator>
1941 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1942 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
1943                                                __parent_pointer& __parent,
1944                                                const key_type& __v)
1945 {
1946     if (__hint == end() || !value_comp()(*__hint, __v))  // check before
1947     {
1948         // __v <= *__hint
1949         const_iterator __prior = __hint;
1950         if (__prior == begin() || !value_comp()(__v, *--__prior))
1951         {
1952             // *prev(__hint) <= __v <= *__hint
1953             if (__hint.__ptr_->__left_ == nullptr)
1954             {
1955                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
1956                 return __parent->__left_;
1957             }
1958             else
1959             {
1960                 __parent = static_cast<__parent_pointer>(__prior.__ptr_);
1961                 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
1962             }
1963         }
1964         // __v < *prev(__hint)
1965         return __find_leaf_high(__parent, __v);
1966     }
1967     // else __v > *__hint
1968     return __find_leaf_low(__parent, __v);
1969 }
1970
1971 // Find place to insert if __v doesn't exist
1972 // Set __parent to parent of null leaf
1973 // Return reference to null leaf
1974 // If __v exists, set parent to node of __v and return reference to node of __v
1975 template <class _Tp, class _Compare, class _Allocator>
1976 template <class _Key>
1977 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1978 __tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent,
1979                                                 const _Key& __v)
1980 {
1981     __node_pointer __nd = __root();
1982     __node_base_pointer* __nd_ptr = __root_ptr();
1983     if (__nd != nullptr)
1984     {
1985         while (true)
1986         {
1987             if (value_comp()(__v, __nd->__value_))
1988             {
1989                 if (__nd->__left_ != nullptr) {
1990                     __nd_ptr = _VSTD::addressof(__nd->__left_);
1991                     __nd = static_cast<__node_pointer>(__nd->__left_);
1992                 } else {
1993                     __parent = static_cast<__parent_pointer>(__nd);
1994                     return __parent->__left_;
1995                 }
1996             }
1997             else if (value_comp()(__nd->__value_, __v))
1998             {
1999                 if (__nd->__right_ != nullptr) {
2000                     __nd_ptr = _VSTD::addressof(__nd->__right_);
2001                     __nd = static_cast<__node_pointer>(__nd->__right_);
2002                 } else {
2003                     __parent = static_cast<__parent_pointer>(__nd);
2004                     return __nd->__right_;
2005                 }
2006             }
2007             else
2008             {
2009                 __parent = static_cast<__parent_pointer>(__nd);
2010                 return *__nd_ptr;
2011             }
2012         }
2013     }
2014     __parent = static_cast<__parent_pointer>(__end_node());
2015     return __parent->__left_;
2016 }
2017
2018 // Find place to insert if __v doesn't exist
2019 // First check prior to __hint.
2020 // Next check after __hint.
2021 // Next do O(log N) search.
2022 // Set __parent to parent of null leaf
2023 // Return reference to null leaf
2024 // If __v exists, set parent to node of __v and return reference to node of __v
2025 template <class _Tp, class _Compare, class _Allocator>
2026 template <class _Key>
2027 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
2028 __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
2029                                                 __parent_pointer& __parent,
2030                                                 __node_base_pointer& __dummy,
2031                                                 const _Key& __v)
2032 {
2033     if (__hint == end() || value_comp()(__v, *__hint))  // check before
2034     {
2035         // __v < *__hint
2036         const_iterator __prior = __hint;
2037         if (__prior == begin() || value_comp()(*--__prior, __v))
2038         {
2039             // *prev(__hint) < __v < *__hint
2040             if (__hint.__ptr_->__left_ == nullptr)
2041             {
2042                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2043                 return __parent->__left_;
2044             }
2045             else
2046             {
2047                 __parent = static_cast<__parent_pointer>(__prior.__ptr_);
2048                 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
2049             }
2050         }
2051         // __v <= *prev(__hint)
2052         return __find_equal(__parent, __v);
2053     }
2054     else if (value_comp()(*__hint, __v))  // check after
2055     {
2056         // *__hint < __v
2057         const_iterator __next = _VSTD::next(__hint);
2058         if (__next == end() || value_comp()(__v, *__next))
2059         {
2060             // *__hint < __v < *_VSTD::next(__hint)
2061             if (__hint.__get_np()->__right_ == nullptr)
2062             {
2063                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2064                 return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
2065             }
2066             else
2067             {
2068                 __parent = static_cast<__parent_pointer>(__next.__ptr_);
2069                 return __parent->__left_;
2070             }
2071         }
2072         // *next(__hint) <= __v
2073         return __find_equal(__parent, __v);
2074     }
2075     // else __v == *__hint
2076     __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2077     __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
2078     return __dummy;
2079 }
2080
2081 template <class _Tp, class _Compare, class _Allocator>
2082 void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
2083     __parent_pointer __parent, __node_base_pointer& __child,
2084     __node_base_pointer __new_node) _NOEXCEPT
2085 {
2086     __new_node->__left_   = nullptr;
2087     __new_node->__right_  = nullptr;
2088     __new_node->__parent_ = __parent;
2089     // __new_node->__is_black_ is initialized in __tree_balance_after_insert
2090     __child = __new_node;
2091     if (__begin_node()->__left_ != nullptr)
2092         __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
2093     _VSTD::__tree_balance_after_insert(__end_node()->__left_, __child);
2094     ++size();
2095 }
2096
2097 template <class _Tp, class _Compare, class _Allocator>
2098 template <class _Key, class... _Args>
2099 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2100 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
2101 {
2102     __parent_pointer __parent;
2103     __node_base_pointer& __child = __find_equal(__parent, __k);
2104     __node_pointer __r = static_cast<__node_pointer>(__child);
2105     bool __inserted = false;
2106     if (__child == nullptr)
2107     {
2108         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2109         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2110         __r = __h.release();
2111         __inserted = true;
2112     }
2113     return pair<iterator, bool>(iterator(__r), __inserted);
2114 }
2115
2116 template <class _Tp, class _Compare, class _Allocator>
2117 template <class _Key, class... _Args>
2118 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2119 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
2120     const_iterator __p, _Key const& __k, _Args&&... __args)
2121 {
2122     __parent_pointer __parent;
2123     __node_base_pointer __dummy;
2124     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
2125     __node_pointer __r = static_cast<__node_pointer>(__child);
2126     bool __inserted = false;
2127     if (__child == nullptr)
2128     {
2129         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2130         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2131         __r = __h.release();
2132         __inserted = true;
2133     }
2134     return pair<iterator, bool>(iterator(__r), __inserted);
2135 }
2136
2137 template <class _Tp, class _Compare, class _Allocator>
2138 template <class ..._Args>
2139 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2140 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
2141 {
2142     static_assert(!__is_tree_value_type<_Args...>::value,
2143                   "Cannot construct from __value_type");
2144     __node_allocator& __na = __node_alloc();
2145     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2146     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
2147     __h.get_deleter().__value_constructed = true;
2148     return __h;
2149 }
2150
2151
2152 template <class _Tp, class _Compare, class _Allocator>
2153 template <class... _Args>
2154 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2155 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
2156 {
2157     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2158     __parent_pointer __parent;
2159     __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
2160     __node_pointer __r = static_cast<__node_pointer>(__child);
2161     bool __inserted = false;
2162     if (__child == nullptr)
2163     {
2164         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2165         __r = __h.release();
2166         __inserted = true;
2167     }
2168     return pair<iterator, bool>(iterator(__r), __inserted);
2169 }
2170
2171 template <class _Tp, class _Compare, class _Allocator>
2172 template <class... _Args>
2173 typename __tree<_Tp, _Compare, _Allocator>::iterator
2174 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
2175 {
2176     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2177     __parent_pointer __parent;
2178     __node_base_pointer __dummy;
2179     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
2180     __node_pointer __r = static_cast<__node_pointer>(__child);
2181     if (__child == nullptr)
2182     {
2183         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2184         __r = __h.release();
2185     }
2186     return iterator(__r);
2187 }
2188
2189 template <class _Tp, class _Compare, class _Allocator>
2190 template <class... _Args>
2191 typename __tree<_Tp, _Compare, _Allocator>::iterator
2192 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
2193 {
2194     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2195     __parent_pointer __parent;
2196     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));
2197     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2198     return iterator(static_cast<__node_pointer>(__h.release()));
2199 }
2200
2201 template <class _Tp, class _Compare, class _Allocator>
2202 template <class... _Args>
2203 typename __tree<_Tp, _Compare, _Allocator>::iterator
2204 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
2205                                                         _Args&&... __args)
2206 {
2207     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2208     __parent_pointer __parent;
2209     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));
2210     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2211     return iterator(static_cast<__node_pointer>(__h.release()));
2212 }
2213
2214 template <class _Tp, class _Compare, class _Allocator>
2215 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2216 __tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd)
2217 {
2218     __parent_pointer __parent;
2219     __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__v));
2220     __node_pointer __r = static_cast<__node_pointer>(__child);
2221     bool __inserted = false;
2222     if (__child == nullptr)
2223     {
2224         __nd->__value_ = __v;
2225         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2226         __r = __nd;
2227         __inserted = true;
2228     }
2229     return pair<iterator, bool>(iterator(__r), __inserted);
2230 }
2231
2232
2233 template <class _Tp, class _Compare, class _Allocator>
2234 typename __tree<_Tp, _Compare, _Allocator>::iterator
2235 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
2236 {
2237     __parent_pointer __parent;
2238     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));
2239     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2240     return iterator(__nd);
2241 }
2242
2243 template <class _Tp, class _Compare, class _Allocator>
2244 typename __tree<_Tp, _Compare, _Allocator>::iterator
2245 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
2246                                                        __node_pointer __nd)
2247 {
2248     __parent_pointer __parent;
2249     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
2250     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2251     return iterator(__nd);
2252 }
2253
2254 template <class _Tp, class _Compare, class _Allocator>
2255 typename __tree<_Tp, _Compare, _Allocator>::iterator
2256 __tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT
2257 {
2258     iterator __r(__ptr);
2259     ++__r;
2260     if (__begin_node() == __ptr)
2261         __begin_node() = __r.__ptr_;
2262     --size();
2263     _VSTD::__tree_remove(__end_node()->__left_,
2264                          static_cast<__node_base_pointer>(__ptr));
2265     return __r;
2266 }
2267
2268 #if _LIBCPP_STD_VER >= 17
2269 template <class _Tp, class _Compare, class _Allocator>
2270 template <class _NodeHandle, class _InsertReturnType>
2271 _LIBCPP_INLINE_VISIBILITY
2272 _InsertReturnType
2273 __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
2274     _NodeHandle&& __nh)
2275 {
2276     if (__nh.empty())
2277         return _InsertReturnType{end(), false, _NodeHandle()};
2278
2279     __node_pointer __ptr = __nh.__ptr_;
2280     __parent_pointer __parent;
2281     __node_base_pointer& __child = __find_equal(__parent,
2282                                                 __ptr->__value_);
2283     if (__child != nullptr)
2284         return _InsertReturnType{
2285             iterator(static_cast<__node_pointer>(__child)),
2286             false, _VSTD::move(__nh)};
2287
2288     __insert_node_at(__parent, __child,
2289                      static_cast<__node_base_pointer>(__ptr));
2290     __nh.__release_ptr();
2291     return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
2292 }
2293
2294 template <class _Tp, class _Compare, class _Allocator>
2295 template <class _NodeHandle>
2296 _LIBCPP_INLINE_VISIBILITY
2297 typename __tree<_Tp, _Compare, _Allocator>::iterator
2298 __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
2299     const_iterator __hint, _NodeHandle&& __nh)
2300 {
2301     if (__nh.empty())
2302         return end();
2303
2304     __node_pointer __ptr = __nh.__ptr_;
2305     __parent_pointer __parent;
2306     __node_base_pointer __dummy;
2307     __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy,
2308                                                 __ptr->__value_);
2309     __node_pointer __r = static_cast<__node_pointer>(__child);
2310     if (__child == nullptr)
2311     {
2312         __insert_node_at(__parent, __child,
2313                          static_cast<__node_base_pointer>(__ptr));
2314         __r = __ptr;
2315         __nh.__release_ptr();
2316     }
2317     return iterator(__r);
2318 }
2319
2320 template <class _Tp, class _Compare, class _Allocator>
2321 template <class _NodeHandle>
2322 _LIBCPP_INLINE_VISIBILITY
2323 _NodeHandle
2324 __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key)
2325 {
2326     iterator __it = find(__key);
2327     if (__it == end())
2328         return _NodeHandle();
2329     return __node_handle_extract<_NodeHandle>(__it);
2330 }
2331
2332 template <class _Tp, class _Compare, class _Allocator>
2333 template <class _NodeHandle>
2334 _LIBCPP_INLINE_VISIBILITY
2335 _NodeHandle
2336 __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p)
2337 {
2338     __node_pointer __np = __p.__get_np();
2339     __remove_node_pointer(__np);
2340     return _NodeHandle(__np, __alloc());
2341 }
2342
2343 template <class _Tp, class _Compare, class _Allocator>
2344 template <class _Tree>
2345 _LIBCPP_INLINE_VISIBILITY
2346 void
2347 __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source)
2348 {
2349     static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
2350
2351     for (typename _Tree::iterator __i = __source.begin();
2352          __i != __source.end();)
2353     {
2354         __node_pointer __src_ptr = __i.__get_np();
2355         __parent_pointer __parent;
2356         __node_base_pointer& __child =
2357             __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_));
2358         ++__i;
2359         if (__child != nullptr)
2360             continue;
2361         __source.__remove_node_pointer(__src_ptr);
2362         __insert_node_at(__parent, __child,
2363                          static_cast<__node_base_pointer>(__src_ptr));
2364     }
2365 }
2366
2367 template <class _Tp, class _Compare, class _Allocator>
2368 template <class _NodeHandle>
2369 _LIBCPP_INLINE_VISIBILITY
2370 typename __tree<_Tp, _Compare, _Allocator>::iterator
2371 __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh)
2372 {
2373     if (__nh.empty())
2374         return end();
2375     __node_pointer __ptr = __nh.__ptr_;
2376     __parent_pointer __parent;
2377     __node_base_pointer& __child = __find_leaf_high(
2378         __parent, _NodeTypes::__get_key(__ptr->__value_));
2379     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
2380     __nh.__release_ptr();
2381     return iterator(__ptr);
2382 }
2383
2384 template <class _Tp, class _Compare, class _Allocator>
2385 template <class _NodeHandle>
2386 _LIBCPP_INLINE_VISIBILITY
2387 typename __tree<_Tp, _Compare, _Allocator>::iterator
2388 __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
2389     const_iterator __hint, _NodeHandle&& __nh)
2390 {
2391     if (__nh.empty())
2392         return end();
2393
2394     __node_pointer __ptr = __nh.__ptr_;
2395     __parent_pointer __parent;
2396     __node_base_pointer& __child = __find_leaf(__hint, __parent,
2397                                                _NodeTypes::__get_key(__ptr->__value_));
2398     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
2399     __nh.__release_ptr();
2400     return iterator(__ptr);
2401 }
2402
2403 template <class _Tp, class _Compare, class _Allocator>
2404 template <class _Tree>
2405 _LIBCPP_INLINE_VISIBILITY
2406 void
2407 __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source)
2408 {
2409     static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
2410
2411     for (typename _Tree::iterator __i = __source.begin();
2412          __i != __source.end();)
2413     {
2414         __node_pointer __src_ptr = __i.__get_np();
2415         __parent_pointer __parent;
2416         __node_base_pointer& __child = __find_leaf_high(
2417             __parent, _NodeTypes::__get_key(__src_ptr->__value_));
2418         ++__i;
2419         __source.__remove_node_pointer(__src_ptr);
2420         __insert_node_at(__parent, __child,
2421                          static_cast<__node_base_pointer>(__src_ptr));
2422     }
2423 }
2424
2425 #endif // _LIBCPP_STD_VER >= 17
2426
2427 template <class _Tp, class _Compare, class _Allocator>
2428 typename __tree<_Tp, _Compare, _Allocator>::iterator
2429 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
2430 {
2431     __node_pointer __np = __p.__get_np();
2432     iterator __r = __remove_node_pointer(__np);
2433     __node_allocator& __na = __node_alloc();
2434     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
2435         const_cast<__node_value_type&>(*__p)));
2436     __node_traits::deallocate(__na, __np, 1);
2437     return __r;
2438 }
2439
2440 template <class _Tp, class _Compare, class _Allocator>
2441 typename __tree<_Tp, _Compare, _Allocator>::iterator
2442 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
2443 {
2444     while (__f != __l)
2445         __f = erase(__f);
2446     return iterator(__l.__ptr_);
2447 }
2448
2449 template <class _Tp, class _Compare, class _Allocator>
2450 template <class _Key>
2451 typename __tree<_Tp, _Compare, _Allocator>::size_type
2452 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
2453 {
2454     iterator __i = find(__k);
2455     if (__i == end())
2456         return 0;
2457     erase(__i);
2458     return 1;
2459 }
2460
2461 template <class _Tp, class _Compare, class _Allocator>
2462 template <class _Key>
2463 typename __tree<_Tp, _Compare, _Allocator>::size_type
2464 __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
2465 {
2466     pair<iterator, iterator> __p = __equal_range_multi(__k);
2467     size_type __r = 0;
2468     for (; __p.first != __p.second; ++__r)
2469         __p.first = erase(__p.first);
2470     return __r;
2471 }
2472
2473 template <class _Tp, class _Compare, class _Allocator>
2474 template <class _Key>
2475 typename __tree<_Tp, _Compare, _Allocator>::iterator
2476 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
2477 {
2478     iterator __p = __lower_bound(__v, __root(), __end_node());
2479     if (__p != end() && !value_comp()(__v, *__p))
2480         return __p;
2481     return end();
2482 }
2483
2484 template <class _Tp, class _Compare, class _Allocator>
2485 template <class _Key>
2486 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2487 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
2488 {
2489     const_iterator __p = __lower_bound(__v, __root(), __end_node());
2490     if (__p != end() && !value_comp()(__v, *__p))
2491         return __p;
2492     return end();
2493 }
2494
2495 template <class _Tp, class _Compare, class _Allocator>
2496 template <class _Key>
2497 typename __tree<_Tp, _Compare, _Allocator>::size_type
2498 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
2499 {
2500     __node_pointer __rt = __root();
2501     while (__rt != nullptr)
2502     {
2503         if (value_comp()(__k, __rt->__value_))
2504         {
2505             __rt = static_cast<__node_pointer>(__rt->__left_);
2506         }
2507         else if (value_comp()(__rt->__value_, __k))
2508             __rt = static_cast<__node_pointer>(__rt->__right_);
2509         else
2510             return 1;
2511     }
2512     return 0;
2513 }
2514
2515 template <class _Tp, class _Compare, class _Allocator>
2516 template <class _Key>
2517 typename __tree<_Tp, _Compare, _Allocator>::size_type
2518 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
2519 {
2520     __iter_pointer __result = __end_node();
2521     __node_pointer __rt = __root();
2522     while (__rt != nullptr)
2523     {
2524         if (value_comp()(__k, __rt->__value_))
2525         {
2526             __result = static_cast<__iter_pointer>(__rt);
2527             __rt = static_cast<__node_pointer>(__rt->__left_);
2528         }
2529         else if (value_comp()(__rt->__value_, __k))
2530             __rt = static_cast<__node_pointer>(__rt->__right_);
2531         else
2532             return _VSTD::distance(
2533                 __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2534                 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)
2535             );
2536     }
2537     return 0;
2538 }
2539
2540 template <class _Tp, class _Compare, class _Allocator>
2541 template <class _Key>
2542 typename __tree<_Tp, _Compare, _Allocator>::iterator
2543 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2544                                                  __node_pointer __root,
2545                                                  __iter_pointer __result)
2546 {
2547     while (__root != nullptr)
2548     {
2549         if (!value_comp()(__root->__value_, __v))
2550         {
2551             __result = static_cast<__iter_pointer>(__root);
2552             __root = static_cast<__node_pointer>(__root->__left_);
2553         }
2554         else
2555             __root = static_cast<__node_pointer>(__root->__right_);
2556     }
2557     return iterator(__result);
2558 }
2559
2560 template <class _Tp, class _Compare, class _Allocator>
2561 template <class _Key>
2562 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2563 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2564                                                  __node_pointer __root,
2565                                                  __iter_pointer __result) const
2566 {
2567     while (__root != nullptr)
2568     {
2569         if (!value_comp()(__root->__value_, __v))
2570         {
2571             __result = static_cast<__iter_pointer>(__root);
2572             __root = static_cast<__node_pointer>(__root->__left_);
2573         }
2574         else
2575             __root = static_cast<__node_pointer>(__root->__right_);
2576     }
2577     return const_iterator(__result);
2578 }
2579
2580 template <class _Tp, class _Compare, class _Allocator>
2581 template <class _Key>
2582 typename __tree<_Tp, _Compare, _Allocator>::iterator
2583 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2584                                                  __node_pointer __root,
2585                                                  __iter_pointer __result)
2586 {
2587     while (__root != nullptr)
2588     {
2589         if (value_comp()(__v, __root->__value_))
2590         {
2591             __result = static_cast<__iter_pointer>(__root);
2592             __root = static_cast<__node_pointer>(__root->__left_);
2593         }
2594         else
2595             __root = static_cast<__node_pointer>(__root->__right_);
2596     }
2597     return iterator(__result);
2598 }
2599
2600 template <class _Tp, class _Compare, class _Allocator>
2601 template <class _Key>
2602 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2603 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2604                                                  __node_pointer __root,
2605                                                  __iter_pointer __result) const
2606 {
2607     while (__root != nullptr)
2608     {
2609         if (value_comp()(__v, __root->__value_))
2610         {
2611             __result = static_cast<__iter_pointer>(__root);
2612             __root = static_cast<__node_pointer>(__root->__left_);
2613         }
2614         else
2615             __root = static_cast<__node_pointer>(__root->__right_);
2616     }
2617     return const_iterator(__result);
2618 }
2619
2620 template <class _Tp, class _Compare, class _Allocator>
2621 template <class _Key>
2622 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2623      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2624 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
2625 {
2626     typedef pair<iterator, iterator> _Pp;
2627     __iter_pointer __result = __end_node();
2628     __node_pointer __rt = __root();
2629     while (__rt != nullptr)
2630     {
2631         if (value_comp()(__k, __rt->__value_))
2632         {
2633             __result = static_cast<__iter_pointer>(__rt);
2634             __rt = static_cast<__node_pointer>(__rt->__left_);
2635         }
2636         else if (value_comp()(__rt->__value_, __k))
2637             __rt = static_cast<__node_pointer>(__rt->__right_);
2638         else
2639             return _Pp(iterator(__rt),
2640                       iterator(
2641                           __rt->__right_ != nullptr ?
2642                               static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_))
2643                             : __result));
2644     }
2645     return _Pp(iterator(__result), iterator(__result));
2646 }
2647
2648 template <class _Tp, class _Compare, class _Allocator>
2649 template <class _Key>
2650 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2651      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2652 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
2653 {
2654     typedef pair<const_iterator, const_iterator> _Pp;
2655     __iter_pointer __result = __end_node();
2656     __node_pointer __rt = __root();
2657     while (__rt != nullptr)
2658     {
2659         if (value_comp()(__k, __rt->__value_))
2660         {
2661             __result = static_cast<__iter_pointer>(__rt);
2662             __rt = static_cast<__node_pointer>(__rt->__left_);
2663         }
2664         else if (value_comp()(__rt->__value_, __k))
2665             __rt = static_cast<__node_pointer>(__rt->__right_);
2666         else
2667             return _Pp(const_iterator(__rt),
2668                       const_iterator(
2669                           __rt->__right_ != nullptr ?
2670                               static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_))
2671                             : __result));
2672     }
2673     return _Pp(const_iterator(__result), const_iterator(__result));
2674 }
2675
2676 template <class _Tp, class _Compare, class _Allocator>
2677 template <class _Key>
2678 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2679      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2680 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
2681 {
2682     typedef pair<iterator, iterator> _Pp;
2683     __iter_pointer __result = __end_node();
2684     __node_pointer __rt = __root();
2685     while (__rt != nullptr)
2686     {
2687         if (value_comp()(__k, __rt->__value_))
2688         {
2689             __result = static_cast<__iter_pointer>(__rt);
2690             __rt = static_cast<__node_pointer>(__rt->__left_);
2691         }
2692         else if (value_comp()(__rt->__value_, __k))
2693             __rt = static_cast<__node_pointer>(__rt->__right_);
2694         else
2695             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2696                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2697     }
2698     return _Pp(iterator(__result), iterator(__result));
2699 }
2700
2701 template <class _Tp, class _Compare, class _Allocator>
2702 template <class _Key>
2703 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2704      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2705 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
2706 {
2707     typedef pair<const_iterator, const_iterator> _Pp;
2708     __iter_pointer __result = __end_node();
2709     __node_pointer __rt = __root();
2710     while (__rt != nullptr)
2711     {
2712         if (value_comp()(__k, __rt->__value_))
2713         {
2714             __result = static_cast<__iter_pointer>(__rt);
2715             __rt = static_cast<__node_pointer>(__rt->__left_);
2716         }
2717         else if (value_comp()(__rt->__value_, __k))
2718             __rt = static_cast<__node_pointer>(__rt->__right_);
2719         else
2720             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2721                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2722     }
2723     return _Pp(const_iterator(__result), const_iterator(__result));
2724 }
2725
2726 template <class _Tp, class _Compare, class _Allocator>
2727 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2728 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2729 {
2730     __node_pointer __np = __p.__get_np();
2731     if (__begin_node() == __p.__ptr_)
2732     {
2733         if (__np->__right_ != nullptr)
2734             __begin_node() = static_cast<__iter_pointer>(__np->__right_);
2735         else
2736             __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
2737     }
2738     --size();
2739     _VSTD::__tree_remove(__end_node()->__left_,
2740                          static_cast<__node_base_pointer>(__np));
2741     return __node_holder(__np, _Dp(__node_alloc(), true));
2742 }
2743
2744 template <class _Tp, class _Compare, class _Allocator>
2745 inline _LIBCPP_INLINE_VISIBILITY
2746 void
2747 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2748      __tree<_Tp, _Compare, _Allocator>& __y)
2749     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2750 {
2751     __x.swap(__y);
2752 }
2753
2754 _LIBCPP_END_NAMESPACE_STD
2755
2756 _LIBCPP_POP_MACROS
2757
2758 #endif // _LIBCPP___TREE