contrib/libc++/include/__tree

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