xref: /freebsd/contrib/llvm-project/libcxx/include/__tree (revision 643ac419fafba89f5adda0e0ea75b538727453fb)
1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___TREE
11#define _LIBCPP___TREE
12
13#include <__config>
14#include <__utility/forward.h>
15#include <algorithm>
16#include <iterator>
17#include <limits>
18#include <memory>
19#include <stdexcept>
20
21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
22#pragma GCC system_header
23#endif
24
25_LIBCPP_PUSH_MACROS
26#include <__undef_macros>
27
28
29_LIBCPP_BEGIN_NAMESPACE_STD
30
31#if defined(__GNUC__) && !defined(__clang__) // gcc.gnu.org/PR37804
32template <class, class, class, class> class _LIBCPP_TEMPLATE_VIS map;
33template <class, class, class, class> class _LIBCPP_TEMPLATE_VIS multimap;
34template <class, class, class> class _LIBCPP_TEMPLATE_VIS set;
35template <class, class, class> class _LIBCPP_TEMPLATE_VIS multiset;
36#endif
37
38template <class _Tp, class _Compare, class _Allocator> class __tree;
39template <class _Tp, class _NodePtr, class _DiffType>
40    class _LIBCPP_TEMPLATE_VIS __tree_iterator;
41template <class _Tp, class _ConstNodePtr, class _DiffType>
42    class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
43
44template <class _Pointer> class __tree_end_node;
45template <class _VoidPtr> class __tree_node_base;
46template <class _Tp, class _VoidPtr> class __tree_node;
47
48template <class _Key, class _Value>
49struct __value_type;
50
51template <class _Allocator> class __map_node_destructor;
52template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator;
53template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
54
55/*
56
57_NodePtr algorithms
58
59The algorithms taking _NodePtr are red black tree algorithms.  Those
60algorithms taking a parameter named __root should assume that __root
61points to a proper red black tree (unless otherwise specified).
62
63Each algorithm herein assumes that __root->__parent_ points to a non-null
64structure which has a member __left_ which points back to __root.  No other
65member is read or written to at __root->__parent_.
66
67__root->__parent_ will be referred to below (in comments only) as end_node.
68end_node->__left_ is an externably accessible lvalue for __root, and can be
69changed by node insertion and removal (without explicit reference to end_node).
70
71All nodes (with the exception of end_node), even the node referred to as
72__root, have a non-null __parent_ field.
73
74*/
75
76// Returns:  true if __x is a left child of its parent, else false
77// Precondition:  __x != nullptr.
78template <class _NodePtr>
79inline _LIBCPP_INLINE_VISIBILITY
80bool
81__tree_is_left_child(_NodePtr __x) _NOEXCEPT
82{
83    return __x == __x->__parent_->__left_;
84}
85
86// Determines if the subtree rooted at __x is a proper red black subtree.  If
87//    __x is a proper subtree, returns the black height (null counts as 1).  If
88//    __x is an improper subtree, returns 0.
89template <class _NodePtr>
90unsigned
91__tree_sub_invariant(_NodePtr __x)
92{
93    if (__x == nullptr)
94        return 1;
95    // parent consistency checked by caller
96    // check __x->__left_ consistency
97    if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
98        return 0;
99    // check __x->__right_ consistency
100    if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
101        return 0;
102    // check __x->__left_ != __x->__right_ unless both are nullptr
103    if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
104        return 0;
105    // If this is red, neither child can be red
106    if (!__x->__is_black_)
107    {
108        if (__x->__left_ && !__x->__left_->__is_black_)
109            return 0;
110        if (__x->__right_ && !__x->__right_->__is_black_)
111            return 0;
112    }
113    unsigned __h = _VSTD::__tree_sub_invariant(__x->__left_);
114    if (__h == 0)
115        return 0;  // invalid left subtree
116    if (__h != _VSTD::__tree_sub_invariant(__x->__right_))
117        return 0;  // invalid or different height right subtree
118    return __h + __x->__is_black_;  // return black height of this node
119}
120
121// Determines if the red black tree rooted at __root is a proper red black tree.
122//    __root == nullptr is a proper tree.  Returns true is __root is a proper
123//    red black tree, else returns false.
124template <class _NodePtr>
125bool
126__tree_invariant(_NodePtr __root)
127{
128    if (__root == nullptr)
129        return true;
130    // check __x->__parent_ consistency
131    if (__root->__parent_ == nullptr)
132        return false;
133    if (!_VSTD::__tree_is_left_child(__root))
134        return false;
135    // root must be black
136    if (!__root->__is_black_)
137        return false;
138    // do normal node checks
139    return _VSTD::__tree_sub_invariant(__root) != 0;
140}
141
142// Returns:  pointer to the left-most node under __x.
143// Precondition:  __x != nullptr.
144template <class _NodePtr>
145inline _LIBCPP_INLINE_VISIBILITY
146_NodePtr
147__tree_min(_NodePtr __x) _NOEXCEPT
148{
149    while (__x->__left_ != nullptr)
150        __x = __x->__left_;
151    return __x;
152}
153
154// Returns:  pointer to the right-most node under __x.
155// Precondition:  __x != nullptr.
156template <class _NodePtr>
157inline _LIBCPP_INLINE_VISIBILITY
158_NodePtr
159__tree_max(_NodePtr __x) _NOEXCEPT
160{
161    while (__x->__right_ != nullptr)
162        __x = __x->__right_;
163    return __x;
164}
165
166// Returns:  pointer to the next in-order node after __x.
167// Precondition:  __x != nullptr.
168template <class _NodePtr>
169_NodePtr
170__tree_next(_NodePtr __x) _NOEXCEPT
171{
172    if (__x->__right_ != nullptr)
173        return _VSTD::__tree_min(__x->__right_);
174    while (!_VSTD::__tree_is_left_child(__x))
175        __x = __x->__parent_unsafe();
176    return __x->__parent_unsafe();
177}
178
179template <class _EndNodePtr, class _NodePtr>
180inline _LIBCPP_INLINE_VISIBILITY
181_EndNodePtr
182__tree_next_iter(_NodePtr __x) _NOEXCEPT
183{
184    if (__x->__right_ != nullptr)
185        return static_cast<_EndNodePtr>(_VSTD::__tree_min(__x->__right_));
186    while (!_VSTD::__tree_is_left_child(__x))
187        __x = __x->__parent_unsafe();
188    return static_cast<_EndNodePtr>(__x->__parent_);
189}
190
191// Returns:  pointer to the previous in-order node before __x.
192// Precondition:  __x != nullptr.
193// Note: __x may be the end node.
194template <class _NodePtr, class _EndNodePtr>
195inline _LIBCPP_INLINE_VISIBILITY
196_NodePtr
197__tree_prev_iter(_EndNodePtr __x) _NOEXCEPT
198{
199    if (__x->__left_ != nullptr)
200        return _VSTD::__tree_max(__x->__left_);
201    _NodePtr __xx = static_cast<_NodePtr>(__x);
202    while (_VSTD::__tree_is_left_child(__xx))
203        __xx = __xx->__parent_unsafe();
204    return __xx->__parent_unsafe();
205}
206
207// Returns:  pointer to a node which has no children
208// Precondition:  __x != nullptr.
209template <class _NodePtr>
210_NodePtr
211__tree_leaf(_NodePtr __x) _NOEXCEPT
212{
213    while (true)
214    {
215        if (__x->__left_ != nullptr)
216        {
217            __x = __x->__left_;
218            continue;
219        }
220        if (__x->__right_ != nullptr)
221        {
222            __x = __x->__right_;
223            continue;
224        }
225        break;
226    }
227    return __x;
228}
229
230// Effects:  Makes __x->__right_ the subtree root with __x as its left child
231//           while preserving in-order order.
232// Precondition:  __x->__right_ != nullptr
233template <class _NodePtr>
234void
235__tree_left_rotate(_NodePtr __x) _NOEXCEPT
236{
237    _NodePtr __y = __x->__right_;
238    __x->__right_ = __y->__left_;
239    if (__x->__right_ != nullptr)
240        __x->__right_->__set_parent(__x);
241    __y->__parent_ = __x->__parent_;
242    if (_VSTD::__tree_is_left_child(__x))
243        __x->__parent_->__left_ = __y;
244    else
245        __x->__parent_unsafe()->__right_ = __y;
246    __y->__left_ = __x;
247    __x->__set_parent(__y);
248}
249
250// Effects:  Makes __x->__left_ the subtree root with __x as its right child
251//           while preserving in-order order.
252// Precondition:  __x->__left_ != nullptr
253template <class _NodePtr>
254void
255__tree_right_rotate(_NodePtr __x) _NOEXCEPT
256{
257    _NodePtr __y = __x->__left_;
258    __x->__left_ = __y->__right_;
259    if (__x->__left_ != nullptr)
260        __x->__left_->__set_parent(__x);
261    __y->__parent_ = __x->__parent_;
262    if (_VSTD::__tree_is_left_child(__x))
263        __x->__parent_->__left_ = __y;
264    else
265        __x->__parent_unsafe()->__right_ = __y;
266    __y->__right_ = __x;
267    __x->__set_parent(__y);
268}
269
270// Effects:  Rebalances __root after attaching __x to a leaf.
271// Precondition:  __root != nulptr && __x != nullptr.
272//                __x has no children.
273//                __x == __root or == a direct or indirect child of __root.
274//                If __x were to be unlinked from __root (setting __root to
275//                  nullptr if __root == __x), __tree_invariant(__root) == true.
276// Postcondition: __tree_invariant(end_node->__left_) == true.  end_node->__left_
277//                may be different than the value passed in as __root.
278template <class _NodePtr>
279void
280__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
281{
282    __x->__is_black_ = __x == __root;
283    while (__x != __root && !__x->__parent_unsafe()->__is_black_)
284    {
285        // __x->__parent_ != __root because __x->__parent_->__is_black == false
286        if (_VSTD::__tree_is_left_child(__x->__parent_unsafe()))
287        {
288            _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
289            if (__y != nullptr && !__y->__is_black_)
290            {
291                __x = __x->__parent_unsafe();
292                __x->__is_black_ = true;
293                __x = __x->__parent_unsafe();
294                __x->__is_black_ = __x == __root;
295                __y->__is_black_ = true;
296            }
297            else
298            {
299                if (!_VSTD::__tree_is_left_child(__x))
300                {
301                    __x = __x->__parent_unsafe();
302                    _VSTD::__tree_left_rotate(__x);
303                }
304                __x = __x->__parent_unsafe();
305                __x->__is_black_ = true;
306                __x = __x->__parent_unsafe();
307                __x->__is_black_ = false;
308                _VSTD::__tree_right_rotate(__x);
309                break;
310            }
311        }
312        else
313        {
314            _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;
315            if (__y != nullptr && !__y->__is_black_)
316            {
317                __x = __x->__parent_unsafe();
318                __x->__is_black_ = true;
319                __x = __x->__parent_unsafe();
320                __x->__is_black_ = __x == __root;
321                __y->__is_black_ = true;
322            }
323            else
324            {
325                if (_VSTD::__tree_is_left_child(__x))
326                {
327                    __x = __x->__parent_unsafe();
328                    _VSTD::__tree_right_rotate(__x);
329                }
330                __x = __x->__parent_unsafe();
331                __x->__is_black_ = true;
332                __x = __x->__parent_unsafe();
333                __x->__is_black_ = false;
334                _VSTD::__tree_left_rotate(__x);
335                break;
336            }
337        }
338    }
339}
340
341// Precondition:  __root != nullptr && __z != nullptr.
342//                __tree_invariant(__root) == true.
343//                __z == __root or == a direct or indirect child of __root.
344// Effects:  unlinks __z from the tree rooted at __root, rebalancing as needed.
345// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_
346//                nor any of its children refer to __z.  end_node->__left_
347//                may be different than the value passed in as __root.
348template <class _NodePtr>
349void
350__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
351{
352    // __z will be removed from the tree.  Client still needs to destruct/deallocate it
353    // __y is either __z, or if __z has two children, __tree_next(__z).
354    // __y will have at most one child.
355    // __y will be the initial hole in the tree (make the hole at a leaf)
356    _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ?
357                    __z : _VSTD::__tree_next(__z);
358    // __x is __y's possibly null single child
359    _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
360    // __w is __x's possibly null uncle (will become __x's sibling)
361    _NodePtr __w = nullptr;
362    // link __x to __y's parent, and find __w
363    if (__x != nullptr)
364        __x->__parent_ = __y->__parent_;
365    if (_VSTD::__tree_is_left_child(__y))
366    {
367        __y->__parent_->__left_ = __x;
368        if (__y != __root)
369            __w = __y->__parent_unsafe()->__right_;
370        else
371            __root = __x;  // __w == nullptr
372    }
373    else
374    {
375        __y->__parent_unsafe()->__right_ = __x;
376        // __y can't be root if it is a right child
377        __w = __y->__parent_->__left_;
378    }
379    bool __removed_black = __y->__is_black_;
380    // If we didn't remove __z, do so now by splicing in __y for __z,
381    //    but copy __z's color.  This does not impact __x or __w.
382    if (__y != __z)
383    {
384        // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
385        __y->__parent_ = __z->__parent_;
386        if (_VSTD::__tree_is_left_child(__z))
387            __y->__parent_->__left_ = __y;
388        else
389            __y->__parent_unsafe()->__right_ = __y;
390        __y->__left_ = __z->__left_;
391        __y->__left_->__set_parent(__y);
392        __y->__right_ = __z->__right_;
393        if (__y->__right_ != nullptr)
394            __y->__right_->__set_parent(__y);
395        __y->__is_black_ = __z->__is_black_;
396        if (__root == __z)
397            __root = __y;
398    }
399    // There is no need to rebalance if we removed a red, or if we removed
400    //     the last node.
401    if (__removed_black && __root != nullptr)
402    {
403        // Rebalance:
404        // __x has an implicit black color (transferred from the removed __y)
405        //    associated with it, no matter what its color is.
406        // If __x is __root (in which case it can't be null), it is supposed
407        //    to be black anyway, and if it is doubly black, then the double
408        //    can just be ignored.
409        // If __x is red (in which case it can't be null), then it can absorb
410        //    the implicit black just by setting its color to black.
411        // Since __y was black and only had one child (which __x points to), __x
412        //   is either red with no children, else null, otherwise __y would have
413        //   different black heights under left and right pointers.
414        // if (__x == __root || __x != nullptr && !__x->__is_black_)
415        if (__x != nullptr)
416            __x->__is_black_ = true;
417        else
418        {
419            //  Else __x isn't root, and is "doubly black", even though it may
420            //     be null.  __w can not be null here, else the parent would
421            //     see a black height >= 2 on the __x side and a black height
422            //     of 1 on the __w side (__w must be a non-null black or a red
423            //     with a non-null black child).
424            while (true)
425            {
426                if (!_VSTD::__tree_is_left_child(__w))  // if x is left child
427                {
428                    if (!__w->__is_black_)
429                    {
430                        __w->__is_black_ = true;
431                        __w->__parent_unsafe()->__is_black_ = false;
432                        _VSTD::__tree_left_rotate(__w->__parent_unsafe());
433                        // __x is still valid
434                        // reset __root only if necessary
435                        if (__root == __w->__left_)
436                            __root = __w;
437                        // reset sibling, and it still can't be null
438                        __w = __w->__left_->__right_;
439                    }
440                    // __w->__is_black_ is now true, __w may have null children
441                    if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
442                        (__w->__right_ == nullptr || __w->__right_->__is_black_))
443                    {
444                        __w->__is_black_ = false;
445                        __x = __w->__parent_unsafe();
446                        // __x can no longer be null
447                        if (__x == __root || !__x->__is_black_)
448                        {
449                            __x->__is_black_ = true;
450                            break;
451                        }
452                        // reset sibling, and it still can't be null
453                        __w = _VSTD::__tree_is_left_child(__x) ?
454                                    __x->__parent_unsafe()->__right_ :
455                                    __x->__parent_->__left_;
456                        // continue;
457                    }
458                    else  // __w has a red child
459                    {
460                        if (__w->__right_ == nullptr || __w->__right_->__is_black_)
461                        {
462                            // __w left child is non-null and red
463                            __w->__left_->__is_black_ = true;
464                            __w->__is_black_ = false;
465                            _VSTD::__tree_right_rotate(__w);
466                            // __w is known not to be root, so root hasn't changed
467                            // reset sibling, and it still can't be null
468                            __w = __w->__parent_unsafe();
469                        }
470                        // __w has a right red child, left child may be null
471                        __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
472                        __w->__parent_unsafe()->__is_black_ = true;
473                        __w->__right_->__is_black_ = true;
474                        _VSTD::__tree_left_rotate(__w->__parent_unsafe());
475                        break;
476                    }
477                }
478                else
479                {
480                    if (!__w->__is_black_)
481                    {
482                        __w->__is_black_ = true;
483                        __w->__parent_unsafe()->__is_black_ = false;
484                        _VSTD::__tree_right_rotate(__w->__parent_unsafe());
485                        // __x is still valid
486                        // reset __root only if necessary
487                        if (__root == __w->__right_)
488                            __root = __w;
489                        // reset sibling, and it still can't be null
490                        __w = __w->__right_->__left_;
491                    }
492                    // __w->__is_black_ is now true, __w may have null children
493                    if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
494                        (__w->__right_ == nullptr || __w->__right_->__is_black_))
495                    {
496                        __w->__is_black_ = false;
497                        __x = __w->__parent_unsafe();
498                        // __x can no longer be null
499                        if (!__x->__is_black_ || __x == __root)
500                        {
501                            __x->__is_black_ = true;
502                            break;
503                        }
504                        // reset sibling, and it still can't be null
505                        __w = _VSTD::__tree_is_left_child(__x) ?
506                                    __x->__parent_unsafe()->__right_ :
507                                    __x->__parent_->__left_;
508                        // continue;
509                    }
510                    else  // __w has a red child
511                    {
512                        if (__w->__left_ == nullptr || __w->__left_->__is_black_)
513                        {
514                            // __w right child is non-null and red
515                            __w->__right_->__is_black_ = true;
516                            __w->__is_black_ = false;
517                            _VSTD::__tree_left_rotate(__w);
518                            // __w is known not to be root, so root hasn't changed
519                            // reset sibling, and it still can't be null
520                            __w = __w->__parent_unsafe();
521                        }
522                        // __w has a left red child, right child may be null
523                        __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
524                        __w->__parent_unsafe()->__is_black_ = true;
525                        __w->__left_->__is_black_ = true;
526                        _VSTD::__tree_right_rotate(__w->__parent_unsafe());
527                        break;
528                    }
529                }
530            }
531        }
532    }
533}
534
535// node traits
536
537
538template <class _Tp>
539struct __is_tree_value_type_imp : false_type {};
540
541template <class _Key, class _Value>
542struct __is_tree_value_type_imp<__value_type<_Key, _Value> > : true_type {};
543
544template <class ..._Args>
545struct __is_tree_value_type : false_type {};
546
547template <class _One>
548struct __is_tree_value_type<_One> : __is_tree_value_type_imp<typename __uncvref<_One>::type> {};
549
550template <class _Tp>
551struct __tree_key_value_types {
552  typedef _Tp key_type;
553  typedef _Tp __node_value_type;
554  typedef _Tp __container_value_type;
555  static const bool __is_map = false;
556
557  _LIBCPP_INLINE_VISIBILITY
558  static key_type const& __get_key(_Tp const& __v) {
559    return __v;
560  }
561  _LIBCPP_INLINE_VISIBILITY
562  static __container_value_type const& __get_value(__node_value_type const& __v) {
563    return __v;
564  }
565  _LIBCPP_INLINE_VISIBILITY
566  static __container_value_type* __get_ptr(__node_value_type& __n) {
567    return _VSTD::addressof(__n);
568  }
569  _LIBCPP_INLINE_VISIBILITY
570  static __container_value_type&& __move(__node_value_type& __v) {
571    return _VSTD::move(__v);
572  }
573};
574
575template <class _Key, class _Tp>
576struct __tree_key_value_types<__value_type<_Key, _Tp> > {
577  typedef _Key                                         key_type;
578  typedef _Tp                                          mapped_type;
579  typedef __value_type<_Key, _Tp>                      __node_value_type;
580  typedef pair<const _Key, _Tp>                        __container_value_type;
581  typedef __container_value_type                       __map_value_type;
582  static const bool __is_map = true;
583
584  _LIBCPP_INLINE_VISIBILITY
585  static key_type const&
586  __get_key(__node_value_type const& __t) {
587    return __t.__get_value().first;
588  }
589
590  template <class _Up>
591  _LIBCPP_INLINE_VISIBILITY
592  static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
593      key_type const&>::type
594  __get_key(_Up& __t) {
595    return __t.first;
596  }
597
598  _LIBCPP_INLINE_VISIBILITY
599  static __container_value_type const&
600  __get_value(__node_value_type const& __t) {
601    return __t.__get_value();
602  }
603
604  template <class _Up>
605  _LIBCPP_INLINE_VISIBILITY
606  static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
607      __container_value_type const&>::type
608  __get_value(_Up& __t) {
609    return __t;
610  }
611
612  _LIBCPP_INLINE_VISIBILITY
613  static __container_value_type* __get_ptr(__node_value_type& __n) {
614    return _VSTD::addressof(__n.__get_value());
615  }
616
617  _LIBCPP_INLINE_VISIBILITY
618  static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {
619    return __v.__move();
620  }
621};
622
623template <class _VoidPtr>
624struct __tree_node_base_types {
625  typedef _VoidPtr                                               __void_pointer;
626
627  typedef __tree_node_base<__void_pointer>                      __node_base_type;
628  typedef typename __rebind_pointer<_VoidPtr, __node_base_type>::type
629                                                             __node_base_pointer;
630
631  typedef __tree_end_node<__node_base_pointer>                  __end_node_type;
632  typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type
633                                                             __end_node_pointer;
634#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)
635  typedef __end_node_pointer __parent_pointer;
636#else
637  typedef typename conditional<
638      is_pointer<__end_node_pointer>::value,
639        __end_node_pointer,
640        __node_base_pointer>::type __parent_pointer;
641#endif
642
643private:
644  static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
645                  "_VoidPtr does not point to unqualified void type");
646};
647
648template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>,
649         bool = _KVTypes::__is_map>
650struct __tree_map_pointer_types {};
651
652template <class _Tp, class _AllocPtr, class _KVTypes>
653struct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
654  typedef typename _KVTypes::__map_value_type   _Mv;
655  typedef typename __rebind_pointer<_AllocPtr, _Mv>::type
656                                                       __map_value_type_pointer;
657  typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type
658                                                 __const_map_value_type_pointer;
659};
660
661template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
662struct __tree_node_types;
663
664template <class _NodePtr, class _Tp, class _VoidPtr>
665struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> >
666    : public __tree_node_base_types<_VoidPtr>,
667             __tree_key_value_types<_Tp>,
668             __tree_map_pointer_types<_Tp, _VoidPtr>
669{
670  typedef __tree_node_base_types<_VoidPtr> __base;
671  typedef __tree_key_value_types<_Tp>      __key_base;
672  typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base;
673public:
674
675  typedef typename pointer_traits<_NodePtr>::element_type       __node_type;
676  typedef _NodePtr                                              __node_pointer;
677
678  typedef _Tp                                                 __node_value_type;
679  typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type
680                                                      __node_value_type_pointer;
681  typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
682                                                __const_node_value_type_pointer;
683#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)
684  typedef typename __base::__end_node_pointer __iter_pointer;
685#else
686  typedef typename conditional<
687      is_pointer<__node_pointer>::value,
688        typename __base::__end_node_pointer,
689        __node_pointer>::type __iter_pointer;
690#endif
691private:
692    static_assert(!is_const<__node_type>::value,
693                "_NodePtr should never be a pointer to const");
694    static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
695                          _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
696};
697
698template <class _ValueTp, class _VoidPtr>
699struct __make_tree_node_types {
700  typedef typename __rebind_pointer<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> >::type
701                                                                        _NodePtr;
702  typedef __tree_node_types<_NodePtr> type;
703};
704
705// node
706
707template <class _Pointer>
708class __tree_end_node
709{
710public:
711    typedef _Pointer pointer;
712    pointer __left_;
713
714    _LIBCPP_INLINE_VISIBILITY
715    __tree_end_node() _NOEXCEPT : __left_() {}
716};
717
718template <class _VoidPtr>
719class _LIBCPP_STANDALONE_DEBUG __tree_node_base
720    : public __tree_node_base_types<_VoidPtr>::__end_node_type
721{
722    typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes;
723
724public:
725    typedef typename _NodeBaseTypes::__node_base_pointer pointer;
726    typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer;
727
728    pointer          __right_;
729    __parent_pointer __parent_;
730    bool __is_black_;
731
732    _LIBCPP_INLINE_VISIBILITY
733    pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);}
734
735    _LIBCPP_INLINE_VISIBILITY
736    void __set_parent(pointer __p) {
737        __parent_ = static_cast<__parent_pointer>(__p);
738    }
739
740private:
741  ~__tree_node_base() = delete;
742  __tree_node_base(__tree_node_base const&) = delete;
743  __tree_node_base& operator=(__tree_node_base const&) = delete;
744};
745
746template <class _Tp, class _VoidPtr>
747class _LIBCPP_STANDALONE_DEBUG __tree_node
748    : public __tree_node_base<_VoidPtr>
749{
750public:
751    typedef _Tp __node_value_type;
752
753    __node_value_type __value_;
754
755private:
756  ~__tree_node() = delete;
757  __tree_node(__tree_node const&) = delete;
758  __tree_node& operator=(__tree_node const&) = delete;
759};
760
761
762template <class _Allocator>
763class __tree_node_destructor
764{
765    typedef _Allocator                                      allocator_type;
766    typedef allocator_traits<allocator_type>                __alloc_traits;
767
768public:
769    typedef typename __alloc_traits::pointer                pointer;
770private:
771    typedef __tree_node_types<pointer> _NodeTypes;
772    allocator_type& __na_;
773
774
775public:
776    bool __value_constructed;
777
778
779    __tree_node_destructor(const __tree_node_destructor &) = default;
780    __tree_node_destructor& operator=(const __tree_node_destructor&) = delete;
781
782    _LIBCPP_INLINE_VISIBILITY
783    explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT
784        : __na_(__na),
785          __value_constructed(__val)
786        {}
787
788    _LIBCPP_INLINE_VISIBILITY
789    void operator()(pointer __p) _NOEXCEPT
790    {
791        if (__value_constructed)
792            __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
793        if (__p)
794            __alloc_traits::deallocate(__na_, __p, 1);
795    }
796
797    template <class> friend class __map_node_destructor;
798};
799
800#if _LIBCPP_STD_VER > 14
801template <class _NodeType, class _Alloc>
802struct __generic_container_node_destructor;
803template <class _Tp, class _VoidPtr, class _Alloc>
804struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>
805    : __tree_node_destructor<_Alloc>
806{
807    using __tree_node_destructor<_Alloc>::__tree_node_destructor;
808};
809#endif
810
811template <class _Tp, class _NodePtr, class _DiffType>
812class _LIBCPP_TEMPLATE_VIS __tree_iterator
813{
814    typedef __tree_node_types<_NodePtr>                     _NodeTypes;
815    typedef _NodePtr                                        __node_pointer;
816    typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
817    typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
818    typedef typename _NodeTypes::__iter_pointer             __iter_pointer;
819    typedef pointer_traits<__node_pointer> __pointer_traits;
820
821    __iter_pointer __ptr_;
822
823public:
824    typedef bidirectional_iterator_tag                     iterator_category;
825    typedef _Tp                                            value_type;
826    typedef _DiffType                                      difference_type;
827    typedef value_type&                                    reference;
828    typedef typename _NodeTypes::__node_value_type_pointer pointer;
829
830    _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT
831#if _LIBCPP_STD_VER > 11
832    : __ptr_(nullptr)
833#endif
834    {}
835
836    _LIBCPP_INLINE_VISIBILITY reference operator*() const
837        {return __get_np()->__value_;}
838    _LIBCPP_INLINE_VISIBILITY pointer operator->() const
839        {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
840
841    _LIBCPP_INLINE_VISIBILITY
842    __tree_iterator& operator++() {
843      __ptr_ = static_cast<__iter_pointer>(
844          _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
845      return *this;
846    }
847    _LIBCPP_INLINE_VISIBILITY
848    __tree_iterator operator++(int)
849        {__tree_iterator __t(*this); ++(*this); return __t;}
850
851    _LIBCPP_INLINE_VISIBILITY
852    __tree_iterator& operator--() {
853      __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>(
854          static_cast<__end_node_pointer>(__ptr_)));
855      return *this;
856    }
857    _LIBCPP_INLINE_VISIBILITY
858    __tree_iterator operator--(int)
859        {__tree_iterator __t(*this); --(*this); return __t;}
860
861    friend _LIBCPP_INLINE_VISIBILITY
862        bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
863        {return __x.__ptr_ == __y.__ptr_;}
864    friend _LIBCPP_INLINE_VISIBILITY
865        bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
866        {return !(__x == __y);}
867
868private:
869    _LIBCPP_INLINE_VISIBILITY
870    explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
871    _LIBCPP_INLINE_VISIBILITY
872    explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
873    _LIBCPP_INLINE_VISIBILITY
874    __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
875    template <class, class, class> friend class __tree;
876    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
877    template <class> friend class _LIBCPP_TEMPLATE_VIS __map_iterator;
878    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
879    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
880    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
881    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
882};
883
884template <class _Tp, class _NodePtr, class _DiffType>
885class _LIBCPP_TEMPLATE_VIS __tree_const_iterator
886{
887    typedef __tree_node_types<_NodePtr>                     _NodeTypes;
888    typedef typename _NodeTypes::__node_pointer             __node_pointer;
889    typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
890    typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
891    typedef typename _NodeTypes::__iter_pointer             __iter_pointer;
892    typedef pointer_traits<__node_pointer> __pointer_traits;
893
894    __iter_pointer __ptr_;
895
896public:
897    typedef bidirectional_iterator_tag                           iterator_category;
898    typedef _Tp                                                  value_type;
899    typedef _DiffType                                            difference_type;
900    typedef const value_type&                                    reference;
901    typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
902
903    _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT
904#if _LIBCPP_STD_VER > 11
905    : __ptr_(nullptr)
906#endif
907    {}
908
909private:
910    typedef __tree_iterator<value_type, __node_pointer, difference_type>
911                                                           __non_const_iterator;
912public:
913    _LIBCPP_INLINE_VISIBILITY
914    __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
915        : __ptr_(__p.__ptr_) {}
916
917    _LIBCPP_INLINE_VISIBILITY reference operator*() const
918        {return __get_np()->__value_;}
919    _LIBCPP_INLINE_VISIBILITY pointer operator->() const
920        {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
921
922    _LIBCPP_INLINE_VISIBILITY
923    __tree_const_iterator& operator++() {
924      __ptr_ = static_cast<__iter_pointer>(
925          _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
926      return *this;
927    }
928
929    _LIBCPP_INLINE_VISIBILITY
930    __tree_const_iterator operator++(int)
931        {__tree_const_iterator __t(*this); ++(*this); return __t;}
932
933    _LIBCPP_INLINE_VISIBILITY
934    __tree_const_iterator& operator--() {
935      __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>(
936          static_cast<__end_node_pointer>(__ptr_)));
937      return *this;
938    }
939
940    _LIBCPP_INLINE_VISIBILITY
941    __tree_const_iterator operator--(int)
942        {__tree_const_iterator __t(*this); --(*this); return __t;}
943
944    friend _LIBCPP_INLINE_VISIBILITY
945        bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
946        {return __x.__ptr_ == __y.__ptr_;}
947    friend _LIBCPP_INLINE_VISIBILITY
948        bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
949        {return !(__x == __y);}
950
951private:
952    _LIBCPP_INLINE_VISIBILITY
953    explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
954        : __ptr_(__p) {}
955    _LIBCPP_INLINE_VISIBILITY
956    explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT
957        : __ptr_(__p) {}
958    _LIBCPP_INLINE_VISIBILITY
959    __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
960
961    template <class, class, class> friend class __tree;
962    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
963    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
964    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
965    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
966    template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
967
968};
969
970template<class _Tp, class _Compare>
971#ifndef _LIBCPP_CXX03_LANG
972    _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value,
973        "the specified comparator type does not provide a viable const call operator")
974#endif
975int __diagnose_non_const_comparator();
976
977template <class _Tp, class _Compare, class _Allocator>
978class __tree
979{
980public:
981    typedef _Tp                                      value_type;
982    typedef _Compare                                 value_compare;
983    typedef _Allocator                               allocator_type;
984
985private:
986    typedef allocator_traits<allocator_type>         __alloc_traits;
987    typedef typename __make_tree_node_types<value_type,
988        typename __alloc_traits::void_pointer>::type
989                                                    _NodeTypes;
990    typedef typename _NodeTypes::key_type           key_type;
991public:
992    typedef typename _NodeTypes::__node_value_type      __node_value_type;
993    typedef typename _NodeTypes::__container_value_type __container_value_type;
994
995    typedef typename __alloc_traits::pointer         pointer;
996    typedef typename __alloc_traits::const_pointer   const_pointer;
997    typedef typename __alloc_traits::size_type       size_type;
998    typedef typename __alloc_traits::difference_type difference_type;
999
1000public:
1001    typedef typename _NodeTypes::__void_pointer        __void_pointer;
1002
1003    typedef typename _NodeTypes::__node_type           __node;
1004    typedef typename _NodeTypes::__node_pointer        __node_pointer;
1005
1006    typedef typename _NodeTypes::__node_base_type      __node_base;
1007    typedef typename _NodeTypes::__node_base_pointer   __node_base_pointer;
1008
1009    typedef typename _NodeTypes::__end_node_type       __end_node_t;
1010    typedef typename _NodeTypes::__end_node_pointer    __end_node_ptr;
1011
1012    typedef typename _NodeTypes::__parent_pointer      __parent_pointer;
1013    typedef typename _NodeTypes::__iter_pointer        __iter_pointer;
1014
1015    typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
1016    typedef allocator_traits<__node_allocator>         __node_traits;
1017
1018private:
1019    // check for sane allocator pointer rebinding semantics. Rebinding the
1020    // allocator for a new pointer type should be exactly the same as rebinding
1021    // the pointer using 'pointer_traits'.
1022    static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
1023                  "Allocator does not rebind pointers in a sane manner.");
1024    typedef typename __rebind_alloc_helper<__node_traits, __node_base>::type
1025        __node_base_allocator;
1026    typedef allocator_traits<__node_base_allocator> __node_base_traits;
1027    static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
1028                 "Allocator does not rebind pointers in a sane manner.");
1029
1030private:
1031    __iter_pointer                                     __begin_node_;
1032    __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
1033    __compressed_pair<size_type, value_compare>        __pair3_;
1034
1035public:
1036    _LIBCPP_INLINE_VISIBILITY
1037    __iter_pointer __end_node() _NOEXCEPT
1038    {
1039        return static_cast<__iter_pointer>(
1040                pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
1041        );
1042    }
1043    _LIBCPP_INLINE_VISIBILITY
1044    __iter_pointer __end_node() const _NOEXCEPT
1045    {
1046        return static_cast<__iter_pointer>(
1047            pointer_traits<__end_node_ptr>::pointer_to(
1048                const_cast<__end_node_t&>(__pair1_.first())
1049            )
1050        );
1051    }
1052    _LIBCPP_INLINE_VISIBILITY
1053          __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}
1054private:
1055    _LIBCPP_INLINE_VISIBILITY
1056    const __node_allocator& __node_alloc() const _NOEXCEPT
1057        {return __pair1_.second();}
1058    _LIBCPP_INLINE_VISIBILITY
1059          __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
1060    _LIBCPP_INLINE_VISIBILITY
1061    const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
1062public:
1063    _LIBCPP_INLINE_VISIBILITY
1064    allocator_type __alloc() const _NOEXCEPT
1065        {return allocator_type(__node_alloc());}
1066private:
1067    _LIBCPP_INLINE_VISIBILITY
1068          size_type& size() _NOEXCEPT {return __pair3_.first();}
1069public:
1070    _LIBCPP_INLINE_VISIBILITY
1071    const size_type& size() const _NOEXCEPT {return __pair3_.first();}
1072    _LIBCPP_INLINE_VISIBILITY
1073          value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}
1074    _LIBCPP_INLINE_VISIBILITY
1075    const value_compare& value_comp() const _NOEXCEPT
1076        {return __pair3_.second();}
1077public:
1078
1079    _LIBCPP_INLINE_VISIBILITY
1080    __node_pointer __root() const _NOEXCEPT
1081        {return static_cast<__node_pointer>(__end_node()->__left_);}
1082
1083    __node_base_pointer* __root_ptr() const _NOEXCEPT {
1084        return _VSTD::addressof(__end_node()->__left_);
1085    }
1086
1087    typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
1088    typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
1089
1090    explicit __tree(const value_compare& __comp)
1091        _NOEXCEPT_(
1092            is_nothrow_default_constructible<__node_allocator>::value &&
1093            is_nothrow_copy_constructible<value_compare>::value);
1094    explicit __tree(const allocator_type& __a);
1095    __tree(const value_compare& __comp, const allocator_type& __a);
1096    __tree(const __tree& __t);
1097    __tree& operator=(const __tree& __t);
1098    template <class _ForwardIterator>
1099        void __assign_unique(_ForwardIterator __first, _ForwardIterator __last);
1100    template <class _InputIterator>
1101        void __assign_multi(_InputIterator __first, _InputIterator __last);
1102    __tree(__tree&& __t)
1103        _NOEXCEPT_(
1104            is_nothrow_move_constructible<__node_allocator>::value &&
1105            is_nothrow_move_constructible<value_compare>::value);
1106    __tree(__tree&& __t, const allocator_type& __a);
1107    __tree& operator=(__tree&& __t)
1108        _NOEXCEPT_(
1109            __node_traits::propagate_on_container_move_assignment::value &&
1110            is_nothrow_move_assignable<value_compare>::value &&
1111            is_nothrow_move_assignable<__node_allocator>::value);
1112    ~__tree();
1113
1114    _LIBCPP_INLINE_VISIBILITY
1115          iterator begin()  _NOEXCEPT {return       iterator(__begin_node());}
1116    _LIBCPP_INLINE_VISIBILITY
1117    const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());}
1118    _LIBCPP_INLINE_VISIBILITY
1119          iterator end() _NOEXCEPT {return       iterator(__end_node());}
1120    _LIBCPP_INLINE_VISIBILITY
1121    const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());}
1122
1123    _LIBCPP_INLINE_VISIBILITY
1124    size_type max_size() const _NOEXCEPT
1125        {return _VSTD::min<size_type>(
1126                __node_traits::max_size(__node_alloc()),
1127                numeric_limits<difference_type >::max());}
1128
1129    void clear() _NOEXCEPT;
1130
1131    void swap(__tree& __t)
1132#if _LIBCPP_STD_VER <= 11
1133        _NOEXCEPT_(
1134            __is_nothrow_swappable<value_compare>::value
1135            && (!__node_traits::propagate_on_container_swap::value ||
1136                 __is_nothrow_swappable<__node_allocator>::value)
1137            );
1138#else
1139        _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value);
1140#endif
1141
1142    template <class _Key, class ..._Args>
1143    pair<iterator, bool>
1144    __emplace_unique_key_args(_Key const&, _Args&&... __args);
1145    template <class _Key, class ..._Args>
1146    pair<iterator, bool>
1147    __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
1148
1149    template <class... _Args>
1150    pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
1151
1152    template <class... _Args>
1153    iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
1154
1155    template <class... _Args>
1156    iterator __emplace_multi(_Args&&... __args);
1157
1158    template <class... _Args>
1159    iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1160
1161    template <class _Pp>
1162    _LIBCPP_INLINE_VISIBILITY
1163    pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1164        return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1165                                            __can_extract_key<_Pp, key_type>());
1166    }
1167
1168    template <class _First, class _Second>
1169    _LIBCPP_INLINE_VISIBILITY
1170    typename enable_if<
1171        __can_extract_map_key<_First, key_type, __container_value_type>::value,
1172        pair<iterator, bool>
1173    >::type __emplace_unique(_First&& __f, _Second&& __s) {
1174        return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
1175                                              _VSTD::forward<_Second>(__s));
1176    }
1177
1178    template <class... _Args>
1179    _LIBCPP_INLINE_VISIBILITY
1180    pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1181        return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1182    }
1183
1184    template <class _Pp>
1185    _LIBCPP_INLINE_VISIBILITY
1186    pair<iterator, bool>
1187    __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1188      return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1189    }
1190
1191    template <class _Pp>
1192    _LIBCPP_INLINE_VISIBILITY
1193    pair<iterator, bool>
1194    __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1195      return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1196    }
1197
1198    template <class _Pp>
1199    _LIBCPP_INLINE_VISIBILITY
1200    pair<iterator, bool>
1201    __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1202      return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1203    }
1204
1205    template <class _Pp>
1206    _LIBCPP_INLINE_VISIBILITY
1207    iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
1208        return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
1209                                            __can_extract_key<_Pp, key_type>());
1210    }
1211
1212    template <class _First, class _Second>
1213    _LIBCPP_INLINE_VISIBILITY
1214    typename enable_if<
1215        __can_extract_map_key<_First, key_type, __container_value_type>::value,
1216        iterator
1217    >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
1218        return __emplace_hint_unique_key_args(__p, __f,
1219                                              _VSTD::forward<_First>(__f),
1220                                              _VSTD::forward<_Second>(__s)).first;
1221    }
1222
1223    template <class... _Args>
1224    _LIBCPP_INLINE_VISIBILITY
1225    iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
1226        return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...);
1227    }
1228
1229    template <class _Pp>
1230    _LIBCPP_INLINE_VISIBILITY
1231    iterator
1232    __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
1233      return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
1234    }
1235
1236    template <class _Pp>
1237    _LIBCPP_INLINE_VISIBILITY
1238    iterator
1239    __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
1240      return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first;
1241    }
1242
1243    template <class _Pp>
1244    _LIBCPP_INLINE_VISIBILITY
1245    iterator
1246    __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
1247      return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first;
1248    }
1249
1250    _LIBCPP_INLINE_VISIBILITY
1251    pair<iterator, bool> __insert_unique(const __container_value_type& __v) {
1252        return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v);
1253    }
1254
1255    _LIBCPP_INLINE_VISIBILITY
1256    iterator __insert_unique(const_iterator __p, const __container_value_type& __v) {
1257        return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first;
1258    }
1259
1260    _LIBCPP_INLINE_VISIBILITY
1261    pair<iterator, bool> __insert_unique(__container_value_type&& __v) {
1262        return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v));
1263    }
1264
1265    _LIBCPP_INLINE_VISIBILITY
1266    iterator __insert_unique(const_iterator __p, __container_value_type&& __v) {
1267        return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first;
1268    }
1269
1270    template <class _Vp, class = typename enable_if<
1271            !is_same<typename __unconstref<_Vp>::type,
1272                     __container_value_type
1273            >::value
1274        >::type>
1275    _LIBCPP_INLINE_VISIBILITY
1276    pair<iterator, bool> __insert_unique(_Vp&& __v) {
1277        return __emplace_unique(_VSTD::forward<_Vp>(__v));
1278    }
1279
1280    template <class _Vp, class = typename enable_if<
1281            !is_same<typename __unconstref<_Vp>::type,
1282                     __container_value_type
1283            >::value
1284        >::type>
1285    _LIBCPP_INLINE_VISIBILITY
1286    iterator __insert_unique(const_iterator __p, _Vp&& __v) {
1287        return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v));
1288    }
1289
1290    _LIBCPP_INLINE_VISIBILITY
1291    iterator __insert_multi(__container_value_type&& __v) {
1292        return __emplace_multi(_VSTD::move(__v));
1293    }
1294
1295    _LIBCPP_INLINE_VISIBILITY
1296    iterator __insert_multi(const_iterator __p, __container_value_type&& __v) {
1297        return __emplace_hint_multi(__p, _VSTD::move(__v));
1298    }
1299
1300    template <class _Vp>
1301    _LIBCPP_INLINE_VISIBILITY
1302    iterator __insert_multi(_Vp&& __v) {
1303        return __emplace_multi(_VSTD::forward<_Vp>(__v));
1304    }
1305
1306    template <class _Vp>
1307    _LIBCPP_INLINE_VISIBILITY
1308    iterator __insert_multi(const_iterator __p, _Vp&& __v) {
1309        return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v));
1310    }
1311
1312    _LIBCPP_INLINE_VISIBILITY
1313    pair<iterator, bool> __node_assign_unique(const __container_value_type& __v, __node_pointer __dest);
1314
1315    _LIBCPP_INLINE_VISIBILITY
1316    iterator __node_insert_multi(__node_pointer __nd);
1317    _LIBCPP_INLINE_VISIBILITY
1318    iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
1319
1320
1321    _LIBCPP_INLINE_VISIBILITY iterator
1322    __remove_node_pointer(__node_pointer) _NOEXCEPT;
1323
1324#if _LIBCPP_STD_VER > 14
1325    template <class _NodeHandle, class _InsertReturnType>
1326    _LIBCPP_INLINE_VISIBILITY
1327    _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
1328    template <class _NodeHandle>
1329    _LIBCPP_INLINE_VISIBILITY
1330    iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
1331    template <class _Tree>
1332    _LIBCPP_INLINE_VISIBILITY
1333    void __node_handle_merge_unique(_Tree& __source);
1334
1335    template <class _NodeHandle>
1336    _LIBCPP_INLINE_VISIBILITY
1337    iterator __node_handle_insert_multi(_NodeHandle&&);
1338    template <class _NodeHandle>
1339    _LIBCPP_INLINE_VISIBILITY
1340    iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
1341    template <class _Tree>
1342    _LIBCPP_INLINE_VISIBILITY
1343    void __node_handle_merge_multi(_Tree& __source);
1344
1345
1346    template <class _NodeHandle>
1347    _LIBCPP_INLINE_VISIBILITY
1348    _NodeHandle __node_handle_extract(key_type const&);
1349    template <class _NodeHandle>
1350    _LIBCPP_INLINE_VISIBILITY
1351    _NodeHandle __node_handle_extract(const_iterator);
1352#endif
1353
1354    iterator erase(const_iterator __p);
1355    iterator erase(const_iterator __f, const_iterator __l);
1356    template <class _Key>
1357        size_type __erase_unique(const _Key& __k);
1358    template <class _Key>
1359        size_type __erase_multi(const _Key& __k);
1360
1361    void __insert_node_at(__parent_pointer     __parent,
1362                          __node_base_pointer& __child,
1363                          __node_base_pointer __new_node) _NOEXCEPT;
1364
1365    template <class _Key>
1366        iterator find(const _Key& __v);
1367    template <class _Key>
1368        const_iterator find(const _Key& __v) const;
1369
1370    template <class _Key>
1371        size_type __count_unique(const _Key& __k) const;
1372    template <class _Key>
1373        size_type __count_multi(const _Key& __k) const;
1374
1375    template <class _Key>
1376        _LIBCPP_INLINE_VISIBILITY
1377        iterator lower_bound(const _Key& __v)
1378            {return __lower_bound(__v, __root(), __end_node());}
1379    template <class _Key>
1380        iterator __lower_bound(const _Key& __v,
1381                               __node_pointer __root,
1382                               __iter_pointer __result);
1383    template <class _Key>
1384        _LIBCPP_INLINE_VISIBILITY
1385        const_iterator lower_bound(const _Key& __v) const
1386            {return __lower_bound(__v, __root(), __end_node());}
1387    template <class _Key>
1388        const_iterator __lower_bound(const _Key& __v,
1389                                     __node_pointer __root,
1390                                     __iter_pointer __result) const;
1391    template <class _Key>
1392        _LIBCPP_INLINE_VISIBILITY
1393        iterator upper_bound(const _Key& __v)
1394            {return __upper_bound(__v, __root(), __end_node());}
1395    template <class _Key>
1396        iterator __upper_bound(const _Key& __v,
1397                               __node_pointer __root,
1398                               __iter_pointer __result);
1399    template <class _Key>
1400        _LIBCPP_INLINE_VISIBILITY
1401        const_iterator upper_bound(const _Key& __v) const
1402            {return __upper_bound(__v, __root(), __end_node());}
1403    template <class _Key>
1404        const_iterator __upper_bound(const _Key& __v,
1405                                     __node_pointer __root,
1406                                     __iter_pointer __result) const;
1407    template <class _Key>
1408        pair<iterator, iterator>
1409        __equal_range_unique(const _Key& __k);
1410    template <class _Key>
1411        pair<const_iterator, const_iterator>
1412        __equal_range_unique(const _Key& __k) const;
1413
1414    template <class _Key>
1415        pair<iterator, iterator>
1416        __equal_range_multi(const _Key& __k);
1417    template <class _Key>
1418        pair<const_iterator, const_iterator>
1419        __equal_range_multi(const _Key& __k) const;
1420
1421    typedef __tree_node_destructor<__node_allocator> _Dp;
1422    typedef unique_ptr<__node, _Dp> __node_holder;
1423
1424    __node_holder remove(const_iterator __p) _NOEXCEPT;
1425private:
1426    __node_base_pointer&
1427        __find_leaf_low(__parent_pointer& __parent, const key_type& __v);
1428    __node_base_pointer&
1429        __find_leaf_high(__parent_pointer& __parent, const key_type& __v);
1430    __node_base_pointer&
1431        __find_leaf(const_iterator __hint,
1432                    __parent_pointer& __parent, const key_type& __v);
1433    // FIXME: Make this function const qualified. Unfortunately doing so
1434    // breaks existing code which uses non-const callable comparators.
1435    template <class _Key>
1436    __node_base_pointer&
1437        __find_equal(__parent_pointer& __parent, const _Key& __v);
1438    template <class _Key>
1439    _LIBCPP_INLINE_VISIBILITY __node_base_pointer&
1440    __find_equal(__parent_pointer& __parent, const _Key& __v) const {
1441      return const_cast<__tree*>(this)->__find_equal(__parent, __v);
1442    }
1443    template <class _Key>
1444    __node_base_pointer&
1445        __find_equal(const_iterator __hint, __parent_pointer& __parent,
1446                     __node_base_pointer& __dummy,
1447                     const _Key& __v);
1448
1449    template <class ..._Args>
1450    __node_holder __construct_node(_Args&& ...__args);
1451
1452    void destroy(__node_pointer __nd) _NOEXCEPT;
1453
1454    _LIBCPP_INLINE_VISIBILITY
1455    void __copy_assign_alloc(const __tree& __t)
1456        {__copy_assign_alloc(__t, integral_constant<bool,
1457             __node_traits::propagate_on_container_copy_assignment::value>());}
1458
1459    _LIBCPP_INLINE_VISIBILITY
1460    void __copy_assign_alloc(const __tree& __t, true_type)
1461        {
1462        if (__node_alloc() != __t.__node_alloc())
1463            clear();
1464        __node_alloc() = __t.__node_alloc();
1465        }
1466    _LIBCPP_INLINE_VISIBILITY
1467    void __copy_assign_alloc(const __tree&, false_type) {}
1468
1469    void __move_assign(__tree& __t, false_type);
1470    void __move_assign(__tree& __t, true_type)
1471        _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1472                   is_nothrow_move_assignable<__node_allocator>::value);
1473
1474    _LIBCPP_INLINE_VISIBILITY
1475    void __move_assign_alloc(__tree& __t)
1476        _NOEXCEPT_(
1477            !__node_traits::propagate_on_container_move_assignment::value ||
1478            is_nothrow_move_assignable<__node_allocator>::value)
1479        {__move_assign_alloc(__t, integral_constant<bool,
1480             __node_traits::propagate_on_container_move_assignment::value>());}
1481
1482    _LIBCPP_INLINE_VISIBILITY
1483    void __move_assign_alloc(__tree& __t, true_type)
1484        _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1485        {__node_alloc() = _VSTD::move(__t.__node_alloc());}
1486    _LIBCPP_INLINE_VISIBILITY
1487    void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}
1488
1489    struct _DetachedTreeCache {
1490      _LIBCPP_INLINE_VISIBILITY
1491      explicit _DetachedTreeCache(__tree *__t) _NOEXCEPT : __t_(__t),
1492        __cache_root_(__detach_from_tree(__t)) {
1493          __advance();
1494        }
1495
1496      _LIBCPP_INLINE_VISIBILITY
1497      __node_pointer __get() const _NOEXCEPT {
1498        return __cache_elem_;
1499      }
1500
1501      _LIBCPP_INLINE_VISIBILITY
1502      void __advance() _NOEXCEPT {
1503        __cache_elem_ = __cache_root_;
1504        if (__cache_root_) {
1505          __cache_root_ = __detach_next(__cache_root_);
1506        }
1507      }
1508
1509      _LIBCPP_INLINE_VISIBILITY
1510      ~_DetachedTreeCache() {
1511        __t_->destroy(__cache_elem_);
1512        if (__cache_root_) {
1513          while (__cache_root_->__parent_ != nullptr)
1514            __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_);
1515          __t_->destroy(__cache_root_);
1516        }
1517      }
1518
1519       _DetachedTreeCache(_DetachedTreeCache const&) = delete;
1520       _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete;
1521
1522    private:
1523      _LIBCPP_INLINE_VISIBILITY
1524      static __node_pointer __detach_from_tree(__tree *__t) _NOEXCEPT;
1525      _LIBCPP_INLINE_VISIBILITY
1526      static __node_pointer __detach_next(__node_pointer) _NOEXCEPT;
1527
1528      __tree *__t_;
1529      __node_pointer __cache_root_;
1530      __node_pointer __cache_elem_;
1531    };
1532
1533
1534    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
1535    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
1536};
1537
1538template <class _Tp, class _Compare, class _Allocator>
1539__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
1540        _NOEXCEPT_(
1541            is_nothrow_default_constructible<__node_allocator>::value &&
1542            is_nothrow_copy_constructible<value_compare>::value)
1543    : __pair3_(0, __comp)
1544{
1545    __begin_node() = __end_node();
1546}
1547
1548template <class _Tp, class _Compare, class _Allocator>
1549__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1550    : __begin_node_(__iter_pointer()),
1551      __pair1_(__default_init_tag(), __node_allocator(__a)),
1552      __pair3_(0, __default_init_tag())
1553{
1554    __begin_node() = __end_node();
1555}
1556
1557template <class _Tp, class _Compare, class _Allocator>
1558__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
1559                                           const allocator_type& __a)
1560    : __begin_node_(__iter_pointer()),
1561      __pair1_(__default_init_tag(), __node_allocator(__a)),
1562      __pair3_(0, __comp)
1563{
1564    __begin_node() = __end_node();
1565}
1566
1567// Precondition:  size() != 0
1568template <class _Tp, class _Compare, class _Allocator>
1569typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1570__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree *__t) _NOEXCEPT
1571{
1572    __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node());
1573    __t->__begin_node() = __t->__end_node();
1574    __t->__end_node()->__left_->__parent_ = nullptr;
1575    __t->__end_node()->__left_ = nullptr;
1576    __t->size() = 0;
1577    // __cache->__left_ == nullptr
1578    if (__cache->__right_ != nullptr)
1579        __cache = static_cast<__node_pointer>(__cache->__right_);
1580    // __cache->__left_ == nullptr
1581    // __cache->__right_ == nullptr
1582    return __cache;
1583}
1584
1585// Precondition:  __cache != nullptr
1586//    __cache->left_ == nullptr
1587//    __cache->right_ == nullptr
1588//    This is no longer a red-black tree
1589template <class _Tp, class _Compare, class _Allocator>
1590typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1591__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT
1592{
1593    if (__cache->__parent_ == nullptr)
1594        return nullptr;
1595    if (_VSTD::__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1596    {
1597        __cache->__parent_->__left_ = nullptr;
1598        __cache = static_cast<__node_pointer>(__cache->__parent_);
1599        if (__cache->__right_ == nullptr)
1600            return __cache;
1601        return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__right_));
1602    }
1603    // __cache is right child
1604    __cache->__parent_unsafe()->__right_ = nullptr;
1605    __cache = static_cast<__node_pointer>(__cache->__parent_);
1606    if (__cache->__left_ == nullptr)
1607        return __cache;
1608    return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_));
1609}
1610
1611template <class _Tp, class _Compare, class _Allocator>
1612__tree<_Tp, _Compare, _Allocator>&
1613__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
1614{
1615    if (this != _VSTD::addressof(__t))
1616    {
1617        value_comp() = __t.value_comp();
1618        __copy_assign_alloc(__t);
1619        __assign_multi(__t.begin(), __t.end());
1620    }
1621    return *this;
1622}
1623
1624template <class _Tp, class _Compare, class _Allocator>
1625template <class _ForwardIterator>
1626void
1627__tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last)
1628{
1629    typedef iterator_traits<_ForwardIterator> _ITraits;
1630    typedef typename _ITraits::value_type _ItValueType;
1631    static_assert((is_same<_ItValueType, __container_value_type>::value),
1632                  "__assign_unique may only be called with the containers value type");
1633    static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
1634                  "__assign_unique requires a forward iterator");
1635    if (size() != 0)
1636    {
1637        _DetachedTreeCache __cache(this);
1638          for (; __cache.__get() != nullptr && __first != __last; ++__first) {
1639              if (__node_assign_unique(*__first, __cache.__get()).second)
1640                  __cache.__advance();
1641            }
1642    }
1643    for (; __first != __last; ++__first)
1644        __insert_unique(*__first);
1645}
1646
1647template <class _Tp, class _Compare, class _Allocator>
1648template <class _InputIterator>
1649void
1650__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
1651{
1652    typedef iterator_traits<_InputIterator> _ITraits;
1653    typedef typename _ITraits::value_type _ItValueType;
1654    static_assert((is_same<_ItValueType, __container_value_type>::value ||
1655                  is_same<_ItValueType, __node_value_type>::value),
1656                  "__assign_multi may only be called with the containers value type"
1657                  " or the nodes value type");
1658    if (size() != 0)
1659    {
1660        _DetachedTreeCache __cache(this);
1661        for (; __cache.__get() && __first != __last; ++__first) {
1662            __cache.__get()->__value_ = *__first;
1663            __node_insert_multi(__cache.__get());
1664            __cache.__advance();
1665        }
1666    }
1667    for (; __first != __last; ++__first)
1668        __insert_multi(_NodeTypes::__get_value(*__first));
1669}
1670
1671template <class _Tp, class _Compare, class _Allocator>
1672__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1673    : __begin_node_(__iter_pointer()),
1674      __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1675      __pair3_(0, __t.value_comp())
1676{
1677    __begin_node() = __end_node();
1678}
1679
1680template <class _Tp, class _Compare, class _Allocator>
1681__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
1682    _NOEXCEPT_(
1683        is_nothrow_move_constructible<__node_allocator>::value &&
1684        is_nothrow_move_constructible<value_compare>::value)
1685    : __begin_node_(_VSTD::move(__t.__begin_node_)),
1686      __pair1_(_VSTD::move(__t.__pair1_)),
1687      __pair3_(_VSTD::move(__t.__pair3_))
1688{
1689    if (size() == 0)
1690        __begin_node() = __end_node();
1691    else
1692    {
1693        __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1694        __t.__begin_node() = __t.__end_node();
1695        __t.__end_node()->__left_ = nullptr;
1696        __t.size() = 0;
1697    }
1698}
1699
1700template <class _Tp, class _Compare, class _Allocator>
1701__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1702    : __pair1_(__default_init_tag(), __node_allocator(__a)),
1703      __pair3_(0, _VSTD::move(__t.value_comp()))
1704{
1705    if (__a == __t.__alloc())
1706    {
1707        if (__t.size() == 0)
1708            __begin_node() = __end_node();
1709        else
1710        {
1711            __begin_node() = __t.__begin_node();
1712            __end_node()->__left_ = __t.__end_node()->__left_;
1713            __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1714            size() = __t.size();
1715            __t.__begin_node() = __t.__end_node();
1716            __t.__end_node()->__left_ = nullptr;
1717            __t.size() = 0;
1718        }
1719    }
1720    else
1721    {
1722        __begin_node() = __end_node();
1723    }
1724}
1725
1726template <class _Tp, class _Compare, class _Allocator>
1727void
1728__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1729    _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1730               is_nothrow_move_assignable<__node_allocator>::value)
1731{
1732    destroy(static_cast<__node_pointer>(__end_node()->__left_));
1733    __begin_node_ = __t.__begin_node_;
1734    __pair1_.first() = __t.__pair1_.first();
1735    __move_assign_alloc(__t);
1736    __pair3_ = _VSTD::move(__t.__pair3_);
1737    if (size() == 0)
1738        __begin_node() = __end_node();
1739    else
1740    {
1741        __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1742        __t.__begin_node() = __t.__end_node();
1743        __t.__end_node()->__left_ = nullptr;
1744        __t.size() = 0;
1745    }
1746}
1747
1748template <class _Tp, class _Compare, class _Allocator>
1749void
1750__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type)
1751{
1752    if (__node_alloc() == __t.__node_alloc())
1753        __move_assign(__t, true_type());
1754    else
1755    {
1756        value_comp() = _VSTD::move(__t.value_comp());
1757        const_iterator __e = end();
1758        if (size() != 0)
1759        {
1760            _DetachedTreeCache __cache(this);
1761            while (__cache.__get() != nullptr && __t.size() != 0) {
1762              __cache.__get()->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_);
1763              __node_insert_multi(__cache.__get());
1764              __cache.__advance();
1765            }
1766        }
1767        while (__t.size() != 0)
1768            __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_));
1769    }
1770}
1771
1772template <class _Tp, class _Compare, class _Allocator>
1773__tree<_Tp, _Compare, _Allocator>&
1774__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1775    _NOEXCEPT_(
1776        __node_traits::propagate_on_container_move_assignment::value &&
1777        is_nothrow_move_assignable<value_compare>::value &&
1778        is_nothrow_move_assignable<__node_allocator>::value)
1779
1780{
1781    __move_assign(__t, integral_constant<bool,
1782                  __node_traits::propagate_on_container_move_assignment::value>());
1783    return *this;
1784}
1785
1786template <class _Tp, class _Compare, class _Allocator>
1787__tree<_Tp, _Compare, _Allocator>::~__tree()
1788{
1789    static_assert((is_copy_constructible<value_compare>::value),
1790                 "Comparator must be copy-constructible.");
1791  destroy(__root());
1792}
1793
1794template <class _Tp, class _Compare, class _Allocator>
1795void
1796__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT
1797{
1798    if (__nd != nullptr)
1799    {
1800        destroy(static_cast<__node_pointer>(__nd->__left_));
1801        destroy(static_cast<__node_pointer>(__nd->__right_));
1802        __node_allocator& __na = __node_alloc();
1803        __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_));
1804        __node_traits::deallocate(__na, __nd, 1);
1805    }
1806}
1807
1808template <class _Tp, class _Compare, class _Allocator>
1809void
1810__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1811#if _LIBCPP_STD_VER <= 11
1812        _NOEXCEPT_(
1813            __is_nothrow_swappable<value_compare>::value
1814            && (!__node_traits::propagate_on_container_swap::value ||
1815                 __is_nothrow_swappable<__node_allocator>::value)
1816            )
1817#else
1818        _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value)
1819#endif
1820{
1821    using _VSTD::swap;
1822    swap(__begin_node_, __t.__begin_node_);
1823    swap(__pair1_.first(), __t.__pair1_.first());
1824    _VSTD::__swap_allocator(__node_alloc(), __t.__node_alloc());
1825    __pair3_.swap(__t.__pair3_);
1826    if (size() == 0)
1827        __begin_node() = __end_node();
1828    else
1829        __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
1830    if (__t.size() == 0)
1831        __t.__begin_node() = __t.__end_node();
1832    else
1833        __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());
1834}
1835
1836template <class _Tp, class _Compare, class _Allocator>
1837void
1838__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
1839{
1840    destroy(__root());
1841    size() = 0;
1842    __begin_node() = __end_node();
1843    __end_node()->__left_ = nullptr;
1844}
1845
1846// Find lower_bound place to insert
1847// Set __parent to parent of null leaf
1848// Return reference to null leaf
1849template <class _Tp, class _Compare, class _Allocator>
1850typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1851__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent,
1852                                                   const key_type& __v)
1853{
1854    __node_pointer __nd = __root();
1855    if (__nd != nullptr)
1856    {
1857        while (true)
1858        {
1859            if (value_comp()(__nd->__value_, __v))
1860            {
1861                if (__nd->__right_ != nullptr)
1862                    __nd = static_cast<__node_pointer>(__nd->__right_);
1863                else
1864                {
1865                    __parent = static_cast<__parent_pointer>(__nd);
1866                    return __nd->__right_;
1867                }
1868            }
1869            else
1870            {
1871                if (__nd->__left_ != nullptr)
1872                    __nd = static_cast<__node_pointer>(__nd->__left_);
1873                else
1874                {
1875                    __parent = static_cast<__parent_pointer>(__nd);
1876                    return __parent->__left_;
1877                }
1878            }
1879        }
1880    }
1881    __parent = static_cast<__parent_pointer>(__end_node());
1882    return __parent->__left_;
1883}
1884
1885// Find upper_bound place to insert
1886// Set __parent to parent of null leaf
1887// Return reference to null leaf
1888template <class _Tp, class _Compare, class _Allocator>
1889typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1890__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent,
1891                                                    const key_type& __v)
1892{
1893    __node_pointer __nd = __root();
1894    if (__nd != nullptr)
1895    {
1896        while (true)
1897        {
1898            if (value_comp()(__v, __nd->__value_))
1899            {
1900                if (__nd->__left_ != nullptr)
1901                    __nd = static_cast<__node_pointer>(__nd->__left_);
1902                else
1903                {
1904                    __parent = static_cast<__parent_pointer>(__nd);
1905                    return __parent->__left_;
1906                }
1907            }
1908            else
1909            {
1910                if (__nd->__right_ != nullptr)
1911                    __nd = static_cast<__node_pointer>(__nd->__right_);
1912                else
1913                {
1914                    __parent = static_cast<__parent_pointer>(__nd);
1915                    return __nd->__right_;
1916                }
1917            }
1918        }
1919    }
1920    __parent = static_cast<__parent_pointer>(__end_node());
1921    return __parent->__left_;
1922}
1923
1924// Find leaf place to insert closest to __hint
1925// First check prior to __hint.
1926// Next check after __hint.
1927// Next do O(log N) search.
1928// Set __parent to parent of null leaf
1929// Return reference to null leaf
1930template <class _Tp, class _Compare, class _Allocator>
1931typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1932__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
1933                                               __parent_pointer& __parent,
1934                                               const key_type& __v)
1935{
1936    if (__hint == end() || !value_comp()(*__hint, __v))  // check before
1937    {
1938        // __v <= *__hint
1939        const_iterator __prior = __hint;
1940        if (__prior == begin() || !value_comp()(__v, *--__prior))
1941        {
1942            // *prev(__hint) <= __v <= *__hint
1943            if (__hint.__ptr_->__left_ == nullptr)
1944            {
1945                __parent = static_cast<__parent_pointer>(__hint.__ptr_);
1946                return __parent->__left_;
1947            }
1948            else
1949            {
1950                __parent = static_cast<__parent_pointer>(__prior.__ptr_);
1951                return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
1952            }
1953        }
1954        // __v < *prev(__hint)
1955        return __find_leaf_high(__parent, __v);
1956    }
1957    // else __v > *__hint
1958    return __find_leaf_low(__parent, __v);
1959}
1960
1961// Find place to insert if __v doesn't exist
1962// Set __parent to parent of null leaf
1963// Return reference to null leaf
1964// If __v exists, set parent to node of __v and return reference to node of __v
1965template <class _Tp, class _Compare, class _Allocator>
1966template <class _Key>
1967typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1968__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent,
1969                                                const _Key& __v)
1970{
1971    __node_pointer __nd = __root();
1972    __node_base_pointer* __nd_ptr = __root_ptr();
1973    if (__nd != nullptr)
1974    {
1975        while (true)
1976        {
1977            if (value_comp()(__v, __nd->__value_))
1978            {
1979                if (__nd->__left_ != nullptr) {
1980                    __nd_ptr = _VSTD::addressof(__nd->__left_);
1981                    __nd = static_cast<__node_pointer>(__nd->__left_);
1982                } else {
1983                    __parent = static_cast<__parent_pointer>(__nd);
1984                    return __parent->__left_;
1985                }
1986            }
1987            else if (value_comp()(__nd->__value_, __v))
1988            {
1989                if (__nd->__right_ != nullptr) {
1990                    __nd_ptr = _VSTD::addressof(__nd->__right_);
1991                    __nd = static_cast<__node_pointer>(__nd->__right_);
1992                } else {
1993                    __parent = static_cast<__parent_pointer>(__nd);
1994                    return __nd->__right_;
1995                }
1996            }
1997            else
1998            {
1999                __parent = static_cast<__parent_pointer>(__nd);
2000                return *__nd_ptr;
2001            }
2002        }
2003    }
2004    __parent = static_cast<__parent_pointer>(__end_node());
2005    return __parent->__left_;
2006}
2007
2008// Find place to insert if __v doesn't exist
2009// First check prior to __hint.
2010// Next check after __hint.
2011// Next do O(log N) search.
2012// Set __parent to parent of null leaf
2013// Return reference to null leaf
2014// If __v exists, set parent to node of __v and return reference to node of __v
2015template <class _Tp, class _Compare, class _Allocator>
2016template <class _Key>
2017typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
2018__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
2019                                                __parent_pointer& __parent,
2020                                                __node_base_pointer& __dummy,
2021                                                const _Key& __v)
2022{
2023    if (__hint == end() || value_comp()(__v, *__hint))  // check before
2024    {
2025        // __v < *__hint
2026        const_iterator __prior = __hint;
2027        if (__prior == begin() || value_comp()(*--__prior, __v))
2028        {
2029            // *prev(__hint) < __v < *__hint
2030            if (__hint.__ptr_->__left_ == nullptr)
2031            {
2032                __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2033                return __parent->__left_;
2034            }
2035            else
2036            {
2037                __parent = static_cast<__parent_pointer>(__prior.__ptr_);
2038                return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
2039            }
2040        }
2041        // __v <= *prev(__hint)
2042        return __find_equal(__parent, __v);
2043    }
2044    else if (value_comp()(*__hint, __v))  // check after
2045    {
2046        // *__hint < __v
2047        const_iterator __next = _VSTD::next(__hint);
2048        if (__next == end() || value_comp()(__v, *__next))
2049        {
2050            // *__hint < __v < *_VSTD::next(__hint)
2051            if (__hint.__get_np()->__right_ == nullptr)
2052            {
2053                __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2054                return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
2055            }
2056            else
2057            {
2058                __parent = static_cast<__parent_pointer>(__next.__ptr_);
2059                return __parent->__left_;
2060            }
2061        }
2062        // *next(__hint) <= __v
2063        return __find_equal(__parent, __v);
2064    }
2065    // else __v == *__hint
2066    __parent = static_cast<__parent_pointer>(__hint.__ptr_);
2067    __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
2068    return __dummy;
2069}
2070
2071template <class _Tp, class _Compare, class _Allocator>
2072void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
2073    __parent_pointer __parent, __node_base_pointer& __child,
2074    __node_base_pointer __new_node) _NOEXCEPT
2075{
2076    __new_node->__left_   = nullptr;
2077    __new_node->__right_  = nullptr;
2078    __new_node->__parent_ = __parent;
2079    // __new_node->__is_black_ is initialized in __tree_balance_after_insert
2080    __child = __new_node;
2081    if (__begin_node()->__left_ != nullptr)
2082        __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
2083    _VSTD::__tree_balance_after_insert(__end_node()->__left_, __child);
2084    ++size();
2085}
2086
2087template <class _Tp, class _Compare, class _Allocator>
2088template <class _Key, class... _Args>
2089pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2090__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
2091{
2092    __parent_pointer __parent;
2093    __node_base_pointer& __child = __find_equal(__parent, __k);
2094    __node_pointer __r = static_cast<__node_pointer>(__child);
2095    bool __inserted = false;
2096    if (__child == nullptr)
2097    {
2098        __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2099        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2100        __r = __h.release();
2101        __inserted = true;
2102    }
2103    return pair<iterator, bool>(iterator(__r), __inserted);
2104}
2105
2106template <class _Tp, class _Compare, class _Allocator>
2107template <class _Key, class... _Args>
2108pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2109__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
2110    const_iterator __p, _Key const& __k, _Args&&... __args)
2111{
2112    __parent_pointer __parent;
2113    __node_base_pointer __dummy;
2114    __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
2115    __node_pointer __r = static_cast<__node_pointer>(__child);
2116    bool __inserted = false;
2117    if (__child == nullptr)
2118    {
2119        __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2120        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2121        __r = __h.release();
2122        __inserted = true;
2123    }
2124    return pair<iterator, bool>(iterator(__r), __inserted);
2125}
2126
2127template <class _Tp, class _Compare, class _Allocator>
2128template <class ..._Args>
2129typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2130__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args)
2131{
2132    static_assert(!__is_tree_value_type<_Args...>::value,
2133                  "Cannot construct from __value_type");
2134    __node_allocator& __na = __node_alloc();
2135    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2136    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
2137    __h.get_deleter().__value_constructed = true;
2138    return __h;
2139}
2140
2141
2142template <class _Tp, class _Compare, class _Allocator>
2143template <class... _Args>
2144pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2145__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
2146{
2147    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2148    __parent_pointer __parent;
2149    __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
2150    __node_pointer __r = static_cast<__node_pointer>(__child);
2151    bool __inserted = false;
2152    if (__child == nullptr)
2153    {
2154        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2155        __r = __h.release();
2156        __inserted = true;
2157    }
2158    return pair<iterator, bool>(iterator(__r), __inserted);
2159}
2160
2161template <class _Tp, class _Compare, class _Allocator>
2162template <class... _Args>
2163typename __tree<_Tp, _Compare, _Allocator>::iterator
2164__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
2165{
2166    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2167    __parent_pointer __parent;
2168    __node_base_pointer __dummy;
2169    __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
2170    __node_pointer __r = static_cast<__node_pointer>(__child);
2171    if (__child == nullptr)
2172    {
2173        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2174        __r = __h.release();
2175    }
2176    return iterator(__r);
2177}
2178
2179template <class _Tp, class _Compare, class _Allocator>
2180template <class... _Args>
2181typename __tree<_Tp, _Compare, _Allocator>::iterator
2182__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
2183{
2184    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2185    __parent_pointer __parent;
2186    __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));
2187    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2188    return iterator(static_cast<__node_pointer>(__h.release()));
2189}
2190
2191template <class _Tp, class _Compare, class _Allocator>
2192template <class... _Args>
2193typename __tree<_Tp, _Compare, _Allocator>::iterator
2194__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
2195                                                        _Args&&... __args)
2196{
2197    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2198    __parent_pointer __parent;
2199    __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));
2200    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
2201    return iterator(static_cast<__node_pointer>(__h.release()));
2202}
2203
2204template <class _Tp, class _Compare, class _Allocator>
2205pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
2206__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd)
2207{
2208    __parent_pointer __parent;
2209    __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__v));
2210    __node_pointer __r = static_cast<__node_pointer>(__child);
2211    bool __inserted = false;
2212    if (__child == nullptr)
2213    {
2214        __nd->__value_ = __v;
2215        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2216        __r = __nd;
2217        __inserted = true;
2218    }
2219    return pair<iterator, bool>(iterator(__r), __inserted);
2220}
2221
2222
2223template <class _Tp, class _Compare, class _Allocator>
2224typename __tree<_Tp, _Compare, _Allocator>::iterator
2225__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
2226{
2227    __parent_pointer __parent;
2228    __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));
2229    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2230    return iterator(__nd);
2231}
2232
2233template <class _Tp, class _Compare, class _Allocator>
2234typename __tree<_Tp, _Compare, _Allocator>::iterator
2235__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
2236                                                       __node_pointer __nd)
2237{
2238    __parent_pointer __parent;
2239    __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
2240    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
2241    return iterator(__nd);
2242}
2243
2244template <class _Tp, class _Compare, class _Allocator>
2245typename __tree<_Tp, _Compare, _Allocator>::iterator
2246__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT
2247{
2248    iterator __r(__ptr);
2249    ++__r;
2250    if (__begin_node() == __ptr)
2251        __begin_node() = __r.__ptr_;
2252    --size();
2253    _VSTD::__tree_remove(__end_node()->__left_,
2254                         static_cast<__node_base_pointer>(__ptr));
2255    return __r;
2256}
2257
2258#if _LIBCPP_STD_VER > 14
2259template <class _Tp, class _Compare, class _Allocator>
2260template <class _NodeHandle, class _InsertReturnType>
2261_LIBCPP_INLINE_VISIBILITY
2262_InsertReturnType
2263__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
2264    _NodeHandle&& __nh)
2265{
2266    if (__nh.empty())
2267        return _InsertReturnType{end(), false, _NodeHandle()};
2268
2269    __node_pointer __ptr = __nh.__ptr_;
2270    __parent_pointer __parent;
2271    __node_base_pointer& __child = __find_equal(__parent,
2272                                                __ptr->__value_);
2273    if (__child != nullptr)
2274        return _InsertReturnType{
2275            iterator(static_cast<__node_pointer>(__child)),
2276            false, _VSTD::move(__nh)};
2277
2278    __insert_node_at(__parent, __child,
2279                     static_cast<__node_base_pointer>(__ptr));
2280    __nh.__release_ptr();
2281    return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
2282}
2283
2284template <class _Tp, class _Compare, class _Allocator>
2285template <class _NodeHandle>
2286_LIBCPP_INLINE_VISIBILITY
2287typename __tree<_Tp, _Compare, _Allocator>::iterator
2288__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
2289    const_iterator __hint, _NodeHandle&& __nh)
2290{
2291    if (__nh.empty())
2292        return end();
2293
2294    __node_pointer __ptr = __nh.__ptr_;
2295    __parent_pointer __parent;
2296    __node_base_pointer __dummy;
2297    __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy,
2298                                                __ptr->__value_);
2299    __node_pointer __r = static_cast<__node_pointer>(__child);
2300    if (__child == nullptr)
2301    {
2302        __insert_node_at(__parent, __child,
2303                         static_cast<__node_base_pointer>(__ptr));
2304        __r = __ptr;
2305        __nh.__release_ptr();
2306    }
2307    return iterator(__r);
2308}
2309
2310template <class _Tp, class _Compare, class _Allocator>
2311template <class _NodeHandle>
2312_LIBCPP_INLINE_VISIBILITY
2313_NodeHandle
2314__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key)
2315{
2316    iterator __it = find(__key);
2317    if (__it == end())
2318        return _NodeHandle();
2319    return __node_handle_extract<_NodeHandle>(__it);
2320}
2321
2322template <class _Tp, class _Compare, class _Allocator>
2323template <class _NodeHandle>
2324_LIBCPP_INLINE_VISIBILITY
2325_NodeHandle
2326__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p)
2327{
2328    __node_pointer __np = __p.__get_np();
2329    __remove_node_pointer(__np);
2330    return _NodeHandle(__np, __alloc());
2331}
2332
2333template <class _Tp, class _Compare, class _Allocator>
2334template <class _Tree>
2335_LIBCPP_INLINE_VISIBILITY
2336void
2337__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source)
2338{
2339    static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
2340
2341    for (typename _Tree::iterator __i = __source.begin();
2342         __i != __source.end();)
2343    {
2344        __node_pointer __src_ptr = __i.__get_np();
2345        __parent_pointer __parent;
2346        __node_base_pointer& __child =
2347            __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_));
2348        ++__i;
2349        if (__child != nullptr)
2350            continue;
2351        __source.__remove_node_pointer(__src_ptr);
2352        __insert_node_at(__parent, __child,
2353                         static_cast<__node_base_pointer>(__src_ptr));
2354    }
2355}
2356
2357template <class _Tp, class _Compare, class _Allocator>
2358template <class _NodeHandle>
2359_LIBCPP_INLINE_VISIBILITY
2360typename __tree<_Tp, _Compare, _Allocator>::iterator
2361__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh)
2362{
2363    if (__nh.empty())
2364        return end();
2365    __node_pointer __ptr = __nh.__ptr_;
2366    __parent_pointer __parent;
2367    __node_base_pointer& __child = __find_leaf_high(
2368        __parent, _NodeTypes::__get_key(__ptr->__value_));
2369    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
2370    __nh.__release_ptr();
2371    return iterator(__ptr);
2372}
2373
2374template <class _Tp, class _Compare, class _Allocator>
2375template <class _NodeHandle>
2376_LIBCPP_INLINE_VISIBILITY
2377typename __tree<_Tp, _Compare, _Allocator>::iterator
2378__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
2379    const_iterator __hint, _NodeHandle&& __nh)
2380{
2381    if (__nh.empty())
2382        return end();
2383
2384    __node_pointer __ptr = __nh.__ptr_;
2385    __parent_pointer __parent;
2386    __node_base_pointer& __child = __find_leaf(__hint, __parent,
2387                                               _NodeTypes::__get_key(__ptr->__value_));
2388    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
2389    __nh.__release_ptr();
2390    return iterator(__ptr);
2391}
2392
2393template <class _Tp, class _Compare, class _Allocator>
2394template <class _Tree>
2395_LIBCPP_INLINE_VISIBILITY
2396void
2397__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source)
2398{
2399    static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
2400
2401    for (typename _Tree::iterator __i = __source.begin();
2402         __i != __source.end();)
2403    {
2404        __node_pointer __src_ptr = __i.__get_np();
2405        __parent_pointer __parent;
2406        __node_base_pointer& __child = __find_leaf_high(
2407            __parent, _NodeTypes::__get_key(__src_ptr->__value_));
2408        ++__i;
2409        __source.__remove_node_pointer(__src_ptr);
2410        __insert_node_at(__parent, __child,
2411                         static_cast<__node_base_pointer>(__src_ptr));
2412    }
2413}
2414
2415#endif // _LIBCPP_STD_VER > 14
2416
2417template <class _Tp, class _Compare, class _Allocator>
2418typename __tree<_Tp, _Compare, _Allocator>::iterator
2419__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
2420{
2421    __node_pointer __np = __p.__get_np();
2422    iterator __r = __remove_node_pointer(__np);
2423    __node_allocator& __na = __node_alloc();
2424    __node_traits::destroy(__na, _NodeTypes::__get_ptr(
2425        const_cast<__node_value_type&>(*__p)));
2426    __node_traits::deallocate(__na, __np, 1);
2427    return __r;
2428}
2429
2430template <class _Tp, class _Compare, class _Allocator>
2431typename __tree<_Tp, _Compare, _Allocator>::iterator
2432__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l)
2433{
2434    while (__f != __l)
2435        __f = erase(__f);
2436    return iterator(__l.__ptr_);
2437}
2438
2439template <class _Tp, class _Compare, class _Allocator>
2440template <class _Key>
2441typename __tree<_Tp, _Compare, _Allocator>::size_type
2442__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k)
2443{
2444    iterator __i = find(__k);
2445    if (__i == end())
2446        return 0;
2447    erase(__i);
2448    return 1;
2449}
2450
2451template <class _Tp, class _Compare, class _Allocator>
2452template <class _Key>
2453typename __tree<_Tp, _Compare, _Allocator>::size_type
2454__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k)
2455{
2456    pair<iterator, iterator> __p = __equal_range_multi(__k);
2457    size_type __r = 0;
2458    for (; __p.first != __p.second; ++__r)
2459        __p.first = erase(__p.first);
2460    return __r;
2461}
2462
2463template <class _Tp, class _Compare, class _Allocator>
2464template <class _Key>
2465typename __tree<_Tp, _Compare, _Allocator>::iterator
2466__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
2467{
2468    iterator __p = __lower_bound(__v, __root(), __end_node());
2469    if (__p != end() && !value_comp()(__v, *__p))
2470        return __p;
2471    return end();
2472}
2473
2474template <class _Tp, class _Compare, class _Allocator>
2475template <class _Key>
2476typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2477__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
2478{
2479    const_iterator __p = __lower_bound(__v, __root(), __end_node());
2480    if (__p != end() && !value_comp()(__v, *__p))
2481        return __p;
2482    return end();
2483}
2484
2485template <class _Tp, class _Compare, class _Allocator>
2486template <class _Key>
2487typename __tree<_Tp, _Compare, _Allocator>::size_type
2488__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
2489{
2490    __node_pointer __rt = __root();
2491    while (__rt != nullptr)
2492    {
2493        if (value_comp()(__k, __rt->__value_))
2494        {
2495            __rt = static_cast<__node_pointer>(__rt->__left_);
2496        }
2497        else if (value_comp()(__rt->__value_, __k))
2498            __rt = static_cast<__node_pointer>(__rt->__right_);
2499        else
2500            return 1;
2501    }
2502    return 0;
2503}
2504
2505template <class _Tp, class _Compare, class _Allocator>
2506template <class _Key>
2507typename __tree<_Tp, _Compare, _Allocator>::size_type
2508__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
2509{
2510    __iter_pointer __result = __end_node();
2511    __node_pointer __rt = __root();
2512    while (__rt != nullptr)
2513    {
2514        if (value_comp()(__k, __rt->__value_))
2515        {
2516            __result = static_cast<__iter_pointer>(__rt);
2517            __rt = static_cast<__node_pointer>(__rt->__left_);
2518        }
2519        else if (value_comp()(__rt->__value_, __k))
2520            __rt = static_cast<__node_pointer>(__rt->__right_);
2521        else
2522            return _VSTD::distance(
2523                __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2524                __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)
2525            );
2526    }
2527    return 0;
2528}
2529
2530template <class _Tp, class _Compare, class _Allocator>
2531template <class _Key>
2532typename __tree<_Tp, _Compare, _Allocator>::iterator
2533__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2534                                                 __node_pointer __root,
2535                                                 __iter_pointer __result)
2536{
2537    while (__root != nullptr)
2538    {
2539        if (!value_comp()(__root->__value_, __v))
2540        {
2541            __result = static_cast<__iter_pointer>(__root);
2542            __root = static_cast<__node_pointer>(__root->__left_);
2543        }
2544        else
2545            __root = static_cast<__node_pointer>(__root->__right_);
2546    }
2547    return iterator(__result);
2548}
2549
2550template <class _Tp, class _Compare, class _Allocator>
2551template <class _Key>
2552typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2553__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
2554                                                 __node_pointer __root,
2555                                                 __iter_pointer __result) const
2556{
2557    while (__root != nullptr)
2558    {
2559        if (!value_comp()(__root->__value_, __v))
2560        {
2561            __result = static_cast<__iter_pointer>(__root);
2562            __root = static_cast<__node_pointer>(__root->__left_);
2563        }
2564        else
2565            __root = static_cast<__node_pointer>(__root->__right_);
2566    }
2567    return const_iterator(__result);
2568}
2569
2570template <class _Tp, class _Compare, class _Allocator>
2571template <class _Key>
2572typename __tree<_Tp, _Compare, _Allocator>::iterator
2573__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2574                                                 __node_pointer __root,
2575                                                 __iter_pointer __result)
2576{
2577    while (__root != nullptr)
2578    {
2579        if (value_comp()(__v, __root->__value_))
2580        {
2581            __result = static_cast<__iter_pointer>(__root);
2582            __root = static_cast<__node_pointer>(__root->__left_);
2583        }
2584        else
2585            __root = static_cast<__node_pointer>(__root->__right_);
2586    }
2587    return iterator(__result);
2588}
2589
2590template <class _Tp, class _Compare, class _Allocator>
2591template <class _Key>
2592typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2593__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
2594                                                 __node_pointer __root,
2595                                                 __iter_pointer __result) const
2596{
2597    while (__root != nullptr)
2598    {
2599        if (value_comp()(__v, __root->__value_))
2600        {
2601            __result = static_cast<__iter_pointer>(__root);
2602            __root = static_cast<__node_pointer>(__root->__left_);
2603        }
2604        else
2605            __root = static_cast<__node_pointer>(__root->__right_);
2606    }
2607    return const_iterator(__result);
2608}
2609
2610template <class _Tp, class _Compare, class _Allocator>
2611template <class _Key>
2612pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2613     typename __tree<_Tp, _Compare, _Allocator>::iterator>
2614__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
2615{
2616    typedef pair<iterator, iterator> _Pp;
2617    __iter_pointer __result = __end_node();
2618    __node_pointer __rt = __root();
2619    while (__rt != nullptr)
2620    {
2621        if (value_comp()(__k, __rt->__value_))
2622        {
2623            __result = static_cast<__iter_pointer>(__rt);
2624            __rt = static_cast<__node_pointer>(__rt->__left_);
2625        }
2626        else if (value_comp()(__rt->__value_, __k))
2627            __rt = static_cast<__node_pointer>(__rt->__right_);
2628        else
2629            return _Pp(iterator(__rt),
2630                      iterator(
2631                          __rt->__right_ != nullptr ?
2632                              static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_))
2633                            : __result));
2634    }
2635    return _Pp(iterator(__result), iterator(__result));
2636}
2637
2638template <class _Tp, class _Compare, class _Allocator>
2639template <class _Key>
2640pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2641     typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2642__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
2643{
2644    typedef pair<const_iterator, const_iterator> _Pp;
2645    __iter_pointer __result = __end_node();
2646    __node_pointer __rt = __root();
2647    while (__rt != nullptr)
2648    {
2649        if (value_comp()(__k, __rt->__value_))
2650        {
2651            __result = static_cast<__iter_pointer>(__rt);
2652            __rt = static_cast<__node_pointer>(__rt->__left_);
2653        }
2654        else if (value_comp()(__rt->__value_, __k))
2655            __rt = static_cast<__node_pointer>(__rt->__right_);
2656        else
2657            return _Pp(const_iterator(__rt),
2658                      const_iterator(
2659                          __rt->__right_ != nullptr ?
2660                              static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_))
2661                            : __result));
2662    }
2663    return _Pp(const_iterator(__result), const_iterator(__result));
2664}
2665
2666template <class _Tp, class _Compare, class _Allocator>
2667template <class _Key>
2668pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
2669     typename __tree<_Tp, _Compare, _Allocator>::iterator>
2670__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
2671{
2672    typedef pair<iterator, iterator> _Pp;
2673    __iter_pointer __result = __end_node();
2674    __node_pointer __rt = __root();
2675    while (__rt != nullptr)
2676    {
2677        if (value_comp()(__k, __rt->__value_))
2678        {
2679            __result = static_cast<__iter_pointer>(__rt);
2680            __rt = static_cast<__node_pointer>(__rt->__left_);
2681        }
2682        else if (value_comp()(__rt->__value_, __k))
2683            __rt = static_cast<__node_pointer>(__rt->__right_);
2684        else
2685            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2686                      __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2687    }
2688    return _Pp(iterator(__result), iterator(__result));
2689}
2690
2691template <class _Tp, class _Compare, class _Allocator>
2692template <class _Key>
2693pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2694     typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2695__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
2696{
2697    typedef pair<const_iterator, const_iterator> _Pp;
2698    __iter_pointer __result = __end_node();
2699    __node_pointer __rt = __root();
2700    while (__rt != nullptr)
2701    {
2702        if (value_comp()(__k, __rt->__value_))
2703        {
2704            __result = static_cast<__iter_pointer>(__rt);
2705            __rt = static_cast<__node_pointer>(__rt->__left_);
2706        }
2707        else if (value_comp()(__rt->__value_, __k))
2708            __rt = static_cast<__node_pointer>(__rt->__right_);
2709        else
2710            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
2711                      __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2712    }
2713    return _Pp(const_iterator(__result), const_iterator(__result));
2714}
2715
2716template <class _Tp, class _Compare, class _Allocator>
2717typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2718__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2719{
2720    __node_pointer __np = __p.__get_np();
2721    if (__begin_node() == __p.__ptr_)
2722    {
2723        if (__np->__right_ != nullptr)
2724            __begin_node() = static_cast<__iter_pointer>(__np->__right_);
2725        else
2726            __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
2727    }
2728    --size();
2729    _VSTD::__tree_remove(__end_node()->__left_,
2730                         static_cast<__node_base_pointer>(__np));
2731    return __node_holder(__np, _Dp(__node_alloc(), true));
2732}
2733
2734template <class _Tp, class _Compare, class _Allocator>
2735inline _LIBCPP_INLINE_VISIBILITY
2736void
2737swap(__tree<_Tp, _Compare, _Allocator>& __x,
2738     __tree<_Tp, _Compare, _Allocator>& __y)
2739    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2740{
2741    __x.swap(__y);
2742}
2743
2744_LIBCPP_END_NAMESPACE_STD
2745
2746_LIBCPP_POP_MACROS
2747
2748#endif // _LIBCPP___TREE
2749