61 #pragma GCC system_header 68 #if __cplusplus >= 201103L 72 namespace std _GLIBCXX_VISIBILITY(default)
74 _GLIBCXX_BEGIN_NAMESPACE_VERSION
92 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
94 struct _Rb_tree_node_base
96 typedef _Rb_tree_node_base* _Base_ptr;
97 typedef const _Rb_tree_node_base* _Const_Base_ptr;
99 _Rb_tree_color _M_color;
105 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
107 while (__x->_M_left != 0) __x = __x->_M_left;
111 static _Const_Base_ptr
112 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
114 while (__x->_M_left != 0) __x = __x->_M_left;
119 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
121 while (__x->_M_right != 0) __x = __x->_M_right;
125 static _Const_Base_ptr
126 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
128 while (__x->_M_right != 0) __x = __x->_M_right;
133 template<
typename _Val>
134 struct _Rb_tree_node :
public _Rb_tree_node_base
136 typedef _Rb_tree_node<_Val>* _Link_type;
138 #if __cplusplus < 201103L 149 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
153 {
return _M_storage._M_ptr(); }
157 {
return _M_storage._M_ptr(); }
161 _GLIBCXX_PURE _Rb_tree_node_base*
162 _Rb_tree_increment(_Rb_tree_node_base* __x)
throw ();
164 _GLIBCXX_PURE
const _Rb_tree_node_base*
165 _Rb_tree_increment(
const _Rb_tree_node_base* __x)
throw ();
167 _GLIBCXX_PURE _Rb_tree_node_base*
168 _Rb_tree_decrement(_Rb_tree_node_base* __x)
throw ();
170 _GLIBCXX_PURE
const _Rb_tree_node_base*
171 _Rb_tree_decrement(
const _Rb_tree_node_base* __x)
throw ();
173 template<
typename _Tp>
174 struct _Rb_tree_iterator
176 typedef _Tp value_type;
177 typedef _Tp& reference;
178 typedef _Tp* pointer;
180 typedef bidirectional_iterator_tag iterator_category;
181 typedef ptrdiff_t difference_type;
183 typedef _Rb_tree_iterator<_Tp> _Self;
184 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
185 typedef _Rb_tree_node<_Tp>* _Link_type;
187 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
191 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
196 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
199 operator->() const _GLIBCXX_NOEXCEPT
200 {
return static_cast<_Link_type
> (_M_node)->_M_valptr(); }
203 operator++() _GLIBCXX_NOEXCEPT
205 _M_node = _Rb_tree_increment(_M_node);
210 operator++(
int) _GLIBCXX_NOEXCEPT
213 _M_node = _Rb_tree_increment(_M_node);
218 operator--() _GLIBCXX_NOEXCEPT
220 _M_node = _Rb_tree_decrement(_M_node);
225 operator--(
int) _GLIBCXX_NOEXCEPT
228 _M_node = _Rb_tree_decrement(_M_node);
233 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
234 {
return _M_node == __x._M_node; }
237 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
238 {
return _M_node != __x._M_node; }
243 template<
typename _Tp>
244 struct _Rb_tree_const_iterator
246 typedef _Tp value_type;
247 typedef const _Tp& reference;
248 typedef const _Tp* pointer;
250 typedef _Rb_tree_iterator<_Tp> iterator;
252 typedef bidirectional_iterator_tag iterator_category;
253 typedef ptrdiff_t difference_type;
255 typedef _Rb_tree_const_iterator<_Tp> _Self;
256 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
257 typedef const _Rb_tree_node<_Tp>* _Link_type;
259 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
263 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
266 _Rb_tree_const_iterator(
const iterator& __it) _GLIBCXX_NOEXCEPT
267 : _M_node(__it._M_node) { }
270 _M_const_cast() const _GLIBCXX_NOEXCEPT
271 {
return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
275 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
278 operator->() const _GLIBCXX_NOEXCEPT
279 {
return static_cast<_Link_type
>(_M_node)->_M_valptr(); }
282 operator++() _GLIBCXX_NOEXCEPT
284 _M_node = _Rb_tree_increment(_M_node);
289 operator++(
int) _GLIBCXX_NOEXCEPT
292 _M_node = _Rb_tree_increment(_M_node);
297 operator--() _GLIBCXX_NOEXCEPT
299 _M_node = _Rb_tree_decrement(_M_node);
304 operator--(
int) _GLIBCXX_NOEXCEPT
307 _M_node = _Rb_tree_decrement(_M_node);
312 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
313 {
return _M_node == __x._M_node; }
316 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
317 {
return _M_node != __x._M_node; }
322 template<
typename _Val>
324 operator==(
const _Rb_tree_iterator<_Val>& __x,
325 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
326 {
return __x._M_node == __y._M_node; }
328 template<
typename _Val>
330 operator!=(
const _Rb_tree_iterator<_Val>& __x,
331 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
332 {
return __x._M_node != __y._M_node; }
335 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
336 _Rb_tree_node_base* __x,
337 _Rb_tree_node_base* __p,
338 _Rb_tree_node_base& __header)
throw ();
341 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
342 _Rb_tree_node_base& __header)
throw ();
344 #if __cplusplus > 201103L 345 template<
typename _Cmp,
typename _SfinaeType,
typename = __
void_t<>>
346 struct __has_is_transparent
349 template<
typename _Cmp,
typename _SfinaeType>
350 struct __has_is_transparent<_Cmp, _SfinaeType,
351 __void_t<typename _Cmp::is_transparent>>
352 {
typedef void type; };
355 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
356 typename _Compare,
typename _Alloc = allocator<_Val> >
360 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
365 typedef _Rb_tree_node_base* _Base_ptr;
366 typedef const _Rb_tree_node_base* _Const_Base_ptr;
367 typedef _Rb_tree_node<_Val>* _Link_type;
368 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
373 struct _Reuse_or_alloc_node
375 _Reuse_or_alloc_node(_Rb_tree& __t)
376 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
380 _M_root->_M_parent = 0;
382 if (_M_nodes->_M_left)
383 _M_nodes = _M_nodes->_M_left;
389 #if __cplusplus >= 201103L 390 _Reuse_or_alloc_node(
const _Reuse_or_alloc_node&) =
delete;
393 ~_Reuse_or_alloc_node()
394 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
396 template<
typename _Arg>
398 #if __cplusplus < 201103L 399 operator()(
const _Arg& __arg)
401 operator()(_Arg&& __arg)
404 _Link_type __node =
static_cast<_Link_type
>(_M_extract());
407 _M_t._M_destroy_node(__node);
408 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
412 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
422 _Base_ptr __node = _M_nodes;
423 _M_nodes = _M_nodes->_M_parent;
426 if (_M_nodes->_M_right == __node)
428 _M_nodes->_M_right = 0;
430 if (_M_nodes->_M_left)
432 _M_nodes = _M_nodes->_M_left;
434 while (_M_nodes->_M_right)
435 _M_nodes = _M_nodes->_M_right;
437 if (_M_nodes->_M_left)
438 _M_nodes = _M_nodes->_M_left;
442 _M_nodes->_M_left = 0;
459 _Alloc_node(_Rb_tree& __t)
462 template<
typename _Arg>
464 #if __cplusplus < 201103L 465 operator()(
const _Arg& __arg)
const 467 operator()(_Arg&& __arg) const
469 {
return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
476 typedef _Key key_type;
477 typedef _Val value_type;
478 typedef value_type* pointer;
479 typedef const value_type* const_pointer;
480 typedef value_type& reference;
481 typedef const value_type& const_reference;
482 typedef size_t size_type;
483 typedef ptrdiff_t difference_type;
484 typedef _Alloc allocator_type;
487 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
488 {
return *
static_cast<_Node_allocator*
>(&this->_M_impl); }
490 const _Node_allocator&
491 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
492 {
return *
static_cast<const _Node_allocator*
>(&this->_M_impl); }
495 get_allocator() const _GLIBCXX_NOEXCEPT
496 {
return allocator_type(_M_get_Node_allocator()); }
501 {
return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
504 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
505 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
507 #if __cplusplus < 201103L 509 _M_construct_node(_Link_type __node,
const value_type& __x)
512 { get_allocator().construct(__node->_M_valptr(), __x); }
516 __throw_exception_again;
521 _M_create_node(
const value_type& __x)
523 _Link_type __tmp = _M_get_node();
524 _M_construct_node(__tmp, __x);
529 _M_destroy_node(_Link_type __p)
530 { get_allocator().destroy(__p->_M_valptr()); }
532 template<
typename... _Args>
534 _M_construct_node(_Link_type __node, _Args&&... __args)
538 ::new(__node) _Rb_tree_node<_Val>;
539 _Alloc_traits::construct(_M_get_Node_allocator(),
545 __node->~_Rb_tree_node<_Val>();
547 __throw_exception_again;
551 template<
typename... _Args>
553 _M_create_node(_Args&&... __args)
555 _Link_type __tmp = _M_get_node();
556 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
561 _M_destroy_node(_Link_type __p) noexcept
563 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
564 __p->~_Rb_tree_node<_Val>();
569 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
571 _M_destroy_node(__p);
575 template<
typename _NodeGen>
577 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
579 _Link_type __tmp = __node_gen(*__x->_M_valptr());
580 __tmp->_M_color = __x->_M_color;
588 template<
typename _Key_compare,
589 bool = __is_pod(_Key_compare)>
590 struct _Rb_tree_impl :
public _Node_allocator
592 _Key_compare _M_key_compare;
593 _Rb_tree_node_base _M_header;
594 size_type _M_node_count;
597 : _Node_allocator(), _M_key_compare(), _M_header(),
601 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
602 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
606 #if __cplusplus >= 201103L 607 _Rb_tree_impl(
const _Key_compare& __comp, _Node_allocator&& __a)
608 : _Node_allocator(
std::move(__a)), _M_key_compare(__comp),
609 _M_header(), _M_node_count(0)
616 this->_M_header._M_parent = 0;
617 this->_M_header._M_left = &this->_M_header;
618 this->_M_header._M_right = &this->_M_header;
619 this->_M_node_count = 0;
626 this->_M_header._M_color = _S_red;
627 this->_M_header._M_parent = 0;
628 this->_M_header._M_left = &this->_M_header;
629 this->_M_header._M_right = &this->_M_header;
633 _Rb_tree_impl<_Compare> _M_impl;
637 _M_root() _GLIBCXX_NOEXCEPT
638 {
return this->_M_impl._M_header._M_parent; }
641 _M_root() const _GLIBCXX_NOEXCEPT
642 {
return this->_M_impl._M_header._M_parent; }
645 _M_leftmost() _GLIBCXX_NOEXCEPT
646 {
return this->_M_impl._M_header._M_left; }
649 _M_leftmost() const _GLIBCXX_NOEXCEPT
650 {
return this->_M_impl._M_header._M_left; }
653 _M_rightmost() _GLIBCXX_NOEXCEPT
654 {
return this->_M_impl._M_header._M_right; }
657 _M_rightmost() const _GLIBCXX_NOEXCEPT
658 {
return this->_M_impl._M_header._M_right; }
661 _M_begin() _GLIBCXX_NOEXCEPT
662 {
return static_cast<_Link_type
>(this->_M_impl._M_header._M_parent); }
665 _M_begin() const _GLIBCXX_NOEXCEPT
667 return static_cast<_Const_Link_type
> 668 (this->_M_impl._M_header._M_parent);
672 _M_end() _GLIBCXX_NOEXCEPT
673 {
return &this->_M_impl._M_header; }
676 _M_end() const _GLIBCXX_NOEXCEPT
677 {
return &this->_M_impl._M_header; }
679 static const_reference
680 _S_value(_Const_Link_type __x)
681 {
return *__x->_M_valptr(); }
684 _S_key(_Const_Link_type __x)
685 {
return _KeyOfValue()(_S_value(__x)); }
688 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
689 {
return static_cast<_Link_type
>(__x->_M_left); }
691 static _Const_Link_type
692 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
693 {
return static_cast<_Const_Link_type
>(__x->_M_left); }
696 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
697 {
return static_cast<_Link_type
>(__x->_M_right); }
699 static _Const_Link_type
700 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
701 {
return static_cast<_Const_Link_type
>(__x->_M_right); }
703 static const_reference
704 _S_value(_Const_Base_ptr __x)
705 {
return *
static_cast<_Const_Link_type
>(__x)->_M_valptr(); }
708 _S_key(_Const_Base_ptr __x)
709 {
return _KeyOfValue()(_S_value(__x)); }
712 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
713 {
return _Rb_tree_node_base::_S_minimum(__x); }
715 static _Const_Base_ptr
716 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
717 {
return _Rb_tree_node_base::_S_minimum(__x); }
720 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
721 {
return _Rb_tree_node_base::_S_maximum(__x); }
723 static _Const_Base_ptr
724 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
725 {
return _Rb_tree_node_base::_S_maximum(__x); }
728 typedef _Rb_tree_iterator<value_type> iterator;
729 typedef _Rb_tree_const_iterator<value_type> const_iterator;
734 pair<_Base_ptr, _Base_ptr>
735 _M_get_insert_unique_pos(
const key_type& __k);
737 pair<_Base_ptr, _Base_ptr>
738 _M_get_insert_equal_pos(
const key_type& __k);
740 pair<_Base_ptr, _Base_ptr>
741 _M_get_insert_hint_unique_pos(const_iterator __pos,
742 const key_type& __k);
744 pair<_Base_ptr, _Base_ptr>
745 _M_get_insert_hint_equal_pos(const_iterator __pos,
746 const key_type& __k);
749 #if __cplusplus >= 201103L 750 template<
typename _Arg,
typename _NodeGen>
752 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
755 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
757 template<
typename _Arg>
759 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
761 template<
typename _Arg>
763 _M_insert_equal_lower(_Arg&& __x);
766 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
769 _M_insert_equal_lower_node(_Link_type __z);
771 template<
typename _NodeGen>
773 _M_insert_(_Base_ptr __x, _Base_ptr __y,
774 const value_type& __v, _NodeGen&);
779 _M_insert_lower(_Base_ptr __y,
const value_type& __v);
782 _M_insert_equal_lower(
const value_type& __x);
785 template<
typename _NodeGen>
787 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
790 _M_copy(_Const_Link_type __x, _Base_ptr __p)
792 _Alloc_node __an(*
this);
793 return _M_copy(__x, __p, __an);
797 _M_erase(_Link_type __x);
800 _M_lower_bound(_Link_type __x, _Base_ptr __y,
804 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
805 const _Key& __k)
const;
808 _M_upper_bound(_Link_type __x, _Base_ptr __y,
812 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
813 const _Key& __k)
const;
819 _Rb_tree(
const _Compare& __comp,
820 const allocator_type& __a = allocator_type())
821 : _M_impl(__comp, _Node_allocator(__a)) { }
823 _Rb_tree(
const _Rb_tree& __x)
824 : _M_impl(__x._M_impl._M_key_compare,
825 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
827 if (__x._M_root() != 0)
829 _M_root() = _M_copy(__x._M_begin(), _M_end());
830 _M_leftmost() = _S_minimum(_M_root());
831 _M_rightmost() = _S_maximum(_M_root());
832 _M_impl._M_node_count = __x._M_impl._M_node_count;
836 #if __cplusplus >= 201103L 837 _Rb_tree(
const allocator_type& __a)
838 : _M_impl(_Compare(), _Node_allocator(__a))
841 _Rb_tree(
const _Rb_tree& __x,
const allocator_type& __a)
842 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
844 if (__x._M_root() !=
nullptr)
846 _M_root() = _M_copy(__x._M_begin(), _M_end());
847 _M_leftmost() = _S_minimum(_M_root());
848 _M_rightmost() = _S_maximum(_M_root());
849 _M_impl._M_node_count = __x._M_impl._M_node_count;
853 _Rb_tree(_Rb_tree&& __x)
854 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
856 if (__x._M_root() != 0)
860 _Rb_tree(_Rb_tree&& __x,
const allocator_type& __a)
861 : _Rb_tree(
std::move(__x), _Node_allocator(__a))
864 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
867 ~_Rb_tree() _GLIBCXX_NOEXCEPT
868 { _M_erase(_M_begin()); }
871 operator=(
const _Rb_tree& __x);
876 {
return _M_impl._M_key_compare; }
879 begin() _GLIBCXX_NOEXCEPT
880 {
return iterator(this->_M_impl._M_header._M_left); }
883 begin() const _GLIBCXX_NOEXCEPT
884 {
return const_iterator(this->_M_impl._M_header._M_left); }
887 end() _GLIBCXX_NOEXCEPT
888 {
return iterator(&this->_M_impl._M_header); }
891 end() const _GLIBCXX_NOEXCEPT
892 {
return const_iterator(&this->_M_impl._M_header); }
895 rbegin() _GLIBCXX_NOEXCEPT
896 {
return reverse_iterator(
end()); }
898 const_reverse_iterator
899 rbegin() const _GLIBCXX_NOEXCEPT
900 {
return const_reverse_iterator(
end()); }
903 rend() _GLIBCXX_NOEXCEPT
904 {
return reverse_iterator(
begin()); }
906 const_reverse_iterator
907 rend() const _GLIBCXX_NOEXCEPT
908 {
return const_reverse_iterator(
begin()); }
911 empty() const _GLIBCXX_NOEXCEPT
912 {
return _M_impl._M_node_count == 0; }
915 size() const _GLIBCXX_NOEXCEPT
916 {
return _M_impl._M_node_count; }
919 max_size() const _GLIBCXX_NOEXCEPT
920 {
return _Alloc_traits::max_size(_M_get_Node_allocator()); }
924 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
927 #if __cplusplus >= 201103L 928 template<
typename _Arg>
930 _M_insert_unique(_Arg&& __x);
932 template<
typename _Arg>
934 _M_insert_equal(_Arg&& __x);
936 template<
typename _Arg,
typename _NodeGen>
938 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
940 template<
typename _Arg>
942 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
944 _Alloc_node __an(*
this);
945 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
948 template<
typename _Arg,
typename _NodeGen>
950 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
952 template<
typename _Arg>
954 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
956 _Alloc_node __an(*
this);
957 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
960 template<
typename... _Args>
962 _M_emplace_unique(_Args&&... __args);
964 template<
typename... _Args>
966 _M_emplace_equal(_Args&&... __args);
968 template<
typename... _Args>
970 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
972 template<
typename... _Args>
974 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
977 _M_insert_unique(
const value_type& __x);
980 _M_insert_equal(
const value_type& __x);
982 template<
typename _NodeGen>
984 _M_insert_unique_(const_iterator __pos,
const value_type& __x,
988 _M_insert_unique_(const_iterator __pos,
const value_type& __x)
990 _Alloc_node __an(*
this);
991 return _M_insert_unique_(__pos, __x, __an);
994 template<
typename _NodeGen>
996 _M_insert_equal_(const_iterator __pos,
const value_type& __x,
999 _M_insert_equal_(const_iterator __pos,
const value_type& __x)
1001 _Alloc_node __an(*
this);
1002 return _M_insert_equal_(__pos, __x, __an);
1006 template<
typename _InputIterator>
1008 _M_insert_unique(_InputIterator __first, _InputIterator __last);
1010 template<
typename _InputIterator>
1012 _M_insert_equal(_InputIterator __first, _InputIterator __last);
1016 _M_erase_aux(const_iterator __position);
1019 _M_erase_aux(const_iterator __first, const_iterator __last);
1022 #if __cplusplus >= 201103L 1025 _GLIBCXX_ABI_TAG_CXX11
1027 erase(const_iterator __position)
1029 const_iterator __result = __position;
1031 _M_erase_aux(__position);
1032 return __result._M_const_cast();
1036 _GLIBCXX_ABI_TAG_CXX11
1038 erase(iterator __position)
1040 iterator __result = __position;
1042 _M_erase_aux(__position);
1047 erase(iterator __position)
1048 { _M_erase_aux(__position); }
1051 erase(const_iterator __position)
1052 { _M_erase_aux(__position); }
1055 erase(
const key_type& __x);
1057 #if __cplusplus >= 201103L 1060 _GLIBCXX_ABI_TAG_CXX11
1062 erase(const_iterator __first, const_iterator __last)
1064 _M_erase_aux(__first, __last);
1065 return __last._M_const_cast();
1069 erase(iterator __first, iterator __last)
1070 { _M_erase_aux(__first, __last); }
1073 erase(const_iterator __first, const_iterator __last)
1074 { _M_erase_aux(__first, __last); }
1077 erase(
const key_type* __first,
const key_type* __last);
1080 clear() _GLIBCXX_NOEXCEPT
1082 _M_erase(_M_begin());
1088 find(
const key_type& __k);
1091 find(
const key_type& __k)
const;
1094 count(
const key_type& __k)
const;
1097 lower_bound(
const key_type& __k)
1098 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1101 lower_bound(
const key_type& __k)
const 1102 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1105 upper_bound(
const key_type& __k)
1106 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1109 upper_bound(
const key_type& __k)
const 1110 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1112 pair<iterator, iterator>
1113 equal_range(
const key_type& __k);
1115 pair<const_iterator, const_iterator>
1116 equal_range(
const key_type& __k)
const;
1118 #if __cplusplus > 201103L 1119 template<
typename _Kt,
1121 typename __has_is_transparent<_Compare, _Kt>::type>
1123 _M_find_tr(
const _Kt& __k)
1125 const _Rb_tree* __const_this =
this;
1126 return __const_this->_M_find_tr(__k)._M_const_cast();
1129 template<
typename _Kt,
1131 typename __has_is_transparent<_Compare, _Kt>::type>
1133 _M_find_tr(
const _Kt& __k)
const 1135 auto __j = _M_lower_bound_tr(__k);
1136 if (__j !=
end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1141 template<
typename _Kt,
1143 typename __has_is_transparent<_Compare, _Kt>::type>
1145 _M_count_tr(
const _Kt& __k)
const 1147 auto __p = _M_equal_range_tr(__k);
1151 template<
typename _Kt,
1153 typename __has_is_transparent<_Compare, _Kt>::type>
1155 _M_lower_bound_tr(
const _Kt& __k)
1157 const _Rb_tree* __const_this =
this;
1158 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1161 template<
typename _Kt,
1163 typename __has_is_transparent<_Compare, _Kt>::type>
1165 _M_lower_bound_tr(
const _Kt& __k)
const 1167 auto __x = _M_begin();
1168 auto __y = _M_end();
1170 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1176 __x = _S_right(__x);
1177 return const_iterator(__y);
1180 template<
typename _Kt,
1182 typename __has_is_transparent<_Compare, _Kt>::type>
1184 _M_upper_bound_tr(
const _Kt& __k)
1186 const _Rb_tree* __const_this =
this;
1187 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1190 template<
typename _Kt,
1192 typename __has_is_transparent<_Compare, _Kt>::type>
1194 _M_upper_bound_tr(
const _Kt& __k)
const 1196 auto __x = _M_begin();
1197 auto __y = _M_end();
1199 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1205 __x = _S_right(__x);
1206 return const_iterator(__y);
1209 template<
typename _Kt,
1211 typename __has_is_transparent<_Compare, _Kt>::type>
1212 pair<iterator, iterator>
1213 _M_equal_range_tr(
const _Kt& __k)
1215 const _Rb_tree* __const_this =
this;
1216 auto __ret = __const_this->_M_equal_range_tr(__k);
1217 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1220 template<
typename _Kt,
1222 typename __has_is_transparent<_Compare, _Kt>::type>
1223 pair<const_iterator, const_iterator>
1224 _M_equal_range_tr(
const _Kt& __k)
const 1226 auto __low = _M_lower_bound_tr(__k);
1227 auto __high = __low;
1228 auto& __cmp = _M_impl._M_key_compare;
1229 while (__high !=
end() && !__cmp(__k, _S_key(__high._M_node)))
1231 return { __low, __high };
1237 __rb_verify()
const;
1239 #if __cplusplus >= 201103L 1241 operator=(_Rb_tree&&)
1242 noexcept(_Alloc_traits::_S_nothrow_move()
1243 && is_nothrow_move_assignable<_Compare>::value);
1245 template<typename _Iterator>
1247 _M_assign_unique(_Iterator, _Iterator);
1249 template<typename _Iterator>
1251 _M_assign_equal(_Iterator, _Iterator);
1265 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1266 typename _Compare,
typename _Alloc>
1268 operator==(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1269 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1271 return __x.size() == __y.size()
1272 &&
std::equal(__x.begin(), __x.end(), __y.begin());
1275 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1276 typename _Compare,
typename _Alloc>
1278 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1279 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1282 __y.begin(), __y.end());
1285 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1286 typename _Compare,
typename _Alloc>
1288 operator!=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1289 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1290 {
return !(__x == __y); }
1292 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1293 typename _Compare,
typename _Alloc>
1295 operator>(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1296 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1297 {
return __y < __x; }
1299 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1300 typename _Compare,
typename _Alloc>
1302 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1303 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1304 {
return !(__y < __x); }
1306 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1307 typename _Compare,
typename _Alloc>
1309 operator>=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1310 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1311 {
return !(__x < __y); }
1313 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1314 typename _Compare,
typename _Alloc>
1316 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1317 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1320 #if __cplusplus >= 201103L 1321 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1322 typename _Compare,
typename _Alloc>
1323 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1324 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1325 : _M_impl(__x._M_impl._M_key_compare,
std::move(__a))
1327 using __eq =
typename _Alloc_traits::is_always_equal;
1328 if (__x._M_root() !=
nullptr)
1329 _M_move_data(__x, __eq());
1332 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1333 typename _Compare,
typename _Alloc>
1335 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1338 _M_root() = __x._M_root();
1339 _M_leftmost() = __x._M_leftmost();
1340 _M_rightmost() = __x._M_rightmost();
1341 _M_root()->_M_parent = _M_end();
1344 __x._M_leftmost() = __x._M_end();
1345 __x._M_rightmost() = __x._M_end();
1347 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1348 __x._M_impl._M_node_count = 0;
1351 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1352 typename _Compare,
typename _Alloc>
1354 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1357 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1361 _Alloc_node __an(*
this);
1363 [&__an](
const value_type& __cval)
1365 auto& __val =
const_cast<value_type&
>(__cval);
1368 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1369 _M_leftmost() = _S_minimum(_M_root());
1370 _M_rightmost() = _S_maximum(_M_root());
1371 _M_impl._M_node_count = __x._M_impl._M_node_count;
1375 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1376 typename _Compare,
typename _Alloc>
1377 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1378 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1379 operator=(_Rb_tree&& __x)
1380 noexcept(_Alloc_traits::_S_nothrow_move()
1381 && is_nothrow_move_assignable<_Compare>::value)
1383 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1384 if (_Alloc_traits::_S_propagate_on_move_assign()
1385 || _Alloc_traits::_S_always_equal()
1386 || _M_get_Node_allocator() == __x._M_get_Node_allocator())
1389 if (__x._M_root() !=
nullptr)
1391 std::__alloc_on_move(_M_get_Node_allocator(),
1392 __x._M_get_Node_allocator());
1398 _Reuse_or_alloc_node __roan(*
this);
1400 if (__x._M_root() !=
nullptr)
1403 [&__roan](
const value_type& __cval)
1405 auto& __val =
const_cast<value_type&
>(__cval);
1408 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1409 _M_leftmost() = _S_minimum(_M_root());
1410 _M_rightmost() = _S_maximum(_M_root());
1411 _M_impl._M_node_count = __x._M_impl._M_node_count;
1417 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1418 typename _Compare,
typename _Alloc>
1419 template<
typename _Iterator>
1421 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1422 _M_assign_unique(_Iterator __first, _Iterator __last)
1424 _Reuse_or_alloc_node __roan(*
this);
1426 for (; __first != __last; ++__first)
1427 _M_insert_unique_(
end(), *__first, __roan);
1430 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1431 typename _Compare,
typename _Alloc>
1432 template<
typename _Iterator>
1434 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1435 _M_assign_equal(_Iterator __first, _Iterator __last)
1437 _Reuse_or_alloc_node __roan(*
this);
1439 for (; __first != __last; ++__first)
1440 _M_insert_equal_(
end(), *__first, __roan);
1444 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1445 typename _Compare,
typename _Alloc>
1446 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1447 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1448 operator=(
const _Rb_tree& __x)
1453 #if __cplusplus >= 201103L 1454 if (_Alloc_traits::_S_propagate_on_copy_assign())
1456 auto& __this_alloc = this->_M_get_Node_allocator();
1457 auto& __that_alloc = __x._M_get_Node_allocator();
1458 if (!_Alloc_traits::_S_always_equal()
1459 && __this_alloc != __that_alloc)
1464 std::__alloc_on_copy(__this_alloc, __that_alloc);
1469 _Reuse_or_alloc_node __roan(*
this);
1471 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1472 if (__x._M_root() != 0)
1474 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1475 _M_leftmost() = _S_minimum(_M_root());
1476 _M_rightmost() = _S_maximum(_M_root());
1477 _M_impl._M_node_count = __x._M_impl._M_node_count;
1484 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1485 typename _Compare,
typename _Alloc>
1486 #if __cplusplus >= 201103L 1487 template<
typename _Arg,
typename _NodeGen>
1489 template<
typename _NodeGen>
1491 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1492 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1493 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1494 #
if __cplusplus >= 201103L
1499 _NodeGen& __node_gen)
1501 bool __insert_left = (__x != 0 || __p == _M_end()
1502 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1505 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1507 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1508 this->_M_impl._M_header);
1509 ++_M_impl._M_node_count;
1510 return iterator(__z);
1513 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1514 typename _Compare,
typename _Alloc>
1515 #if __cplusplus >= 201103L 1516 template<
typename _Arg>
1518 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1519 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1520 #if __cplusplus >= 201103L 1521 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1523 _M_insert_lower(_Base_ptr __p,
const _Val& __v)
1526 bool __insert_left = (__p == _M_end()
1527 || !_M_impl._M_key_compare(_S_key(__p),
1528 _KeyOfValue()(__v)));
1530 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1532 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1533 this->_M_impl._M_header);
1534 ++_M_impl._M_node_count;
1535 return iterator(__z);
1538 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1539 typename _Compare,
typename _Alloc>
1540 #if __cplusplus >= 201103L 1541 template<
typename _Arg>
1543 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1544 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1545 #if __cplusplus >= 201103L 1546 _M_insert_equal_lower(_Arg&& __v)
1548 _M_insert_equal_lower(
const _Val& __v)
1551 _Link_type __x = _M_begin();
1552 _Base_ptr __y = _M_end();
1556 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1557 _S_left(__x) : _S_right(__x);
1559 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1562 template<
typename _Key,
typename _Val,
typename _KoV,
1563 typename _Compare,
typename _Alloc>
1564 template<
typename _NodeGen>
1565 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1566 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1567 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1570 _Link_type __top = _M_clone_node(__x, __node_gen);
1571 __top->_M_parent = __p;
1576 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1582 _Link_type __y = _M_clone_node(__x, __node_gen);
1584 __y->_M_parent = __p;
1586 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1594 __throw_exception_again;
1599 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1600 typename _Compare,
typename _Alloc>
1602 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1603 _M_erase(_Link_type __x)
1608 _M_erase(_S_right(__x));
1609 _Link_type __y = _S_left(__x);
1615 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1616 typename _Compare,
typename _Alloc>
1617 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1618 _Compare, _Alloc>::iterator
1619 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1620 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1624 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1625 __y = __x, __x = _S_left(__x);
1627 __x = _S_right(__x);
1628 return iterator(__y);
1631 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1632 typename _Compare,
typename _Alloc>
1633 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1634 _Compare, _Alloc>::const_iterator
1635 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1636 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1637 const _Key& __k)
const 1640 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1641 __y = __x, __x = _S_left(__x);
1643 __x = _S_right(__x);
1644 return const_iterator(__y);
1647 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1648 typename _Compare,
typename _Alloc>
1649 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1650 _Compare, _Alloc>::iterator
1651 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1652 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1656 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1657 __y = __x, __x = _S_left(__x);
1659 __x = _S_right(__x);
1660 return iterator(__y);
1663 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1664 typename _Compare,
typename _Alloc>
1665 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1666 _Compare, _Alloc>::const_iterator
1667 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1668 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1669 const _Key& __k)
const 1672 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1673 __y = __x, __x = _S_left(__x);
1675 __x = _S_right(__x);
1676 return const_iterator(__y);
1679 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1680 typename _Compare,
typename _Alloc>
1681 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1682 _Compare, _Alloc>::iterator,
1683 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1684 _Compare, _Alloc>::iterator>
1685 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1686 equal_range(
const _Key& __k)
1688 _Link_type __x = _M_begin();
1689 _Base_ptr __y = _M_end();
1692 if (_M_impl._M_key_compare(_S_key(__x), __k))
1693 __x = _S_right(__x);
1694 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1695 __y = __x, __x = _S_left(__x);
1698 _Link_type __xu(__x);
1699 _Base_ptr __yu(__y);
1700 __y = __x, __x = _S_left(__x);
1701 __xu = _S_right(__xu);
1702 return pair<iterator,
1703 iterator>(_M_lower_bound(__x, __y, __k),
1704 _M_upper_bound(__xu, __yu, __k));
1707 return pair<iterator, iterator>(iterator(__y),
1711 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1712 typename _Compare,
typename _Alloc>
1713 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1714 _Compare, _Alloc>::const_iterator,
1715 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1716 _Compare, _Alloc>::const_iterator>
1717 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1718 equal_range(
const _Key& __k)
const 1720 _Const_Link_type __x = _M_begin();
1721 _Const_Base_ptr __y = _M_end();
1724 if (_M_impl._M_key_compare(_S_key(__x), __k))
1725 __x = _S_right(__x);
1726 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1727 __y = __x, __x = _S_left(__x);
1730 _Const_Link_type __xu(__x);
1731 _Const_Base_ptr __yu(__y);
1732 __y = __x, __x = _S_left(__x);
1733 __xu = _S_right(__xu);
1734 return pair<const_iterator,
1735 const_iterator>(_M_lower_bound(__x, __y, __k),
1736 _M_upper_bound(__xu, __yu, __k));
1739 return pair<const_iterator, const_iterator>(const_iterator(__y),
1740 const_iterator(__y));
1743 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1744 typename _Compare,
typename _Alloc>
1746 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1748 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1752 if (__t._M_root() != 0)
1754 _M_root() = __t._M_root();
1755 _M_leftmost() = __t._M_leftmost();
1756 _M_rightmost() = __t._M_rightmost();
1757 _M_root()->_M_parent = _M_end();
1758 _M_impl._M_node_count = __t._M_impl._M_node_count;
1760 __t._M_impl._M_reset();
1763 else if (__t._M_root() == 0)
1765 __t._M_root() = _M_root();
1766 __t._M_leftmost() = _M_leftmost();
1767 __t._M_rightmost() = _M_rightmost();
1768 __t._M_root()->_M_parent = __t._M_end();
1769 __t._M_impl._M_node_count = _M_impl._M_node_count;
1775 std::swap(_M_root(),__t._M_root());
1776 std::swap(_M_leftmost(),__t._M_leftmost());
1777 std::swap(_M_rightmost(),__t._M_rightmost());
1779 _M_root()->_M_parent = _M_end();
1780 __t._M_root()->_M_parent = __t._M_end();
1781 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1784 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1786 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1787 __t._M_get_Node_allocator());
1790 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1791 typename _Compare,
typename _Alloc>
1792 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1793 _Compare, _Alloc>::_Base_ptr,
1794 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1795 _Compare, _Alloc>::_Base_ptr>
1796 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1797 _M_get_insert_unique_pos(
const key_type& __k)
1799 typedef pair<_Base_ptr, _Base_ptr> _Res;
1800 _Link_type __x = _M_begin();
1801 _Base_ptr __y = _M_end();
1806 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1807 __x = __comp ? _S_left(__x) : _S_right(__x);
1809 iterator __j = iterator(__y);
1813 return _Res(__x, __y);
1817 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1818 return _Res(__x, __y);
1819 return _Res(__j._M_node, 0);
1822 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1823 typename _Compare,
typename _Alloc>
1824 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1825 _Compare, _Alloc>::_Base_ptr,
1826 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1827 _Compare, _Alloc>::_Base_ptr>
1828 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1829 _M_get_insert_equal_pos(
const key_type& __k)
1831 typedef pair<_Base_ptr, _Base_ptr> _Res;
1832 _Link_type __x = _M_begin();
1833 _Base_ptr __y = _M_end();
1837 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1838 _S_left(__x) : _S_right(__x);
1840 return _Res(__x, __y);
1843 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1844 typename _Compare,
typename _Alloc>
1845 #if __cplusplus >= 201103L 1846 template<
typename _Arg>
1848 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1849 _Compare, _Alloc>::iterator,
bool>
1850 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1851 #if __cplusplus >= 201103L 1852 _M_insert_unique(_Arg&& __v)
1854 _M_insert_unique(
const _Val& __v)
1857 typedef pair<iterator, bool> _Res;
1858 pair<_Base_ptr, _Base_ptr> __res
1859 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1863 _Alloc_node __an(*
this);
1864 return _Res(_M_insert_(__res.first, __res.second,
1865 _GLIBCXX_FORWARD(_Arg, __v), __an),
1869 return _Res(iterator(__res.first),
false);
1872 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1873 typename _Compare,
typename _Alloc>
1874 #if __cplusplus >= 201103L 1875 template<
typename _Arg>
1877 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1878 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1879 #if __cplusplus >= 201103L 1880 _M_insert_equal(_Arg&& __v)
1882 _M_insert_equal(
const _Val& __v)
1885 pair<_Base_ptr, _Base_ptr> __res
1886 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1887 _Alloc_node __an(*
this);
1888 return _M_insert_(__res.first, __res.second,
1889 _GLIBCXX_FORWARD(_Arg, __v), __an);
1892 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1893 typename _Compare,
typename _Alloc>
1894 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1895 _Compare, _Alloc>::_Base_ptr,
1896 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1897 _Compare, _Alloc>::_Base_ptr>
1898 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1899 _M_get_insert_hint_unique_pos(const_iterator __position,
1900 const key_type& __k)
1902 iterator __pos = __position._M_const_cast();
1903 typedef pair<_Base_ptr, _Base_ptr> _Res;
1906 if (__pos._M_node == _M_end())
1909 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1910 return _Res(0, _M_rightmost());
1912 return _M_get_insert_unique_pos(__k);
1914 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1917 iterator __before = __pos;
1918 if (__pos._M_node == _M_leftmost())
1919 return _Res(_M_leftmost(), _M_leftmost());
1920 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1922 if (_S_right(__before._M_node) == 0)
1923 return _Res(0, __before._M_node);
1925 return _Res(__pos._M_node, __pos._M_node);
1928 return _M_get_insert_unique_pos(__k);
1930 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1933 iterator __after = __pos;
1934 if (__pos._M_node == _M_rightmost())
1935 return _Res(0, _M_rightmost());
1936 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1938 if (_S_right(__pos._M_node) == 0)
1939 return _Res(0, __pos._M_node);
1941 return _Res(__after._M_node, __after._M_node);
1944 return _M_get_insert_unique_pos(__k);
1948 return _Res(__pos._M_node, 0);
1951 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1952 typename _Compare,
typename _Alloc>
1953 #if __cplusplus >= 201103L 1954 template<
typename _Arg,
typename _NodeGen>
1956 template<
typename _NodeGen>
1958 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1959 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1960 _M_insert_unique_(const_iterator __position,
1961 #
if __cplusplus >= 201103L
1966 _NodeGen& __node_gen)
1968 pair<_Base_ptr, _Base_ptr> __res
1969 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1972 return _M_insert_(__res.first, __res.second,
1973 _GLIBCXX_FORWARD(_Arg, __v),
1975 return iterator(__res.first);
1978 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1979 typename _Compare,
typename _Alloc>
1980 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1981 _Compare, _Alloc>::_Base_ptr,
1982 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1983 _Compare, _Alloc>::_Base_ptr>
1984 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1985 _M_get_insert_hint_equal_pos(const_iterator __position,
const key_type& __k)
1987 iterator __pos = __position._M_const_cast();
1988 typedef pair<_Base_ptr, _Base_ptr> _Res;
1991 if (__pos._M_node == _M_end())
1994 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1995 return _Res(0, _M_rightmost());
1997 return _M_get_insert_equal_pos(__k);
1999 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2002 iterator __before = __pos;
2003 if (__pos._M_node == _M_leftmost())
2004 return _Res(_M_leftmost(), _M_leftmost());
2005 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2007 if (_S_right(__before._M_node) == 0)
2008 return _Res(0, __before._M_node);
2010 return _Res(__pos._M_node, __pos._M_node);
2013 return _M_get_insert_equal_pos(__k);
2018 iterator __after = __pos;
2019 if (__pos._M_node == _M_rightmost())
2020 return _Res(0, _M_rightmost());
2021 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2023 if (_S_right(__pos._M_node) == 0)
2024 return _Res(0, __pos._M_node);
2026 return _Res(__after._M_node, __after._M_node);
2033 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2034 typename _Compare,
typename _Alloc>
2035 #if __cplusplus >= 201103L 2036 template<
typename _Arg,
typename _NodeGen>
2038 template<
typename _NodeGen>
2040 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2041 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2042 _M_insert_equal_(const_iterator __position,
2043 #
if __cplusplus >= 201103L
2048 _NodeGen& __node_gen)
2050 pair<_Base_ptr, _Base_ptr> __res
2051 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2054 return _M_insert_(__res.first, __res.second,
2055 _GLIBCXX_FORWARD(_Arg, __v),
2058 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2061 #if __cplusplus >= 201103L 2062 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2063 typename _Compare,
typename _Alloc>
2064 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2065 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2066 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2068 bool __insert_left = (__x != 0 || __p == _M_end()
2069 || _M_impl._M_key_compare(_S_key(__z),
2072 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2073 this->_M_impl._M_header);
2074 ++_M_impl._M_node_count;
2075 return iterator(__z);
2078 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2079 typename _Compare,
typename _Alloc>
2080 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2081 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2082 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2084 bool __insert_left = (__p == _M_end()
2085 || !_M_impl._M_key_compare(_S_key(__p),
2088 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2089 this->_M_impl._M_header);
2090 ++_M_impl._M_node_count;
2091 return iterator(__z);
2094 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2095 typename _Compare,
typename _Alloc>
2096 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2097 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2098 _M_insert_equal_lower_node(_Link_type __z)
2100 _Link_type __x = _M_begin();
2101 _Base_ptr __y = _M_end();
2105 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2106 _S_left(__x) : _S_right(__x);
2108 return _M_insert_lower_node(__y, __z);
2111 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2112 typename _Compare,
typename _Alloc>
2113 template<
typename... _Args>
2114 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2115 _Compare, _Alloc>::iterator,
bool>
2116 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2117 _M_emplace_unique(_Args&&... __args)
2119 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2123 typedef pair<iterator, bool> _Res;
2124 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2126 return _Res(_M_insert_node(__res.first, __res.second, __z),
true);
2129 return _Res(iterator(__res.first),
false);
2134 __throw_exception_again;
2138 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2139 typename _Compare,
typename _Alloc>
2140 template<
typename... _Args>
2141 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2142 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2143 _M_emplace_equal(_Args&&... __args)
2145 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2149 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2150 return _M_insert_node(__res.first, __res.second, __z);
2155 __throw_exception_again;
2159 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2160 typename _Compare,
typename _Alloc>
2161 template<
typename... _Args>
2162 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2163 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2164 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2166 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2170 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2173 return _M_insert_node(__res.first, __res.second, __z);
2176 return iterator(__res.first);
2181 __throw_exception_again;
2185 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2186 typename _Compare,
typename _Alloc>
2187 template<
typename... _Args>
2188 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2189 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2190 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2192 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2196 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2199 return _M_insert_node(__res.first, __res.second, __z);
2201 return _M_insert_equal_lower_node(__z);
2206 __throw_exception_again;
2211 template<
typename _Key,
typename _Val,
typename _KoV,
2212 typename _Cmp,
typename _Alloc>
2215 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2216 _M_insert_unique(_II __first, _II __last)
2218 _Alloc_node __an(*
this);
2219 for (; __first != __last; ++__first)
2220 _M_insert_unique_(
end(), *__first, __an);
2223 template<
typename _Key,
typename _Val,
typename _KoV,
2224 typename _Cmp,
typename _Alloc>
2227 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2228 _M_insert_equal(_II __first, _II __last)
2230 _Alloc_node __an(*
this);
2231 for (; __first != __last; ++__first)
2232 _M_insert_equal_(
end(), *__first, __an);
2235 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2236 typename _Compare,
typename _Alloc>
2238 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2239 _M_erase_aux(const_iterator __position)
2242 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2243 (const_cast<_Base_ptr>(__position._M_node),
2244 this->_M_impl._M_header));
2246 --_M_impl._M_node_count;
2249 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2250 typename _Compare,
typename _Alloc>
2252 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2253 _M_erase_aux(const_iterator __first, const_iterator __last)
2255 if (__first ==
begin() && __last ==
end())
2258 while (__first != __last)
2262 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2263 typename _Compare,
typename _Alloc>
2264 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2265 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2266 erase(
const _Key& __x)
2268 pair<iterator, iterator> __p = equal_range(__x);
2269 const size_type __old_size =
size();
2270 erase(__p.first, __p.second);
2271 return __old_size -
size();
2274 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2275 typename _Compare,
typename _Alloc>
2277 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2278 erase(
const _Key* __first,
const _Key* __last)
2280 while (__first != __last)
2284 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2285 typename _Compare,
typename _Alloc>
2286 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2287 _Compare, _Alloc>::iterator
2288 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2289 find(
const _Key& __k)
2291 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2292 return (__j ==
end()
2293 || _M_impl._M_key_compare(__k,
2294 _S_key(__j._M_node))) ?
end() : __j;
2297 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2298 typename _Compare,
typename _Alloc>
2299 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2300 _Compare, _Alloc>::const_iterator
2301 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2302 find(
const _Key& __k)
const 2304 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2305 return (__j ==
end()
2306 || _M_impl._M_key_compare(__k,
2307 _S_key(__j._M_node))) ?
end() : __j;
2310 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2311 typename _Compare,
typename _Alloc>
2312 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2313 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2314 count(
const _Key& __k)
const 2316 pair<const_iterator, const_iterator> __p = equal_range(__k);
2321 _GLIBCXX_PURE
unsigned int 2322 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
2323 const _Rb_tree_node_base* __root)
throw ();
2325 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2326 typename _Compare,
typename _Alloc>
2328 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const 2330 if (_M_impl._M_node_count == 0 ||
begin() ==
end())
2331 return _M_impl._M_node_count == 0 &&
begin() ==
end()
2332 && this->_M_impl._M_header._M_left == _M_end()
2333 && this->_M_impl._M_header._M_right == _M_end();
2335 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2336 for (const_iterator __it =
begin(); __it !=
end(); ++__it)
2338 _Const_Link_type __x =
static_cast<_Const_Link_type
>(__it._M_node);
2339 _Const_Link_type __L = _S_left(__x);
2340 _Const_Link_type __R = _S_right(__x);
2342 if (__x->_M_color == _S_red)
2343 if ((__L && __L->_M_color == _S_red)
2344 || (__R && __R->_M_color == _S_red))
2347 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2349 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2352 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2356 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2358 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2363 _GLIBCXX_END_NAMESPACE_VERSION
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Uniform interface to C++98 and C++11 allocators.
ISO C++ entities toplevel namespace is std.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
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.
iterator end()
As per Table mumble.
auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
size_type size() const
As per Table mumble.
bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.
iterator begin()
As per Table mumble.
auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.