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