contrib/libc++/include/__tree

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP___TREE
  12 #define _LIBCPP___TREE
  13
  14 #include <__config>
  15 #include <iterator>
  16 #include <memory>
  17 #include <stdexcept>
  18 #include <algorithm>
  19
  20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  21 #pragma GCC system_header
  22 #endif
  23
  24 _LIBCPP_BEGIN_NAMESPACE_STD
  25
  26 template <class _Tp, class _Compare, class _Allocator> class __tree;
  27 template <class _Tp, class _NodePtr, class _DiffType>
  28     class _LIBCPP_TEMPLATE_VIS __tree_iterator;
  29 template <class _Tp, class _ConstNodePtr, class _DiffType>
  30     class _LIBCPP_TEMPLATE_VIS __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_TEMPLATE_VIS __map_iterator;
  46 template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __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_TEMPLATE_VIS __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_TEMPLATE_VIS __tree_const_iterator;
 865     template <class> friend class _LIBCPP_TEMPLATE_VIS __map_iterator;
 866     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
 867     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 868     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
 869     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
 870 };
 871
 872 template <class _Tp, class _NodePtr, class _DiffType>
 873 class _LIBCPP_TEMPLATE_VIS __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_TEMPLATE_VIS map;
 951     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
 952     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
 953     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
 954     template <class> friend class _LIBCPP_TEMPLATE_VIS __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     // FIXME: Make this function const qualified. Unfortunetly doing so
