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 __rebind_pointer<_VoidPtr, __tree_node_base<_VoidPtr> >::type
 552              >
 553 {
 554     __tree_node_base(const __tree_node_base&);
 555     __tree_node_base& operator=(const __tree_node_base&);
 556 public:
 557     typedef typename __rebind_pointer<_VoidPtr, __tree_node_base>::type pointer;
 558     typedef typename __rebind_pointer<_VoidPtr, const __tree_node_base>::type const_pointer;
 559
 560     typedef __tree_end_node<pointer> base;
 561
 562     pointer __right_;
 563     pointer __parent_;
 564     bool __is_black_;
 565
 566     _LIBCPP_INLINE_VISIBILITY
 567     __tree_node_base() _NOEXCEPT
 568         : __right_(), __parent_(), __is_black_(false) {}
 569 };
 570
 571 template <class _Tp, class _VoidPtr>
 572 class __tree_node
 573     : public __tree_node_base<_VoidPtr>
 574 {
 575 public:
 576     typedef __tree_node_base<_VoidPtr> base;
 577     typedef _Tp value_type;
 578
 579     value_type __value_;
 580
 581 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 582     template <class ..._Args>
 583         _LIBCPP_INLINE_VISIBILITY
 584         explicit __tree_node(_Args&& ...__args)
 585             : __value_(_VSTD::forward<_Args>(__args)...) {}
 586 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 587     _LIBCPP_INLINE_VISIBILITY
 588     explicit __tree_node(const value_type& __v)
 589             : __value_(__v) {}
 590 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 591 };
 592
 593 template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator;
 594 template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
 595
 596 template <class _Tp, class _NodePtr, class _DiffType>
 597 class _LIBCPP_TYPE_VIS_ONLY __tree_iterator
 598 {
 599     typedef _NodePtr                                              __node_pointer;
 600     typedef typename pointer_traits<__node_pointer>::element_type __node;
 601
 602     __node_pointer __ptr_;
 603
 604     typedef pointer_traits<__node_pointer> __pointer_traits;
 605 public:
 606     typedef bidirectional_iterator_tag iterator_category;
 607     typedef _Tp                        value_type;
 608     typedef _DiffType                  difference_type;
 609     typedef value_type&                reference;
 610     typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
 611
 612     _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT
 613 #if _LIBCPP_STD_VER > 11
 614     : __ptr_(nullptr)
 615 #endif
 616     {}
 617
 618     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
 619     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
 620         {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
 621
 622     _LIBCPP_INLINE_VISIBILITY
 623     __tree_iterator& operator++() {
 624       __ptr_ = static_cast<__node_pointer>(
 625           __tree_next(static_cast<typename __node::base::pointer>(__ptr_)));
 626       return *this;
 627     }
 628     _LIBCPP_INLINE_VISIBILITY
 629     __tree_iterator operator++(int)
 630         {__tree_iterator __t(*this); ++(*this); return __t;}
 631
 632     _LIBCPP_INLINE_VISIBILITY
 633     __tree_iterator& operator--() {
 634       __ptr_ = static_cast<__node_pointer>(
 635           __tree_prev(static_cast<typename __node::base::pointer>(__ptr_)));
 636       return *this;
 637     }
 638     _LIBCPP_INLINE_VISIBILITY
 639     __tree_iterator operator--(int)
 640         {__tree_iterator __t(*this); --(*this); return __t;}
 641
 642     friend _LIBCPP_INLINE_VISIBILITY
 643         bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
 644         {return __x.__ptr_ == __y.__ptr_;}
 645     friend _LIBCPP_INLINE_VISIBILITY
 646         bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
 647         {return !(__x == __y);}
 648
 649 private:
 650     _LIBCPP_INLINE_VISIBILITY
 651     explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 652     template <class, class, class> friend class __tree;
 653     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
 654     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator;
 655     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
 656     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
 657     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;
 658     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;
 659 };
 660
 661 template <class _Tp, class _ConstNodePtr, class _DiffType>
 662 class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator
 663 {
 664     typedef _ConstNodePtr                                         __node_pointer;
 665     typedef typename pointer_traits<__node_pointer>::element_type __node;
 666
 667     __node_pointer __ptr_;
 668
 669     typedef pointer_traits<__node_pointer> __pointer_traits;
 670 public:
 671     typedef bidirectional_iterator_tag       iterator_category;
 672     typedef _Tp                              value_type;
 673     typedef _DiffType                        difference_type;
 674     typedef const value_type&                reference;
 675     typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer;
 676
 677     _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT
 678 #if _LIBCPP_STD_VER > 11
 679     : __ptr_(nullptr)
 680 #endif
 681     {}
 682
 683 private:
 684     typedef typename remove_const<__node>::type  __non_const_node;
 685     typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
 686         __non_const_node_pointer;
 687     typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type>
 688                                                  __non_const_iterator;
 689 public:
 690     _LIBCPP_INLINE_VISIBILITY
 691     __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
 692         : __ptr_(__p.__ptr_) {}
 693
 694     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
 695     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
 696         {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
 697
 698     _LIBCPP_INLINE_VISIBILITY
 699     __tree_const_iterator& operator++() {
 700       typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type
 701         __node_base_pointer;
 702       __ptr_ = static_cast<__node_pointer>(
 703           __tree_next(static_cast<__node_base_pointer>(__ptr_)));
 704       return *this;
 705     }
 706
 707     _LIBCPP_INLINE_VISIBILITY
 708     __tree_const_iterator operator++(int)
 709         {__tree_const_iterator __t(*this); ++(*this); return __t;}
 710
 711     _LIBCPP_INLINE_VISIBILITY
 712     __tree_const_iterator& operator--() {
 713       typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type
 714         __node_base_pointer;
 715       __ptr_ = static_cast<__node_pointer>(
 716           __tree_prev(static_cast<__node_base_pointer>(__ptr_)));
 717       return *this;
 718     }
 719
 720     _LIBCPP_INLINE_VISIBILITY
 721     __tree_const_iterator operator--(int)
 722         {__tree_const_iterator __t(*this); --(*this); return __t;}
 723
 724     friend _LIBCPP_INLINE_VISIBILITY
 725         bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
 726         {return __x.__ptr_ == __y.__ptr_;}
 727     friend _LIBCPP_INLINE_VISIBILITY
 728         bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
 729         {return !(__x == __y);}
 730
 731 private:
 732     _LIBCPP_INLINE_VISIBILITY
 733     explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
 734         : __ptr_(__p) {}
 735     template <class, class, class> friend class __tree;
 736     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
 737     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
 738     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;
 739     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;
 740     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
 741 };
 742
 743 template <class _Tp, class _Compare, class _Allocator>
 744 class __tree
 745 {
 746 public:
 747     typedef _Tp                                      value_type;
 748     typedef _Compare                                 value_compare;
 749     typedef _Allocator                               allocator_type;
 750     typedef allocator_traits<allocator_type>         __alloc_traits;
 751     typedef typename __alloc_traits::pointer         pointer;
 752     typedef typename __alloc_traits::const_pointer   const_pointer;
 753     typedef typename __alloc_traits::size_type       size_type;
 754     typedef typename __alloc_traits::difference_type difference_type;
 755
 756     typedef typename __alloc_traits::void_pointer  __void_pointer;
 757
 758     typedef __tree_node<value_type, __void_pointer> __node;
 759     typedef __tree_node_base<__void_pointer>        __node_base;
 760     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
 761     typedef allocator_traits<__node_allocator>       __node_traits;
 762     typedef typename __node_traits::pointer          __node_pointer;
 763     typedef typename __node_traits::pointer          __node_const_pointer;
 764     typedef typename __node_base::pointer            __node_base_pointer;
 765     typedef typename __node_base::pointer            __node_base_const_pointer;
 766 private:
 767     typedef typename __node_base::base __end_node_t;
 768     typedef typename __rebind_pointer<__node_pointer, __end_node_t>::type
 769         __end_node_ptr;
 770     typedef __end_node_ptr __end_node_const_ptr;
 771
 772     __node_pointer                                          __begin_node_;
 773     __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
 774     __compressed_pair<size_type, value_compare>        __pair3_;
 775
 776 public:
 777     _LIBCPP_INLINE_VISIBILITY
 778     __node_pointer __end_node() _NOEXCEPT
 779     {
 780         return static_cast<__node_pointer>
 781                (
 782                    pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
 783                );
 784     }
 785     _LIBCPP_INLINE_VISIBILITY
 786     __node_const_pointer __end_node() const _NOEXCEPT
 787     {
 788         return static_cast<__node_const_pointer>
 789                (
 790                    pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first()))
 791                );
 792     }
 793     _LIBCPP_INLINE_VISIBILITY
 794           __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}
 795 private:
 796     _LIBCPP_INLINE_VISIBILITY
 797     const __node_allocator& __node_alloc() const _NOEXCEPT
 798         {return __pair1_.second();}
 799     _LIBCPP_INLINE_VISIBILITY
 800           __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
 801     _LIBCPP_INLINE_VISIBILITY
 802     const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
 803 public:
 804     _LIBCPP_INLINE_VISIBILITY
 805     allocator_type __alloc() const _NOEXCEPT
 806         {return allocator_type(__node_alloc());}
 807 private:
 808     _LIBCPP_INLINE_VISIBILITY
 809           size_type& size() _NOEXCEPT {return __pair3_.first();}
 810 public:
 811     _LIBCPP_INLINE_VISIBILITY
 812     const size_type& size() const _NOEXCEPT {return __pair3_.first();}
 813     _LIBCPP_INLINE_VISIBILITY
 814           value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}
 815     _LIBCPP_INLINE_VISIBILITY
 816     const value_compare& value_comp() const _NOEXCEPT
 817         {return __pair3_.second();}
 818 public:
 819     _LIBCPP_INLINE_VISIBILITY
 820     __node_pointer __root() _NOEXCEPT
 821         {return static_cast<__node_pointer>      (__end_node()->__left_);}
 822     _LIBCPP_INLINE_VISIBILITY
 823     __node_const_pointer __root() const _NOEXCEPT
 824         {return static_cast<__node_const_pointer>(__end_node()->__left_);}
 825
 826     typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
 827     typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
 828
 829     explicit __tree(const value_compare& __comp)
 830         _NOEXCEPT_(
 831             is_nothrow_default_constructible<__node_allocator>::value &&
 832             is_nothrow_copy_constructible<value_compare>::value);
 833     explicit __tree(const allocator_type& __a);
 834     __tree(const value_compare& __comp, const allocator_type& __a);
 835     __tree(const __tree& __t);
 836     __tree& operator=(const __tree& __t);
 837     template <class _InputIterator>
 838         void __assign_unique(_InputIterator __first, _InputIterator __last);
 839     template <class _InputIterator>
 840         void __assign_multi(_InputIterator __first, _InputIterator __last);
 841 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 842     __tree(__tree&& __t)
 843         _NOEXCEPT_(
 844             is_nothrow_move_constructible<__node_allocator>::value &&
 845             is_nothrow_move_constructible<value_compare>::value);
 846     __tree(__tree&& __t, const allocator_type& __a);
 847     __tree& operator=(__tree&& __t)
 848         _NOEXCEPT_(
 849             __node_traits::propagate_on_container_move_assignment::value &&
 850             is_nothrow_move_assignable<value_compare>::value &&
 851             is_nothrow_move_assignable<__node_allocator>::value);
 852 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 853
 854     ~__tree();
 855
 856     _LIBCPP_INLINE_VISIBILITY
 857           iterator begin()  _NOEXCEPT {return       iterator(__begin_node());}
 858     _LIBCPP_INLINE_VISIBILITY
 859     const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());}
 860     _LIBCPP_INLINE_VISIBILITY
 861           iterator end() _NOEXCEPT {return       iterator(__end_node());}
 862     _LIBCPP_INLINE_VISIBILITY
 863     const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());}
 864
 865     _LIBCPP_INLINE_VISIBILITY
 866     size_type max_size() const _NOEXCEPT
 867         {return __node_traits::max_size(__node_alloc());}
 868
 869     void clear() _NOEXCEPT;
 870
 871     void swap(__tree& __t)
 872         _NOEXCEPT_(
 873             __is_nothrow_swappable<value_compare>::value
 874 #if _LIBCPP_STD_VER <= 11
 875             && (!__node_traits::propagate_on_container_swap::value ||
 876                  __is_nothrow_swappable<__node_allocator>::value)
 877 #endif
 878             );
 879
 880 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 881 #ifndef _LIBCPP_HAS_NO_VARIADICS
 882     template <class... _Args>
 883         pair<iterator, bool>
 884         __emplace_unique(_Args&&... __args);
 885     template <class... _Args>
 886         iterator
 887         __emplace_multi(_Args&&... __args);
 888
 889     template <class... _Args>
 890         iterator
 891         __emplace_hint_unique(const_iterator __p, _Args&&... __args);
 892     template <class... _Args>
 893         iterator
 894         __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 895 #endif  // _LIBCPP_HAS_NO_VARIADICS
 896
 897     template <class _Vp>
 898         pair<iterator, bool> __insert_unique(_Vp&& __v);
 899     template <class _Vp>
 900         iterator __insert_unique(const_iterator __p, _Vp&& __v);
 901     template <class _Vp>
 902         iterator __insert_multi(_Vp&& __v);
 903     template <class _Vp>
 904         iterator __insert_multi(const_iterator __p, _Vp&& __v);
 905 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 906
 907     pair<iterator, bool> __insert_unique(const value_type& __v);
 908     iterator __insert_unique(const_iterator __p, const value_type& __v);
 909     iterator __insert_multi(const value_type& __v);
 910     iterator __insert_multi(const_iterator __p, const value_type& __v);
 911
 912 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 913     pair<iterator, bool> __insert_unique(        value_type&& __v);
 914     iterator __insert_unique(const_iterator __p, value_type&& __v);
 915     iterator __insert_multi(                    value_type&& __v);
 916     iterator __insert_multi(const_iterator __p, value_type&& __v);
 917 #endif
 918
 919     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
 920     iterator             __node_insert_unique(const_iterator __p,
 921                                               __node_pointer __nd);
 922
 923     iterator __node_insert_multi(__node_pointer __nd);
 924     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 925
 926     iterator erase(const_iterator __p);
 927     iterator erase(const_iterator __f, const_iterator __l);
 928     template <class _Key>
 929         size_type __erase_unique(const _Key& __k);
 930     template <class _Key>
 931         size_type __erase_multi(const _Key& __k);
 932
 933     void __insert_node_at(__node_base_pointer __parent,
 934                           __node_base_pointer& __child,
 935                           __node_base_pointer __new_node);
 936
 937     template <class _Key>
 938         iterator find(const _Key& __v);
 939     template <class _Key>
 940         const_iterator find(const _Key& __v) const;
 941
 942     template <class _Key>
 943         size_type __count_unique(const _Key& __k) const;
 944     template <class _Key>
 945         size_type __count_multi(const _Key& __k) const;
 946
 947     template <class _Key>
 948         _LIBCPP_INLINE_VISIBILITY
 949         iterator lower_bound(const _Key& __v)
 950             {return __lower_bound(__v, __root(), __end_node());}
 951     template <class _Key>
 952         iterator __lower_bound(const _Key& __v,
 953                                __node_pointer __root,
 954                                __node_pointer __result);
 955     template <class _Key>
 956         _LIBCPP_INLINE_VISIBILITY
 957         const_iterator lower_bound(const _Key& __v) const
 958             {return __lower_bound(__v, __root(), __end_node());}
 959     template <class _Key>
 960         const_iterator __lower_bound(const _Key& __v,
 961                                      __node_const_pointer __root,
 962                                      __node_const_pointer __result) const;
 963     template <class _Key>
 964         _LIBCPP_INLINE_VISIBILITY
 965         iterator upper_bound(const _Key& __v)
 966             {return __upper_bound(__v, __root(), __end_node());}
 967     template <class _Key>
 968         iterator __upper_bound(const _Key& __v,
 969                                __node_pointer __root,
 970                                __node_pointer __result);
 971     template <class _Key>
 972         _LIBCPP_INLINE_VISIBILITY
 973         const_iterator upper_bound(const _Key& __v) const
 974             {return __upper_bound(__v, __root(), __end_node());}
 975     template <class _Key>
 976         const_iterator __upper_bound(const _Key& __v,
 977                                      __node_const_pointer __root,
 978                                      __node_const_pointer __result) const;
 979     template <class _Key>
 980         pair<iterator, iterator>
 981         __equal_range_unique(const _Key& __k);
 982     template <class _Key>
 983         pair<const_iterator, const_iterator>
 984         __equal_range_unique(const _Key& __k) const;
 985
 986     template <class _Key>
 987         pair<iterator, iterator>
 988         __equal_range_multi(const _Key& __k);
 989     template <class _Key>
 990         pair<const_iterator, const_iterator>
 991         __equal_range_multi(const _Key& __k) const;
 992
 993     typedef __tree_node_destructor<__node_allocator> _Dp;
 994     typedef unique_ptr<__node, _Dp> __node_holder;
 995
 996     __node_holder remove(const_iterator __p) _NOEXCEPT;
 997 private:
 998     typename __node_base::pointer&
 999         __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v);
