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