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