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