__tree revision 262801 
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
26template <class _Tp, class _Compare, class _Allocator> class __tree;
27template <class _Tp, class _NodePtr, class _DiffType>
28    class _LIBCPP_TYPE_VIS_ONLY __tree_iterator;
29template <class _Tp, class _ConstNodePtr, class _DiffType>
30    class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
31template <class _Key, class _Tp, class _Compare, class _Allocator>
32    class _LIBCPP_TYPE_VIS_ONLY map;
33template <class _Key, class _Tp, class _Compare, class _Allocator>
34    class _LIBCPP_TYPE_VIS_ONLY multimap;
35template <class _Key, class _Compare, class _Allocator>
36    class _LIBCPP_TYPE_VIS_ONLY set;
37template <class _Key, class _Compare, class _Allocator>
38    class _LIBCPP_TYPE_VIS_ONLY multiset;
39
40/*
41
42_NodePtr algorithms
43
44The algorithms taking _NodePtr are red black tree algorithms.  Those
45algorithms taking a parameter named __root should assume that __root
46points to a proper red black tree (unless otherwise specified).
47
48Each algorithm herein assumes that __root->__parent_ points to a non-null
49structure which has a member __left_ which points back to __root.  No other
50member is read or written to at __root->__parent_.
51
52__root->__parent_ will be referred to below (in comments only) as end_node.
53end_node->__left_ is an externably accessible lvalue for __root, and can be
54changed by node insertion and removal (without explicit reference to end_node).
55
56All 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.
63template <class _NodePtr>
64inline _LIBCPP_INLINE_VISIBILITY
65bool
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.
74template <class _NodePtr>
75unsigned
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.
109template <class _NodePtr>
110bool
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.
129template <class _NodePtr>
130inline _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.
141template <class _NodePtr>
142inline _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.
153template <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.
166template <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.
179template <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
203template <class _NodePtr>
204void
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
223template <class _NodePtr>
224void
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.
248template <class _NodePtr>
249void
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.
318template <class _NodePtr>
319void
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
505template <class _Allocator> class __map_node_destructor;
506
507template <class _Allocator>
508class __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;
513public:
514    typedef typename __alloc_traits::pointer                pointer;
515private:
516
517    allocator_type& __na_;
518
519    __tree_node_destructor& operator=(const __tree_node_destructor&);
520
521public:
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
544template <class _Pointer>
545class __tree_end_node
546{
547public:
548    typedef _Pointer pointer;
549    pointer __left_;
550
551    _LIBCPP_INLINE_VISIBILITY
552    __tree_end_node() _NOEXCEPT : __left_() {}
553};
554
555template <class _VoidPtr>
556class __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&);
569public:
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
595template <class _Tp, class _VoidPtr>
596class __tree_node
597    : public __tree_node_base<_VoidPtr>
598{
599public:
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
617template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator;
618template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
619
620template <class _Tp, class _NodePtr, class _DiffType>
621class _LIBCPP_TYPE_VIS_ONLY __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;
631public:
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#if _LIBCPP_STD_VER > 11
646    : __ptr_(nullptr)
647#endif
648    {}
649
650    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
651    _LIBCPP_INLINE_VISIBILITY pointer operator->() const
652        {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
653
654    _LIBCPP_INLINE_VISIBILITY
655    __tree_iterator& operator++()
656        {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_)));
657         return *this;}
658    _LIBCPP_INLINE_VISIBILITY
659    __tree_iterator operator++(int)
660        {__tree_iterator __t(*this); ++(*this); return __t;}
661
662    _LIBCPP_INLINE_VISIBILITY
663    __tree_iterator& operator--()
664        {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_)));
665         return *this;}
666    _LIBCPP_INLINE_VISIBILITY
667    __tree_iterator operator--(int)
668        {__tree_iterator __t(*this); --(*this); return __t;}
669
670    friend _LIBCPP_INLINE_VISIBILITY 
671        bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
672        {return __x.__ptr_ == __y.__ptr_;}
673    friend _LIBCPP_INLINE_VISIBILITY
674        bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
675        {return !(__x == __y);}
676
677private:
678    _LIBCPP_INLINE_VISIBILITY
679    explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
680    template <class, class, class> friend class __tree;
681    template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
682    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator;
683    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
684    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
685    template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;
686    template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;
687};
688
689template <class _Tp, class _ConstNodePtr, class _DiffType>
690class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator
691{
692    typedef _ConstNodePtr                                         __node_pointer;
693    typedef typename pointer_traits<__node_pointer>::element_type __node;
694    typedef typename __node::base                                 __node_base;
695    typedef typename pointer_traits<__node_pointer>::template
696#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
697            rebind<__node_base>
698#else
699            rebind<__node_base>::other
700#endif
701                                                                  __node_base_pointer;
702
703    __node_pointer __ptr_;
704
705    typedef pointer_traits<__node_pointer> __pointer_traits;
706public:
707    typedef bidirectional_iterator_tag       iterator_category;
708    typedef _Tp                              value_type;
709    typedef _DiffType                        difference_type;
710    typedef const value_type&                reference;
711    typedef typename pointer_traits<__node_pointer>::template
712#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
713            rebind<const value_type>
714#else
715            rebind<const value_type>::other
716#endif
717                                       pointer;
718
719    _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT
720#if _LIBCPP_STD_VER > 11
721    : __ptr_(nullptr)
722#endif
723    {}
724
725private:
726    typedef typename remove_const<__node>::type  __non_const_node;
727    typedef typename pointer_traits<__node_pointer>::template
728#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
729            rebind<__non_const_node>
730#else
731            rebind<__non_const_node>::other
732#endif
733                                                 __non_const_node_pointer;
734    typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type>
735                                                 __non_const_iterator;
736public:
737    _LIBCPP_INLINE_VISIBILITY
738    __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
739        : __ptr_(__p.__ptr_) {}
740
741    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
742    _LIBCPP_INLINE_VISIBILITY pointer operator->() const
743        {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
744
745    _LIBCPP_INLINE_VISIBILITY
746    __tree_const_iterator& operator++()
747        {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_)));
748         return *this;}
749    _LIBCPP_INLINE_VISIBILITY
750    __tree_const_iterator operator++(int)
751        {__tree_const_iterator __t(*this); ++(*this); return __t;}
752
753    _LIBCPP_INLINE_VISIBILITY
754    __tree_const_iterator& operator--()
755        {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_)));
756         return *this;}
757    _LIBCPP_INLINE_VISIBILITY
758    __tree_const_iterator operator--(int)
759        {__tree_const_iterator __t(*this); --(*this); return __t;}
760
761    friend _LIBCPP_INLINE_VISIBILITY
762        bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
763        {return __x.__ptr_ == __y.__ptr_;}
764    friend _LIBCPP_INLINE_VISIBILITY
765        bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
766        {return !(__x == __y);}
767
768private:
769    _LIBCPP_INLINE_VISIBILITY
770    explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
771        : __ptr_(__p) {}
772    template <class, class, class> friend class __tree;
773    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
774    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
775    template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;
776    template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;
777    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
778};
779
780template <class _Tp, class _Compare, class _Allocator>
781class __tree
782{
783public:
784    typedef _Tp                                      value_type;
785    typedef _Compare                                 value_compare;
786    typedef _Allocator                               allocator_type;
787    typedef allocator_traits<allocator_type>         __alloc_traits;
788    typedef typename __alloc_traits::pointer         pointer;
789    typedef typename __alloc_traits::const_pointer   const_pointer;
790    typedef typename __alloc_traits::size_type       size_type;
791    typedef typename __alloc_traits::difference_type difference_type;
792
793    typedef typename __alloc_traits::void_pointer  __void_pointer;
794
795    typedef __tree_node<value_type, __void_pointer> __node;
796    typedef __tree_node_base<__void_pointer>        __node_base;
797    typedef typename __alloc_traits::template
798#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
799            rebind_alloc<__node>
800#else
801            rebind_alloc<__node>::other
802#endif
803                                                     __node_allocator;
804    typedef allocator_traits<__node_allocator>       __node_traits;
805    typedef typename __node_traits::pointer          __node_pointer;
806    typedef typename __node_traits::pointer          __node_const_pointer;
807    typedef typename __node_base::pointer            __node_base_pointer;
808    typedef typename __node_base::pointer            __node_base_const_pointer;
809private:
810    typedef typename __node_base::base __end_node_t;
811    typedef typename pointer_traits<__node_pointer>::template
812#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
813            rebind<__end_node_t>
814#else
815            rebind<__end_node_t>::other
816#endif
817                                                     __end_node_ptr;
818    typedef typename pointer_traits<__node_pointer>::template
819#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
820            rebind<__end_node_t>
821#else
822            rebind<__end_node_t>::other
823#endif
824                                                     __end_node_const_ptr;
825
826    __node_pointer                                          __begin_node_;
827    __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
828    __compressed_pair<size_type, value_compare>        __pair3_;
829
830public:
831    _LIBCPP_INLINE_VISIBILITY
832    __node_pointer __end_node() _NOEXCEPT
833    {
834        return static_cast<__node_pointer>
835               (
836                   pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
837               );
838    }
839    _LIBCPP_INLINE_VISIBILITY
840    __node_const_pointer __end_node() const _NOEXCEPT
841    {
842        return static_cast<__node_const_pointer>
843               (
844                   pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first()))
845               );
846    }
847    _LIBCPP_INLINE_VISIBILITY
848          __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}
849private:
850    _LIBCPP_INLINE_VISIBILITY
851    const __node_allocator& __node_alloc() const _NOEXCEPT
852        {return __pair1_.second();}
853    _LIBCPP_INLINE_VISIBILITY
854          __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
855    _LIBCPP_INLINE_VISIBILITY
856    const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
857public:
858    _LIBCPP_INLINE_VISIBILITY
859    allocator_type __alloc() const _NOEXCEPT
860        {return allocator_type(__node_alloc());}
861private:
862    _LIBCPP_INLINE_VISIBILITY
863          size_type& size() _NOEXCEPT {return __pair3_.first();}
864public:
865    _LIBCPP_INLINE_VISIBILITY
866    const size_type& size() const _NOEXCEPT {return __pair3_.first();}
867    _LIBCPP_INLINE_VISIBILITY
868          value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}
869    _LIBCPP_INLINE_VISIBILITY
870    const value_compare& value_comp() const _NOEXCEPT
871        {return __pair3_.second();}
872public:
873    _LIBCPP_INLINE_VISIBILITY
874    __node_pointer __root() _NOEXCEPT
875        {return static_cast<__node_pointer>      (__end_node()->__left_);}
876    _LIBCPP_INLINE_VISIBILITY
877    __node_const_pointer __root() const _NOEXCEPT
878        {return static_cast<__node_const_pointer>(__end_node()->__left_);}
879
880    typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
881    typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
882
883    explicit __tree(const value_compare& __comp)
884        _NOEXCEPT_(
885            is_nothrow_default_constructible<__node_allocator>::value &&
886            is_nothrow_copy_constructible<value_compare>::value);
887    explicit __tree(const allocator_type& __a);
888    __tree(const value_compare& __comp, const allocator_type& __a);
889    __tree(const __tree& __t);
890    __tree& operator=(const __tree& __t);
891    template <class _InputIterator>
892        void __assign_unique(_InputIterator __first, _InputIterator __last);
893    template <class _InputIterator>
894        void __assign_multi(_InputIterator __first, _InputIterator __last);
895#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
896    __tree(__tree&& __t)
897        _NOEXCEPT_(
898            is_nothrow_move_constructible<__node_allocator>::value &&
899            is_nothrow_move_constructible<value_compare>::value);
900    __tree(__tree&& __t, const allocator_type& __a);
901    __tree& operator=(__tree&& __t)
902        _NOEXCEPT_(
903            __node_traits::propagate_on_container_move_assignment::value &&
904            is_nothrow_move_assignable<value_compare>::value &&
905            is_nothrow_move_assignable<__node_allocator>::value);
906#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
907
908    ~__tree();
909
910    _LIBCPP_INLINE_VISIBILITY
911          iterator begin()  _NOEXCEPT {return       iterator(__begin_node());}
912    _LIBCPP_INLINE_VISIBILITY
913    const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());}
914    _LIBCPP_INLINE_VISIBILITY
915          iterator end() _NOEXCEPT {return       iterator(__end_node());}
916    _LIBCPP_INLINE_VISIBILITY
917    const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());}
918
919    _LIBCPP_INLINE_VISIBILITY
920    size_type max_size() const _NOEXCEPT
921        {return __node_traits::max_size(__node_alloc());}
922
923    void clear() _NOEXCEPT;
924
925    void swap(__tree& __t)
926        _NOEXCEPT_(
927            __is_nothrow_swappable<value_compare>::value &&
928            (!__node_traits::propagate_on_container_swap::value ||
929             __is_nothrow_swappable<__node_allocator>::value));
930
931#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
932#ifndef _LIBCPP_HAS_NO_VARIADICS
933    template <class... _Args>
934        pair<iterator, bool>
935        __emplace_unique(_Args&&... __args);
936    template <class... _Args>
937        iterator
938        __emplace_multi(_Args&&... __args);
939
940    template <class... _Args>
941        iterator
942        __emplace_hint_unique(const_iterator __p, _Args&&... __args);
943    template <class... _Args>
944        iterator
945        __emplace_hint_multi(const_iterator __p, _Args&&... __args);
946#endif  // _LIBCPP_HAS_NO_VARIADICS
947
948    template <class _Vp>
949        pair<iterator, bool> __insert_unique(_Vp&& __v);
950    template <class _Vp>
951        iterator __insert_unique(const_iterator __p, _Vp&& __v);
952    template <class _Vp>
953        iterator __insert_multi(_Vp&& __v);
954    template <class _Vp>
955        iterator __insert_multi(const_iterator __p, _Vp&& __v);
956#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
957
958    pair<iterator, bool> __insert_unique(const value_type& __v);
959    iterator __insert_unique(const_iterator __p, const value_type& __v);
960    iterator __insert_multi(const value_type& __v);
961    iterator __insert_multi(const_iterator __p, const value_type& __v);
962
963    pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
964    iterator             __node_insert_unique(const_iterator __p,
965                                              __node_pointer __nd);
966
967    iterator __node_insert_multi(__node_pointer __nd);
968    iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
969
970    iterator erase(const_iterator __p);
971    iterator erase(const_iterator __f, const_iterator __l);
972    template <class _Key>
973        size_type __erase_unique(const _Key& __k);
974    template <class _Key>
975        size_type __erase_multi(const _Key& __k);
976
977    void __insert_node_at(__node_base_pointer __parent,
978                          __node_base_pointer& __child,
979                          __node_base_pointer __new_node);
980
981    template <class _Key>
982        iterator find(const _Key& __v);
983    template <class _Key>
984        const_iterator find(const _Key& __v) const;
985
986    template <class _Key>
987        size_type __count_unique(const _Key& __k) const;
988    template <class _Key>
989        size_type __count_multi(const _Key& __k) const;
990
991    template <class _Key>
992        _LIBCPP_INLINE_VISIBILITY
993        iterator lower_bound(const _Key& __v)
994            {return __lower_bound(__v, __root(), __end_node());}
995    template <class _Key>
996        iterator __lower_bound(const _Key& __v,
997                               __node_pointer __root,
998                               __node_pointer __result);
999    template <class _Key>
1000        _LIBCPP_INLINE_VISIBILITY
1001        const_iterator lower_bound(const _Key& __v) const
1002            {return __lower_bound(__v, __root(), __end_node());}
1003    template <class _Key>
1004        const_iterator __lower_bound(const _Key& __v,
1005                                     __node_const_pointer __root,
1006                                     __node_const_pointer __result) const;
1007    template <class _Key>
1008        _LIBCPP_INLINE_VISIBILITY
1009        iterator upper_bound(const _Key& __v)
1010            {return __upper_bound(__v, __root(), __end_node());}
1011    template <class _Key>
1012        iterator __upper_bound(const _Key& __v,
1013                               __node_pointer __root,
1014                               __node_pointer __result);
1015    template <class _Key>
1016        _LIBCPP_INLINE_VISIBILITY
1017        const_iterator upper_bound(const _Key& __v) const
1018            {return __upper_bound(__v, __root(), __end_node());}
1019    template <class _Key>
1020        const_iterator __upper_bound(const _Key& __v,
1021                                     __node_const_pointer __root,
1022                                     __node_const_pointer __result) const;
1023    template <class _Key>
1024        pair<iterator, iterator>
1025        __equal_range_unique(const _Key& __k);
1026    template <class _Key>
1027        pair<const_iterator, const_iterator>
1028        __equal_range_unique(const _Key& __k) const;
1029
1030    template <class _Key>
1031        pair<iterator, iterator>
1032        __equal_range_multi(const _Key& __k);
1033    template <class _Key>
1034        pair<const_iterator, const_iterator>
1035        __equal_range_multi(const _Key& __k) const;
1036
1037    typedef __tree_node_destructor<__node_allocator> _Dp;
1038    typedef unique_ptr<__node, _Dp> __node_holder;
1039
1040    __node_holder remove(const_iterator __p) _NOEXCEPT;
1041private:
1042    typename __node_base::pointer&
1043        __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v);
1044    typename __node_base::pointer&
1045        __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v);
1046    typename __node_base::pointer&
1047        __find_leaf(const_iterator __hint,
1048                    typename __node_base::pointer& __parent, const value_type& __v);
1049    template <class _Key>
1050        typename __node_base::pointer&
1051        __find_equal(typename __node_base::pointer& __parent, const _Key& __v);
1052    template <class _Key>
1053        typename __node_base::pointer&
1054        __find_equal(const_iterator __hint, typename __node_base::pointer& __parent,
1055                     const _Key& __v);
1056
1057#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1058    template <class ..._Args>
1059        __node_holder __construct_node(_Args&& ...__args);
1060#else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1061        __node_holder __construct_node(const value_type& __v);
1062#endif
1063
1064    void destroy(__node_pointer __nd) _NOEXCEPT;
1065
1066    _LIBCPP_INLINE_VISIBILITY
1067    void __copy_assign_alloc(const __tree& __t)
1068        {__copy_assign_alloc(__t, integral_constant<bool,
1069             __node_traits::propagate_on_container_copy_assignment::value>());}
1070
1071    _LIBCPP_INLINE_VISIBILITY
1072    void __copy_assign_alloc(const __tree& __t, true_type)
1073        {__node_alloc() = __t.__node_alloc();}
1074    _LIBCPP_INLINE_VISIBILITY
1075    void __copy_assign_alloc(const __tree& __t, false_type) {}
1076
1077    void __move_assign(__tree& __t, false_type);
1078    void __move_assign(__tree& __t, true_type)
1079        _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1080                   is_nothrow_move_assignable<__node_allocator>::value);
1081
1082    _LIBCPP_INLINE_VISIBILITY
1083    void __move_assign_alloc(__tree& __t)
1084        _NOEXCEPT_(
1085            !__node_traits::propagate_on_container_move_assignment::value ||
1086            is_nothrow_move_assignable<__node_allocator>::value)
1087        {__move_assign_alloc(__t, integral_constant<bool,
1088             __node_traits::propagate_on_container_move_assignment::value>());}
1089
1090    _LIBCPP_INLINE_VISIBILITY
1091    void __move_assign_alloc(__tree& __t, true_type)
1092        _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1093        {__node_alloc() = _VSTD::move(__t.__node_alloc());}
1094    _LIBCPP_INLINE_VISIBILITY
1095    void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {}
1096
1097    _LIBCPP_INLINE_VISIBILITY
1098    static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
1099        _NOEXCEPT_(
1100            !__node_traits::propagate_on_container_swap::value ||
1101            __is_nothrow_swappable<__node_allocator>::value)
1102        {__swap_alloc(__x, __y, integral_constant<bool,
1103                      __node_traits::propagate_on_container_swap::value>());}
1104    _LIBCPP_INLINE_VISIBILITY
1105    static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type)
1106        _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
1107        {
1108            using _VSTD::swap;
1109            swap(__x, __y);
1110        }
1111    _LIBCPP_INLINE_VISIBILITY
1112    static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type)
1113        _NOEXCEPT
1114        {}
1115
1116    __node_pointer __detach();
1117    static __node_pointer __detach(__node_pointer);
1118
1119    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
1120    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
1121};
1122
1123template <class _Tp, class _Compare, class _Allocator>
1124__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
1125        _NOEXCEPT_(
1126            is_nothrow_default_constructible<__node_allocator>::value &&
1127            is_nothrow_copy_constructible<value_compare>::value)
1128    : __pair3_(0, __comp)
1129{
1130    __begin_node() = __end_node();
1131}
1132
1133template <class _Tp, class _Compare, class _Allocator>
1134__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1135    : __pair1_(__node_allocator(__a)),
1136      __begin_node_(__node_pointer()),
1137      __pair3_(0)
1138{
1139    __begin_node() = __end_node();
1140}
1141
1142template <class _Tp, class _Compare, class _Allocator>
1143__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
1144                                           const allocator_type& __a)
1145    : __pair1_(__node_allocator(__a)),
1146      __begin_node_(__node_pointer()),
1147      __pair3_(0, __comp)
1148{
1149    __begin_node() = __end_node();
1150}
1151
1152// Precondition:  size() != 0
1153template <class _Tp, class _Compare, class _Allocator>
1154typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1155__tree<_Tp, _Compare, _Allocator>::__detach()
1156{
1157    __node_pointer __cache = __begin_node();
1158    __begin_node() = __end_node();
1159    __end_node()->__left_->__parent_ = nullptr;
1160    __end_node()->__left_ = nullptr;
1161    size() = 0;
1162    // __cache->__left_ == nullptr
1163    if (__cache->__right_ != nullptr)
1164        __cache = static_cast<__node_pointer>(__cache->__right_);
1165    // __cache->__left_ == nullptr
1166    // __cache->__right_ == nullptr
1167    return __cache;
1168}
1169
1170// Precondition:  __cache != nullptr
1171//    __cache->left_ == nullptr
1172//    __cache->right_ == nullptr
1173//    This is no longer a red-black tree
1174template <class _Tp, class _Compare, class _Allocator>
1175typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1176__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache)
1177{
1178    if (__cache->__parent_ == nullptr)
1179        return nullptr;
1180    if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1181    {
1182        __cache->__parent_->__left_ = nullptr;
1183        __cache = static_cast<__node_pointer>(__cache->__parent_);
1184        if (__cache->__right_ == nullptr)
1185            return __cache;
1186        return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
1187    }
1188    // __cache is right child
1189    __cache->__parent_->__right_ = nullptr;
1190    __cache = static_cast<__node_pointer>(__cache->__parent_);
1191    if (__cache->__left_ == nullptr)
1192        return __cache;
1193    return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
1194}
1195
1196template <class _Tp, class _Compare, class _Allocator>
1197__tree<_Tp, _Compare, _Allocator>&
1198__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
1199{
1200    if (this != &__t)
1201    {
1202        value_comp() = __t.value_comp();
1203        __copy_assign_alloc(__t);
1204        __assign_multi(__t.begin(), __t.end());
1205    }
1206    return *this;
1207}
1208
1209template <class _Tp, class _Compare, class _Allocator>
1210template <class _InputIterator>
1211void
1212__tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last)
1213{
1214    if (size() != 0)
1215    {
1216        __node_pointer __cache = __detach();
1217#ifndef _LIBCPP_NO_EXCEPTIONS
1218        try
1219        {
1220#endif  // _LIBCPP_NO_EXCEPTIONS
1221            for (; __cache != nullptr && __first != __last; ++__first)
1222            {
1223                __cache->__value_ = *__first;
1224                __node_pointer __next = __detach(__cache);
1225                __node_insert_unique(__cache);
1226                __cache = __next;
1227            }
1228#ifndef _LIBCPP_NO_EXCEPTIONS
1229        }
1230        catch (...)
1231        {
1232            while (__cache->__parent_ != nullptr)
1233                __cache = static_cast<__node_pointer>(__cache->__parent_);
1234            destroy(__cache);
1235            throw;
1236        }
1237#endif  // _LIBCPP_NO_EXCEPTIONS
1238        if (__cache != nullptr)
1239        {
1240            while (__cache->__parent_ != nullptr)
1241                __cache = static_cast<__node_pointer>(__cache->__parent_);
1242            destroy(__cache);
1243        }
1244    }
1245    for (; __first != __last; ++__first)
1246        __insert_unique(*__first);
1247}
1248
1249template <class _Tp, class _Compare, class _Allocator>
1250template <class _InputIterator>
1251void
1252__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
1253{
1254    if (size() != 0)
1255    {
1256        __node_pointer __cache = __detach();
1257#ifndef _LIBCPP_NO_EXCEPTIONS
1258        try
1259        {
1260#endif  // _LIBCPP_NO_EXCEPTIONS
1261            for (; __cache != nullptr && __first != __last; ++__first)
1262            {
1263                __cache->__value_ = *__first;
1264                __node_pointer __next = __detach(__cache);
1265                __node_insert_multi(__cache);
1266                __cache = __next;
1267            }
1268#ifndef _LIBCPP_NO_EXCEPTIONS
1269        }
1270        catch (...)
1271        {
1272            while (__cache->__parent_ != nullptr)
1273                __cache = static_cast<__node_pointer>(__cache->__parent_);
1274            destroy(__cache);
1275            throw;
1276        }
1277#endif  // _LIBCPP_NO_EXCEPTIONS
1278        if (__cache != nullptr)
1279        {
1280            while (__cache->__parent_ != nullptr)
1281                __cache = static_cast<__node_pointer>(__cache->__parent_);
1282            destroy(__cache);
1283        }
1284    }
1285    for (; __first != __last; ++__first)
1286        __insert_multi(*__first);
1287}
1288
1289template <class _Tp, class _Compare, class _Allocator>
1290__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1291    : __begin_node_(__node_pointer()),
1292      __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1293      __pair3_(0, __t.value_comp())
1294{
1295    __begin_node() = __end_node();
1296}
1297
1298#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1299
1300template <class _Tp, class _Compare, class _Allocator>
1301__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
1302    _NOEXCEPT_(
1303        is_nothrow_move_constructible<__node_allocator>::value &&
1304        is_nothrow_move_constructible<value_compare>::value)
1305    : __begin_node_(_VSTD::move(__t.__begin_node_)),
1306      __pair1_(_VSTD::move(__t.__pair1_)),
1307      __pair3_(_VSTD::move(__t.__pair3_))
1308{
1309    if (size() == 0)
1310        __begin_node() = __end_node();
1311    else
1312    {
1313        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1314        __t.__begin_node() = __t.__end_node();
1315        __t.__end_node()->__left_ = nullptr;
1316        __t.size() = 0;
1317    }
1318}
1319
1320template <class _Tp, class _Compare, class _Allocator>
1321__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1322    : __pair1_(__node_allocator(__a)),
1323      __pair3_(0, _VSTD::move(__t.value_comp()))
1324{
1325    if (__a == __t.__alloc())
1326    {
1327        if (__t.size() == 0)
1328            __begin_node() = __end_node();
1329        else
1330        {
1331            __begin_node() = __t.__begin_node();
1332            __end_node()->__left_ = __t.__end_node()->__left_;
1333            __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1334            size() = __t.size();
1335            __t.__begin_node() = __t.__end_node();
1336            __t.__end_node()->__left_ = nullptr;
1337            __t.size() = 0;
1338        }
1339    }
1340    else
1341    {
1342        __begin_node() = __end_node();
1343    }
1344}
1345
1346template <class _Tp, class _Compare, class _Allocator>
1347void
1348__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1349    _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1350               is_nothrow_move_assignable<__node_allocator>::value)
1351{
1352    destroy(static_cast<__node_pointer>(__end_node()->__left_));
1353    __begin_node_ = __t.__begin_node_;
1354    __pair1_.first() = __t.__pair1_.first();
1355    __move_assign_alloc(__t);
1356    __pair3_ = _VSTD::move(__t.__pair3_);
1357    if (size() == 0)
1358        __begin_node() = __end_node();
1359    else
1360    {
1361        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1362        __t.__begin_node() = __t.__end_node();
1363        __t.__end_node()->__left_ = nullptr;
1364        __t.size() = 0;
1365    }
1366}
1367
1368template <class _Tp, class _Compare, class _Allocator>
1369void
1370__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
1371{
1372    if (__node_alloc() == __t.__node_alloc())
1373        __move_assign(__t, true_type());
1374    else
1375    {
1376        value_comp() = _VSTD::move(__t.value_comp());
1377        const_iterator __e = end();
1378        if (size() != 0)
1379        {
1380            __node_pointer __cache = __detach();
1381#ifndef _LIBCPP_NO_EXCEPTIONS
1382            try
1383            {
1384#endif  // _LIBCPP_NO_EXCEPTIONS
1385                while (__cache != nullptr && __t.size() != 0)
1386                {
1387                    __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
1388                    __node_pointer __next = __detach(__cache);
1389                    __node_insert_multi(__cache);
1390                    __cache = __next;
1391                }
1392#ifndef _LIBCPP_NO_EXCEPTIONS
1393            }
1394            catch (...)
1395            {
1396                while (__cache->__parent_ != nullptr)
1397                    __cache = static_cast<__node_pointer>(__cache->__parent_);
1398                destroy(__cache);
1399                throw;
1400            }
1401#endif  // _LIBCPP_NO_EXCEPTIONS
1402            if (__cache != nullptr)
1403            {
1404                while (__cache->__parent_ != nullptr)
1405                    __cache = static_cast<__node_pointer>(__cache->__parent_);
1406                destroy(__cache);
1407            }
1408        }
1409        while (__t.size() != 0)
1410            __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_));
1411    }
1412}
1413
1414template <class _Tp, class _Compare, class _Allocator>
1415__tree<_Tp, _Compare, _Allocator>&
1416__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1417    _NOEXCEPT_(
1418        __node_traits::propagate_on_container_move_assignment::value &&
1419        is_nothrow_move_assignable<value_compare>::value &&
1420        is_nothrow_move_assignable<__node_allocator>::value)
1421        
1422{
1423    __move_assign(__t, integral_constant<bool,
1424                  __node_traits::propagate_on_container_move_assignment::value>());
1425    return *this;
1426}
1427
1428#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1429
1430template <class _Tp, class _Compare, class _Allocator>
1431__tree<_Tp, _Compare, _Allocator>::~__tree()
1432{
1433    destroy(__root());
1434}
1435
1436template <class _Tp, class _Compare, class _Allocator>
1437void
1438__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
1439{
1440    if (__nd != nullptr)
1441    {
1442        destroy(static_cast<__node_pointer>(__nd->__left_));
1443        destroy(static_cast<__node_pointer>(__nd->__right_));
1444        __node_allocator& __na = __node_alloc();
1445        __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_));
1446        __node_traits::deallocate(__na, __nd, 1);
1447    }
1448}
1449
1450template <class _Tp, class _Compare, class _Allocator>
1451void
1452__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1453    _NOEXCEPT_(
1454        __is_nothrow_swappable<value_compare>::value &&
1455        (!__node_traits::propagate_on_container_swap::value ||
1456         __is_nothrow_swappable<__node_allocator>::value))
1457{
1458    using _VSTD::swap;
1459    swap(__begin_node_, __t.__begin_node_);
1460    swap(__pair1_.first(), __t.__pair1_.first());
1461    __swap_alloc(__node_alloc(), __t.__node_alloc());
1462    __pair3_.swap(__t.__pair3_);
1463    if (size() == 0)
1464        __begin_node() = __end_node();
1465    else
1466        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1467    if (__t.size() == 0)
1468        __t.__begin_node() = __t.__end_node();
1469    else
1470        __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
1471}
1472
1473template <class _Tp, class _Compare, class _Allocator>
1474void
1475__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
1476{
1477    destroy(__root());
1478    size() = 0;
1479    __begin_node() = __end_node();
1480    __end_node()->__left_ = nullptr;
1481}
1482
1483// Find lower_bound place to insert
1484// Set __parent to parent of null leaf
1485// Return reference to null leaf
1486template <class _Tp, class _Compare, class _Allocator>
1487typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1488__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent,
1489                                                   const value_type& __v)
1490{
1491    __node_pointer __nd = __root();
1492    if (__nd != nullptr)
1493    {
1494        while (true)
1495        {
1496            if (value_comp()(__nd->__value_, __v))
1497            {
1498                if (__nd->__right_ != nullptr)
1499                    __nd = static_cast<__node_pointer>(__nd->__right_);
1500                else
1501                {
1502                    __parent = static_cast<__node_base_pointer>(__nd);
1503                    return __parent->__right_;
1504                }
1505            }
1506            else
1507            {
1508                if (__nd->__left_ != nullptr)
1509                    __nd = static_cast<__node_pointer>(__nd->__left_);
1510                else
1511                {
1512                    __parent = static_cast<__node_base_pointer>(__nd);
1513                    return __parent->__left_;
1514                }
1515            }
1516        }
1517    }
1518    __parent = static_cast<__node_base_pointer>(__end_node());
1519    return __parent->__left_;
1520}
1521
1522// Find upper_bound place to insert
1523// Set __parent to parent of null leaf
1524// Return reference to null leaf
1525template <class _Tp, class _Compare, class _Allocator>
1526typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1527__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent,
1528                                                    const value_type& __v)
1529{
1530    __node_pointer __nd = __root();
1531    if (__nd != nullptr)
1532    {
1533        while (true)
1534        {
1535            if (value_comp()(__v, __nd->__value_))
1536            {
1537                if (__nd->__left_ != nullptr)
1538                    __nd = static_cast<__node_pointer>(__nd->__left_);
1539                else
1540                {
1541                    __parent = static_cast<__node_base_pointer>(__nd);
1542                    return __parent->__left_;
1543                }
1544            }
1545            else
1546            {
1547                if (__nd->__right_ != nullptr)
1548                    __nd = static_cast<__node_pointer>(__nd->__right_);
1549                else
1550                {
1551                    __parent = static_cast<__node_base_pointer>(__nd);
1552                    return __parent->__right_;
1553                }
1554            }
1555        }
1556    }
1557    __parent = static_cast<__node_base_pointer>(__end_node());
1558    return __parent->__left_;
1559}
1560
1561// Find leaf place to insert closest to __hint
1562// First check prior to __hint.
1563// Next check after __hint.
1564// Next do O(log N) search.
1565// Set __parent to parent of null leaf
1566// Return reference to null leaf
1567template <class _Tp, class _Compare, class _Allocator>
1568typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1569__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
1570                                               typename __node_base::pointer& __parent,
1571                                               const value_type& __v)
1572{
1573    if (__hint == end() || !value_comp()(*__hint, __v))  // check before
1574    {
1575        // __v <= *__hint
1576        const_iterator __prior = __hint;
1577        if (__prior == begin() || !value_comp()(__v, *--__prior))
1578        {
1579            // *prev(__hint) <= __v <= *__hint
1580            if (__hint.__ptr_->__left_ == nullptr)
1581            {
1582                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1583                return __parent->__left_;
1584            }
1585            else
1586            {
1587                __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
1588                return __parent->__right_;
1589            }
1590        }
1591        // __v < *prev(__hint)
1592        return __find_leaf_high(__parent, __v);
1593    }
1594    // else __v > *__hint
1595    return __find_leaf_low(__parent, __v);
1596}
1597
1598// Find place to insert if __v doesn't exist
1599// Set __parent to parent of null leaf
1600// Return reference to null leaf
1601// If __v exists, set parent to node of __v and return reference to node of __v
1602template <class _Tp, class _Compare, class _Allocator>
1603template <class _Key>
1604typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1605__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent,
1606                                                const _Key& __v)
1607{
1608    __node_pointer __nd = __root();
1609    if (__nd != nullptr)
1610    {
1611        while (true)
1612        {
1613            if (value_comp()(__v, __nd->__value_))
1614            {
1615                if (__nd->__left_ != nullptr)
1616                    __nd = static_cast<__node_pointer>(__nd->__left_);
1617                else
1618                {
1619                    __parent = static_cast<__node_base_pointer>(__nd);
1620                    return __parent->__left_;
1621                }
1622            }
1623            else if (value_comp()(__nd->__value_, __v))
1624            {
1625                if (__nd->__right_ != nullptr)
1626                    __nd = static_cast<__node_pointer>(__nd->__right_);
1627                else
1628                {
1629                    __parent = static_cast<__node_base_pointer>(__nd);
1630                    return __parent->__right_;
1631                }
1632            }
1633            else
1634            {
1635                __parent = static_cast<__node_base_pointer>(__nd);
1636                return __parent;
1637            }
1638        }
1639    }
1640    __parent = static_cast<__node_base_pointer>(__end_node());
1641    return __parent->__left_;
1642}
1643
1644// Find place to insert if __v doesn't exist
1645// First check prior to __hint.
1646// Next check after __hint.
1647// Next do O(log N) search.
1648// Set __parent to parent of null leaf
1649// Return reference to null leaf
1650// If __v exists, set parent to node of __v and return reference to node of __v
1651template <class _Tp, class _Compare, class _Allocator>
1652template <class _Key>
1653typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
1654__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
1655                                                typename __node_base::pointer& __parent,
1656                                                const _Key& __v)
1657{
1658    if (__hint == end() || value_comp()(__v, *__hint))  // check before
1659    {
1660        // __v < *__hint
1661        const_iterator __prior = __hint;
1662        if (__prior == begin() || value_comp()(*--__prior, __v))
1663        {
1664            // *prev(__hint) < __v < *__hint
1665            if (__hint.__ptr_->__left_ == nullptr)
1666            {
1667                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1668                return __parent->__left_;
1669            }
1670            else
1671            {
1672                __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
1673                return __parent->__right_;
1674            }
1675        }
1676        // __v <= *prev(__hint)
1677        return __find_equal(__parent, __v);
1678    }
1679    else if (value_comp()(*__hint, __v))  // check after
1680    {
1681        // *__hint < __v
1682        const_iterator __next = _VSTD::next(__hint);
1683        if (__next == end() || value_comp()(__v, *__next))
1684        {
1685            // *__hint < __v < *_VSTD::next(__hint)
1686            if (__hint.__ptr_->__right_ == nullptr)
1687            {
1688                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1689                return __parent->__right_;
1690            }
1691            else
1692            {
1693                __parent = static_cast<__node_base_pointer>(__next.__ptr_);
1694                return __parent->__left_;
1695            }
1696        }
1697        // *next(__hint) <= __v
1698        return __find_equal(__parent, __v);
1699    }
1700    // else __v == *__hint
1701    __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1702    return __parent;
1703}
1704
1705template <class _Tp, class _Compare, class _Allocator>
1706void
1707__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent,
1708                                                    __node_base_pointer& __child,
1709                                                    __node_base_pointer __new_node)
1710{
1711    __new_node->__left_   = nullptr;
1712    __new_node->__right_  = nullptr;
1713    __new_node->__parent_ = __parent;
1714    __child = __new_node;
1715    if (__begin_node()->__left_ != nullptr)
1716        __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
1717    __tree_balance_after_insert(__end_node()->__left_, __child);
1718    ++size();
1719}
1720
1721#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1722#ifndef _LIBCPP_HAS_NO_VARIADICS
1723
1724template <class _Tp, class _Compare, class _Allocator>
1725template <class ..._Args>
1726typename __tree<_Tp, _Compare, _Allocator>::__node_holder
1727__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
1728{
1729    __node_allocator& __na = __node_alloc();
1730    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1731    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
1732    __h.get_deleter().__value_constructed = true;
1733    return __h;
1734}
1735
1736template <class _Tp, class _Compare, class _Allocator>
1737template <class... _Args>
1738pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1739__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args)
1740{
1741    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1742    __node_base_pointer __parent;
1743    __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
1744    __node_pointer __r = static_cast<__node_pointer>(__child);
1745    bool __inserted = false;
1746    if (__child == nullptr)
1747    {
1748        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1749        __r = __h.release();
1750        __inserted = true;
1751    }
1752    return pair<iterator, bool>(iterator(__r), __inserted);
1753}
1754
1755template <class _Tp, class _Compare, class _Allocator>
1756template <class... _Args>
1757typename __tree<_Tp, _Compare, _Allocator>::iterator
1758__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args)
1759{
1760    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1761    __node_base_pointer __parent;
1762    __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_);
1763    __node_pointer __r = static_cast<__node_pointer>(__child);
1764    if (__child == nullptr)
1765    {
1766        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1767        __r = __h.release();
1768    }
1769    return iterator(__r);
1770}
1771
1772template <class _Tp, class _Compare, class _Allocator>
1773template <class... _Args>
1774typename __tree<_Tp, _Compare, _Allocator>::iterator
1775__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
1776{
1777    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1778    __node_base_pointer __parent;
1779    __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1780    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1781    return iterator(static_cast<__node_pointer>(__h.release()));
1782}
1783
1784template <class _Tp, class _Compare, class _Allocator>
1785template <class... _Args>
1786typename __tree<_Tp, _Compare, _Allocator>::iterator
1787__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
1788                                                        _Args&&... __args)
1789{
1790    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1791    __node_base_pointer __parent;
1792    __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1793    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1794    return iterator(static_cast<__node_pointer>(__h.release()));
1795}
1796
1797#endif  // _LIBCPP_HAS_NO_VARIADICS
1798
1799template <class _Tp, class _Compare, class _Allocator>
1800template <class _Vp>
1801pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1802__tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v)
1803{
1804    __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1805    pair<iterator, bool> __r = __node_insert_unique(__h.get());
1806    if (__r.second)
1807        __h.release();
1808    return __r;
1809}
1810
1811template <class _Tp, class _Compare, class _Allocator>
1812template <class _Vp>
1813typename __tree<_Tp, _Compare, _Allocator>::iterator
1814__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v)
1815{
1816    __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1817    iterator __r = __node_insert_unique(__p, __h.get());
1818    if (__r.__ptr_ == __h.get())
1819        __h.release();
1820    return __r;
1821}
1822
1823template <class _Tp, class _Compare, class _Allocator>
1824template <class _Vp>
1825typename __tree<_Tp, _Compare, _Allocator>::iterator
1826__tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v)
1827{
1828    __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1829    __node_base_pointer __parent;
1830    __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1831    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1832    return iterator(__h.release());
1833}
1834
1835template <class _Tp, class _Compare, class _Allocator>
1836template <class _Vp>
1837typename __tree<_Tp, _Compare, _Allocator>::iterator
1838__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v)
1839{
1840    __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1841    __node_base_pointer __parent;
1842    __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1843    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1844    return iterator(__h.release());
1845}
1846
1847#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1848
1849template <class _Tp, class _Compare, class _Allocator>
1850typename __tree<_Tp, _Compare, _Allocator>::__node_holder
1851__tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v)
1852{
1853    __node_allocator& __na = __node_alloc();
1854    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1855    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
1856    __h.get_deleter().__value_constructed = true;
1857    return _VSTD::move(__h);  // explicitly moved for C++03
1858}
1859
1860#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1861
1862template <class _Tp, class _Compare, class _Allocator>
1863pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1864__tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v)
1865{
1866    __node_base_pointer __parent;
1867    __node_base_pointer& __child = __find_equal(__parent, __v);
1868    __node_pointer __r = static_cast<__node_pointer>(__child);
1869    bool __inserted = false;
1870    if (__child == nullptr)
1871    {
1872        __node_holder __h = __construct_node(__v);
1873        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1874        __r = __h.release();
1875        __inserted = true;
1876    }
1877    return pair<iterator, bool>(iterator(__r), __inserted);
1878}
1879
1880template <class _Tp, class _Compare, class _Allocator>
1881typename __tree<_Tp, _Compare, _Allocator>::iterator
1882__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v)
1883{
1884    __node_base_pointer __parent;
1885    __node_base_pointer& __child = __find_equal(__p, __parent, __v);
1886    __node_pointer __r = static_cast<__node_pointer>(__child);
1887    if (__child == nullptr)
1888    {
1889        __node_holder __h = __construct_node(__v);
1890        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1891        __r = __h.release();
1892    }
1893    return iterator(__r);
1894}
1895
1896template <class _Tp, class _Compare, class _Allocator>
1897typename __tree<_Tp, _Compare, _Allocator>::iterator
1898__tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v)
1899{
1900    __node_base_pointer __parent;
1901    __node_base_pointer& __child = __find_leaf_high(__parent, __v);
1902    __node_holder __h = __construct_node(__v);
1903    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1904    return iterator(__h.release());
1905}
1906
1907template <class _Tp, class _Compare, class _Allocator>
1908typename __tree<_Tp, _Compare, _Allocator>::iterator
1909__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v)
1910{
1911    __node_base_pointer __parent;
1912    __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
1913    __node_holder __h = __construct_node(__v);
1914    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1915    return iterator(__h.release());
1916}
1917
1918template <class _Tp, class _Compare, class _Allocator>
1919pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1920__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
1921{
1922    __node_base_pointer __parent;
1923    __node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
1924    __node_pointer __r = static_cast<__node_pointer>(__child);
1925    bool __inserted = false;
1926    if (__child == nullptr)
1927    {
1928        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1929        __r = __nd;
1930        __inserted = true;
1931    }
1932    return pair<iterator, bool>(iterator(__r), __inserted);
1933}
1934
1935template <class _Tp, class _Compare, class _Allocator>
1936typename __tree<_Tp, _Compare, _Allocator>::iterator
1937__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
1938                                                        __node_pointer __nd)
1939{
1940    __node_base_pointer __parent;
1941    __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
1942    __node_pointer __r = static_cast<__node_pointer>(__child);
1943    if (__child == nullptr)
1944    {
1945        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1946        __r = __nd;
1947    }
1948    return iterator(__r);
1949}
1950
1951template <class _Tp, class _Compare, class _Allocator>
1952typename __tree<_Tp, _Compare, _Allocator>::iterator
1953__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
1954{
1955    __node_base_pointer __parent;
1956    __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_);
1957    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1958    return iterator(__nd);
1959}
1960
1961template <class _Tp, class _Compare, class _Allocator>
1962typename __tree<_Tp, _Compare, _Allocator>::iterator
1963__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
1964                                                       __node_pointer __nd)
1965{
1966    __node_base_pointer __parent;
1967    __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_);
1968    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1969    return iterator(__nd);
1970}
1971
1972template <class _Tp, class _Compare, class _Allocator>
1973typename __tree<_Tp, _Compare, _Allocator>::iterator
1974__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
1975{
1976    __node_pointer __np = __p.__ptr_;
1977    iterator __r(__np);
1978    ++__r;
1979    if (__begin_node() == __np)
1980        __begin_node() = __r.__ptr_;
1981    --size();
1982    __node_allocator& __na = __node_alloc();
1983    __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p)));
1984    __tree_remove(__end_node()->__left_,
1985                  static_cast<__node_base_pointer>(__np));
1986    __node_traits::deallocate(__na, __np, 1);
1987    return __r;
1988}
1989
1990template <class _Tp, class _Compare, class _Allocator>
1991typename __tree<_Tp, _Compare, _Allocator>::iterator
1992__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
1993{
1994    while (__f != __l)
1995        __f = erase(__f);
1996    return iterator(__l.__ptr_);
1997}
1998
1999template <class _Tp, class _Compare, class _Allocator>
2000template <class _Key>
2001typename __tree<_Tp, _Compare, _Allocator>::size_type
2002__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
2003{
2004    iterator __i = find(__k);
2005    if (__i == end())
2006        return 0;
2007    erase(__i);
2008    return 1;
2009}
2010
2011template <class _Tp, class _Compare, class _Allocator>
2012template <class _Key>
2013typename __tree<_Tp, _Compare, _Allocator>::size_type
2014__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
2015{
2016    pair<iterator, iterator> __p = __equal_range_multi(__k);
2017    size_type __r = 0;
2018    for (; __p.first != __p.second; ++__r)
2019        __p.first = erase(__p.first);
2020    return __r;
2021}
2022
2023template <class _Tp, class _Compare, class _Allocator>
2024template <class _Key>
2025typename __tree<_Tp, _Compare, _Allocator>::iterator
2026__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
2027{
2028    iterator __p = __lower_bound(__v, __root(), __end_node());
2029    if (__p != end() && !value_comp()(__v, *__p))
2030        return __p;
2031    return end();
2032}
2033
2034template <class _Tp, class _Compare, class _Allocator>
2035template <class _Key>
2036typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2037__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
2038{
2039    const_iterator __p = __lower_bound(__v, __root(), __end_node());
2040    if (__p != end() && !value_comp()(__v, *__p))
2041        return __p;
2042    return end();
2043}
2044
2045template <class _Tp, class _Compare, class _Allocator>
2046template <class _Key>
2047typename __tree<_Tp, _Compare, _Allocator>::size_type
2048__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
2049{
2050    __node_const_pointer __result = __end_node();
2051    __node_const_pointer __rt = __root();
2052    while (__rt != nullptr)
2053    {
2054        if (value_comp()(__k, __rt->__value_))
2055        {
2056            __result = __rt;
2057            __rt = static_cast<__node_const_pointer>(__rt->__left_);
2058        }
2059        else if (value_comp()(__rt->__value_, __k))
2060            __rt = static_cast<__node_const_pointer>(__rt->__right_);
2061        else
2062            return 1;
2063    }
2064    return 0;
2065}
2066
2067template <class _Tp, class _Compare, class _Allocator>
2068template <class _Key>
2069typename __tree<_Tp, _Compare, _Allocator>::size_type
2070__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
2071{
2072    typedef pair<const_iterator, const_iterator> _Pp;
2073    __node_const_pointer __result = __end_node();
2074    __node_const_pointer __rt = __root();
2075    while (__rt != nullptr)
2076    {
2077        if (value_comp()(__k, __rt->__value_))
2078        {
2079            __result = __rt;
2080            __rt = static_cast<__node_const_pointer>(__rt->__left_);
2081        }
2082        else if (value_comp()(__rt->__value_, __k))
2083            __rt = static_cast<__node_const_pointer>(__rt->__right_);
2084        else
2085            return _VSTD::distance(
2086                __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2087                __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)
2088            );
2089    }
2090    return 0;
2091}
2092
2093template <class _Tp, class _Compare, class _Allocator>
2094template <class _Key>
2095typename __tree<_Tp, _Compare, _Allocator>::iterator
2096__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2097                                                 __node_pointer __root,
2098                                                 __node_pointer __result)
2099{
2100    while (__root != nullptr)
2101    {
2102        if (!value_comp()(__root->__value_, __v))
2103        {
2104            __result = __root;
2105            __root = static_cast<__node_pointer>(__root->__left_);
2106        }
2107        else
2108            __root = static_cast<__node_pointer>(__root->__right_);
2109    }
2110    return iterator(__result);
2111}
2112
2113template <class _Tp, class _Compare, class _Allocator>
2114template <class _Key>
2115typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2116__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2117                                                 __node_const_pointer __root,
2118                                                 __node_const_pointer __result) const
2119{
2120    while (__root != nullptr)
2121    {
2122        if (!value_comp()(__root->__value_, __v))
2123        {
2124            __result = __root;
2125            __root = static_cast<__node_const_pointer>(__root->__left_);
2126        }
2127        else
2128            __root = static_cast<__node_const_pointer>(__root->__right_);
2129    }
2130    return const_iterator(__result);
2131}
2132
2133template <class _Tp, class _Compare, class _Allocator>
2134template <class _Key>
2135typename __tree<_Tp, _Compare, _Allocator>::iterator
2136__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2137                                                 __node_pointer __root,
2138                                                 __node_pointer __result)
2139{
2140    while (__root != nullptr)
2141    {
2142        if (value_comp()(__v, __root->__value_))
2143        {
2144            __result = __root;
2145            __root = static_cast<__node_pointer>(__root->__left_);
2146        }
2147        else
2148            __root = static_cast<__node_pointer>(__root->__right_);
2149    }
2150    return iterator(__result);
2151}
2152
2153template <class _Tp, class _Compare, class _Allocator>
2154template <class _Key>
2155typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2156__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2157                                                 __node_const_pointer __root,
2158                                                 __node_const_pointer __result) const
2159{
2160    while (__root != nullptr)
2161    {
2162        if (value_comp()(__v, __root->__value_))
2163        {
2164            __result = __root;
2165            __root = static_cast<__node_const_pointer>(__root->__left_);
2166        }
2167        else
2168            __root = static_cast<__node_const_pointer>(__root->__right_);
2169    }
2170    return const_iterator(__result);
2171}
2172
2173template <class _Tp, class _Compare, class _Allocator>
2174template <class _Key>
2175pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2176     typename __tree<_Tp, _Compare, _Allocator>::iterator>
2177__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
2178{
2179    typedef pair<iterator, iterator> _Pp;
2180    __node_pointer __result = __end_node();
2181    __node_pointer __rt = __root();
2182    while (__rt != nullptr)
2183    {
2184        if (value_comp()(__k, __rt->__value_))
2185        {
2186            __result = __rt;
2187            __rt = static_cast<__node_pointer>(__rt->__left_);
2188        }
2189        else if (value_comp()(__rt->__value_, __k))
2190            __rt = static_cast<__node_pointer>(__rt->__right_);
2191        else
2192            return _Pp(iterator(__rt),
2193                      iterator(
2194                          __rt->__right_ != nullptr ?
2195                              static_cast<__node_pointer>(__tree_min(__rt->__right_))
2196                            : __result));
2197    }
2198    return _Pp(iterator(__result), iterator(__result));
2199}
2200
2201template <class _Tp, class _Compare, class _Allocator>
2202template <class _Key>
2203pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2204     typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2205__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
2206{
2207    typedef pair<const_iterator, const_iterator> _Pp;
2208    __node_const_pointer __result = __end_node();
2209    __node_const_pointer __rt = __root();
2210    while (__rt != nullptr)
2211    {
2212        if (value_comp()(__k, __rt->__value_))
2213        {
2214            __result = __rt;
2215            __rt = static_cast<__node_const_pointer>(__rt->__left_);
2216        }
2217        else if (value_comp()(__rt->__value_, __k))
2218            __rt = static_cast<__node_const_pointer>(__rt->__right_);
2219        else
2220            return _Pp(const_iterator(__rt),
2221                      const_iterator(
2222                          __rt->__right_ != nullptr ?
2223                              static_cast<__node_const_pointer>(__tree_min(__rt->__right_))
2224                            : __result));
2225    }
2226    return _Pp(const_iterator(__result), const_iterator(__result));
2227}
2228
2229template <class _Tp, class _Compare, class _Allocator>
2230template <class _Key>
2231pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2232     typename __tree<_Tp, _Compare, _Allocator>::iterator>
2233__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
2234{
2235    typedef pair<iterator, iterator> _Pp;
2236    __node_pointer __result = __end_node();
2237    __node_pointer __rt = __root();
2238    while (__rt != nullptr)
2239    {
2240        if (value_comp()(__k, __rt->__value_))
2241        {
2242            __result = __rt;
2243            __rt = static_cast<__node_pointer>(__rt->__left_);
2244        }
2245        else if (value_comp()(__rt->__value_, __k))
2246            __rt = static_cast<__node_pointer>(__rt->__right_);
2247        else
2248            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
2249                      __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2250    }
2251    return _Pp(iterator(__result), iterator(__result));
2252}
2253
2254template <class _Tp, class _Compare, class _Allocator>
2255template <class _Key>
2256pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2257     typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2258__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
2259{
2260    typedef pair<const_iterator, const_iterator> _Pp;
2261    __node_const_pointer __result = __end_node();
2262    __node_const_pointer __rt = __root();
2263    while (__rt != nullptr)
2264    {
2265        if (value_comp()(__k, __rt->__value_))
2266        {
2267            __result = __rt;
2268            __rt = static_cast<__node_const_pointer>(__rt->__left_);
2269        }
2270        else if (value_comp()(__rt->__value_, __k))
2271            __rt = static_cast<__node_const_pointer>(__rt->__right_);
2272        else
2273            return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt),
2274                      __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result));
2275    }
2276    return _Pp(const_iterator(__result), const_iterator(__result));
2277}
2278
2279template <class _Tp, class _Compare, class _Allocator>
2280typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2281__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2282{
2283    __node_pointer __np = __p.__ptr_;
2284    if (__begin_node() == __np)
2285    {
2286        if (__np->__right_ != nullptr)
2287            __begin_node() = static_cast<__node_pointer>(__np->__right_);
2288        else
2289            __begin_node() = static_cast<__node_pointer>(__np->__parent_);
2290    }
2291    --size();
2292    __tree_remove(__end_node()->__left_,
2293                  static_cast<__node_base_pointer>(__np));
2294    return __node_holder(__np, _Dp(__node_alloc()));
2295}
2296
2297template <class _Tp, class _Compare, class _Allocator>
2298inline _LIBCPP_INLINE_VISIBILITY
2299void
2300swap(__tree<_Tp, _Compare, _Allocator>& __x,
2301     __tree<_Tp, _Compare, _Allocator>& __y)
2302    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2303{
2304    __x.swap(__y);
2305}
2306
2307_LIBCPP_END_NAMESPACE_STD
2308
2309#endif  // _LIBCPP___TREE
2310