contrib/libc++/include/__tree

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