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