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