contrib/llvm-project/libcxx/include/__tree

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