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