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