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