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