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