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