master
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 template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type<_ValueT>::value, int> = 0>
1019 _LIBCPP_HIDE_FROM_ABI void
1020 __insert_unique_from_orphaned_node(const_iterator __p, __get_node_value_type_t<_Tp>&& __value) {
1021 __emplace_hint_unique(__p, const_cast<key_type&&>(__value.first), std::move(__value.second));
1022 }
1023
1024 template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type<_ValueT>::value, int> = 0>
1025 _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(const_iterator __p, _Tp&& __value) {
1026 __emplace_hint_unique(__p, std::move(__value));
1027 }
1028
1029 template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type<_ValueT>::value, int> = 0>
1030 _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(const_iterator __p, value_type&& __value) {
1031 __emplace_hint_multi(__p, const_cast<key_type&&>(__value.first), std::move(__value.second));
1032 }
1033
1034 template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type<_ValueT>::value, int> = 0>
1035 _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(const_iterator __p, _Tp&& __value) {
1036 __emplace_hint_multi(__p, std::move(__value));
1037 }
1038
1039 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_assign_unique(const value_type& __v, __node_pointer __dest);
1040
1041 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
1042 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
1043
1044 _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT;
1045
1046#if _LIBCPP_STD_VER >= 17
1047 template <class _NodeHandle, class _InsertReturnType>
1048 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
1049 template <class _NodeHandle>
1050 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
1051 template <class _Tree>
1052 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Tree& __source);
1053
1054 template <class _NodeHandle>
1055 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&&);
1056 template <class _NodeHandle>
1057 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
1058 template <class _Tree>
1059 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Tree& __source);
1060
1061 template <class _NodeHandle>
1062 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const&);
1063 template <class _NodeHandle>
1064 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator);
1065#endif
1066
1067 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
1068 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l);
1069 template <class _Key>
1070 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
1071 template <class _Key>
1072 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
1073
1074 _LIBCPP_HIDE_FROM_ABI void
1075 __insert_node_at(__end_node_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT;
1076
1077 template <class _Key>
1078 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __v);
1079 template <class _Key>
1080 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __v) const;
1081
1082 template <class _Key>
1083 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
1084 template <class _Key>
1085 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
1086
1087 template <class _Key>
1088 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Key& __v) {
1089 return __lower_bound(__v, __root(), __end_node());
1090 }
1091 template <class _Key>
1092 _LIBCPP_HIDE_FROM_ABI iterator __lower_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result);
1093 template <class _Key>
1094 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _Key& __v) const {
1095 return __lower_bound(__v, __root(), __end_node());
1096 }
1097 template <class _Key>
1098 _LIBCPP_HIDE_FROM_ABI const_iterator
1099 __lower_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result) const;
1100 template <class _Key>
1101 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _Key& __v) {
1102 return __upper_bound(__v, __root(), __end_node());
1103 }
1104 template <class _Key>
1105 _LIBCPP_HIDE_FROM_ABI iterator __upper_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result);
1106 template <class _Key>
1107 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _Key& __v) const {
1108 return __upper_bound(__v, __root(), __end_node());
1109 }
1110 template <class _Key>
1111 _LIBCPP_HIDE_FROM_ABI const_iterator
1112 __upper_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result) const;
1113 template <class _Key>
1114 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);
1115 template <class _Key>
1116 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;
1117
1118 template <class _Key>
1119 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);
1120 template <class _Key>
1121 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;
1122
1123 typedef __tree_node_destructor<__node_allocator> _Dp;
1124 typedef unique_ptr<__node, _Dp> __node_holder;
1125
1126 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
1127
1128 // FIXME: Make this function const qualified. Unfortunately doing so
1129 // breaks existing code which uses non-const callable comparators.
1130 template <class _Key>
1131 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__end_node_pointer& __parent, const _Key& __v);
1132 template <class _Key>
1133 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_equal(__end_node_pointer& __parent, const _Key& __v) const {
1134 return const_cast<__tree*>(this)->__find_equal(__parent, __v);
1135 }
1136 template <class _Key>
1137 _LIBCPP_HIDE_FROM_ABI __node_base_pointer&
1138 __find_equal(const_iterator __hint, __end_node_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v);
1139
1140 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t) {
1141 __copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
1142 }
1143
1144 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree& __t, true_type) {
1145 if (__node_alloc() != __t.__node_alloc())
1146 clear();
1147 __node_alloc() = __t.__node_alloc();
1148 }
1149 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __tree&, false_type) {}
1150
1151private:
1152 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_low(__end_node_pointer& __parent, const value_type& __v);
1153
1154 _LIBCPP_HIDE_FROM_ABI __node_base_pointer& __find_leaf_high(__end_node_pointer& __parent, const value_type& __v);
1155
1156 _LIBCPP_HIDE_FROM_ABI __node_base_pointer&
1157 __find_leaf(const_iterator __hint, __end_node_pointer& __parent, const value_type& __v);
1158
1159 template <class... _Args>
1160 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
1161
1162 // TODO: Make this _LIBCPP_HIDE_FROM_ABI
1163 _LIBCPP_HIDDEN void destroy(__node_pointer __nd) _NOEXCEPT;
1164
1165 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, false_type);
1166 _LIBCPP_HIDE_FROM_ABI void __move_assign(__tree& __t, true_type) _NOEXCEPT_(
1167 is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value);
1168
1169 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t)
1170 _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
1171 is_nothrow_move_assignable<__node_allocator>::value) {
1172 __move_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1173 }
1174
1175 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree& __t, true_type)
1176 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {
1177 __node_alloc() = std::move(__t.__node_alloc());
1178 }
1179 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {}
1180
1181 template <class _From, class _ValueT = _Tp, __enable_if_t<__is_tree_value_type<_ValueT>::value, int> = 0>
1182 _LIBCPP_HIDE_FROM_ABI static void __assign_value(__get_node_value_type_t<value_type>& __lhs, _From&& __rhs) {
1183 using __key_type = __remove_const_t<typename value_type::first_type>;
1184
1185 // This is technically UB, since the object was constructed as `const`.
1186 // Clang doesn't optimize on this currently though.
1187 const_cast<__key_type&>(__lhs.first) = const_cast<__copy_cvref_t<_From, __key_type>&&>(__rhs.first);
1188 __lhs.second = std::forward<_From>(__rhs).second;
1189 }
1190
1191 template <class _To, class _From, class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type<_ValueT>::value, int> = 0>
1192 _LIBCPP_HIDE_FROM_ABI static void __assign_value(_To& __lhs, _From&& __rhs) {
1193 __lhs = std::forward<_From>(__rhs);
1194 }
1195
1196 struct _DetachedTreeCache {
1197 _LIBCPP_HIDE_FROM_ABI explicit _DetachedTreeCache(__tree* __t) _NOEXCEPT
1198 : __t_(__t),
1199 __cache_root_(__detach_from_tree(__t)) {
1200 __advance();
1201 }
1202
1203 _LIBCPP_HIDE_FROM_ABI __node_pointer __get() const _NOEXCEPT { return __cache_elem_; }
1204
1205 _LIBCPP_HIDE_FROM_ABI void __advance() _NOEXCEPT {
1206 __cache_elem_ = __cache_root_;
1207 if (__cache_root_) {
1208 __cache_root_ = __detach_next(__cache_root_);
1209 }
1210 }
1211
1212 _LIBCPP_HIDE_FROM_ABI ~_DetachedTreeCache() {
1213 __t_->destroy(__cache_elem_);
1214 if (__cache_root_) {
1215 while (__cache_root_->__parent_ != nullptr)
1216 __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_);
1217 __t_->destroy(__cache_root_);
1218 }
1219 }
1220
1221 _DetachedTreeCache(_DetachedTreeCache const&) = delete;
1222 _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete;
1223
1224 private:
1225 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_from_tree(__tree* __t) _NOEXCEPT;
1226 _LIBCPP_HIDE_FROM_ABI static __node_pointer __detach_next(__node_pointer) _NOEXCEPT;
1227
1228 __tree* __t_;
1229 __node_pointer __cache_root_;
1230 __node_pointer __cache_elem_;
1231 };
1232};
1233
1234template <class _Tp, class _Compare, class _Allocator>
1235__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) _NOEXCEPT_(
1236 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value)
1237 : __size_(0), __value_comp_(__comp) {
1238 __begin_node() = __end_node();
1239}
1240
1241template <class _Tp, class _Compare, class _Allocator>
1242__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
1243 : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0) {
1244 __begin_node() = __end_node();
1245}
1246
1247template <class _Tp, class _Compare, class _Allocator>
1248__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a)
1249 : __begin_node_(), __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(__comp) {
1250 __begin_node() = __end_node();
1251}
1252
1253// Precondition: size() != 0
1254template <class _Tp, class _Compare, class _Allocator>
1255typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1256__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT {
1257 __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node());
1258 __t->__begin_node() = __t->__end_node();
1259 __t->__end_node()->__left_->__parent_ = nullptr;
1260 __t->__end_node()->__left_ = nullptr;
1261 __t->size() = 0;
1262 // __cache->__left_ == nullptr
1263 if (__cache->__right_ != nullptr)
1264 __cache = static_cast<__node_pointer>(__cache->__right_);
1265 // __cache->__left_ == nullptr
1266 // __cache->__right_ == nullptr
1267 return __cache;
1268}
1269
1270// Precondition: __cache != nullptr
1271// __cache->left_ == nullptr
1272// __cache->right_ == nullptr
1273// This is no longer a red-black tree
1274template <class _Tp, class _Compare, class _Allocator>
1275typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
1276__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT {
1277 if (__cache->__parent_ == nullptr)
1278 return nullptr;
1279 if (std::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) {
1280 __cache->__parent_->__left_ = nullptr;
1281 __cache = static_cast<__node_pointer>(__cache->__parent_);
1282 if (__cache->__right_ == nullptr)
1283 return __cache;
1284 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__right_));
1285 }
1286 // __cache is right child
1287 __cache->__parent_unsafe()->__right_ = nullptr;
1288 __cache = static_cast<__node_pointer>(__cache->__parent_);
1289 if (__cache->__left_ == nullptr)
1290 return __cache;
1291 return static_cast<__node_pointer>(std::__tree_leaf(__cache->__left_));
1292}
1293
1294template <class _Tp, class _Compare, class _Allocator>
1295__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) {
1296 if (this != std::addressof(__t)) {
1297 value_comp() = __t.value_comp();
1298 __copy_assign_alloc(__t);
1299 __assign_multi(__t.begin(), __t.end());
1300 }
1301 return *this;
1302}
1303
1304template <class _Tp, class _Compare, class _Allocator>
1305template <class _ForwardIterator>
1306void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) {
1307 typedef iterator_traits<_ForwardIterator> _ITraits;
1308 typedef typename _ITraits::value_type _ItValueType;
1309 static_assert(
1310 is_same<_ItValueType, value_type>::value, "__assign_unique may only be called with the containers value type");
1311 static_assert(
1312 __has_forward_iterator_category<_ForwardIterator>::value, "__assign_unique requires a forward iterator");
1313 if (size() != 0) {
1314 _DetachedTreeCache __cache(this);
1315 for (; __cache.__get() != nullptr && __first != __last; ++__first) {
1316 if (__node_assign_unique(*__first, __cache.__get()).second)
1317 __cache.__advance();
1318 }
1319 }
1320 for (; __first != __last; ++__first)
1321 __emplace_unique(*__first);
1322}
1323
1324template <class _Tp, class _Compare, class _Allocator>
1325template <class _InputIterator>
1326void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) {
1327 typedef iterator_traits<_InputIterator> _ITraits;
1328 typedef typename _ITraits::value_type _ItValueType;
1329 static_assert(
1330 is_same<_ItValueType, value_type>::value, "__assign_multi may only be called with the containers value_type");
1331 if (size() != 0) {
1332 _DetachedTreeCache __cache(this);
1333 for (; __cache.__get() && __first != __last; ++__first) {
1334 __assign_value(__cache.__get()->__value_, *__first);
1335 __node_insert_multi(__cache.__get());
1336 __cache.__advance();
1337 }
1338 }
1339 const_iterator __e = end();
1340 for (; __first != __last; ++__first)
1341 __emplace_hint_multi(__e, *__first);
1342}
1343
1344template <class _Tp, class _Compare, class _Allocator>
1345__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
1346 : __begin_node_(),
1347 __node_alloc_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
1348 __size_(0),
1349 __value_comp_(__t.value_comp()) {
1350 __begin_node() = __end_node();
1351}
1352
1353template <class _Tp, class _Compare, class _Allocator>
1354__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_(
1355 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value)
1356 : __begin_node_(std::move(__t.__begin_node_)),
1357 __end_node_(std::move(__t.__end_node_)),
1358 __node_alloc_(std::move(__t.__node_alloc_)),
1359 __size_(__t.__size_),
1360 __value_comp_(std::move(__t.__value_comp_)) {
1361 if (size() == 0)
1362 __begin_node() = __end_node();
1363 else {
1364 __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node());
1365 __t.__begin_node() = __t.__end_node();
1366 __t.__end_node()->__left_ = nullptr;
1367 __t.size() = 0;
1368 }
1369}
1370
1371template <class _Tp, class _Compare, class _Allocator>
1372__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
1373 : __node_alloc_(__node_allocator(__a)), __size_(0), __value_comp_(std::move(__t.value_comp())) {
1374 if (__a == __t.__alloc()) {
1375 if (__t.size() == 0)
1376 __begin_node() = __end_node();
1377 else {
1378 __begin_node() = __t.__begin_node();
1379 __end_node()->__left_ = __t.__end_node()->__left_;
1380 __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node());
1381 size() = __t.size();
1382 __t.__begin_node() = __t.__end_node();
1383 __t.__end_node()->__left_ = nullptr;
1384 __t.size() = 0;
1385 }
1386 } else {
1387 __begin_node() = __end_node();
1388 }
1389}
1390
1391template <class _Tp, class _Compare, class _Allocator>
1392void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
1393 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value) {
1394 destroy(static_cast<__node_pointer>(__end_node()->__left_));
1395 __begin_node_ = __t.__begin_node_;
1396 __end_node_ = __t.__end_node_;
1397 __move_assign_alloc(__t);
1398 __size_ = __t.__size_;
1399 __value_comp_ = std::move(__t.__value_comp_);
1400 if (size() == 0)
1401 __begin_node() = __end_node();
1402 else {
1403 __end_node()->__left_->__parent_ = static_cast<__end_node_pointer>(__end_node());
1404 __t.__begin_node() = __t.__end_node();
1405 __t.__end_node()->__left_ = nullptr;
1406 __t.size() = 0;
1407 }
1408}
1409
1410template <class _Tp, class _Compare, class _Allocator>
1411void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) {
1412 if (__node_alloc() == __t.__node_alloc())
1413 __move_assign(__t, true_type());
1414 else {
1415 value_comp() = std::move(__t.value_comp());
1416 const_iterator __e = end();
1417 if (size() != 0) {
1418 _DetachedTreeCache __cache(this);
1419 while (__cache.__get() != nullptr && __t.size() != 0) {
1420 __assign_value(__cache.__get()->__value_, std::move(__t.remove(__t.begin())->__value_));
1421 __node_insert_multi(__cache.__get());
1422 __cache.__advance();
1423 }
1424 }
1425 while (__t.size() != 0) {
1426 __insert_multi_from_orphaned_node(__e, std::move(__t.remove(__t.begin())->__value_));
1427 }
1428 }
1429}
1430
1431template <class _Tp, class _Compare, class _Allocator>
1432__tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t)
1433 _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value &&
1434 ((__node_traits::propagate_on_container_move_assignment::value &&
1435 is_nothrow_move_assignable<__node_allocator>::value) ||
1436 allocator_traits<__node_allocator>::is_always_equal::value)) {
1437 __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1438 return *this;
1439}
1440
1441template <class _Tp, class _Compare, class _Allocator>
1442__tree<_Tp, _Compare, _Allocator>::~__tree() {
1443 static_assert(is_copy_constructible<value_compare>::value, "Comparator must be copy-constructible.");
1444 destroy(__root());
1445}
1446
1447template <class _Tp, class _Compare, class _Allocator>
1448void __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT {
1449 if (__nd != nullptr) {
1450 destroy(static_cast<__node_pointer>(__nd->__left_));
1451 destroy(static_cast<__node_pointer>(__nd->__right_));
1452 __node_allocator& __na = __node_alloc();
1453 __node_traits::destroy(__na, std::addressof(__nd->__value_));
1454 __node_traits::deallocate(__na, __nd, 1);
1455 }
1456}
1457
1458template <class _Tp, class _Compare, class _Allocator>
1459void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)
1460#if _LIBCPP_STD_VER <= 11
1461 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> &&
1462 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))
1463#else
1464 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>)
1465#endif
1466{
1467 using std::swap;
1468 swap(__begin_node_, __t.__begin_node_);
1469 swap(__end_node_, __t.__end_node_);
1470 std::__swap_allocator(__node_alloc(), __t.__node_alloc());
1471 swap(__size_, __t.__size_);
1472 swap(__value_comp_, __t.__value_comp_);
1473 if (size() == 0)
1474 __begin_node() = __end_node();
1475 else
1476 __end_node()->__left_->__parent_ = __end_node();
1477 if (__t.size() == 0)
1478 __t.__begin_node() = __t.__end_node();
1479 else
1480 __t.__end_node()->__left_->__parent_ = __t.__end_node();
1481}
1482
1483template <class _Tp, class _Compare, class _Allocator>
1484void __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT {
1485 destroy(__root());
1486 size() = 0;
1487 __begin_node() = __end_node();
1488 __end_node()->__left_ = nullptr;
1489}
1490
1491// Find lower_bound place to insert
1492// Set __parent to parent of null leaf
1493// Return reference to null leaf
1494template <class _Tp, class _Compare, class _Allocator>
1495typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1496__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__end_node_pointer& __parent, const value_type& __v) {
1497 __node_pointer __nd = __root();
1498 if (__nd != nullptr) {
1499 while (true) {
1500 if (value_comp()(__nd->__value_, __v)) {
1501 if (__nd->__right_ != nullptr)
1502 __nd = static_cast<__node_pointer>(__nd->__right_);
1503 else {
1504 __parent = static_cast<__end_node_pointer>(__nd);
1505 return __nd->__right_;
1506 }
1507 } else {
1508 if (__nd->__left_ != nullptr)
1509 __nd = static_cast<__node_pointer>(__nd->__left_);
1510 else {
1511 __parent = static_cast<__end_node_pointer>(__nd);
1512 return __parent->__left_;
1513 }
1514 }
1515 }
1516 }
1517 __parent = __end_node();
1518 return __parent->__left_;
1519}
1520
1521// Find upper_bound place to insert
1522// Set __parent to parent of null leaf
1523// Return reference to null leaf
1524template <class _Tp, class _Compare, class _Allocator>
1525typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1526__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__end_node_pointer& __parent, const value_type& __v) {
1527 __node_pointer __nd = __root();
1528 if (__nd != nullptr) {
1529 while (true) {
1530 if (value_comp()(__v, __nd->__value_)) {
1531 if (__nd->__left_ != nullptr)
1532 __nd = static_cast<__node_pointer>(__nd->__left_);
1533 else {
1534 __parent = static_cast<__end_node_pointer>(__nd);
1535 return __parent->__left_;
1536 }
1537 } else {
1538 if (__nd->__right_ != nullptr)
1539 __nd = static_cast<__node_pointer>(__nd->__right_);
1540 else {
1541 __parent = static_cast<__end_node_pointer>(__nd);
1542 return __nd->__right_;
1543 }
1544 }
1545 }
1546 }
1547 __parent = __end_node();
1548 return __parent->__left_;
1549}
1550
1551// Find leaf place to insert closest to __hint
1552// First check prior to __hint.
1553// Next check after __hint.
1554// Next do O(log N) search.
1555// Set __parent to parent of null leaf
1556// Return reference to null leaf
1557template <class _Tp, class _Compare, class _Allocator>
1558typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf(
1559 const_iterator __hint, __end_node_pointer& __parent, const value_type& __v) {
1560 if (__hint == end() || !value_comp()(*__hint, __v)) // check before
1561 {
1562 // __v <= *__hint
1563 const_iterator __prior = __hint;
1564 if (__prior == begin() || !value_comp()(__v, *--__prior)) {
1565 // *prev(__hint) <= __v <= *__hint
1566 if (__hint.__ptr_->__left_ == nullptr) {
1567 __parent = static_cast<__end_node_pointer>(__hint.__ptr_);
1568 return __parent->__left_;
1569 } else {
1570 __parent = static_cast<__end_node_pointer>(__prior.__ptr_);
1571 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
1572 }
1573 }
1574 // __v < *prev(__hint)
1575 return __find_leaf_high(__parent, __v);
1576 }
1577 // else __v > *__hint
1578 return __find_leaf_low(__parent, __v);
1579}
1580
1581// Find place to insert if __v doesn't exist
1582// Set __parent to parent of null leaf
1583// Return reference to null leaf
1584// If __v exists, set parent to node of __v and return reference to node of __v
1585template <class _Tp, class _Compare, class _Allocator>
1586template <class _Key>
1587typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
1588__tree<_Tp, _Compare, _Allocator>::__find_equal(__end_node_pointer& __parent, const _Key& __v) {
1589 __node_pointer __nd = __root();
1590 __node_base_pointer* __nd_ptr = __root_ptr();
1591 if (__nd != nullptr) {
1592 while (true) {
1593 if (value_comp()(__v, __nd->__value_)) {
1594 if (__nd->__left_ != nullptr) {
1595 __nd_ptr = std::addressof(__nd->__left_);
1596 __nd = static_cast<__node_pointer>(__nd->__left_);
1597 } else {
1598 __parent = static_cast<__end_node_pointer>(__nd);
1599 return __parent->__left_;
1600 }
1601 } else if (value_comp()(__nd->__value_, __v)) {
1602 if (__nd->__right_ != nullptr) {
1603 __nd_ptr = std::addressof(__nd->__right_);
1604 __nd = static_cast<__node_pointer>(__nd->__right_);
1605 } else {
1606 __parent = static_cast<__end_node_pointer>(__nd);
1607 return __nd->__right_;
1608 }
1609 } else {
1610 __parent = static_cast<__end_node_pointer>(__nd);
1611 return *__nd_ptr;
1612 }
1613 }
1614 }
1615 __parent = __end_node();
1616 return __parent->__left_;
1617}
1618
1619// Find place to insert if __v doesn't exist
1620// First check prior to __hint.
1621// Next check after __hint.
1622// Next do O(log N) search.
1623// Set __parent to parent of null leaf
1624// Return reference to null leaf
1625// If __v exists, set parent to node of __v and return reference to node of __v
1626template <class _Tp, class _Compare, class _Allocator>
1627template <class _Key>
1628typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_equal(
1629 const_iterator __hint, __end_node_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v) {
1630 if (__hint == end() || value_comp()(__v, *__hint)) // check before
1631 {
1632 // __v < *__hint
1633 const_iterator __prior = __hint;
1634 if (__prior == begin() || value_comp()(*--__prior, __v)) {
1635 // *prev(__hint) < __v < *__hint
1636 if (__hint.__ptr_->__left_ == nullptr) {
1637 __parent = __hint.__ptr_;
1638 return __parent->__left_;
1639 } else {
1640 __parent = __prior.__ptr_;
1641 return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
1642 }
1643 }
1644 // __v <= *prev(__hint)
1645 return __find_equal(__parent, __v);
1646 } else if (value_comp()(*__hint, __v)) // check after
1647 {
1648 // *__hint < __v
1649 const_iterator __next = std::next(__hint);
1650 if (__next == end() || value_comp()(__v, *__next)) {
1651 // *__hint < __v < *std::next(__hint)
1652 if (__hint.__get_np()->__right_ == nullptr) {
1653 __parent = __hint.__ptr_;
1654 return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
1655 } else {
1656 __parent = __next.__ptr_;
1657 return __parent->__left_;
1658 }
1659 }
1660 // *next(__hint) <= __v
1661 return __find_equal(__parent, __v);
1662 }
1663 // else __v == *__hint
1664 __parent = __hint.__ptr_;
1665 __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
1666 return __dummy;
1667}
1668
1669template <class _Tp, class _Compare, class _Allocator>
1670void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
1671 __end_node_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT {
1672 __new_node->__left_ = nullptr;
1673 __new_node->__right_ = nullptr;
1674 __new_node->__parent_ = __parent;
1675 // __new_node->__is_black_ is initialized in __tree_balance_after_insert
1676 __child = __new_node;
1677 if (__begin_node()->__left_ != nullptr)
1678 __begin_node() = static_cast<__end_node_pointer>(__begin_node()->__left_);
1679 std::__tree_balance_after_insert(__end_node()->__left_, __child);
1680 ++size();
1681}
1682
1683template <class _Tp, class _Compare, class _Allocator>
1684template <class _Key, class... _Args>
1685pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1686__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
1687 __end_node_pointer __parent;
1688 __node_base_pointer& __child = __find_equal(__parent, __k);
1689 __node_pointer __r = static_cast<__node_pointer>(__child);
1690 bool __inserted = false;
1691 if (__child == nullptr) {
1692 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1693 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1694 __r = __h.release();
1695 __inserted = true;
1696 }
1697 return pair<iterator, bool>(iterator(__r), __inserted);
1698}
1699
1700template <class _Tp, class _Compare, class _Allocator>
1701template <class _Key, class... _Args>
1702pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1703__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
1704 const_iterator __p, _Key const& __k, _Args&&... __args) {
1705 __end_node_pointer __parent;
1706 __node_base_pointer __dummy;
1707 __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
1708 __node_pointer __r = static_cast<__node_pointer>(__child);
1709 bool __inserted = false;
1710 if (__child == nullptr) {
1711 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1712 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1713 __r = __h.release();
1714 __inserted = true;
1715 }
1716 return pair<iterator, bool>(iterator(__r), __inserted);
1717}
1718
1719template <class _Tp, class _Compare, class _Allocator>
1720template <class... _Args>
1721typename __tree<_Tp, _Compare, _Allocator>::__node_holder
1722__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
1723 __node_allocator& __na = __node_alloc();
1724 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1725 __node_traits::construct(__na, std::addressof(__h->__value_), std::forward<_Args>(__args)...);
1726 __h.get_deleter().__value_constructed = true;
1727 return __h;
1728}
1729
1730template <class _Tp, class _Compare, class _Allocator>
1731template <class... _Args>
1732pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1733__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) {
1734 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1735 __end_node_pointer __parent;
1736 __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
1737 __node_pointer __r = static_cast<__node_pointer>(__child);
1738 bool __inserted = false;
1739 if (__child == nullptr) {
1740 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1741 __r = __h.release();
1742 __inserted = true;
1743 }
1744 return pair<iterator, bool>(iterator(__r), __inserted);
1745}
1746
1747template <class _Tp, class _Compare, class _Allocator>
1748template <class... _Args>
1749typename __tree<_Tp, _Compare, _Allocator>::iterator
1750__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) {
1751 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1752 __end_node_pointer __parent;
1753 __node_base_pointer __dummy;
1754 __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
1755 __node_pointer __r = static_cast<__node_pointer>(__child);
1756 if (__child == nullptr) {
1757 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1758 __r = __h.release();
1759 }
1760 return iterator(__r);
1761}
1762
1763template <class _Tp, class _Compare, class _Allocator>
1764template <class... _Args>
1765typename __tree<_Tp, _Compare, _Allocator>::iterator
1766__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) {
1767 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1768 __end_node_pointer __parent;
1769 __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1770 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1771 return iterator(static_cast<__node_pointer>(__h.release()));
1772}
1773
1774template <class _Tp, class _Compare, class _Allocator>
1775template <class... _Args>
1776typename __tree<_Tp, _Compare, _Allocator>::iterator
1777__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
1778 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1779 __end_node_pointer __parent;
1780 __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1781 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1782 return iterator(static_cast<__node_pointer>(__h.release()));
1783}
1784
1785template <class _Tp, class _Compare, class _Allocator>
1786pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
1787__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const value_type& __v, __node_pointer __nd) {
1788 __end_node_pointer __parent;
1789 __node_base_pointer& __child = __find_equal(__parent, __v);
1790 __node_pointer __r = static_cast<__node_pointer>(__child);
1791 bool __inserted = false;
1792 if (__child == nullptr) {
1793 __assign_value(__nd->__value_, __v);
1794 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1795 __r = __nd;
1796 __inserted = true;
1797 }
1798 return pair<iterator, bool>(iterator(__r), __inserted);
1799}
1800
1801template <class _Tp, class _Compare, class _Allocator>
1802typename __tree<_Tp, _Compare, _Allocator>::iterator
1803__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) {
1804 __end_node_pointer __parent;
1805 __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_);
1806 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1807 return iterator(__nd);
1808}
1809
1810template <class _Tp, class _Compare, class _Allocator>
1811typename __tree<_Tp, _Compare, _Allocator>::iterator
1812__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) {
1813 __end_node_pointer __parent;
1814 __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_);
1815 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1816 return iterator(__nd);
1817}
1818
1819template <class _Tp, class _Compare, class _Allocator>
1820typename __tree<_Tp, _Compare, _Allocator>::iterator
1821__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT {
1822 iterator __r(__ptr);
1823 ++__r;
1824 if (__begin_node() == __ptr)
1825 __begin_node() = __r.__ptr_;
1826 --size();
1827 std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__ptr));
1828 return __r;
1829}
1830
1831#if _LIBCPP_STD_VER >= 17
1832template <class _Tp, class _Compare, class _Allocator>
1833template <class _NodeHandle, class _InsertReturnType>
1834_LIBCPP_HIDE_FROM_ABI _InsertReturnType
1835__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(_NodeHandle&& __nh) {
1836 if (__nh.empty())
1837 return _InsertReturnType{end(), false, _NodeHandle()};
1838
1839 __node_pointer __ptr = __nh.__ptr_;
1840 __end_node_pointer __parent;
1841 __node_base_pointer& __child = __find_equal(__parent, __ptr->__value_);
1842 if (__child != nullptr)
1843 return _InsertReturnType{iterator(static_cast<__node_pointer>(__child)), false, std::move(__nh)};
1844
1845 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
1846 __nh.__release_ptr();
1847 return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
1848}
1849
1850template <class _Tp, class _Compare, class _Allocator>
1851template <class _NodeHandle>
1852_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator
1853__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh) {
1854 if (__nh.empty())
1855 return end();
1856
1857 __node_pointer __ptr = __nh.__ptr_;
1858 __end_node_pointer __parent;
1859 __node_base_pointer __dummy;
1860 __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, __ptr->__value_);
1861 __node_pointer __r = static_cast<__node_pointer>(__child);
1862 if (__child == nullptr) {
1863 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
1864 __r = __ptr;
1865 __nh.__release_ptr();
1866 }
1867 return iterator(__r);
1868}
1869
1870template <class _Tp, class _Compare, class _Allocator>
1871template <class _NodeHandle>
1872_LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) {
1873 iterator __it = find(__key);
1874 if (__it == end())
1875 return _NodeHandle();
1876 return __node_handle_extract<_NodeHandle>(__it);
1877}
1878
1879template <class _Tp, class _Compare, class _Allocator>
1880template <class _NodeHandle>
1881_LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) {
1882 __node_pointer __np = __p.__get_np();
1883 __remove_node_pointer(__np);
1884 return _NodeHandle(__np, __alloc());
1885}
1886
1887template <class _Tp, class _Compare, class _Allocator>
1888template <class _Tree>
1889_LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) {
1890 static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
1891
1892 for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) {
1893 __node_pointer __src_ptr = __i.__get_np();
1894 __end_node_pointer __parent;
1895 __node_base_pointer& __child = __find_equal(__parent, __src_ptr->__value_);
1896 ++__i;
1897 if (__child != nullptr)
1898 continue;
1899 __source.__remove_node_pointer(__src_ptr);
1900 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr));
1901 }
1902}
1903
1904template <class _Tp, class _Compare, class _Allocator>
1905template <class _NodeHandle>
1906_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator
1907__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) {
1908 if (__nh.empty())
1909 return end();
1910 __node_pointer __ptr = __nh.__ptr_;
1911 __end_node_pointer __parent;
1912 __node_base_pointer& __child = __find_leaf_high(__parent, __ptr->__value_);
1913 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
1914 __nh.__release_ptr();
1915 return iterator(__ptr);
1916}
1917
1918template <class _Tp, class _Compare, class _Allocator>
1919template <class _NodeHandle>
1920_LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator
1921__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {
1922 if (__nh.empty())
1923 return end();
1924
1925 __node_pointer __ptr = __nh.__ptr_;
1926 __end_node_pointer __parent;
1927 __node_base_pointer& __child = __find_leaf(__hint, __parent, __ptr->__value_);
1928 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
1929 __nh.__release_ptr();
1930 return iterator(__ptr);
1931}
1932
1933template <class _Tp, class _Compare, class _Allocator>
1934template <class _Tree>
1935_LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) {
1936 static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
1937
1938 for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) {
1939 __node_pointer __src_ptr = __i.__get_np();
1940 __end_node_pointer __parent;
1941 __node_base_pointer& __child = __find_leaf_high(__parent, __src_ptr->__value_);
1942 ++__i;
1943 __source.__remove_node_pointer(__src_ptr);
1944 __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr));
1945 }
1946}
1947
1948#endif // _LIBCPP_STD_VER >= 17
1949
1950template <class _Tp, class _Compare, class _Allocator>
1951typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) {
1952 __node_pointer __np = __p.__get_np();
1953 iterator __r = __remove_node_pointer(__np);
1954 __node_allocator& __na = __node_alloc();
1955 __node_traits::destroy(__na, std::addressof(const_cast<value_type&>(*__p)));
1956 __node_traits::deallocate(__na, __np, 1);
1957 return __r;
1958}
1959
1960template <class _Tp, class _Compare, class _Allocator>
1961typename __tree<_Tp, _Compare, _Allocator>::iterator
1962__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) {
1963 while (__f != __l)
1964 __f = erase(__f);
1965 return iterator(__l.__ptr_);
1966}
1967
1968template <class _Tp, class _Compare, class _Allocator>
1969template <class _Key>
1970typename __tree<_Tp, _Compare, _Allocator>::size_type
1971__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) {
1972 iterator __i = find(__k);
1973 if (__i == end())
1974 return 0;
1975 erase(__i);
1976 return 1;
1977}
1978
1979template <class _Tp, class _Compare, class _Allocator>
1980template <class _Key>
1981typename __tree<_Tp, _Compare, _Allocator>::size_type
1982__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) {
1983 pair<iterator, iterator> __p = __equal_range_multi(__k);
1984 size_type __r = 0;
1985 for (; __p.first != __p.second; ++__r)
1986 __p.first = erase(__p.first);
1987 return __r;
1988}
1989
1990template <class _Tp, class _Compare, class _Allocator>
1991template <class _Key>
1992typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) {
1993 iterator __p = __lower_bound(__v, __root(), __end_node());
1994 if (__p != end() && !value_comp()(__v, *__p))
1995 return __p;
1996 return end();
1997}
1998
1999template <class _Tp, class _Compare, class _Allocator>
2000template <class _Key>
2001typename __tree<_Tp, _Compare, _Allocator>::const_iterator
2002__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const {
2003 const_iterator __p = __lower_bound(__v, __root(), __end_node());
2004 if (__p != end() && !value_comp()(__v, *__p))
2005 return __p;
2006 return end();
2007}
2008
2009template <class _Tp, class _Compare, class _Allocator>
2010template <class _Key>
2011typename __tree<_Tp, _Compare, _Allocator>::size_type
2012__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const {
2013 __node_pointer __rt = __root();
2014 while (__rt != nullptr) {
2015 if (value_comp()(__k, __rt->__value_)) {
2016 __rt = static_cast<__node_pointer>(__rt->__left_);
2017 } else if (value_comp()(__rt->__value_, __k))
2018 __rt = static_cast<__node_pointer>(__rt->__right_);
2019 else
2020 return 1;
2021 }
2022 return 0;
2023}
2024
2025template <class _Tp, class _Compare, class _Allocator>
2026template <class _Key>
2027typename __tree<_Tp, _Compare, _Allocator>::size_type
2028__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const {
2029 __end_node_pointer __result = __end_node();
2030 __node_pointer __rt = __root();
2031 while (__rt != nullptr) {
2032 if (value_comp()(__k, __rt->__value_)) {
2033 __result = static_cast<__end_node_pointer>(__rt);
2034 __rt = static_cast<__node_pointer>(__rt->__left_);
2035 } else if (value_comp()(__rt->__value_, __k))
2036 __rt = static_cast<__node_pointer>(__rt->__right_);
2037 else
2038 return std::distance(
2039 __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)),
2040 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2041 }
2042 return 0;
2043}
2044
2045template <class _Tp, class _Compare, class _Allocator>
2046template <class _Key>
2047typename __tree<_Tp, _Compare, _Allocator>::iterator
2048__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result) {
2049 while (__root != nullptr) {
2050 if (!value_comp()(__root->__value_, __v)) {
2051 __result = static_cast<__end_node_pointer>(__root);
2052 __root = static_cast<__node_pointer>(__root->__left_);
2053 } else
2054 __root = static_cast<__node_pointer>(__root->__right_);
2055 }
2056 return iterator(__result);
2057}
2058
2059template <class _Tp, class _Compare, class _Allocator>
2060template <class _Key>
2061typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound(
2062 const _Key& __v, __node_pointer __root, __end_node_pointer __result) const {
2063 while (__root != nullptr) {
2064 if (!value_comp()(__root->__value_, __v)) {
2065 __result = static_cast<__end_node_pointer>(__root);
2066 __root = static_cast<__node_pointer>(__root->__left_);
2067 } else
2068 __root = static_cast<__node_pointer>(__root->__right_);
2069 }
2070 return const_iterator(__result);
2071}
2072
2073template <class _Tp, class _Compare, class _Allocator>
2074template <class _Key>
2075typename __tree<_Tp, _Compare, _Allocator>::iterator
2076__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result) {
2077 while (__root != nullptr) {
2078 if (value_comp()(__v, __root->__value_)) {
2079 __result = static_cast<__end_node_pointer>(__root);
2080 __root = static_cast<__node_pointer>(__root->__left_);
2081 } else
2082 __root = static_cast<__node_pointer>(__root->__right_);
2083 }
2084 return iterator(__result);
2085}
2086
2087template <class _Tp, class _Compare, class _Allocator>
2088template <class _Key>
2089typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound(
2090 const _Key& __v, __node_pointer __root, __end_node_pointer __result) const {
2091 while (__root != nullptr) {
2092 if (value_comp()(__v, __root->__value_)) {
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 const_iterator(__result);
2099}
2100
2101template <class _Tp, class _Compare, class _Allocator>
2102template <class _Key>
2103pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>
2104__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) {
2105 typedef pair<iterator, iterator> _Pp;
2106 __end_node_pointer __result = __end_node();
2107 __node_pointer __rt = __root();
2108 while (__rt != nullptr) {
2109 if (value_comp()(__k, __rt->__value_)) {
2110 __result = static_cast<__end_node_pointer>(__rt);
2111 __rt = static_cast<__node_pointer>(__rt->__left_);
2112 } else if (value_comp()(__rt->__value_, __k))
2113 __rt = static_cast<__node_pointer>(__rt->__right_);
2114 else
2115 return _Pp(iterator(__rt),
2116 iterator(__rt->__right_ != nullptr ? static_cast<__end_node_pointer>(std::__tree_min(__rt->__right_))
2117 : __result));
2118 }
2119 return _Pp(iterator(__result), iterator(__result));
2120}
2121
2122template <class _Tp, class _Compare, class _Allocator>
2123template <class _Key>
2124pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2125 typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2126__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const {
2127 typedef pair<const_iterator, const_iterator> _Pp;
2128 __end_node_pointer __result = __end_node();
2129 __node_pointer __rt = __root();
2130 while (__rt != nullptr) {
2131 if (value_comp()(__k, __rt->__value_)) {
2132 __result = static_cast<__end_node_pointer>(__rt);
2133 __rt = static_cast<__node_pointer>(__rt->__left_);
2134 } else if (value_comp()(__rt->__value_, __k))
2135 __rt = static_cast<__node_pointer>(__rt->__right_);
2136 else
2137 return _Pp(
2138 const_iterator(__rt),
2139 const_iterator(
2140 __rt->__right_ != nullptr ? static_cast<__end_node_pointer>(std::__tree_min(__rt->__right_)) : __result));
2141 }
2142 return _Pp(const_iterator(__result), const_iterator(__result));
2143}
2144
2145template <class _Tp, class _Compare, class _Allocator>
2146template <class _Key>
2147pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>
2148__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) {
2149 typedef pair<iterator, iterator> _Pp;
2150 __end_node_pointer __result = __end_node();
2151 __node_pointer __rt = __root();
2152 while (__rt != nullptr) {
2153 if (value_comp()(__k, __rt->__value_)) {
2154 __result = static_cast<__end_node_pointer>(__rt);
2155 __rt = static_cast<__node_pointer>(__rt->__left_);
2156 } else if (value_comp()(__rt->__value_, __k))
2157 __rt = static_cast<__node_pointer>(__rt->__right_);
2158 else
2159 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)),
2160 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2161 }
2162 return _Pp(iterator(__result), iterator(__result));
2163}
2164
2165template <class _Tp, class _Compare, class _Allocator>
2166template <class _Key>
2167pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
2168 typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
2169__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const {
2170 typedef pair<const_iterator, const_iterator> _Pp;
2171 __end_node_pointer __result = __end_node();
2172 __node_pointer __rt = __root();
2173 while (__rt != nullptr) {
2174 if (value_comp()(__k, __rt->__value_)) {
2175 __result = static_cast<__end_node_pointer>(__rt);
2176 __rt = static_cast<__node_pointer>(__rt->__left_);
2177 } else if (value_comp()(__rt->__value_, __k))
2178 __rt = static_cast<__node_pointer>(__rt->__right_);
2179 else
2180 return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)),
2181 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
2182 }
2183 return _Pp(const_iterator(__result), const_iterator(__result));
2184}
2185
2186template <class _Tp, class _Compare, class _Allocator>
2187typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2188__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT {
2189 __node_pointer __np = __p.__get_np();
2190 if (__begin_node() == __p.__ptr_) {
2191 if (__np->__right_ != nullptr)
2192 __begin_node() = static_cast<__end_node_pointer>(__np->__right_);
2193 else
2194 __begin_node() = static_cast<__end_node_pointer>(__np->__parent_);
2195 }
2196 --size();
2197 std::__tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np));
2198 return __node_holder(__np, _Dp(__node_alloc(), true));
2199}
2200
2201template <class _Tp, class _Compare, class _Allocator>
2202inline _LIBCPP_HIDE_FROM_ABI void swap(__tree<_Tp, _Compare, _Allocator>& __x, __tree<_Tp, _Compare, _Allocator>& __y)
2203 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2204 __x.swap(__y);
2205}
2206
2207_LIBCPP_END_NAMESPACE_STD
2208
2209_LIBCPP_POP_MACROS
2210
2211#endif // _LIBCPP___TREE