61 #pragma GCC system_header
68 #if __cplusplus >= 201103L
72 namespace std _GLIBCXX_VISIBILITY(default)
74 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 #if __cplusplus > 201103L
77 # define __cpp_lib_generic_associative_lookup 201304
96 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
98 struct _Rb_tree_node_base
100 typedef _Rb_tree_node_base* _Base_ptr;
101 typedef const _Rb_tree_node_base* _Const_Base_ptr;
103 _Rb_tree_color _M_color;
109 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
111 while (__x->_M_left != 0) __x = __x->_M_left;
115 static _Const_Base_ptr
116 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
118 while (__x->_M_left != 0) __x = __x->_M_left;
123 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
125 while (__x->_M_right != 0) __x = __x->_M_right;
129 static _Const_Base_ptr
130 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
132 while (__x->_M_right != 0) __x = __x->_M_right;
137 template<
typename _Val>
138 struct _Rb_tree_node :
public _Rb_tree_node_base
140 typedef _Rb_tree_node<_Val>* _Link_type;
142 #if __cplusplus < 201103L
153 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
157 {
return _M_storage._M_ptr(); }
161 {
return _M_storage._M_ptr(); }
165 _GLIBCXX_PURE _Rb_tree_node_base*
166 _Rb_tree_increment(_Rb_tree_node_base* __x)
throw ();
168 _GLIBCXX_PURE
const _Rb_tree_node_base*
169 _Rb_tree_increment(
const _Rb_tree_node_base* __x)
throw ();
171 _GLIBCXX_PURE _Rb_tree_node_base*
172 _Rb_tree_decrement(_Rb_tree_node_base* __x)
throw ();
174 _GLIBCXX_PURE
const _Rb_tree_node_base*
175 _Rb_tree_decrement(
const _Rb_tree_node_base* __x)
throw ();
177 template<
typename _Tp>
178 struct _Rb_tree_iterator
180 typedef _Tp value_type;
181 typedef _Tp& reference;
182 typedef _Tp* pointer;
184 typedef bidirectional_iterator_tag iterator_category;
185 typedef ptrdiff_t difference_type;
187 typedef _Rb_tree_iterator<_Tp> _Self;
188 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
189 typedef _Rb_tree_node<_Tp>* _Link_type;
191 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
195 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
200 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
203 operator->() const _GLIBCXX_NOEXCEPT
204 {
return static_cast<_Link_type
> (_M_node)->_M_valptr(); }
207 operator++() _GLIBCXX_NOEXCEPT
209 _M_node = _Rb_tree_increment(_M_node);
214 operator++(
int) _GLIBCXX_NOEXCEPT
217 _M_node = _Rb_tree_increment(_M_node);
222 operator--() _GLIBCXX_NOEXCEPT
224 _M_node = _Rb_tree_decrement(_M_node);
229 operator--(
int) _GLIBCXX_NOEXCEPT
232 _M_node = _Rb_tree_decrement(_M_node);
237 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
238 {
return _M_node == __x._M_node; }
241 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
242 {
return _M_node != __x._M_node; }
247 template<
typename _Tp>
248 struct _Rb_tree_const_iterator
250 typedef _Tp value_type;
251 typedef const _Tp& reference;
252 typedef const _Tp* pointer;
254 typedef _Rb_tree_iterator<_Tp> iterator;
256 typedef bidirectional_iterator_tag iterator_category;
257 typedef ptrdiff_t difference_type;
259 typedef _Rb_tree_const_iterator<_Tp> _Self;
260 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
261 typedef const _Rb_tree_node<_Tp>* _Link_type;
263 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
267 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
270 _Rb_tree_const_iterator(
const iterator& __it) _GLIBCXX_NOEXCEPT
271 : _M_node(__it._M_node) { }
274 _M_const_cast() const _GLIBCXX_NOEXCEPT
275 {
return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
279 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
282 operator->() const _GLIBCXX_NOEXCEPT
283 {
return static_cast<_Link_type
>(_M_node)->_M_valptr(); }
286 operator++() _GLIBCXX_NOEXCEPT
288 _M_node = _Rb_tree_increment(_M_node);
293 operator++(
int) _GLIBCXX_NOEXCEPT
296 _M_node = _Rb_tree_increment(_M_node);
301 operator--() _GLIBCXX_NOEXCEPT
303 _M_node = _Rb_tree_decrement(_M_node);
308 operator--(
int) _GLIBCXX_NOEXCEPT
311 _M_node = _Rb_tree_decrement(_M_node);
316 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
317 {
return _M_node == __x._M_node; }
320 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
321 {
return _M_node != __x._M_node; }
326 template<
typename _Val>
328 operator==(
const _Rb_tree_iterator<_Val>& __x,
329 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
330 {
return __x._M_node == __y._M_node; }
332 template<
typename _Val>
334 operator!=(
const _Rb_tree_iterator<_Val>& __x,
335 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
336 {
return __x._M_node != __y._M_node; }
339 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
340 _Rb_tree_node_base* __x,
341 _Rb_tree_node_base* __p,
342 _Rb_tree_node_base& __header)
throw ();
345 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
346 _Rb_tree_node_base& __header)
throw ();
348 #if __cplusplus > 201103L
349 template<
typename _Cmp,
typename _SfinaeType,
typename = __
void_t<>>
350 struct __has_is_transparent
353 template<
typename _Cmp,
typename _SfinaeType>
354 struct __has_is_transparent<_Cmp, _SfinaeType,
355 __void_t<typename _Cmp::is_transparent>>
356 {
typedef void type; };
359 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
360 typename _Compare,
typename _Alloc = allocator<_Val> >
364 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
369 typedef _Rb_tree_node_base* _Base_ptr;
370 typedef const _Rb_tree_node_base* _Const_Base_ptr;
371 typedef _Rb_tree_node<_Val>* _Link_type;
372 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
377 struct _Reuse_or_alloc_node
379 _Reuse_or_alloc_node(_Rb_tree& __t)
380 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
384 _M_root->_M_parent = 0;
386 if (_M_nodes->_M_left)
387 _M_nodes = _M_nodes->_M_left;
393 #if __cplusplus >= 201103L
394 _Reuse_or_alloc_node(
const _Reuse_or_alloc_node&) =
delete;
397 ~_Reuse_or_alloc_node()
398 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
400 template<
typename _Arg>
402 #if __cplusplus < 201103L
403 operator()(
const _Arg& __arg)
405 operator()(_Arg&& __arg)
408 _Link_type __node =
static_cast<_Link_type
>(_M_extract());
411 _M_t._M_destroy_node(__node);
412 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
416 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
426 _Base_ptr __node = _M_nodes;
427 _M_nodes = _M_nodes->_M_parent;
430 if (_M_nodes->_M_right == __node)
432 _M_nodes->_M_right = 0;
434 if (_M_nodes->_M_left)
436 _M_nodes = _M_nodes->_M_left;
438 while (_M_nodes->_M_right)
439 _M_nodes = _M_nodes->_M_right;
441 if (_M_nodes->_M_left)
442 _M_nodes = _M_nodes->_M_left;
446 _M_nodes->_M_left = 0;
463 _Alloc_node(_Rb_tree& __t)
466 template<
typename _Arg>
468 #if __cplusplus < 201103L
469 operator()(
const _Arg& __arg)
const
471 operator()(_Arg&& __arg) const
473 {
return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
480 typedef _Key key_type;
481 typedef _Val value_type;
482 typedef value_type* pointer;
483 typedef const value_type* const_pointer;
484 typedef value_type& reference;
485 typedef const value_type& const_reference;
486 typedef size_t size_type;
487 typedef ptrdiff_t difference_type;
488 typedef _Alloc allocator_type;
491 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
492 {
return *
static_cast<_Node_allocator*
>(&this->_M_impl); }
494 const _Node_allocator&
495 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
496 {
return *
static_cast<const _Node_allocator*
>(&this->_M_impl); }
499 get_allocator() const _GLIBCXX_NOEXCEPT
500 {
return allocator_type(_M_get_Node_allocator()); }
505 {
return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
508 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
511 #if __cplusplus < 201103L
513 _M_construct_node(_Link_type __node,
const value_type& __x)
516 { get_allocator().construct(__node->_M_valptr(), __x); }
520 __throw_exception_again;
525 _M_create_node(
const value_type& __x)
527 _Link_type __tmp = _M_get_node();
528 _M_construct_node(__tmp, __x);
533 _M_destroy_node(_Link_type __p)
534 { get_allocator().destroy(__p->_M_valptr()); }
536 template<
typename... _Args>
538 _M_construct_node(_Link_type __node, _Args&&... __args)
542 ::new(__node) _Rb_tree_node<_Val>;
543 _Alloc_traits::construct(_M_get_Node_allocator(),
545 std::
forward<_Args>(__args)...);
549 __node->~_Rb_tree_node<_Val>();
551 __throw_exception_again;
555 template<
typename... _Args>
557 _M_create_node(_Args&&... __args)
559 _Link_type __tmp = _M_get_node();
560 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
565 _M_destroy_node(_Link_type __p) noexcept
567 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
568 __p->~_Rb_tree_node<_Val>();
573 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
575 _M_destroy_node(__p);
579 template<
typename _NodeGen>
581 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
583 _Link_type __tmp = __node_gen(*__x->_M_valptr());
584 __tmp->_M_color = __x->_M_color;
592 template<
typename _Key_compare,
593 bool = __is_pod(_Key_compare)>
594 struct _Rb_tree_impl :
public _Node_allocator
596 _Key_compare _M_key_compare;
597 _Rb_tree_node_base _M_header;
598 size_type _M_node_count;
601 : _Node_allocator(), _M_key_compare(), _M_header(),
605 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
606 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
610 #if __cplusplus >= 201103L
611 _Rb_tree_impl(
const _Key_compare& __comp, _Node_allocator&& __a)
612 : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
613 _M_header(), _M_node_count(0)
620 this->_M_header._M_parent = 0;
621 this->_M_header._M_left = &this->_M_header;
622 this->_M_header._M_right = &this->_M_header;
623 this->_M_node_count = 0;
630 this->_M_header._M_color = _S_red;
631 this->_M_header._M_parent = 0;
632 this->_M_header._M_left = &this->_M_header;
633 this->_M_header._M_right = &this->_M_header;
637 _Rb_tree_impl<_Compare> _M_impl;
641 _M_root() _GLIBCXX_NOEXCEPT
642 {
return this->_M_impl._M_header._M_parent; }
645 _M_root() const _GLIBCXX_NOEXCEPT
646 {
return this->_M_impl._M_header._M_parent; }
649 _M_leftmost() _GLIBCXX_NOEXCEPT
650 {
return this->_M_impl._M_header._M_left; }
653 _M_leftmost() const _GLIBCXX_NOEXCEPT
654 {
return this->_M_impl._M_header._M_left; }
657 _M_rightmost() _GLIBCXX_NOEXCEPT
658 {
return this->_M_impl._M_header._M_right; }
661 _M_rightmost() const _GLIBCXX_NOEXCEPT
662 {
return this->_M_impl._M_header._M_right; }
665 _M_begin() _GLIBCXX_NOEXCEPT
666 {
return static_cast<_Link_type
>(this->_M_impl._M_header._M_parent); }
669 _M_begin() const _GLIBCXX_NOEXCEPT
671 return static_cast<_Const_Link_type
>
672 (this->_M_impl._M_header._M_parent);
676 _M_end() _GLIBCXX_NOEXCEPT
677 {
return &this->_M_impl._M_header; }
680 _M_end() const _GLIBCXX_NOEXCEPT
681 {
return &this->_M_impl._M_header; }
683 static const_reference
684 _S_value(_Const_Link_type __x)
685 {
return *__x->_M_valptr(); }
688 _S_key(_Const_Link_type __x)
689 {
return _KeyOfValue()(_S_value(__x)); }
692 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
693 {
return static_cast<_Link_type
>(__x->_M_left); }
695 static _Const_Link_type
696 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
697 {
return static_cast<_Const_Link_type
>(__x->_M_left); }
700 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
701 {
return static_cast<_Link_type
>(__x->_M_right); }
703 static _Const_Link_type
704 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
705 {
return static_cast<_Const_Link_type
>(__x->_M_right); }
707 static const_reference
708 _S_value(_Const_Base_ptr __x)
709 {
return *
static_cast<_Const_Link_type
>(__x)->_M_valptr(); }
712 _S_key(_Const_Base_ptr __x)
713 {
return _KeyOfValue()(_S_value(__x)); }
716 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
717 {
return _Rb_tree_node_base::_S_minimum(__x); }
719 static _Const_Base_ptr
720 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
721 {
return _Rb_tree_node_base::_S_minimum(__x); }
724 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
725 {
return _Rb_tree_node_base::_S_maximum(__x); }
727 static _Const_Base_ptr
728 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
729 {
return _Rb_tree_node_base::_S_maximum(__x); }
732 typedef _Rb_tree_iterator<value_type> iterator;
733 typedef _Rb_tree_const_iterator<value_type> const_iterator;
738 pair<_Base_ptr, _Base_ptr>
739 _M_get_insert_unique_pos(
const key_type& __k);
741 pair<_Base_ptr, _Base_ptr>
742 _M_get_insert_equal_pos(
const key_type& __k);
744 pair<_Base_ptr, _Base_ptr>
745 _M_get_insert_hint_unique_pos(const_iterator __pos,
746 const key_type& __k);
748 pair<_Base_ptr, _Base_ptr>
749 _M_get_insert_hint_equal_pos(const_iterator __pos,
750 const key_type& __k);
753 #if __cplusplus >= 201103L
754 template<
typename _Arg,
typename _NodeGen>
756 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
759 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
761 template<
typename _Arg>
763 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
765 template<
typename _Arg>
767 _M_insert_equal_lower(_Arg&& __x);
770 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
773 _M_insert_equal_lower_node(_Link_type __z);
775 template<
typename _NodeGen>
777 _M_insert_(_Base_ptr __x, _Base_ptr __y,
778 const value_type& __v, _NodeGen&);
783 _M_insert_lower(_Base_ptr __y,
const value_type& __v);
786 _M_insert_equal_lower(
const value_type& __x);
789 template<
typename _NodeGen>
791 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
794 _M_copy(_Const_Link_type __x, _Base_ptr __p)
796 _Alloc_node __an(*
this);
797 return _M_copy(__x, __p, __an);
801 _M_erase(_Link_type __x);
804 _M_lower_bound(_Link_type __x, _Base_ptr __y,
808 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
809 const _Key& __k)
const;
812 _M_upper_bound(_Link_type __x, _Base_ptr __y,
816 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
817 const _Key& __k)
const;
823 _Rb_tree(
const _Compare& __comp,
824 const allocator_type& __a = allocator_type())
825 : _M_impl(__comp, _Node_allocator(__a)) { }
827 _Rb_tree(
const _Rb_tree& __x)
828 : _M_impl(__x._M_impl._M_key_compare,
829 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
831 if (__x._M_root() != 0)
833 _M_root() = _M_copy(__x._M_begin(), _M_end());
834 _M_leftmost() = _S_minimum(_M_root());
835 _M_rightmost() = _S_maximum(_M_root());
836 _M_impl._M_node_count = __x._M_impl._M_node_count;
840 #if __cplusplus >= 201103L
841 _Rb_tree(
const allocator_type& __a)
842 : _M_impl(_Compare(), _Node_allocator(__a))
845 _Rb_tree(
const _Rb_tree& __x,
const allocator_type& __a)
846 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
848 if (__x._M_root() !=
nullptr)
850 _M_root() = _M_copy(__x._M_begin(), _M_end());
851 _M_leftmost() = _S_minimum(_M_root());
852 _M_rightmost() = _S_maximum(_M_root());
853 _M_impl._M_node_count = __x._M_impl._M_node_count;
857 _Rb_tree(_Rb_tree&& __x)
858 : _M_impl(__x._M_impl._M_key_compare,
859 std::move(__x._M_get_Node_allocator()))
861 if (__x._M_root() != 0)
865 _Rb_tree(_Rb_tree&& __x,
const allocator_type& __a)
866 : _Rb_tree(std::move(__x), _Node_allocator(__a))
869 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
872 ~_Rb_tree() _GLIBCXX_NOEXCEPT
873 { _M_erase(_M_begin()); }
876 operator=(
const _Rb_tree& __x);
881 {
return _M_impl._M_key_compare; }
884 begin() _GLIBCXX_NOEXCEPT
885 {
return iterator(this->_M_impl._M_header._M_left); }
888 begin() const _GLIBCXX_NOEXCEPT
889 {
return const_iterator(this->_M_impl._M_header._M_left); }
892 end() _GLIBCXX_NOEXCEPT
893 {
return iterator(&this->_M_impl._M_header); }
896 end() const _GLIBCXX_NOEXCEPT
897 {
return const_iterator(&this->_M_impl._M_header); }
900 rbegin() _GLIBCXX_NOEXCEPT
901 {
return reverse_iterator(
end()); }
903 const_reverse_iterator
904 rbegin() const _GLIBCXX_NOEXCEPT
905 {
return const_reverse_iterator(
end()); }
908 rend() _GLIBCXX_NOEXCEPT
909 {
return reverse_iterator(
begin()); }
911 const_reverse_iterator
912 rend() const _GLIBCXX_NOEXCEPT
913 {
return const_reverse_iterator(
begin()); }
916 empty() const _GLIBCXX_NOEXCEPT
917 {
return _M_impl._M_node_count == 0; }
920 size() const _GLIBCXX_NOEXCEPT
921 {
return _M_impl._M_node_count; }
924 max_size() const _GLIBCXX_NOEXCEPT
929 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
932 #if __cplusplus >= 201103L
933 template<
typename _Arg>
935 _M_insert_unique(_Arg&& __x);
937 template<
typename _Arg>
939 _M_insert_equal(_Arg&& __x);
941 template<
typename _Arg,
typename _NodeGen>
943 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
945 template<
typename _Arg>
947 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
949 _Alloc_node __an(*
this);
950 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
953 template<
typename _Arg,
typename _NodeGen>
955 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
957 template<
typename _Arg>
959 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
961 _Alloc_node __an(*
this);
962 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
965 template<
typename... _Args>
967 _M_emplace_unique(_Args&&... __args);
969 template<
typename... _Args>
971 _M_emplace_equal(_Args&&... __args);
973 template<
typename... _Args>
975 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
977 template<
typename... _Args>
979 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
982 _M_insert_unique(
const value_type& __x);
985 _M_insert_equal(
const value_type& __x);
987 template<
typename _NodeGen>
989 _M_insert_unique_(const_iterator __pos,
const value_type& __x,
993 _M_insert_unique_(const_iterator __pos,
const value_type& __x)
995 _Alloc_node __an(*
this);
996 return _M_insert_unique_(__pos, __x, __an);
999 template<
typename _NodeGen>
1001 _M_insert_equal_(const_iterator __pos,
const value_type& __x,
1004 _M_insert_equal_(const_iterator __pos,
const value_type& __x)
1006 _Alloc_node __an(*
this);
1007 return _M_insert_equal_(__pos, __x, __an);
1011 template<
typename _InputIterator>
1013 _M_insert_unique(_InputIterator __first, _InputIterator __last);
1015 template<
typename _InputIterator>
1017 _M_insert_equal(_InputIterator __first, _InputIterator __last);
1021 _M_erase_aux(const_iterator __position);
1024 _M_erase_aux(const_iterator __first, const_iterator __last);
1027 #if __cplusplus >= 201103L
1030 _GLIBCXX_ABI_TAG_CXX11
1032 erase(const_iterator __position)
1034 const_iterator __result = __position;
1036 _M_erase_aux(__position);
1037 return __result._M_const_cast();
1041 _GLIBCXX_ABI_TAG_CXX11
1043 erase(iterator __position)
1045 iterator __result = __position;
1047 _M_erase_aux(__position);
1052 erase(iterator __position)
1053 { _M_erase_aux(__position); }
1056 erase(const_iterator __position)
1057 { _M_erase_aux(__position); }
1060 erase(
const key_type& __x);
1062 #if __cplusplus >= 201103L
1065 _GLIBCXX_ABI_TAG_CXX11
1067 erase(const_iterator __first, const_iterator __last)
1069 _M_erase_aux(__first, __last);
1070 return __last._M_const_cast();
1074 erase(iterator __first, iterator __last)
1075 { _M_erase_aux(__first, __last); }
1078 erase(const_iterator __first, const_iterator __last)
1079 { _M_erase_aux(__first, __last); }
1082 erase(
const key_type* __first,
const key_type* __last);
1085 clear() _GLIBCXX_NOEXCEPT
1087 _M_erase(_M_begin());
1093 find(
const key_type& __k);
1096 find(
const key_type& __k)
const;
1099 count(
const key_type& __k)
const;
1102 lower_bound(
const key_type& __k)
1103 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1106 lower_bound(
const key_type& __k)
const
1107 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1110 upper_bound(
const key_type& __k)
1111 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1114 upper_bound(
const key_type& __k)
const
1115 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1117 pair<iterator, iterator>
1118 equal_range(
const key_type& __k);
1120 pair<const_iterator, const_iterator>
1121 equal_range(
const key_type& __k)
const;
1123 #if __cplusplus > 201103L
1124 template<
typename _Kt,
1126 typename __has_is_transparent<_Compare, _Kt>::type>
1128 _M_find_tr(
const _Kt& __k)
1130 const _Rb_tree* __const_this =
this;
1131 return __const_this->_M_find_tr(__k)._M_const_cast();
1134 template<
typename _Kt,
1136 typename __has_is_transparent<_Compare, _Kt>::type>
1138 _M_find_tr(
const _Kt& __k)
const
1140 auto __j = _M_lower_bound_tr(__k);
1141 if (__j !=
end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1146 template<
typename _Kt,
1148 typename __has_is_transparent<_Compare, _Kt>::type>
1150 _M_count_tr(
const _Kt& __k)
const
1152 auto __p = _M_equal_range_tr(__k);
1156 template<
typename _Kt,
1158 typename __has_is_transparent<_Compare, _Kt>::type>
1160 _M_lower_bound_tr(
const _Kt& __k)
1162 const _Rb_tree* __const_this =
this;
1163 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1166 template<
typename _Kt,
1168 typename __has_is_transparent<_Compare, _Kt>::type>
1170 _M_lower_bound_tr(
const _Kt& __k)
const
1172 auto __x = _M_begin();
1173 auto __y = _M_end();
1175 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1181 __x = _S_right(__x);
1182 return const_iterator(__y);
1185 template<
typename _Kt,
1187 typename __has_is_transparent<_Compare, _Kt>::type>
1189 _M_upper_bound_tr(
const _Kt& __k)
1191 const _Rb_tree* __const_this =
this;
1192 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1195 template<
typename _Kt,
1197 typename __has_is_transparent<_Compare, _Kt>::type>
1199 _M_upper_bound_tr(
const _Kt& __k)
const
1201 auto __x = _M_begin();
1202 auto __y = _M_end();
1204 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1210 __x = _S_right(__x);
1211 return const_iterator(__y);
1214 template<
typename _Kt,
1216 typename __has_is_transparent<_Compare, _Kt>::type>
1217 pair<iterator, iterator>
1218 _M_equal_range_tr(
const _Kt& __k)
1220 const _Rb_tree* __const_this =
this;
1221 auto __ret = __const_this->_M_equal_range_tr(__k);
1222 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1225 template<
typename _Kt,
1227 typename __has_is_transparent<_Compare, _Kt>::type>
1228 pair<const_iterator, const_iterator>
1229 _M_equal_range_tr(
const _Kt& __k)
const
1231 auto __low = _M_lower_bound_tr(__k);
1232 auto __high = __low;
1233 auto& __cmp = _M_impl._M_key_compare;
1234 while (__high !=
end() && !__cmp(__k, _S_key(__high._M_node)))
1236 return { __low, __high };
1242 __rb_verify()
const;
1244 #if __cplusplus >= 201103L
1246 operator=(_Rb_tree&&)
1247 noexcept(_Alloc_traits::_S_nothrow_move()
1248 && is_nothrow_move_assignable<_Compare>::value);
1250 template<typename _Iterator>
1252 _M_assign_unique(_Iterator, _Iterator);
1254 template<typename _Iterator>
1256 _M_assign_equal(_Iterator, _Iterator);
1261 _M_move_data(_Rb_tree&, std::
true_type);
1270 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1271 typename _Compare,
typename _Alloc>
1273 operator==(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1274 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1276 return __x.size() == __y.size()
1277 &&
std::equal(__x.begin(), __x.end(), __y.begin());
1280 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1281 typename _Compare,
typename _Alloc>
1283 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1284 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1287 __y.begin(), __y.end());
1290 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1291 typename _Compare,
typename _Alloc>
1293 operator!=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1294 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1295 {
return !(__x == __y); }
1297 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1298 typename _Compare,
typename _Alloc>
1300 operator>(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1301 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1302 {
return __y < __x; }
1304 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1305 typename _Compare,
typename _Alloc>
1307 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1308 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1309 {
return !(__y < __x); }
1311 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1312 typename _Compare,
typename _Alloc>
1314 operator>=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1315 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1316 {
return !(__x < __y); }
1318 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1319 typename _Compare,
typename _Alloc>
1321 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1322 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1325 #if __cplusplus >= 201103L
1326 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1327 typename _Compare,
typename _Alloc>
1328 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1329 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1330 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1332 using __eq =
typename _Alloc_traits::is_always_equal;
1333 if (__x._M_root() !=
nullptr)
1334 _M_move_data(__x, __eq());
1337 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1338 typename _Compare,
typename _Alloc>
1340 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1343 _M_root() = __x._M_root();
1344 _M_leftmost() = __x._M_leftmost();
1345 _M_rightmost() = __x._M_rightmost();
1346 _M_root()->_M_parent = _M_end();
1349 __x._M_leftmost() = __x._M_end();
1350 __x._M_rightmost() = __x._M_end();
1352 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1353 __x._M_impl._M_node_count = 0;
1356 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1357 typename _Compare,
typename _Alloc>
1359 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1362 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1366 _Alloc_node __an(*
this);
1368 [&__an](
const value_type& __cval)
1370 auto& __val =
const_cast<value_type&
>(__cval);
1373 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1374 _M_leftmost() = _S_minimum(_M_root());
1375 _M_rightmost() = _S_maximum(_M_root());
1376 _M_impl._M_node_count = __x._M_impl._M_node_count;
1380 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1381 typename _Compare,
typename _Alloc>
1382 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1383 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1384 operator=(_Rb_tree&& __x)
1385 noexcept(_Alloc_traits::_S_nothrow_move()
1386 && is_nothrow_move_assignable<_Compare>::value)
1388 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1389 if (_Alloc_traits::_S_propagate_on_move_assign()
1390 || _Alloc_traits::_S_always_equal()
1391 || _M_get_Node_allocator() == __x._M_get_Node_allocator())
1394 if (__x._M_root() !=
nullptr)
1396 std::__alloc_on_move(_M_get_Node_allocator(),
1397 __x._M_get_Node_allocator());
1403 _Reuse_or_alloc_node __roan(*
this);
1405 if (__x._M_root() !=
nullptr)
1408 [&__roan](
const value_type& __cval)
1410 auto& __val =
const_cast<value_type&
>(__cval);
1413 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1414 _M_leftmost() = _S_minimum(_M_root());
1415 _M_rightmost() = _S_maximum(_M_root());
1416 _M_impl._M_node_count = __x._M_impl._M_node_count;
1422 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1423 typename _Compare,
typename _Alloc>
1424 template<
typename _Iterator>
1426 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1427 _M_assign_unique(_Iterator __first, _Iterator __last)
1429 _Reuse_or_alloc_node __roan(*
this);
1431 for (; __first != __last; ++__first)
1432 _M_insert_unique_(
end(), *__first, __roan);
1435 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1436 typename _Compare,
typename _Alloc>
1437 template<
typename _Iterator>
1439 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1440 _M_assign_equal(_Iterator __first, _Iterator __last)
1442 _Reuse_or_alloc_node __roan(*
this);
1444 for (; __first != __last; ++__first)
1445 _M_insert_equal_(
end(), *__first, __roan);
1449 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1450 typename _Compare,
typename _Alloc>
1451 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1452 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1453 operator=(
const _Rb_tree& __x)
1458 #if __cplusplus >= 201103L
1459 if (_Alloc_traits::_S_propagate_on_copy_assign())
1461 auto& __this_alloc = this->_M_get_Node_allocator();
1462 auto& __that_alloc = __x._M_get_Node_allocator();
1463 if (!_Alloc_traits::_S_always_equal()
1464 && __this_alloc != __that_alloc)
1469 std::__alloc_on_copy(__this_alloc, __that_alloc);
1474 _Reuse_or_alloc_node __roan(*
this);
1476 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1477 if (__x._M_root() != 0)
1479 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1480 _M_leftmost() = _S_minimum(_M_root());
1481 _M_rightmost() = _S_maximum(_M_root());
1482 _M_impl._M_node_count = __x._M_impl._M_node_count;
1489 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1490 typename _Compare,
typename _Alloc>
1491 #if __cplusplus >= 201103L
1492 template<
typename _Arg,
typename _NodeGen>
1494 template<
typename _NodeGen>
1496 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1497 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1498 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1499 #
if __cplusplus >= 201103L
1504 _NodeGen& __node_gen)
1506 bool __insert_left = (__x != 0 || __p == _M_end()
1507 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1510 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1512 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1513 this->_M_impl._M_header);
1514 ++_M_impl._M_node_count;
1515 return iterator(__z);
1518 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1519 typename _Compare,
typename _Alloc>
1520 #if __cplusplus >= 201103L
1521 template<
typename _Arg>
1523 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1524 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1525 #if __cplusplus >= 201103L
1526 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1528 _M_insert_lower(_Base_ptr __p,
const _Val& __v)
1531 bool __insert_left = (__p == _M_end()
1532 || !_M_impl._M_key_compare(_S_key(__p),
1533 _KeyOfValue()(__v)));
1535 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1537 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1538 this->_M_impl._M_header);
1539 ++_M_impl._M_node_count;
1540 return iterator(__z);
1543 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1544 typename _Compare,
typename _Alloc>
1545 #if __cplusplus >= 201103L
1546 template<
typename _Arg>
1548 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1549 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1550 #if __cplusplus >= 201103L
1551 _M_insert_equal_lower(_Arg&& __v)
1553 _M_insert_equal_lower(
const _Val& __v)
1556 _Link_type __x = _M_begin();
1557 _Base_ptr __y = _M_end();
1561 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1562 _S_left(__x) : _S_right(__x);
1564 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1567 template<
typename _Key,
typename _Val,
typename _KoV,
1568 typename _Compare,
typename _Alloc>
1569 template<
typename _NodeGen>
1570 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1571 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1572 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1575 _Link_type __top = _M_clone_node(__x, __node_gen);
1576 __top->_M_parent = __p;
1581 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1587 _Link_type __y = _M_clone_node(__x, __node_gen);
1589 __y->_M_parent = __p;
1591 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1599 __throw_exception_again;
1604 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1605 typename _Compare,
typename _Alloc>
1607 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1608 _M_erase(_Link_type __x)
1613 _M_erase(_S_right(__x));
1614 _Link_type __y = _S_left(__x);
1620 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1621 typename _Compare,
typename _Alloc>
1622 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1623 _Compare, _Alloc>::iterator
1624 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1625 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1629 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1630 __y = __x, __x = _S_left(__x);
1632 __x = _S_right(__x);
1633 return iterator(__y);
1636 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1637 typename _Compare,
typename _Alloc>
1638 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1639 _Compare, _Alloc>::const_iterator
1640 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1641 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1642 const _Key& __k)
const
1645 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1646 __y = __x, __x = _S_left(__x);
1648 __x = _S_right(__x);
1649 return const_iterator(__y);
1652 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1653 typename _Compare,
typename _Alloc>
1654 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1655 _Compare, _Alloc>::iterator
1656 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1657 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1661 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1662 __y = __x, __x = _S_left(__x);
1664 __x = _S_right(__x);
1665 return iterator(__y);
1668 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1669 typename _Compare,
typename _Alloc>
1670 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1671 _Compare, _Alloc>::const_iterator
1672 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1673 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1674 const _Key& __k)
const
1677 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1678 __y = __x, __x = _S_left(__x);
1680 __x = _S_right(__x);
1681 return const_iterator(__y);
1684 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1685 typename _Compare,
typename _Alloc>
1686 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1687 _Compare, _Alloc>::iterator,
1688 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1689 _Compare, _Alloc>::iterator>
1690 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1691 equal_range(
const _Key& __k)
1693 _Link_type __x = _M_begin();
1694 _Base_ptr __y = _M_end();
1697 if (_M_impl._M_key_compare(_S_key(__x), __k))
1698 __x = _S_right(__x);
1699 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1700 __y = __x, __x = _S_left(__x);
1703 _Link_type __xu(__x);
1704 _Base_ptr __yu(__y);
1705 __y = __x, __x = _S_left(__x);
1706 __xu = _S_right(__xu);
1707 return pair<iterator,
1708 iterator>(_M_lower_bound(__x, __y, __k),
1709 _M_upper_bound(__xu, __yu, __k));
1712 return pair<iterator, iterator>(iterator(__y),
1716 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1717 typename _Compare,
typename _Alloc>
1718 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1719 _Compare, _Alloc>::const_iterator,
1720 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1721 _Compare, _Alloc>::const_iterator>
1722 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1723 equal_range(
const _Key& __k)
const
1725 _Const_Link_type __x = _M_begin();
1726 _Const_Base_ptr __y = _M_end();
1729 if (_M_impl._M_key_compare(_S_key(__x), __k))
1730 __x = _S_right(__x);
1731 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1732 __y = __x, __x = _S_left(__x);
1735 _Const_Link_type __xu(__x);
1736 _Const_Base_ptr __yu(__y);
1737 __y = __x, __x = _S_left(__x);
1738 __xu = _S_right(__xu);
1739 return pair<const_iterator,
1740 const_iterator>(_M_lower_bound(__x, __y, __k),
1741 _M_upper_bound(__xu, __yu, __k));
1744 return pair<const_iterator, const_iterator>(const_iterator(__y),
1745 const_iterator(__y));
1748 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1749 typename _Compare,
typename _Alloc>
1753 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1757 if (__t._M_root() != 0)
1759 _M_root() = __t._M_root();
1760 _M_leftmost() = __t._M_leftmost();
1761 _M_rightmost() = __t._M_rightmost();
1762 _M_root()->_M_parent = _M_end();
1763 _M_impl._M_node_count = __t._M_impl._M_node_count;
1765 __t._M_impl._M_reset();
1768 else if (__t._M_root() == 0)
1770 __t._M_root() = _M_root();
1771 __t._M_leftmost() = _M_leftmost();
1772 __t._M_rightmost() = _M_rightmost();
1773 __t._M_root()->_M_parent = __t._M_end();
1774 __t._M_impl._M_node_count = _M_impl._M_node_count;
1781 std::swap(_M_leftmost(),__t._M_leftmost());
1782 std::swap(_M_rightmost(),__t._M_rightmost());
1784 _M_root()->_M_parent = _M_end();
1785 __t._M_root()->_M_parent = __t._M_end();
1786 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1789 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1791 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1792 __t._M_get_Node_allocator());
1795 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1796 typename _Compare,
typename _Alloc>
1797 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1798 _Compare, _Alloc>::_Base_ptr,
1799 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1800 _Compare, _Alloc>::_Base_ptr>
1801 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1802 _M_get_insert_unique_pos(
const key_type& __k)
1804 typedef pair<_Base_ptr, _Base_ptr> _Res;
1805 _Link_type __x = _M_begin();
1806 _Base_ptr __y = _M_end();
1811 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1812 __x = __comp ? _S_left(__x) : _S_right(__x);
1814 iterator __j = iterator(__y);
1818 return _Res(__x, __y);
1822 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1823 return _Res(__x, __y);
1824 return _Res(__j._M_node, 0);
1827 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1828 typename _Compare,
typename _Alloc>
1829 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1830 _Compare, _Alloc>::_Base_ptr,
1831 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1832 _Compare, _Alloc>::_Base_ptr>
1833 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1834 _M_get_insert_equal_pos(
const key_type& __k)
1836 typedef pair<_Base_ptr, _Base_ptr> _Res;
1837 _Link_type __x = _M_begin();
1838 _Base_ptr __y = _M_end();
1842 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1843 _S_left(__x) : _S_right(__x);
1845 return _Res(__x, __y);
1848 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1849 typename _Compare,
typename _Alloc>
1850 #if __cplusplus >= 201103L
1851 template<
typename _Arg>
1853 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1854 _Compare, _Alloc>::iterator,
bool>
1855 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1856 #if __cplusplus >= 201103L
1857 _M_insert_unique(_Arg&& __v)
1859 _M_insert_unique(
const _Val& __v)
1862 typedef pair<iterator, bool> _Res;
1863 pair<_Base_ptr, _Base_ptr> __res
1864 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1868 _Alloc_node __an(*
this);
1869 return _Res(_M_insert_(__res.first, __res.second,
1870 _GLIBCXX_FORWARD(_Arg, __v), __an),
1874 return _Res(iterator(__res.first),
false);
1877 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1878 typename _Compare,
typename _Alloc>
1879 #if __cplusplus >= 201103L
1880 template<
typename _Arg>
1882 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1883 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1884 #if __cplusplus >= 201103L
1885 _M_insert_equal(_Arg&& __v)
1887 _M_insert_equal(
const _Val& __v)
1890 pair<_Base_ptr, _Base_ptr> __res
1891 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1892 _Alloc_node __an(*
this);
1893 return _M_insert_(__res.first, __res.second,
1894 _GLIBCXX_FORWARD(_Arg, __v), __an);
1897 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1898 typename _Compare,
typename _Alloc>
1899 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1900 _Compare, _Alloc>::_Base_ptr,
1901 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1902 _Compare, _Alloc>::_Base_ptr>
1903 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1904 _M_get_insert_hint_unique_pos(const_iterator __position,
1905 const key_type& __k)
1907 iterator __pos = __position._M_const_cast();
1908 typedef pair<_Base_ptr, _Base_ptr> _Res;
1911 if (__pos._M_node == _M_end())
1914 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1915 return _Res(0, _M_rightmost());
1917 return _M_get_insert_unique_pos(__k);
1919 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1922 iterator __before = __pos;
1923 if (__pos._M_node == _M_leftmost())
1924 return _Res(_M_leftmost(), _M_leftmost());
1925 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1927 if (_S_right(__before._M_node) == 0)
1928 return _Res(0, __before._M_node);
1930 return _Res(__pos._M_node, __pos._M_node);
1933 return _M_get_insert_unique_pos(__k);
1935 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1938 iterator __after = __pos;
1939 if (__pos._M_node == _M_rightmost())
1940 return _Res(0, _M_rightmost());
1941 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1943 if (_S_right(__pos._M_node) == 0)
1944 return _Res(0, __pos._M_node);
1946 return _Res(__after._M_node, __after._M_node);
1949 return _M_get_insert_unique_pos(__k);
1953 return _Res(__pos._M_node, 0);
1956 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1957 typename _Compare,
typename _Alloc>
1958 #if __cplusplus >= 201103L
1959 template<
typename _Arg,
typename _NodeGen>
1961 template<
typename _NodeGen>
1963 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1964 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1965 _M_insert_unique_(const_iterator __position,
1966 #
if __cplusplus >= 201103L
1971 _NodeGen& __node_gen)
1973 pair<_Base_ptr, _Base_ptr> __res
1974 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1977 return _M_insert_(__res.first, __res.second,
1978 _GLIBCXX_FORWARD(_Arg, __v),
1980 return iterator(__res.first);
1983 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1984 typename _Compare,
typename _Alloc>
1985 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1986 _Compare, _Alloc>::_Base_ptr,
1987 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1988 _Compare, _Alloc>::_Base_ptr>
1989 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1990 _M_get_insert_hint_equal_pos(const_iterator __position,
const key_type& __k)
1992 iterator __pos = __position._M_const_cast();
1993 typedef pair<_Base_ptr, _Base_ptr> _Res;
1996 if (__pos._M_node == _M_end())
1999 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2000 return _Res(0, _M_rightmost());
2002 return _M_get_insert_equal_pos(__k);
2004 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2007 iterator __before = __pos;
2008 if (__pos._M_node == _M_leftmost())
2009 return _Res(_M_leftmost(), _M_leftmost());
2010 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2012 if (_S_right(__before._M_node) == 0)
2013 return _Res(0, __before._M_node);
2015 return _Res(__pos._M_node, __pos._M_node);
2018 return _M_get_insert_equal_pos(__k);
2023 iterator __after = __pos;
2024 if (__pos._M_node == _M_rightmost())
2025 return _Res(0, _M_rightmost());
2026 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2028 if (_S_right(__pos._M_node) == 0)
2029 return _Res(0, __pos._M_node);
2031 return _Res(__after._M_node, __after._M_node);
2038 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2039 typename _Compare,
typename _Alloc>
2040 #if __cplusplus >= 201103L
2041 template<
typename _Arg,
typename _NodeGen>
2043 template<
typename _NodeGen>
2045 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2046 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2047 _M_insert_equal_(const_iterator __position,
2048 #
if __cplusplus >= 201103L
2053 _NodeGen& __node_gen)
2055 pair<_Base_ptr, _Base_ptr> __res
2056 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2059 return _M_insert_(__res.first, __res.second,
2060 _GLIBCXX_FORWARD(_Arg, __v),
2063 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2066 #if __cplusplus >= 201103L
2067 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2068 typename _Compare,
typename _Alloc>
2069 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2070 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2071 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2073 bool __insert_left = (__x != 0 || __p == _M_end()
2074 || _M_impl._M_key_compare(_S_key(__z),
2077 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2078 this->_M_impl._M_header);
2079 ++_M_impl._M_node_count;
2080 return iterator(__z);
2083 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2084 typename _Compare,
typename _Alloc>
2085 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2086 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2087 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2089 bool __insert_left = (__p == _M_end()
2090 || !_M_impl._M_key_compare(_S_key(__p),
2093 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2094 this->_M_impl._M_header);
2095 ++_M_impl._M_node_count;
2096 return iterator(__z);
2099 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2100 typename _Compare,
typename _Alloc>
2101 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2102 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2103 _M_insert_equal_lower_node(_Link_type __z)
2105 _Link_type __x = _M_begin();
2106 _Base_ptr __y = _M_end();
2110 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2111 _S_left(__x) : _S_right(__x);
2113 return _M_insert_lower_node(__y, __z);
2116 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2117 typename _Compare,
typename _Alloc>
2118 template<
typename... _Args>
2119 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2120 _Compare, _Alloc>::iterator,
bool>
2121 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2122 _M_emplace_unique(_Args&&... __args)
2124 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2128 typedef pair<iterator, bool> _Res;
2129 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2131 return _Res(_M_insert_node(__res.first, __res.second, __z),
true);
2134 return _Res(iterator(__res.first),
false);
2139 __throw_exception_again;
2143 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2144 typename _Compare,
typename _Alloc>
2145 template<
typename... _Args>
2146 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2147 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2148 _M_emplace_equal(_Args&&... __args)
2150 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2154 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2155 return _M_insert_node(__res.first, __res.second, __z);
2160 __throw_exception_again;
2164 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2165 typename _Compare,
typename _Alloc>
2166 template<
typename... _Args>
2167 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2168 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2169 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2171 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2175 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2178 return _M_insert_node(__res.first, __res.second, __z);
2181 return iterator(__res.first);
2186 __throw_exception_again;
2190 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2191 typename _Compare,
typename _Alloc>
2192 template<
typename... _Args>
2193 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2194 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2195 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2197 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2201 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2204 return _M_insert_node(__res.first, __res.second, __z);
2206 return _M_insert_equal_lower_node(__z);
2211 __throw_exception_again;
2216 template<
typename _Key,
typename _Val,
typename _KoV,
2217 typename _Cmp,
typename _Alloc>
2220 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2221 _M_insert_unique(_II __first, _II __last)
2223 _Alloc_node __an(*
this);
2224 for (; __first != __last; ++__first)
2225 _M_insert_unique_(
end(), *__first, __an);
2228 template<
typename _Key,
typename _Val,
typename _KoV,
2229 typename _Cmp,
typename _Alloc>
2232 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2233 _M_insert_equal(_II __first, _II __last)
2235 _Alloc_node __an(*
this);
2236 for (; __first != __last; ++__first)
2237 _M_insert_equal_(
end(), *__first, __an);
2240 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2241 typename _Compare,
typename _Alloc>
2243 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2244 _M_erase_aux(const_iterator __position)
2247 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2248 (const_cast<_Base_ptr>(__position._M_node),
2249 this->_M_impl._M_header));
2251 --_M_impl._M_node_count;
2254 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2255 typename _Compare,
typename _Alloc>
2257 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2258 _M_erase_aux(const_iterator __first, const_iterator __last)
2260 if (__first ==
begin() && __last ==
end())
2263 while (__first != __last)
2267 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2268 typename _Compare,
typename _Alloc>
2269 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2270 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2271 erase(
const _Key& __x)
2273 pair<iterator, iterator> __p = equal_range(__x);
2274 const size_type __old_size = size();
2275 erase(__p.first, __p.second);
2276 return __old_size - size();
2279 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2280 typename _Compare,
typename _Alloc>
2282 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2283 erase(
const _Key* __first,
const _Key* __last)
2285 while (__first != __last)
2289 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2290 typename _Compare,
typename _Alloc>
2291 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2292 _Compare, _Alloc>::iterator
2293 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2294 find(
const _Key& __k)
2296 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2297 return (__j ==
end()
2298 || _M_impl._M_key_compare(__k,
2299 _S_key(__j._M_node))) ?
end() : __j;
2302 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2303 typename _Compare,
typename _Alloc>
2304 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2305 _Compare, _Alloc>::const_iterator
2306 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2307 find(
const _Key& __k)
const
2309 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2310 return (__j ==
end()
2311 || _M_impl._M_key_compare(__k,
2312 _S_key(__j._M_node))) ?
end() : __j;
2315 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2316 typename _Compare,
typename _Alloc>
2317 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2318 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2319 count(
const _Key& __k)
const
2321 pair<const_iterator, const_iterator> __p = equal_range(__k);
2326 _GLIBCXX_PURE
unsigned int
2327 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
2328 const _Rb_tree_node_base* __root)
throw ();
2330 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2331 typename _Compare,
typename _Alloc>
2333 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const
2335 if (_M_impl._M_node_count == 0 ||
begin() ==
end())
2336 return _M_impl._M_node_count == 0 &&
begin() ==
end()
2337 && this->_M_impl._M_header._M_left == _M_end()
2338 && this->_M_impl._M_header._M_right == _M_end();
2340 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2341 for (const_iterator __it =
begin(); __it !=
end(); ++__it)
2343 _Const_Link_type __x =
static_cast<_Const_Link_type
>(__it._M_node);
2344 _Const_Link_type __L = _S_left(__x);
2345 _Const_Link_type __R = _S_right(__x);
2347 if (__x->_M_color == _S_red)
2348 if ((__L && __L->_M_color == _S_red)
2349 || (__R && __R->_M_color == _S_red))
2352 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2354 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2357 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2361 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2363 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2368 _GLIBCXX_END_NAMESPACE_VERSION
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
static void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
static size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.
constexpr conditional< __move_if_noexcept_cond< _Tp >::value, const _Tp &, _Tp && >::type move_if_noexcept(_Tp &__x) noexcept
Conditionally convert a value to an rvalue.
Uniform interface to C++98 and C++11 allocators.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.