contrib/libc++/include/__tree

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