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 std::min<size_type>(
1110                 __node_traits::max_size(__node_alloc()),
1111                 numeric_limits<difference_type >::max());}
1112
1113     void clear() _NOEXCEPT;
1114
1115     void swap(__tree& __t)
1116 #if _LIBCPP_STD_VER <= 11
1117         _NOEXCEPT_(
1118             __is_nothrow_swappable<value_compare>::value
1119             && (!__node_traits::propagate_on_container_swap::value ||
1120                  __is_nothrow_swappable<__node_allocator>::value)
1121             );
1122 #else
1123         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value);
1124 #endif
1125
1126 #ifndef _LIBCPP_CXX03_LANG
1127     template <class _Key, class ..._Args>
1128     pair<iterator, bool>
1129     __emplace_unique_key_args(_Key const&, _Args&&... __args);
1130     template <class _Key, class ..._Args>
1131     iterator
1132     __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
1133
1134     template <class... _Args>
1135     pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
1136
1137     template <class... _Args>
1138     iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
1139
1140     template <class... _Args>
1141     iterator __emplace_multi(_Args&&... __args);
1142
1143     template <class... _Args>
1144     iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1145
1146     template <class _Pp>
1147     _LIBCPP_INLINE_VISIBILITY
1148     pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1149         return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1150                                             __can_extract_key<_Pp, key_type>());
1151     }
1152
1153     template <class _First, class _Second>
1154     _LIBCPP_INLINE_VISIBILITY
1155     typename enable_if<
1156         __can_extract_map_key<_First, key_type, __container_value_type>::value,
1157         pair<iterator, bool>
1158     >::type __emplace_unique(_First&& __f, _Second&& __s) {
1159         return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
1160                                               _VSTD::forward<_Second>(__s));
1161     }
1162
1163     template <class... _Args>
1164     _LIBCPP_INLINE_VISIBILITY
1165     pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1166         return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1167     }
1168
1169     template <class _Pp>
1170     _LIBCPP_INLINE_VISIBILITY
1171     pair<iterator, bool>
1172     __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1173       return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1174     }
1175
1176     template <class _Pp>
1177     _LIBCPP_INLINE_VISIBILITY
1178     pair<iterator, bool>
1179     __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1180       return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1181     }
1182
1183     template <class _Pp>
1184     _LIBCPP_INLINE_VISIBILITY
1185     pair<iterator, bool>
1186     __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1187       return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1188     }
1189
1190     template <class _Pp>
1191     _LIBCPP_INLINE_VISIBILITY
1192     iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
1193         return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
1194                                             __can_extract_key<_Pp, key_type>());
1195     }
1196
1197     template <class _First, class _Second>
1198     _LIBCPP_INLINE_VISIBILITY
1199     typename enable_if<
1200         __can_extract_map_key<_First, key_type, __container_value_type>::value,
1201         iterator
1202     >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
1203         return __emplace_hint_unique_key_args(__p, __f,
1204                                               _VSTD::forward<_First>(__f),
1205                                               _VSTD::forward<_Second>(__s));
1206     }
1207
1208     template <class... _Args>
1209     _LIBCPP_INLINE_VISIBILITY
1210     iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
1211         return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...);
1212     }
1213
1214     template <class _Pp>
1215     _LIBCPP_INLINE_VISIBILITY
1216     iterator
1217     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
1218       return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
1219     }
1220
1221     template <class _Pp>
1222     _LIBCPP_INLINE_VISIBILITY
1223     iterator
1224     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
1225       return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x));
1226     }
1227
1228     template <class _Pp>
1229     _LIBCPP_INLINE_VISIBILITY
1230     iterator
1231     __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
1232       return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x));
1233     }
1234
1235 #else
1236     template <class _Key, class _Args>
1237     _LIBCPP_INLINE_VISIBILITY
1238     pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
1239     template <class _Key, class _Args>
1240     _LIBCPP_INLINE_VISIBILITY
1241     iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&);
1242 #endif
1243
1244     _LIBCPP_INLINE_VISIBILITY
1245     pair<iterator, bool> __insert_unique(const __container_value_type& __v) {
1246         return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v);
1247     }
1248
1249     _LIBCPP_INLINE_VISIBILITY
1250     iterator __insert_unique(const_iterator __p, const __container_value_type& __v) {
1251         return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v);
1252     }
1253
1254 #ifdef _LIBCPP_CXX03_LANG
1255     _LIBCPP_INLINE_VISIBILITY
1256     iterator __insert_multi(const __container_value_type& __v);
1257     _LIBCPP_INLINE_VISIBILITY
1258     iterator __insert_multi(const_iterator __p, const __container_value_type& __v);
1259 #else
1260     _LIBCPP_INLINE_VISIBILITY
1261     pair<iterator, bool> __insert_unique(__container_value_type&& __v) {
1262         return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v));
1263     }
1264
1265     _LIBCPP_INLINE_VISIBILITY
1266     iterator __insert_unique(const_iterator __p, __container_value_type&& __v) {
1267         return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v));
1268     }
1269
1270     template <class _Vp, class = typename enable_if<
1271             !is_same<typename __unconstref<_Vp>::type,
1272                      __container_value_type
1273             >::value
1274         >::type>
1275     _LIBCPP_INLINE_VISIBILITY
1276     pair<iterator, bool> __insert_unique(_Vp&& __v) {
1277         return __emplace_unique(_VSTD::forward<_Vp>(__v));
1278     }
1279
1280     template <class _Vp, class = typename enable_if<
1281             !is_same<typename __unconstref<_Vp>::type,
1282                      __container_value_type
1283             >::value
1284         >::type>
1285     _LIBCPP_INLINE_VISIBILITY
1286     iterator __insert_unique(const_iterator __p, _Vp&& __v) {
1287         return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v));
1288     }
1289
1290     _LIBCPP_INLINE_VISIBILITY
1291     iterator __insert_multi(__container_value_type&& __v) {
1292         return __emplace_multi(_VSTD::move(__v));
1293     }
1294
1295     _LIBCPP_INLINE_VISIBILITY
1296     iterator __insert_multi(const_iterator __p, __container_value_type&& __v) {
1297         return __emplace_hint_multi(__p, _VSTD::move(__v));
1298     }
1299
1300     template <class _Vp>
1301     _LIBCPP_INLINE_VISIBILITY
1302     iterator __insert_multi(_Vp&& __v) {
1303         return __emplace_multi(_VSTD::forward<_Vp>(__v));
1304     }
1305
1306     template <class _Vp>
1307     _LIBCPP_INLINE_VISIBILITY
1308     iterator __insert_multi(const_iterator __p, _Vp&& __v) {
1309         return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v));
1310     }
1311
1312 #endif // !_LIBCPP_CXX03_LANG
1313
1314     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
1315     iterator             __node_insert_unique(const_iterator __p,
1316                                               __node_pointer __nd);
1317
1318     iterator __node_insert_multi(__node_pointer __nd);
1319     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
1320
1321     iterator erase(const_iterator __p);
1322     iterator erase(const_iterator __f, const_iterator __l);
1323     template <class _Key>
1324         size_type __erase_unique(const _Key& __k);
1325     template <class _Key>
1326         size_type __erase_multi(const _Key& __k);
1327
1328     void __insert_node_at(__parent_pointer     __parent,
1329                           __node_base_pointer& __child,
1330                           __node_base_pointer __new_node);
1331
1332     template <class _Key>
1333         iterator find(const _Key& __v);
1334     template <class _Key>
1335         const_iterator find(const _Key& __v) const;
1336
1337     template <class _Key>
1338         size_type __count_unique(const _Key& __k) const;
1339     template <class _Key>
1340         size_type __count_multi(const _Key& __k) const;
1341
1342     template <class _Key>
1343         _LIBCPP_INLINE_VISIBILITY
1344         iterator lower_bound(const _Key& __v)
1345             {return __lower_bound(__v, __root(), __end_node());}
1346     template <class _Key>
1347         iterator __lower_bound(const _Key& __v,
1348                                __node_pointer __root,
1349                                __iter_pointer __result);
1350     template <class _Key>
1351         _LIBCPP_INLINE_VISIBILITY
1352         const_iterator lower_bound(const _Key& __v) const
1353             {return __lower_bound(__v, __root(), __end_node());}
1354     template <class _Key>
1355         const_iterator __lower_bound(const _Key& __v,
1356                                      __node_pointer __root,
1357                                      __iter_pointer __result) const;
1358     template <class _Key>
1359         _LIBCPP_INLINE_VISIBILITY
1360         iterator upper_bound(const _Key& __v)
1361             {return __upper_bound(__v, __root(), __end_node());}
1362     template <class _Key>
1363         iterator __upper_bound(const _Key& __v,
1364                                __node_pointer __root,
1365                                __iter_pointer __result);
1366     template <class _Key>
1367         _LIBCPP_INLINE_VISIBILITY
1368         const_iterator upper_bound(const _Key& __v) const
1369             {return __upper_bound(__v, __root(), __end_node());}
1370     template <class _Key>
1371         const_iterator __upper_bound(const _Key& __v,
1372                                      __node_pointer __root,
1373                                      __iter_pointer __result) const;
1374     template <class _Key>
1375         pair<iterator, iterator>
1376         __equal_range_unique(const _Key& __k);
1377     template <class _Key>
1378         pair<const_iterator, const_iterator>
1379         __equal_range_unique(const _Key& __k) const;
1380
1381     template <class _Key>
1382         pair<iterator, iterator>
1383         __equal_range_multi(const _Key& __k);
1384     template <class _Key>
1385         pair<const_iterator, const_iterator>
1386         __equal_range_multi(const _Key& __k) const;
1387
1388     typedef __tree_node_destructor<__node_allocator> _Dp;
1389     typedef unique_ptr<__node, _Dp> __node_holder;
1390
1391     __node_holder remove(const_iterator __p) _NOEXCEPT;
1392 private:
1393     __node_base_pointer&
1394         __find_leaf_low(__parent_pointer& __parent, const key_type& __v);
1395     __node_base_pointer&
1396         __find_leaf_high(__parent_pointer& __parent, const key_type& __v);
1397     __node_base_pointer&
1398         __find_leaf(const_iterator __hint,
1399                     __parent_pointer& __parent, const key_type& __v);
1400     template <class _Key>
1401     __node_base_pointer&
1402         __find_equal(__parent_pointer& __parent, const _Key& __v);
1403     template <class _Key>
1404     __node_base_pointer&
1405         __find_equal(const_iterator __hint, __parent_pointer& __parent,
1406                      __node_base_pointer& __dummy,
1407                      const _Key& __v);
1408
1409 #ifndef _LIBCPP_CXX03_LANG
1410     template <class ..._Args>
1411     __node_holder __construct_node(_Args&& ...__args);
1412 #else
1413     __node_holder __construct_node(const __container_value_type& __v);
1414 #endif
1415
1416     void destroy(__node_pointer __nd) _NOEXCEPT;
1417
1418     _LIBCPP_INLINE_VISIBILITY
1419     void __copy_assign_alloc(const __tree& __t)
1420         {__copy_assign_alloc(__t, integral_constant<bool,
1421              __node_traits::propagate_on_container_copy_assignment::value>());}
1422
1423     _LIBCPP_INLINE_VISIBILITY
1424     void __copy_assign_alloc(const __tree& __t, true_type)
1425         {
1426         if (__node_alloc() != __t.__node_alloc())
1427                 clear();
1428         __node_alloc() = __t.__node_alloc();
1429         }
1430     _LIBCPP_INLINE_VISIBILITY
1431     void __copy_assign_alloc(const __tree&, false_type) {}
1432
1433     void __move_assign(__tree& __t, false_type);
1434     void __move_assign(__tree& __t, true_type)
1435         _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1436                    is_nothrow_move_assignable<__node_allocator>::value);
1437
1438     _LIBCPP_INLINE_VISIBILITY
1439     void __move_assign_alloc(__tree& __t)
1440         _NOEXCEPT_(
1441             !__node_traits::propagate_on_container_move_assignment::value ||
1442             is_nothrow_move_assignable<__node_allocator>::value)
1443         {__move_assign_alloc(__t, integral_constant<bool,
1444              __node_traits::propagate_on_container_move_assignment::value>());}
1445
1446     _LIBCPP_INLINE_VISIBILITY
1447     void __move_assign_alloc(__tree& __t, true_type)
1448         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1449         {__node_alloc() = _VSTD::move(__t.__node_alloc());}
1450     _LIBCPP_INLINE_VISIBILITY
1451     void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}
1452
1453     __node_pointer __detach();
1454     static __node_pointer __detach(__node_pointer);
1455
1456     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
1457     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
1458 };
1459
1460 template <class _Tp, class _Compare, class _Allocator>
1461 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
1462         _NOEXCEPT_(
1463             is_nothrow_default_constructible<__node_allocator>::value &&
1464             is_nothrow_copy_constructible<value_compare>::value)
1465     : __pair3_(0, __comp)
1466 {
1467     __begin_node() = __end_node();
1468 }
1469
1470 template <class _Tp, class _Compare, class _Allocator>
1471 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1472     : __begin_node_(__iter_pointer()),
1473       __pair1_(__node_allocator(__a)),
1474       __pair3_(0)
1475 {
1476     __begin_node() = __end_node();
1477 }
1478
1479 template <class _Tp, class _Compare, class _Allocator>
1480 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
1481                                            const allocator_type& __a)
1482     : __begin_node_(__iter_pointer()),
1483       __pair1_(__node_allocator(__a)),
1484       __pair3_(0, __comp)
1485 {
1486     __begin_node() = __end_node();
1487 }
1488
1489 // Precondition:  size() != 0
1490 template <class _Tp, class _Compare, class _Allocator>
1491 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1492 __tree<_Tp, _Compare, _Allocator>::__detach()
1493 {
1494     __node_pointer __cache = static_cast<__node_pointer>(__begin_node());
1495     __begin_node() = __end_node();
1496     __end_node()->__left_->__parent_ = nullptr;
1497     __end_node()->__left_ = nullptr;
1498     size() = 0;
1499     // __cache->__left_ == nullptr
1500     if (__cache->__right_ != nullptr)
1501         __cache = static_cast<__node_pointer>(__cache->__right_);
1502     // __cache->__left_ == nullptr
1503     // __cache->__right_ == nullptr
1504     return __cache;
1505 }
1506
1507 // Precondition:  __cache != nullptr
1508 //    __cache->left_ == nullptr
1509 //    __cache->right_ == nullptr
1510 //    This is no longer a red-black tree
1511 template <class _Tp, class _Compare, class _Allocator>
1512 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1513 __tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache)
1514 {
1515     if (__cache->__parent_ == nullptr)
1516         return nullptr;
1517     if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1518     {
1519         __cache->__parent_->__left_ = nullptr;
1520         __cache = static_cast<__node_pointer>(__cache->__parent_);
1521         if (__cache->__right_ == nullptr)
1522             return __cache;
1523         return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
1524     }
1525     // __cache is right child
1526     __cache->__parent_unsafe()->__right_ = nullptr;
1527     __cache = static_cast<__node_pointer>(__cache->__parent_);
1528     if (__cache->__left_ == nullptr)
1529         return __cache;
1530     return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
1531 }
1532
1533 template <class _Tp, class _Compare, class _Allocator>
1534 __tree<_Tp, _Compare, _Allocator>&
1535 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
1536 {
1537     if (this != &__t)
1538     {
1539         value_comp() = __t.value_comp();
1540         __copy_assign_alloc(__t);
1541         __assign_multi(__t.begin(), __t.end());
1542     }
1543     return *this;
1544 }
1545
1546 template <class _Tp, class _Compare, class _Allocator>
1547 template <class _InputIterator>
1548 void
1549 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last)
1550 {
1551     typedef iterator_traits<_InputIterator> _ITraits;
1552     typedef typename _ITraits::value_type _ItValueType;
1553     static_assert((is_same<_ItValueType, __container_value_type>::value),
1554                   "__assign_unique may only be called with the containers value type");
1555
1556     if (size() != 0)
1557     {
1558         __node_pointer __cache = __detach();
1559 #ifndef _LIBCPP_NO_EXCEPTIONS
1560         try
1561         {
1562 #endif  // _LIBCPP_NO_EXCEPTIONS
1563             for (; __cache != nullptr && __first != __last; ++__first)
1564             {
1565                 __cache->__value_ = *__first;
1566                 __node_pointer __next = __detach(__cache);
1567                 __node_insert_unique(__cache);
1568                 __cache = __next;
1569             }
1570 #ifndef _LIBCPP_NO_EXCEPTIONS
1571         }
1572         catch (...)
1573         {
1574             while (__cache->__parent_ != nullptr)
1575                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1576             destroy(__cache);
1577             throw;
1578         }
1579 #endif  // _LIBCPP_NO_EXCEPTIONS
1580         if (__cache != nullptr)
1581         {
1582             while (__cache->__parent_ != nullptr)
1583                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1584             destroy(__cache);
1585         }
1586     }
1587     for (; __first != __last; ++__first)
1588         __insert_unique(*__first);
1589 }
1590
1591 template <class _Tp, class _Compare, class _Allocator>
1592 template <class _InputIterator>
1593 void
1594 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
1595 {
1596     typedef iterator_traits<_InputIterator> _ITraits;
1597     typedef typename _ITraits::value_type _ItValueType;
1598     static_assert((is_same<_ItValueType, __container_value_type>::value ||
1599                   is_same<_ItValueType, __node_value_type>::value),
1600                   "__assign_multi may only be called with the containers value type"
1601                   " or the nodes value type");
1602     if (size() != 0)
1603     {
1604         __node_pointer __cache = __detach();
1605 #ifndef _LIBCPP_NO_EXCEPTIONS
1606         try
1607         {
1608 #endif  // _LIBCPP_NO_EXCEPTIONS
1609             for (; __cache != nullptr && __first != __last; ++__first)
1610             {
1611                 __cache->__value_ = *__first;
1612                 __node_pointer __next = __detach(__cache);
1613                 __node_insert_multi(__cache);
1614                 __cache = __next;
1615             }
1616 #ifndef _LIBCPP_NO_EXCEPTIONS
1617         }
1618         catch (...)
1619         {
1620             while (__cache->__parent_ != nullptr)
1621                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1622             destroy(__cache);
1623             throw;
1624         }
1625 #endif  // _LIBCPP_NO_EXCEPTIONS
1626         if (__cache != nullptr)
1627         {
1628             while (__cache->__parent_ != nullptr)
1629                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1630             destroy(__cache);
1631         }
1632     }
1633     for (; __first != __last; ++__first)
1634         __insert_multi(_NodeTypes::__get_value(*__first));
1635 }
1636
1637 template <class _Tp, class _Compare, class _Allocator>
1638 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1639     : __begin_node_(__iter_pointer()),
1640       __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1641       __pair3_(0, __t.value_comp())
1642 {
1643     __begin_node() = __end_node();
1644 }
1645
1646 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1647
1648 template <class _Tp, class _Compare, class _Allocator>
1649 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
1650     _NOEXCEPT_(
1651         is_nothrow_move_constructible<__node_allocator>::value &&
1652         is_nothrow_move_constructible<value_compare>::value)
1653     : __begin_node_(_VSTD::move(__t.__begin_node_)),
1654       __pair1_(_VSTD::move(__t.__pair1_)),
1655       __pair3_(_VSTD::move(__t.__pair3_))
1656 {
1657     if (size() == 0)
1658         __begin_node() = __end_node();
1659     else
1660     {
1661         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1662         __t.__begin_node() = __t.__end_node();
1663         __t.__end_node()->__left_ = nullptr;
1664         __t.size() = 0;
1665     }
1666 }
1667
1668 template <class _Tp, class _Compare, class _Allocator>
1669 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1670     : __pair1_(__node_allocator(__a)),
1671       __pair3_(0, _VSTD::move(__t.value_comp()))
1672 {
1673     if (__a == __t.__alloc())
1674     {
1675         if (__t.size() == 0)
1676             __begin_node() = __end_node();
1677         else
1678         {
1679             __begin_node() = __t.__begin_node();
1680             __end_node()->__left_ = __t.__end_node()->__left_;
1681             __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1682             size() = __t.size();
1683             __t.__begin_node() = __t.__end_node();
1684             __t.__end_node()->__left_ = nullptr;
1685             __t.size() = 0;
1686         }
1687     }
1688     else
1689     {
1690         __begin_node() = __end_node();
1691     }
1692 }
1693
1694 template <class _Tp, class _Compare, class _Allocator>
1695 void
1696 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1697     _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1698                is_nothrow_move_assignable<__node_allocator>::value)
1699 {
1700     destroy(static_cast<__node_pointer>(__end_node()->__left_));
1701     __begin_node_ = __t.__begin_node_;
1702     __pair1_.first() = __t.__pair1_.first();
1703     __move_assign_alloc(__t);
1704     __pair3_ = _VSTD::move(__t.__pair3_);
1705     if (size() == 0)
1706         __begin_node() = __end_node();
1707     else
1708     {
1709         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1710         __t.__begin_node() = __t.__end_node();
1711         __t.__end_node()->__left_ = nullptr;
1712         __t.size() = 0;
1713     }
1714 }
1715
1716 template <class _Tp, class _Compare, class _Allocator>
1717 void
1718 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
1719 {
1720     if (__node_alloc() == __t.__node_alloc())
1721         __move_assign(__t, true_type());
1722     else
1723     {
1724         value_comp() = _VSTD::move(__t.value_comp());
1725         const_iterator __e = end();
1726         if (size() != 0)
1727         {
1728             __node_pointer __cache = __detach();
1729 #ifndef _LIBCPP_NO_EXCEPTIONS
1730             try
1731             {
1732 #endif  // _LIBCPP_NO_EXCEPTIONS
1733                 while (__cache != nullptr && __t.size() != 0)
1734                 {
1735                     __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
1736                     __node_pointer __next = __detach(__cache);
1737                     __node_insert_multi(__cache);
1738                     __cache = __next;
1739                 }
1740 #ifndef _LIBCPP_NO_EXCEPTIONS
1741             }
1742             catch (...)
1743             {
1744                 while (__cache->__parent_ != nullptr)
1745                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1746                 destroy(__cache);
1747                 throw;
1748             }
1749 #endif  // _LIBCPP_NO_EXCEPTIONS
1750             if (__cache != nullptr)
1751             {
1752                 while (__cache->__parent_ != nullptr)
1753                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1754                 destroy(__cache);
1755             }
1756         }
1757         while (__t.size() != 0)
1758             __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_));
1759     }
1760 }
1761
1762 template <class _Tp, class _Compare, class _Allocator>
1763 __tree<_Tp, _Compare, _Allocator>&
1764 __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1765     _NOEXCEPT_(
1766         __node_traits::propagate_on_container_move_assignment::value &&
1767         is_nothrow_move_assignable<value_compare>::value &&
1768         is_nothrow_move_assignable<__node_allocator>::value)
1769
1770 {
1771     __move_assign(__t, integral_constant<bool,
1772                   __node_traits::propagate_on_container_move_assignment::value>());
1773     return *this;
1774 }
1775
1776 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1777
1778 template <class _Tp, class _Compare, class _Allocator>
1779 __tree<_Tp, _Compare, _Allocator>::~__tree()
1780 {
1781     static_assert((is_copy_constructible<value_compare>::value),
1782                  "Comparator must be copy-constructible.");
1783     destroy(__root());
1784 }
1785
1786 template <class _Tp, class _Compare, class _Allocator>
1787 void
1788 __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
1789 {
1790     if (__nd != nullptr)
1791     {
1792         destroy(static_cast<__node_pointer>(__nd->__left_));
1793         destroy(static_cast<__node_pointer>(__nd->__right_));
1794         __node_allocator& __na = __node_alloc();
1795         __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_));
1796         __node_traits::deallocate(__na, __nd, 1);
1797     }
1798 }
1799
1800 template <class _Tp, class _Compare, class _Allocator>
1801 void
1802 __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1803 #if _LIBCPP_STD_VER <= 11
1804         _NOEXCEPT_(
1805             __is_nothrow_swappable<value_compare>::value
1806             && (!__node_traits::propagate_on_container_swap::value ||
1807                  __is_nothrow_swappable<__node_allocator>::value)
1808             )
1809 #else
1810         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value)
1811 #endif
1812 {
1813     using _VSTD::swap;
1814     swap(__begin_node_, __t.__begin_node_);
1815     swap(__pair1_.first(), __t.__pair1_.first());
1816     __swap_allocator(__node_alloc(), __t.__node_alloc());
1817     __pair3_.swap(__t.__pair3_);
1818     if (size() == 0)
1819         __begin_node() = __end_node();
1820     else
1821         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1822     if (__t.size() == 0)
1823         __t.__begin_node() = __t.__end_node();
1824     else
1825         __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());
1826 }
1827
1828 template <class _Tp, class _Compare, class _Allocator>
1829 void
1830 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
1831 {
1832     destroy(__root());
1833     size() = 0;
1834     __begin_node() = __end_node();
1835     __end_node()->__left_ = nullptr;
1836 }
1837
1838 // Find lower_bound place to insert
1839 // Set __parent to parent of null leaf
1840 // Return reference to null leaf
1841 template <class _Tp, class _Compare, class _Allocator>
1842 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1843 __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent,
1844                                                    const key_type& __v)
1845 {
1846     __node_pointer __nd = __root();
1847     if (__nd != nullptr)
1848     {
1849         while (true)
1850         {
1851             if (value_comp()(__nd->__value_, __v))
1852             {
1853                 if (__nd->__right_ != nullptr)
1854                     __nd = static_cast<__node_pointer>(__nd->__right_);
1855                 else
1856                 {
1857                     __parent = static_cast<__parent_pointer>(__nd);
1858                     return __nd->__right_;
1859                 }
1860             }
1861             else
1862             {
1863                 if (__nd->__left_ != nullptr)
1864                     __nd = static_cast<__node_pointer>(__nd->__left_);
1865                 else
1866                 {
1867                     __parent = static_cast<__parent_pointer>(__nd);
1868                     return __parent->__left_;
1869                 }
1870             }
1871         }
1872     }
1873     __parent = static_cast<__parent_pointer>(__end_node());
1874     return __parent->__left_;
1875 }
1876
1877 // Find upper_bound place to insert
1878 // Set __parent to parent of null leaf
1879 // Return reference to null leaf
1880 template <class _Tp, class _Compare, class _Allocator>
1881 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1882 __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent,
1883                                                     const key_type& __v)
1884 {
1885     __node_pointer __nd = __root();
1886     if (__nd != nullptr)
1887     {
1888         while (true)
1889         {
1890             if (value_comp()(__v, __nd->__value_))
1891             {
1892                 if (__nd->__left_ != nullptr)
1893                     __nd = static_cast<__node_pointer>(__nd->__left_);
1894                 else
1895                 {
1896                     __parent = static_cast<__parent_pointer>(__nd);
1897                     return __parent->__left_;
1898                 }
1899             }
1900             else
1901             {
1902                 if (__nd->__right_ != nullptr)
1903                     __nd = static_cast<__node_pointer>(__nd->__right_);
1904                 else
1905                 {
1906                     __parent = static_cast<__parent_pointer>(__nd);
1907                     return __nd->__right_;
1908                 }
1909             }
1910         }
1911     }
1912     __parent = static_cast<__parent_pointer>(__end_node());
1913     return __parent->__left_;
1914 }
1915
1916 // Find leaf place to insert closest to __hint
1917 // First check prior to __hint.
1918 // Next check after __hint.
1919 // Next do O(log N) search.
1920 // Set __parent to parent of null leaf
1921 // Return reference to null leaf
1922 template <class _Tp, class _Compare, class _Allocator>
1923 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1924 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
1925                                                __parent_pointer& __parent,
1926                                                const key_type& __v)
1927 {
1928     if (__hint == end() || !value_comp()(*__hint, __v))  // check before
1929     {
1930         // __v <= *__hint
1931         const_iterator __prior = __hint;
1932         if (__prior == begin() || !value_comp()(__v, *--__prior))
1933         {
1934             // *prev(__hint) <= __v <= *__hint
1935             if (__hint.__ptr_->__left_ == nullptr)
1936             {
1937                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
1938                 return __parent->__left_;
1939             }
1940             else
1941             {
1942                 __parent = static_cast<__parent_pointer>(__prior.__ptr_);
1943                 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
1944             }
1945         }
1946         // __v < *prev(__hint)
1947         return __find_leaf_high(__parent, __v);
1948     }
1949     // else __v > *__hint
1950     return __find_leaf_low(__parent, __v);
1951 }
1952
1953 // Find place to insert if __v doesn't exist
1954 // Set __parent to parent of null leaf
1955 // Return reference to null leaf
1956 // If __v exists, set parent to node of __v and return reference to node of __v
1957 template <class _Tp, class _Compare, class _Allocator>
1958 template <class _Key>
1959 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1960 __tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent,
1961                                                 const _Key& __v)
1962 {
1963     __node_pointer __nd = __root();
1964     __node_base_pointer* __nd_ptr = __root_ptr();
1965     if (__nd != nullptr)
1966     {
1967         while (true)
1968         {
1969             if (value_comp()(__v, __nd->__value_))
1970             {
1971                 if (__nd->__left_ != nullptr) {
1972                     __nd_ptr = _VSTD::addressof(__nd->__left_);
1973                     __nd = static_cast<__node_pointer>(__nd->__left_);
1974                 } else {
1975                     __parent = static_cast<__parent_pointer>(__nd);
1976                     return __parent->__left_;
1977                 }
1978             }
1979             else if (value_comp()(__nd->__value_, __v))
1980             {
1981                 if (__nd->__right_ != nullptr) {
1982                     __nd_ptr = _VSTD::addressof(__nd->__right_);
1983                     __nd = static_cast<__node_pointer>(__nd->__right_);
1984                 } else {
1985                     __parent = static_cast<__parent_pointer>(__nd);
1986                     return __nd->__right_;
1987                 }
1988             }
1989             else
1990             {
1991                 __parent = static_cast<__parent_pointer>(__nd);
1992                 return *__nd_ptr;
1993             }
1994         }
1995     }
1996     __parent = static_cast<__parent_pointer>(__end_node());
1997     return __parent->__left_;
1998 }
1999
2000 // Find place to insert if __v doesn't exist
2001 // First check prior to __hint.
2002 // Next check after __hint.
2003 // Next do O(log N) search.
2004 // Set __parent to parent of null leaf
2005 // Return reference to null leaf
2006 // If __v exists, set parent to node of __v and return reference to node of __v
2007 template <class _Tp, class _Compare, class _Allocator>
2008 template <class _Key>
2009 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
2010 __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
2011                                                 __parent_pointer& __parent,
2012                                                 __node_base_pointer& __dummy,
2013                                                 const _Key& __v)
2014 {
2015     if (__hint == end() || value_comp()(__v, *__hint))  // check before
2016     {
2017         // __v < *__hint
2018         const_iterator __prior = __hint;
2019         if (__prior == begin() || value_comp()(*--__prior, __v))
2020         {
2021             // *prev(__hint) < __v < *__hint
2022             if (__hint.__ptr_->__left_ == nullptr)
2023             {
2024                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2025                 return __parent->__left_;
2026             }
2027             else
2028             {
2029                 __parent = static_cast<__parent_pointer>(__prior.__ptr_);
2030                 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
2031             }
2032         }
2033         // __v <= *prev(__hint)
2034         return __find_equal(__parent, __v);
2035     }
2036     else if (value_comp()(*__hint, __v))  // check after
2037     {
2038         // *__hint < __v
2039         const_iterator __next = _VSTD::next(__hint);
2040         if (__next == end() || value_comp()(__v, *__next))
2041         {
2042             // *__hint < __v < *_VSTD::next(__hint)
2043             if (__hint.__get_np()->__right_ == nullptr)
2044             {
2045                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2046                 return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
2047             }
2048             else
2049             {
2050                 __parent = static_cast<__parent_pointer>(__next.__ptr_);
2051                 return __parent->__left_;
2052             }
2053         }
2054         // *next(__hint) <= __v
2055         return __find_equal(__parent, __v);
2056     }
2057     // else __v == *__hint
2058     __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2059     __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
2060     return __dummy;
2061 }
2062
2063 template <class _Tp, class _Compare, class _Allocator>
2064 void
2065 __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer     __parent,
2066                                                     __node_base_pointer& __child,
2067                                                     __node_base_pointer  __new_node)
2068 {
2069     __new_node->__left_   = nullptr;
2070     __new_node->__right_  = nullptr;
2071     __new_node->__parent_ = __parent;
2072     // __new_node->__is_black_ is initialized in __tree_balance_after_insert
2073     __child = __new_node;
2074     if (__begin_node()->__left_ != nullptr)
2075         __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
2076     __tree_balance_after_insert(__end_node()->__left_, __child);
2077     ++size();
2078 }
2079
2080 #ifndef _LIBCPP_CXX03_LANG
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 #else
2086 template <class _Tp, class _Compare, class _Allocator>
2087 template <class _Key, class _Args>
2088 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2089 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
2090 #endif
2091 {
2092     __parent_pointer __parent;
2093     __node_base_pointer& __child = __find_equal(__parent, __k);
2094     __node_pointer __r = static_cast<__node_pointer>(__child);
2095     bool __inserted = false;
2096     if (__child == nullptr)
2097     {
2098 #ifndef _LIBCPP_CXX03_LANG
2099         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2100 #else
2101         __node_holder __h = __construct_node(__args);
2102 #endif
2103         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2104         __r = __h.release();
2105         __inserted = true;
2106     }
2107     return pair<iterator, bool>(iterator(__r), __inserted);
2108 }
2109
2110
2111 #ifndef _LIBCPP_CXX03_LANG
2112 template <class _Tp, class _Compare, class _Allocator>
2113 template <class _Key, class... _Args>
2114 typename __tree<_Tp, _Compare, _Allocator>::iterator
2115 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
2116     const_iterator __p, _Key const& __k, _Args&&... __args)
2117 #else
2118 template <class _Tp, class _Compare, class _Allocator>
2119 template <class _Key, class _Args>
2120 typename __tree<_Tp, _Compare, _Allocator>::iterator
2121 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
2122     const_iterator __p, _Key const& __k, _Args& __args)
2123 #endif
2124 {
2125     __parent_pointer __parent;
2126     __node_base_pointer __dummy;
2127     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
2128     __node_pointer __r = static_cast<__node_pointer>(__child);
2129     if (__child == nullptr)
2130     {
2131 #ifndef _LIBCPP_CXX03_LANG
2132         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2133 #else
2134         __node_holder __h = __construct_node(__args);
2135 #endif
2136         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2137         __r = __h.release();
2138     }
2139     return iterator(__r);
2140 }
2141
2142
2143 #ifndef _LIBCPP_CXX03_LANG
2144
2145 template <class _Tp, class _Compare, class _Allocator>
2146 template <class ..._Args>
2147 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2148 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
2149 {
2150     static_assert(!__is_tree_value_type<_Args...>::value,
2151                   "Cannot construct from __value_type");
2152     __node_allocator& __na = __node_alloc();
2153     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2154     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
2155     __h.get_deleter().__value_constructed = true;
2156     return __h;
2157 }
2158
2159
2160 template <class _Tp, class _Compare, class _Allocator>
2161 template <class... _Args>
2162 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2163 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
2164 {
2165     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2166     __parent_pointer __parent;
2167     __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
2168     __node_pointer __r = static_cast<__node_pointer>(__child);
2169     bool __inserted = false;
2170     if (__child == nullptr)
2171     {
2172         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2173         __r = __h.release();
2174         __inserted = true;
2175     }
2176     return pair<iterator, bool>(iterator(__r), __inserted);
2177 }
2178
2179 template <class _Tp, class _Compare, class _Allocator>
2180 template <class... _Args>
2181 typename __tree<_Tp, _Compare, _Allocator>::iterator
2182 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
2183 {
2184     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2185     __parent_pointer __parent;
2186     __node_base_pointer __dummy;
2187     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
2188     __node_pointer __r = static_cast<__node_pointer>(__child);
2189     if (__child == nullptr)
2190     {
2191         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2192         __r = __h.release();
2193     }
2194     return iterator(__r);
2195 }
2196
2197 template <class _Tp, class _Compare, class _Allocator>
2198 template <class... _Args>
2199 typename __tree<_Tp, _Compare, _Allocator>::iterator
2200 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
2201 {
2202     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2203     __parent_pointer __parent;
2204     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));
2205     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2206     return iterator(static_cast<__node_pointer>(__h.release()));
2207 }
2208
2209 template <class _Tp, class _Compare, class _Allocator>
2210 template <class... _Args>
2211 typename __tree<_Tp, _Compare, _Allocator>::iterator
2212 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
2213                                                         _Args&&... __args)
2214 {
2215     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2216     __parent_pointer __parent;
2217     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));
2218     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2219     return iterator(static_cast<__node_pointer>(__h.release()));
2220 }
2221
2222
2223 #else  // _LIBCPP_CXX03_LANG
2224
2225 template <class _Tp, class _Compare, class _Allocator>
2226 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2227 __tree<_Tp, _Compare, _Allocator>::__construct_node(const __container_value_type& __v)
2228 {
2229     __node_allocator& __na = __node_alloc();
2230     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2231     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
2232     __h.get_deleter().__value_constructed = true;
2233     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
2234 }
2235
2236 #endif  // _LIBCPP_CXX03_LANG
2237
2238 #ifdef _LIBCPP_CXX03_LANG
2239 template <class _Tp, class _Compare, class _Allocator>
2240 typename __tree<_Tp, _Compare, _Allocator>::iterator
2241 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v)
2242 {
2243     __parent_pointer __parent;
2244     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__v));
2245     __node_holder __h = __construct_node(__v);
2246     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2247     return iterator(__h.release());
2248 }
2249
2250 template <class _Tp, class _Compare, class _Allocator>
2251 typename __tree<_Tp, _Compare, _Allocator>::iterator
2252 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v)
2253 {
2254     __parent_pointer __parent;
2255     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__v));
2256     __node_holder __h = __construct_node(__v);
2257     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2258     return iterator(__h.release());
2259 }
2260 #endif
2261
2262 template <class _Tp, class _Compare, class _Allocator>
2263 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2264 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
2265 {
2266     __parent_pointer __parent;
2267     __node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
2268     __node_pointer __r = static_cast<__node_pointer>(__child);
2269     bool __inserted = false;
2270     if (__child == nullptr)
2271     {
2272         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2273         __r = __nd;
2274         __inserted = true;
2275     }
2276     return pair<iterator, bool>(iterator(__r), __inserted);
2277 }
2278
2279 template <class _Tp, class _Compare, class _Allocator>
2280 typename __tree<_Tp, _Compare, _Allocator>::iterator
2281 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
2282                                                         __node_pointer __nd)
2283 {
2284     __parent_pointer __parent;
2285     __node_base_pointer __dummy;
2286     __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
2287     __node_pointer __r = static_cast<__node_pointer>(__child);
2288     if (__child == nullptr)
2289     {
2290         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2291         __r = __nd;
2292     }
2293     return iterator(__r);
2294 }
2295
2296 template <class _Tp, class _Compare, class _Allocator>
2297 typename __tree<_Tp, _Compare, _Allocator>::iterator
2298 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
2299 {
2300     __parent_pointer __parent;
2301     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));
2302     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2303     return iterator(__nd);
2304 }
2305
2306 template <class _Tp, class _Compare, class _Allocator>
2307 typename __tree<_Tp, _Compare, _Allocator>::iterator
2308 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
2309                                                        __node_pointer __nd)
2310 {
2311     __parent_pointer __parent;
2312     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
2313     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2314     return iterator(__nd);
2315 }
2316
2317 template <class _Tp, class _Compare, class _Allocator>
2318 typename __tree<_Tp, _Compare, _Allocator>::iterator
2319 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
2320 {
2321     __node_pointer __np = __p.__get_np();
2322     iterator __r(__p.__ptr_);
2323     ++__r;
2324     if (__begin_node() == __p.__ptr_)
2325         __begin_node() = __r.__ptr_;
2326     --size();
2327     __node_allocator& __na = __node_alloc();
2328     __tree_remove(__end_node()->__left_,
2329                   static_cast<__node_base_pointer>(__np));
2330     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
2331         const_cast<__node_value_type&>(*__p)));
2332     __node_traits::deallocate(__na, __np, 1);
2333     return __r;
2334 }
2335
2336 template <class _Tp, class _Compare, class _Allocator>
2337 typename __tree<_Tp, _Compare, _Allocator>::iterator
2338 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
2339 {
2340     while (__f != __l)
2341         __f = erase(__f);
2342     return iterator(__l.__ptr_);
2343 }
2344
2345 template <class _Tp, class _Compare, class _Allocator>
2346 template <class _Key>
2347 typename __tree<_Tp, _Compare, _Allocator>::size_type
2348 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
2349 {
2350     iterator __i = find(__k);
2351     if (__i == end())
2352         return 0;
2353     erase(__i);
2354     return 1;
2355 }
2356
2357 template <class _Tp, class _Compare, class _Allocator>
2358 template <class _Key>
2359 typename __tree<_Tp, _Compare, _Allocator>::size_type
2360 __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
2361 {
2362     pair<iterator, iterator> __p = __equal_range_multi(__k);
2363     size_type __r = 0;
2364     for (; __p.first != __p.second; ++__r)
2365         __p.first = erase(__p.first);
2366     return __r;
2367 }
2368
2369 template <class _Tp, class _Compare, class _Allocator>
2370 template <class _Key>
2371 typename __tree<_Tp, _Compare, _Allocator>::iterator
2372 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
2373 {
2374     iterator __p = __lower_bound(__v, __root(), __end_node());
2375     if (__p != end() && !value_comp()(__v, *__p))
2376         return __p;
2377     return end();
2378 }
2379
2380 template <class _Tp, class _Compare, class _Allocator>
2381 template <class _Key>
2382 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2383 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
2384 {
2385     const_iterator __p = __lower_bound(__v, __root(), __end_node());
2386     if (__p != end() && !value_comp()(__v, *__p))
2387         return __p;
2388     return end();
2389 }
2390
2391 template <class _Tp, class _Compare, class _Allocator>
2392 template <class _Key>
2393 typename __tree<_Tp, _Compare, _Allocator>::size_type
2394 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
2395 {
2396     __node_pointer __rt = __root();
2397     while (__rt != nullptr)
2398     {
2399         if (value_comp()(__k, __rt->__value_))
2400         {
2401             __rt = static_cast<__node_pointer>(__rt->__left_);
2402         }
2403         else if (value_comp()(__rt->__value_, __k))
2404             __rt = static_cast<__node_pointer>(__rt->__right_);
2405         else
2406             return 1;
2407     }
2408     return 0;
2409 }
2410
2411 template <class _Tp, class _Compare, class _Allocator>
2412 template <class _Key>
2413 typename __tree<_Tp, _Compare, _Allocator>::size_type
2414 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
2415 {
2416     __iter_pointer __result = __end_node();
2417     __node_pointer __rt = __root();
2418     while (__rt != nullptr)
2419     {
2420         if (value_comp()(__k, __rt->__value_))
2421         {
2422             __result = static_cast<__iter_pointer>(__rt);
2423             __rt = static_cast<__node_pointer>(__rt->__left_);
2424         }
2425         else if (value_comp()(__rt->__value_, __k))
2426             __rt = static_cast<__node_pointer>(__rt->__right_);
2427         else
2428             return _VSTD::distance(
2429                 __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2430                 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)
2431             );
2432     }
2433     return 0;
2434 }
2435
2436 template <class _Tp, class _Compare, class _Allocator>
2437 template <class _Key>
2438 typename __tree<_Tp, _Compare, _Allocator>::iterator
2439 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2440                                                  __node_pointer __root,
2441                                                  __iter_pointer __result)
2442 {
2443     while (__root != nullptr)
2444     {
2445         if (!value_comp()(__root->__value_, __v))
2446         {
2447             __result = static_cast<__iter_pointer>(__root);
2448             __root = static_cast<__node_pointer>(__root->__left_);
2449         }
2450         else
2451             __root = static_cast<__node_pointer>(__root->__right_);
2452     }
2453     return iterator(__result);
2454 }
2455
2456 template <class _Tp, class _Compare, class _Allocator>
2457 template <class _Key>
2458 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2459 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2460                                                  __node_pointer __root,
2461                                                  __iter_pointer __result) const
2462 {
2463     while (__root != nullptr)
2464     {
2465         if (!value_comp()(__root->__value_, __v))
2466         {
2467             __result = static_cast<__iter_pointer>(__root);
2468             __root = static_cast<__node_pointer>(__root->__left_);
2469         }
2470         else
2471             __root = static_cast<__node_pointer>(__root->__right_);
2472     }
2473     return const_iterator(__result);
2474 }
2475
2476 template <class _Tp, class _Compare, class _Allocator>
2477 template <class _Key>
2478 typename __tree<_Tp, _Compare, _Allocator>::iterator
2479 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2480                                                  __node_pointer __root,
2481                                                  __iter_pointer __result)
2482 {
2483     while (__root != nullptr)
2484     {
2485         if (value_comp()(__v, __root->__value_))
2486         {
2487             __result = static_cast<__iter_pointer>(__root);
2488             __root = static_cast<__node_pointer>(__root->__left_);
2489         }
2490         else
2491             __root = static_cast<__node_pointer>(__root->__right_);
2492     }
2493     return iterator(__result);
2494 }
2495
2496 template <class _Tp, class _Compare, class _Allocator>
2497 template <class _Key>
2498 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2499 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2500                                                  __node_pointer __root,
2501                                                  __iter_pointer __result) const
2502 {
2503     while (__root != nullptr)
2504     {
2505         if (value_comp()(__v, __root->__value_))
2506         {
2507             __result = static_cast<__iter_pointer>(__root);
2508             __root = static_cast<__node_pointer>(__root->__left_);
2509         }
2510         else
2511             __root = static_cast<__node_pointer>(__root->__right_);
2512     }
2513     return const_iterator(__result);
2514 }
2515
2516 template <class _Tp, class _Compare, class _Allocator>
2517 template <class _Key>
2518 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2519      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2520 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
2521 {
2522     typedef pair<iterator, iterator> _Pp;
2523     __iter_pointer __result = __end_node();
2524     __node_pointer __rt = __root();
2525     while (__rt != nullptr)
2526     {
2527         if (value_comp()(__k, __rt->__value_))
2528         {
2529             __result = static_cast<__iter_pointer>(__rt);
2530             __rt = static_cast<__node_pointer>(__rt->__left_);
2531         }
2532         else if (value_comp()(__rt->__value_, __k))
2533             __rt = static_cast<__node_pointer>(__rt->__right_);
2534         else
2535             return _Pp(iterator(__rt),
2536                       iterator(
2537                           __rt->__right_ != nullptr ?
2538                               static_cast<__iter_pointer>(__tree_min(__rt->__right_))
2539                             : __result));
2540     }
2541     return _Pp(iterator(__result), iterator(__result));
2542 }
2543
2544 template <class _Tp, class _Compare, class _Allocator>
2545 template <class _Key>
2546 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2547      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2548 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
2549 {
2550     typedef pair<const_iterator, const_iterator> _Pp;
2551     __iter_pointer __result = __end_node();
2552     __node_pointer __rt = __root();
2553     while (__rt != nullptr)
2554     {
2555         if (value_comp()(__k, __rt->__value_))
2556         {
2557             __result = static_cast<__iter_pointer>(__rt);
2558             __rt = static_cast<__node_pointer>(__rt->__left_);
2559         }
2560         else if (value_comp()(__rt->__value_, __k))
2561             __rt = static_cast<__node_pointer>(__rt->__right_);
2562         else
2563             return _Pp(const_iterator(__rt),
2564                       const_iterator(
2565                           __rt->__right_ != nullptr ?
2566                               static_cast<__iter_pointer>(__tree_min(__rt->__right_))
2567                             : __result));
2568     }
2569     return _Pp(const_iterator(__result), const_iterator(__result));
2570 }
2571
2572 template <class _Tp, class _Compare, class _Allocator>
2573 template <class _Key>
2574 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2575      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2576 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
2577 {
2578     typedef pair<iterator, iterator> _Pp;
2579     __iter_pointer __result = __end_node();
2580     __node_pointer __rt = __root();
2581     while (__rt != nullptr)
2582     {
2583         if (value_comp()(__k, __rt->__value_))
2584         {
2585             __result = static_cast<__iter_pointer>(__rt);
2586             __rt = static_cast<__node_pointer>(__rt->__left_);
2587         }
2588         else if (value_comp()(__rt->__value_, __k))
2589             __rt = static_cast<__node_pointer>(__rt->__right_);
2590         else
2591             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2592                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2593     }
2594     return _Pp(iterator(__result), iterator(__result));
2595 }
2596
2597 template <class _Tp, class _Compare, class _Allocator>
2598 template <class _Key>
2599 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2600      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2601 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
2602 {
2603     typedef pair<const_iterator, const_iterator> _Pp;
2604     __iter_pointer __result = __end_node();
2605     __node_pointer __rt = __root();
2606     while (__rt != nullptr)
2607     {
2608         if (value_comp()(__k, __rt->__value_))
2609         {
2610             __result = static_cast<__iter_pointer>(__rt);
2611             __rt = static_cast<__node_pointer>(__rt->__left_);
2612         }
2613         else if (value_comp()(__rt->__value_, __k))
2614             __rt = static_cast<__node_pointer>(__rt->__right_);
2615         else
2616             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2617                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2618     }
2619     return _Pp(const_iterator(__result), const_iterator(__result));
2620 }
2621
2622 template <class _Tp, class _Compare, class _Allocator>
2623 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2624 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2625 {
2626     __node_pointer __np = __p.__get_np();
2627     if (__begin_node() == __p.__ptr_)
2628     {
2629         if (__np->__right_ != nullptr)
2630             __begin_node() = static_cast<__iter_pointer>(__np->__right_);
2631         else
2632             __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
2633     }
2634     --size();
2635     __tree_remove(__end_node()->__left_,
2636                   static_cast<__node_base_pointer>(__np));
2637     return __node_holder(__np, _Dp(__node_alloc(), true));
2638 }
2639
2640 template <class _Tp, class _Compare, class _Allocator>
2641 inline _LIBCPP_INLINE_VISIBILITY
2642 void
2643 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2644      __tree<_Tp, _Compare, _Allocator>& __y)
2645     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2646 {
2647     __x.swap(__y);
2648 }
2649
2650 _LIBCPP_END_NAMESPACE_STD
2651
2652 #endif  // _LIBCPP___TREE