62#pragma GCC system_header
71#if __cplusplus >= 201103L
74#if __cplusplus > 201402L
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
85namespace std _GLIBCXX_VISIBILITY(default)
87_GLIBCXX_BEGIN_NAMESPACE_VERSION
105 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
107 struct _Rb_tree_node_base
109 typedef _Rb_tree_node_base* _Base_ptr;
111 _Rb_tree_color _M_color;
117 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
119 while (__x->_M_left != 0) __x = __x->_M_left;
124 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
126 while (__x->_M_right != 0) __x = __x->_M_right;
134 _M_base_ptr() const _GLIBCXX_NOEXCEPT
135 {
return const_cast<_Rb_tree_node_base*
>(
this); }
139 template<
typename _Key_compare>
140 struct _Rb_tree_key_compare
142 _Key_compare _M_key_compare;
144 _Rb_tree_key_compare()
145 _GLIBCXX_NOEXCEPT_IF(
146 is_nothrow_default_constructible<_Key_compare>::value)
150 _Rb_tree_key_compare(
const _Key_compare& __comp)
151 : _M_key_compare(__comp)
154#if __cplusplus >= 201103L
156 _Rb_tree_key_compare(
const _Rb_tree_key_compare&) =
default;
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)
166 struct _Rb_tree_header
168 _Rb_tree_node_base _M_header;
169 size_t _M_node_count;
171 _Rb_tree_header() _GLIBCXX_NOEXCEPT
173 _M_header._M_color = _S_red;
177#if __cplusplus >= 201103L
178 _Rb_tree_header(_Rb_tree_header&& __x)
noexcept
180 if (__x._M_header._M_parent !=
nullptr)
184 _M_header._M_color = _S_red;
191 _M_move_data(_Rb_tree_header& __from)
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;
206 _M_header._M_parent = 0;
207 _M_header._M_left = &_M_header;
208 _M_header._M_right = &_M_header;
213 template<
typename _Val>
214 struct _Rb_tree_node :
public _Rb_tree_node_base
216#if __cplusplus < 201103L
227 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
231 {
return _M_storage._M_ptr(); }
235 {
return _M_storage._M_ptr(); }
239 _M_node_ptr() _GLIBCXX_NOEXCEPT
243#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
246 template<
typename _Vo
idPtr>
249 using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
251 _Rb_tree_color _M_color;
257 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
259 while (__x->_M_left) __x = __x->_M_left;
264 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
266 while (__x->_M_right) __x = __x->_M_right;
274 _M_base_ptr() const noexcept
276 return pointer_traits<_Base_ptr>::pointer_to
277 (*
const_cast<_Node_base*
>(
this));
282 template<
typename _NodeBase>
286 using _Base_ptr =
typename _NodeBase::_Base_ptr;
290 size_t _M_node_count;
294 _M_header._M_color = _S_red;
298 _Header(_Header&& __x)
noexcept
300 if (__x._M_header._M_parent)
304 _M_header._M_color = _S_red;
310 _M_move_data(_Header& __from)
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;
325 _M_header._M_parent =
nullptr;
326 _M_header._M_left = _M_header._M_right = _M_header._M_base_ptr();
331 template<
typename _ValPtr>
332 struct _Node :
public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>
334 using value_type =
typename pointer_traits<_ValPtr>::element_type;
335 using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
339 _Node(_Node&&) =
delete;
341 union _Uninit_storage
343 _Uninit_storage() noexcept { }
344 ~_Uninit_storage() { }
348 _Uninit_storage _M_u;
359 _M_node_ptr() noexcept
360 {
return pointer_traits<_Node_ptr>::pointer_to(*
this); }
365 _GLIBCXX_PURE _Rb_tree_node_base*
366 _Rb_tree_increment(_Rb_tree_node_base* __x)
throw ();
368 _GLIBCXX_PURE _Rb_tree_node_base*
369 _Rb_tree_decrement(_Rb_tree_node_base* __x)
throw ();
371 template<
typename _Tp>
372 struct _Rb_tree_iterator
374 typedef _Tp value_type;
375 typedef _Tp& reference;
376 typedef _Tp* pointer;
378 typedef bidirectional_iterator_tag iterator_category;
379 typedef ptrdiff_t difference_type;
381 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
382 typedef _Rb_tree_node<_Tp>* _Node_ptr;
384 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
388 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
393 {
return *
static_cast<_Node_ptr
>(_M_node)->_M_valptr(); }
396 operator->() const _GLIBCXX_NOEXCEPT
397 {
return static_cast<_Node_ptr
>(_M_node)->_M_valptr(); }
400 operator++() _GLIBCXX_NOEXCEPT
402 _M_node = _Rb_tree_increment(_M_node);
407 operator++(
int) _GLIBCXX_NOEXCEPT
409 _Rb_tree_iterator __tmp = *
this;
410 _M_node = _Rb_tree_increment(_M_node);
415 operator--() _GLIBCXX_NOEXCEPT
417 _M_node = _Rb_tree_decrement(_M_node);
422 operator--(
int) _GLIBCXX_NOEXCEPT
424 _Rb_tree_iterator __tmp = *
this;
425 _M_node = _Rb_tree_decrement(_M_node);
430 operator==(
const _Rb_tree_iterator& __x,
431 const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
432 {
return __x._M_node == __y._M_node; }
434#if ! __cpp_lib_three_way_comparison
436 operator!=(
const _Rb_tree_iterator& __x,
437 const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
438 {
return __x._M_node != __y._M_node; }
444 template<
typename _Tp>
445 struct _Rb_tree_const_iterator
447 typedef _Tp value_type;
448 typedef const _Tp& reference;
449 typedef const _Tp* pointer;
451 typedef _Rb_tree_iterator<_Tp> iterator;
453 typedef bidirectional_iterator_tag iterator_category;
454 typedef ptrdiff_t difference_type;
456 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
457 typedef const _Rb_tree_node<_Tp>* _Node_ptr;
459 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
463 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
466 _Rb_tree_const_iterator(
const iterator& __it) _GLIBCXX_NOEXCEPT
467 : _M_node(__it._M_node) { }
471 {
return *
static_cast<_Node_ptr
>(_M_node)->_M_valptr(); }
474 operator->() const _GLIBCXX_NOEXCEPT
475 {
return static_cast<_Node_ptr
>(_M_node)->_M_valptr(); }
477 _Rb_tree_const_iterator&
478 operator++() _GLIBCXX_NOEXCEPT
480 _M_node = _Rb_tree_increment(_M_node);
484 _Rb_tree_const_iterator
485 operator++(
int) _GLIBCXX_NOEXCEPT
487 _Rb_tree_const_iterator __tmp = *
this;
488 _M_node = _Rb_tree_increment(_M_node);
492 _Rb_tree_const_iterator&
493 operator--() _GLIBCXX_NOEXCEPT
495 _M_node = _Rb_tree_decrement(_M_node);
499 _Rb_tree_const_iterator
500 operator--(
int) _GLIBCXX_NOEXCEPT
502 _Rb_tree_const_iterator __tmp = *
this;
503 _M_node = _Rb_tree_decrement(_M_node);
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; }
512#if ! __cpp_lib_three_way_comparison
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; }
522 __attribute__((__nonnull__))
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 ();
529 __attribute__((__nonnull__,__returns_nonnull__))
531 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
532 _Rb_tree_node_base& __header)
throw ();
536#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
537 template<
bool _Const,
typename _ValPtr>
540 template<
typename _Tp>
541 using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
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>*;
548 using iterator_category = bidirectional_iterator_tag;
549 using difference_type = ptrdiff_t;
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;
559 _Iterator(_Base_ptr __x) noexcept
562 _Iterator(
const _Iterator&) =
default;
563 _Iterator& operator=(
const _Iterator&) =
default;
565#ifdef __glibcxx_concepts
567 _Iterator(
const _Iterator<false, _ValPtr>& __it)
requires _Const
569 template<
bool _OtherConst,
570 typename = __enable_if_t<_Const && !_OtherConst>>
572 _Iterator(
const _Iterator<_OtherConst, _ValPtr>& __it)
574 : _M_node(__it._M_node) { }
579 {
return *
static_cast<_Node&
>(*_M_node)._M_valptr(); }
583 operator->() const noexcept
584 {
return static_cast<_Node&
>(*_M_node)._M_valptr(); }
586 _GLIBCXX14_CONSTEXPR _Iterator&
587 operator++() noexcept
589 if (_M_node->_M_right)
591 _M_node = _M_node->_M_right;
592 while (_M_node->_M_left)
593 _M_node = _M_node->_M_left;
597 _Base_ptr __y = _M_node->_M_parent;
598 while (_M_node == __y->_M_right)
601 __y = __y->_M_parent;
603 if (_M_node->_M_right != __y)
610 _GLIBCXX14_CONSTEXPR _Iterator
611 operator++(
int)
noexcept
613 _Iterator __tmp(this->_M_node);
618 _GLIBCXX14_CONSTEXPR _Iterator&
619 operator--() noexcept
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)
626 _Base_ptr __y = _M_node->_M_left;
627 while (__y->_M_right)
633 _Base_ptr __y = _M_node->_M_parent;
634 while (_M_node == __y->_M_left)
637 __y = __y->_M_parent;
644 _GLIBCXX14_CONSTEXPR _Iterator
645 operator--(
int)
noexcept
647 _Iterator __tmp(this->_M_node);
654 operator==(
const _Iterator& __x,
const _Iterator& __y) _GLIBCXX_NOEXCEPT
655 {
return __x._M_node == __y._M_node; }
657#if ! __cpp_lib_three_way_comparison
660 operator!=(
const _Iterator& __x,
const _Iterator& __y) _GLIBCXX_NOEXCEPT
661 {
return __x._M_node != __y._M_node; }
669 template<
typename _Val,
typename _Ptr>
672#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000
676 template<
typename _Val>
677 struct _Node_traits<_Val, _Val*>
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;
687 __attribute__((__nonnull__))
689 _S_insert_and_rebalance(
const bool __insert_left,
690 _Node_base* __x, _Node_base* __p,
691 _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
693 return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header);
696 __attribute__((__nonnull__,__returns_nonnull__))
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); }
704#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
706 template<
typename _Val,
typename _Ptr>
708 : _Node_traits<_Val, _Val*>
712 template<
typename _Val,
typename _ValPtr>
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>;
724 _Rotate_left(_Base_ptr __x, _Base_ptr& __root)
726 const _Base_ptr __y = __x->_M_right;
728 __x->_M_right = __y->_M_left;
730 __y->_M_left->_M_parent = __x;
731 __y->_M_parent = __x->_M_parent;
735 else if (__x == __x->_M_parent->_M_left)
736 __x->_M_parent->_M_left = __y;
738 __x->_M_parent->_M_right = __y;
740 __x->_M_parent = __y;
744 _Rotate_right(_Base_ptr __x, _Base_ptr& __root)
746 const _Base_ptr __y = __x->_M_left;
748 __x->_M_left = __y->_M_right;
750 __y->_M_right->_M_parent = __x;
751 __y->_M_parent = __x->_M_parent;
755 else if (__x == __x->_M_parent->_M_right)
756 __x->_M_parent->_M_right = __y;
758 __x->_M_parent->_M_left = __y;
760 __x->_M_parent = __y;
764 _S_insert_and_rebalance(
const bool __insert_left,
765 _Base_ptr __x, _Base_ptr __p,
766 _Node_base& __header)
768 _Base_ptr& __root = __header._M_parent;
771 __x->_M_parent = __p;
772 __x->_M_left = __x->_M_right =
nullptr;
773 __x->_M_color = _S_red;
785 __header._M_parent = __x;
786 __header._M_right = __x;
788 else if (__p == __header._M_left)
789 __header._M_left = __x;
795 if (__p == __header._M_right)
796 __header._M_right = __x;
800 && __x->_M_parent->_M_color == _S_red)
802 const _Base_ptr __xpp = __x->_M_parent->_M_parent;
804 if (__x->_M_parent == __xpp->_M_left)
806 const _Base_ptr __y = __xpp->_M_right;
807 if (__y && __y->_M_color == _S_red)
809 __x->_M_parent->_M_color = _S_black;
810 __y->_M_color = _S_black;
811 __xpp->_M_color = _S_red;
816 if (__x == __x->_M_parent->_M_right)
818 __x = __x->_M_parent;
819 _Rotate_left(__x, __root);
821 __x->_M_parent->_M_color = _S_black;
822 __xpp->_M_color = _S_red;
823 _Rotate_right(__xpp, __root);
828 const _Base_ptr __y = __xpp->_M_left;
829 if (__y && __y->_M_color == _S_red)
831 __x->_M_parent->_M_color = _S_black;
832 __y->_M_color = _S_black;
833 __xpp->_M_color = _S_red;
838 if (__x == __x->_M_parent->_M_left)
840 __x = __x->_M_parent;
841 _Rotate_right(__x, __root);
843 __x->_M_parent->_M_color = _S_black;
844 __xpp->_M_color = _S_red;
845 _Rotate_left(__xpp, __root);
849 __root->_M_color = _S_black;
853 _S_rebalance_for_erase(_Base_ptr __z, _Node_base& __header)
855 _Base_ptr& __root = __header._M_parent;
856 _Base_ptr& __leftmost = __header._M_left;
857 _Base_ptr& __rightmost = __header._M_right;
860 _Base_ptr __x_parent{};
878 __z->_M_left->_M_parent = __y;
879 __y->_M_left = __z->_M_left;
880 if (__y != __z->_M_right)
882 __x_parent = __y->_M_parent;
884 __x->_M_parent = __y->_M_parent;
885 __y->_M_parent->_M_left = __x;
886 __y->_M_right = __z->_M_right;
887 __z->_M_right->_M_parent = __y;
893 else if (__z->_M_parent->_M_left == __z)
894 __z->_M_parent->_M_left = __y;
896 __z->_M_parent->_M_right = __y;
897 __y->_M_parent = __z->_M_parent;
898 std::swap(__y->_M_color, __z->_M_color);
904 __x_parent = __y->_M_parent;
906 __x->_M_parent = __y->_M_parent;
910 if (__z->_M_parent->_M_left == __z)
911 __z->_M_parent->_M_left = __x;
913 __z->_M_parent->_M_right = __x;
914 if (__leftmost == __z)
917 __leftmost = __z->_M_parent;
920 __leftmost = _Node_base::_S_minimum(__x);
922 if (__rightmost == __z)
924 if (__z->_M_left == 0)
925 __rightmost = __z->_M_parent;
928 __rightmost = _Node_base::_S_maximum(__x);
931 if (__y->_M_color != _S_red)
933 while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
934 if (__x == __x_parent->_M_left)
936 _Base_ptr __w = __x_parent->_M_right;
937 if (__w->_M_color == _S_red)
939 __w->_M_color = _S_black;
940 __x_parent->_M_color = _S_red;
941 _Rotate_left(__x_parent, __root);
942 __w = __x_parent->_M_right;
944 if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) &&
945 (!__w->_M_right || __w->_M_right->_M_color == _S_black))
947 __w->_M_color = _S_red;
949 __x_parent = __x_parent->_M_parent;
953 if (!__w->_M_right || __w->_M_right->_M_color == _S_black)
955 __w->_M_left->_M_color = _S_black;
956 __w->_M_color = _S_red;
957 _Rotate_right(__w, __root);
958 __w = __x_parent->_M_right;
960 __w->_M_color = __x_parent->_M_color;
961 __x_parent->_M_color = _S_black;
963 __w->_M_right->_M_color = _S_black;
964 _Rotate_left(__x_parent, __root);
971 _Base_ptr __w = __x_parent->_M_left;
972 if (__w->_M_color == _S_red)
974 __w->_M_color = _S_black;
975 __x_parent->_M_color = _S_red;
976 _Rotate_right(__x_parent, __root);
977 __w = __x_parent->_M_left;
979 if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) &&
980 (!__w->_M_left || __w->_M_left->_M_color == _S_black))
982 __w->_M_color = _S_red;
984 __x_parent = __x_parent->_M_parent;
988 if (!__w->_M_left || __w->_M_left->_M_color == _S_black)
990 __w->_M_right->_M_color = _S_black;
991 __w->_M_color = _S_red;
992 _Rotate_left(__w, __root);
993 __w = __x_parent->_M_left;
995 __w->_M_color = __x_parent->_M_color;
996 __x_parent->_M_color = _S_black;
998 __w->_M_left->_M_color = _S_black;
999 _Rotate_right(__x_parent, __root);
1004 __x->_M_color = _S_black;
1013#if __cplusplus > 201402L
1014 template<
typename _Tree1,
typename _Cmp2>
1015 struct _Rb_tree_merge_helper { };
1018 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1019 typename _Compare,
typename _Alloc = allocator<_Val> >
1023 rebind<_Val>::other _Val_alloc_type;
1026 typedef typename _Val_alloc_traits::pointer _ValPtr;
1027 typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits;
1029 typedef typename _Node_traits::_Node_base _Node_base;
1030 typedef typename _Node_traits::_Node _Node;
1033 rebind<_Node>::other _Node_allocator;
1038 typedef typename _Node_traits::_Base_ptr _Base_ptr;
1039 typedef typename _Node_traits::_Node_ptr _Node_ptr;
1044 struct _Reuse_or_alloc_node
1046 _Reuse_or_alloc_node(_Rb_tree& __t)
1047 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
1051 _M_root->_M_parent = _Base_ptr();
1053 if (_M_nodes->_M_left)
1054 _M_nodes = _M_nodes->_M_left;
1057 _M_nodes = _Base_ptr();
1060#if __cplusplus >= 201103L
1061 _Reuse_or_alloc_node(
const _Reuse_or_alloc_node&) =
delete;
1064 ~_Reuse_or_alloc_node()
1067 _M_t._M_erase(
static_cast<_Node&
>(*_M_root)._M_node_ptr());
1070 template<
typename _Arg>
1072 operator()(_GLIBCXX_FWDREF(_Arg) __arg)
1074 _Base_ptr
__base = _M_extract();
1077 _Node_ptr __node =
static_cast<_Node&
>(*__base)._M_node_ptr();
1078 _M_t._M_destroy_node(__node);
1079 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
1083 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
1093 _Base_ptr __node = _M_nodes;
1094 _M_nodes = _M_nodes->_M_parent;
1097 if (_M_nodes->_M_right == __node)
1099 _M_nodes->_M_right = _Base_ptr();
1101 if (_M_nodes->_M_left)
1103 _M_nodes = _M_nodes->_M_left;
1105 while (_M_nodes->_M_right)
1106 _M_nodes = _M_nodes->_M_right;
1108 if (_M_nodes->_M_left)
1109 _M_nodes = _M_nodes->_M_left;
1113 _M_nodes->_M_left = _Base_ptr();
1116 _M_root = _Base_ptr();
1130 _Alloc_node(_Rb_tree& __t)
1133 template<
typename _Arg>
1135 operator()(_GLIBCXX_FWDREF(_Arg) __arg)
const
1136 {
return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
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;
1154 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
1155 {
return this->_M_impl; }
1157 const _Node_allocator&
1158 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
1159 {
return this->_M_impl; }
1162 get_allocator() const _GLIBCXX_NOEXCEPT
1163 {
return allocator_type(_M_get_Node_allocator()); }
1169#if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
1172#pragma GCC diagnostic push
1173#pragma GCC diagnostic ignored "-Wc++17-extensions"
1174 using __alloc_pointer =
typename _Node_alloc_traits::pointer;
1175 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
1181 return std::__to_address(__ptr);
1183#pragma GCC diagnostic pop
1188 _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1190#if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
1193#pragma GCC diagnostic push
1194#pragma GCC diagnostic ignored "-Wc++17-extensions"
1195 using __alloc_pointer =
typename _Node_alloc_traits::pointer;
1196 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
1202 auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);
1205#pragma GCC diagnostic pop
1209#if __cplusplus < 201103L
1211 _M_construct_node(_Node_ptr __node,
const value_type& __x)
1214 { get_allocator().construct(__node->_M_valptr(), __x); }
1217 _M_put_node(__node);
1218 __throw_exception_again;
1223 _M_create_node(
const value_type& __x)
1225 _Node_ptr __tmp = _M_get_node();
1226 _M_construct_node(__tmp, __x);
1230 template<
typename... _Args>
1232 _M_construct_node(_Node_ptr __node, _Args&&... __args)
1237 _Node_alloc_traits::construct(_M_get_Node_allocator(),
1238 __node->_M_valptr(),
1239 std::forward<_Args>(__args)...);
1244 _M_put_node(__node);
1245 __throw_exception_again;
1249 template<
typename... _Args>
1251 _M_create_node(_Args&&... __args)
1253 _Node_ptr __tmp = _M_get_node();
1254 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
1260 _M_destroy_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1262#if __cplusplus < 201103L
1263 get_allocator().destroy(__p->_M_valptr());
1265 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
1271 _M_drop_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1273 _M_destroy_node(__p);
1277 template<
bool _MoveValue,
typename _NodeGen>
1279 _M_clone_node(_Node_ptr __x, _NodeGen& __node_gen)
1281#if __cplusplus >= 201103L
1282 using _Vp = __conditional_t<_MoveValue,
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();
1294 typedef typename _Node_traits::_Header_t _Header_t;
1296#if _GLIBCXX_INLINE_VERSION
1297 template<
typename _Key_compare>
1300 template<
typename _Key_compare,
1301 bool = __is_pod(_Key_compare)>
1303 struct _Rb_tree_impl
1304 :
public _Node_allocator
1305 ,
public _Rb_tree_key_compare<_Key_compare>
1308 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
1311 _GLIBCXX_NOEXCEPT_IF(
1312 is_nothrow_default_constructible<_Node_allocator>::value
1313 && is_nothrow_default_constructible<_Base_key_compare>::value )
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)
1323#if __cplusplus < 201103L
1324 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
1325 : _Node_allocator(__a), _Base_key_compare(__comp)
1328 _Rb_tree_impl(_Rb_tree_impl&&)
1329 noexcept( is_nothrow_move_constructible<_Base_key_compare>::value )
1333 _Rb_tree_impl(_Node_allocator&& __a)
1334 : _Node_allocator(
std::
move(__a))
1337 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
1338 : _Node_allocator(
std::
move(__a)),
1339 _Base_key_compare(
std::
move(__x)),
1343 _Rb_tree_impl(
const _Key_compare& __comp, _Node_allocator&& __a)
1344 : _Node_allocator(
std::
move(__a)), _Base_key_compare(__comp)
1349 _Rb_tree_impl<_Compare> _M_impl;
1353 _M_root() _GLIBCXX_NOEXCEPT
1354 {
return this->_M_impl._M_header._M_parent; }
1357 _M_root() const _GLIBCXX_NOEXCEPT
1358 {
return this->_M_impl._M_header._M_parent; }
1361 _M_leftmost() _GLIBCXX_NOEXCEPT
1362 {
return this->_M_impl._M_header._M_left; }
1365 _M_leftmost() const _GLIBCXX_NOEXCEPT
1366 {
return this->_M_impl._M_header._M_left; }
1369 _M_rightmost() _GLIBCXX_NOEXCEPT
1370 {
return this->_M_impl._M_header._M_right; }
1373 _M_rightmost() const _GLIBCXX_NOEXCEPT
1374 {
return this->_M_impl._M_header._M_right; }
1377 _M_begin() const _GLIBCXX_NOEXCEPT
1378 {
return this->_M_impl._M_header._M_parent; }
1381 _M_begin_node() const _GLIBCXX_NOEXCEPT
1383 _Base_ptr __begin = this->_M_impl._M_header._M_parent;
1385 ?
static_cast<_Node&
>(*__begin)._M_node_ptr()
1390 _M_end() const _GLIBCXX_NOEXCEPT
1391 {
return this->_M_impl._M_header._M_base_ptr(); }
1394 _S_key(
const _Node& __node)
1396#if __cplusplus >= 201103L
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
1405 if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
1407 is_invocable_v<const _Compare&, const _Key&, const _Key&>,
1408 "comparison object must be invocable as const");
1412 return _KeyOfValue()(*__node._M_valptr());
1416 _S_key(_Base_ptr __x)
1417 {
return _S_key(
static_cast<const _Node&
>(*__x)); }
1420 _S_key(_Node_ptr __x)
1421 {
return _S_key(*__x); }
1424 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
1425 {
return __x->_M_left; }
1428 _S_left(_Node_ptr __x)
1431 ?
static_cast<_Node&
>(*__x->_M_left)._M_node_ptr()
1436 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
1437 {
return __x->_M_right; }
1440 _S_right(_Node_ptr __x) _GLIBCXX_NOEXCEPT
1442 return __x->_M_right
1443 ?
static_cast<_Node&
>(*__x->_M_right)._M_node_ptr()
1448 typedef typename _Node_traits::_Iterator iterator;
1449 typedef typename _Node_traits::_Const_iterator const_iterator;
1454#if __cplusplus > 201402L
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>,
1461 pair<_Base_ptr, _Base_ptr>
1462 _M_get_insert_unique_pos(
const key_type& __k);
1464 pair<_Base_ptr, _Base_ptr>
1465 _M_get_insert_equal_pos(
const key_type& __k);
1467 pair<_Base_ptr, _Base_ptr>
1468 _M_get_insert_hint_unique_pos(const_iterator __pos,
1469 const key_type& __k);
1471 pair<_Base_ptr, _Base_ptr>
1472 _M_get_insert_hint_equal_pos(const_iterator __pos,
1473 const key_type& __k);
1476#if __cplusplus >= 201103L
1477 template<
typename _Arg,
typename _NodeGen>
1479 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
1482 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Node_ptr __z);
1484 template<
typename _Arg>
1486 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
1488 template<
typename _Arg>
1490 _M_insert_equal_lower(_Arg&& __x);
1493 _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z);
1496 _M_insert_equal_lower_node(_Node_ptr __z);
1498 template<
typename _NodeGen>
1500 _M_insert_(_Base_ptr __x, _Base_ptr __y,
1501 const value_type& __v, _NodeGen&);
1506 _M_insert_lower(_Base_ptr __y,
const value_type& __v);
1509 _M_insert_equal_lower(
const value_type& __x);
1512 enum { __as_lvalue, __as_rvalue };
1514 template<
bool _MoveValues,
typename _NodeGen>
1516 _M_copy(_Node_ptr, _Base_ptr, _NodeGen&);
1518 template<
bool _MoveValues,
typename _NodeGen>
1520 _M_copy(
const _Rb_tree& __x, _NodeGen& __gen)
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;
1531 _M_copy(
const _Rb_tree& __x)
1533 _Alloc_node __an(*
this);
1534 return _M_copy<__as_lvalue>(__x, __an);
1538 _M_erase(_Node_ptr __x);
1541 _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
1542 const _Key& __k)
const;
1545 _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
1546 const _Key& __k)
const;
1550#if __cplusplus < 201103L
1553 _Rb_tree() =
default;
1556 _Rb_tree(
const _Compare& __comp,
1557 const allocator_type& __a = allocator_type())
1558 : _M_impl(__comp, _Node_allocator(__a)) { }
1560 _Rb_tree(
const _Rb_tree& __x)
1561 : _M_impl(__x._M_impl)
1564 _M_root() = _M_copy(__x);
1567#if __cplusplus >= 201103L
1568 _Rb_tree(
const allocator_type& __a)
1569 : _M_impl(_Node_allocator(__a))
1572 _Rb_tree(
const _Rb_tree& __x,
const allocator_type& __a)
1573 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
1576 _M_root() = _M_copy(__x);
1579 _Rb_tree(_Rb_tree&&) =
default;
1581 _Rb_tree(_Rb_tree&& __x,
const allocator_type& __a)
1582 : _Rb_tree(
std::
move(__x), _Node_allocator(__a))
1586 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a,
true_type)
1587 noexcept(is_nothrow_default_constructible<_Compare>::value)
1591 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a,
false_type)
1592 : _M_impl(__x._M_impl._M_key_compare,
std::
move(__a))
1599 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1601 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
1602 std::declval<typename _Node_alloc_traits::is_always_equal>())) )
1608 ~_Rb_tree() _GLIBCXX_NOEXCEPT
1609 { _M_erase(_M_begin_node()); }
1612 operator=(
const _Rb_tree& __x);
1617 {
return _M_impl._M_key_compare; }
1620 begin() _GLIBCXX_NOEXCEPT
1621 {
return iterator(this->_M_impl._M_header._M_left); }
1624 begin() const _GLIBCXX_NOEXCEPT
1625 {
return const_iterator(this->_M_impl._M_header._M_left); }
1628 end() _GLIBCXX_NOEXCEPT
1629 {
return iterator(_M_end()); }
1632 end() const _GLIBCXX_NOEXCEPT
1633 {
return const_iterator(_M_end()); }
1636 rbegin() _GLIBCXX_NOEXCEPT
1637 {
return reverse_iterator(
end()); }
1639 const_reverse_iterator
1640 rbegin() const _GLIBCXX_NOEXCEPT
1641 {
return const_reverse_iterator(
end()); }
1644 rend() _GLIBCXX_NOEXCEPT
1645 {
return reverse_iterator(
begin()); }
1647 const_reverse_iterator
1648 rend() const _GLIBCXX_NOEXCEPT
1649 {
return const_reverse_iterator(
begin()); }
1651 _GLIBCXX_NODISCARD
bool
1652 empty() const _GLIBCXX_NOEXCEPT
1653 {
return _M_impl._M_node_count == 0; }
1656 size() const _GLIBCXX_NOEXCEPT
1657 {
return _M_impl._M_node_count; }
1660 max_size() const _GLIBCXX_NOEXCEPT
1665 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1668#if __cplusplus >= 201103L
1669 template<
typename _Arg>
1670 pair<iterator, bool>
1671 _M_insert_unique(_Arg&& __x);
1673 template<
typename _Arg>
1675 _M_insert_equal(_Arg&& __x);
1677 template<
typename _Arg,
typename _NodeGen>
1679 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1681 template<
typename _Arg>
1683 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1685 _Alloc_node __an(*
this);
1686 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1689 template<
typename _Arg,
typename _NodeGen>
1691 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1693 template<
typename _Arg>
1695 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1697 _Alloc_node __an(*
this);
1698 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1701 template<
typename... _Args>
1702 pair<iterator, bool>
1703 _M_emplace_unique(_Args&&... __args);
1705 template<
typename... _Args>
1707 _M_emplace_equal(_Args&&... __args);
1709 template<
typename... _Args>
1711 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1713 template<
typename... _Args>
1715 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1717 template<
typename _Iter>
1718 using __same_value_type
1719 = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1721 template<
typename _InputIterator>
1722 __enable_if_t<__same_value_type<_InputIterator>::value>
1723 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1725 _Alloc_node __an(*
this);
1726 for (; __first != __last; ++__first)
1727 _M_insert_unique_(
end(), *__first, __an);
1730 template<
typename _InputIterator>
1731 __enable_if_t<!__same_value_type<_InputIterator>::value>
1732 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1734 for (; __first != __last; ++__first)
1735 _M_emplace_unique(*__first);
1738 template<
typename _InputIterator>
1739 __enable_if_t<__same_value_type<_InputIterator>::value>
1740 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1742 _Alloc_node __an(*
this);
1743 for (; __first != __last; ++__first)
1744 _M_insert_equal_(
end(), *__first, __an);
1747 template<
typename _InputIterator>
1748 __enable_if_t<!__same_value_type<_InputIterator>::value>
1749 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1751 for (; __first != __last; ++__first)
1752 _M_emplace_equal(*__first);
1755 pair<iterator, bool>
1756 _M_insert_unique(
const value_type& __x);
1759 _M_insert_equal(
const value_type& __x);
1761 template<
typename _NodeGen>
1763 _M_insert_unique_(const_iterator __pos,
const value_type& __x,
1767 _M_insert_unique_(const_iterator __pos,
const value_type& __x)
1769 _Alloc_node __an(*
this);
1770 return _M_insert_unique_(__pos, __x, __an);
1773 template<
typename _NodeGen>
1775 _M_insert_equal_(const_iterator __pos,
const value_type& __x,
1778 _M_insert_equal_(const_iterator __pos,
const value_type& __x)
1780 _Alloc_node __an(*
this);
1781 return _M_insert_equal_(__pos, __x, __an);
1784 template<
typename _InputIterator>
1786 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1788 _Alloc_node __an(*
this);
1789 for (; __first != __last; ++__first)
1790 _M_insert_unique_(
end(), *__first, __an);
1793 template<
typename _InputIterator>
1795 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1797 _Alloc_node __an(*
this);
1798 for (; __first != __last; ++__first)
1799 _M_insert_equal_(
end(), *__first, __an);
1805 _M_erase_aux(const_iterator __position);
1808 _M_erase_aux(const_iterator __first, const_iterator __last);
1811#if __cplusplus >= 201103L
1814 _GLIBCXX_ABI_TAG_CXX11
1816 erase(const_iterator __position)
1818 __glibcxx_assert(__position !=
end());
1819 const_iterator __result = __position;
1821 _M_erase_aux(__position);
1822 return iterator(__result._M_node);
1826 _GLIBCXX_ABI_TAG_CXX11
1828 erase(iterator __position)
1830 __glibcxx_assert(__position !=
end());
1831 iterator __result = __position;
1833 _M_erase_aux(__position);
1838 erase(iterator __position)
1840 __glibcxx_assert(__position !=
end());
1841 _M_erase_aux(__position);
1845 erase(const_iterator __position)
1847 __glibcxx_assert(__position !=
end());
1848 _M_erase_aux(__position);
1853 erase(
const key_type& __x);
1855#if __cplusplus >= 201103L
1858 _GLIBCXX_ABI_TAG_CXX11
1860 erase(const_iterator __first, const_iterator __last)
1862 _M_erase_aux(__first, __last);
1863 return iterator(__last._M_node);
1867 erase(iterator __first, iterator __last)
1868 { _M_erase_aux(__first, __last); }
1871 erase(const_iterator __first, const_iterator __last)
1872 { _M_erase_aux(__first, __last); }
1876 clear() _GLIBCXX_NOEXCEPT
1878 _M_erase(_M_begin_node());
1884 find(
const key_type& __k);
1887 find(
const key_type& __k)
const;
1890 count(
const key_type& __k)
const;
1893 lower_bound(
const key_type& __k)
1894 {
return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
1897 lower_bound(
const key_type& __k)
const
1899 return const_iterator
1900 (_M_lower_bound(_M_begin(), _M_end(), __k));
1904 upper_bound(
const key_type& __k)
1905 {
return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
1908 upper_bound(
const key_type& __k)
const
1910 return const_iterator
1911 (_M_upper_bound(_M_begin(), _M_end(), __k));
1914 pair<iterator, iterator>
1915 equal_range(
const key_type& __k);
1917 pair<const_iterator, const_iterator>
1918 equal_range(
const key_type& __k)
const;
1920#if __cplusplus >= 201402L
1921 template<
typename _Kt,
1922 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1924 _M_find_tr(
const _Kt& __k)
1926 const _Rb_tree* __const_this =
this;
1927 return iterator(__const_this->_M_find_tr(__k)._M_node);
1930 template<
typename _Kt,
1931 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1933 _M_find_tr(
const _Kt& __k)
const
1935 const_iterator __j(_M_lower_bound_tr(__k));
1936 if (__j !=
end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1941 template<
typename _Kt,
1942 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1944 _M_count_tr(
const _Kt& __k)
const
1946 auto __p = _M_equal_range_tr(__k);
1950 template<
typename _Kt,
1951 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1953 _M_lower_bound_tr(
const _Kt& __k)
const
1955 auto __x = _M_begin();
1956 auto __y = _M_end();
1958 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1964 __x = _S_right(__x);
1968 template<
typename _Kt,
1969 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1971 _M_upper_bound_tr(
const _Kt& __k)
const
1973 auto __x = _M_begin();
1974 auto __y = _M_end();
1976 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1982 __x = _S_right(__x);
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)
1991 const _Rb_tree* __const_this =
this;
1992 auto __ret = __const_this->_M_equal_range_tr(__k);
1994 { iterator(__ret.first._M_node), iterator(__ret.second._M_node) };
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
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)))
2007 return { __low, __high };
2013 __rb_verify()
const;
2015#if __cplusplus >= 201103L
2017 operator=(_Rb_tree&&)
2018 noexcept(_Node_alloc_traits::_S_nothrow_move()
2019 && is_nothrow_move_assignable<_Compare>::value);
2021 template<typename _Iterator>
2023 _M_assign_unique(_Iterator, _Iterator);
2025 template<typename _Iterator>
2027 _M_assign_equal(_Iterator, _Iterator);
2033 { _M_impl._M_move_data(__x._M_impl); }
2050#if __glibcxx_node_extract
2052 _S_adapt(
typename _Node_alloc_traits::pointer __ptr)
2054#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
2057#pragma GCC diagnostic push
2058#pragma GCC diagnostic ignored "-Wc++17-extensions"
2059 using __alloc_ptr =
typename _Node_alloc_traits::pointer;
2060 if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
2063 return std::__to_address(__ptr);
2064#pragma GCC diagnostic pop
2071 _M_reinsert_node_unique(node_type&& __nh)
2073 insert_return_type __ret;
2075 __ret.position =
end();
2078 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2080 auto __res = _M_get_insert_unique_pos(__nh._M_key());
2084 = _M_insert_node(__res.first, __res.second,
2085 _S_adapt(__nh._M_ptr));
2087 __ret.inserted =
true;
2092 __ret.position = iterator(__res.first);
2093 __ret.inserted =
false;
2101 _M_reinsert_node_equal(node_type&& __nh)
2108 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2109 auto __res = _M_get_insert_equal_pos(__nh._M_key());
2111 __ret = _M_insert_node(__res.first, __res.second,
2112 _S_adapt(__nh._M_ptr));
2114 __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr));
2122 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
2129 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2130 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
2133 __ret = _M_insert_node(__res.first, __res.second,
2134 _S_adapt(__nh._M_ptr));
2138 __ret = iterator(__res.first);
2145 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
2152 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2153 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
2155 __ret = _M_insert_node(__res.first, __res.second,
2156 _S_adapt(__nh._M_ptr));
2158 __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr));
2166 extract(const_iterator __pos)
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() };
2175#pragma GCC diagnostic push
2176#pragma GCC diagnostic ignored "-Wc++17-extensions"
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() };
2182 auto __ap = pointer_traits<__alloc_ptr>::pointer_to(*__node_ptr);
2183 return { __ap, _M_get_Node_allocator() };
2185#pragma GCC diagnostic pop
2191 extract(
const key_type& __k)
2194 auto __pos = find(__k);
2196 __nh = extract(const_iterator(__pos));
2200 template<
typename _Compare2>
2201 using _Compatible_tree
2202 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
2204 template<
typename,
typename>
2205 friend struct _Rb_tree_merge_helper;
2208 template<
typename _Compare2>
2210 _M_merge_unique(_Compatible_tree<_Compare2>& __src)
noexcept
2212 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
2213 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
2216 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
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(__res.first, __res.second, __node_ptr);
2230 template<
typename _Compare2>
2232 _M_merge_equal(_Compatible_tree<_Compare2>& __src)
noexcept
2234 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
2235 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
2238 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
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(__res.first, __res.second, __node_ptr);
2253 operator==(
const _Rb_tree& __x,
const _Rb_tree& __y)
2255 return __x.size() == __y.size()
2256 && std::equal(__x.begin(), __x.end(), __y.begin());
2259#if __cpp_lib_three_way_comparison
2261 operator<=>(
const _Rb_tree& __x,
const _Rb_tree& __y)
2263 if constexpr (
requires {
typename __detail::__synth3way_t<_Val>; })
2265 __y.begin(), __y.end(),
2266 __detail::__synth3way);
2270 operator<(
const _Rb_tree& __x,
const _Rb_tree& __y)
2272 return std::lexicographical_compare(__x.begin(), __x.end(),
2273 __y.begin(), __y.end());
2278#if __cplusplus >= 201103L
2282 template<
typename... _Args>
2283 _Auto_node(_Rb_tree& __t, _Args&&... __args)
2285 _M_node(__t._M_create_node(
std::
forward<_Args>(__args)...))
2291 _M_t._M_drop_node(_M_node);
2294 _Auto_node(_Auto_node&& __n)
2295 : _M_t(__n._M_t), _M_node(__n._M_node)
2296 { __n._M_node =
nullptr; }
2300 {
return _S_key(_M_node); }
2303 _M_insert(pair<_Base_ptr, _Base_ptr> __p)
2305 auto __it = _M_t._M_insert_node(__p.first, __p.second, _M_node);
2311 _M_insert_equal_lower()
2313 auto __it = _M_t._M_insert_equal_lower_node(_M_node);
2324 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2325 typename _Compare,
typename _Alloc>
2327 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
2328 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
2331#if __cplusplus >= 201103L
2332 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2333 typename _Compare,
typename _Alloc>
2335 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2338 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
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)
2350 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2351 typename _Compare,
typename _Alloc>
2353 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2354 _M_move_assign(_Rb_tree& __x,
true_type)
2359 std::__alloc_on_move(_M_get_Node_allocator(),
2360 __x._M_get_Node_allocator());
2363 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2364 typename _Compare,
typename _Alloc>
2366 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2369 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
2370 return _M_move_assign(__x,
true_type{});
2374 _Reuse_or_alloc_node __roan(*
this);
2378 _M_root() = _M_copy<__as_rvalue>(__x, __roan);
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)
2391 _M_impl._M_key_compare =
std::move(__x._M_impl._M_key_compare);
2393 __bool_constant<_Node_alloc_traits::_S_nothrow_move()>());
2397 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2398 typename _Compare,
typename _Alloc>
2399 template<
typename _Iterator>
2401 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2402 _M_assign_unique(_Iterator __first, _Iterator __last)
2404 _Reuse_or_alloc_node __roan(*
this);
2406 for (; __first != __last; ++__first)
2407 _M_insert_unique_(
end(), *__first, __roan);
2410 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2411 typename _Compare,
typename _Alloc>
2412 template<
typename _Iterator>
2414 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2415 _M_assign_equal(_Iterator __first, _Iterator __last)
2417 _Reuse_or_alloc_node __roan(*
this);
2419 for (; __first != __last; ++__first)
2420 _M_insert_equal_(
end(), *__first, __roan);
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)
2433#if __cplusplus >= 201103L
2434 if (_Node_alloc_traits::_S_propagate_on_copy_assign())
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)
2444 std::__alloc_on_copy(__this_alloc, __that_alloc);
2449 _Reuse_or_alloc_node __roan(*
this);
2451 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
2453 _M_root() = _M_copy<__as_lvalue>(__x, __roan);
2459 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2460 typename _Compare,
typename _Alloc>
2461#if __cplusplus >= 201103L
2462 template<
typename _Arg,
typename _NodeGen>
2464 template<
typename _NodeGen>
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
2474 _NodeGen& __node_gen)
2476 bool __insert_left = (__x || __p == _M_end()
2477 || _M_impl._M_key_compare(_KeyOfValue()(__v),
2481 __node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
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);
2489 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2490 typename _Compare,
typename _Alloc>
2491#if __cplusplus >= 201103L
2492 template<
typename _Arg>
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)
2499 _M_insert_lower(_Base_ptr __p,
const _Val& __v)
2502 bool __insert_left = (__p == _M_end()
2503 || !_M_impl._M_key_compare(_S_key(__p),
2504 _KeyOfValue()(__v)));
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);
2514 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2515 typename _Compare,
typename _Alloc>
2516#if __cplusplus >= 201103L
2517 template<
typename _Arg>
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)
2524 _M_insert_equal_lower(
const _Val& __v)
2527 _Base_ptr __x = _M_begin();
2528 _Base_ptr __y = _M_end();
2532 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
2533 _S_left(__x) : _S_right(__x);
2535 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
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)
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;
2554 _M_copy<_MoveValues>(_S_right(__x), __top_base, __node_gen);
2561 _M_clone_node<_MoveValues>(__x, __node_gen)->_M_base_ptr();
2563 __y->_M_parent = __p;
2565 __y->_M_right = _M_copy<_MoveValues>(_S_right(__x),
2574 __throw_exception_again;
2579 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2580 typename _Compare,
typename _Alloc>
2582 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2583 _M_erase(_Node_ptr __x)
2588 _M_erase(_S_right(__x));
2589 _Node_ptr __y = _S_left(__x);
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
2604 if (!_M_impl._M_key_compare(_S_key(__x), __k))
2605 __y = __x, __x = _S_left(__x);
2607 __x = _S_right(__x);
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
2620 if (_M_impl._M_key_compare(__k, _S_key(__x)))
2621 __y = __x, __x = _S_left(__x);
2623 __x = _S_right(__x);
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)
2636 _Base_ptr __x = _M_begin();
2637 _Base_ptr __y = _M_end();
2640 if (_M_impl._M_key_compare(_S_key(__x), __k))
2641 __x = _S_right(__x);
2642 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2643 __y = __x, __x = _S_left(__x);
2646 _Base_ptr __xu(__x);
2647 _Base_ptr __yu(__y);
2648 __y = __x, __x = _S_left(__x);
2649 __xu = _S_right(__xu);
2650 return make_pair(iterator(_M_lower_bound(__x, __y, __k)),
2651 iterator(_M_upper_bound(__xu, __yu, __k)));
2654 return pair<iterator, iterator>(iterator(__y),
2658 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2659 typename _Compare,
typename _Alloc>
2660 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2661 _Compare, _Alloc>::const_iterator,
2662 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2663 _Compare, _Alloc>::const_iterator>
2664 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2665 equal_range(
const _Key& __k)
const
2667 _Base_ptr __x = _M_begin();
2668 _Base_ptr __y = _M_end();
2671 if (_M_impl._M_key_compare(_S_key(__x), __k))
2672 __x = _S_right(__x);
2673 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2674 __y = __x, __x = _S_left(__x);
2677 _Base_ptr __xu(__x);
2678 _Base_ptr __yu(__y);
2679 __y = __x, __x = _S_left(__x);
2680 __xu = _S_right(__xu);
2681 return make_pair(const_iterator(_M_lower_bound(__x, __y, __k)),
2682 const_iterator(_M_upper_bound(__xu, __yu, __k)));
2685 return pair<const_iterator, const_iterator>(const_iterator(__y),
2686 const_iterator(__y));
2689 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2690 typename _Compare,
typename _Alloc>
2692 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2694 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2699 _M_impl._M_move_data(__t._M_impl);
2701 else if (!__t._M_root())
2702 __t._M_impl._M_move_data(_M_impl);
2705 std::swap(_M_root(),__t._M_root());
2706 std::swap(_M_leftmost(),__t._M_leftmost());
2707 std::swap(_M_rightmost(),__t._M_rightmost());
2709 _M_root()->_M_parent = _M_end();
2710 __t._M_root()->_M_parent = __t._M_end();
2711 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2716 swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2718 _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2719 __t._M_get_Node_allocator());
2722 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2723 typename _Compare,
typename _Alloc>
2724 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2725 _Compare, _Alloc>::_Base_ptr,
2726 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2727 _Compare, _Alloc>::_Base_ptr>
2728 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2729 _M_get_insert_unique_pos(
const key_type& __k)
2731 typedef pair<_Base_ptr, _Base_ptr> _Res;
2732 _Base_ptr __x = _M_begin();
2733 _Base_ptr __y = _M_end();
2738 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2739 __x = __comp ? _S_left(__x) : _S_right(__x);
2741 iterator __j = iterator(__y);
2745 return _Res(__x, __y);
2749 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2750 return _Res(__x, __y);
2751 return _Res(__j._M_node, _Base_ptr());
2754 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2755 typename _Compare,
typename _Alloc>
2756 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2757 _Compare, _Alloc>::_Base_ptr,
2758 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2759 _Compare, _Alloc>::_Base_ptr>
2760 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2761 _M_get_insert_equal_pos(
const key_type& __k)
2763 typedef pair<_Base_ptr, _Base_ptr> _Res;
2764 _Base_ptr __x = _M_begin();
2765 _Base_ptr __y = _M_end();
2769 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2770 _S_left(__x) : _S_right(__x);
2772 return _Res(__x, __y);
2775 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2776 typename _Compare,
typename _Alloc>
2777#if __cplusplus >= 201103L
2778 template<
typename _Arg>
2780 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2781 _Compare, _Alloc>::iterator,
bool>
2782 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2783#if __cplusplus >= 201103L
2784 _M_insert_unique(_Arg&& __v)
2786 _M_insert_unique(
const _Val& __v)
2789 typedef pair<iterator, bool> _Res;
2790 pair<_Base_ptr, _Base_ptr> __res
2791 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2795 _Alloc_node __an(*
this);
2796 return _Res(_M_insert_(__res.first, __res.second,
2797 _GLIBCXX_FORWARD(_Arg, __v), __an),
2801 return _Res(iterator(__res.first),
false);
2804 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2805 typename _Compare,
typename _Alloc>
2806#if __cplusplus >= 201103L
2807 template<
typename _Arg>
2809 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2810 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2811#if __cplusplus >= 201103L
2812 _M_insert_equal(_Arg&& __v)
2814 _M_insert_equal(
const _Val& __v)
2817 pair<_Base_ptr, _Base_ptr> __res
2818 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2819 _Alloc_node __an(*
this);
2820 return _M_insert_(__res.first, __res.second,
2821 _GLIBCXX_FORWARD(_Arg, __v), __an);
2824 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2825 typename _Compare,
typename _Alloc>
2826 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2827 _Compare, _Alloc>::_Base_ptr,
2828 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2829 _Compare, _Alloc>::_Base_ptr>
2830 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2831 _M_get_insert_hint_unique_pos(const_iterator __position,
2832 const key_type& __k)
2834 typedef pair<_Base_ptr, _Base_ptr> _Res;
2837 if (__position._M_node == _M_end())
2840 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2841 return _Res(_Base_ptr(), _M_rightmost());
2843 return _M_get_insert_unique_pos(__k);
2845 else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))
2848 iterator __before(__position._M_node);
2849 if (__position._M_node == _M_leftmost())
2850 return _Res(_M_leftmost(), _M_leftmost());
2851 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2853 if (!_S_right(__before._M_node))
2854 return _Res(_Base_ptr(), __before._M_node);
2856 return _Res(__position._M_node, __position._M_node);
2859 return _M_get_insert_unique_pos(__k);
2861 else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))
2864 iterator __after(__position._M_node);
2865 if (__position._M_node == _M_rightmost())
2866 return _Res(_Base_ptr(), _M_rightmost());
2867 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2869 if (!_S_right(__position._M_node))
2870 return _Res(_Base_ptr(), __position._M_node);
2872 return _Res(__after._M_node, __after._M_node);
2875 return _M_get_insert_unique_pos(__k);
2879 return _Res(__position._M_node, _Base_ptr());
2882 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2883 typename _Compare,
typename _Alloc>
2884#if __cplusplus >= 201103L
2885 template<
typename _Arg,
typename _NodeGen>
2887 template<
typename _NodeGen>
2889 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2890 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2891 _M_insert_unique_(const_iterator __position,
2892#
if __cplusplus >= 201103L
2897 _NodeGen& __node_gen)
2899 pair<_Base_ptr, _Base_ptr> __res
2900 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2903 return _M_insert_(__res.first, __res.second,
2904 _GLIBCXX_FORWARD(_Arg, __v),
2906 return iterator(__res.first);
2909 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2910 typename _Compare,
typename _Alloc>
2911 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2912 _Compare, _Alloc>::_Base_ptr,
2913 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2914 _Compare, _Alloc>::_Base_ptr>
2915 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2916 _M_get_insert_hint_equal_pos(const_iterator __position,
const key_type& __k)
2918 typedef pair<_Base_ptr, _Base_ptr> _Res;
2921 if (__position._M_node == _M_end())
2924 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2925 return _Res(_Base_ptr(), _M_rightmost());
2927 return _M_get_insert_equal_pos(__k);
2929 else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))
2932 iterator __before(__position._M_node);
2933 if (__position._M_node == _M_leftmost())
2934 return _Res(_M_leftmost(), _M_leftmost());
2935 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2937 if (!_S_right(__before._M_node))
2938 return _Res(_Base_ptr(), __before._M_node);
2940 return _Res(__position._M_node, __position._M_node);
2943 return _M_get_insert_equal_pos(__k);
2948 iterator __after(__position._M_node);
2949 if (__position._M_node == _M_rightmost())
2950 return _Res(_Base_ptr(), _M_rightmost());
2951 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2953 if (!_S_right(__position._M_node))
2954 return _Res(_Base_ptr(), __position._M_node);
2956 return _Res(__after._M_node, __after._M_node);
2959 return _Res(_Base_ptr(), _Base_ptr());
2963 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2964 typename _Compare,
typename _Alloc>
2965#if __cplusplus >= 201103L
2966 template<
typename _Arg,
typename _NodeGen>
2968 template<
typename _NodeGen>
2970 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2971 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2972 _M_insert_equal_(const_iterator __position,
2973#
if __cplusplus >= 201103L
2978 _NodeGen& __node_gen)
2980 pair<_Base_ptr, _Base_ptr> __res
2981 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2984 return _M_insert_(__res.first, __res.second,
2985 _GLIBCXX_FORWARD(_Arg, __v),
2988 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2991#if __cplusplus >= 201103L
2992 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2993 typename _Compare,
typename _Alloc>
2995 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2996 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Node_ptr __z)
2999 bool __insert_left = (__x || __p == _M_end()
3000 || _M_impl._M_key_compare(_S_key(__z),
3003 _Base_ptr __base_z = __z->_M_base_ptr();
3004 _Node_traits::_S_insert_and_rebalance
3005 (__insert_left, __base_z, __p, this->_M_impl._M_header);
3006 ++_M_impl._M_node_count;
3007 return iterator(__base_z);
3010 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3011 typename _Compare,
typename _Alloc>
3013 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3014 _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z)
3017 bool __insert_left = (__p == _M_end()
3018 || !_M_impl._M_key_compare(_S_key(__p),
3021 _Base_ptr __base_z = __z->_M_base_ptr();
3022 _Node_traits::_S_insert_and_rebalance
3023 (__insert_left, __base_z, __p, this->_M_impl._M_header);
3024 ++_M_impl._M_node_count;
3025 return iterator(__base_z);
3028 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3029 typename _Compare,
typename _Alloc>
3031 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3032 _M_insert_equal_lower_node(_Node_ptr __z)
3035 _Base_ptr __x = _M_begin();
3036 _Base_ptr __y = _M_end();
3040 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
3041 _S_left(__x) : _S_right(__x);
3043 return _M_insert_lower_node(__y, __z);
3046 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3047 typename _Compare,
typename _Alloc>
3048 template<
typename... _Args>
3050 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3051 _M_emplace_unique(_Args&&... __args)
3052 -> pair<iterator, bool>
3054 _Auto_node __z(*
this, std::forward<_Args>(__args)...);
3055 auto __res = _M_get_insert_unique_pos(__z._M_key());
3057 return {__z._M_insert(__res),
true};
3058 return {iterator(__res.first),
false};
3061 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3062 typename _Compare,
typename _Alloc>
3063 template<
typename... _Args>
3065 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3066 _M_emplace_equal(_Args&&... __args)
3069 _Auto_node __z(*
this, std::forward<_Args>(__args)...);
3070 auto __res = _M_get_insert_equal_pos(__z._M_key());
3071 return __z._M_insert(__res);
3074 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3075 typename _Compare,
typename _Alloc>
3076 template<
typename... _Args>
3078 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3079 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
3082 _Auto_node __z(*
this, std::forward<_Args>(__args)...);
3083 auto __res = _M_get_insert_hint_unique_pos(__pos, __z._M_key());
3085 return __z._M_insert(__res);
3086 return iterator(__res.first);
3089 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3090 typename _Compare,
typename _Alloc>
3091 template<
typename... _Args>
3093 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3094 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
3097 _Auto_node __z(*
this, std::forward<_Args>(__args)...);
3098 auto __res = _M_get_insert_hint_equal_pos(__pos, __z._M_key());
3100 return __z._M_insert(__res);
3101 return __z._M_insert_equal_lower();
3106 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3107 typename _Compare,
typename _Alloc>
3109 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3110 _M_erase_aux(const_iterator __position)
3112 _Base_ptr __y = _Node_traits::_S_rebalance_for_erase
3113 (__position._M_node, this->_M_impl._M_header);
3114 _M_drop_node(
static_cast<_Node&
>(*__y)._M_node_ptr());
3115 --_M_impl._M_node_count;
3118 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3119 typename _Compare,
typename _Alloc>
3121 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3122 _M_erase_aux(const_iterator __first, const_iterator __last)
3124 if (__first ==
begin() && __last ==
end())
3127 while (__first != __last)
3128 _M_erase_aux(__first++);
3131 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3132 typename _Compare,
typename _Alloc>
3133 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
3134 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3135 erase(
const _Key& __x)
3137 pair<iterator, iterator> __p = equal_range(__x);
3138 const size_type __old_size =
size();
3139 _M_erase_aux(__p.first, __p.second);
3140 return __old_size -
size();
3143 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3144 typename _Compare,
typename _Alloc>
3145 typename _Rb_tree<_Key, _Val, _KeyOfValue,
3146 _Compare, _Alloc>::iterator
3147 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3148 find(
const _Key& __k)
3150 iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
3151 return (__j ==
end()
3152 || _M_impl._M_key_compare(__k,
3153 _S_key(__j._M_node))) ?
end() : __j;
3156 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3157 typename _Compare,
typename _Alloc>
3158 typename _Rb_tree<_Key, _Val, _KeyOfValue,
3159 _Compare, _Alloc>::const_iterator
3160 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3161 find(
const _Key& __k)
const
3163 const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
3164 return (__j ==
end()
3165 || _M_impl._M_key_compare(__k,
3166 _S_key(__j._M_node))) ?
end() : __j;
3169 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3170 typename _Compare,
typename _Alloc>
3171 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
3172 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3173 count(
const _Key& __k)
const
3175 pair<const_iterator, const_iterator> __p = equal_range(__k);
3180 _GLIBCXX_PURE
unsigned int
3181 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
3182 const _Rb_tree_node_base* __root)
throw ();
3184 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
3185 typename _Compare,
typename _Alloc>
3187 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const
3189 if (_M_impl._M_node_count == 0 ||
begin() ==
end())
3190 return _M_impl._M_node_count == 0 &&
begin() ==
end()
3191 && this->_M_impl._M_header._M_left == _M_end()
3192 && this->_M_impl._M_header._M_right == _M_end();
3194 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
3195 for (const_iterator __it =
begin(); __it !=
end(); ++__it)
3197 _Base_ptr __x = __it._M_node;
3198 _Base_ptr __L = _S_left(__x);
3199 _Base_ptr __R = _S_right(__x);
3201 if (__x->_M_color == _S_red)
3202 if ((__L && __L->_M_color == _S_red)
3203 || (__R && __R->_M_color == _S_red))
3206 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
3208 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
3211 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
3215 if (_M_leftmost() != _Node_base::_S_minimum(_M_root()))
3217 if (_M_rightmost() != _Node_base::_S_maximum(_M_root()))
3222#if __cplusplus > 201402L
3224 template<
typename _Key,
typename _Val,
typename _Sel,
typename _Cmp1,
3225 typename _Alloc,
typename _Cmp2>
3226 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
3230 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
3233 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
3234 {
return __tree._M_impl; }
3238_GLIBCXX_END_NAMESPACE_VERSION
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
constexpr _Tp * addressof(_Tp &__r) noexcept
Returns the actual address of the object or function referenced by r, even in the presence of an over...
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
ISO C++ entities toplevel namespace is std.
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr _Iterator __base(_Iterator __it)
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
Whether all instances of the allocator type compare equal.
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.