include/__tree

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