1// RB tree implementation -*- C++ -*-
2
3// Copyright (C) 2001-2025 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1994
40 * Hewlett-Packard Company
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 *
50 *
51 */
52
53/** @file bits/stl_tree.h
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{map,set}
56 */
57
58#ifndef _STL_TREE_H
59#define _STL_TREE_H 1
60
61#ifdef _GLIBCXX_SYSHDR
62#pragma GCC system_header
63#endif
64
65#include <bits/stl_algobase.h>
66#include <bits/allocator.h>
67#include <bits/stl_function.h>
68#include <bits/cpp_type_traits.h>
69#include <bits/ptr_traits.h>
70#include <ext/alloc_traits.h>
71#if __cplusplus >= 201103L
72# include <ext/aligned_buffer.h>
73#endif
74#ifdef __glibcxx_node_extract // >= C++17
75# include <bits/node_handle.h>
76#endif
77
78#if __cplusplus < 201103L
79# undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
80# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 0
81#elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
82# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1
83#endif
84
85namespace std _GLIBCXX_VISIBILITY(default)
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION
88
89 // Red-black tree class, designed for use in implementing STL
90 // associative containers (set, multiset, map, and multimap). The
91 // insertion and deletion algorithms are based on those in Cormen,
92 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
93 // 1990), except that
94 //
95 // (1) the header cell is maintained with links not only to the root
96 // but also to the leftmost node of the tree, to enable constant
97 // time begin(), and to the rightmost node of the tree, to enable
98 // linear time performance when used with the generic set algorithms
99 // (set_union, etc.)
100 //
101 // (2) when a node being deleted has two children its successor node
102 // is relinked into its place, rather than copied, so that the only
103 // iterators invalidated are those referring to the deleted node.
104
105 enum _Rb_tree_color { _S_red = false, _S_black = true };
106
107 struct _Rb_tree_node_base
108 {
109 typedef _Rb_tree_node_base* _Base_ptr;
110
111 _Rb_tree_color _M_color;
112 _Base_ptr _M_parent;
113 _Base_ptr _M_left;
114 _Base_ptr _M_right;
115
116 static _Base_ptr
117 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
118 {
119 while (__x->_M_left != 0) __x = __x->_M_left;
120 return __x;
121 }
122
123 static _Base_ptr
124 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
125 {
126 while (__x->_M_right != 0) __x = __x->_M_right;
127 return __x;
128 }
129
130 // This is not const-correct, but it's only used in a const access path
131 // by std::_Rb_tree::_M_end() where the pointer is used to initialize a
132 // const_iterator and so constness is restored.
133 _Base_ptr
134 _M_base_ptr() const _GLIBCXX_NOEXCEPT
135 { return const_cast<_Rb_tree_node_base*>(this); }
136 };
137
138 // Helper type offering value initialization guarantee on the compare functor.
139 template<typename _Key_compare>
140 struct _Rb_tree_key_compare
141 {
142 _Key_compare _M_key_compare;
143
144 _Rb_tree_key_compare()
145 _GLIBCXX_NOEXCEPT_IF(
146 is_nothrow_default_constructible<_Key_compare>::value)
147 : _M_key_compare()
148 { }
149
150 _Rb_tree_key_compare(const _Key_compare& __comp)
151 : _M_key_compare(__comp)
152 { }
153
154#if __cplusplus >= 201103L
155 // Copy constructor added for consistency with C++98 mode.
156 _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
157
158 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
159 noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
160 : _M_key_compare(__x._M_key_compare)
161 { }
162#endif
163 };
164
165 // Helper type to manage default initialization of node count and header.
166 struct _Rb_tree_header
167 {
168 _Rb_tree_node_base _M_header;
169 size_t _M_node_count; // Keeps track of size of tree.
170
171 _Rb_tree_header() _GLIBCXX_NOEXCEPT
172 {
173 _M_header._M_color = _S_red;
174 _M_reset();
175 }
176
177#if __cplusplus >= 201103L
178 _Rb_tree_header(_Rb_tree_header&& __x) noexcept
179 {
180 if (__x._M_header._M_parent != nullptr)
181 _M_move_data(from&: __x);
182 else
183 {
184 _M_header._M_color = _S_red;
185 _M_reset();
186 }
187 }
188#endif
189
190 void
191 _M_move_data(_Rb_tree_header& __from)
192 {
193 _M_header._M_color = __from._M_header._M_color;
194 _M_header._M_parent = __from._M_header._M_parent;
195 _M_header._M_left = __from._M_header._M_left;
196 _M_header._M_right = __from._M_header._M_right;
197 _M_header._M_parent->_M_parent = &_M_header;
198 _M_node_count = __from._M_node_count;
199
200 __from._M_reset();
201 }
202
203 void
204 _M_reset()
205 {
206 _M_header._M_parent = 0;
207 _M_header._M_left = &_M_header;
208 _M_header._M_right = &_M_header;
209 _M_node_count = 0;
210 }
211 };
212
213 template<typename _Val>
214 struct _Rb_tree_node : public _Rb_tree_node_base
215 {
216#if __cplusplus < 201103L
217 _Val _M_value_field;
218
219 _Val*
220 _M_valptr()
221 { return std::__addressof(_M_value_field); }
222
223 const _Val*
224 _M_valptr() const
225 { return std::__addressof(_M_value_field); }
226#else
227 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
228
229 _Val*
230 _M_valptr()
231 { return _M_storage._M_ptr(); }
232
233 const _Val*
234 _M_valptr() const
235 { return _M_storage._M_ptr(); }
236#endif
237
238 _Rb_tree_node*
239 _M_node_ptr() _GLIBCXX_NOEXCEPT
240 { return this; }
241 };
242
243#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
244namespace __rb_tree
245{
246 template<typename _VoidPtr>
247 struct _Node_base
248 {
249 using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
250
251 _Rb_tree_color _M_color;
252 _Base_ptr _M_parent;
253 _Base_ptr _M_left;
254 _Base_ptr _M_right;
255
256 static _Base_ptr
257 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
258 {
259 while (__x->_M_left) __x = __x->_M_left;
260 return __x;
261 }
262
263 static _Base_ptr
264 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
265 {
266 while (__x->_M_right) __x = __x->_M_right;
267 return __x;
268 }
269
270 // This is not const-correct, but it's only used in a const access path
271 // by std::_Rb_tree::_M_end() where the pointer is used to initialize a
272 // const_iterator and so constness is restored.
273 _Base_ptr
274 _M_base_ptr() const noexcept
275 {
276 return pointer_traits<_Base_ptr>::pointer_to
277 (*const_cast<_Node_base*>(this));
278 }
279 };
280
281 // Helper type to manage default initialization of node count and header.
282 template<typename _NodeBase>
283 struct _Header
284 {
285 private:
286 using _Base_ptr = typename _NodeBase::_Base_ptr;
287
288 public:
289 _NodeBase _M_header;
290 size_t _M_node_count; // Keeps track of size of tree.
291
292 _Header() noexcept
293 {
294 _M_header._M_color = _S_red;
295 _M_reset();
296 }
297
298 _Header(_Header&& __x) noexcept
299 {
300 if (__x._M_header._M_parent)
301 _M_move_data(from&: __x);
302 else
303 {
304 _M_header._M_color = _S_red;
305 _M_reset();
306 }
307 }
308
309 void
310 _M_move_data(_Header& __from)
311 {
312 _M_header._M_color = __from._M_header._M_color;
313 _M_header._M_parent = __from._M_header._M_parent;
314 _M_header._M_left = __from._M_header._M_left;
315 _M_header._M_right = __from._M_header._M_right;
316 _M_header._M_parent->_M_parent = _M_header._M_base_ptr();
317 _M_node_count = __from._M_node_count;
318
319 __from._M_reset();
320 }
321
322 void
323 _M_reset()
324 {
325 _M_header._M_parent = nullptr;
326 _M_header._M_left = _M_header._M_right = _M_header._M_base_ptr();
327 _M_node_count = 0;
328 }
329 };
330
331 template<typename _ValPtr>
332 struct _Node : public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>
333 {
334 using value_type = typename pointer_traits<_ValPtr>::element_type;
335 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
336
337 _Node() noexcept { }
338 ~_Node() { }
339 _Node(_Node&&) = delete;
340
341 union _Uninit_storage
342 {
343 _Uninit_storage() noexcept { }
344 ~_Uninit_storage() { }
345
346 value_type _M_data;
347 };
348 _Uninit_storage _M_u;
349
350 value_type*
351 _M_valptr()
352 { return std::addressof(_M_u._M_data); }
353
354 value_type const*
355 _M_valptr() const
356 { return std::addressof(_M_u._M_data); }
357
358 _Node_ptr
359 _M_node_ptr() noexcept
360 { return pointer_traits<_Node_ptr>::pointer_to(*this); }
361 };
362} // namespace __rb_tree
363#endif // _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
364
365 _GLIBCXX_PURE _Rb_tree_node_base*
366 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
367
368 _GLIBCXX_PURE _Rb_tree_node_base*
369 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
370
371 template<typename _Tp>
372 struct _Rb_tree_iterator
373 {
374 typedef _Tp value_type;
375 typedef _Tp& reference;
376 typedef _Tp* pointer;
377
378 typedef bidirectional_iterator_tag iterator_category;
379 typedef ptrdiff_t difference_type;
380
381 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
382 typedef _Rb_tree_node<_Tp>* _Node_ptr;
383
384 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
385 : _M_node() { }
386
387 explicit
388 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
389 : _M_node(__x) { }
390
391 reference
392 operator*() const _GLIBCXX_NOEXCEPT
393 { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
394
395 pointer
396 operator->() const _GLIBCXX_NOEXCEPT
397 { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
398
399 _Rb_tree_iterator&
400 operator++() _GLIBCXX_NOEXCEPT
401 {
402 _M_node = _Rb_tree_increment(x: _M_node);
403 return *this;
404 }
405
406 _Rb_tree_iterator
407 operator++(int) _GLIBCXX_NOEXCEPT
408 {
409 _Rb_tree_iterator __tmp = *this;
410 _M_node = _Rb_tree_increment(x: _M_node);
411 return __tmp;
412 }
413
414 _Rb_tree_iterator&
415 operator--() _GLIBCXX_NOEXCEPT
416 {
417 _M_node = _Rb_tree_decrement(x: _M_node);
418 return *this;
419 }
420
421 _Rb_tree_iterator
422 operator--(int) _GLIBCXX_NOEXCEPT
423 {
424 _Rb_tree_iterator __tmp = *this;
425 _M_node = _Rb_tree_decrement(x: _M_node);
426 return __tmp;
427 }
428
429 friend bool
430 operator==(const _Rb_tree_iterator& __x,
431 const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
432 { return __x._M_node == __y._M_node; }
433
434#if ! __cpp_lib_three_way_comparison
435 friend bool
436 operator!=(const _Rb_tree_iterator& __x,
437 const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
438 { return __x._M_node != __y._M_node; }
439#endif
440
441 _Base_ptr _M_node;
442 };
443
444 template<typename _Tp>
445 struct _Rb_tree_const_iterator
446 {
447 typedef _Tp value_type;
448 typedef const _Tp& reference;
449 typedef const _Tp* pointer;
450
451 typedef _Rb_tree_iterator<_Tp> iterator;
452
453 typedef bidirectional_iterator_tag iterator_category;
454 typedef ptrdiff_t difference_type;
455
456 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
457 typedef const _Rb_tree_node<_Tp>* _Node_ptr;
458
459 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
460 : _M_node() { }
461
462 explicit
463 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
464 : _M_node(__x) { }
465
466 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
467 : _M_node(__it._M_node) { }
468
469 reference
470 operator*() const _GLIBCXX_NOEXCEPT
471 { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
472
473 pointer
474 operator->() const _GLIBCXX_NOEXCEPT
475 { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
476
477 _Rb_tree_const_iterator&
478 operator++() _GLIBCXX_NOEXCEPT
479 {
480 _M_node = _Rb_tree_increment(x: _M_node);
481 return *this;
482 }
483
484 _Rb_tree_const_iterator
485 operator++(int) _GLIBCXX_NOEXCEPT
486 {
487 _Rb_tree_const_iterator __tmp = *this;
488 _M_node = _Rb_tree_increment(x: _M_node);
489 return __tmp;
490 }
491
492 _Rb_tree_const_iterator&
493 operator--() _GLIBCXX_NOEXCEPT
494 {
495 _M_node = _Rb_tree_decrement(x: _M_node);
496 return *this;
497 }
498
499 _Rb_tree_const_iterator
500 operator--(int) _GLIBCXX_NOEXCEPT
501 {
502 _Rb_tree_const_iterator __tmp = *this;
503 _M_node = _Rb_tree_decrement(x: _M_node);
504 return __tmp;
505 }
506
507 friend bool
508 operator==(const _Rb_tree_const_iterator& __x,
509 const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT
510 { return __x._M_node == __y._M_node; }
511
512#if ! __cpp_lib_three_way_comparison
513 friend bool
514 operator!=(const _Rb_tree_const_iterator& __x,
515 const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT
516 { return __x._M_node != __y._M_node; }
517#endif
518
519 _Base_ptr _M_node;
520 };
521
522 __attribute__((__nonnull__))
523 void
524 _Rb_tree_insert_and_rebalance(const bool __insert_left,
525 _Rb_tree_node_base* __x,
526 _Rb_tree_node_base* __p,
527 _Rb_tree_node_base& __header) throw ();
528
529 __attribute__((__nonnull__,__returns_nonnull__))
530 _Rb_tree_node_base*
531 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
532 _Rb_tree_node_base& __header) throw ();
533
534namespace __rb_tree
535{
536#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
537 template<bool _Const, typename _ValPtr>
538 struct _Iterator
539 {
540 template<typename _Tp>
541 using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
542
543 using __ptr_traits = pointer_traits<_ValPtr>;
544 using value_type = typename __ptr_traits::element_type;
545 using reference = __maybe_const<value_type>&;
546 using pointer = __maybe_const<value_type>*;
547
548 using iterator_category = bidirectional_iterator_tag;
549 using difference_type = ptrdiff_t;
550
551 using _Node = __rb_tree::_Node<_ValPtr>;
552 using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;
553 using _Base_ptr = typename _Node_base::_Base_ptr;
554
555 _Iterator() noexcept
556 : _M_node() { }
557
558 constexpr explicit
559 _Iterator(_Base_ptr __x) noexcept
560 : _M_node(__x) { }
561
562 _Iterator(const _Iterator&) = default;
563 _Iterator& operator=(const _Iterator&) = default;
564
565#ifdef __glibcxx_concepts
566 constexpr
567 _Iterator(const _Iterator<false, _ValPtr>& __it) requires _Const
568#else
569 template<bool _OtherConst,
570 typename = __enable_if_t<_Const && !_OtherConst>>
571 constexpr
572 _Iterator(const _Iterator<_OtherConst, _ValPtr>& __it)
573#endif
574 : _M_node(__it._M_node) { }
575
576 [[__nodiscard__]]
577 reference
578 operator*() const noexcept
579 { return *static_cast<_Node&>(*_M_node)._M_valptr(); }
580
581 [[__nodiscard__]]
582 pointer
583 operator->() const noexcept
584 { return static_cast<_Node&>(*_M_node)._M_valptr(); }
585
586 _GLIBCXX14_CONSTEXPR _Iterator&
587 operator++() noexcept
588 {
589 if (_M_node->_M_right)
590 {
591 _M_node = _M_node->_M_right;
592 while (_M_node->_M_left)
593 _M_node = _M_node->_M_left;
594 }
595 else
596 {
597 _Base_ptr __y = _M_node->_M_parent;
598 while (_M_node == __y->_M_right)
599 {
600 _M_node = __y;
601 __y = __y->_M_parent;
602 }
603 if (_M_node->_M_right != __y)
604 _M_node = __y;
605 }
606
607 return *this;
608 }
609
610 _GLIBCXX14_CONSTEXPR _Iterator
611 operator++(int) noexcept
612 {
613 _Iterator __tmp(this->_M_node);
614 ++*this;
615 return __tmp;
616 }
617
618 _GLIBCXX14_CONSTEXPR _Iterator&
619 operator--() noexcept
620 {
621 if (_M_node->_M_color == _S_red
622 && _M_node->_M_parent->_M_parent == _M_node)
623 _M_node = _M_node->_M_right;
624 else if (_M_node->_M_left)
625 {
626 _Base_ptr __y = _M_node->_M_left;
627 while (__y->_M_right)
628 __y = __y->_M_right;
629 _M_node = __y;
630 }
631 else
632 {
633 _Base_ptr __y = _M_node->_M_parent;
634 while (_M_node == __y->_M_left)
635 {
636 _M_node = __y;
637 __y = __y->_M_parent;
638 }
639 _M_node = __y;
640 }
641 return *this;
642 }
643
644 _GLIBCXX14_CONSTEXPR _Iterator
645 operator--(int) noexcept
646 {
647 _Iterator __tmp(this->_M_node);
648 --*this;
649 return __tmp;
650 }
651
652 [[__nodiscard__]]
653 friend bool
654 operator==(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT
655 { return __x._M_node == __y._M_node; }
656
657#if ! __cpp_lib_three_way_comparison
658 [[__nodiscard__]]
659 friend bool
660 operator!=(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT
661 { return __x._M_node != __y._M_node; }
662#endif
663
664 _Base_ptr _M_node;
665 };
666#endif // USE_ALLOC_PTR_FOR_RB_TREE
667
668 // Determine the node and iterator types used by std::_Rb_tree.
669 template<typename _Val, typename _Ptr>
670 struct _Node_traits;
671
672#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000
673 // Specialization for the simple case where the allocator's pointer type
674 // is the same type as value_type*.
675 // For ABI compatibility we can't change the types used for this case.
676 template<typename _Val>
677 struct _Node_traits<_Val, _Val*>
678 {
679 typedef _Rb_tree_node<_Val> _Node;
680 typedef _Node* _Node_ptr;
681 typedef _Rb_tree_node_base _Node_base;
682 typedef _Node_base* _Base_ptr;
683 typedef _Rb_tree_header _Header_t;
684 typedef _Rb_tree_iterator<_Val> _Iterator;
685 typedef _Rb_tree_const_iterator<_Val> _Const_iterator;
686
687 __attribute__((__nonnull__))
688 static void
689 _S_insert_and_rebalance(const bool __insert_left,
690 _Node_base* __x, _Node_base* __p,
691 _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
692 {
693 return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header);
694 }
695
696 __attribute__((__nonnull__,__returns_nonnull__))
697 static _Node_base*
698 _S_rebalance_for_erase(_Node_base* const __z,
699 _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
700 { return _Rb_tree_rebalance_for_erase(__z, __header); }
701 };
702#endif
703
704#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
705 // Always use the T* specialization.
706 template<typename _Val, typename _Ptr>
707 struct _Node_traits
708 : _Node_traits<_Val, _Val*>
709 { };
710#else
711 // Primary template used when the allocator uses fancy pointers.
712 template<typename _Val, typename _ValPtr>
713 struct _Node_traits
714 {
715 using _Node = __rb_tree::_Node<_ValPtr>;
716 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
717 using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;
718 using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>;
719 using _Header_t = __rb_tree::_Header<_Node_base>;
720 using _Iterator = __rb_tree::_Iterator<false, _ValPtr>;
721 using _Const_iterator = __rb_tree::_Iterator<true, _ValPtr>;
722
723 static void
724 _Rotate_left(_Base_ptr __x, _Base_ptr& __root)
725 {
726 const _Base_ptr __y = __x->_M_right;
727
728 __x->_M_right = __y->_M_left;
729 if (__y->_M_left)
730 __y->_M_left->_M_parent = __x;
731 __y->_M_parent = __x->_M_parent;
732
733 if (__x == __root)
734 __root = __y;
735 else if (__x == __x->_M_parent->_M_left)
736 __x->_M_parent->_M_left = __y;
737 else
738 __x->_M_parent->_M_right = __y;
739 __y->_M_left = __x;
740 __x->_M_parent = __y;
741 }
742
743 static void
744 _Rotate_right(_Base_ptr __x, _Base_ptr& __root)
745 {
746 const _Base_ptr __y = __x->_M_left;
747
748 __x->_M_left = __y->_M_right;
749 if (__y->_M_right)
750 __y->_M_right->_M_parent = __x;
751 __y->_M_parent = __x->_M_parent;
752
753 if (__x == __root)
754 __root = __y;
755 else if (__x == __x->_M_parent->_M_right)
756 __x->_M_parent->_M_right = __y;
757 else
758 __x->_M_parent->_M_left = __y;
759 __y->_M_right = __x;
760 __x->_M_parent = __y;
761 }
762
763 static void
764 _S_insert_and_rebalance(const bool __insert_left,
765 _Base_ptr __x, _Base_ptr __p,
766 _Node_base& __header)
767 {
768 _Base_ptr& __root = __header._M_parent;
769
770 // Initialize fields in new node to insert.
771 __x->_M_parent = __p;
772 __x->_M_left = __x->_M_right = nullptr;
773 __x->_M_color = _S_red;
774
775 // Insert.
776 // Make new node child of parent and maintain root, leftmost and
777 // rightmost nodes.
778 // N.B. First node is always inserted left.
779 if (__insert_left)
780 {
781 __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
782
783 if (std::__to_address(__p) == std::addressof(__header))
784 {
785 __header._M_parent = __x;
786 __header._M_right = __x;
787 }
788 else if (__p == __header._M_left)
789 __header._M_left = __x; // maintain leftmost pointing to min node
790 }
791 else
792 {
793 __p->_M_right = __x;
794
795 if (__p == __header._M_right)
796 __header._M_right = __x; // maintain rightmost pointing to max node
797 }
798 // Rebalance.
799 while (__x != __root
800 && __x->_M_parent->_M_color == _S_red)
801 {
802 const _Base_ptr __xpp = __x->_M_parent->_M_parent;
803
804 if (__x->_M_parent == __xpp->_M_left)
805 {
806 const _Base_ptr __y = __xpp->_M_right;
807 if (__y && __y->_M_color == _S_red)
808 {
809 __x->_M_parent->_M_color = _S_black;
810 __y->_M_color = _S_black;
811 __xpp->_M_color = _S_red;
812 __x = __xpp;
813 }
814 else
815 {
816 if (__x == __x->_M_parent->_M_right)
817 {
818 __x = __x->_M_parent;
819 _Rotate_left(__x, __root);
820 }
821 __x->_M_parent->_M_color = _S_black;
822 __xpp->_M_color = _S_red;
823 _Rotate_right(x: __xpp, __root);
824 }
825 }
826 else
827 {
828 const _Base_ptr __y = __xpp->_M_left;
829 if (__y && __y->_M_color == _S_red)
830 {
831 __x->_M_parent->_M_color = _S_black;
832 __y->_M_color = _S_black;
833 __xpp->_M_color = _S_red;
834 __x = __xpp;
835 }
836 else
837 {
838 if (__x == __x->_M_parent->_M_left)
839 {
840 __x = __x->_M_parent;
841 _Rotate_right(__x, __root);
842 }
843 __x->_M_parent->_M_color = _S_black;
844 __xpp->_M_color = _S_red;
845 _Rotate_left(x: __xpp, __root);
846 }
847 }
848 }
849 __root->_M_color = _S_black;
850 }
851
852 static _Base_ptr
853 _S_rebalance_for_erase(_Base_ptr __z, _Node_base& __header)
854 {
855 _Base_ptr& __root = __header._M_parent;
856 _Base_ptr& __leftmost = __header._M_left;
857 _Base_ptr& __rightmost = __header._M_right;
858 _Base_ptr __y = __z;
859 _Base_ptr __x{};
860 _Base_ptr __x_parent{};
861
862 if (!__y->_M_left) // __z has at most one non-null child. y == z.
863 __x = __y->_M_right; // __x might be null.
864 else
865 if (!__y->_M_right) // __z has exactly one non-null child. y == z.
866 __x = __y->_M_left; // __x is not null.
867 else
868 {
869 // __z has two non-null children. Set __y to
870 __y = __y->_M_right; // __z's successor. __x might be null.
871 while (__y->_M_left)
872 __y = __y->_M_left;
873 __x = __y->_M_right;
874 }
875 if (__y != __z)
876 {
877 // relink y in place of z. y is z's successor
878 __z->_M_left->_M_parent = __y;
879 __y->_M_left = __z->_M_left;
880 if (__y != __z->_M_right)
881 {
882 __x_parent = __y->_M_parent;
883 if (__x)
884 __x->_M_parent = __y->_M_parent;
885 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left
886 __y->_M_right = __z->_M_right;
887 __z->_M_right->_M_parent = __y;
888 }
889 else
890 __x_parent = __y;
891 if (__root == __z)
892 __root = __y;
893 else if (__z->_M_parent->_M_left == __z)
894 __z->_M_parent->_M_left = __y;
895 else
896 __z->_M_parent->_M_right = __y;
897 __y->_M_parent = __z->_M_parent;
898 std::swap(__y->_M_color, __z->_M_color);
899 __y = __z;
900 // __y now points to node to be actually deleted
901 }
902 else
903 { // __y == __z
904 __x_parent = __y->_M_parent;
905 if (__x)
906 __x->_M_parent = __y->_M_parent;
907 if (__root == __z)
908 __root = __x;
909 else
910 if (__z->_M_parent->_M_left == __z)
911 __z->_M_parent->_M_left = __x;
912 else
913 __z->_M_parent->_M_right = __x;
914 if (__leftmost == __z)
915 {
916 if (!__z->_M_right) // __z->_M_left must be null also
917 __leftmost = __z->_M_parent;
918 // makes __leftmost == _M_header if __z == __root
919 else
920 __leftmost = _Node_base::_S_minimum(__x);
921 }
922 if (__rightmost == __z)
923 {
924 if (__z->_M_left == 0) // __z->_M_right must be null also
925 __rightmost = __z->_M_parent;
926 // makes __rightmost == _M_header if __z == __root
927 else // __x == __z->_M_left
928 __rightmost = _Node_base::_S_maximum(__x);
929 }
930 }
931 if (__y->_M_color != _S_red)
932 {
933 while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
934 if (__x == __x_parent->_M_left)
935 {
936 _Base_ptr __w = __x_parent->_M_right;
937 if (__w->_M_color == _S_red)
938 {
939 __w->_M_color = _S_black;
940 __x_parent->_M_color = _S_red;
941 _Rotate_left(x: __x_parent, __root);
942 __w = __x_parent->_M_right;
943 }
944 if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) &&
945 (!__w->_M_right || __w->_M_right->_M_color == _S_black))
946 {
947 __w->_M_color = _S_red;
948 __x = __x_parent;
949 __x_parent = __x_parent->_M_parent;
950 }
951 else
952 {
953 if (!__w->_M_right || __w->_M_right->_M_color == _S_black)
954 {
955 __w->_M_left->_M_color = _S_black;
956 __w->_M_color = _S_red;
957 _Rotate_right(x: __w, __root);
958 __w = __x_parent->_M_right;
959 }
960 __w->_M_color = __x_parent->_M_color;
961 __x_parent->_M_color = _S_black;
962 if (__w->_M_right)
963 __w->_M_right->_M_color = _S_black;
964 _Rotate_left(x: __x_parent, __root);
965 break;
966 }
967 }
968 else
969 {
970 // same as above, with _M_right <-> _M_left.
971 _Base_ptr __w = __x_parent->_M_left;
972 if (__w->_M_color == _S_red)
973 {
974 __w->_M_color = _S_black;
975 __x_parent->_M_color = _S_red;
976 _Rotate_right(x: __x_parent, __root);
977 __w = __x_parent->_M_left;
978 }
979 if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) &&
980 (!__w->_M_left || __w->_M_left->_M_color == _S_black))
981 {
982 __w->_M_color = _S_red;
983 __x = __x_parent;
984 __x_parent = __x_parent->_M_parent;
985 }
986 else
987 {
988 if (!__w->_M_left || __w->_M_left->_M_color == _S_black)
989 {
990 __w->_M_right->_M_color = _S_black;
991 __w->_M_color = _S_red;
992 _Rotate_left(x: __w, __root);
993 __w = __x_parent->_M_left;
994 }
995 __w->_M_color = __x_parent->_M_color;
996 __x_parent->_M_color = _S_black;
997 if (__w->_M_left)
998 __w->_M_left->_M_color = _S_black;
999 _Rotate_right(x: __x_parent, __root);
1000 break;
1001 }
1002 }
1003 if (__x)
1004 __x->_M_color = _S_black;
1005 }
1006
1007 return __y;
1008 }
1009 };
1010#endif
1011} // namespace __rb_tree
1012
1013#ifdef __glibcxx_node_extract // >= C++17
1014 template<typename _Tree1, typename _Cmp2>
1015 struct _Rb_tree_merge_helper { };
1016#endif
1017
1018 template<typename _Key, typename _Val, typename _KeyOfValue,
1019 typename _Compare, typename _Alloc = allocator<_Val> >
1020 class _Rb_tree
1021 {
1022 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
1023 rebind<_Val>::other _Val_alloc_type;
1024
1025 typedef __gnu_cxx::__alloc_traits<_Val_alloc_type> _Val_alloc_traits;
1026 typedef typename _Val_alloc_traits::pointer _ValPtr;
1027 typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits;
1028
1029 typedef typename _Node_traits::_Node_base _Node_base;
1030 typedef typename _Node_traits::_Node _Node;
1031
1032 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
1033 rebind<_Node>::other _Node_allocator;
1034
1035 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Node_alloc_traits;
1036
1037 protected:
1038 typedef typename _Node_traits::_Base_ptr _Base_ptr;
1039 typedef typename _Node_traits::_Node_ptr _Node_ptr;
1040
1041 private:
1042 // Functor recycling a pool of nodes and using allocation once the pool
1043 // is empty.
1044 struct _Reuse_or_alloc_node
1045 {
1046 _Reuse_or_alloc_node(_Rb_tree& __t)
1047 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
1048 {
1049 if (_M_root)
1050 {
1051 _M_root->_M_parent = _Base_ptr();
1052
1053 if (_M_nodes->_M_left)
1054 _M_nodes = _M_nodes->_M_left;
1055 }
1056 else
1057 _M_nodes = _Base_ptr();
1058 }
1059
1060#if __cplusplus >= 201103L
1061 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
1062#endif
1063
1064 ~_Reuse_or_alloc_node()
1065 {
1066 if (_M_root)
1067 _M_t._M_erase(x: static_cast<_Node&>(*_M_root)._M_node_ptr());
1068 }
1069
1070 template<typename _Arg>
1071 _Node_ptr
1072 operator()(_GLIBCXX_FWDREF(_Arg) __arg)
1073 {
1074 _Base_ptr __base = _M_extract();
1075 if (__base)
1076 {
1077 _Node_ptr __node = static_cast<_Node&>(*__base)._M_node_ptr();
1078 _M_t._M_destroy_node(p: __node);
1079 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
1080 return __node;
1081 }
1082
1083 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
1084 }
1085
1086 private:
1087 _Base_ptr
1088 _M_extract()
1089 {
1090 if (!_M_nodes)
1091 return _M_nodes;
1092
1093 _Base_ptr __node = _M_nodes;
1094 _M_nodes = _M_nodes->_M_parent;
1095 if (_M_nodes)
1096 {
1097 if (_M_nodes->_M_right == __node)
1098 {
1099 _M_nodes->_M_right = _Base_ptr();
1100
1101 if (_M_nodes->_M_left)
1102 {
1103 _M_nodes = _M_nodes->_M_left;
1104
1105 while (_M_nodes->_M_right)
1106 _M_nodes = _M_nodes->_M_right;
1107
1108 if (_M_nodes->_M_left)
1109 _M_nodes = _M_nodes->_M_left;
1110 }
1111 }
1112 else // __node is on the left.
1113 _M_nodes->_M_left = _Base_ptr();
1114 }
1115 else
1116 _M_root = _Base_ptr();
1117
1118 return __node;
1119 }
1120
1121 _Base_ptr _M_root;
1122 _Base_ptr _M_nodes;
1123 _Rb_tree& _M_t;
1124 };
1125
1126 // Functor similar to the previous one but without any pool of nodes to
1127 // recycle.
1128 struct _Alloc_node
1129 {
1130 _Alloc_node(_Rb_tree& __t)
1131 : _M_t(__t) { }
1132
1133 template<typename _Arg>
1134 _Node_ptr
1135 operator()(_GLIBCXX_FWDREF(_Arg) __arg) const
1136 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
1137
1138 private:
1139 _Rb_tree& _M_t;
1140 };
1141
1142 public:
1143 typedef _Key key_type;
1144 typedef _Val value_type;
1145 typedef value_type* pointer;
1146 typedef const value_type* const_pointer;
1147 typedef value_type& reference;
1148 typedef const value_type& const_reference;
1149 typedef size_t size_type;
1150 typedef ptrdiff_t difference_type;
1151 typedef _Alloc allocator_type;
1152
1153 _Node_allocator&
1154 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
1155 { return this->_M_impl; }
1156
1157 const _Node_allocator&
1158 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
1159 { return this->_M_impl; }
1160
1161 allocator_type
1162 get_allocator() const _GLIBCXX_NOEXCEPT
1163 { return allocator_type(_M_get_Node_allocator()); }
1164
1165 protected:
1166 _Node_ptr
1167 _M_get_node()
1168 {
1169#if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
1170 return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
1171#else
1172#pragma GCC diagnostic push
1173#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1174 using __alloc_pointer = typename _Node_alloc_traits::pointer;
1175 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
1176 return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
1177 else
1178 {
1179 auto __ptr =
1180 _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
1181 return std::__to_address(__ptr);
1182 }
1183#pragma GCC diagnostic pop
1184#endif
1185 }
1186
1187 void
1188 _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1189 {
1190#if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
1191 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
1192#else
1193#pragma GCC diagnostic push
1194#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1195 using __alloc_pointer = typename _Node_alloc_traits::pointer;
1196 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
1197 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
1198 else
1199 {
1200 // When not using the allocator's pointer type internally we must
1201 // convert __p to __alloc_pointer so it can be deallocated.
1202 auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);
1203 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ap, 1);
1204 }
1205#pragma GCC diagnostic pop
1206#endif
1207 }
1208
1209#if __cplusplus < 201103L
1210 void
1211 _M_construct_node(_Node_ptr __node, const value_type& __x)
1212 {
1213 __try
1214 { get_allocator().construct(__node->_M_valptr(), __x); }
1215 __catch(...)
1216 {
1217 _M_put_node(__node);
1218 __throw_exception_again;
1219 }
1220 }
1221
1222 _Node_ptr
1223 _M_create_node(const value_type& __x)
1224 {
1225 _Node_ptr __tmp = _M_get_node();
1226 _M_construct_node(__tmp, __x);
1227 return __tmp;
1228 }
1229#else
1230 template<typename... _Args>
1231 void
1232 _M_construct_node(_Node_ptr __node, _Args&&... __args)
1233 {
1234 __try
1235 {
1236 ::new(std::addressof(*__node)) _Node;
1237 _Node_alloc_traits::construct(_M_get_Node_allocator(),
1238 __node->_M_valptr(),
1239 std::forward<_Args>(__args)...);
1240 }
1241 __catch(...)
1242 {
1243 __node->~_Node();
1244 _M_put_node(p: __node);
1245 __throw_exception_again;
1246 }
1247 }
1248
1249 template<typename... _Args>
1250 _Node_ptr
1251 _M_create_node(_Args&&... __args)
1252 {
1253 _Node_ptr __tmp = _M_get_node();
1254 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
1255 return __tmp;
1256 }
1257#endif
1258
1259 void
1260 _M_destroy_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1261 {
1262#if __cplusplus < 201103L
1263 get_allocator().destroy(__p->_M_valptr());
1264#else
1265 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
1266 __p->~_Node();
1267#endif
1268 }
1269
1270 void
1271 _M_drop_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1272 {
1273 _M_destroy_node(__p);
1274 _M_put_node(__p);
1275 }
1276
1277 template<bool _MoveValue, typename _NodeGen>
1278 _Node_ptr
1279 _M_clone_node(_Node_ptr __x, _NodeGen& __node_gen)
1280 {
1281#if __cplusplus >= 201103L
1282 using _Vp = __conditional_t<_MoveValue,
1283 value_type&&,
1284 const value_type&>;
1285#endif
1286 _Node_ptr __tmp
1287 = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));
1288 __tmp->_M_color = __x->_M_color;
1289 __tmp->_M_left = __tmp->_M_right = _Base_ptr();
1290 return __tmp;
1291 }
1292
1293 protected:
1294 typedef typename _Node_traits::_Header_t _Header_t;
1295
1296#if _GLIBCXX_INLINE_VERSION
1297 template<typename _Key_compare>
1298#else
1299 // Unused _Is_pod_comparator is kept as it is part of mangled name.
1300 template<typename _Key_compare,
1301 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
1302#endif
1303 struct _Rb_tree_impl
1304 : public _Node_allocator
1305 , public _Rb_tree_key_compare<_Key_compare>
1306 , public _Header_t
1307 {
1308 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
1309
1310 _Rb_tree_impl()
1311 _GLIBCXX_NOEXCEPT_IF(
1312 is_nothrow_default_constructible<_Node_allocator>::value
1313 && is_nothrow_default_constructible<_Base_key_compare>::value )
1314 : _Node_allocator()
1315 { }
1316
1317 _Rb_tree_impl(const _Rb_tree_impl& __x)
1318 : _Node_allocator(_Node_alloc_traits::_S_select_on_copy(__x))
1319 , _Base_key_compare(__x._M_key_compare)
1320 , _Header_t()
1321 { }
1322
1323#if __cplusplus < 201103L
1324 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
1325 : _Node_allocator(__a), _Base_key_compare(__comp)
1326 { }
1327#else
1328 _Rb_tree_impl(_Rb_tree_impl&&)
1329 noexcept( is_nothrow_move_constructible<_Base_key_compare>::value )
1330 = default;
1331
1332 explicit
1333 _Rb_tree_impl(_Node_allocator&& __a)
1334 : _Node_allocator(std::move(__a))
1335 { }
1336
1337 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
1338 : _Node_allocator(std::move(__a)),
1339 _Base_key_compare(std::move(__x)),
1340 _Header_t(std::move(__x))
1341 { }
1342
1343 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
1344 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
1345 { }
1346#endif
1347 };
1348
1349 _Rb_tree_impl<_Compare> _M_impl;
1350
1351 protected:
1352 _Base_ptr&
1353 _M_root() _GLIBCXX_NOEXCEPT
1354 { return this->_M_impl._M_header._M_parent; }
1355
1356 _Base_ptr
1357 _M_root() const _GLIBCXX_NOEXCEPT
1358 { return this->_M_impl._M_header._M_parent; }
1359
1360 _Base_ptr&
1361 _M_leftmost() _GLIBCXX_NOEXCEPT
1362 { return this->_M_impl._M_header._M_left; }
1363
1364 _Base_ptr
1365 _M_leftmost() const _GLIBCXX_NOEXCEPT
1366 { return this->_M_impl._M_header._M_left; }
1367
1368 _Base_ptr&
1369 _M_rightmost() _GLIBCXX_NOEXCEPT
1370 { return this->_M_impl._M_header._M_right; }
1371
1372 _Base_ptr
1373 _M_rightmost() const _GLIBCXX_NOEXCEPT
1374 { return this->_M_impl._M_header._M_right; }
1375
1376 _Base_ptr
1377 _M_begin() const _GLIBCXX_NOEXCEPT
1378 { return this->_M_impl._M_header._M_parent; }
1379
1380 _Node_ptr
1381 _M_begin_node() const _GLIBCXX_NOEXCEPT
1382 {
1383 _Base_ptr __begin = this->_M_impl._M_header._M_parent;
1384 return __begin
1385 ? static_cast<_Node&>(*__begin)._M_node_ptr()
1386 : _Node_ptr();
1387 }
1388
1389 _Base_ptr
1390 _M_end() const _GLIBCXX_NOEXCEPT
1391 { return this->_M_impl._M_header._M_base_ptr(); }
1392
1393 static const _Key&
1394 _S_key(const _Node& __node)
1395 {
1396#if __cplusplus >= 201103L
1397 // If we're asking for the key we're presumably using the comparison
1398 // object, and so this is a good place to sanity check it.
1399 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
1400 "comparison object must be invocable "
1401 "with two arguments of key type");
1402# if __cplusplus >= 201703L
1403 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1404 // 2542. Missing const requirements for associative containers
1405 if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
1406 static_assert(
1407 is_invocable_v<const _Compare&, const _Key&, const _Key&>,
1408 "comparison object must be invocable as const");
1409# endif // C++17
1410#endif // C++11
1411
1412 return _KeyOfValue()(*__node._M_valptr());
1413 }
1414
1415 static const _Key&
1416 _S_key(_Base_ptr __x)
1417 { return _S_key(static_cast<const _Node&>(*__x)); }
1418
1419 static const _Key&
1420 _S_key(_Node_ptr __x)
1421 { return _S_key(*__x); }
1422
1423 static _Base_ptr
1424 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
1425 { return __x->_M_left; }
1426
1427 static _Node_ptr
1428 _S_left(_Node_ptr __x)
1429 {
1430 return __x->_M_left
1431 ? static_cast<_Node&>(*__x->_M_left)._M_node_ptr()
1432 : _Node_ptr();
1433 }
1434
1435 static _Base_ptr
1436 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
1437 { return __x->_M_right; }
1438
1439 static _Node_ptr
1440 _S_right(_Node_ptr __x) _GLIBCXX_NOEXCEPT
1441 {
1442 return __x->_M_right
1443 ? static_cast<_Node&>(*__x->_M_right)._M_node_ptr()
1444 : _Node_ptr();
1445 }
1446
1447 public:
1448 typedef typename _Node_traits::_Iterator iterator;
1449 typedef typename _Node_traits::_Const_iterator const_iterator;
1450
1451 typedef std::reverse_iterator<iterator> reverse_iterator;
1452 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1453
1454#ifdef __glibcxx_node_extract // >= C++17
1455 using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
1456 using insert_return_type = _Node_insert_return<
1457 __conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
1458 node_type>;
1459#endif
1460
1461 pair<_Base_ptr, _Base_ptr>
1462 _M_get_insert_unique_pos(const key_type& __k);
1463
1464 pair<_Base_ptr, _Base_ptr>
1465 _M_get_insert_equal_pos(const key_type& __k);
1466
1467 pair<_Base_ptr, _Base_ptr>
1468 _M_get_insert_hint_unique_pos(const_iterator __pos,
1469 const key_type& __k);
1470
1471 pair<_Base_ptr, _Base_ptr>
1472 _M_get_insert_hint_equal_pos(const_iterator __pos,
1473 const key_type& __k);
1474
1475 private:
1476#if __cplusplus >= 201103L
1477 template<typename _Arg, typename _NodeGen>
1478 iterator
1479 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
1480
1481 iterator
1482 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Node_ptr __z);
1483
1484 template<typename _Arg>
1485 iterator
1486 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
1487
1488 template<typename _Arg>
1489 iterator
1490 _M_insert_equal_lower(_Arg&& __x);
1491
1492 iterator
1493 _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z);
1494
1495 iterator
1496 _M_insert_equal_lower_node(_Node_ptr __z);
1497#else
1498 template<typename _NodeGen>
1499 iterator
1500 _M_insert_(_Base_ptr __x, _Base_ptr __y,
1501 const value_type& __v, _NodeGen&);
1502
1503 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1504 // 233. Insertion hints in associative containers.
1505 iterator
1506 _M_insert_lower(_Base_ptr __y, const value_type& __v);
1507
1508 iterator
1509 _M_insert_equal_lower(const value_type& __x);
1510#endif
1511
1512 enum { __as_lvalue, __as_rvalue };
1513
1514 template<bool _MoveValues, typename _NodeGen>
1515 _Base_ptr
1516 _M_copy(_Node_ptr, _Base_ptr, _NodeGen&);
1517
1518 template<bool _MoveValues, typename _NodeGen>
1519 _Base_ptr
1520 _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
1521 {
1522 _Base_ptr __root =
1523 _M_copy<_MoveValues>(__x._M_begin_node(), _M_end(), __gen);
1524 _M_leftmost() = _Node_base::_S_minimum(__root);
1525 _M_rightmost() = _Node_base::_S_maximum(__root);
1526 _M_impl._M_node_count = __x._M_impl._M_node_count;
1527 return __root;
1528 }
1529
1530 _Base_ptr
1531 _M_copy(const _Rb_tree& __x)
1532 {
1533 _Alloc_node __an(*this);
1534 return _M_copy<__as_lvalue>(__x, __an);
1535 }
1536
1537 void
1538 _M_erase(_Node_ptr __x);
1539
1540 _Base_ptr
1541 _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
1542 const _Key& __k) const;
1543
1544 _Base_ptr
1545 _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
1546 const _Key& __k) const;
1547
1548 public:
1549 // allocation/deallocation
1550#if __cplusplus < 201103L
1551 _Rb_tree() { }
1552#else
1553 _Rb_tree() = default;
1554#endif
1555
1556 _Rb_tree(const _Compare& __comp,
1557 const allocator_type& __a = allocator_type())
1558 : _M_impl(__comp, _Node_allocator(__a)) { }
1559
1560 _Rb_tree(const _Rb_tree& __x)
1561 : _M_impl(__x._M_impl)
1562 {
1563 if (__x._M_root())
1564 _M_root() = _M_copy(__x);
1565 }
1566
1567#if __cplusplus >= 201103L
1568 _Rb_tree(const allocator_type& __a)
1569 : _M_impl(_Node_allocator(__a))
1570 { }
1571
1572 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
1573 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
1574 {
1575 if (__x._M_root())
1576 _M_root() = _M_copy(__x);
1577 }
1578
1579 _Rb_tree(_Rb_tree&&) = default;
1580
1581 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
1582 : _Rb_tree(std::move(__x), _Node_allocator(__a))
1583 { }
1584
1585 private:
1586 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
1587 noexcept(is_nothrow_default_constructible<_Compare>::value)
1588 : _M_impl(std::move(__x._M_impl), std::move(__a))
1589 { }
1590
1591 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
1592 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1593 {
1594 if (__x._M_root())
1595 _M_move_data(__x, false_type{});
1596 }
1597
1598 public:
1599 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1600 noexcept( noexcept(
1601 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
1602 std::declval<typename _Node_alloc_traits::is_always_equal>())) )
1603 : _Rb_tree(std::move(__x), std::move(__a),
1604 typename _Node_alloc_traits::is_always_equal{})
1605 { }
1606#endif
1607
1608 ~_Rb_tree() _GLIBCXX_NOEXCEPT
1609 { _M_erase(x: _M_begin_node()); }
1610
1611 _Rb_tree&
1612 operator=(const _Rb_tree& __x);
1613
1614 // Accessors.
1615 _Compare
1616 key_comp() const
1617 { return _M_impl._M_key_compare; }
1618
1619 iterator
1620 begin() _GLIBCXX_NOEXCEPT
1621 { return iterator(this->_M_impl._M_header._M_left); }
1622
1623 const_iterator
1624 begin() const _GLIBCXX_NOEXCEPT
1625 { return const_iterator(this->_M_impl._M_header._M_left); }
1626
1627 iterator
1628 end() _GLIBCXX_NOEXCEPT
1629 { return iterator(_M_end()); }
1630
1631 const_iterator
1632 end() const _GLIBCXX_NOEXCEPT
1633 { return const_iterator(_M_end()); }
1634
1635 reverse_iterator
1636 rbegin() _GLIBCXX_NOEXCEPT
1637 { return reverse_iterator(end()); }
1638
1639 const_reverse_iterator
1640 rbegin() const _GLIBCXX_NOEXCEPT
1641 { return const_reverse_iterator(end()); }
1642
1643 reverse_iterator
1644 rend() _GLIBCXX_NOEXCEPT
1645 { return reverse_iterator(begin()); }
1646
1647 const_reverse_iterator
1648 rend() const _GLIBCXX_NOEXCEPT
1649 { return const_reverse_iterator(begin()); }
1650
1651 _GLIBCXX_NODISCARD bool
1652 empty() const _GLIBCXX_NOEXCEPT
1653 { return _M_impl._M_node_count == 0; }
1654
1655 size_type
1656 size() const _GLIBCXX_NOEXCEPT
1657 { return _M_impl._M_node_count; }
1658
1659 size_type
1660 max_size() const _GLIBCXX_NOEXCEPT
1661 { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
1662
1663 void
1664 swap(_Rb_tree& __t)
1665 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1666
1667 // Insert/erase.
1668#if __cplusplus >= 201103L
1669 template<typename _Arg>
1670 pair<iterator, bool>
1671 _M_insert_unique(_Arg&& __x);
1672
1673 template<typename _Arg>
1674 iterator
1675 _M_insert_equal(_Arg&& __x);
1676
1677 template<typename _Arg, typename _NodeGen>
1678 iterator
1679 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1680
1681 template<typename _Arg>
1682 iterator
1683 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1684 {
1685 _Alloc_node __an(*this);
1686 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1687 }
1688
1689 template<typename _Arg, typename _NodeGen>
1690 iterator
1691 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1692
1693 template<typename _Arg>
1694 iterator
1695 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1696 {
1697 _Alloc_node __an(*this);
1698 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1699 }
1700
1701 template<typename... _Args>
1702 pair<iterator, bool>
1703 _M_emplace_unique(_Args&&... __args);
1704
1705 template<typename... _Args>
1706 iterator
1707 _M_emplace_equal(_Args&&... __args);
1708
1709 template<typename... _Args>
1710 iterator
1711 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1712
1713 template<typename... _Args>
1714 iterator
1715 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1716
1717 template<typename _Iter>
1718 using __same_value_type
1719 = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1720
1721 template<typename _InputIterator>
1722 __enable_if_t<__same_value_type<_InputIterator>::value>
1723 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1724 {
1725 _Alloc_node __an(*this);
1726 for (; __first != __last; ++__first)
1727 _M_insert_unique_(end(), *__first, __an);
1728 }
1729
1730 template<typename _InputIterator>
1731 __enable_if_t<!__same_value_type<_InputIterator>::value>
1732 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1733 {
1734 for (; __first != __last; ++__first)
1735 _M_emplace_unique(*__first);
1736 }
1737
1738 template<typename _InputIterator>
1739 __enable_if_t<__same_value_type<_InputIterator>::value>
1740 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1741 {
1742 _Alloc_node __an(*this);
1743 for (; __first != __last; ++__first)
1744 _M_insert_equal_(end(), *__first, __an);
1745 }
1746
1747 template<typename _InputIterator>
1748 __enable_if_t<!__same_value_type<_InputIterator>::value>
1749 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1750 {
1751 for (; __first != __last; ++__first)
1752 _M_emplace_equal(*__first);
1753 }
1754#else
1755 pair<iterator, bool>
1756 _M_insert_unique(const value_type& __x);
1757
1758 iterator
1759 _M_insert_equal(const value_type& __x);
1760
1761 template<typename _NodeGen>
1762 iterator
1763 _M_insert_unique_(const_iterator __pos, const value_type& __x,
1764 _NodeGen&);
1765
1766 iterator
1767 _M_insert_unique_(const_iterator __pos, const value_type& __x)
1768 {
1769 _Alloc_node __an(*this);
1770 return _M_insert_unique_(__pos, __x, __an);
1771 }
1772
1773 template<typename _NodeGen>
1774 iterator
1775 _M_insert_equal_(const_iterator __pos, const value_type& __x,
1776 _NodeGen&);
1777 iterator
1778 _M_insert_equal_(const_iterator __pos, const value_type& __x)
1779 {
1780 _Alloc_node __an(*this);
1781 return _M_insert_equal_(__pos, __x, __an);
1782 }
1783
1784 template<typename _InputIterator>
1785 void
1786 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1787 {
1788 _Alloc_node __an(*this);
1789 for (; __first != __last; ++__first)
1790 _M_insert_unique_(end(), *__first, __an);
1791 }
1792
1793 template<typename _InputIterator>
1794 void
1795 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1796 {
1797 _Alloc_node __an(*this);
1798 for (; __first != __last; ++__first)
1799 _M_insert_equal_(end(), *__first, __an);
1800 }
1801#endif
1802
1803 private:
1804 void
1805 _M_erase_aux(const_iterator __position);
1806
1807 void
1808 _M_erase_aux(const_iterator __first, const_iterator __last);
1809
1810 public:
1811#if __cplusplus >= 201103L
1812 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1813 // DR 130. Associative erase should return an iterator.
1814 _GLIBCXX_ABI_TAG_CXX11
1815 iterator
1816 erase(const_iterator __position)
1817 {
1818 __glibcxx_assert(__position != end());
1819 const_iterator __result = __position;
1820 ++__result;
1821 _M_erase_aux(__position);
1822 return iterator(__result._M_node);
1823 }
1824
1825 // LWG 2059.
1826 _GLIBCXX_ABI_TAG_CXX11
1827 iterator
1828 erase(iterator __position)
1829 {
1830 __glibcxx_assert(__position != end());
1831 iterator __result = __position;
1832 ++__result;
1833 _M_erase_aux(__position);
1834 return __result;
1835 }
1836#else
1837 void
1838 erase(iterator __position)
1839 {
1840 __glibcxx_assert(__position != end());
1841 _M_erase_aux(__position);
1842 }
1843
1844 void
1845 erase(const_iterator __position)
1846 {
1847 __glibcxx_assert(__position != end());
1848 _M_erase_aux(__position);
1849 }
1850#endif
1851
1852 size_type
1853 erase(const key_type& __x);
1854
1855#if __cplusplus >= 201103L
1856 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1857 // DR 130. Associative erase should return an iterator.
1858 _GLIBCXX_ABI_TAG_CXX11
1859 iterator
1860 erase(const_iterator __first, const_iterator __last)
1861 {
1862 _M_erase_aux(__first, __last);
1863 return iterator(__last._M_node);
1864 }
1865#else
1866 void
1867 erase(iterator __first, iterator __last)
1868 { _M_erase_aux(__first, __last); }
1869
1870 void
1871 erase(const_iterator __first, const_iterator __last)
1872 { _M_erase_aux(__first, __last); }
1873#endif
1874
1875 void
1876 clear() _GLIBCXX_NOEXCEPT
1877 {
1878 _M_erase(x: _M_begin_node());
1879 _M_impl._M_reset();
1880 }
1881
1882 // Set operations.
1883 iterator
1884 find(const key_type& __k);
1885
1886 const_iterator
1887 find(const key_type& __k) const;
1888
1889 size_type
1890 count(const key_type& __k) const;
1891
1892 iterator
1893 lower_bound(const key_type& __k)
1894 { return iterator(_M_lower_bound(x: _M_begin(), y: _M_end(), __k)); }
1895
1896 const_iterator
1897 lower_bound(const key_type& __k) const
1898 {
1899 return const_iterator
1900 (_M_lower_bound(x: _M_begin(), y: _M_end(), __k));
1901 }
1902
1903 iterator
1904 upper_bound(const key_type& __k)
1905 { return iterator(_M_upper_bound(x: _M_begin(), y: _M_end(), __k)); }
1906
1907 const_iterator
1908 upper_bound(const key_type& __k) const
1909 {
1910 return const_iterator
1911 (_M_upper_bound(x: _M_begin(), y: _M_end(), __k));
1912 }
1913
1914 pair<iterator, iterator>
1915 equal_range(const key_type& __k);
1916
1917 pair<const_iterator, const_iterator>
1918 equal_range(const key_type& __k) const;
1919
1920#if __cplusplus >= 201402L
1921 template<typename _Kt,
1922 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1923 iterator
1924 _M_find_tr(const _Kt& __k)
1925 {
1926 const _Rb_tree* __const_this = this;
1927 return iterator(__const_this->_M_find_tr(__k)._M_node);
1928 }
1929
1930 template<typename _Kt,
1931 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1932 const_iterator
1933 _M_find_tr(const _Kt& __k) const
1934 {
1935 const_iterator __j(_M_lower_bound_tr(__k));
1936 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1937 __j = end();
1938 return __j;
1939 }
1940
1941 template<typename _Kt,
1942 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1943 size_type
1944 _M_count_tr(const _Kt& __k) const
1945 {
1946 auto __p = _M_equal_range_tr(__k);
1947 return std::distance(__p.first, __p.second);
1948 }
1949
1950 template<typename _Kt,
1951 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1952 _Base_ptr
1953 _M_lower_bound_tr(const _Kt& __k) const
1954 {
1955 auto __x = _M_begin();
1956 auto __y = _M_end();
1957 while (__x)
1958 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1959 {
1960 __y = __x;
1961 __x = _S_left(__x);
1962 }
1963 else
1964 __x = _S_right(__x);
1965 return __y;
1966 }
1967
1968 template<typename _Kt,
1969 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1970 _Base_ptr
1971 _M_upper_bound_tr(const _Kt& __k) const
1972 {
1973 auto __x = _M_begin();
1974 auto __y = _M_end();
1975 while (__x)
1976 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1977 {
1978 __y = __x;
1979 __x = _S_left(__x);
1980 }
1981 else
1982 __x = _S_right(__x);
1983 return __y;
1984 }
1985
1986 template<typename _Kt,
1987 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1988 pair<iterator, iterator>
1989 _M_equal_range_tr(const _Kt& __k)
1990 {
1991 const _Rb_tree* __const_this = this;
1992 auto __ret = __const_this->_M_equal_range_tr(__k);
1993 return
1994 { iterator(__ret.first._M_node), iterator(__ret.second._M_node) };
1995 }
1996
1997 template<typename _Kt,
1998 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1999 pair<const_iterator, const_iterator>
2000 _M_equal_range_tr(const _Kt& __k) const
2001 {
2002 const_iterator __low(_M_lower_bound_tr(__k));
2003 auto __high = __low;
2004 auto& __cmp = _M_impl._M_key_compare;
2005 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
2006 ++__high;
2007 return { __low, __high };
2008 }
2009#endif
2010
2011 // Debugging.
2012 bool
2013 __rb_verify() const;
2014
2015#if __cplusplus >= 201103L
2016 _Rb_tree&
2017 operator=(_Rb_tree&&)
2018 noexcept(_Node_alloc_traits::_S_nothrow_move()
2019 && is_nothrow_move_assignable<_Compare>::value);
2020
2021 template<typename _Iterator>
2022 void
2023 _M_assign_unique(_Iterator, _Iterator);
2024
2025 template<typename _Iterator>
2026 void
2027 _M_assign_equal(_Iterator, _Iterator);
2028
2029 private:
2030 // Move elements from container with equal allocator.
2031 void
2032 _M_move_data(_Rb_tree& __x, true_type)
2033 { _M_impl._M_move_data(__x._M_impl); }
2034
2035 // Move elements from container with possibly non-equal allocator,
2036 // which might result in a copy not a move.
2037 void
2038 _M_move_data(_Rb_tree&, false_type);
2039
2040 // Move assignment from container with equal allocator.
2041 void
2042 _M_move_assign(_Rb_tree&, true_type);
2043
2044 // Move assignment from container with possibly non-equal allocator,
2045 // which might result in a copy not a move.
2046 void
2047 _M_move_assign(_Rb_tree&, false_type);
2048#endif
2049
2050#if __glibcxx_node_extract // >= C++17
2051 static _Node_ptr
2052 _S_adapt(typename _Node_alloc_traits::pointer __ptr)
2053 {
2054#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
2055 return __ptr;
2056#else
2057#pragma GCC diagnostic push
2058#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
2059 using __alloc_ptr = typename _Node_alloc_traits::pointer;
2060 if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
2061 return __ptr;
2062 else
2063 return std::__to_address(__ptr);
2064#pragma GCC diagnostic pop
2065#endif
2066 }
2067
2068 public:
2069 /// Re-insert an extracted node.
2070 insert_return_type
2071 _M_reinsert_node_unique(node_type&& __nh)
2072 {
2073 insert_return_type __ret;
2074 if (__nh.empty())
2075 __ret.position = end();
2076 else
2077 {
2078 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2079
2080 auto __res = _M_get_insert_unique_pos(k: __nh._M_key());
2081 if (__res.second)
2082 {
2083 __ret.position
2084 = _M_insert_node(x: __res.first, y: __res.second,
2085 z: _S_adapt(ptr: __nh._M_ptr));
2086 __nh.release();
2087 __ret.inserted = true;
2088 }
2089 else
2090 {
2091 __ret.node = std::move(__nh);
2092 __ret.position = iterator(__res.first);
2093 __ret.inserted = false;
2094 }
2095 }
2096 return __ret;
2097 }
2098
2099 /// Re-insert an extracted node.
2100 iterator
2101 _M_reinsert_node_equal(node_type&& __nh)
2102 {
2103 iterator __ret;
2104 if (__nh.empty())
2105 __ret = end();
2106 else
2107 {
2108 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2109 auto __res = _M_get_insert_equal_pos(k: __nh._M_key());
2110 if (__res.second)
2111 __ret = _M_insert_node(x: __res.first, y: __res.second,
2112 z: _S_adapt(ptr: __nh._M_ptr));
2113 else
2114 __ret = _M_insert_equal_lower_node(z: _S_adapt(ptr: __nh._M_ptr));
2115 __nh.release();
2116 }
2117 return __ret;
2118 }
2119
2120 /// Re-insert an extracted node.
2121 iterator
2122 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
2123 {
2124 iterator __ret;
2125 if (__nh.empty())
2126 __ret = end();
2127 else
2128 {
2129 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2130 auto __res = _M_get_insert_hint_unique_pos(pos: __hint, k: __nh._M_key());
2131 if (__res.second)
2132 {
2133 __ret = _M_insert_node(x: __res.first, y: __res.second,
2134 z: _S_adapt(ptr: __nh._M_ptr));
2135 __nh.release();
2136 }
2137 else
2138 __ret = iterator(__res.first);
2139 }
2140 return __ret;
2141 }
2142
2143 /// Re-insert an extracted node.
2144 iterator
2145 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
2146 {
2147 iterator __ret;
2148 if (__nh.empty())
2149 __ret = end();
2150 else
2151 {
2152 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2153 auto __res = _M_get_insert_hint_equal_pos(pos: __hint, k: __nh._M_key());
2154 if (__res.second)
2155 __ret = _M_insert_node(x: __res.first, y: __res.second,
2156 z: _S_adapt(ptr: __nh._M_ptr));
2157 else
2158 __ret = _M_insert_equal_lower_node(z: _S_adapt(ptr: __nh._M_ptr));
2159 __nh.release();
2160 }
2161 return __ret;
2162 }
2163
2164 /// Extract a node.
2165 node_type
2166 extract(const_iterator __pos)
2167 {
2168 auto __ptr = _Node_traits::_S_rebalance_for_erase
2169 (__pos._M_node, _M_impl._M_header);
2170 --_M_impl._M_node_count;
2171 auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();
2172#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
2173 return { __node_ptr, _M_get_Node_allocator() };
2174#else
2175#pragma GCC diagnostic push
2176#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
2177 using __alloc_ptr = typename _Node_alloc_traits::pointer;
2178 if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
2179 return { __node_ptr, _M_get_Node_allocator() };
2180 else
2181 {
2182 auto __ap = pointer_traits<__alloc_ptr>::pointer_to(*__node_ptr);
2183 return { __ap, _M_get_Node_allocator() };
2184 }
2185#pragma GCC diagnostic pop
2186#endif
2187 }
2188
2189 /// Extract a node.
2190 node_type
2191 extract(const key_type& __k)
2192 {
2193 node_type __nh;
2194 auto __pos = find(__k);
2195 if (__pos != end())
2196 __nh = extract(const_iterator(__pos));
2197 return __nh;
2198 }
2199
2200 template<typename _Compare2>
2201 using _Compatible_tree
2202 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
2203
2204 template<typename, typename>
2205 friend struct _Rb_tree_merge_helper;
2206
2207 /// Merge from a compatible container into one with unique keys.
2208 template<typename _Compare2>
2209 void
2210 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
2211 {
2212 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
2213 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
2214 {
2215 auto __pos = __i++;
2216 auto __res = _M_get_insert_unique_pos(k: _KeyOfValue()(*__pos));
2217 if (__res.second)
2218 {
2219 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
2220 auto __ptr = _Node_traits::_S_rebalance_for_erase
2221 (__pos._M_node, __src_impl._M_header);
2222 --__src_impl._M_node_count;
2223 auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();
2224 _M_insert_node(x: __res.first, y: __res.second, z: __node_ptr);
2225 }
2226 }
2227 }
2228
2229 /// Merge from a compatible container into one with equivalent keys.
2230 template<typename _Compare2>
2231 void
2232 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
2233 {
2234 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
2235 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
2236 {
2237 auto __pos = __i++;
2238 auto __res = _M_get_insert_equal_pos(k: _KeyOfValue()(*__pos));
2239 if (__res.second)
2240 {
2241 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
2242 auto __ptr = _Node_traits::_S_rebalance_for_erase
2243 (__pos._M_node, __src_impl._M_header);
2244 --__src_impl._M_node_count;
2245 auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();
2246 _M_insert_node(x: __res.first, y: __res.second, z: __node_ptr);
2247 }
2248 }
2249 }
2250#endif // C++17 node_extract
2251
2252 friend bool
2253 operator==(const _Rb_tree& __x, const _Rb_tree& __y)
2254 {
2255 return __x.size() == __y.size()
2256 && std::equal(__x.begin(), __x.end(), __y.begin());
2257 }
2258
2259#if __cpp_lib_three_way_comparison
2260 friend auto
2261 operator<=>(const _Rb_tree& __x, const _Rb_tree& __y)
2262 {
2263 if constexpr (requires { typename __detail::__synth3way_t<_Val>; })
2264 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2265 __y.begin(), __y.end(),
2266 __detail::__synth3way);
2267 }
2268#else
2269 friend bool
2270 operator<(const _Rb_tree& __x, const _Rb_tree& __y)
2271 {
2272 return std::lexicographical_compare(__x.begin(), __x.end(),
2273 __y.begin(), __y.end());
2274 }
2275#endif
2276
2277 private:
2278#if __cplusplus >= 201103L
2279 // An RAII _Node handle
2280 struct _Auto_node
2281 {
2282 template<typename... _Args>
2283 _Auto_node(_Rb_tree& __t, _Args&&... __args)
2284 : _M_t(__t),
2285 _M_node(__t._M_create_node(std::forward<_Args>(__args)...))
2286 { }
2287
2288 ~_Auto_node()
2289 {
2290 if (_M_node)
2291 _M_t._M_drop_node(p: _M_node);
2292 }
2293
2294 _Auto_node(_Auto_node&& __n)
2295 : _M_t(__n._M_t), _M_node(__n._M_node)
2296 { __n._M_node = nullptr; }
2297
2298 const _Key&
2299 _M_key() const
2300 { return _S_key(_M_node); }
2301
2302 iterator
2303 _M_insert(pair<_Base_ptr, _Base_ptr> __p)
2304 {
2305 auto __it = _M_t._M_insert_node(x: __p.first, y: __p.second, z: _M_node);
2306 _M_node = nullptr;
2307 return __it;
2308 }
2309
2310 iterator
2311 _M_insert_equal_lower()
2312 {
2313 auto __it = _M_t._M_insert_equal_lower_node(z: _M_node);
2314 _M_node = nullptr;
2315 return __it;
2316 }
2317
2318 _Rb_tree& _M_t;
2319 _Node_ptr _M_node;
2320 };
2321#endif // C++11
2322 };
2323
2324 template<typename _Key, typename _Val, typename _KeyOfValue,
2325 typename _Compare, typename _Alloc>
2326 inline void
2327 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
2328 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
2329 { __x.swap(__y); }
2330
2331#if __cplusplus >= 201103L
2332 template<typename _Key, typename _Val, typename _KeyOfValue,
2333 typename _Compare, typename _Alloc>
2334 void
2335 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2336 _M_move_data(_Rb_tree& __x, false_type)
2337 {
2338 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
2339 _M_move_data(__x, true_type());
2340 else
2341 {
2342 constexpr bool __move = !__move_if_noexcept_cond<value_type>::value;
2343 _Alloc_node __an(*this);
2344 _M_root() = _M_copy<__move>(__x, __an);
2345 if _GLIBCXX17_CONSTEXPR (__move)
2346 __x.clear();
2347 }
2348 }
2349
2350 template<typename _Key, typename _Val, typename _KeyOfValue,
2351 typename _Compare, typename _Alloc>
2352 inline void
2353 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2354 _M_move_assign(_Rb_tree& __x, true_type)
2355 {
2356 clear();
2357 if (__x._M_root())
2358 _M_move_data(__x, true_type());
2359 std::__alloc_on_move(_M_get_Node_allocator(),
2360 __x._M_get_Node_allocator());
2361 }
2362
2363 template<typename _Key, typename _Val, typename _KeyOfValue,
2364 typename _Compare, typename _Alloc>
2365 void
2366 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2367 _M_move_assign(_Rb_tree& __x, false_type)
2368 {
2369 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
2370 return _M_move_assign(__x, true_type{});
2371
2372 // Try to move each node reusing existing nodes and copying __x nodes
2373 // structure.
2374 _Reuse_or_alloc_node __roan(*this);
2375 _M_impl._M_reset();
2376 if (__x._M_root())
2377 {
2378 _M_root() = _M_copy<__as_rvalue>(__x, __roan);
2379 __x.clear();
2380 }
2381 }
2382
2383 template<typename _Key, typename _Val, typename _KeyOfValue,
2384 typename _Compare, typename _Alloc>
2385 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
2386 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2387 operator=(_Rb_tree&& __x)
2388 noexcept(_Node_alloc_traits::_S_nothrow_move()
2389 && is_nothrow_move_assignable<_Compare>::value)
2390 {
2391 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
2392 _M_move_assign(__x,
2393 __bool_constant<_Node_alloc_traits::_S_nothrow_move()>());
2394 return *this;
2395 }
2396
2397 template<typename _Key, typename _Val, typename _KeyOfValue,
2398 typename _Compare, typename _Alloc>
2399 template<typename _Iterator>
2400 void
2401 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2402 _M_assign_unique(_Iterator __first, _Iterator __last)
2403 {
2404 _Reuse_or_alloc_node __roan(*this);
2405 _M_impl._M_reset();
2406 for (; __first != __last; ++__first)
2407 _M_insert_unique_(end(), *__first, __roan);
2408 }
2409
2410 template<typename _Key, typename _Val, typename _KeyOfValue,
2411 typename _Compare, typename _Alloc>
2412 template<typename _Iterator>
2413 void
2414 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2415 _M_assign_equal(_Iterator __first, _Iterator __last)
2416 {
2417 _Reuse_or_alloc_node __roan(*this);
2418 _M_impl._M_reset();
2419 for (; __first != __last; ++__first)
2420 _M_insert_equal_(end(), *__first, __roan);
2421 }
2422#endif
2423
2424 template<typename _Key, typename _Val, typename _KeyOfValue,
2425 typename _Compare, typename _Alloc>
2426 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
2427 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2428 operator=(const _Rb_tree& __x)
2429 {
2430 if (this != std::__addressof(__x))
2431 {
2432 // Note that _Key may be a constant type.
2433#if __cplusplus >= 201103L
2434 if (_Node_alloc_traits::_S_propagate_on_copy_assign())
2435 {
2436 auto& __this_alloc = this->_M_get_Node_allocator();
2437 auto& __that_alloc = __x._M_get_Node_allocator();
2438 if (!_Node_alloc_traits::_S_always_equal()
2439 && __this_alloc != __that_alloc)
2440 {
2441 // Replacement allocator cannot free existing storage, we need
2442 // to erase nodes first.
2443 clear();
2444 std::__alloc_on_copy(__this_alloc, __that_alloc);
2445 }
2446 }
2447#endif
2448
2449 _Reuse_or_alloc_node __roan(*this);
2450 _M_impl._M_reset();
2451 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
2452 if (__x._M_root())
2453 _M_root() = _M_copy<__as_lvalue>(__x, __roan);
2454 }
2455
2456 return *this;
2457 }
2458
2459 template<typename _Key, typename _Val, typename _KeyOfValue,
2460 typename _Compare, typename _Alloc>
2461#if __cplusplus >= 201103L
2462 template<typename _Arg, typename _NodeGen>
2463#else
2464 template<typename _NodeGen>
2465#endif
2466 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2468 _M_insert_(_Base_ptr __x, _Base_ptr __p,
2469#if __cplusplus >= 201103L
2470 _Arg&& __v,
2471#else
2472 const _Val& __v,
2473#endif
2474 _NodeGen& __node_gen)
2475 {
2476 bool __insert_left = (__x || __p == _M_end()
2477 || _M_impl._M_key_compare(_KeyOfValue()(__v),
2478 _S_key(__p)));
2479
2480 _Base_ptr __z =
2481 __node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
2482
2483 _Node_traits::_S_insert_and_rebalance
2484 (__insert_left, __z, __p, this->_M_impl._M_header);
2485 ++_M_impl._M_node_count;
2486 return iterator(__z);
2487 }
2488
2489 template<typename _Key, typename _Val, typename _KeyOfValue,
2490 typename _Compare, typename _Alloc>
2491#if __cplusplus >= 201103L
2492 template<typename _Arg>
2493#endif
2494 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2495 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2496#if __cplusplus >= 201103L
2497 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
2498#else
2499 _M_insert_lower(_Base_ptr __p, const _Val& __v)
2500#endif
2501 {
2502 bool __insert_left = (__p == _M_end()
2503 || !_M_impl._M_key_compare(_S_key(__p),
2504 _KeyOfValue()(__v)));
2505
2506 _Base_ptr __z =
2507 _M_create_node(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
2508 _Node_traits::_S_insert_and_rebalance
2509 (__insert_left, __z, __p, this->_M_impl._M_header);
2510 ++_M_impl._M_node_count;
2511 return iterator(__z);
2512 }
2513
2514 template<typename _Key, typename _Val, typename _KeyOfValue,
2515 typename _Compare, typename _Alloc>
2516#if __cplusplus >= 201103L
2517 template<typename _Arg>
2518#endif
2519 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2520 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2521#if __cplusplus >= 201103L
2522 _M_insert_equal_lower(_Arg&& __v)
2523#else
2524 _M_insert_equal_lower(const _Val& __v)
2525#endif
2526 {
2527 _Base_ptr __x = _M_begin();
2528 _Base_ptr __y = _M_end();
2529 while (__x)
2530 {
2531 __y = __x;
2532 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
2533 _S_left(__x) : _S_right(__x);
2534 }
2535 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
2536 }
2537
2538 template<typename _Key, typename _Val, typename _KoV,
2539 typename _Compare, typename _Alloc>
2540 template<bool _MoveValues, typename _NodeGen>
2541 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Base_ptr
2542 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
2543 _M_copy(_Node_ptr __x, _Base_ptr __p, _NodeGen& __node_gen)
2544 {
2545 // Structural copy. __x and __p must be non-null.
2546 _Node_ptr __top = _M_clone_node<_MoveValues>(__x, __node_gen);
2547 _Base_ptr __top_base = __top->_M_base_ptr();
2548 __top->_M_parent = __p;
2549
2550 __try
2551 {
2552 if (__x->_M_right)
2553 __top->_M_right =
2554 _M_copy<_MoveValues>(_S_right(__x), __top_base, __node_gen);
2555 __p = __top_base;
2556 __x = _S_left(__x);
2557
2558 while (__x)
2559 {
2560 _Base_ptr __y =
2561 _M_clone_node<_MoveValues>(__x, __node_gen)->_M_base_ptr();
2562 __p->_M_left = __y;
2563 __y->_M_parent = __p;
2564 if (__x->_M_right)
2565 __y->_M_right = _M_copy<_MoveValues>(_S_right(__x),
2566 __y, __node_gen);
2567 __p = __y;
2568 __x = _S_left(__x);
2569 }
2570 }
2571 __catch(...)
2572 {
2573 _M_erase(x: __top);
2574 __throw_exception_again;
2575 }
2576 return __top_base;
2577 }
2578
2579 template<typename _Key, typename _Val, typename _KeyOfValue,
2580 typename _Compare, typename _Alloc>
2581 void
2582 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2583 _M_erase(_Node_ptr __x)
2584 {
2585 // Erase without rebalancing.
2586 while (__x)
2587 {
2588 _M_erase(x: _S_right(__x));
2589 _Node_ptr __y = _S_left(__x);
2590 _M_drop_node(p: __x);
2591 __x = __y;
2592 }
2593 }
2594
2595 template<typename _Key, typename _Val, typename _KeyOfValue,
2596 typename _Compare, typename _Alloc>
2597 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2598 _Compare, _Alloc>::_Base_ptr
2599 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2600 _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
2601 const _Key& __k) const
2602 {
2603 while (__x)
2604 if (!_M_impl._M_key_compare(_S_key(__x), __k))
2605 __y = __x, __x = _S_left(__x);
2606 else
2607 __x = _S_right(__x);
2608 return __y;
2609 }
2610
2611 template<typename _Key, typename _Val, typename _KeyOfValue,
2612 typename _Compare, typename _Alloc>
2613 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2614 _Compare, _Alloc>::_Base_ptr
2615 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2616 _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
2617 const _Key& __k) const
2618 {
2619 while (__x)
2620 if (_M_impl._M_key_compare(__k, _S_key(__x)))
2621 __y = __x, __x = _S_left(__x);
2622 else
2623 __x = _S_right(__x);
2624 return __y;
2625 }
2626
2627 template<typename _Key, typename _Val, typename _KeyOfValue,
2628 typename _Compare, typename _Alloc>
2629 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2630 _Compare, _Alloc>::iterator,
2631 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2632 _Compare, _Alloc>::iterator>
2633 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2634 equal_range(const _Key& __k)
2635 {
2636 typedef pair<iterator, iterator> _Ret;
2637
2638 _Base_ptr __x = _M_begin();
2639 _Base_ptr __y = _M_end();
2640 while (__x)
2641 {
2642 if (_M_impl._M_key_compare(_S_key(__x), __k))
2643 __x = _S_right(__x);
2644 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2645 __y = __x, __x = _S_left(__x);
2646 else
2647 {
2648 _Base_ptr __xu(__x);
2649 _Base_ptr __yu(__y);
2650 __y = __x, __x = _S_left(__x);
2651 __xu = _S_right(__xu);
2652 return _Ret(iterator(_M_lower_bound(__x, __y, __k)),
2653 iterator(_M_upper_bound(x: __xu, y: __yu, __k)));
2654 }
2655 }
2656 return _Ret(iterator(__y), iterator(__y));
2657 }
2658
2659 template<typename _Key, typename _Val, typename _KeyOfValue,
2660 typename _Compare, typename _Alloc>
2661 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2662 _Compare, _Alloc>::const_iterator,
2663 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2664 _Compare, _Alloc>::const_iterator>
2665 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2666 equal_range(const _Key& __k) const
2667 {
2668 typedef pair<const_iterator, const_iterator> _Ret;
2669
2670 _Base_ptr __x = _M_begin();
2671 _Base_ptr __y = _M_end();
2672 while (__x)
2673 {
2674 if (_M_impl._M_key_compare(_S_key(__x), __k))
2675 __x = _S_right(__x);
2676 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2677 __y = __x, __x = _S_left(__x);
2678 else
2679 {
2680 _Base_ptr __xu(__x);
2681 _Base_ptr __yu(__y);
2682 __y = __x, __x = _S_left(__x);
2683 __xu = _S_right(__xu);
2684 return _Ret(const_iterator(_M_lower_bound(__x, __y, __k)),
2685 const_iterator(_M_upper_bound(x: __xu, y: __yu, __k)));
2686 }
2687 }
2688 return _Ret(const_iterator(__y), const_iterator(__y));
2689 }
2690
2691 template<typename _Key, typename _Val, typename _KeyOfValue,
2692 typename _Compare, typename _Alloc>
2693 void
2694 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2695 swap(_Rb_tree& __t)
2696 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2697 {
2698 if (!_M_root())
2699 {
2700 if (__t._M_root())
2701 _M_impl._M_move_data(__t._M_impl);
2702 }
2703 else if (!__t._M_root())
2704 __t._M_impl._M_move_data(_M_impl);
2705 else
2706 {
2707 std::swap(_M_root(),__t._M_root());
2708 std::swap(_M_leftmost(),__t._M_leftmost());
2709 std::swap(_M_rightmost(),__t._M_rightmost());
2710
2711 _M_root()->_M_parent = _M_end();
2712 __t._M_root()->_M_parent = __t._M_end();
2713 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2714 }
2715 // No need to swap header's color as it does not change.
2716
2717 using std::swap;
2718 swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2719
2720 _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2721 __t._M_get_Node_allocator());
2722 }
2723
2724 template<typename _Key, typename _Val, typename _KeyOfValue,
2725 typename _Compare, typename _Alloc>
2726 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2727 _Compare, _Alloc>::_Base_ptr,
2728 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2729 _Compare, _Alloc>::_Base_ptr>
2730 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2731 _M_get_insert_unique_pos(const key_type& __k)
2732 {
2733 typedef pair<_Base_ptr, _Base_ptr> _Res;
2734 _Base_ptr __x = _M_begin();
2735 _Base_ptr __y = _M_end();
2736 bool __comp = true;
2737 while (__x)
2738 {
2739 __y = __x;
2740 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2741 __x = __comp ? _S_left(__x) : _S_right(__x);
2742 }
2743 iterator __j = iterator(__y);
2744 if (__comp)
2745 {
2746 if (__j == begin())
2747 return _Res(__x, __y);
2748 else
2749 --__j;
2750 }
2751 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2752 return _Res(__x, __y);
2753 return _Res(__j._M_node, _Base_ptr());
2754 }
2755
2756 template<typename _Key, typename _Val, typename _KeyOfValue,
2757 typename _Compare, typename _Alloc>
2758 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2759 _Compare, _Alloc>::_Base_ptr,
2760 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2761 _Compare, _Alloc>::_Base_ptr>
2762 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2763 _M_get_insert_equal_pos(const key_type& __k)
2764 {
2765 typedef pair<_Base_ptr, _Base_ptr> _Res;
2766 _Base_ptr __x = _M_begin();
2767 _Base_ptr __y = _M_end();
2768 while (__x)
2769 {
2770 __y = __x;
2771 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2772 _S_left(__x) : _S_right(__x);
2773 }
2774 return _Res(__x, __y);
2775 }
2776
2777 template<typename _Key, typename _Val, typename _KeyOfValue,
2778 typename _Compare, typename _Alloc>
2779#if __cplusplus >= 201103L
2780 template<typename _Arg>
2781#endif
2782 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2783 _Compare, _Alloc>::iterator, bool>
2784 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2785#if __cplusplus >= 201103L
2786 _M_insert_unique(_Arg&& __v)
2787#else
2788 _M_insert_unique(const _Val& __v)
2789#endif
2790 {
2791 typedef pair<iterator, bool> _Res;
2792 pair<_Base_ptr, _Base_ptr> __res
2793 = _M_get_insert_unique_pos(k: _KeyOfValue()(__v));
2794
2795 if (__res.second)
2796 {
2797 _Alloc_node __an(*this);
2798 return _Res(_M_insert_(__res.first, __res.second,
2799 _GLIBCXX_FORWARD(_Arg, __v), __an),
2800 true);
2801 }
2802
2803 return _Res(iterator(__res.first), false);
2804 }
2805
2806 template<typename _Key, typename _Val, typename _KeyOfValue,
2807 typename _Compare, typename _Alloc>
2808#if __cplusplus >= 201103L
2809 template<typename _Arg>
2810#endif
2811 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2812 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2813#if __cplusplus >= 201103L
2814 _M_insert_equal(_Arg&& __v)
2815#else
2816 _M_insert_equal(const _Val& __v)
2817#endif
2818 {
2819 pair<_Base_ptr, _Base_ptr> __res
2820 = _M_get_insert_equal_pos(k: _KeyOfValue()(__v));
2821 _Alloc_node __an(*this);
2822 return _M_insert_(__res.first, __res.second,
2823 _GLIBCXX_FORWARD(_Arg, __v), __an);
2824 }
2825
2826 template<typename _Key, typename _Val, typename _KeyOfValue,
2827 typename _Compare, typename _Alloc>
2828 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2829 _Compare, _Alloc>::_Base_ptr,
2830 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2831 _Compare, _Alloc>::_Base_ptr>
2832 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2833 _M_get_insert_hint_unique_pos(const_iterator __position,
2834 const key_type& __k)
2835 {
2836 typedef pair<_Base_ptr, _Base_ptr> _Res;
2837
2838 // end()
2839 if (__position._M_node == _M_end())
2840 {
2841 if (size() > 0
2842 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2843 return _Res(_Base_ptr(), _M_rightmost());
2844 else
2845 return _M_get_insert_unique_pos(__k);
2846 }
2847 else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))
2848 {
2849 // First, try before...
2850 iterator __before(__position._M_node);
2851 if (__position._M_node == _M_leftmost()) // begin()
2852 return _Res(_M_leftmost(), _M_leftmost());
2853 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2854 {
2855 if (!_S_right(__before._M_node))
2856 return _Res(_Base_ptr(), __before._M_node);
2857 else
2858 return _Res(__position._M_node, __position._M_node);
2859 }
2860 else
2861 return _M_get_insert_unique_pos(__k);
2862 }
2863 else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))
2864 {
2865 // ... then try after.
2866 iterator __after(__position._M_node);
2867 if (__position._M_node == _M_rightmost())
2868 return _Res(_Base_ptr(), _M_rightmost());
2869 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2870 {
2871 if (!_S_right(__position._M_node))
2872 return _Res(_Base_ptr(), __position._M_node);
2873 else
2874 return _Res(__after._M_node, __after._M_node);
2875 }
2876 else
2877 return _M_get_insert_unique_pos(__k);
2878 }
2879 else
2880 // Equivalent keys.
2881 return _Res(__position._M_node, _Base_ptr());
2882 }
2883
2884 template<typename _Key, typename _Val, typename _KeyOfValue,
2885 typename _Compare, typename _Alloc>
2886#if __cplusplus >= 201103L
2887 template<typename _Arg, typename _NodeGen>
2888#else
2889 template<typename _NodeGen>
2890#endif
2891 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2892 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2893 _M_insert_unique_(const_iterator __position,
2894#if __cplusplus >= 201103L
2895 _Arg&& __v,
2896#else
2897 const _Val& __v,
2898#endif
2899 _NodeGen& __node_gen)
2900 {
2901 pair<_Base_ptr, _Base_ptr> __res
2902 = _M_get_insert_hint_unique_pos(__position, k: _KeyOfValue()(__v));
2903
2904 if (__res.second)
2905 return _M_insert_(__res.first, __res.second,
2906 _GLIBCXX_FORWARD(_Arg, __v),
2907 __node_gen);
2908 return iterator(__res.first);
2909 }
2910
2911 template<typename _Key, typename _Val, typename _KeyOfValue,
2912 typename _Compare, typename _Alloc>
2913 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2914 _Compare, _Alloc>::_Base_ptr,
2915 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2916 _Compare, _Alloc>::_Base_ptr>
2917 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2918 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2919 {
2920 typedef pair<_Base_ptr, _Base_ptr> _Res;
2921
2922 // end()
2923 if (__position._M_node == _M_end())
2924 {
2925 if (size() > 0
2926 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2927 return _Res(_Base_ptr(), _M_rightmost());
2928 else
2929 return _M_get_insert_equal_pos(__k);
2930 }
2931 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))
2932 {
2933 // First, try before...
2934 iterator __before(__position._M_node);
2935 if (__position._M_node == _M_leftmost()) // begin()
2936 return _Res(_M_leftmost(), _M_leftmost());
2937 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2938 {
2939 if (!_S_right(__before._M_node))
2940 return _Res(_Base_ptr(), __before._M_node);
2941 else
2942 return _Res(__position._M_node, __position._M_node);
2943 }
2944 else
2945 return _M_get_insert_equal_pos(__k);
2946 }
2947 else
2948 {
2949 // ... then try after.
2950 iterator __after(__position._M_node);
2951 if (__position._M_node == _M_rightmost())
2952 return _Res(_Base_ptr(), _M_rightmost());
2953 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2954 {
2955 if (!_S_right(__position._M_node))
2956 return _Res(_Base_ptr(), __position._M_node);
2957 else
2958 return _Res(__after._M_node, __after._M_node);
2959 }
2960 else
2961 return _Res(_Base_ptr(), _Base_ptr());
2962 }
2963 }
2964
2965 template<typename _Key, typename _Val, typename _KeyOfValue,
2966 typename _Compare, typename _Alloc>
2967#if __cplusplus >= 201103L
2968 template<typename _Arg, typename _NodeGen>
2969#else
2970 template<typename _NodeGen>
2971#endif
2972 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2973 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2974 _M_insert_equal_(const_iterator __position,
2975#if __cplusplus >= 201103L
2976 _Arg&& __v,
2977#else
2978 const _Val& __v,
2979#endif
2980 _NodeGen& __node_gen)
2981 {
2982 pair<_Base_ptr, _Base_ptr> __res
2983 = _M_get_insert_hint_equal_pos(__position, k: _KeyOfValue()(__v));
2984
2985 if (__res.second)
2986 return _M_insert_(__res.first, __res.second,
2987 _GLIBCXX_FORWARD(_Arg, __v),
2988 __node_gen);
2989
2990 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2991 }
2992
2993#if __cplusplus >= 201103L
2994 template<typename _Key, typename _Val, typename _KeyOfValue,
2995 typename _Compare, typename _Alloc>
2996 auto
2997 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2998 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Node_ptr __z)
2999 -> iterator
3000 {
3001 bool __insert_left = (__x || __p == _M_end()
3002 || _M_impl._M_key_compare(_S_key(__z),
3003 _S_key(__p)));
3004
3005 _Base_ptr __base_z = __z->_M_base_ptr();
3006 _Node_traits::_S_insert_and_rebalance
3007 (__insert_left, __base_z, __p, this->_M_impl._M_header);
3008 ++_M_impl._M_node_count;
3009 return iterator(__base_z);
3010 }
3011
3012 template<typename _Key, typename _Val, typename _KeyOfValue,
3013 typename _Compare, typename _Alloc>
3014 auto
3015 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3016 _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z)
3017 -> iterator
3018 {
3019 bool __insert_left = (__p == _M_end()
3020 || !_M_impl._M_key_compare(_S_key(__p),
3021 _S_key(__z)));
3022
3023 _Base_ptr __base_z = __z->_M_base_ptr();
3024 _Node_traits::_S_insert_and_rebalance
3025 (__insert_left, __base_z, __p, this->_M_impl._M_header);
3026 ++_M_impl._M_node_count;
3027 return iterator(__base_z);
3028 }
3029
3030 template<typename _Key, typename _Val, typename _KeyOfValue,
3031 typename _Compare, typename _Alloc>
3032 auto
3033 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3034 _M_insert_equal_lower_node(_Node_ptr __z)
3035 -> iterator
3036 {
3037 _Base_ptr __x = _M_begin();
3038 _Base_ptr __y = _M_end();
3039 while (__x)
3040 {
3041 __y = __x;
3042 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
3043 _S_left(__x) : _S_right(__x);
3044 }
3045 return _M_insert_lower_node(p: __y, __z);
3046 }
3047
3048 template<typename _Key, typename _Val, typename _KeyOfValue,
3049 typename _Compare, typename _Alloc>
3050 template<typename... _Args>
3051 auto
3052 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3053 _M_emplace_unique(_Args&&... __args)
3054 -> pair<iterator, bool>
3055 {
3056 _Auto_node __z(*this, std::forward<_Args>(__args)...);
3057 auto __res = _M_get_insert_unique_pos(k: __z._M_key());
3058 if (__res.second)
3059 return {__z._M_insert(__res), true};
3060 return {iterator(__res.first), false};
3061 }
3062
3063 template<typename _Key, typename _Val, typename _KeyOfValue,
3064 typename _Compare, typename _Alloc>
3065 template<typename... _Args>
3066 auto
3067 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3068 _M_emplace_equal(_Args&&... __args)
3069 -> iterator
3070 {
3071 _Auto_node __z(*this, std::forward<_Args>(__args)...);
3072 auto __res = _M_get_insert_equal_pos(k: __z._M_key());
3073 return __z._M_insert(__res);
3074 }
3075
3076 template<typename _Key, typename _Val, typename _KeyOfValue,
3077 typename _Compare, typename _Alloc>
3078 template<typename... _Args>
3079 auto
3080 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3081 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
3082 -> iterator
3083 {
3084 _Auto_node __z(*this, std::forward<_Args>(__args)...);
3085 auto __res = _M_get_insert_hint_unique_pos(position: __pos, k: __z._M_key());
3086 if (__res.second)
3087 return __z._M_insert(__res);
3088 return iterator(__res.first);
3089 }
3090
3091 template<typename _Key, typename _Val, typename _KeyOfValue,
3092 typename _Compare, typename _Alloc>
3093 template<typename... _Args>
3094 auto
3095 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3096 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
3097 -> iterator
3098 {
3099 _Auto_node __z(*this, std::forward<_Args>(__args)...);
3100 auto __res = _M_get_insert_hint_equal_pos(position: __pos, k: __z._M_key());
3101 if (__res.second)
3102 return __z._M_insert(__res);
3103 return __z._M_insert_equal_lower();
3104 }
3105#endif
3106
3107
3108 template<typename _Key, typename _Val, typename _KeyOfValue,
3109 typename _Compare, typename _Alloc>
3110 void
3111 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3112 _M_erase_aux(const_iterator __position)
3113 {
3114 _Base_ptr __y = _Node_traits::_S_rebalance_for_erase
3115 (__position._M_node, this->_M_impl._M_header);
3116 _M_drop_node(p: static_cast<_Node&>(*__y)._M_node_ptr());
3117 --_M_impl._M_node_count;
3118 }
3119
3120 template<typename _Key, typename _Val, typename _KeyOfValue,
3121 typename _Compare, typename _Alloc>
3122 void
3123 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3124 _M_erase_aux(const_iterator __first, const_iterator __last)
3125 {
3126 if (__first == begin() && __last == end())
3127 clear();
3128 else
3129 while (__first != __last)
3130 _M_erase_aux(__first++);
3131 }
3132
3133 template<typename _Key, typename _Val, typename _KeyOfValue,
3134 typename _Compare, typename _Alloc>
3135 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
3136 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3137 erase(const _Key& __x)
3138 {
3139 pair<iterator, iterator> __p = equal_range(__x);
3140 const size_type __old_size = size();
3141 _M_erase_aux(__p.first, __p.second);
3142 return __old_size - size();
3143 }
3144
3145 template<typename _Key, typename _Val, typename _KeyOfValue,
3146 typename _Compare, typename _Alloc>
3147 typename _Rb_tree<_Key, _Val, _KeyOfValue,
3148 _Compare, _Alloc>::iterator
3149 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3150 find(const _Key& __k)
3151 {
3152 iterator __j(_M_lower_bound(x: _M_begin(), y: _M_end(), __k));
3153 return (__j == end()
3154 || _M_impl._M_key_compare(__k,
3155 _S_key(__j._M_node))) ? end() : __j;
3156 }
3157
3158 template<typename _Key, typename _Val, typename _KeyOfValue,
3159 typename _Compare, typename _Alloc>
3160 typename _Rb_tree<_Key, _Val, _KeyOfValue,
3161 _Compare, _Alloc>::const_iterator
3162 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3163 find(const _Key& __k) const
3164 {
3165 const_iterator __j(_M_lower_bound(x: _M_begin(), y: _M_end(), __k));
3166 return (__j == end()
3167 || _M_impl._M_key_compare(__k,
3168 _S_key(__j._M_node))) ? end() : __j;
3169 }
3170
3171 template<typename _Key, typename _Val, typename _KeyOfValue,
3172 typename _Compare, typename _Alloc>
3173 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
3174 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3175 count(const _Key& __k) const
3176 {
3177 pair<const_iterator, const_iterator> __p = equal_range(__k);
3178 const size_type __n = std::distance(__p.first, __p.second);
3179 return __n;
3180 }
3181
3182 _GLIBCXX_PURE unsigned int
3183 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
3184 const _Rb_tree_node_base* __root) throw ();
3185
3186 template<typename _Key, typename _Val, typename _KeyOfValue,
3187 typename _Compare, typename _Alloc>
3188 bool
3189 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
3190 {
3191 if (_M_impl._M_node_count == 0 || begin() == end())
3192 return _M_impl._M_node_count == 0 && begin() == end()
3193 && this->_M_impl._M_header._M_left == _M_end()
3194 && this->_M_impl._M_header._M_right == _M_end();
3195
3196 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
3197 for (const_iterator __it = begin(); __it != end(); ++__it)
3198 {
3199 _Base_ptr __x = __it._M_node;
3200 _Base_ptr __L = _S_left(__x);
3201 _Base_ptr __R = _S_right(__x);
3202
3203 if (__x->_M_color == _S_red)
3204 if ((__L && __L->_M_color == _S_red)
3205 || (__R && __R->_M_color == _S_red))
3206 return false;
3207
3208 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
3209 return false;
3210 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
3211 return false;
3212
3213 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
3214 return false;
3215 }
3216
3217 if (_M_leftmost() != _Node_base::_S_minimum(_M_root()))
3218 return false;
3219 if (_M_rightmost() != _Node_base::_S_maximum(_M_root()))
3220 return false;
3221 return true;
3222 }
3223
3224#ifdef __glibcxx_node_extract // >= C++17
3225 // Allow access to internals of compatible _Rb_tree specializations.
3226 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
3227 typename _Alloc, typename _Cmp2>
3228 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
3229 _Cmp2>
3230 {
3231 private:
3232 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
3233
3234 static auto&
3235 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
3236 { return __tree._M_impl; }
3237 };
3238#endif // C++17
3239
3240_GLIBCXX_END_NAMESPACE_VERSION
3241} // namespace
3242
3243#endif
3244