Home | History | Annotate | Download | only in include
      1 // -*- C++ -*-
      2 //===----------------------------------------------------------------------===//
      3 //
      4 //                     The LLVM Compiler Infrastructure
      5 //
      6 // This file is dual licensed under the MIT and the University of Illinois Open
      7 // Source Licenses. See LICENSE.TXT for details.
      8 //
      9 //===----------------------------------------------------------------------===//
     10 
     11 #ifndef _LIBCPP___TREE
     12 #define _LIBCPP___TREE
     13 
     14 #include <__config>
     15 #include <iterator>
     16 #include <memory>
     17 #include <stdexcept>
     18 #include <algorithm>
     19 
     20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
     21 #pragma GCC system_header
     22 #endif
     23 
     24 _LIBCPP_BEGIN_NAMESPACE_STD
     25 
     26 template <class _Tp, class _Compare, class _Allocator> class __tree;
     27 template <class _Tp, class _NodePtr, class _DiffType>
     28     class _LIBCPP_VISIBLE __tree_iterator;
     29 template <class _Tp, class _ConstNodePtr, class _DiffType>
     30     class _LIBCPP_VISIBLE __tree_const_iterator;
     31 template <class _Key, class _Tp, class _Compare, class _Allocator>
     32     class _LIBCPP_VISIBLE map;
     33 template <class _Key, class _Tp, class _Compare, class _Allocator>
     34     class _LIBCPP_VISIBLE multimap;
     35 template <class _Key, class _Compare, class _Allocator>
     36     class _LIBCPP_VISIBLE set;
     37 template <class _Key, class _Compare, class _Allocator>
     38     class _LIBCPP_VISIBLE multiset;
     39 
     40 /*
     41 
     42 _NodePtr algorithms
     43 
     44 The algorithms taking _NodePtr are red black tree algorithms.  Those
     45 algorithms taking a parameter named __root should assume that __root
     46 points to a proper red black tree (unless otherwise specified).
     47 
     48 Each algorithm herein assumes that __root->__parent_ points to a non-null
     49 structure which has a member __left_ which points back to __root.  No other
     50 member is read or written to at __root->__parent_.
     51 
     52 __root->__parent_ will be referred to below (in comments only) as end_node.
     53 end_node->__left_ is an externably accessible lvalue for __root, and can be
     54 changed by node insertion and removal (without explicit reference to end_node).
     55 
     56 All nodes (with the exception of end_node), even the node referred to as
     57 __root, have a non-null __parent_ field.
     58 
     59 */
     60 
     61 // Returns:  true if __x is a left child of its parent, else false
     62 // Precondition:  __x != nullptr.
     63 template <class _NodePtr>
     64 inline _LIBCPP_INLINE_VISIBILITY
     65 bool
     66 __tree_is_left_child(_NodePtr __x) _NOEXCEPT
     67 {
     68     return __x == __x->__parent_->__left_;
     69 }
     70 
     71 // Determintes if the subtree rooted at __x is a proper red black subtree.  If
     72 //    __x is a proper subtree, returns the black height (null counts as 1).  If
     73 //    __x is an improper subtree, returns 0.
     74 template <class _NodePtr>
     75 unsigned
     76 __tree_sub_invariant(_NodePtr __x)
     77 {
     78     if (__x == nullptr)
     79         return 1;
     80     // parent consistency checked by caller
     81     // check __x->__left_ consistency
     82     if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
     83         return 0;
     84     // check __x->__right_ consistency
     85     if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
     86         return 0;
     87     // check __x->__left_ != __x->__right_ unless both are nullptr
     88     if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
     89         return 0;
     90     // If this is red, neither child can be red
     91     if (!__x->__is_black_)
     92     {
     93         if (__x->__left_ && !__x->__left_->__is_black_)
     94             return 0;
     95         if (__x->__right_ && !__x->__right_->__is_black_)
     96             return 0;
     97     }
     98     unsigned __h = __tree_sub_invariant(__x->__left_);
     99     if (__h == 0)
    100         return 0;  // invalid left subtree
    101     if (__h != __tree_sub_invariant(__x->__right_))
    102         return 0;  // invalid or different height right subtree
    103     return __h + __x->__is_black_;  // return black height of this node
    104 }
    105 
    106 // Determintes if the red black tree rooted at __root is a proper red black tree.
    107 //    __root == nullptr is a proper tree.  Returns true is __root is a proper
    108 //    red black tree, else returns false.
    109 template <class _NodePtr>
    110 bool
    111 __tree_invariant(_NodePtr __root)
    112 {
    113     if (__root == nullptr)
    114         return true;
    115     // check __x->__parent_ consistency
    116     if (__root->__parent_ == nullptr)
    117         return false;
    118     if (!__tree_is_left_child(__root))
    119         return false;
    120     // root must be black
    121     if (!__root->__is_black_)
    122         return false;
    123     // do normal node checks
    124     return __tree_sub_invariant(__root) != 0;
    125 }
    126 
    127 // Returns:  pointer to the left-most node under __x.
    128 // Precondition:  __x != nullptr.
    129 template <class _NodePtr>
    130 inline _LIBCPP_INLINE_VISIBILITY
    131 _NodePtr
    132 __tree_min(_NodePtr __x) _NOEXCEPT
    133 {
    134     while (__x->__left_ != nullptr)
    135         __x = __x->__left_;
    136     return __x;
    137 }
    138 
    139 // Returns:  pointer to the right-most node under __x.
    140 // Precondition:  __x != nullptr.
    141 template <class _NodePtr>
    142 inline _LIBCPP_INLINE_VISIBILITY
    143 _NodePtr
    144 __tree_max(_NodePtr __x) _NOEXCEPT
    145 {
    146     while (__x->__right_ != nullptr)
    147         __x = __x->__right_;
    148     return __x;
    149 }
    150 
    151 // Returns:  pointer to the next in-order node after __x.
    152 // Precondition:  __x != nullptr.
    153 template <class _NodePtr>
    154 _NodePtr
    155 __tree_next(_NodePtr __x) _NOEXCEPT
    156 {
    157     if (__x->__right_ != nullptr)
    158         return __tree_min(__x->__right_);
    159     while (!__tree_is_left_child(__x))
    160         __x = __x->__parent_;
    161     return __x->__parent_;
    162 }
    163 
    164 // Returns:  pointer to the previous in-order node before __x.
    165 // Precondition:  __x != nullptr.
    166 template <class _NodePtr>
    167 _NodePtr
    168 __tree_prev(_NodePtr __x) _NOEXCEPT
    169 {
    170     if (__x->__left_ != nullptr)
    171         return __tree_max(__x->__left_);
    172     while (__tree_is_left_child(__x))
    173         __x = __x->__parent_;
    174     return __x->__parent_;
    175 }
    176 
    177 // Returns:  pointer to a node which has no children
    178 // Precondition:  __x != nullptr.
    179 template <class _NodePtr>
    180 _NodePtr
    181 __tree_leaf(_NodePtr __x) _NOEXCEPT
    182 {
    183     while (true)
    184     {
    185         if (__x->__left_ != nullptr)
    186         {
    187             __x = __x->__left_;
    188             continue;
    189         }
    190         if (__x->__right_ != nullptr)
    191         {
    192             __x = __x->__right_;
    193             continue;
    194         }
    195         break;
    196     }
    197     return __x;
    198 }
    199 
    200 // Effects:  Makes __x->__right_ the subtree root with __x as its left child
    201 //           while preserving in-order order.
    202 // Precondition:  __x->__right_ != nullptr
    203 template <class _NodePtr>
    204 void
    205 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
    206 {
    207     _NodePtr __y = __x->__right_;
    208     __x->__right_ = __y->__left_;
    209     if (__x->__right_ != nullptr)
    210         __x->__right_->__parent_ = __x;
    211     __y->__parent_ = __x->__parent_;
    212     if (__tree_is_left_child(__x))
    213         __x->__parent_->__left_ = __y;
    214     else
    215         __x->__parent_->__right_ = __y;
    216     __y->__left_ = __x;
    217     __x->__parent_ = __y;
    218 }
    219 
    220 // Effects:  Makes __x->__left_ the subtree root with __x as its right child
    221 //           while preserving in-order order.
    222 // Precondition:  __x->__left_ != nullptr
    223 template <class _NodePtr>
    224 void
    225 __tree_right_rotate(_NodePtr __x) _NOEXCEPT
    226 {
    227     _NodePtr __y = __x->__left_;
    228     __x->__left_ = __y->__right_;
    229     if (__x->__left_ != nullptr)
    230         __x->__left_->__parent_ = __x;
    231     __y->__parent_ = __x->__parent_;
    232     if (__tree_is_left_child(__x))
    233         __x->__parent_->__left_ = __y;
    234     else
    235         __x->__parent_->__right_ = __y;
    236     __y->__right_ = __x;
    237     __x->__parent_ = __y;
    238 }
    239 
    240 // Effects:  Rebalances __root after attaching __x to a leaf.
    241 // Precondition:  __root != nulptr && __x != nullptr.
    242 //                __x has no children.
    243 //                __x == __root or == a direct or indirect child of __root.
    244 //                If __x were to be unlinked from __root (setting __root to
    245 //                  nullptr if __root == __x), __tree_invariant(__root) == true.
    246 // Postcondition: __tree_invariant(end_node->__left_) == true.  end_node->__left_
    247 //                may be different than the value passed in as __root.
    248 template <class _NodePtr>
    249 void
    250 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
    251 {
    252     __x->__is_black_ = __x == __root;
    253     while (__x != __root && !__x->__parent_->__is_black_)
    254     {
    255         // __x->__parent_ != __root because __x->__parent_->__is_black == false
    256         if (__tree_is_left_child(__x->__parent_))
    257         {
    258             _NodePtr __y = __x->__parent_->__parent_->__right_;
    259             if (__y != nullptr && !__y->__is_black_)
    260             {
    261                 __x = __x->__parent_;
    262                 __x->__is_black_ = true;
    263                 __x = __x->__parent_;
    264                 __x->__is_black_ = __x == __root;
    265                 __y->__is_black_ = true;
    266             }
    267             else
    268             {
    269                 if (!__tree_is_left_child(__x))
    270                 {
    271                     __x = __x->__parent_;
    272                     __tree_left_rotate(__x);
    273                 }
    274                 __x = __x->__parent_;
    275                 __x->__is_black_ = true;
    276                 __x = __x->__parent_;
    277                 __x->__is_black_ = false;
    278                 __tree_right_rotate(__x);
    279                 break;
    280             }
    281         }
    282         else
    283         {
    284             _NodePtr __y = __x->__parent_->__parent_->__left_;
    285             if (__y != nullptr && !__y->__is_black_)
    286             {
    287                 __x = __x->__parent_;
    288                 __x->__is_black_ = true;
    289                 __x = __x->__parent_;
    290                 __x->__is_black_ = __x == __root;
    291                 __y->__is_black_ = true;
    292             }
    293             else
    294             {
    295                 if (__tree_is_left_child(__x))
    296                 {
    297                     __x = __x->__parent_;
    298                     __tree_right_rotate(__x);
    299                 }
    300                 __x = __x->__parent_;
    301                 __x->__is_black_ = true;
    302                 __x = __x->__parent_;
    303                 __x->__is_black_ = false;
    304                 __tree_left_rotate(__x);
    305                 break;
    306             }
    307         }
    308     }
    309 }
    310 
    311 // Precondition:  __root != nullptr && __z != nullptr.
    312 //                __tree_invariant(__root) == true.
    313 //                __z == __root or == a direct or indirect child of __root.
    314 // Effects:  unlinks __z from the tree rooted at __root, rebalancing as needed.
    315 // Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_
    316 //                nor any of its children refer to __z.  end_node->__left_
    317 //                may be different than the value passed in as __root.
    318 template <class _NodePtr>
    319 void
    320 __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
    321 {
    322     // __z will be removed from the tree.  Client still needs to destruct/deallocate it
    323     // __y is either __z, or if __z has two children, __tree_next(__z).
    324     // __y will have at most one child.
    325     // __y will be the initial hole in the tree (make the hole at a leaf)
    326     _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ?
    327                     __z : __tree_next(__z);
    328     // __x is __y's possibly null single child
    329     _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
    330     // __w is __x's possibly null uncle (will become __x's sibling)
    331     _NodePtr __w = nullptr;
    332     // link __x to __y's parent, and find __w
    333     if (__x != nullptr)
    334         __x->__parent_ = __y->__parent_;
    335     if (__tree_is_left_child(__y))
    336     {
    337         __y->__parent_->__left_ = __x;
    338         if (__y != __root)
    339             __w = __y->__parent_->__right_;
    340         else
    341             __root = __x;  // __w == nullptr
    342     }
    343     else
    344     {
    345         __y->__parent_->__right_ = __x;
    346         // __y can't be root if it is a right child
    347         __w = __y->__parent_->__left_;
    348     }
    349     bool __removed_black = __y->__is_black_;
    350     // If we didn't remove __z, do so now by splicing in __y for __z,
    351     //    but copy __z's color.  This does not impact __x or __w.
    352     if (__y != __z)
    353     {
    354         // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
    355         __y->__parent_ = __z->__parent_;
    356         if (__tree_is_left_child(__z))
    357             __y->__parent_->__left_ = __y;
    358         else
    359             __y->__parent_->__right_ = __y;
    360         __y->__left_ = __z->__left_;
    361         __y->__left_->__parent_ = __y;
    362         __y->__right_ = __z->__right_;
    363         if (__y->__right_ != nullptr)
    364             __y->__right_->__parent_ = __y;
    365         __y->__is_black_ = __z->__is_black_;
    366         if (__root == __z)
    367             __root = __y;
    368     }
    369     // There is no need to rebalance if we removed a red, or if we removed
    370     //     the last node.
    371     if (__removed_black && __root != nullptr)
    372     {
    373         // Rebalance:
    374         // __x has an implicit black color (transferred from the removed __y)
    375         //    associated with it, no matter what its color is.
    376         // If __x is __root (in which case it can't be null), it is supposed
    377         //    to be black anyway, and if it is doubly black, then the double
    378         //    can just be ignored.
    379         // If __x is red (in which case it can't be null), then it can absorb
    380         //    the implicit black just by setting its color to black.
    381         // Since __y was black and only had one child (which __x points to), __x
    382         //   is either red with no children, else null, otherwise __y would have
    383         //   different black heights under left and right pointers.
    384         // if (__x == __root || __x != nullptr && !__x->__is_black_)
    385         if (__x != nullptr)
    386             __x->__is_black_ = true;
    387         else
    388         {
    389             //  Else __x isn't root, and is "doubly black", even though it may
    390             //     be null.  __w can not be null here, else the parent would
    391             //     see a black height >= 2 on the __x side and a black height
    392             //     of 1 on the __w side (__w must be a non-null black or a red
    393             //     with a non-null black child).
    394             while (true)
    395             {
    396                 if (!__tree_is_left_child(__w))  // if x is left child
    397                 {
    398                     if (!__w->__is_black_)
    399                     {
    400                         __w->__is_black_ = true;
    401                         __w->__parent_->__is_black_ = false;
    402                         __tree_left_rotate(__w->__parent_);
    403                         // __x is still valid
    404                         // reset __root only if necessary
    405                         if (__root == __w->__left_)
    406                             __root = __w;
    407                         // reset sibling, and it still can't be null
    408                         __w = __w->__left_->__right_;
    409                     }
    410                     // __w->__is_black_ is now true, __w may have null children
    411                     if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
    412                         (__w->__right_ == nullptr || __w->__right_->__is_black_))
    413                     {
    414                         __w->__is_black_ = false;
    415                         __x = __w->__parent_;
    416                         // __x can no longer be null
    417                         if (__x == __root || !__x->__is_black_)
    418                         {
    419                             __x->__is_black_ = true;
    420                             break;
    421                         }
    422                         // reset sibling, and it still can't be null
    423                         __w = __tree_is_left_child(__x) ?
    424                                     __x->__parent_->__right_ :
    425                                     __x->__parent_->__left_;
    426                         // continue;
    427                     }
    428                     else  // __w has a red child
    429                     {
    430                         if (__w->__right_ == nullptr || __w->__right_->__is_black_)
    431                         {
    432                             // __w left child is non-null and red
    433                             __w->__left_->__is_black_ = true;
    434                             __w->__is_black_ = false;
    435                             __tree_right_rotate(__w);
    436                             // __w is known not to be root, so root hasn't changed
    437                             // reset sibling, and it still can't be null
    438                             __w = __w->__parent_;
    439                         }
    440                         // __w has a right red child, left child may be null
    441                         __w->__is_black_ = __w->__parent_->__is_black_;
    442                         __w->__parent_->__is_black_ = true;
    443                         __w->__right_->__is_black_ = true;
    444                         __tree_left_rotate(__w->__parent_);
    445                         break;
    446                     }
    447                 }
    448                 else
    449                 {
    450                     if (!__w->__is_black_)
    451                     {
    452                         __w->__is_black_ = true;
    453                         __w->__parent_->__is_black_ = false;
    454                         __tree_right_rotate(__w->__parent_);
    455                         // __x is still valid
    456                         // reset __root only if necessary
    457                         if (__root == __w->__right_)
    458                             __root = __w;
    459                         // reset sibling, and it still can't be null
    460                         __w = __w->__right_->__left_;
    461                     }
    462                     // __w->__is_black_ is now true, __w may have null children
    463                     if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
    464                         (__w->__right_ == nullptr || __w->__right_->__is_black_))
    465                     {
    466                         __w->__is_black_ = false;
    467                         __x = __w->__parent_;
    468                         // __x can no longer be null
    469                         if (!__x->__is_black_ || __x == __root)
    470                         {
    471                             __x->__is_black_ = true;
    472                             break;
    473                         }
    474                         // reset sibling, and it still can't be null
    475                         __w = __tree_is_left_child(__x) ?
    476                                     __x->__parent_->__right_ :
    477                                     __x->__parent_->__left_;
    478                         // continue;
    479                     }
    480                     else  // __w has a red child
    481                     {
    482                         if (__w->__left_ == nullptr || __w->__left_->__is_black_)
    483                         {
    484                             // __w right child is non-null and red
    485                             __w->__right_->__is_black_ = true;
    486                             __w->__is_black_ = false;
    487                             __tree_left_rotate(__w);
    488                             // __w is known not to be root, so root hasn't changed
    489                             // reset sibling, and it still can't be null
    490                             __w = __w->__parent_;
    491                         }
    492                         // __w has a left red child, right child may be null
    493                         __w->__is_black_ = __w->__parent_->__is_black_;
    494                         __w->__parent_->__is_black_ = true;
    495                         __w->__left_->__is_black_ = true;
    496                         __tree_right_rotate(__w->__parent_);
    497                         break;
    498                     }
    499                 }
    500             }
    501         }
    502     }
    503 }
    504 
    505 template <class _Allocator> class __map_node_destructor;
    506 
    507 template <class _Allocator>
    508 class __tree_node_destructor
    509 {
    510     typedef _Allocator                                      allocator_type;
    511     typedef allocator_traits<allocator_type>                __alloc_traits;
    512     typedef typename __alloc_traits::value_type::value_type value_type;
    513 public:
    514     typedef typename __alloc_traits::pointer                pointer;
    515 private:
    516 
    517     allocator_type& __na_;
    518 
    519     __tree_node_destructor& operator=(const __tree_node_destructor&);
    520 
    521 public:
    522     bool __value_constructed;
    523 
    524     _LIBCPP_INLINE_VISIBILITY
    525     explicit __tree_node_destructor(allocator_type& __na) _NOEXCEPT
    526         : __na_(__na),
    527           __value_constructed(false)
    528         {}
    529 
    530     _LIBCPP_INLINE_VISIBILITY
    531     void operator()(pointer __p) _NOEXCEPT
    532     {
    533         if (__value_constructed)
    534             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
    535         if (__p)
    536             __alloc_traits::deallocate(__na_, __p, 1);
    537     }
    538 
    539     template <class> friend class __map_node_destructor;
    540 };
    541 
    542 // node
    543 
    544 template <class _Pointer>
    545 class __tree_end_node
    546 {
    547 public:
    548     typedef _Pointer pointer;
    549     pointer __left_;
    550 
    551     _LIBCPP_INLINE_VISIBILITY
    552     __tree_end_node() _NOEXCEPT : __left_() {}
    553 };
    554 
    555 template <class _VoidPtr>
    556 class __tree_node_base
    557     : public __tree_end_node
    558              <
    559                 typename pointer_traits<_VoidPtr>::template
    560 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    561                      rebind<__tree_node_base<_VoidPtr> >
    562 #else
    563                      rebind<__tree_node_base<_VoidPtr> >::other
    564 #endif
    565              >
    566 {
    567     __tree_node_base(const __tree_node_base&);
    568     __tree_node_base& operator=(const __tree_node_base&);
    569 public:
    570     typedef typename pointer_traits<_VoidPtr>::template
    571 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    572             rebind<__tree_node_base>
    573 #else
    574             rebind<__tree_node_base>::other
    575 #endif
    576                                                 pointer;
    577     typedef typename pointer_traits<_VoidPtr>::template
    578 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    579             rebind<const __tree_node_base>
    580 #else
    581             rebind<const __tree_node_base>::other
    582 #endif
    583                                                 const_pointer;
    584     typedef __tree_end_node<pointer> base;
    585 
    586     pointer __right_;
    587     pointer __parent_;
    588     bool __is_black_;
    589 
    590     _LIBCPP_INLINE_VISIBILITY
    591     __tree_node_base() _NOEXCEPT
    592         : __right_(), __parent_(), __is_black_(false) {}
    593 };
    594 
    595 template <class _Tp, class _VoidPtr>
    596 class __tree_node
    597     : public __tree_node_base<_VoidPtr>
    598 {
    599 public:
    600     typedef __tree_node_base<_VoidPtr> base;
    601     typedef _Tp value_type;
    602 
    603     value_type __value_;
    604 
    605 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
    606     template <class ..._Args>
    607         _LIBCPP_INLINE_VISIBILITY
    608         explicit __tree_node(_Args&& ...__args)
    609             : __value_(_VSTD::forward<_Args>(__args)...) {}
    610 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
    611     _LIBCPP_INLINE_VISIBILITY
    612     explicit __tree_node(const value_type& __v)
    613             : __value_(__v) {}
    614 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
    615 };
    616 
    617 template <class _TreeIterator> class _LIBCPP_VISIBLE __map_iterator;
    618 template <class _TreeIterator> class _LIBCPP_VISIBLE __map_const_iterator;
    619 
    620 template <class _Tp, class _NodePtr, class _DiffType>
    621 class _LIBCPP_VISIBLE __tree_iterator
    622 {
    623     typedef _NodePtr                                              __node_pointer;
    624     typedef typename pointer_traits<__node_pointer>::element_type __node;
    625     typedef typename __node::base                                 __node_base;
    626     typedef typename __node_base::pointer                         __node_base_pointer;
    627 
    628     __node_pointer __ptr_;
    629 
    630     typedef pointer_traits<__node_pointer> __pointer_traits;
    631 public:
    632     typedef bidirectional_iterator_tag iterator_category;
    633     typedef _Tp                        value_type;
    634     typedef _DiffType                  difference_type;
    635     typedef value_type&                reference;
    636     typedef typename pointer_traits<__node_pointer>::template
    637 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    638             rebind<value_type>
    639 #else
    640             rebind<value_type>::other
    641 #endif
    642                                        pointer;
    643 
    644     _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT {}
    645 
    646     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
    647     _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;}
    648 
    649     _LIBCPP_INLINE_VISIBILITY
    650     __tree_iterator& operator++()
    651         {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_)));
    652          return *this;}
    653     _LIBCPP_INLINE_VISIBILITY
    654     __tree_iterator operator++(int)
    655         {__tree_iterator __t(*this); ++(*this); return __t;}
    656 
    657     _LIBCPP_INLINE_VISIBILITY
    658     __tree_iterator& operator--()
    659         {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_)));
    660          return *this;}
    661     _LIBCPP_INLINE_VISIBILITY
    662     __tree_iterator operator--(int)
    663         {__tree_iterator __t(*this); --(*this); return __t;}
    664 
    665     friend _LIBCPP_INLINE_VISIBILITY 
    666         bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
    667         {return __x.__ptr_ == __y.__ptr_;}
    668     friend _LIBCPP_INLINE_VISIBILITY
    669         bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
    670         {return !(__x == __y);}
    671 
    672 private:
    673     _LIBCPP_INLINE_VISIBILITY
    674     explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
    675     template <class, class, class> friend class __tree;
    676     template <class, class, class> friend class _LIBCPP_VISIBLE __tree_const_iterator;
    677     template <class> friend class _LIBCPP_VISIBLE __map_iterator;
    678     template <class, class, class, class> friend class _LIBCPP_VISIBLE map;
    679     template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap;
    680     template <class, class, class> friend class _LIBCPP_VISIBLE set;
    681     template <class, class, class> friend class _LIBCPP_VISIBLE multiset;
    682 };
    683 
    684 template <class _Tp, class _ConstNodePtr, class _DiffType>
    685 class _LIBCPP_VISIBLE __tree_const_iterator
    686 {
    687     typedef _ConstNodePtr                                         __node_pointer;
    688     typedef typename pointer_traits<__node_pointer>::element_type __node;
    689     typedef const typename __node::base                           __node_base;
    690     typedef typename pointer_traits<__node_pointer>::template
    691 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    692             rebind<__node_base>
    693 #else
    694             rebind<__node_base>::other
    695 #endif
    696                                                                   __node_base_pointer;
    697 
    698     __node_pointer __ptr_;
    699 
    700     typedef pointer_traits<__node_pointer> __pointer_traits;
    701 public:
    702     typedef bidirectional_iterator_tag       iterator_category;
    703     typedef _Tp                              value_type;
    704     typedef _DiffType                        difference_type;
    705     typedef const value_type&                reference;
    706     typedef typename pointer_traits<__node_pointer>::template
    707 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    708             rebind<const value_type>
    709 #else
    710             rebind<const value_type>::other
    711 #endif
    712                                        pointer;
    713 
    714     _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() {}
    715 private:
    716     typedef typename remove_const<__node>::type  __non_const_node;
    717     typedef typename pointer_traits<__node_pointer>::template
    718 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    719             rebind<__non_const_node>
    720 #else
    721             rebind<__non_const_node>::other
    722 #endif
    723                                                  __non_const_node_pointer;
    724     typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type>
    725                                                  __non_const_iterator;
    726 public:
    727     _LIBCPP_INLINE_VISIBILITY
    728     __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
    729         : __ptr_(__p.__ptr_) {}
    730 
    731     _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
    732     _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;}
    733 
    734     _LIBCPP_INLINE_VISIBILITY
    735     __tree_const_iterator& operator++()
    736         {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_)));
    737          return *this;}
    738     _LIBCPP_INLINE_VISIBILITY
    739     __tree_const_iterator operator++(int)
    740         {__tree_const_iterator __t(*this); ++(*this); return __t;}
    741 
    742     _LIBCPP_INLINE_VISIBILITY
    743     __tree_const_iterator& operator--()
    744         {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_)));
    745          return *this;}
    746     _LIBCPP_INLINE_VISIBILITY
    747     __tree_const_iterator operator--(int)
    748         {__tree_const_iterator __t(*this); --(*this); return __t;}
    749 
    750     friend _LIBCPP_INLINE_VISIBILITY
    751         bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
    752         {return __x.__ptr_ == __y.__ptr_;}
    753     friend _LIBCPP_INLINE_VISIBILITY
    754         bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
    755         {return !(__x == __y);}
    756 
    757 private:
    758     _LIBCPP_INLINE_VISIBILITY
    759     explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
    760         : __ptr_(__p) {}
    761     template <class, class, class> friend class __tree;
    762     template <class, class, class, class> friend class _LIBCPP_VISIBLE map;
    763     template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap;
    764     template <class, class, class> friend class _LIBCPP_VISIBLE set;
    765     template <class, class, class> friend class _LIBCPP_VISIBLE multiset;
    766     template <class> friend class _LIBCPP_VISIBLE __map_const_iterator;
    767 };
    768 
    769 template <class _Tp, class _Compare, class _Allocator>
    770 class __tree
    771 {
    772 public:
    773     typedef _Tp                                      value_type;
    774     typedef _Compare                                 value_compare;
    775     typedef _Allocator                               allocator_type;
    776     typedef allocator_traits<allocator_type>         __alloc_traits;
    777     typedef typename __alloc_traits::pointer         pointer;
    778     typedef typename __alloc_traits::const_pointer   const_pointer;
    779     typedef typename __alloc_traits::size_type       size_type;
    780     typedef typename __alloc_traits::difference_type difference_type;
    781 
    782     typedef __tree_node<value_type, typename __alloc_traits::void_pointer> __node;
    783     typedef __tree_node_base<typename __alloc_traits::void_pointer> __node_base;
    784     typedef typename __alloc_traits::template
    785 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    786             rebind_alloc<__node>
    787 #else
    788             rebind_alloc<__node>::other
    789 #endif
    790                                                      __node_allocator;
    791     typedef allocator_traits<__node_allocator>       __node_traits;
    792     typedef typename __node_traits::pointer          __node_pointer;
    793     typedef typename __node_traits::const_pointer    __node_const_pointer;
    794     typedef typename __node_base::pointer            __node_base_pointer;
    795     typedef typename __node_base::const_pointer      __node_base_const_pointer;
    796 private:
    797     typedef typename __node_base::base __end_node_t;
    798     typedef typename pointer_traits<__node_pointer>::template
    799 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    800             rebind<__end_node_t>
    801 #else
    802             rebind<__end_node_t>::other
    803 #endif
    804                                                      __end_node_ptr;
    805     typedef typename pointer_traits<__node_pointer>::template
    806 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
    807             rebind<const __end_node_t>
    808 #else
    809             rebind<const __end_node_t>::other
    810 #endif
    811                                                      __end_node_const_ptr;
    812 
    813     __node_pointer                                          __begin_node_;
    814     __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
    815     __compressed_pair<size_type, value_compare>        __pair3_;
    816 
    817 public:
    818     _LIBCPP_INLINE_VISIBILITY
    819     __node_pointer __end_node() _NOEXCEPT
    820     {
    821         return static_cast<__node_pointer>
    822                (
    823                    pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
    824                );
    825     }
    826     _LIBCPP_INLINE_VISIBILITY
    827     __node_const_pointer __end_node() const _NOEXCEPT
    828     {
    829         return static_cast<__node_const_pointer>
    830                (
    831                    pointer_traits<__end_node_const_ptr>::pointer_to(__pair1_.first())
    832                );
    833     }
    834     _LIBCPP_INLINE_VISIBILITY
    835           __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}
    836 private:
    837     _LIBCPP_INLINE_VISIBILITY
    838     const __node_allocator& __node_alloc() const _NOEXCEPT
    839         {return __pair1_.second();}
    840     _LIBCPP_INLINE_VISIBILITY
    841           __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
    842     _LIBCPP_INLINE_VISIBILITY
    843     const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
    844 public:
    845     _LIBCPP_INLINE_VISIBILITY
    846     allocator_type __alloc() const _NOEXCEPT
    847         {return allocator_type(__node_alloc());}
    848 private:
    849     _LIBCPP_INLINE_VISIBILITY
    850           size_type& size() _NOEXCEPT {return __pair3_.first();}
    851 public:
    852     _LIBCPP_INLINE_VISIBILITY
    853     const size_type& size() const _NOEXCEPT {return __pair3_.first();}
    854     _LIBCPP_INLINE_VISIBILITY
    855           value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}
    856     _LIBCPP_INLINE_VISIBILITY
    857     const value_compare& value_comp() const _NOEXCEPT
    858         {return __pair3_.second();}
    859 public:
    860     _LIBCPP_INLINE_VISIBILITY
    861     __node_pointer __root() _NOEXCEPT
    862         {return static_cast<__node_pointer>      (__end_node()->__left_);}
    863     _LIBCPP_INLINE_VISIBILITY
    864     __node_const_pointer __root() const _NOEXCEPT
    865         {return static_cast<__node_const_pointer>(__end_node()->__left_);}
    866 
    867     typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
    868     typedef __tree_const_iterator<value_type, __node_const_pointer, difference_type> const_iterator;
    869 
    870     explicit __tree(const value_compare& __comp)
    871         _NOEXCEPT_(
    872             is_nothrow_default_constructible<__node_allocator>::value &&
    873             is_nothrow_copy_constructible<value_compare>::value);
    874     explicit __tree(const allocator_type& __a);
    875     __tree(const value_compare& __comp, const allocator_type& __a);
    876     __tree(const __tree& __t);
    877     __tree& operator=(const __tree& __t);
    878     template <class _InputIterator>
    879         void __assign_unique(_InputIterator __first, _InputIterator __last);
    880     template <class _InputIterator>
    881         void __assign_multi(_InputIterator __first, _InputIterator __last);
    882 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    883     __tree(__tree&& __t)
    884         _NOEXCEPT_(
    885             is_nothrow_move_constructible<__node_allocator>::value &&
    886             is_nothrow_move_constructible<value_compare>::value);
    887     __tree(__tree&& __t, const allocator_type& __a);
    888     __tree& operator=(__tree&& __t)
    889         _NOEXCEPT_(
    890             __node_traits::propagate_on_container_move_assignment::value &&
    891             is_nothrow_move_assignable<value_compare>::value &&
    892             is_nothrow_move_assignable<__node_allocator>::value);
    893 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
    894 
    895     ~__tree();
    896 
    897     _LIBCPP_INLINE_VISIBILITY
    898           iterator begin()  _NOEXCEPT {return       iterator(__begin_node());}
    899     _LIBCPP_INLINE_VISIBILITY
    900     const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());}
    901     _LIBCPP_INLINE_VISIBILITY
    902           iterator end() _NOEXCEPT {return       iterator(__end_node());}
    903     _LIBCPP_INLINE_VISIBILITY
    904     const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());}
    905 
    906     _LIBCPP_INLINE_VISIBILITY
    907     size_type max_size() const _NOEXCEPT
    908         {return __node_traits::max_size(__node_alloc());}
    909 
    910     void clear() _NOEXCEPT;
    911 
    912     void swap(__tree& __t)
    913         _NOEXCEPT_(
    914             __is_nothrow_swappable<value_compare>::value &&
    915             (!__node_traits::propagate_on_container_swap::value ||
    916              __is_nothrow_swappable<__node_allocator>::value));
    917 
    918 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
    919 #ifndef _LIBCPP_HAS_NO_VARIADICS
    920     template <class... _Args>
    921         pair<iterator, bool>
    922         __emplace_unique(_Args&&... __args);
    923     template <class... _Args>
    924         iterator
    925         __emplace_multi(_Args&&... __args);
    926 
    927     template <class... _Args>
    928         iterator
    929         __emplace_hint_unique(const_iterator __p, _Args&&... __args);
    930     template <class... _Args>
    931         iterator
    932         __emplace_hint_multi(const_iterator __p, _Args&&... __args);
    933 #endif  // _LIBCPP_HAS_NO_VARIADICS
    934 
    935     template <class _Vp>
    936         pair<iterator, bool> __insert_unique(_Vp&& __v);
    937     template <class _Vp>
    938         iterator __insert_unique(const_iterator __p, _Vp&& __v);
    939     template <class _Vp>
    940         iterator __insert_multi(_Vp&& __v);
    941     template <class _Vp>
    942         iterator __insert_multi(const_iterator __p, _Vp&& __v);
    943 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
    944 
    945     pair<iterator, bool> __insert_unique(const value_type& __v);
    946     iterator __insert_unique(const_iterator __p, const value_type& __v);
    947     iterator __insert_multi(const value_type& __v);
    948     iterator __insert_multi(const_iterator __p, const value_type& __v);
    949 
    950     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
    951     iterator             __node_insert_unique(const_iterator __p,
    952                                               __node_pointer __nd);
    953 
    954     iterator __node_insert_multi(__node_pointer __nd);
    955     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
    956 
    957     iterator erase(const_iterator __p);
    958     iterator erase(const_iterator __f, const_iterator __l);
    959     template <class _Key>
    960         size_type __erase_unique(const _Key& __k);
    961     template <class _Key>
    962         size_type __erase_multi(const _Key& __k);
    963 
    964     void __insert_node_at(__node_base_pointer __parent,
    965                           __node_base_pointer& __child,
    966                           __node_base_pointer __new_node);
    967 
    968     template <class _Key>
    969         iterator find(const _Key& __v);
    970     template <class _Key>
    971         const_iterator find(const _Key& __v) const;
    972 
    973     template <class _Key>
    974         size_type __count_unique(const _Key& __k) const;
    975     template <class _Key>
    976         size_type __count_multi(const _Key& __k) const;
    977 
    978     template <class _Key>
    979         _LIBCPP_INLINE_VISIBILITY
    980         iterator lower_bound(const _Key& __v)
    981             {return __lower_bound(__v, __root(), __end_node());}
    982     template <class _Key>
    983         iterator __lower_bound(const _Key& __v,
    984                                __node_pointer __root,
    985                                __node_pointer __result);
    986     template <class _Key>
    987         _LIBCPP_INLINE_VISIBILITY
    988         const_iterator lower_bound(const _Key& __v) const
    989             {return __lower_bound(__v, __root(), __end_node());}
    990     template <class _Key>
    991         const_iterator __lower_bound(const _Key& __v,
    992                                      __node_const_pointer __root,
    993                                      __node_const_pointer __result) const;
    994     template <class _Key>
    995         _LIBCPP_INLINE_VISIBILITY
    996         iterator upper_bound(const _Key& __v)
    997             {return __upper_bound(__v, __root(), __end_node());}
    998     template <class _Key>
    999         iterator __upper_bound(const _Key& __v,
   1000                                __node_pointer __root,
   1001                                __node_pointer __result);
   1002     template <class _Key>
   1003         _LIBCPP_INLINE_VISIBILITY
   1004         const_iterator upper_bound(const _Key& __v) const
   1005             {return __upper_bound(__v, __root(), __end_node());}
   1006     template <class _Key>
   1007         const_iterator __upper_bound(const _Key& __v,
   1008                                      __node_const_pointer __root,
   1009                                      __node_const_pointer __result) const;
   1010     template <class _Key>
   1011         pair<iterator, iterator>
   1012         __equal_range_unique(const _Key& __k);
   1013     template <class _Key>
   1014         pair<const_iterator, const_iterator>
   1015         __equal_range_unique(const _Key& __k) const;
   1016 
   1017     template <class _Key>
   1018         pair<iterator, iterator>
   1019         __equal_range_multi(const _Key& __k);
   1020     template <class _Key>
   1021         pair<const_iterator, const_iterator>
   1022         __equal_range_multi(const _Key& __k) const;
   1023 
   1024     typedef __tree_node_destructor<__node_allocator> _Dp;
   1025     typedef unique_ptr<__node, _Dp> __node_holder;
   1026 
   1027     __node_holder remove(const_iterator __p) _NOEXCEPT;
   1028 private:
   1029     typename __node_base::pointer&
   1030         __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v);
   1031     typename __node_base::pointer&
   1032         __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v);
   1033     typename __node_base::pointer&
   1034         __find_leaf(const_iterator __hint,
   1035                     typename __node_base::pointer& __parent, const value_type& __v);
   1036     template <class _Key>
   1037         typename __node_base::pointer&
   1038         __find_equal(typename __node_base::pointer& __parent, const _Key& __v);
   1039     template <class _Key>
   1040         typename __node_base::pointer&
   1041         __find_equal(const_iterator __hint, typename __node_base::pointer& __parent,
   1042                      const _Key& __v);
   1043 
   1044 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
   1045     template <class ..._Args>
   1046         __node_holder __construct_node(_Args&& ...__args);
   1047 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
   1048         __node_holder __construct_node(const value_type& __v);
   1049 #endif
   1050 
   1051     void destroy(__node_pointer __nd) _NOEXCEPT;
   1052 
   1053     _LIBCPP_INLINE_VISIBILITY
   1054     void __copy_assign_alloc(const __tree& __t)
   1055         {__copy_assign_alloc(__t, integral_constant<bool,
   1056              __node_traits::propagate_on_container_copy_assignment::value>());}
   1057 
   1058     _LIBCPP_INLINE_VISIBILITY
   1059     void __copy_assign_alloc(const __tree& __t, true_type)
   1060         {__node_alloc() = __t.__node_alloc();}
   1061     _LIBCPP_INLINE_VISIBILITY
   1062     void __copy_assign_alloc(const __tree& __t, false_type) {}
   1063 
   1064     void __move_assign(__tree& __t, false_type);
   1065     void __move_assign(__tree& __t, true_type)
   1066         _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
   1067                    is_nothrow_move_assignable<__node_allocator>::value);
   1068 
   1069     _LIBCPP_INLINE_VISIBILITY
   1070     void __move_assign_alloc(__tree& __t)
   1071         _NOEXCEPT_(
   1072             !__node_traits::propagate_on_container_move_assignment::value ||
   1073             is_nothrow_move_assignable<__node_allocator>::value)
   1074         {__move_assign_alloc(__t, integral_constant<bool,
   1075              __node_traits::propagate_on_container_move_assignment::value>());}
   1076 
   1077     _LIBCPP_INLINE_VISIBILITY
   1078     void __move_assign_alloc(__tree& __t, true_type)
   1079         _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
   1080         {__node_alloc() = _VSTD::move(__t.__node_alloc());}
   1081     _LIBCPP_INLINE_VISIBILITY
   1082     void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {}
   1083 
   1084     _LIBCPP_INLINE_VISIBILITY
   1085     static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
   1086         _NOEXCEPT_(
   1087             !__node_traits::propagate_on_container_swap::value ||
   1088             __is_nothrow_swappable<__node_allocator>::value)
   1089         {__swap_alloc(__x, __y, integral_constant<bool,
   1090                       __node_traits::propagate_on_container_swap::value>());}
   1091     _LIBCPP_INLINE_VISIBILITY
   1092     static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type)
   1093         _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
   1094         {
   1095             using _VSTD::swap;
   1096             swap(__x, __y);
   1097         }
   1098     _LIBCPP_INLINE_VISIBILITY
   1099     static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type)
   1100         _NOEXCEPT
   1101         {}
   1102 
   1103     __node_pointer __detach();
   1104     static __node_pointer __detach(__node_pointer);
   1105 };
   1106 
   1107 template <class _Tp, class _Compare, class _Allocator>
   1108 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
   1109         _NOEXCEPT_(
   1110             is_nothrow_default_constructible<__node_allocator>::value &&
   1111             is_nothrow_copy_constructible<value_compare>::value)
   1112     : __pair3_(0, __comp)
   1113 {
   1114     __begin_node() = __end_node();
   1115 }
   1116 
   1117 template <class _Tp, class _Compare, class _Allocator>
   1118 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
   1119     : __pair1_(__node_allocator(__a)),
   1120       __begin_node_(__node_pointer()),
   1121       __pair3_(0)
   1122 {
   1123     __begin_node() = __end_node();
   1124 }
   1125 
   1126 template <class _Tp, class _Compare, class _Allocator>
   1127 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
   1128                                            const allocator_type& __a)
   1129     : __pair1_(__node_allocator(__a)),
   1130       __begin_node_(__node_pointer()),
   1131       __pair3_(0, __comp)
   1132 {
   1133     __begin_node() = __end_node();
   1134 }
   1135 
   1136 // Precondition:  size() != 0
   1137 template <class _Tp, class _Compare, class _Allocator>
   1138 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
   1139 __tree<_Tp, _Compare, _Allocator>::__detach()
   1140 {
   1141     __node_pointer __cache = __begin_node();
   1142     __begin_node() = __end_node();
   1143     __end_node()->__left_->__parent_ = nullptr;
   1144     __end_node()->__left_ = nullptr;
   1145     size() = 0;
   1146     // __cache->__left_ == nullptr
   1147     if (__cache->__right_ != nullptr)
   1148         __cache = static_cast<__node_pointer>(__cache->__right_);
   1149     // __cache->__left_ == nullptr
   1150     // __cache->__right_ == nullptr
   1151     return __cache;
   1152 }
   1153 
   1154 // Precondition:  __cache != nullptr
   1155 //    __cache->left_ == nullptr
   1156 //    __cache->right_ == nullptr
   1157 //    This is no longer a red-black tree
   1158 template <class _Tp, class _Compare, class _Allocator>
   1159 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
   1160 __tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache)
   1161 {
   1162     if (__cache->__parent_ == nullptr)
   1163         return nullptr;
   1164     if (__tree_is_left_child(__cache))
   1165     {
   1166         __cache->__parent_->__left_ = nullptr;
   1167         __cache = static_cast<__node_pointer>(__cache->__parent_);
   1168         if (__cache->__right_ == nullptr)
   1169             return __cache;
   1170         return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
   1171     }
   1172     // __cache is right child
   1173     __cache->__parent_->__right_ = nullptr;
   1174     __cache = static_cast<__node_pointer>(__cache->__parent_);
   1175     if (__cache->__left_ == nullptr)
   1176         return __cache;
   1177     return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
   1178 }
   1179 
   1180 template <class _Tp, class _Compare, class _Allocator>
   1181 __tree<_Tp, _Compare, _Allocator>&
   1182 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
   1183 {
   1184     if (this != &__t)
   1185     {
   1186         value_comp() = __t.value_comp();
   1187         __copy_assign_alloc(__t);
   1188         __assign_multi(__t.begin(), __t.end());
   1189     }
   1190     return *this;
   1191 }
   1192 
   1193 template <class _Tp, class _Compare, class _Allocator>
   1194 template <class _InputIterator>
   1195 void
   1196 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last)
   1197 {
   1198     if (size() != 0)
   1199     {
   1200         __node_pointer __cache = __detach();
   1201 #ifndef _LIBCPP_NO_EXCEPTIONS
   1202         try
   1203         {
   1204 #endif  // _LIBCPP_NO_EXCEPTIONS
   1205             for (; __cache != nullptr && __first != __last; ++__first)
   1206             {
   1207                 __cache->__value_ = *__first;
   1208                 __node_pointer __next = __detach(__cache);
   1209                 __node_insert_unique(__cache);
   1210                 __cache = __next;
   1211             }
   1212 #ifndef _LIBCPP_NO_EXCEPTIONS
   1213         }
   1214         catch (...)
   1215         {
   1216             while (__cache->__parent_ != nullptr)
   1217                 __cache = static_cast<__node_pointer>(__cache->__parent_);
   1218             destroy(__cache);
   1219             throw;
   1220         }
   1221 #endif  // _LIBCPP_NO_EXCEPTIONS
   1222         if (__cache != nullptr)
   1223         {
   1224             while (__cache->__parent_ != nullptr)
   1225                 __cache = static_cast<__node_pointer>(__cache->__parent_);
   1226             destroy(__cache);
   1227         }
   1228     }
   1229     for (; __first != __last; ++__first)
   1230         __insert_unique(*__first);
   1231 }
   1232 
   1233 template <class _Tp, class _Compare, class _Allocator>
   1234 template <class _InputIterator>
   1235 void
   1236 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
   1237 {
   1238     if (size() != 0)
   1239     {
   1240         __node_pointer __cache = __detach();
   1241 #ifndef _LIBCPP_NO_EXCEPTIONS
   1242         try
   1243         {
   1244 #endif  // _LIBCPP_NO_EXCEPTIONS
   1245             for (; __cache != nullptr && __first != __last; ++__first)
   1246             {
   1247                 __cache->__value_ = *__first;
   1248                 __node_pointer __next = __detach(__cache);
   1249                 __node_insert_multi(__cache);
   1250                 __cache = __next;
   1251             }
   1252 #ifndef _LIBCPP_NO_EXCEPTIONS
   1253         }
   1254         catch (...)
   1255         {
   1256             while (__cache->__parent_ != nullptr)
   1257                 __cache = static_cast<__node_pointer>(__cache->__parent_);
   1258             destroy(__cache);
   1259             throw;
   1260         }
   1261 #endif  // _LIBCPP_NO_EXCEPTIONS
   1262         if (__cache != nullptr)
   1263         {
   1264             while (__cache->__parent_ != nullptr)
   1265                 __cache = static_cast<__node_pointer>(__cache->__parent_);
   1266             destroy(__cache);
   1267         }
   1268     }
   1269     for (; __first != __last; ++__first)
   1270         __insert_multi(*__first);
   1271 }
   1272 
   1273 template <class _Tp, class _Compare, class _Allocator>
   1274 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
   1275     : __begin_node_(__node_pointer()),
   1276       __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
   1277       __pair3_(0, __t.value_comp())
   1278 {
   1279     __begin_node() = __end_node();
   1280 }
   1281 
   1282 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
   1283 
   1284 template <class _Tp, class _Compare, class _Allocator>
   1285 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
   1286     _NOEXCEPT_(
   1287         is_nothrow_move_constructible<__node_allocator>::value &&
   1288         is_nothrow_move_constructible<value_compare>::value)
   1289     : __begin_node_(_VSTD::move(__t.__begin_node_)),
   1290       __pair1_(_VSTD::move(__t.__pair1_)),
   1291       __pair3_(_VSTD::move(__t.__pair3_))
   1292 {
   1293     if (size() == 0)
   1294         __begin_node() = __end_node();
   1295     else
   1296     {
   1297         __end_node()->__left_->__parent_ = __end_node();
   1298         __t.__begin_node() = __t.__end_node();
   1299         __t.__end_node()->__left_ = nullptr;
   1300         __t.size() = 0;
   1301     }
   1302 }
   1303 
   1304 template <class _Tp, class _Compare, class _Allocator>
   1305 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
   1306     : __pair1_(__node_allocator(__a)),
   1307       __pair3_(0, _VSTD::move(__t.value_comp()))
   1308 {
   1309     if (__a == __t.__alloc())
   1310     {
   1311         if (__t.size() == 0)
   1312             __begin_node() = __end_node();
   1313         else
   1314         {
   1315             __begin_node() = __t.__begin_node();
   1316             __end_node()->__left_ = __t.__end_node()->__left_;
   1317             __end_node()->__left_->__parent_ = __end_node();
   1318             size() = __t.size();
   1319             __t.__begin_node() = __t.__end_node();
   1320             __t.__end_node()->__left_ = nullptr;
   1321             __t.size() = 0;
   1322         }
   1323     }
   1324     else
   1325     {
   1326         __begin_node() = __end_node();
   1327     }
   1328 }
   1329 
   1330 template <class _Tp, class _Compare, class _Allocator>
   1331 void
   1332 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
   1333     _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
   1334                is_nothrow_move_assignable<__node_allocator>::value)
   1335 {
   1336     destroy(static_cast<__node_pointer>(__end_node()->__left_));
   1337     __begin_node_ = __t.__begin_node_;
   1338     __pair1_.first() = __t.__pair1_.first();
   1339     __move_assign_alloc(__t);
   1340     __pair3_ = _VSTD::move(__t.__pair3_);
   1341     if (size() == 0)
   1342         __begin_node() = __end_node();
   1343     else
   1344     {
   1345         __end_node()->__left_->__parent_ = __end_node();
   1346         __t.__begin_node() = __t.__end_node();
   1347         __t.__end_node()->__left_ = nullptr;
   1348         __t.size() = 0;
   1349     }
   1350 }
   1351 
   1352 template <class _Tp, class _Compare, class _Allocator>
   1353 void
   1354 __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
   1355 {
   1356     if (__node_alloc() == __t.__node_alloc())
   1357         __move_assign(__t, true_type());
   1358     else
   1359     {
   1360         value_comp() = _VSTD::move(__t.value_comp());
   1361         const_iterator __e = end();
   1362         if (size() != 0)
   1363         {
   1364             __node_pointer __cache = __detach();
   1365 #ifndef _LIBCPP_NO_EXCEPTIONS
   1366             try
   1367             {
   1368 #endif  // _LIBCPP_NO_EXCEPTIONS
   1369                 while (__cache != nullptr && __t.size() != 0)
   1370                 {
   1371                     __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
   1372                     __node_pointer __next = __detach(__cache);
   1373                     __node_insert_multi(__cache);
   1374                     __cache = __next;
   1375                 }
   1376 #ifndef _LIBCPP_NO_EXCEPTIONS
   1377             }
   1378             catch (...)
   1379             {
   1380                 while (__cache->__parent_ != nullptr)
   1381                     __cache = static_cast<__node_pointer>(__cache->__parent_);
   1382                 destroy(__cache);
   1383                 throw;
   1384             }
   1385 #endif  // _LIBCPP_NO_EXCEPTIONS
   1386             if (__cache != nullptr)
   1387             {
   1388                 while (__cache->__parent_ != nullptr)
   1389                     __cache = static_cast<__node_pointer>(__cache->__parent_);
   1390                 destroy(__cache);
   1391             }
   1392         }
   1393         while (__t.size() != 0)
   1394             __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_));
   1395     }
   1396 }
   1397 
   1398 template <class _Tp, class _Compare, class _Allocator>
   1399 __tree<_Tp, _Compare, _Allocator>&
   1400 __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
   1401     _NOEXCEPT_(
   1402         __node_traits::propagate_on_container_move_assignment::value &&
   1403         is_nothrow_move_assignable<value_compare>::value &&
   1404         is_nothrow_move_assignable<__node_allocator>::value)
   1405         
   1406 {
   1407     __move_assign(__t, integral_constant<bool,
   1408                   __node_traits::propagate_on_container_move_assignment::value>());
   1409     return *this;
   1410 }
   1411 
   1412 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
   1413 
   1414 template <class _Tp, class _Compare, class _Allocator>
   1415 __tree<_Tp, _Compare, _Allocator>::~__tree()
   1416 {
   1417     destroy(__root());
   1418 }
   1419 
   1420 template <class _Tp, class _Compare, class _Allocator>
   1421 void
   1422 __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
   1423 {
   1424     if (__nd != nullptr)
   1425     {
   1426         destroy(static_cast<__node_pointer>(__nd->__left_));
   1427         destroy(static_cast<__node_pointer>(__nd->__right_));
   1428         __node_allocator& __na = __node_alloc();
   1429         __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_));
   1430         __node_traits::deallocate(__na, __nd, 1);
   1431     }
   1432 }
   1433 
   1434 template <class _Tp, class _Compare, class _Allocator>
   1435 void
   1436 __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
   1437     _NOEXCEPT_(
   1438         __is_nothrow_swappable<value_compare>::value &&
   1439         (!__node_traits::propagate_on_container_swap::value ||
   1440          __is_nothrow_swappable<__node_allocator>::value))
   1441 {
   1442     using _VSTD::swap;
   1443     swap(__begin_node_, __t.__begin_node_);
   1444     swap(__pair1_.first(), __t.__pair1_.first());
   1445     __swap_alloc(__node_alloc(), __t.__node_alloc());
   1446     __pair3_.swap(__t.__pair3_);
   1447     if (size() == 0)
   1448         __begin_node() = __end_node();
   1449     else
   1450         __end_node()->__left_->__parent_ = __end_node();
   1451     if (__t.size() == 0)
   1452         __t.__begin_node() = __t.__end_node();
   1453     else
   1454         __t.__end_node()->__left_->__parent_ = __t.__end_node();
   1455 }
   1456 
   1457 template <class _Tp, class _Compare, class _Allocator>
   1458 void
   1459 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
   1460 {
   1461     destroy(__root());
   1462     size() = 0;
   1463     __begin_node() = __end_node();
   1464     __end_node()->__left_ = nullptr;
   1465 }
   1466 
   1467 // Find lower_bound place to insert
   1468 // Set __parent to parent of null leaf
   1469 // Return reference to null leaf
   1470 template <class _Tp, class _Compare, class _Allocator>
   1471 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
   1472 __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent,
   1473                                                    const value_type& __v)
   1474 {
   1475     __node_pointer __nd = __root();
   1476     if (__nd != nullptr)
   1477     {
   1478         while (true)
   1479         {
   1480             if (value_comp()(__nd->__value_, __v))
   1481             {
   1482                 if (__nd->__right_ != nullptr)
   1483                     __nd = static_cast<__node_pointer>(__nd->__right_);
   1484                 else
   1485                 {
   1486                     __parent = __nd;
   1487                     return __parent->__right_;
   1488                 }
   1489             }
   1490             else
   1491             {
   1492                 if (__nd->__left_ != nullptr)
   1493                     __nd = static_cast<__node_pointer>(__nd->__left_);
   1494                 else
   1495                 {
   1496                     __parent = __nd;
   1497                     return __parent->__left_;
   1498                 }
   1499             }
   1500         }
   1501     }
   1502     __parent = __end_node();
   1503     return __parent->__left_;
   1504 }
   1505 
   1506 // Find upper_bound place to insert
   1507 // Set __parent to parent of null leaf
   1508 // Return reference to null leaf
   1509 template <class _Tp, class _Compare, class _Allocator>
   1510 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
   1511 __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent,
   1512                                                     const value_type& __v)
   1513 {
   1514     __node_pointer __nd = __root();
   1515     if (__nd != nullptr)
   1516     {
   1517         while (true)
   1518         {
   1519             if (value_comp()(__v, __nd->__value_))
   1520             {
   1521                 if (__nd->__left_ != nullptr)
   1522                     __nd = static_cast<__node_pointer>(__nd->__left_);
   1523                 else
   1524                 {
   1525                     __parent = __nd;
   1526                     return __parent->__left_;
   1527                 }
   1528             }
   1529             else
   1530             {
   1531                 if (__nd->__right_ != nullptr)
   1532                     __nd = static_cast<__node_pointer>(__nd->__right_);
   1533                 else
   1534                 {
   1535                     __parent = __nd;
   1536                     return __parent->__right_;
   1537                 }
   1538             }
   1539         }
   1540     }
   1541     __parent = __end_node();
   1542     return __parent->__left_;
   1543 }
   1544 
   1545 // Find leaf place to insert closest to __hint
   1546 // First check prior to __hint.
   1547 // Next check after __hint.
   1548 // Next do O(log N) search.
   1549 // Set __parent to parent of null leaf
   1550 // Return reference to null leaf
   1551 template <class _Tp, class _Compare, class _Allocator>
   1552 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
   1553 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
   1554                                                typename __node_base::pointer& __parent,
   1555                                                const value_type& __v)
   1556 {
   1557     if (__hint == end() || !value_comp()(*__hint, __v))  // check before
   1558     {
   1559         // __v <= *__hint
   1560         const_iterator __prior = __hint;
   1561         if (__prior == begin() || !value_comp()(__v, *--__prior))
   1562         {
   1563             // *prev(__hint) <= __v <= *__hint
   1564             if (__hint.__ptr_->__left_ == nullptr)
   1565             {
   1566                 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
   1567                 return __parent->__left_;
   1568             }
   1569             else
   1570             {
   1571                 __parent = const_cast<__node_pointer&>(__prior.__ptr_);
   1572                 return __parent->__right_;
   1573             }
   1574         }
   1575         // __v < *prev(__hint)
   1576         return __find_leaf_high(__parent, __v);
   1577     }
   1578     // else __v > *__hint
   1579     return __find_leaf_low(__parent, __v);
   1580 }
   1581 
   1582 // Find place to insert if __v doesn't exist
   1583 // Set __parent to parent of null leaf
   1584 // Return reference to null leaf
   1585 // If __v exists, set parent to node of __v and return reference to node of __v
   1586 template <class _Tp, class _Compare, class _Allocator>
   1587 template <class _Key>
   1588 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
   1589 __tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent,
   1590                                                 const _Key& __v)
   1591 {
   1592     __node_pointer __nd = __root();
   1593     if (__nd != nullptr)
   1594     {
   1595         while (true)
   1596         {
   1597             if (value_comp()(__v, __nd->__value_))
   1598             {
   1599                 if (__nd->__left_ != nullptr)
   1600                     __nd = static_cast<__node_pointer>(__nd->__left_);
   1601                 else
   1602                 {
   1603                     __parent = __nd;
   1604                     return __parent->__left_;
   1605                 }
   1606             }
   1607             else if (value_comp()(__nd->__value_, __v))
   1608             {
   1609                 if (__nd->__right_ != nullptr)
   1610                     __nd = static_cast<__node_pointer>(__nd->__right_);
   1611                 else
   1612                 {
   1613                     __parent = __nd;
   1614                     return __parent->__right_;
   1615                 }
   1616             }
   1617             else
   1618             {
   1619                 __parent = __nd;
   1620                 return __parent;
   1621             }
   1622         }
   1623     }
   1624     __parent = __end_node();
   1625     return __parent->__left_;
   1626 }
   1627 
   1628 // Find place to insert if __v doesn't exist
   1629 // First check prior to __hint.
   1630 // Next check after __hint.
   1631 // Next do O(log N) search.
   1632 // Set __parent to parent of null leaf
   1633 // Return reference to null leaf
   1634 // If __v exists, set parent to node of __v and return reference to node of __v
   1635 template <class _Tp, class _Compare, class _Allocator>
   1636 template <class _Key>
   1637 typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
   1638 __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
   1639                                                 typename __node_base::pointer& __parent,
   1640                                                 const _Key& __v)
   1641 {
   1642     if (__hint == end() || value_comp()(__v, *__hint))  // check before
   1643     {
   1644         // __v < *__hint
   1645         const_iterator __prior = __hint;
   1646         if (__prior == begin() || value_comp()(*--__prior, __v))
   1647         {
   1648             // *prev(__hint) < __v < *__hint
   1649             if (__hint.__ptr_->__left_ == nullptr)
   1650             {
   1651                 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
   1652                 return __parent->__left_;
   1653             }
   1654             else
   1655             {
   1656                 __parent = const_cast<__node_pointer&>(__prior.__ptr_);
   1657                 return __parent->__right_;
   1658             }
   1659         }
   1660         // __v <= *prev(__hint)
   1661         return __find_equal(__parent, __v);
   1662     }
   1663     else if (value_comp()(*__hint, __v))  // check after
   1664     {
   1665         // *__hint < __v
   1666         const_iterator __next = _VSTD::next(__hint);
   1667         if (__next == end() || value_comp()(__v, *__next))
   1668         {
   1669             // *__hint < __v < *_VSTD::next(__hint)
   1670             if (__hint.__ptr_->__right_ == nullptr)
   1671             {
   1672                 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
   1673                 return __parent->__right_;
   1674             }
   1675             else
   1676             {
   1677                 __parent = const_cast<__node_pointer&>(__next.__ptr_);
   1678                 return __parent->__left_;
   1679             }
   1680         }
   1681         // *next(__hint) <= __v
   1682         return __find_equal(__parent, __v);
   1683     }
   1684     // else __v == *__hint
   1685     __parent = const_cast<__node_pointer&>(__hint.__ptr_);
   1686     return __parent;
   1687 }
   1688 
   1689 template <class _Tp, class _Compare, class _Allocator>
   1690 void
   1691 __tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent,
   1692                                                     __node_base_pointer& __child,
   1693                                                     __node_base_pointer __new_node)
   1694 {
   1695     __new_node->__left_   = nullptr;
   1696     __new_node->__right_  = nullptr;
   1697     __new_node->__parent_ = __parent;
   1698     __child = __new_node;
   1699     if (__begin_node()->__left_ != nullptr)
   1700         __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
   1701     __tree_balance_after_insert(__end_node()->__left_, __child);
   1702     ++size();
   1703 }
   1704 
   1705 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
   1706 #ifndef _LIBCPP_HAS_NO_VARIADICS
   1707 
   1708 template <class _Tp, class _Compare, class _Allocator>
   1709 template <class ..._Args>
   1710 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
   1711 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
   1712 {
   1713     __node_allocator& __na = __node_alloc();
   1714     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
   1715     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
   1716     __h.get_deleter().__value_constructed = true;
   1717     return __h;
   1718 }
   1719 
   1720 template <class _Tp, class _Compare, class _Allocator>
   1721 template <class... _Args>
   1722 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
   1723 __tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args)
   1724 {
   1725     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
   1726     __node_base_pointer __parent;
   1727     __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
   1728     __node_pointer __r = static_cast<__node_pointer>(__child);
   1729     bool __inserted = false;
   1730     if (__child == nullptr)
   1731     {
   1732         __insert_node_at(__parent, __child, __h.get());
   1733         __r = __h.release();
   1734         __inserted = true;
   1735     }
   1736     return pair<iterator, bool>(iterator(__r), __inserted);
   1737 }
   1738 
   1739 template <class _Tp, class _Compare, class _Allocator>
   1740 template <class... _Args>
   1741 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1742 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args)
   1743 {
   1744     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
   1745     __node_base_pointer __parent;
   1746     __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_);
   1747     __node_pointer __r = static_cast<__node_pointer>(__child);
   1748     if (__child == nullptr)
   1749     {
   1750         __insert_node_at(__parent, __child, __h.get());
   1751         __r = __h.release();
   1752     }
   1753     return iterator(__r);
   1754 }
   1755 
   1756 template <class _Tp, class _Compare, class _Allocator>
   1757 template <class... _Args>
   1758 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1759 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
   1760 {
   1761     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
   1762     __node_base_pointer __parent;
   1763     __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
   1764     __insert_node_at(__parent, __child, __h.get());
   1765     return iterator(static_cast<__node_pointer>(__h.release()));
   1766 }
   1767 
   1768 template <class _Tp, class _Compare, class _Allocator>
   1769 template <class... _Args>
   1770 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1771 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
   1772                                                         _Args&&... __args)
   1773 {
   1774     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
   1775     __node_base_pointer __parent;
   1776     __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
   1777     __insert_node_at(__parent, __child, __h.get());
   1778     return iterator(static_cast<__node_pointer>(__h.release()));
   1779 }
   1780 
   1781 #endif  // _LIBCPP_HAS_NO_VARIADICS
   1782 
   1783 template <class _Tp, class _Compare, class _Allocator>
   1784 template <class _Vp>
   1785 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
   1786 __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v)
   1787 {
   1788     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
   1789     pair<iterator, bool> __r = __node_insert_unique(__h.get());
   1790     if (__r.second)
   1791         __h.release();
   1792     return __r;
   1793 }
   1794 
   1795 template <class _Tp, class _Compare, class _Allocator>
   1796 template <class _Vp>
   1797 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1798 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v)
   1799 {
   1800     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
   1801     iterator __r = __node_insert_unique(__p, __h.get());
   1802     if (__r.__ptr_ == __h.get())
   1803         __h.release();
   1804     return __r;
   1805 }
   1806 
   1807 template <class _Tp, class _Compare, class _Allocator>
   1808 template <class _Vp>
   1809 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1810 __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v)
   1811 {
   1812     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
   1813     __node_base_pointer __parent;
   1814     __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
   1815     __insert_node_at(__parent, __child, __h.get());
   1816     return iterator(__h.release());
   1817 }
   1818 
   1819 template <class _Tp, class _Compare, class _Allocator>
   1820 template <class _Vp>
   1821 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1822 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v)
   1823 {
   1824     __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
   1825     __node_base_pointer __parent;
   1826     __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
   1827     __insert_node_at(__parent, __child, __h.get());
   1828     return iterator(__h.release());
   1829 }
   1830 
   1831 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
   1832 
   1833 template <class _Tp, class _Compare, class _Allocator>
   1834 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
   1835 __tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v)
   1836 {
   1837     __node_allocator& __na = __node_alloc();
   1838     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
   1839     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
   1840     __h.get_deleter().__value_constructed = true;
   1841     return _VSTD::move(__h);
   1842 }
   1843 
   1844 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
   1845 
   1846 template <class _Tp, class _Compare, class _Allocator>
   1847 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
   1848 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v)
   1849 {
   1850     __node_base_pointer __parent;
   1851     __node_base_pointer& __child = __find_equal(__parent, __v);
   1852     __node_pointer __r = static_cast<__node_pointer>(__child);
   1853     bool __inserted = false;
   1854     if (__child == nullptr)
   1855     {
   1856         __node_holder __h = __construct_node(__v);
   1857         __insert_node_at(__parent, __child, __h.get());
   1858         __r = __h.release();
   1859         __inserted = true;
   1860     }
   1861     return pair<iterator, bool>(iterator(__r), __inserted);
   1862 }
   1863 
   1864 template <class _Tp, class _Compare, class _Allocator>
   1865 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1866 __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v)
   1867 {
   1868     __node_base_pointer __parent;
   1869     __node_base_pointer& __child = __find_equal(__p, __parent, __v);
   1870     __node_pointer __r = static_cast<__node_pointer>(__child);
   1871     if (__child == nullptr)
   1872     {
   1873         __node_holder __h = __construct_node(__v);
   1874         __insert_node_at(__parent, __child, __h.get());
   1875         __r = __h.release();
   1876     }
   1877     return iterator(__r);
   1878 }
   1879 
   1880 template <class _Tp, class _Compare, class _Allocator>
   1881 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1882 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v)
   1883 {
   1884     __node_base_pointer __parent;
   1885     __node_base_pointer& __child = __find_leaf_high(__parent, __v);
   1886     __node_holder __h = __construct_node(__v);
   1887     __insert_node_at(__parent, __child, __h.get());
   1888     return iterator(__h.release());
   1889 }
   1890 
   1891 template <class _Tp, class _Compare, class _Allocator>
   1892 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1893 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v)
   1894 {
   1895     __node_base_pointer __parent;
   1896     __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
   1897     __node_holder __h = __construct_node(__v);
   1898     __insert_node_at(__parent, __child, __h.get());
   1899     return iterator(__h.release());
   1900 }
   1901 
   1902 template <class _Tp, class _Compare, class _Allocator>
   1903 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
   1904 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
   1905 {
   1906     __node_base_pointer __parent;
   1907     __node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
   1908     __node_pointer __r = static_cast<__node_pointer>(__child);
   1909     bool __inserted = false;
   1910     if (__child == nullptr)
   1911     {
   1912         __insert_node_at(__parent, __child, __nd);
   1913         __r = __nd;
   1914         __inserted = true;
   1915     }
   1916     return pair<iterator, bool>(iterator(__r), __inserted);
   1917 }
   1918 
   1919 template <class _Tp, class _Compare, class _Allocator>
   1920 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1921 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
   1922                                                         __node_pointer __nd)
   1923 {
   1924     __node_base_pointer __parent;
   1925     __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
   1926     __node_pointer __r = static_cast<__node_pointer>(__child);
   1927     if (__child == nullptr)
   1928     {
   1929         __insert_node_at(__parent, __child, __nd);
   1930         __r = __nd;
   1931     }
   1932     return iterator(__r);
   1933 }
   1934 
   1935 template <class _Tp, class _Compare, class _Allocator>
   1936 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1937 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
   1938 {
   1939     __node_base_pointer __parent;
   1940     __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_);
   1941     __insert_node_at(__parent, __child, __nd);
   1942     return iterator(__nd);
   1943 }
   1944 
   1945 template <class _Tp, class _Compare, class _Allocator>
   1946 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1947 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
   1948                                                        __node_pointer __nd)
   1949 {
   1950     __node_base_pointer __parent;
   1951     __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_);
   1952     __insert_node_at(__parent, __child, __nd);
   1953     return iterator(__nd);
   1954 }
   1955 
   1956 template <class _Tp, class _Compare, class _Allocator>
   1957 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1958 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
   1959 {
   1960     __node_pointer __np = const_cast<__node_pointer>(__p.__ptr_);
   1961     iterator __r(__np);
   1962     ++__r;
   1963     if (__begin_node() == __np)
   1964         __begin_node() = __r.__ptr_;
   1965     --size();
   1966     __node_allocator& __na = __node_alloc();
   1967     __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p)));
   1968     __tree_remove(__end_node()->__left_,
   1969                   static_cast<__node_base_pointer>(__np));
   1970     __node_traits::deallocate(__na, __np, 1);
   1971     return __r;
   1972 }
   1973 
   1974 template <class _Tp, class _Compare, class _Allocator>
   1975 typename __tree<_Tp, _Compare, _Allocator>::iterator
   1976 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
   1977 {
   1978     while (__f != __l)
   1979         __f = erase(__f);
   1980     return iterator(const_cast<__node_pointer>(__l.__ptr_));
   1981 }
   1982 
   1983 template <class _Tp, class _Compare, class _Allocator>
   1984 template <class _Key>
   1985 typename __tree<_Tp, _Compare, _Allocator>::size_type
   1986 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
   1987 {
   1988     iterator __i = find(__k);
   1989     if (__i == end())
   1990         return 0;
   1991     erase(__i);
   1992     return 1;
   1993 }
   1994 
   1995 template <class _Tp, class _Compare, class _Allocator>
   1996 template <class _Key>
   1997 typename __tree<_Tp, _Compare, _Allocator>::size_type
   1998 __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
   1999 {
   2000     pair<iterator, iterator> __p = __equal_range_multi(__k);
   2001     size_type __r = 0;
   2002     for (; __p.first != __p.second; ++__r)
   2003         __p.first = erase(__p.first);
   2004     return __r;
   2005 }
   2006 
   2007 template <class _Tp, class _Compare, class _Allocator>
   2008 template <class _Key>
   2009 typename __tree<_Tp, _Compare, _Allocator>::iterator
   2010 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
   2011 {
   2012     iterator __p = __lower_bound(__v, __root(), __end_node());
   2013     if (__p != end() && !value_comp()(__v, *__p))
   2014         return __p;
   2015     return end();
   2016 }
   2017 
   2018 template <class _Tp, class _Compare, class _Allocator>
   2019 template <class _Key>
   2020 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
   2021 __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
   2022 {
   2023     const_iterator __p = __lower_bound(__v, __root(), __end_node());
   2024     if (__p != end() && !value_comp()(__v, *__p))
   2025         return __p;
   2026     return end();
   2027 }
   2028 
   2029 template <class _Tp, class _Compare, class _Allocator>
   2030 template <class _Key>
   2031 typename __tree<_Tp, _Compare, _Allocator>::size_type
   2032 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
   2033 {
   2034     __node_const_pointer __result = __end_node();
   2035     __node_const_pointer __rt = __root();
   2036     while (__rt != nullptr)
   2037     {
   2038         if (value_comp()(__k, __rt->__value_))
   2039         {
   2040             __result = __rt;
   2041             __rt = static_cast<__node_const_pointer>(__rt->__left_);
   2042         }
   2043         else if (value_comp()(__rt->__value_, __k))
   2044             __rt = static_cast<__node_const_pointer>(__rt->__right_);
   2045         else
   2046             return 1;
   2047     }
   2048     return 0;
   2049 }
   2050 
   2051 template <class _Tp, class _Compare, class _Allocator>
   2052 template <class _Key>
   2053 typename __tree<_Tp, _Compare, _Allocator>::size_type
   2054 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
   2055 {
   2056     typedef pair<const_iterator, const_iterator> _Pp;
   2057     __node_const_pointer __result = __end_node();
   2058     __node_const_pointer __rt = __root();
   2059     while (__rt != nullptr)
   2060     {
   2061         if (value_comp()(__k, __rt->__value_))
   2062         {
   2063             __result = __rt;
   2064             __rt = static_cast<__node_const_pointer>(__rt->__left_);
   2065         }
   2066         else if (value_comp()(__rt->__value_, __k))
   2067             __rt = static_cast<__node_const_pointer>(__rt->__right_);
   2068         else
   2069             return _VSTD::distance(
   2070                 __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
   2071                 __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)
   2072             );
   2073     }
   2074     return 0;
   2075 }
   2076 
   2077 template <class _Tp, class _Compare, class _Allocator>
   2078 template <class _Key>
   2079 typename __tree<_Tp, _Compare, _Allocator>::iterator
   2080 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
   2081                                                  __node_pointer __root,
   2082                                                  __node_pointer __result)
   2083 {
   2084     while (__root != nullptr)
   2085     {
   2086         if (!value_comp()(__root->__value_, __v))
   2087         {
   2088             __result = __root;
   2089             __root = static_cast<__node_pointer>(__root->__left_);
   2090         }
   2091         else
   2092             __root = static_cast<__node_pointer>(__root->__right_);
   2093     }
   2094     return iterator(__result);
   2095 }
   2096 
   2097 template <class _Tp, class _Compare, class _Allocator>
   2098 template <class _Key>
   2099 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
   2100 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
   2101                                                  __node_const_pointer __root,
   2102                                                  __node_const_pointer __result) const
   2103 {
   2104     while (__root != nullptr)
   2105     {
   2106         if (!value_comp()(__root->__value_, __v))
   2107         {
   2108             __result = __root;
   2109             __root = static_cast<__node_const_pointer>(__root->__left_);
   2110         }
   2111         else
   2112             __root = static_cast<__node_const_pointer>(__root->__right_);
   2113     }
   2114     return const_iterator(__result);
   2115 }
   2116 
   2117 template <class _Tp, class _Compare, class _Allocator>
   2118 template <class _Key>
   2119 typename __tree<_Tp, _Compare, _Allocator>::iterator
   2120 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
   2121                                                  __node_pointer __root,
   2122                                                  __node_pointer __result)
   2123 {
   2124     while (__root != nullptr)
   2125     {
   2126         if (value_comp()(__v, __root->__value_))
   2127         {
   2128             __result = __root;
   2129             __root = static_cast<__node_pointer>(__root->__left_);
   2130         }
   2131         else
   2132             __root = static_cast<__node_pointer>(__root->__right_);
   2133     }
   2134     return iterator(__result);
   2135 }
   2136 
   2137 template <class _Tp, class _Compare, class _Allocator>
   2138 template <class _Key>
   2139 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
   2140 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
   2141                                                  __node_const_pointer __root,
   2142                                                  __node_const_pointer __result) const
   2143 {
   2144     while (__root != nullptr)
   2145     {
   2146         if (value_comp()(__v, __root->__value_))
   2147         {
   2148             __result = __root;
   2149             __root = static_cast<__node_const_pointer>(__root->__left_);
   2150         }
   2151         else
   2152             __root = static_cast<__node_const_pointer>(__root->__right_);
   2153     }
   2154     return const_iterator(__result);
   2155 }
   2156 
   2157 template <class _Tp, class _Compare, class _Allocator>
   2158 template <class _Key>
   2159 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
   2160      typename __tree<_Tp, _Compare, _Allocator>::iterator>
   2161 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
   2162 {
   2163     typedef pair<iterator, iterator> _Pp;
   2164     __node_pointer __result = __end_node();
   2165     __node_pointer __rt = __root();
   2166     while (__rt != nullptr)
   2167     {
   2168         if (value_comp()(__k, __rt->__value_))
   2169         {
   2170             __result = __rt;
   2171             __rt = static_cast<__node_pointer>(__rt->__left_);
   2172         }
   2173         else if (value_comp()(__rt->__value_, __k))
   2174             __rt = static_cast<__node_pointer>(__rt->__right_);
   2175         else
   2176             return _Pp(iterator(__rt),
   2177                       iterator(
   2178                           __rt->__right_ != nullptr ?
   2179                               static_cast<__node_pointer>(__tree_min(__rt->__right_))
   2180                             : __result));
   2181     }
   2182     return _Pp(iterator(__result), iterator(__result));
   2183 }
   2184 
   2185 template <class _Tp, class _Compare, class _Allocator>
   2186 template <class _Key>
   2187 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
   2188      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
   2189 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
   2190 {
   2191     typedef pair<const_iterator, const_iterator> _Pp;
   2192     __node_const_pointer __result = __end_node();
   2193     __node_const_pointer __rt = __root();
   2194     while (__rt != nullptr)
   2195     {
   2196         if (value_comp()(__k, __rt->__value_))
   2197         {
   2198             __result = __rt;
   2199             __rt = static_cast<__node_const_pointer>(__rt->__left_);
   2200         }
   2201         else if (value_comp()(__rt->__value_, __k))
   2202             __rt = static_cast<__node_const_pointer>(__rt->__right_);
   2203         else
   2204             return _Pp(const_iterator(__rt),
   2205                       const_iterator(
   2206                           __rt->__right_ != nullptr ?
   2207                               static_cast<__node_const_pointer>(__tree_min(__rt->__right_))
   2208                             : __result));
   2209     }
   2210     return _Pp(const_iterator(__result), const_iterator(__result));
   2211 }
   2212 
   2213 template <class _Tp, class _Compare, class _Allocator>
   2214 template <class _Key>
   2215 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
   2216      typename __tree<_Tp, _Compare, _Allocator>::iterator>
   2217 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
   2218 {
   2219     typedef pair<iterator, iterator> _Pp;
   2220     __node_pointer __result = __end_node();
   2221     __node_pointer __rt = __root();
   2222     while (__rt != nullptr)
   2223     {
   2224         if (value_comp()(__k, __rt->__value_))
   2225         {
   2226             __result = __rt;
   2227             __rt = static_cast<__node_pointer>(__rt->__left_);
   2228         }
   2229         else if (value_comp()(__rt->__value_, __k))
   2230             __rt = static_cast<__node_pointer>(__rt->__right_);
   2231         else
   2232             return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
   2233                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
   2234     }
   2235     return _Pp(iterator(__result), iterator(__result));
   2236 }
   2237 
   2238 template <class _Tp, class _Compare, class _Allocator>
   2239 template <class _Key>
   2240 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
   2241      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
   2242 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
   2243 {
   2244     typedef pair<const_iterator, const_iterator> _Pp;
   2245     __node_const_pointer __result = __end_node();
   2246     __node_const_pointer __rt = __root();
   2247     while (__rt != nullptr)
   2248     {
   2249         if (value_comp()(__k, __rt->__value_))
   2250         {
   2251             __result = __rt;
   2252             __rt = static_cast<__node_const_pointer>(__rt->__left_);
   2253         }
   2254         else if (value_comp()(__rt->__value_, __k))
   2255             __rt = static_cast<__node_const_pointer>(__rt->__right_);
   2256         else
   2257             return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
   2258                       __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result));
   2259     }
   2260     return _Pp(const_iterator(__result), const_iterator(__result));
   2261 }
   2262 
   2263 template <class _Tp, class _Compare, class _Allocator>
   2264 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
   2265 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
   2266 {
   2267     __node_pointer __np = const_cast<__node_pointer>(__p.__ptr_);
   2268     if (__begin_node() == __np)
   2269     {
   2270         if (__np->__right_ != nullptr)
   2271             __begin_node() = static_cast<__node_pointer>(__np->__right_);
   2272         else
   2273             __begin_node() = static_cast<__node_pointer>(__np->__parent_);
   2274     }
   2275     --size();
   2276     __tree_remove(__end_node()->__left_,
   2277                   static_cast<__node_base_pointer>(__np));
   2278     return __node_holder(__np, _Dp(__node_alloc()));
   2279 }
   2280 
   2281 template <class _Tp, class _Compare, class _Allocator>
   2282 inline _LIBCPP_INLINE_VISIBILITY
   2283 void
   2284 swap(__tree<_Tp, _Compare, _Allocator>& __x,
   2285      __tree<_Tp, _Compare, _Allocator>& __y)
   2286     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
   2287 {
   2288     __x.swap(__y);
   2289 }
   2290 
   2291 _LIBCPP_END_NAMESPACE_STD
   2292 
   2293 #endif  // _LIBCPP___TREE
   2294