1401     // breaks existing code which uses non-const callable comparators.
1402     template <class _Key>
1403     __node_base_pointer&
1404         __find_equal(__parent_pointer& __parent, const _Key& __v);
1405     template <class _Key>
1406     _LIBCPP_INLINE_VISIBILITY __node_base_pointer&
1407     __find_equal(__parent_pointer& __parent, const _Key& __v) const {
1408       return const_cast<__tree*>(this)->__find_equal(__parent, __v);
1409     }
1410     template <class _Key>
1411     __node_base_pointer&
1412         __find_equal(const_iterator __hint, __parent_pointer& __parent,
1413                      __node_base_pointer& __dummy,
1414                      const _Key& __v);
1415
1416 #ifndef _LIBCPP_CXX03_LANG
1417     template <class ..._Args>
1418     __node_holder __construct_node(_Args&& ...__args);
1419 #else
1420     __node_holder __construct_node(const __container_value_type& __v);
1421 #endif
1422
1423     void destroy(__node_pointer __nd) _NOEXCEPT;
1424
1425     _LIBCPP_INLINE_VISIBILITY
1426     void __copy_assign_alloc(const __tree& __t)
1427         {__copy_assign_alloc(__t, integral_constant<bool,
1428              __node_traits::propagate_on_container_copy_assignment::value>());}
1429
1430     _LIBCPP_INLINE_VISIBILITY
1431     void __copy_assign_alloc(const __tree& __t, true_type)
1432         {
1433         if (__node_alloc() != __t.__node_alloc())
1434                 clear();
1435         __node_alloc() = __t.__node_alloc();
1436         }
1437     _LIBCPP_INLINE_VISIBILITY
1438     void __copy_assign_alloc(const __tree&, false_type) {}
1439
1440     void __move_assign(__tree& __t, false_type);
1441     void __move_assign(__tree& __t, true_type)
1442         _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1443                    is_nothrow_move_assignable<__node_allocator>::value);
1444
1445     _LIBCPP_INLINE_VISIBILITY
1446     void __move_assign_alloc(__tree& __t)
1447         _NOEXCEPT_(
1448             !__node_traits::propagate_on_container_move_assignment::value ||
1449             is_nothrow_move_assignable<__node_allocator>::value)
1450         {__move_assign_alloc(__t, integral_constant<bool,
1451              __node_traits::propagate_on_container_move_assignment::value>());}
1452
1453     _LIBCPP_INLINE_VISIBILITY
1454     void __move_assign_alloc(__tree& __t, true_type)
1455         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1456         {__node_alloc() = _VSTD::move(__t.__node_alloc());}
1457     _LIBCPP_INLINE_VISIBILITY
1458     void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}
1459
1460     __node_pointer __detach();
1461     static __node_pointer __detach(__node_pointer);
1462
1463     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
1464     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
1465 };
1466
1467 template <class _Tp, class _Compare, class _Allocator>
1468 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
1469         _NOEXCEPT_(
1470             is_nothrow_default_constructible<__node_allocator>::value &&
1471             is_nothrow_copy_constructible<value_compare>::value)
1472     : __pair3_(0, __comp)
1473 {
1474     __begin_node() = __end_node();
1475 }
1476
1477 template <class _Tp, class _Compare, class _Allocator>
1478 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1479     : __begin_node_(__iter_pointer()),
1480       __pair1_(__node_allocator(__a)),
1481       __pair3_(0)
1482 {
1483     __begin_node() = __end_node();
1484 }
1485
1486 template <class _Tp, class _Compare, class _Allocator>
1487 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
1488                                            const allocator_type& __a)
1489     : __begin_node_(__iter_pointer()),
1490       __pair1_(__node_allocator(__a)),
1491       __pair3_(0, __comp)
1492 {
1493     __begin_node() = __end_node();
1494 }
1495
1496 // Precondition:  size() != 0
1497 template <class _Tp, class _Compare, class _Allocator>
1498 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1499 __tree<_Tp, _Compare, _Allocator>::__detach()
1500 {
1501     __node_pointer __cache = static_cast<__node_pointer>(__begin_node());
1502     __begin_node() = __end_node();
1503     __end_node()->__left_->__parent_ = nullptr;
1504     __end_node()->__left_ = nullptr;
1505     size() = 0;
1506     // __cache->__left_ == nullptr
1507     if (__cache->__right_ != nullptr)
1508         __cache = static_cast<__node_pointer>(__cache->__right_);
1509     // __cache->__left_ == nullptr
1510     // __cache->__right_ == nullptr
1511     return __cache;
1512 }
1513
1514 // Precondition:  __cache != nullptr
1515 //    __cache->left_ == nullptr
1516 //    __cache->right_ == nullptr
1517 //    This is no longer a red-black tree
1518 template <class _Tp, class _Compare, class _Allocator>
1519 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1520 __tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache)
1521 {
1522     if (__cache->__parent_ == nullptr)
1523         return nullptr;
1524     if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1525     {
1526         __cache->__parent_->__left_ = nullptr;
1527         __cache = static_cast<__node_pointer>(__cache->__parent_);
1528         if (__cache->__right_ == nullptr)
1529             return __cache;
1530         return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
1531     }
1532     // __cache is right child
1533     __cache->__parent_unsafe()->__right_ = nullptr;
1534     __cache = static_cast<__node_pointer>(__cache->__parent_);
1535     if (__cache->__left_ == nullptr)
1536         return __cache;
1537     return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
1538 }
1539
1540 template <class _Tp, class _Compare, class _Allocator>
1541 __tree<_Tp, _Compare, _Allocator>&
1542 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
1543 {
1544     if (this != &__t)
1545     {
1546         value_comp() = __t.value_comp();
1547         __copy_assign_alloc(__t);
1548         __assign_multi(__t.begin(), __t.end());
1549     }
1550     return *this;
1551 }
1552
1553 template <class _Tp, class _Compare, class _Allocator>
1554 template <class _InputIterator>
1555 void
1556 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last)
1557 {
1558     typedef iterator_traits<_InputIterator> _ITraits;
1559     typedef typename _ITraits::value_type _ItValueType;
1560     static_assert((is_same<_ItValueType, __container_value_type>::value),
1561                   "__assign_unique may only be called with the containers value type");
1562
1563     if (size() != 0)
1564     {
1565         __node_pointer __cache = __detach();
1566 #ifndef _LIBCPP_NO_EXCEPTIONS
1567         try
1568         {
1569 #endif  // _LIBCPP_NO_EXCEPTIONS
1570             for (; __cache != nullptr && __first != __last; ++__first)
1571             {
1572                 __cache->__value_ = *__first;
1573                 __node_pointer __next = __detach(__cache);
1574                 __node_insert_unique(__cache);
1575                 __cache = __next;
1576             }
1577 #ifndef _LIBCPP_NO_EXCEPTIONS
1578         }
1579         catch (...)
1580         {
1581             while (__cache->__parent_ != nullptr)
1582                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1583             destroy(__cache);
1584             throw;
1585         }
1586 #endif  // _LIBCPP_NO_EXCEPTIONS
1587         if (__cache != nullptr)
1588         {
1589             while (__cache->__parent_ != nullptr)
1590                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1591             destroy(__cache);
1592         }
1593     }
1594     for (; __first != __last; ++__first)
1595         __insert_unique(*__first);
1596 }
1597
1598 template <class _Tp, class _Compare, class _Allocator>
1599 template <class _InputIterator>
1600 void
1601 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
1602 {
1603     typedef iterator_traits<_InputIterator> _ITraits;
1604     typedef typename _ITraits::value_type _ItValueType;
1605     static_assert((is_same<_ItValueType, __container_value_type>::value ||
1606                   is_same<_ItValueType, __node_value_type>::value),
1607                   "__assign_multi may only be called with the containers value type"
1608                   " or the nodes value type");
1609     if (size() != 0)
1610     {
1611         __node_pointer __cache = __detach();
1612 #ifndef _LIBCPP_NO_EXCEPTIONS
1613         try
1614         {
1615 #endif  // _LIBCPP_NO_EXCEPTIONS
1616             for (; __cache != nullptr && __first != __last; ++__first)
1617             {
1618                 __cache->__value_ = *__first;
1619                 __node_pointer __next = __detach(__cache);
1620                 __node_insert_multi(__cache);
1621                 __cache = __next;
1622             }
1623 #ifndef _LIBCPP_NO_EXCEPTIONS
1624         }
1625         catch (...)
1626         {
1627             while (__cache->__parent_ != nullptr)
1628                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1629             destroy(__cache);
1630             throw;
1631         }
1632 #endif  // _LIBCPP_NO_EXCEPTIONS
1633         if (__cache != nullptr)
1634         {
1635             while (__cache->__parent_ != nullptr)
1636                 __cache = static_cast<__node_pointer>(__cache->__parent_);
1637             destroy(__cache);
1638         }
1639     }
1640     for (; __first != __last; ++__first)
1641         __insert_multi(_NodeTypes::__get_value(*__first));
1642 }
1643
1644 template <class _Tp, class _Compare, class _Allocator>
1645 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1646     : __begin_node_(__iter_pointer()),
1647       __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1648       __pair3_(0, __t.value_comp())
1649 {
1650     __begin_node() = __end_node();
1651 }
1652
1653 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1654
1655 template <class _Tp, class _Compare, class _Allocator>
1656 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
1657     _NOEXCEPT_(
1658         is_nothrow_move_constructible<__node_allocator>::value &&
1659         is_nothrow_move_constructible<value_compare>::value)
1660     : __begin_node_(_VSTD::move(__t.__begin_node_)),
1661       __pair1_(_VSTD::move(__t.__pair1_)),
1662       __pair3_(_VSTD::move(__t.__pair3_))
1663 {
1664     if (size() == 0)
1665         __begin_node() = __end_node();
1666     else
1667     {
1668         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1669         __t.__begin_node() = __t.__end_node();
1670         __t.__end_node()->__left_ = nullptr;
1671         __t.size() = 0;
1672     }
1673 }
1674
1675 template <class _Tp, class _Compare, class _Allocator>
1676 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1677     : __pair1_(__node_allocator(__a)),
1678       __pair3_(0, _VSTD::move(__t.value_comp()))
1679 {
1680     if (__a == __t.__alloc())
1681     {
1682         if (__t.size() == 0)
1683             __begin_node() = __end_node();
1684         else
1685         {
1686             __begin_node() = __t.__begin_node();
1687             __end_node()->__left_ = __t.__end_node()->__left_;
1688             __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1689             size() = __t.size();
1690             __t.__begin_node() = __t.__end_node();
1691             __t.__end_node()->__left_ = nullptr;
1692             __t.size() = 0;
1693         }
1694     }
1695     else
1696     {
1697         __begin_node() = __end_node();
1698     }
1699 }
1700
1701 template <class _Tp, class _Compare, class _Allocator>
1702 void
1703 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1704     _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1705                is_nothrow_move_assignable<__node_allocator>::value)
1706 {
1707     destroy(static_cast<__node_pointer>(__end_node()->__left_));
1708     __begin_node_ = __t.__begin_node_;
1709     __pair1_.first() = __t.__pair1_.first();
1710     __move_assign_alloc(__t);
1711     __pair3_ = _VSTD::move(__t.__pair3_);
1712     if (size() == 0)
1713         __begin_node() = __end_node();
1714     else
1715     {
1716         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1717         __t.__begin_node() = __t.__end_node();
1718         __t.__end_node()->__left_ = nullptr;
1719         __t.size() = 0;
1720     }
1721 }
1722
1723 template <class _Tp, class _Compare, class _Allocator>
1724 void
1725 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
1726 {
1727     if (__node_alloc() == __t.__node_alloc())
1728         __move_assign(__t, true_type());
1729     else
1730     {
1731         value_comp() = _VSTD::move(__t.value_comp());
1732         const_iterator __e = end();
1733         if (size() != 0)
1734         {
1735             __node_pointer __cache = __detach();
1736 #ifndef _LIBCPP_NO_EXCEPTIONS
1737             try
1738             {
1739 #endif  // _LIBCPP_NO_EXCEPTIONS
1740                 while (__cache != nullptr && __t.size() != 0)
1741                 {
1742                     __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
1743                     __node_pointer __next = __detach(__cache);
1744                     __node_insert_multi(__cache);
1745                     __cache = __next;
1746                 }
1747 #ifndef _LIBCPP_NO_EXCEPTIONS
1748             }
1749             catch (...)
1750             {
1751                 while (__cache->__parent_ != nullptr)
1752                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1753                 destroy(__cache);
1754                 throw;
1755             }
1756 #endif  // _LIBCPP_NO_EXCEPTIONS
1757             if (__cache != nullptr)
1758             {
1759                 while (__cache->__parent_ != nullptr)
1760                     __cache = static_cast<__node_pointer>(__cache->__parent_);
1761                 destroy(__cache);
1762             }
1763         }
1764         while (__t.size() != 0)
1765             __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_));
1766     }
1767 }
1768
1769 template <class _Tp, class _Compare, class _Allocator>
1770 __tree<_Tp, _Compare, _Allocator>&
1771 __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1772     _NOEXCEPT_(
1773         __node_traits::propagate_on_container_move_assignment::value &&
1774         is_nothrow_move_assignable<value_compare>::value &&
1775         is_nothrow_move_assignable<__node_allocator>::value)
1776
1777 {
1778     __move_assign(__t, integral_constant<bool,
1779                   __node_traits::propagate_on_container_move_assignment::value>());
1780     return *this;
1781 }
1782
1783 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1784
1785 template <class _Tp, class _Compare, class _Allocator>
1786 __tree<_Tp, _Compare, _Allocator>::~__tree()
1787 {
1788     static_assert((is_copy_constructible<value_compare>::value),
1789                  "Comparator must be copy-constructible.");
1790     destroy(__root());
1791 }
1792
1793 template <class _Tp, class _Compare, class _Allocator>
1794 void
1795 __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
1796 {
1797     if (__nd != nullptr)
1798     {
1799         destroy(static_cast<__node_pointer>(__nd->__left_));
1800         destroy(static_cast<__node_pointer>(__nd->__right_));
1801         __node_allocator& __na = __node_alloc();
1802         __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_));
1803         __node_traits::deallocate(__na, __nd, 1);
1804     }
1805 }
1806
1807 template <class _Tp, class _Compare, class _Allocator>
1808 void
1809 __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1810 #if _LIBCPP_STD_VER <= 11
1811         _NOEXCEPT_(
1812             __is_nothrow_swappable<value_compare>::value
1813             && (!__node_traits::propagate_on_container_swap::value ||
1814                  __is_nothrow_swappable<__node_allocator>::value)
1815             )
1816 #else
1817         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value)
1818 #endif
1819 {
1820     using _VSTD::swap;
1821     swap(__begin_node_, __t.__begin_node_);
1822     swap(__pair1_.first(), __t.__pair1_.first());
1823     __swap_allocator(__node_alloc(), __t.__node_alloc());
1824     __pair3_.swap(__t.__pair3_);
1825     if (size() == 0)
1826         __begin_node() = __end_node();
1827     else
1828         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1829     if (__t.size() == 0)
1830         __t.__begin_node() = __t.__end_node();
1831     else
1832         __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());
1833 }
1834
1835 template <class _Tp, class _Compare, class _Allocator>
1836 void
1837 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
1838 {
1839     destroy(__root());
1840     size() = 0;
1841     __begin_node() = __end_node();
1842     __end_node()->__left_ = nullptr;
1843 }
1844
1845 // Find lower_bound place to insert
1846 // Set __parent to parent of null leaf
1847 // Return reference to null leaf
1848 template <class _Tp, class _Compare, class _Allocator>
1849 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1850 __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent,
1851                                                    const key_type& __v)
1852 {
1853     __node_pointer __nd = __root();
1854     if (__nd != nullptr)
1855     {
1856         while (true)
1857         {
1858             if (value_comp()(__nd->__value_, __v))
1859             {
1860                 if (__nd->__right_ != nullptr)
1861                     __nd = static_cast<__node_pointer>(__nd->__right_);
1862                 else
1863                 {
1864                     __parent = static_cast<__parent_pointer>(__nd);
1865                     return __nd->__right_;
1866                 }
1867             }
1868             else
1869             {
1870                 if (__nd->__left_ != nullptr)
1871                     __nd = static_cast<__node_pointer>(__nd->__left_);
1872                 else
1873                 {
1874                     __parent = static_cast<__parent_pointer>(__nd);
1875                     return __parent->__left_;
1876                 }
1877             }
1878         }
1879     }
1880     __parent = static_cast<__parent_pointer>(__end_node());
1881     return __parent->__left_;
1882 }
1883
1884 // Find upper_bound place to insert
1885 // Set __parent to parent of null leaf
1886 // Return reference to null leaf
1887 template <class _Tp, class _Compare, class _Allocator>
1888 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1889 __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent,
1890                                                     const key_type& __v)
1891 {
1892     __node_pointer __nd = __root();
1893     if (__nd != nullptr)
1894     {
1895         while (true)
1896         {
1897             if (value_comp()(__v, __nd->__value_))
1898             {
1899                 if (__nd->__left_ != nullptr)
1900                     __nd = static_cast<__node_pointer>(__nd->__left_);
1901                 else
1902                 {
1903                     __parent = static_cast<__parent_pointer>(__nd);
1904                     return __parent->__left_;
1905                 }
1906             }
1907             else
1908             {
1909                 if (__nd->__right_ != nullptr)
1910                     __nd = static_cast<__node_pointer>(__nd->__right_);
1911                 else
1912                 {
1913                     __parent = static_cast<__parent_pointer>(__nd);
1914                     return __nd->__right_;
1915                 }
1916             }
1917         }
1918     }
1919     __parent = static_cast<__parent_pointer>(__end_node());
1920     return __parent->__left_;
1921 }
1922
1923 // Find leaf place to insert closest to __hint
1924 // First check prior to __hint.
1925 // Next check after __hint.
1926 // Next do O(log N) search.
1927 // Set __parent to parent of null leaf
1928 // Return reference to null leaf
1929 template <class _Tp, class _Compare, class _Allocator>
1930 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1931 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
1932                                                __parent_pointer& __parent,
1933                                                const key_type& __v)
1934 {
1935     if (__hint == end() || !value_comp()(*__hint, __v))  // check before
1936     {
1937         // __v <= *__hint
1938         const_iterator __prior = __hint;
1939         if (__prior == begin() || !value_comp()(__v, *--__prior))
1940         {
1941             // *prev(__hint) <= __v <= *__hint
1942             if (__hint.__ptr_->__left_ == nullptr)
1943             {
1944                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
1945                 return __parent->__left_;
1946             }
1947             else
1948             {
1949                 __parent = static_cast<__parent_pointer>(__prior.__ptr_);
1950                 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
1951             }
1952         }
1953         // __v < *prev(__hint)
1954         return __find_leaf_high(__parent, __v);
1955     }
1956     // else __v > *__hint
1957     return __find_leaf_low(__parent, __v);
1958 }
1959
1960 // Find place to insert if __v doesn't exist
1961 // Set __parent to parent of null leaf
1962 // Return reference to null leaf
1963 // If __v exists, set parent to node of __v and return reference to node of __v
1964 template <class _Tp, class _Compare, class _Allocator>
1965 template <class _Key>
1966 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1967 __tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent,
1968                                                 const _Key& __v)
1969 {
1970     __node_pointer __nd = __root();
1971     __node_base_pointer* __nd_ptr = __root_ptr();
1972     if (__nd != nullptr)
1973     {
1974         while (true)
1975         {
1976             if (value_comp()(__v, __nd->__value_))
1977             {
1978                 if (__nd->__left_ != nullptr) {
1979                     __nd_ptr = _VSTD::addressof(__nd->__left_);
1980                     __nd = static_cast<__node_pointer>(__nd->__left_);
1981                 } else {
1982                     __parent = static_cast<__parent_pointer>(__nd);
1983                     return __parent->__left_;
1984                 }
1985             }
1986             else if (value_comp()(__nd->__value_, __v))
1987             {
1988                 if (__nd->__right_ != nullptr) {
1989                     __nd_ptr = _VSTD::addressof(__nd->__right_);
1990                     __nd = static_cast<__node_pointer>(__nd->__right_);
1991                 } else {
1992                     __parent = static_cast<__parent_pointer>(__nd);
1993                     return __nd->__right_;
1994                 }
1995             }
1996             else
1997             {
1998                 __parent = static_cast<__parent_pointer>(__nd);
1999                 return *__nd_ptr;
2000             }
2001         }
2002     }
2003     __parent = static_cast<__parent_pointer>(__end_node());
2004     return __parent->__left_;
2005 }
2006
2007 // Find place to insert if __v doesn't exist
2008 // First check prior to __hint.
2009 // Next check after __hint.
2010 // Next do O(log N) search.
2011 // Set __parent to parent of null leaf
2012 // Return reference to null leaf
2013 // If __v exists, set parent to node of __v and return reference to node of __v
2014 template <class _Tp, class _Compare, class _Allocator>
2015 template <class _Key>
2016 typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
2017 __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
2018                                                 __parent_pointer& __parent,
2019                                                 __node_base_pointer& __dummy,
2020                                                 const _Key& __v)
2021 {
2022     if (__hint == end() || value_comp()(__v, *__hint))  // check before
2023     {
2024         // __v < *__hint
2025         const_iterator __prior = __hint;
2026         if (__prior == begin() || value_comp()(*--__prior, __v))
2027         {
2028             // *prev(__hint) < __v < *__hint
2029             if (__hint.__ptr_->__left_ == nullptr)
2030             {
2031                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2032                 return __parent->__left_;
2033             }
2034             else
2035             {
2036                 __parent = static_cast<__parent_pointer>(__prior.__ptr_);
2037                 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
2038             }
2039         }
2040         // __v <= *prev(__hint)
2041         return __find_equal(__parent, __v);
2042     }
2043     else if (value_comp()(*__hint, __v))  // check after
2044     {
2045         // *__hint < __v
2046         const_iterator __next = _VSTD::next(__hint);
2047         if (__next == end() || value_comp()(__v, *__next))
2048         {
2049             // *__hint < __v < *_VSTD::next(__hint)
2050             if (__hint.__get_np()->__right_ == nullptr)
2051             {
2052                 __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2053                 return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
2054             }
2055             else
2056             {
2057                 __parent = static_cast<__parent_pointer>(__next.__ptr_);
2058                 return __parent->__left_;
2059             }
2060         }
2061         // *next(__hint) <= __v
2062         return __find_equal(__parent, __v);
2063     }
2064     // else __v == *__hint
2065     __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2066     __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
2067     return __dummy;
2068 }
2069
2070 template <class _Tp, class _Compare, class _Allocator>
2071 void
2072 __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer     __parent,
2073                                                     __node_base_pointer& __child,
2074                                                     __node_base_pointer  __new_node)
2075 {
2076     __new_node->__left_   = nullptr;
2077     __new_node->__right_  = nullptr;
2078     __new_node->__parent_ = __parent;
2079     // __new_node->__is_black_ is initialized in __tree_balance_after_insert
2080     __child = __new_node;
2081     if (__begin_node()->__left_ != nullptr)
2082         __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
2083     __tree_balance_after_insert(__end_node()->__left_, __child);
2084     ++size();
2085 }
2086
2087 #ifndef _LIBCPP_CXX03_LANG
2088 template <class _Tp, class _Compare, class _Allocator>
2089 template <class _Key, class... _Args>
2090 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2091 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
2092 #else
2093 template <class _Tp, class _Compare, class _Allocator>
2094 template <class _Key, class _Args>
2095 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2096 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
2097 #endif
2098 {
2099     __parent_pointer __parent;
2100     __node_base_pointer& __child = __find_equal(__parent, __k);
2101     __node_pointer __r = static_cast<__node_pointer>(__child);
2102     bool __inserted = false;
2103     if (__child == nullptr)
2104     {
2105 #ifndef _LIBCPP_CXX03_LANG
2106         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2107 #else
2108         __node_holder __h = __construct_node(__args);
2109 #endif
2110         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2111         __r = __h.release();
2112         __inserted = true;
2113     }
2114     return pair<iterator, bool>(iterator(__r), __inserted);
2115 }
2116
2117
2118 #ifndef _LIBCPP_CXX03_LANG
2119 template <class _Tp, class _Compare, class _Allocator>
2120 template <class _Key, class... _Args>
2121 typename __tree<_Tp, _Compare, _Allocator>::iterator
2122 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
2123     const_iterator __p, _Key const& __k, _Args&&... __args)
2124 #else
2125 template <class _Tp, class _Compare, class _Allocator>
2126 template <class _Key, class _Args>
2127 typename __tree<_Tp, _Compare, _Allocator>::iterator
2128 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
2129     const_iterator __p, _Key const& __k, _Args& __args)
2130 #endif
2131 {
2132     __parent_pointer __parent;
2133     __node_base_pointer __dummy;
2134     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
2135     __node_pointer __r = static_cast<__node_pointer>(__child);
2136     if (__child == nullptr)
2137     {
2138 #ifndef _LIBCPP_CXX03_LANG
2139         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2140 #else
2141         __node_holder __h = __construct_node(__args);
2142 #endif
2143         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2144         __r = __h.release();
2145     }
2146     return iterator(__r);
2147 }
2148
2149
2150 #ifndef _LIBCPP_CXX03_LANG
2151
2152 template <class _Tp, class _Compare, class _Allocator>
2153 template <class ..._Args>
2154 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2155 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
2156 {
2157     static_assert(!__is_tree_value_type<_Args...>::value,
2158                   "Cannot construct from __value_type");
2159     __node_allocator& __na = __node_alloc();
2160     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2161     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
2162     __h.get_deleter().__value_constructed = true;
2163     return __h;
2164 }
2165
2166
2167 template <class _Tp, class _Compare, class _Allocator>
2168 template <class... _Args>
2169 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2170 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
2171 {
2172     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2173     __parent_pointer __parent;
2174     __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
2175     __node_pointer __r = static_cast<__node_pointer>(__child);
2176     bool __inserted = false;
2177     if (__child == nullptr)
2178     {
2179         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2180         __r = __h.release();
2181         __inserted = true;
2182     }
2183     return pair<iterator, bool>(iterator(__r), __inserted);
2184 }
2185
2186 template <class _Tp, class _Compare, class _Allocator>
2187 template <class... _Args>
2188 typename __tree<_Tp, _Compare, _Allocator>::iterator
2189 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
2190 {
2191     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2192     __parent_pointer __parent;
2193     __node_base_pointer __dummy;
2194     __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
2195     __node_pointer __r = static_cast<__node_pointer>(__child);
2196     if (__child == nullptr)
2197     {
2198         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2199         __r = __h.release();
2200     }
2201     return iterator(__r);
2202 }
2203
2204 template <class _Tp, class _Compare, class _Allocator>
2205 template <class... _Args>
2206 typename __tree<_Tp, _Compare, _Allocator>::iterator
2207 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
2208 {
2209     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2210     __parent_pointer __parent;
2211     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));
2212     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2213     return iterator(static_cast<__node_pointer>(__h.release()));
2214 }
2215
2216 template <class _Tp, class _Compare, class _Allocator>
2217 template <class... _Args>
2218 typename __tree<_Tp, _Compare, _Allocator>::iterator
2219 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
2220                                                         _Args&&... __args)
2221 {
2222     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2223     __parent_pointer __parent;
2224     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));
2225     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2226     return iterator(static_cast<__node_pointer>(__h.release()));
2227 }
2228
2229
2230 #else  // _LIBCPP_CXX03_LANG
2231
2232 template <class _Tp, class _Compare, class _Allocator>
2233 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2234 __tree<_Tp, _Compare, _Allocator>::__construct_node(const __container_value_type& __v)
2235 {
2236     __node_allocator& __na = __node_alloc();
2237     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2238     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
2239     __h.get_deleter().__value_constructed = true;
2240     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
2241 }
2242
2243 #endif  // _LIBCPP_CXX03_LANG
2244
2245 #ifdef _LIBCPP_CXX03_LANG
2246 template <class _Tp, class _Compare, class _Allocator>
2247 typename __tree<_Tp, _Compare, _Allocator>::iterator
2248 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v)
2249 {
2250     __parent_pointer __parent;
2251     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__v));
2252     __node_holder __h = __construct_node(__v);
2253     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2254     return iterator(__h.release());
2255 }
2256
2257 template <class _Tp, class _Compare, class _Allocator>
2258 typename __tree<_Tp, _Compare, _Allocator>::iterator
2259 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v)
2260 {
2261     __parent_pointer __parent;
2262     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__v));
2263     __node_holder __h = __construct_node(__v);
2264     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2265     return iterator(__h.release());
2266 }
2267 #endif
2268
2269 template <class _Tp, class _Compare, class _Allocator>
2270 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2271 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
2272 {
2273     __parent_pointer __parent;
2274     __node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
2275     __node_pointer __r = static_cast<__node_pointer>(__child);
2276     bool __inserted = false;
2277     if (__child == nullptr)
2278     {
2279         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2280         __r = __nd;
2281         __inserted = true;
2282     }
2283     return pair<iterator, bool>(iterator(__r), __inserted);
2284 }
2285
2286 template <class _Tp, class _Compare, class _Allocator>
2287 typename __tree<_Tp, _Compare, _Allocator>::iterator
2288 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
2289                                                         __node_pointer __nd)
2290 {
2291     __parent_pointer __parent;
2292     __node_base_pointer __dummy;
2293     __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
2294     __node_pointer __r = static_cast<__node_pointer>(__child);
2295     if (__child == nullptr)
2296     {
2297         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2298         __r = __nd;
2299     }
2300     return iterator(__r);
2301 }
2302
2303 template <class _Tp, class _Compare, class _Allocator>
2304 typename __tree<_Tp, _Compare, _Allocator>::iterator
2305 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
2306 {
2307     __parent_pointer __parent;
2308     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));
2309     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2310     return iterator(__nd);
2311 }
2312
2313 template <class _Tp, class _Compare, class _Allocator>
2314 typename __tree<_Tp, _Compare, _Allocator>::iterator
2315 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
2316                                                        __node_pointer __nd)
2317 {
2318     __parent_pointer __parent;
2319     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
2320     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2321     return iterator(__nd);
2322 }
2323
2324 template <class _Tp, class _Compare, class _Allocator>
2325 typename __tree<_Tp, _Compare, _Allocator>::iterator
2326 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
2327 {
2328     __node_pointer __np = __p.__get_np();
2329     iterator __r(__p.__ptr_);
2330     ++__r;
2331     if (__begin_node() == __p.__ptr_)
2332         __begin_node() = __r.__ptr_;
2333     --size();
2334     __node_allocator& __na = __node_alloc();
2335     __tree_remove(__end_node()->__left_,
2336                   static_cast<__node_base_pointer>(__np));
2337     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
2338         const_cast<__node_value_type&>(*__p)));
2339     __node_traits::deallocate(__na, __np, 1);
2340     return __r;
2341 }
2342
2343 template <class _Tp, class _Compare, class _Allocator>
2344 typename __tree<_Tp, _Compare, _Allocator>::iterator
2345 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
2346 {
2347     while (__f != __l)
2348         __f = erase(__f);
2349     return iterator(__l.__ptr_);
2350 }
2351
2352 template <class _Tp, class _Compare, class _Allocator>
2353 template <class _Key>
2354 typename __tree<_Tp, _Compare, _Allocator>::size_type
2355 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
2356 {
2357     iterator __i = find(__k);
2358     if (__i == end())
2359         return 0;
2360     erase(__i);
2361     return 1;
2362 }
2363
2364 template <class _Tp, class _Compare, class _Allocator>
2365 template <class _Key>
2366 typename __tree<_Tp, _Compare, _Allocator>::size_type
2367 __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
2368 {
2369     pair<iterator, iterator> __p = __equal_range_multi(__k);
2370     size_type __r = 0;
2371     for (; __p.first != __p.second; ++__r)
2372         __p.first = erase(__p.first);
2373     return __r;
2374 }
2375
2376 template <class _Tp, class _Compare, class _Allocator>
2377 template <class _Key>
2378 typename __tree<_Tp, _Compare, _Allocator>::iterator
2379 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
2380 {
2381     iterator __p = __lower_bound(__v, __root(), __end_node());
2382     if (__p != end() && !value_comp()(__v, *__p))
2383         return __p;
2384     return end();
2385 }
2386
2387 template <class _Tp, class _Compare, class _Allocator>
2388 template <class _Key>
2389 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2390 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
2391 {
2392     const_iterator __p = __lower_bound(__v, __root(), __end_node());
2393     if (__p != end() && !value_comp()(__v, *__p))
2394         return __p;
2395     return end();
2396 }
2397
2398 template <class _Tp, class _Compare, class _Allocator>
2399 template <class _Key>
2400 typename __tree<_Tp, _Compare, _Allocator>::size_type
2401 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
2402 {
2403     __node_pointer __rt = __root();
2404     while (__rt != nullptr)
2405     {
2406         if (value_comp()(__k, __rt->__value_))
2407         {
2408             __rt = static_cast<__node_pointer>(__rt->__left_);
2409         }
2410         else if (value_comp()(__rt->__value_, __k))
2411             __rt = static_cast<__node_pointer>(__rt->__right_);
2412         else
2413             return 1;
2414     }
2415     return 0;
2416 }
2417
2418 template <class _Tp, class _Compare, class _Allocator>
2419 template <class _Key>
2420 typename __tree<_Tp, _Compare, _Allocator>::size_type
2421 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
2422 {
2423     __iter_pointer __result = __end_node();
2424     __node_pointer __rt = __root();
2425     while (__rt != nullptr)
2426     {
2427         if (value_comp()(__k, __rt->__value_))
2428         {
2429             __result = static_cast<__iter_pointer>(__rt);
2430             __rt = static_cast<__node_pointer>(__rt->__left_);
2431         }
2432         else if (value_comp()(__rt->__value_, __k))
2433             __rt = static_cast<__node_pointer>(__rt->__right_);
2434         else
2435             return _VSTD::distance(
2436                 __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2437                 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)
2438             );
2439     }
2440     return 0;
2441 }
2442
2443 template <class _Tp, class _Compare, class _Allocator>
2444 template <class _Key>
2445 typename __tree<_Tp, _Compare, _Allocator>::iterator
2446 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2447                                                  __node_pointer __root,
2448                                                  __iter_pointer __result)
2449 {
2450     while (__root != nullptr)
2451     {
2452         if (!value_comp()(__root->__value_, __v))
2453         {
2454             __result = static_cast<__iter_pointer>(__root);
2455             __root = static_cast<__node_pointer>(__root->__left_);
2456         }
2457         else
2458             __root = static_cast<__node_pointer>(__root->__right_);
2459     }
2460     return iterator(__result);
2461 }
2462
2463 template <class _Tp, class _Compare, class _Allocator>
2464 template <class _Key>
2465 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2466 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2467                                                  __node_pointer __root,
2468                                                  __iter_pointer __result) const
2469 {
2470     while (__root != nullptr)
2471     {
2472         if (!value_comp()(__root->__value_, __v))
2473         {
2474             __result = static_cast<__iter_pointer>(__root);
2475             __root = static_cast<__node_pointer>(__root->__left_);
2476         }
2477         else
2478             __root = static_cast<__node_pointer>(__root->__right_);
2479     }
2480     return const_iterator(__result);
2481 }
2482
2483 template <class _Tp, class _Compare, class _Allocator>
2484 template <class _Key>
2485 typename __tree<_Tp, _Compare, _Allocator>::iterator
2486 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2487                                                  __node_pointer __root,
2488                                                  __iter_pointer __result)
2489 {
2490     while (__root != nullptr)
2491     {
2492         if (value_comp()(__v, __root->__value_))
2493         {
2494             __result = static_cast<__iter_pointer>(__root);
2495             __root = static_cast<__node_pointer>(__root->__left_);
2496         }
2497         else
2498             __root = static_cast<__node_pointer>(__root->__right_);
2499     }
2500     return iterator(__result);
2501 }
2502
2503 template <class _Tp, class _Compare, class _Allocator>
2504 template <class _Key>
2505 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2506 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2507                                                  __node_pointer __root,
2508                                                  __iter_pointer __result) const
2509 {
2510     while (__root != nullptr)
2511     {
2512         if (value_comp()(__v, __root->__value_))
2513         {
2514             __result = static_cast<__iter_pointer>(__root);
2515             __root = static_cast<__node_pointer>(__root->__left_);
2516         }
2517         else
2518             __root = static_cast<__node_pointer>(__root->__right_);
2519     }
2520     return const_iterator(__result);
2521 }
2522
2523 template <class _Tp, class _Compare, class _Allocator>
2524 template <class _Key>
2525 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2526      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2527 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
2528 {
2529     typedef pair<iterator, iterator> _Pp;
2530     __iter_pointer __result = __end_node();
2531     __node_pointer __rt = __root();
2532     while (__rt != nullptr)
2533     {
2534         if (value_comp()(__k, __rt->__value_))
2535         {
2536             __result = static_cast<__iter_pointer>(__rt);
2537             __rt = static_cast<__node_pointer>(__rt->__left_);
2538         }
2539         else if (value_comp()(__rt->__value_, __k))
2540             __rt = static_cast<__node_pointer>(__rt->__right_);
2541         else
2542             return _Pp(iterator(__rt),
2543                       iterator(
2544                           __rt->__right_ != nullptr ?
2545                               static_cast<__iter_pointer>(__tree_min(__rt->__right_))
2546                             : __result));
2547     }
2548     return _Pp(iterator(__result), iterator(__result));
2549 }
2550
2551 template <class _Tp, class _Compare, class _Allocator>
2552 template <class _Key>
2553 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2554      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2555 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
2556 {
2557     typedef pair<const_iterator, const_iterator> _Pp;
2558     __iter_pointer __result = __end_node();
2559     __node_pointer __rt = __root();
2560     while (__rt != nullptr)
2561     {
2562         if (value_comp()(__k, __rt->__value_))
2563         {
2564             __result = static_cast<__iter_pointer>(__rt);
2565             __rt = static_cast<__node_pointer>(__rt->__left_);
2566         }
2567         else if (value_comp()(__rt->__value_, __k))
2568             __rt = static_cast<__node_pointer>(__rt->__right_);
2569         else
2570             return _Pp(const_iterator(__rt),
2571                       const_iterator(
2572                           __rt->__right_ != nullptr ?
2573                               static_cast<__iter_pointer>(__tree_min(__rt->__right_))
2574                             : __result));
2575     }
2576     return _Pp(const_iterator(__result), const_iterator(__result));
2577 }
2578
2579 template <class _Tp, class _Compare, class _Allocator>
2580 template <class _Key>
2581 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2582      typename __tree<_Tp, _Compare, _Allocator>::iterator>
2583 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
2584 {
2585     typedef pair<iterator, iterator> _Pp;
2586     __iter_pointer __result = __end_node();
2587     __node_pointer __rt = __root();
2588     while (__rt != nullptr)
2589     {
2590         if (value_comp()(__k, __rt->__value_))
2591         {
2592             __result = static_cast<__iter_pointer>(__rt);
2593             __rt = static_cast<__node_pointer>(__rt->__left_);
2594         }
2595         else if (value_comp()(__rt->__value_, __k))
2596             __rt = static_cast<__node_pointer>(__rt->__right_);
2597         else
2598             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2599                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2600     }
2601     return _Pp(iterator(__result), iterator(__result));
2602 }
2603
2604 template <class _Tp, class _Compare, class _Allocator>
2605 template <class _Key>
2606 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2607      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2608 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
2609 {
2610     typedef pair<const_iterator, const_iterator> _Pp;
2611     __iter_pointer __result = __end_node();
2612     __node_pointer __rt = __root();
2613     while (__rt != nullptr)
2614     {
2615         if (value_comp()(__k, __rt->__value_))
2616         {
2617             __result = static_cast<__iter_pointer>(__rt);
2618             __rt = static_cast<__node_pointer>(__rt->__left_);
2619         }
2620         else if (value_comp()(__rt->__value_, __k))
2621             __rt = static_cast<__node_pointer>(__rt->__right_);
2622         else
2623             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2624                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2625     }
2626     return _Pp(const_iterator(__result), const_iterator(__result));
2627 }
2628
2629 template <class _Tp, class _Compare, class _Allocator>
2630 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2631 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2632 {
2633     __node_pointer __np = __p.__get_np();
2634     if (__begin_node() == __p.__ptr_)
2635     {
2636         if (__np->__right_ != nullptr)
2637             __begin_node() = static_cast<__iter_pointer>(__np->__right_);
2638         else
2639             __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
2640     }
2641     --size();
2642     __tree_remove(__end_node()->__left_,
2643                   static_cast<__node_base_pointer>(__np));
2644     return __node_holder(__np, _Dp(__node_alloc(), true));
2645 }
2646
2647 template <class _Tp, class _Compare, class _Allocator>
2648 inline _LIBCPP_INLINE_VISIBILITY
2649 void
2650 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2651      __tree<_Tp, _Compare, _Allocator>& __y)
2652     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2653 {
2654     __x.swap(__y);
2655 }
2656
2657 _LIBCPP_END_NAMESPACE_STD
2658
2659 #endif  // _LIBCPP___TREE