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