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