1000     typename __node_base::pointer&
1001         __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v);
1002     typename __node_base::pointer&
1003         __find_leaf(const_iterator __hint,
1004                     typename __node_base::pointer& __parent, const value_type& __v);
1005     template <class _Key>
1006         typename __node_base::pointer&
1007         __find_equal(typename __node_base::pointer& __parent, const _Key& __v);
1008     template <class _Key>
1009         typename __node_base::pointer&
1010         __find_equal(const_iterator __hint, typename __node_base::pointer& __parent,
1011                      const _Key& __v);
1012
1013 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1014     template <class ..._Args>
1015         __node_holder __construct_node(_Args&& ...__args);
1016 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1017         __node_holder __construct_node(const value_type& __v);
1018 #endif
1019
1020     void destroy(__node_pointer __nd) _NOEXCEPT;
1021
1022     _LIBCPP_INLINE_VISIBILITY
1023     void __copy_assign_alloc(const __tree& __t)
1024         {__copy_assign_alloc(__t, integral_constant<bool,
1025              __node_traits::propagate_on_container_copy_assignment::value>());}
1026
1027     _LIBCPP_INLINE_VISIBILITY
1028     void __copy_assign_alloc(const __tree& __t, true_type)
1029         {__node_alloc() = __t.__node_alloc();}
1030     _LIBCPP_INLINE_VISIBILITY
1031     void __copy_assign_alloc(const __tree& __t, false_type) {}
1032
1033     void __move_assign(__tree& __t, false_type);
1034     void __move_assign(__tree& __t, true_type)
1035         _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1036                    is_nothrow_move_assignable<__node_allocator>::value);
1037
1038     _LIBCPP_INLINE_VISIBILITY
1039     void __move_assign_alloc(__tree& __t)
1040         _NOEXCEPT_(
1041             !__node_traits::propagate_on_container_move_assignment::value ||
1042             is_nothrow_move_assignable<__node_allocator>::value)
1043         {__move_assign_alloc(__t, integral_constant<bool,
1044              __node_traits::propagate_on_container_move_assignment::value>());}
1045
1046     _LIBCPP_INLINE_VISIBILITY
1047     void __move_assign_alloc(__tree& __t, true_type)
1048         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1049         {__node_alloc() = _VSTD::move(__t.__node_alloc());}
1050     _LIBCPP_INLINE_VISIBILITY
1051     void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {}
1052
1053     __node_pointer __detach();
1054     static __node_pointer __detach(__node_pointer);
1055
1056     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
1057     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
1058 };
1059
1060 template <class _Tp, class _Compare, class _Allocator>
1061 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
1062         _NOEXCEPT_(
1063             is_nothrow_default_constructible<__node_allocator>::value &&
1064             is_nothrow_copy_constructible<value_compare>::value)
1065     : __pair3_(0, __comp)
1066 {
1067     __begin_node() = __end_node();
1068 }
1069
1070 template <class _Tp, class _Compare, class _Allocator>
1071 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1072     : __begin_node_(__node_pointer()),
1073       __pair1_(__node_allocator(__a)),
1074       __pair3_(0)
1075 {
1076     __begin_node() = __end_node();
1077 }
1078
1079 template <class _Tp, class _Compare, class _Allocator>
1080 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
1081                                            const allocator_type& __a)
1082     : __begin_node_(__node_pointer()),
1083       __pair1_(__node_allocator(__a)),
1084       __pair3_(0, __comp)
1085 {
1086     __begin_node() = __end_node();
1087 }
1088
1089 // Precondition:  size() != 0
1090 template <class _Tp, class _Compare, class _Allocator>
1091 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1092 __tree<_Tp, _Compare, _Allocator>::__detach()
1093 {
1094     __node_pointer __cache = __begin_node();
1095     __begin_node() = __end_node();
1096     __end_node()->__left_->__parent_ = nullptr;
1097     __end_node()->__left_ = nullptr;
1098     size() = 0;
1099     // __cache->__left_ == nullptr
1100     if (__cache->__right_ != nullptr)
1101         __cache = static_cast<__node_pointer>(__cache->__right_);
1102     // __cache->__left_ == nullptr
1103     // __cache->__right_ == nullptr
1104     return __cache;
1105 }
1106
1107 // Precondition:  __cache != nullptr
1108 //    __cache->left_ == nullptr
1109 //    __cache->right_ == nullptr
1110 //    This is no longer a red-black tree
1111 template <class _Tp, class _Compare, class _Allocator>
1112 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1113 __tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache)
1114 {
1115     if (__cache->__parent_ == nullptr)
1116         return nullptr;
1117     if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1118     {
1119         __cache->__parent_->__left_ = nullptr;
1120         __cache = static_cast<__node_pointer>(__cache->__parent_);
1121         if (__cache->__right_ == nullptr)
1122             return __cache;
1123         return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
1124     }
1125     // __cache is right child
1126     __cache->__parent_->__right_ = nullptr;
1127     __cache = static_cast<__node_pointer>(__cache->__parent_);
1128     if (__cache->__left_ == nullptr)
1129         return __cache;
1130     return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
1131 }
1132
1133 template <class _Tp, class _Compare, class _Allocator>
1134 __tree<_Tp, _Compare, _Allocator>&
1135 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
1136 {
1137     if (this != &__t)
1138     {
1139         value_comp() = __t.value_comp();
1140         __copy_assign_alloc(__t);
1141         __assign_multi(__t.begin(), __t.end());
1142     }
1143     return *this;
1144 }
1145
1146 template <class _Tp, class _Compare, class _Allocator>
1147 template <class _InputIterator>
1148 void
1149 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last)
1150 {
1151     if (size() != 0)
1152     {
1153         __node_pointer __cache = __detach();
1154 #ifndef _LIBCPP_NO_EXCEPTIONS
1155         try
1156         {
1157 #endif  // _LIBCPP_NO_EXCEPTIONS
1158             for (; __cache != nullptr && __first != __last; ++__first)
1159             {
1160                 __cache->__value_ = *__first;
1161                 __node_pointer __next = __detach(__cache);
1162                 __node_insert_unique(__cache);
1163                 __cache = __next;
1164             }
1165 #ifndef _LIBCPP_NO_EXCEPTIONS
1166         }
1167         catch (...)
1168         {
1169             while (__cache->__parent_ != nullptr)
1170                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1171             destroy(__cache);
1172             throw;
1173         }
1174 #endif  // _LIBCPP_NO_EXCEPTIONS
1175         if (__cache != nullptr)
1176         {
1177             while (__cache->__parent_ != nullptr)
1178                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1179             destroy(__cache);
1180         }
1181     }
1182     for (; __first != __last; ++__first)
1183         __insert_unique(*__first);
1184 }
1185
1186 template <class _Tp, class _Compare, class _Allocator>
1187 template <class _InputIterator>
1188 void
1189 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
1190 {
1191     if (size() != 0)
1192     {
1193         __node_pointer __cache = __detach();
1194 #ifndef _LIBCPP_NO_EXCEPTIONS
1195         try
1196         {
1197 #endif  // _LIBCPP_NO_EXCEPTIONS
1198             for (; __cache != nullptr && __first != __last; ++__first)
1199             {
1200                 __cache->__value_ = *__first;
1201                 __node_pointer __next = __detach(__cache);
1202                 __node_insert_multi(__cache);
1203                 __cache = __next;
1204             }
1205 #ifndef _LIBCPP_NO_EXCEPTIONS
1206         }
1207         catch (...)
1208         {
1209             while (__cache->__parent_ != nullptr)
1210                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1211             destroy(__cache);
1212             throw;
1213         }
1214 #endif  // _LIBCPP_NO_EXCEPTIONS
1215         if (__cache != nullptr)
1216         {
1217             while (__cache->__parent_ != nullptr)
1218                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1219             destroy(__cache);
1220         }
1221     }
1222     for (; __first != __last; ++__first)
1223         __insert_multi(*__first);
1224 }
1225
1226 template <class _Tp, class _Compare, class _Allocator>
1227 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1228     : __begin_node_(__node_pointer()),
1229       __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1230       __pair3_(0, __t.value_comp())
1231 {
1232     __begin_node() = __end_node();
1233 }
1234
1235 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1236
1237 template <class _Tp, class _Compare, class _Allocator>
1238 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
1239     _NOEXCEPT_(
1240         is_nothrow_move_constructible<__node_allocator>::value &&
1241         is_nothrow_move_constructible<value_compare>::value)
1242     : __begin_node_(_VSTD::move(__t.__begin_node_)),
1243       __pair1_(_VSTD::move(__t.__pair1_)),
1244       __pair3_(_VSTD::move(__t.__pair3_))
1245 {
1246     if (size() == 0)
1247         __begin_node() = __end_node();
1248     else
1249     {
1250         __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1251         __t.__begin_node() = __t.__end_node();
1252         __t.__end_node()->__left_ = nullptr;
1253         __t.size() = 0;
1254     }
1255 }
1256
1257 template <class _Tp, class _Compare, class _Allocator>
1258 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1259     : __pair1_(__node_allocator(__a)),
1260       __pair3_(0, _VSTD::move(__t.value_comp()))
1261 {
1262     if (__a == __t.__alloc())
1263     {
1264         if (__t.size() == 0)
1265             __begin_node() = __end_node();
1266         else
1267         {
1268             __begin_node() = __t.__begin_node();
1269             __end_node()->__left_ = __t.__end_node()->__left_;
1270             __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1271             size() = __t.size();
1272             __t.__begin_node() = __t.__end_node();
1273             __t.__end_node()->__left_ = nullptr;
1274             __t.size() = 0;
1275         }
1276     }
1277     else
1278     {
1279         __begin_node() = __end_node();
1280     }
1281 }
1282
1283 template <class _Tp, class _Compare, class _Allocator>
1284 void
1285 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1286     _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1287                is_nothrow_move_assignable<__node_allocator>::value)
1288 {
1289     destroy(static_cast<__node_pointer>(__end_node()->__left_));
1290     __begin_node_ = __t.__begin_node_;
1291     __pair1_.first() = __t.__pair1_.first();
1292     __move_assign_alloc(__t);
1293     __pair3_ = _VSTD::move(__t.__pair3_);
1294     if (size() == 0)
1295         __begin_node() = __end_node();
1296     else
1297     {
1298         __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1299         __t.__begin_node() = __t.__end_node();
1300         __t.__end_node()->__left_ = nullptr;
1301         __t.size() = 0;
1302     }
1303 }
1304
1305 template <class _Tp, class _Compare, class _Allocator>
1306 void
1307 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
1308 {
1309     if (__node_alloc() == __t.__node_alloc())
1310         __move_assign(__t, true_type());
1311     else
1312     {
1313         value_comp() = _VSTD::move(__t.value_comp());
1314         const_iterator __e = end();
1315         if (size() != 0)
1316         {
1317             __node_pointer __cache = __detach();
1318 #ifndef _LIBCPP_NO_EXCEPTIONS
1319             try
1320             {
1321 #endif  // _LIBCPP_NO_EXCEPTIONS
1322                 while (__cache != nullptr && __t.size() != 0)
1323                 {
1324                     __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
1325                     __node_pointer __next = __detach(__cache);
1326                     __node_insert_multi(__cache);
1327                     __cache = __next;
1328                 }
1329 #ifndef _LIBCPP_NO_EXCEPTIONS
1330             }
1331             catch (...)
1332             {
1333                 while (__cache->__parent_ != nullptr)
1334                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1335                 destroy(__cache);
1336                 throw;
1337             }
1338 #endif  // _LIBCPP_NO_EXCEPTIONS
1339             if (__cache != nullptr)
1340             {
1341                 while (__cache->__parent_ != nullptr)
1342                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1343                 destroy(__cache);
1344             }
1345         }
1346         while (__t.size() != 0)
1347             __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_));
1348     }
1349 }
1350
1351 template <class _Tp, class _Compare, class _Allocator>
1352 __tree<_Tp, _Compare, _Allocator>&
1353 __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1354     _NOEXCEPT_(
1355         __node_traits::propagate_on_container_move_assignment::value &&
1356         is_nothrow_move_assignable<value_compare>::value &&
1357         is_nothrow_move_assignable<__node_allocator>::value)
1358
1359 {
1360     __move_assign(__t, integral_constant<bool,
1361                   __node_traits::propagate_on_container_move_assignment::value>());
1362     return *this;
1363 }
1364
1365 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1366
1367 template <class _Tp, class _Compare, class _Allocator>
1368 __tree<_Tp, _Compare, _Allocator>::~__tree()
1369 {
1370     destroy(__root());
1371 }
1372
1373 template <class _Tp, class _Compare, class _Allocator>
1374 void
1375 __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
1376 {
1377     if (__nd != nullptr)
1378     {
1379         destroy(static_cast<__node_pointer>(__nd->__left_));
1380         destroy(static_cast<__node_pointer>(__nd->__right_));
1381         __node_allocator& __na = __node_alloc();
1382         __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_));
1383         __node_traits::deallocate(__na, __nd, 1);
1384     }
1385 }
1386
1387 template <class _Tp, class _Compare, class _Allocator>
1388 void
1389 __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1390         _NOEXCEPT_(
1391             __is_nothrow_swappable<value_compare>::value
1392 #if _LIBCPP_STD_VER <= 11
1393             && (!__node_traits::propagate_on_container_swap::value ||
1394                  __is_nothrow_swappable<__node_allocator>::value)
1395 #endif
1396             )
1397 {
1398     using _VSTD::swap;
1399     swap(__begin_node_, __t.__begin_node_);
1400     swap(__pair1_.first(), __t.__pair1_.first());
1401     __swap_allocator(__node_alloc(), __t.__node_alloc());
1402     __pair3_.swap(__t.__pair3_);
1403     if (size() == 0)
1404         __begin_node() = __end_node();
1405     else
1406         __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1407     if (__t.size() == 0)
1408         __t.__begin_node() = __t.__end_node();
1409     else
1410         __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
1411 }
1412
1413 template <class _Tp, class _Compare, class _Allocator>
1414 void
1415 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
1416 {
1417     destroy(__root());
1418     size() = 0;
1419     __begin_node() = __end_node();
1420     __end_node()->__left_ = nullptr;
1421 }
1422
1423 // Find lower_bound place to insert
1424 // Set __parent to parent of null leaf
1425 // Return reference to null leaf
1426 template <class _Tp, class _Compare, class _Allocator>
1427 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1428 __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent,
1429                                                    const value_type& __v)
1430 {
1431     __node_pointer __nd = __root();
1432     if (__nd != nullptr)
1433     {
1434         while (true)
1435         {
1436             if (value_comp()(__nd->__value_, __v))
1437             {
1438                 if (__nd->__right_ != nullptr)
1439                     __nd = static_cast<__node_pointer>(__nd->__right_);
1440                 else
1441                 {
1442                     __parent = static_cast<__node_base_pointer>(__nd);
1443                     return __parent->__right_;
1444                 }
1445             }
1446             else
1447             {
1448                 if (__nd->__left_ != nullptr)
1449                     __nd = static_cast<__node_pointer>(__nd->__left_);
1450                 else
1451                 {
1452                     __parent = static_cast<__node_base_pointer>(__nd);
1453                     return __parent->__left_;
1454                 }
1455             }
1456         }
1457     }
1458     __parent = static_cast<__node_base_pointer>(__end_node());
1459     return __parent->__left_;
1460 }
1461
1462 // Find upper_bound place to insert
1463 // Set __parent to parent of null leaf
1464 // Return reference to null leaf
1465 template <class _Tp, class _Compare, class _Allocator>
1466 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1467 __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent,
1468                                                     const value_type& __v)
1469 {
1470     __node_pointer __nd = __root();
1471     if (__nd != nullptr)
1472     {
1473         while (true)
1474         {
1475             if (value_comp()(__v, __nd->__value_))
1476             {
1477                 if (__nd->__left_ != nullptr)
1478                     __nd = static_cast<__node_pointer>(__nd->__left_);
1479                 else
1480                 {
1481                     __parent = static_cast<__node_base_pointer>(__nd);
1482                     return __parent->__left_;
1483                 }
1484             }
1485             else
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         }
1496     }
1497     __parent = static_cast<__node_base_pointer>(__end_node());
1498     return __parent->__left_;
1499 }
1500
1501 // Find leaf place to insert closest to __hint
1502 // First check prior to __hint.
1503 // Next check after __hint.
1504 // Next do O(log N) search.
1505 // Set __parent to parent of null leaf
1506 // Return reference to null leaf
1507 template <class _Tp, class _Compare, class _Allocator>
1508 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1509 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
1510                                                typename __node_base::pointer& __parent,
1511                                                const value_type& __v)
1512 {
1513     if (__hint == end() || !value_comp()(*__hint, __v))  // check before
1514     {
1515         // __v <= *__hint
1516         const_iterator __prior = __hint;
1517         if (__prior == begin() || !value_comp()(__v, *--__prior))
1518         {
1519             // *prev(__hint) <= __v <= *__hint
1520             if (__hint.__ptr_->__left_ == nullptr)
1521             {
1522                 __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1523                 return __parent->__left_;
1524             }
1525             else
1526             {
1527                 __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
1528                 return __parent->__right_;
1529             }
1530         }
1531         // __v < *prev(__hint)
1532         return __find_leaf_high(__parent, __v);
1533     }
1534     // else __v > *__hint
1535     return __find_leaf_low(__parent, __v);
1536 }
1537
1538 // Find place to insert if __v doesn't exist
1539 // Set __parent to parent of null leaf
1540 // Return reference to null leaf
1541 // If __v exists, set parent to node of __v and return reference to node of __v
1542 template <class _Tp, class _Compare, class _Allocator>
1543 template <class _Key>
1544 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1545 __tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent,
1546                                                 const _Key& __v)
1547 {
1548     __node_pointer __nd = __root();
1549     if (__nd != nullptr)
1550     {
1551         while (true)
1552         {
1553             if (value_comp()(__v, __nd->__value_))
1554             {
1555                 if (__nd->__left_ != nullptr)
1556                     __nd = static_cast<__node_pointer>(__nd->__left_);
1557                 else
1558                 {
1559                     __parent = static_cast<__node_base_pointer>(__nd);
1560                     return __parent->__left_;
1561                 }
1562             }
1563             else if (value_comp()(__nd->__value_, __v))
1564             {
1565                 if (__nd->__right_ != nullptr)
1566                     __nd = static_cast<__node_pointer>(__nd->__right_);
1567                 else
1568                 {
1569                     __parent = static_cast<__node_base_pointer>(__nd);
1570                     return __parent->__right_;
1571                 }
1572             }
1573             else
1574             {
1575                 __parent = static_cast<__node_base_pointer>(__nd);
1576                 return __parent;
1577             }
1578         }
1579     }
1580     __parent = static_cast<__node_base_pointer>(__end_node());
1581     return __parent->__left_;
1582 }
1583
1584 // Find place to insert if __v doesn't exist
1585 // First check prior to __hint.
1586 // Next check after __hint.
1587 // Next do O(log N) search.
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(const_iterator __hint,
1595                                                 typename __node_base::pointer& __parent,
1596                                                 const _Key& __v)
1597 {
1598     if (__hint == end() || value_comp()(__v, *__hint))  // check before
1599     {
1600         // __v < *__hint
1601         const_iterator __prior = __hint;
1602         if (__prior == begin() || value_comp()(*--__prior, __v))
1603         {
1604             // *prev(__hint) < __v < *__hint
1605             if (__hint.__ptr_->__left_ == nullptr)
1606             {
1607                 __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1608                 return __parent->__left_;
1609             }
1610             else
1611             {
1612                 __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
1613                 return __parent->__right_;
1614             }
1615         }
1616         // __v <= *prev(__hint)
1617         return __find_equal(__parent, __v);
1618     }
1619     else if (value_comp()(*__hint, __v))  // check after
1620     {
1621         // *__hint < __v
1622         const_iterator __next = _VSTD::next(__hint);
1623         if (__next == end() || value_comp()(__v, *__next))
1624         {
1625             // *__hint < __v < *_VSTD::next(__hint)
1626             if (__hint.__ptr_->__right_ == nullptr)
1627             {
1628                 __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1629                 return __parent->__right_;
1630             }
1631             else
1632             {
1633                 __parent = static_cast<__node_base_pointer>(__next.__ptr_);
1634                 return __parent->__left_;
1635             }
1636         }
1637         // *next(__hint) <= __v
1638         return __find_equal(__parent, __v);
1639     }
1640     // else __v == *__hint
1641     __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1642     return __parent;
1643 }
1644
1645 template <class _Tp, class _Compare, class _Allocator>
1646 void
1647 __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent,
1648                                                     __node_base_pointer& __child,
1649                                                     __node_base_pointer __new_node)
1650 {
1651     __new_node->__left_   = nullptr;
1652     __new_node->__right_  = nullptr;
1653     __new_node->__parent_ = __parent;
1654     __child = __new_node;
1655     if (__begin_node()->__left_ != nullptr)
1656         __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
1657     __tree_balance_after_insert(__end_node()->__left_, __child);
1658     ++size();
1659 }
1660
1661 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1662 #ifndef _LIBCPP_HAS_NO_VARIADICS
1663
1664 template <class _Tp, class _Compare, class _Allocator>
1665 template <class ..._Args>
1666 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
1667 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
1668 {
1669     __node_allocator& __na = __node_alloc();
1670     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1671     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
1672     __h.get_deleter().__value_constructed = true;
1673     return __h;
1674 }
1675
1676 template <class _Tp, class _Compare, class _Allocator>
1677 template <class... _Args>
1678 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1679 __tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args)
1680 {
1681     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1682     __node_base_pointer __parent;
1683     __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
1684     __node_pointer __r = static_cast<__node_pointer>(__child);
1685     bool __inserted = false;
1686     if (__child == nullptr)
1687     {
1688         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1689         __r = __h.release();
1690         __inserted = true;
1691     }
1692     return pair<iterator, bool>(iterator(__r), __inserted);
1693 }
1694
1695 template <class _Tp, class _Compare, class _Allocator>
1696 template <class... _Args>
1697 typename __tree<_Tp, _Compare, _Allocator>::iterator
1698 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args)
1699 {
1700     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1701     __node_base_pointer __parent;
1702     __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_);
1703     __node_pointer __r = static_cast<__node_pointer>(__child);
1704     if (__child == nullptr)
1705     {
1706         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1707         __r = __h.release();
1708     }
1709     return iterator(__r);
1710 }
1711
1712 template <class _Tp, class _Compare, class _Allocator>
1713 template <class... _Args>
1714 typename __tree<_Tp, _Compare, _Allocator>::iterator
1715 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
1716 {
1717     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1718     __node_base_pointer __parent;
1719     __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1720     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1721     return iterator(static_cast<__node_pointer>(__h.release()));
1722 }
1723
1724 template <class _Tp, class _Compare, class _Allocator>
1725 template <class... _Args>
1726 typename __tree<_Tp, _Compare, _Allocator>::iterator
1727 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
1728                                                         _Args&&... __args)
1729 {
1730     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1731     __node_base_pointer __parent;
1732     __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1733     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1734     return iterator(static_cast<__node_pointer>(__h.release()));
1735 }
1736
1737 #endif  // _LIBCPP_HAS_NO_VARIADICS
1738
1739 template <class _Tp, class _Compare, class _Allocator>
1740 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1741 __tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v)
1742 {
1743     __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
1744     pair<iterator, bool> __r = __node_insert_unique(__h.get());
1745     if (__r.second)
1746         __h.release();
1747     return __r;
1748 }
1749
1750 template <class _Tp, class _Compare, class _Allocator>
1751 typename __tree<_Tp, _Compare, _Allocator>::iterator
1752 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v)
1753 {
1754     __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
1755     iterator __r = __node_insert_unique(__p, __h.get());
1756     if (__r.__ptr_ == __h.get())
1757         __h.release();
1758     return __r;
1759 }
1760
1761 template <class _Tp, class _Compare, class _Allocator>
1762 template <class _Vp>
1763 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1764 __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v)
1765 {
1766     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1767     pair<iterator, bool> __r = __node_insert_unique(__h.get());
1768     if (__r.second)
1769         __h.release();
1770     return __r;
1771 }
1772
1773 template <class _Tp, class _Compare, class _Allocator>
1774 template <class _Vp>
1775 typename __tree<_Tp, _Compare, _Allocator>::iterator
1776 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v)
1777 {
1778     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1779     iterator __r = __node_insert_unique(__p, __h.get());
1780     if (__r.__ptr_ == __h.get())
1781         __h.release();
1782     return __r;
1783 }
1784
1785 template <class _Tp, class _Compare, class _Allocator>
1786 typename __tree<_Tp, _Compare, _Allocator>::iterator
1787 __tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v)
1788 {
1789     __node_base_pointer __parent;
1790     __node_base_pointer& __child = __find_leaf_high(__parent, __v);
1791     __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
1792     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1793     return iterator(__h.release());
1794 }
1795
1796 template <class _Tp, class _Compare, class _Allocator>
1797 typename __tree<_Tp, _Compare, _Allocator>::iterator
1798 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v)
1799 {
1800     __node_base_pointer __parent;
1801     __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
1802     __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
1803     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1804     return iterator(__h.release());
1805 }
1806
1807 template <class _Tp, class _Compare, class _Allocator>
1808 template <class _Vp>
1809 typename __tree<_Tp, _Compare, _Allocator>::iterator
1810 __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v)
1811 {
1812     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1813     __node_base_pointer __parent;
1814     __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1815     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1816     return iterator(__h.release());
1817 }
1818
1819 template <class _Tp, class _Compare, class _Allocator>
1820 template <class _Vp>
1821 typename __tree<_Tp, _Compare, _Allocator>::iterator
1822 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v)
1823 {
1824     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1825     __node_base_pointer __parent;
1826     __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1827     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1828     return iterator(__h.release());
1829 }
1830
1831 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1832
1833 template <class _Tp, class _Compare, class _Allocator>
1834 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
1835 __tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v)
1836 {
1837     __node_allocator& __na = __node_alloc();
1838     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1839     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
1840     __h.get_deleter().__value_constructed = true;
1841     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1842 }
1843
1844 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1845
1846 template <class _Tp, class _Compare, class _Allocator>
1847 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1848 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v)
1849 {
1850     __node_base_pointer __parent;
1851     __node_base_pointer& __child = __find_equal(__parent, __v);
1852     __node_pointer __r = static_cast<__node_pointer>(__child);
1853     bool __inserted = false;
1854     if (__child == nullptr)
1855     {
1856         __node_holder __h = __construct_node(__v);
1857         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1858         __r = __h.release();
1859         __inserted = true;
1860     }
1861     return pair<iterator, bool>(iterator(__r), __inserted);
1862 }
1863
1864 template <class _Tp, class _Compare, class _Allocator>
1865 typename __tree<_Tp, _Compare, _Allocator>::iterator
1866 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v)
1867 {
1868     __node_base_pointer __parent;
1869     __node_base_pointer& __child = __find_equal(__p, __parent, __v);
1870     __node_pointer __r = static_cast<__node_pointer>(__child);
1871     if (__child == nullptr)
1872     {
1873         __node_holder __h = __construct_node(__v);
1874         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1875         __r = __h.release();
1876     }
1877     return iterator(__r);
1878 }
1879
1880 template <class _Tp, class _Compare, class _Allocator>
1881 typename __tree<_Tp, _Compare, _Allocator>::iterator
1882 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v)
1883 {
1884     __node_base_pointer __parent;
1885     __node_base_pointer& __child = __find_leaf_high(__parent, __v);
1886     __node_holder __h = __construct_node(__v);
1887     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1888     return iterator(__h.release());
1889 }
1890
1891 template <class _Tp, class _Compare, class _Allocator>
1892 typename __tree<_Tp, _Compare, _Allocator>::iterator
1893 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v)
1894 {
1895     __node_base_pointer __parent;
1896     __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
1897     __node_holder __h = __construct_node(__v);
1898     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1899     return iterator(__h.release());
1900 }
1901
1902 template <class _Tp, class _Compare, class _Allocator>
1903 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1904 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
1905 {
1906     __node_base_pointer __parent;
1907     __node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
1908     __node_pointer __r = static_cast<__node_pointer>(__child);
1909     bool __inserted = false;
1910     if (__child == nullptr)
1911     {
1912         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1913         __r = __nd;
1914         __inserted = true;
1915     }
1916     return pair<iterator, bool>(iterator(__r), __inserted);
1917 }
1918
1919 template <class _Tp, class _Compare, class _Allocator>
1920 typename __tree<_Tp, _Compare, _Allocator>::iterator
1921 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
1922                                                         __node_pointer __nd)
1923 {
1924     __node_base_pointer __parent;
1925     __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
1926     __node_pointer __r = static_cast<__node_pointer>(__child);
1927     if (__child == nullptr)
1928     {
1929         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1930         __r = __nd;
1931     }
1932     return iterator(__r);
1933 }
1934
1935 template <class _Tp, class _Compare, class _Allocator>
1936 typename __tree<_Tp, _Compare, _Allocator>::iterator
1937 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
1938 {
1939     __node_base_pointer __parent;
1940     __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_);
1941     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1942     return iterator(__nd);
1943 }
1944
1945 template <class _Tp, class _Compare, class _Allocator>
1946 typename __tree<_Tp, _Compare, _Allocator>::iterator
1947 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
1948                                                        __node_pointer __nd)
1949 {
1950     __node_base_pointer __parent;
1951     __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_);
1952     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1953     return iterator(__nd);
1954 }
1955
1956 template <class _Tp, class _Compare, class _Allocator>
1957 typename __tree<_Tp, _Compare, _Allocator>::iterator
1958 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
1959 {
1960     __node_pointer __np = __p.__ptr_;
1961     iterator __r(__np);
1962     ++__r;
1963     if (__begin_node() == __np)
1964         __begin_node() = __r.__ptr_;
1965     --size();
1966     __node_allocator& __na = __node_alloc();
1967     __tree_remove(__end_node()->__left_,
1968                   static_cast<__node_base_pointer>(__np));
1969     __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p)));
1970     __node_traits::deallocate(__na, __np, 1);
1971     return __r;
1972 }
1973
1974 template <class _Tp, class _Compare, class _Allocator>
1975 typename __tree<_Tp, _Compare, _Allocator>::iterator
1976 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
1977 {
1978     while (__f != __l)
1979         __f = erase(__f);
1980     return iterator(__l.__ptr_);
1981 }
1982
1983 template <class _Tp, class _Compare, class _Allocator>
1984 template <class _Key>
1985 typename __tree<_Tp, _Compare, _Allocator>::size_type
1986 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
1987 {
1988     iterator __i = find(__k);
1989     if (__i == end())
1990         return 0;
1991     erase(__i);
1992     return 1;
1993 }
1994
1995 template <class _Tp, class _Compare, class _Allocator>
1996 template <class _Key>
1997 typename __tree<_Tp, _Compare, _Allocator>::size_type
1998 __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
1999 {
2000     pair<iterator, iterator> __p = __equal_range_multi(__k);
2001     size_type __r = 0;
2002     for (; __p.first != __p.second; ++__r)
2003         __p.first = erase(__p.first);
2004     return __r;
2005 }
2006
2007 template <class _Tp, class _Compare, class _Allocator>
2008 template <class _Key>
2009 typename __tree<_Tp, _Compare, _Allocator>::iterator
2010 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
2011 {
2012     iterator __p = __lower_bound(__v, __root(), __end_node());
2013     if (__p != end() && !value_comp()(__v, *__p))
2014         return __p;
2015     return end();
2016 }
2017
2018 template <class _Tp, class _Compare, class _Allocator>
2019 template <class _Key>
2020 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2021 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
2022 {
2023     const_iterator __p = __lower_bound(__v, __root(), __end_node());
2024     if (__p != end() && !value_comp()(__v, *__p))
2025         return __p;
2026     return end();
2027 }
2028
2029 template <class _Tp, class _Compare, class _Allocator>
2030 template <class _Key>
2031 typename __tree<_Tp, _Compare, _Allocator>::size_type
2032 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
2033 {
2034     __node_const_pointer __result = __end_node();
2035     __node_const_pointer __rt = __root();
2036     while (__rt != nullptr)
2037     {
2038         if (value_comp()(__k, __rt->__value_))
2039         {
2040             __result = __rt;
2041             __rt = static_cast<__node_const_pointer>(__rt->__left_);
2042         }
2043         else if (value_comp()(__rt->__value_, __k))
2044             __rt = static_cast<__node_const_pointer>(__rt->__right_);
2045         else
2046             return 1;
2047     }
2048     return 0;
2049 }
2050
2051 template <class _Tp, class _Compare, class _Allocator>
2052 template <class _Key>
2053 typename __tree<_Tp, _Compare, _Allocator>::size_type
2054 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
2055 {
2056     __node_const_pointer __result = __end_node();
2057     __node_const_pointer __rt = __root();
2058     while (__rt != nullptr)
2059     {
2060         if (value_comp()(__k, __rt->__value_))
2061         {
2062             __result = __rt;
2063             __rt = static_cast<__node_const_pointer>(__rt->__left_);
2064         }
2065         else if (value_comp()(__rt->__value_, __k))
2066             __rt = static_cast<__node_const_pointer>(__rt->__right_);
2067         else
2068             return _VSTD::distance(
2069                 __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2070                 __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)
2071             );
2072     }
2073     return 0;
2074 }
2075
2076 template <class _Tp, class _Compare, class _Allocator>
2077 template <class _Key>
2078 typename __tree<_Tp, _Compare, _Allocator>::iterator
2079 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2080                                                  __node_pointer __root,
2081                                                  __node_pointer __result)
2082 {
2083     while (__root != nullptr)
2084     {
2085         if (!value_comp()(__root->__value_, __v))
2086         {
2087             __result = __root;
2088             __root = static_cast<__node_pointer>(__root->__left_);
2089         }
2090         else
2091             __root = static_cast<__node_pointer>(__root->__right_);
2092     }
2093     return iterator(__result);
2094 }
2095
2096 template <class _Tp, class _Compare, class _Allocator>
2097 template <class _Key>
2098 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2099 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2100                                                  __node_const_pointer __root,
2101                                                  __node_const_pointer __result) const
2102 {
2103     while (__root != nullptr)
2104     {
2105         if (!value_comp()(__root->__value_, __v))
2106         {
2107             __result = __root;
2108             __root = static_cast<__node_const_pointer>(__root->__left_);
2109         }
2110         else
2111             __root = static_cast<__node_const_pointer>(__root->__right_);
2112     }
2113     return const_iterator(__result);
2114 }
2115
2116 template <class _Tp, class _Compare, class _Allocator>
2117 template <class _Key>
2118 typename __tree<_Tp, _Compare, _Allocator>::iterator
2119 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2120                                                  __node_pointer __root,
2121                                                  __node_pointer __result)
2122 {
2123     while (__root != nullptr)
2124     {
2125         if (value_comp()(__v, __root->__value_))
2126         {
2127             __result = __root;
2128             __root = static_cast<__node_pointer>(__root->__left_);
2129         }
2130         else
2131             __root = static_cast<__node_pointer>(__root->__right_);
2132     }
2133     return iterator(__result);
2134 }
2135
2136 template <class _Tp, class _Compare, class _Allocator>
2137 template <class _Key>
2138 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2139 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2140                                                  __node_const_pointer __root,
2141                                                  __node_const_pointer __result) const
2142 {
2143     while (__root != nullptr)
2144     {
2145         if (value_comp()(__v, __root->__value_))
2146         {
2147             __result = __root;
2148             __root = static_cast<__node_const_pointer>(__root->__left_);
2149         }
2150         else
2151             __root = static_cast<__node_const_pointer>(__root->__right_);
2152     }
2153     return const_iterator(__result);
2154 }
2155
2156 template <class _Tp, class _Compare, class _Allocator>
2157 template <class _Key>
2158 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2159      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2160 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
2161 {
2162     typedef pair<iterator, iterator> _Pp;
2163     __node_pointer __result = __end_node();
2164     __node_pointer __rt = __root();
2165     while (__rt != nullptr)
2166     {
2167         if (value_comp()(__k, __rt->__value_))
2168         {
2169             __result = __rt;
2170             __rt = static_cast<__node_pointer>(__rt->__left_);
2171         }
2172         else if (value_comp()(__rt->__value_, __k))
2173             __rt = static_cast<__node_pointer>(__rt->__right_);
2174         else
2175             return _Pp(iterator(__rt),
2176                       iterator(
2177                           __rt->__right_ != nullptr ?
2178                               static_cast<__node_pointer>(__tree_min(__rt->__right_))
2179                             : __result));
2180     }
2181     return _Pp(iterator(__result), iterator(__result));
2182 }
2183
2184 template <class _Tp, class _Compare, class _Allocator>
2185 template <class _Key>
2186 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2187      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2188 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
2189 {
2190     typedef pair<const_iterator, const_iterator> _Pp;
2191     __node_const_pointer __result = __end_node();
2192     __node_const_pointer __rt = __root();
2193     while (__rt != nullptr)
2194     {
2195         if (value_comp()(__k, __rt->__value_))
2196         {
2197             __result = __rt;
2198             __rt = static_cast<__node_const_pointer>(__rt->__left_);
2199         }
2200         else if (value_comp()(__rt->__value_, __k))
2201             __rt = static_cast<__node_const_pointer>(__rt->__right_);
2202         else
2203             return _Pp(const_iterator(__rt),
2204                       const_iterator(
2205                           __rt->__right_ != nullptr ?
2206                               static_cast<__node_const_pointer>(__tree_min(__rt->__right_))
2207                             : __result));
2208     }
2209     return _Pp(const_iterator(__result), const_iterator(__result));
2210 }
2211
2212 template <class _Tp, class _Compare, class _Allocator>
2213 template <class _Key>
2214 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2215      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2216 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
2217 {
2218     typedef pair<iterator, iterator> _Pp;
2219     __node_pointer __result = __end_node();
2220     __node_pointer __rt = __root();
2221     while (__rt != nullptr)
2222     {
2223         if (value_comp()(__k, __rt->__value_))
2224         {
2225             __result = __rt;
2226             __rt = static_cast<__node_pointer>(__rt->__left_);
2227         }
2228         else if (value_comp()(__rt->__value_, __k))
2229             __rt = static_cast<__node_pointer>(__rt->__right_);
2230         else
2231             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
2232                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2233     }
2234     return _Pp(iterator(__result), iterator(__result));
2235 }
2236
2237 template <class _Tp, class _Compare, class _Allocator>
2238 template <class _Key>
2239 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2240      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2241 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
2242 {
2243     typedef pair<const_iterator, const_iterator> _Pp;
2244     __node_const_pointer __result = __end_node();
2245     __node_const_pointer __rt = __root();
2246     while (__rt != nullptr)
2247     {
2248         if (value_comp()(__k, __rt->__value_))
2249         {
2250             __result = __rt;
2251             __rt = static_cast<__node_const_pointer>(__rt->__left_);
2252         }
2253         else if (value_comp()(__rt->__value_, __k))
2254             __rt = static_cast<__node_const_pointer>(__rt->__right_);
2255         else
2256             return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2257                       __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result));
2258     }
2259     return _Pp(const_iterator(__result), const_iterator(__result));
2260 }
2261
2262 template <class _Tp, class _Compare, class _Allocator>
2263 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2264 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2265 {
2266     __node_pointer __np = __p.__ptr_;
2267     if (__begin_node() == __np)
2268     {
2269         if (__np->__right_ != nullptr)
2270             __begin_node() = static_cast<__node_pointer>(__np->__right_);
2271         else
2272             __begin_node() = static_cast<__node_pointer>(__np->__parent_);
2273     }
2274     --size();
2275     __tree_remove(__end_node()->__left_,
2276                   static_cast<__node_base_pointer>(__np));
2277     return __node_holder(__np, _Dp(__node_alloc(), true));
2278 }
2279
2280 template <class _Tp, class _Compare, class _Allocator>
2281 inline _LIBCPP_INLINE_VISIBILITY
2282 void
2283 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2284      __tree<_Tp, _Compare, _Allocator>& __y)
2285     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2286 {
2287     __x.swap(__y);
2288 }
2289
2290 _LIBCPP_END_NAMESPACE_STD
2291
2292 #endif  // _LIBCPP___TREE