61 #pragma GCC system_header 68 #if __cplusplus >= 201103L 71 #if __cplusplus > 201402L 75 namespace std _GLIBCXX_VISIBILITY(default)
77 _GLIBCXX_BEGIN_NAMESPACE_VERSION
79 #if __cplusplus > 201103L 80 # define __cpp_lib_generic_associative_lookup 201304 99 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
101 struct _Rb_tree_node_base
103 typedef _Rb_tree_node_base* _Base_ptr;
104 typedef const _Rb_tree_node_base* _Const_Base_ptr;
106 _Rb_tree_color _M_color;
112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
114 while (__x->_M_left != 0) __x = __x->_M_left;
118 static _Const_Base_ptr
119 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
121 while (__x->_M_left != 0) __x = __x->_M_left;
126 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
128 while (__x->_M_right != 0) __x = __x->_M_right;
132 static _Const_Base_ptr
133 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
135 while (__x->_M_right != 0) __x = __x->_M_right;
140 template<
typename _Val>
141 struct _Rb_tree_node :
public _Rb_tree_node_base
143 typedef _Rb_tree_node<_Val>* _Link_type;
145 #if __cplusplus < 201103L 156 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
160 {
return _M_storage._M_ptr(); }
164 {
return _M_storage._M_ptr(); }
168 _GLIBCXX_PURE _Rb_tree_node_base*
169 _Rb_tree_increment(_Rb_tree_node_base* __x)
throw ();
171 _GLIBCXX_PURE
const _Rb_tree_node_base*
172 _Rb_tree_increment(
const _Rb_tree_node_base* __x)
throw ();
174 _GLIBCXX_PURE _Rb_tree_node_base*
175 _Rb_tree_decrement(_Rb_tree_node_base* __x)
throw ();
177 _GLIBCXX_PURE
const _Rb_tree_node_base*
178 _Rb_tree_decrement(
const _Rb_tree_node_base* __x)
throw ();
180 template<
typename _Tp>
181 struct _Rb_tree_iterator
183 typedef _Tp value_type;
184 typedef _Tp& reference;
185 typedef _Tp* pointer;
187 typedef bidirectional_iterator_tag iterator_category;
188 typedef ptrdiff_t difference_type;
190 typedef _Rb_tree_iterator<_Tp> _Self;
191 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
192 typedef _Rb_tree_node<_Tp>* _Link_type;
194 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
198 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
203 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
206 operator->() const _GLIBCXX_NOEXCEPT
207 {
return static_cast<_Link_type
> (_M_node)->_M_valptr(); }
210 operator++() _GLIBCXX_NOEXCEPT
212 _M_node = _Rb_tree_increment(_M_node);
217 operator++(
int) _GLIBCXX_NOEXCEPT
220 _M_node = _Rb_tree_increment(_M_node);
225 operator--() _GLIBCXX_NOEXCEPT
227 _M_node = _Rb_tree_decrement(_M_node);
232 operator--(
int) _GLIBCXX_NOEXCEPT
235 _M_node = _Rb_tree_decrement(_M_node);
240 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
241 {
return _M_node == __x._M_node; }
244 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
245 {
return _M_node != __x._M_node; }
250 template<
typename _Tp>
251 struct _Rb_tree_const_iterator
253 typedef _Tp value_type;
254 typedef const _Tp& reference;
255 typedef const _Tp* pointer;
257 typedef _Rb_tree_iterator<_Tp> iterator;
259 typedef bidirectional_iterator_tag iterator_category;
260 typedef ptrdiff_t difference_type;
262 typedef _Rb_tree_const_iterator<_Tp> _Self;
263 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
264 typedef const _Rb_tree_node<_Tp>* _Link_type;
266 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
270 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
273 _Rb_tree_const_iterator(
const iterator& __it) _GLIBCXX_NOEXCEPT
274 : _M_node(__it._M_node) { }
277 _M_const_cast() const _GLIBCXX_NOEXCEPT
278 {
return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
282 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
285 operator->() const _GLIBCXX_NOEXCEPT
286 {
return static_cast<_Link_type
>(_M_node)->_M_valptr(); }
289 operator++() _GLIBCXX_NOEXCEPT
291 _M_node = _Rb_tree_increment(_M_node);
296 operator++(
int) _GLIBCXX_NOEXCEPT
299 _M_node = _Rb_tree_increment(_M_node);
304 operator--() _GLIBCXX_NOEXCEPT
306 _M_node = _Rb_tree_decrement(_M_node);
311 operator--(
int) _GLIBCXX_NOEXCEPT
314 _M_node = _Rb_tree_decrement(_M_node);
319 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
320 {
return _M_node == __x._M_node; }
323 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
324 {
return _M_node != __x._M_node; }
329 template<
typename _Val>
331 operator==(
const _Rb_tree_iterator<_Val>& __x,
332 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
333 {
return __x._M_node == __y._M_node; }
335 template<
typename _Val>
337 operator!=(
const _Rb_tree_iterator<_Val>& __x,
338 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
339 {
return __x._M_node != __y._M_node; }
342 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
343 _Rb_tree_node_base* __x,
344 _Rb_tree_node_base* __p,
345 _Rb_tree_node_base& __header)
throw ();
348 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
349 _Rb_tree_node_base& __header)
throw ();
351 #if __cplusplus > 201103L 352 template<
typename _Cmp,
typename _SfinaeType,
typename = __
void_t<>>
353 struct __has_is_transparent
356 template<
typename _Cmp,
typename _SfinaeType>
357 struct __has_is_transparent<_Cmp, _SfinaeType,
358 __void_t<typename _Cmp::is_transparent>>
359 {
typedef void type; };
362 #if __cplusplus > 201402L 363 template<
typename _Tree1,
typename _Cmp2>
364 struct _Rb_tree_merge_helper { };
367 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
368 typename _Compare,
typename _Alloc = allocator<_Val> >
372 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
377 typedef _Rb_tree_node_base* _Base_ptr;
378 typedef const _Rb_tree_node_base* _Const_Base_ptr;
379 typedef _Rb_tree_node<_Val>* _Link_type;
380 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
385 struct _Reuse_or_alloc_node
387 _Reuse_or_alloc_node(_Rb_tree& __t)
388 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
392 _M_root->_M_parent = 0;
394 if (_M_nodes->_M_left)
395 _M_nodes = _M_nodes->_M_left;
401 #if __cplusplus >= 201103L 402 _Reuse_or_alloc_node(
const _Reuse_or_alloc_node&) =
delete;
405 ~_Reuse_or_alloc_node()
406 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
408 template<
typename _Arg>
410 #if __cplusplus < 201103L 411 operator()(
const _Arg& __arg)
413 operator()(_Arg&& __arg)
416 _Link_type __node =
static_cast<_Link_type
>(_M_extract());
419 _M_t._M_destroy_node(__node);
420 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
424 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
434 _Base_ptr __node = _M_nodes;
435 _M_nodes = _M_nodes->_M_parent;
438 if (_M_nodes->_M_right == __node)
440 _M_nodes->_M_right = 0;
442 if (_M_nodes->_M_left)
444 _M_nodes = _M_nodes->_M_left;
446 while (_M_nodes->_M_right)
447 _M_nodes = _M_nodes->_M_right;
449 if (_M_nodes->_M_left)
450 _M_nodes = _M_nodes->_M_left;
454 _M_nodes->_M_left = 0;
471 _Alloc_node(_Rb_tree& __t)
474 template<
typename _Arg>
476 #if __cplusplus < 201103L 477 operator()(
const _Arg& __arg)
const 479 operator()(_Arg&& __arg) const
481 {
return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
488 typedef _Key key_type;
489 typedef _Val value_type;
490 typedef value_type* pointer;
491 typedef const value_type* const_pointer;
492 typedef value_type& reference;
493 typedef const value_type& const_reference;
494 typedef size_t size_type;
495 typedef ptrdiff_t difference_type;
496 typedef _Alloc allocator_type;
499 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
500 {
return *
static_cast<_Node_allocator*
>(&this->_M_impl); }
502 const _Node_allocator&
503 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
504 {
return *
static_cast<const _Node_allocator*
>(&this->_M_impl); }
507 get_allocator() const _GLIBCXX_NOEXCEPT
508 {
return allocator_type(_M_get_Node_allocator()); }
513 {
return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
516 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
517 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
519 #if __cplusplus < 201103L 521 _M_construct_node(_Link_type __node,
const value_type& __x)
524 { get_allocator().construct(__node->_M_valptr(), __x); }
528 __throw_exception_again;
533 _M_create_node(
const value_type& __x)
535 _Link_type __tmp = _M_get_node();
536 _M_construct_node(__tmp, __x);
541 _M_destroy_node(_Link_type __p)
542 { get_allocator().destroy(__p->_M_valptr()); }
544 template<
typename... _Args>
546 _M_construct_node(_Link_type __node, _Args&&... __args)
550 ::new(__node) _Rb_tree_node<_Val>;
551 _Alloc_traits::construct(_M_get_Node_allocator(),
557 __node->~_Rb_tree_node<_Val>();
559 __throw_exception_again;
563 template<
typename... _Args>
565 _M_create_node(_Args&&... __args)
567 _Link_type __tmp = _M_get_node();
568 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
573 _M_destroy_node(_Link_type __p) noexcept
575 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
576 __p->~_Rb_tree_node<_Val>();
581 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
583 _M_destroy_node(__p);
587 template<
typename _NodeGen>
589 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
591 _Link_type __tmp = __node_gen(*__x->_M_valptr());
592 __tmp->_M_color = __x->_M_color;
600 template<
typename _Key_compare,
601 bool = __is_pod(_Key_compare)>
602 struct _Rb_tree_impl :
public _Node_allocator
604 _Key_compare _M_key_compare;
605 _Rb_tree_node_base _M_header;
606 size_type _M_node_count;
609 _GLIBCXX_NOEXCEPT_IF(
610 is_nothrow_default_constructible<_Node_allocator>::value
611 && is_nothrow_default_constructible<_Key_compare>::value)
612 : _Node_allocator(), _M_key_compare(), _M_header(),
616 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
617 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
621 #if __cplusplus >= 201103L 622 _Rb_tree_impl(
const _Key_compare& __comp, _Node_allocator&& __a)
623 : _Node_allocator(
std::move(__a)), _M_key_compare(__comp),
624 _M_header(), _M_node_count(0)
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;
634 this->_M_node_count = 0;
641 this->_M_header._M_color = _S_red;
642 this->_M_header._M_parent = 0;
643 this->_M_header._M_left = &this->_M_header;
644 this->_M_header._M_right = &this->_M_header;
648 _Rb_tree_impl<_Compare> _M_impl;
652 _M_root() _GLIBCXX_NOEXCEPT
653 {
return this->_M_impl._M_header._M_parent; }
656 _M_root() const _GLIBCXX_NOEXCEPT
657 {
return this->_M_impl._M_header._M_parent; }
660 _M_leftmost() _GLIBCXX_NOEXCEPT
661 {
return this->_M_impl._M_header._M_left; }
664 _M_leftmost() const _GLIBCXX_NOEXCEPT
665 {
return this->_M_impl._M_header._M_left; }
668 _M_rightmost() _GLIBCXX_NOEXCEPT
669 {
return this->_M_impl._M_header._M_right; }
672 _M_rightmost() const _GLIBCXX_NOEXCEPT
673 {
return this->_M_impl._M_header._M_right; }
676 _M_begin() _GLIBCXX_NOEXCEPT
677 {
return static_cast<_Link_type
>(this->_M_impl._M_header._M_parent); }
680 _M_begin() const _GLIBCXX_NOEXCEPT
682 return static_cast<_Const_Link_type
> 683 (this->_M_impl._M_header._M_parent);
687 _M_end() _GLIBCXX_NOEXCEPT
688 {
return &this->_M_impl._M_header; }
691 _M_end() const _GLIBCXX_NOEXCEPT
692 {
return &this->_M_impl._M_header; }
694 static const_reference
695 _S_value(_Const_Link_type __x)
696 {
return *__x->_M_valptr(); }
699 _S_key(_Const_Link_type __x)
700 {
return _KeyOfValue()(_S_value(__x)); }
703 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
704 {
return static_cast<_Link_type
>(__x->_M_left); }
706 static _Const_Link_type
707 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
708 {
return static_cast<_Const_Link_type
>(__x->_M_left); }
711 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
712 {
return static_cast<_Link_type
>(__x->_M_right); }
714 static _Const_Link_type
715 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
716 {
return static_cast<_Const_Link_type
>(__x->_M_right); }
718 static const_reference
719 _S_value(_Const_Base_ptr __x)
720 {
return *
static_cast<_Const_Link_type
>(__x)->_M_valptr(); }
723 _S_key(_Const_Base_ptr __x)
724 {
return _KeyOfValue()(_S_value(__x)); }
727 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
728 {
return _Rb_tree_node_base::_S_minimum(__x); }
730 static _Const_Base_ptr
731 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
732 {
return _Rb_tree_node_base::_S_minimum(__x); }
735 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
736 {
return _Rb_tree_node_base::_S_maximum(__x); }
738 static _Const_Base_ptr
739 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
740 {
return _Rb_tree_node_base::_S_maximum(__x); }
743 typedef _Rb_tree_iterator<value_type> iterator;
744 typedef _Rb_tree_const_iterator<value_type> const_iterator;
749 #if __cplusplus > 201402L 750 using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
751 using insert_return_type = _Node_insert_return<iterator, node_type>;
754 pair<_Base_ptr, _Base_ptr>
755 _M_get_insert_unique_pos(
const key_type& __k);
757 pair<_Base_ptr, _Base_ptr>
758 _M_get_insert_equal_pos(
const key_type& __k);
760 pair<_Base_ptr, _Base_ptr>
761 _M_get_insert_hint_unique_pos(const_iterator __pos,
762 const key_type& __k);
764 pair<_Base_ptr, _Base_ptr>
765 _M_get_insert_hint_equal_pos(const_iterator __pos,
766 const key_type& __k);
769 #if __cplusplus >= 201103L 770 template<
typename _Arg,
typename _NodeGen>
772 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
775 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
777 template<
typename _Arg>
779 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
781 template<
typename _Arg>
783 _M_insert_equal_lower(_Arg&& __x);
786 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
789 _M_insert_equal_lower_node(_Link_type __z);
791 template<
typename _NodeGen>
793 _M_insert_(_Base_ptr __x, _Base_ptr __y,
794 const value_type& __v, _NodeGen&);
799 _M_insert_lower(_Base_ptr __y,
const value_type& __v);
802 _M_insert_equal_lower(
const value_type& __x);
805 template<
typename _NodeGen>
807 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
810 _M_copy(_Const_Link_type __x, _Base_ptr __p)
812 _Alloc_node __an(*
this);
813 return _M_copy(__x, __p, __an);
817 _M_erase(_Link_type __x);
820 _M_lower_bound(_Link_type __x, _Base_ptr __y,
824 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
825 const _Key& __k)
const;
828 _M_upper_bound(_Link_type __x, _Base_ptr __y,
832 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
833 const _Key& __k)
const;
837 #if __cplusplus < 201103L 840 _Rb_tree() =
default;
843 _Rb_tree(
const _Compare& __comp,
844 const allocator_type& __a = allocator_type())
845 : _M_impl(__comp, _Node_allocator(__a)) { }
847 _Rb_tree(
const _Rb_tree& __x)
848 : _M_impl(__x._M_impl._M_key_compare,
849 _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
851 if (__x._M_root() != 0)
853 _M_root() = _M_copy(__x._M_begin(), _M_end());
854 _M_leftmost() = _S_minimum(_M_root());
855 _M_rightmost() = _S_maximum(_M_root());
856 _M_impl._M_node_count = __x._M_impl._M_node_count;
860 #if __cplusplus >= 201103L 861 _Rb_tree(
const allocator_type& __a)
862 : _M_impl(_Compare(), _Node_allocator(__a))
865 _Rb_tree(
const _Rb_tree& __x,
const allocator_type& __a)
866 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
868 if (__x._M_root() !=
nullptr)
870 _M_root() = _M_copy(__x._M_begin(), _M_end());
871 _M_leftmost() = _S_minimum(_M_root());
872 _M_rightmost() = _S_maximum(_M_root());
873 _M_impl._M_node_count = __x._M_impl._M_node_count;
877 _Rb_tree(_Rb_tree&& __x)
878 : _M_impl(__x._M_impl._M_key_compare,
879 std::move(__x._M_get_Node_allocator()))
881 if (__x._M_root() != 0)
885 _Rb_tree(_Rb_tree&& __x,
const allocator_type& __a)
886 : _Rb_tree(
std::move(__x), _Node_allocator(__a))
889 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
892 ~_Rb_tree() _GLIBCXX_NOEXCEPT
893 { _M_erase(_M_begin()); }
896 operator=(
const _Rb_tree& __x);
901 {
return _M_impl._M_key_compare; }
904 begin() _GLIBCXX_NOEXCEPT
905 {
return iterator(this->_M_impl._M_header._M_left); }
908 begin() const _GLIBCXX_NOEXCEPT
909 {
return const_iterator(this->_M_impl._M_header._M_left); }
912 end() _GLIBCXX_NOEXCEPT
913 {
return iterator(&this->_M_impl._M_header); }
916 end() const _GLIBCXX_NOEXCEPT
917 {
return const_iterator(&this->_M_impl._M_header); }
920 rbegin() _GLIBCXX_NOEXCEPT
921 {
return reverse_iterator(
end()); }
923 const_reverse_iterator
924 rbegin() const _GLIBCXX_NOEXCEPT
925 {
return const_reverse_iterator(
end()); }
928 rend() _GLIBCXX_NOEXCEPT
929 {
return reverse_iterator(
begin()); }
931 const_reverse_iterator
932 rend() const _GLIBCXX_NOEXCEPT
933 {
return const_reverse_iterator(
begin()); }
936 empty() const _GLIBCXX_NOEXCEPT
937 {
return _M_impl._M_node_count == 0; }
940 size() const _GLIBCXX_NOEXCEPT
941 {
return _M_impl._M_node_count; }
944 max_size() const _GLIBCXX_NOEXCEPT
945 {
return _Alloc_traits::max_size(_M_get_Node_allocator()); }
949 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
952 #if __cplusplus >= 201103L 953 template<
typename _Arg>
955 _M_insert_unique(_Arg&& __x);
957 template<
typename _Arg>
959 _M_insert_equal(_Arg&& __x);
961 template<
typename _Arg,
typename _NodeGen>
963 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
965 template<
typename _Arg>
967 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
969 _Alloc_node __an(*
this);
970 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
973 template<
typename _Arg,
typename _NodeGen>
975 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
977 template<
typename _Arg>
979 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
981 _Alloc_node __an(*
this);
982 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
985 template<
typename... _Args>
987 _M_emplace_unique(_Args&&... __args);
989 template<
typename... _Args>
991 _M_emplace_equal(_Args&&... __args);
993 template<
typename... _Args>
995 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
997 template<
typename... _Args>
999 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1001 pair<iterator, bool>
1002 _M_insert_unique(
const value_type& __x);
1005 _M_insert_equal(
const value_type& __x);
1007 template<
typename _NodeGen>
1009 _M_insert_unique_(const_iterator __pos,
const value_type& __x,
1013 _M_insert_unique_(const_iterator __pos,
const value_type& __x)
1015 _Alloc_node __an(*
this);
1016 return _M_insert_unique_(__pos, __x, __an);
1019 template<
typename _NodeGen>
1021 _M_insert_equal_(const_iterator __pos,
const value_type& __x,
1024 _M_insert_equal_(const_iterator __pos,
const value_type& __x)
1026 _Alloc_node __an(*
this);
1027 return _M_insert_equal_(__pos, __x, __an);
1031 template<
typename _InputIterator>
1033 _M_insert_unique(_InputIterator __first, _InputIterator __last);
1035 template<
typename _InputIterator>
1037 _M_insert_equal(_InputIterator __first, _InputIterator __last);
1041 _M_erase_aux(const_iterator __position);
1044 _M_erase_aux(const_iterator __first, const_iterator __last);
1047 #if __cplusplus >= 201103L 1050 _GLIBCXX_ABI_TAG_CXX11
1052 erase(const_iterator __position)
1054 const_iterator __result = __position;
1056 _M_erase_aux(__position);
1057 return __result._M_const_cast();
1061 _GLIBCXX_ABI_TAG_CXX11
1063 erase(iterator __position)
1065 iterator __result = __position;
1067 _M_erase_aux(__position);
1072 erase(iterator __position)
1073 { _M_erase_aux(__position); }
1076 erase(const_iterator __position)
1077 { _M_erase_aux(__position); }
1080 erase(
const key_type& __x);
1082 #if __cplusplus >= 201103L 1085 _GLIBCXX_ABI_TAG_CXX11
1087 erase(const_iterator __first, const_iterator __last)
1089 _M_erase_aux(__first, __last);
1090 return __last._M_const_cast();
1094 erase(iterator __first, iterator __last)
1095 { _M_erase_aux(__first, __last); }
1098 erase(const_iterator __first, const_iterator __last)
1099 { _M_erase_aux(__first, __last); }
1102 erase(
const key_type* __first,
const key_type* __last);
1105 clear() _GLIBCXX_NOEXCEPT
1107 _M_erase(_M_begin());
1113 find(
const key_type& __k);
1116 find(
const key_type& __k)
const;
1119 count(
const key_type& __k)
const;
1122 lower_bound(
const key_type& __k)
1123 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1126 lower_bound(
const key_type& __k)
const 1127 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1130 upper_bound(
const key_type& __k)
1131 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1134 upper_bound(
const key_type& __k)
const 1135 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1137 pair<iterator, iterator>
1138 equal_range(
const key_type& __k);
1140 pair<const_iterator, const_iterator>
1141 equal_range(
const key_type& __k)
const;
1143 #if __cplusplus > 201103L 1144 template<
typename _Kt,
1146 typename __has_is_transparent<_Compare, _Kt>::type>
1148 _M_find_tr(
const _Kt& __k)
1150 const _Rb_tree* __const_this =
this;
1151 return __const_this->_M_find_tr(__k)._M_const_cast();
1154 template<
typename _Kt,
1156 typename __has_is_transparent<_Compare, _Kt>::type>
1158 _M_find_tr(
const _Kt& __k)
const 1160 auto __j = _M_lower_bound_tr(__k);
1161 if (__j !=
end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1166 template<
typename _Kt,
1168 typename __has_is_transparent<_Compare, _Kt>::type>
1170 _M_count_tr(
const _Kt& __k)
const 1172 auto __p = _M_equal_range_tr(__k);
1176 template<
typename _Kt,
1178 typename __has_is_transparent<_Compare, _Kt>::type>
1180 _M_lower_bound_tr(
const _Kt& __k)
1182 const _Rb_tree* __const_this =
this;
1183 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1186 template<
typename _Kt,
1188 typename __has_is_transparent<_Compare, _Kt>::type>
1190 _M_lower_bound_tr(
const _Kt& __k)
const 1192 auto __x = _M_begin();
1193 auto __y = _M_end();
1195 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1201 __x = _S_right(__x);
1202 return const_iterator(__y);
1205 template<
typename _Kt,
1207 typename __has_is_transparent<_Compare, _Kt>::type>
1209 _M_upper_bound_tr(
const _Kt& __k)
1211 const _Rb_tree* __const_this =
this;
1212 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1215 template<
typename _Kt,
1217 typename __has_is_transparent<_Compare, _Kt>::type>
1219 _M_upper_bound_tr(
const _Kt& __k)
const 1221 auto __x = _M_begin();
1222 auto __y = _M_end();
1224 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1230 __x = _S_right(__x);
1231 return const_iterator(__y);
1234 template<
typename _Kt,
1236 typename __has_is_transparent<_Compare, _Kt>::type>
1237 pair<iterator, iterator>
1238 _M_equal_range_tr(
const _Kt& __k)
1240 const _Rb_tree* __const_this =
this;
1241 auto __ret = __const_this->_M_equal_range_tr(__k);
1242 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1245 template<
typename _Kt,
1247 typename __has_is_transparent<_Compare, _Kt>::type>
1248 pair<const_iterator, const_iterator>
1249 _M_equal_range_tr(
const _Kt& __k)
const 1251 auto __low = _M_lower_bound_tr(__k);
1252 auto __high = __low;
1253 auto& __cmp = _M_impl._M_key_compare;
1254 while (__high !=
end() && !__cmp(__k, _S_key(__high._M_node)))
1256 return { __low, __high };
1262 __rb_verify()
const;
1264 #if __cplusplus >= 201103L 1266 operator=(_Rb_tree&&)
1267 noexcept(_Alloc_traits::_S_nothrow_move()
1268 && is_nothrow_move_assignable<_Compare>::value);
1270 template<typename _Iterator>
1272 _M_assign_unique(_Iterator, _Iterator);
1274 template<typename _Iterator>
1276 _M_assign_equal(_Iterator, _Iterator);
1290 _M_move_assign(_Rb_tree&,
std::true_type);
1295 _M_move_assign(_Rb_tree&,
std::false_type);
1298 #if __cplusplus > 201402L 1302 _M_reinsert_node_unique(node_type&& __nh)
1304 insert_return_type __ret;
1306 __ret.position =
end();
1309 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1311 auto __res = _M_get_insert_unique_pos(__nh._M_key());
1315 = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1316 __nh._M_ptr =
nullptr;
1317 __ret.inserted =
true;
1321 __ret.node = std::move(__nh);
1322 __ret.position = iterator(__res.first);
1323 __ret.inserted =
false;
1331 _M_reinsert_node_equal(node_type&& __nh)
1338 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1339 auto __res = _M_get_insert_equal_pos(__nh._M_key());
1341 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1343 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1344 __nh._M_ptr =
nullptr;
1351 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1358 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1359 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1362 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1363 __nh._M_ptr =
nullptr;
1366 __ret = iterator(__res.first);
1373 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1380 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1381 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1383 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1385 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1386 __nh._M_ptr =
nullptr;
1393 extract(const_iterator __pos)
1395 auto __ptr = _Rb_tree_rebalance_for_erase(
1396 __pos._M_const_cast()._M_node, _M_impl._M_header);
1397 --_M_impl._M_node_count;
1398 return {
static_cast<_Link_type
>(__ptr), _M_get_Node_allocator() };
1403 extract(
const key_type& __k)
1406 auto __pos = find(__k);
1408 __nh = extract(const_iterator(__pos));
1412 template<
typename _Compare2>
1413 using _Compatible_tree
1414 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1416 template<
typename,
typename>
1417 friend class _Rb_tree_merge_helper;
1420 template<
typename _Compare2>
1422 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1424 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1425 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1428 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1431 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1432 auto __ptr = _Rb_tree_rebalance_for_erase(
1433 __pos._M_node, __src_impl._M_header);
1434 --__src_impl._M_node_count;
1435 _M_insert_node(__res.first, __res.second,
1436 static_cast<_Link_type>(__ptr));
1442 template<
typename _Compare2>
1444 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1446 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1447 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1450 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1453 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1454 auto __ptr = _Rb_tree_rebalance_for_erase(
1455 __pos._M_node, __src_impl._M_header);
1456 --__src_impl._M_node_count;
1457 _M_insert_node(__res.first, __res.second,
1458 static_cast<_Link_type>(__ptr));
1465 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1466 typename _Compare,
typename _Alloc>
1468 operator==(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1469 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1471 return __x.size() == __y.size()
1472 &&
std::equal(__x.begin(), __x.end(), __y.begin());
1475 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1476 typename _Compare,
typename _Alloc>
1478 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1479 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1482 __y.begin(), __y.end());
1485 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1486 typename _Compare,
typename _Alloc>
1488 operator!=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1489 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1490 {
return !(__x == __y); }
1492 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1493 typename _Compare,
typename _Alloc>
1495 operator>(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1496 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1497 {
return __y < __x; }
1499 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1500 typename _Compare,
typename _Alloc>
1502 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1503 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1504 {
return !(__y < __x); }
1506 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1507 typename _Compare,
typename _Alloc>
1509 operator>=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1510 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1511 {
return !(__x < __y); }
1513 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1514 typename _Compare,
typename _Alloc>
1516 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1517 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1520 #if __cplusplus >= 201103L 1521 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1522 typename _Compare,
typename _Alloc>
1523 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1524 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1525 : _M_impl(__x._M_impl._M_key_compare,
std::move(__a))
1527 using __eq =
typename _Alloc_traits::is_always_equal;
1528 if (__x._M_root() !=
nullptr)
1529 _M_move_data(__x, __eq());
1532 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1533 typename _Compare,
typename _Alloc>
1535 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1538 _M_root() = __x._M_root();
1539 _M_leftmost() = __x._M_leftmost();
1540 _M_rightmost() = __x._M_rightmost();
1541 _M_root()->_M_parent = _M_end();
1544 __x._M_leftmost() = __x._M_end();
1545 __x._M_rightmost() = __x._M_end();
1547 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1548 __x._M_impl._M_node_count = 0;
1551 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1552 typename _Compare,
typename _Alloc>
1554 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1557 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1561 _Alloc_node __an(*
this);
1563 [&__an](
const value_type& __cval)
1565 auto& __val =
const_cast<value_type&
>(__cval);
1568 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1569 _M_leftmost() = _S_minimum(_M_root());
1570 _M_rightmost() = _S_maximum(_M_root());
1571 _M_impl._M_node_count = __x._M_impl._M_node_count;
1575 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1576 typename _Compare,
typename _Alloc>
1578 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1579 _M_move_assign(_Rb_tree& __x, true_type)
1582 if (__x._M_root() !=
nullptr)
1584 std::__alloc_on_move(_M_get_Node_allocator(),
1585 __x._M_get_Node_allocator());
1588 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1589 typename _Compare,
typename _Alloc>
1591 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1592 _M_move_assign(_Rb_tree& __x, false_type)
1594 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1595 return _M_move_assign(__x, true_type{});
1599 _Reuse_or_alloc_node __roan(*
this);
1601 if (__x._M_root() !=
nullptr)
1604 [&__roan](
const value_type& __cval)
1606 auto& __val =
const_cast<value_type&
>(__cval);
1609 _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1610 _M_leftmost() = _S_minimum(_M_root());
1611 _M_rightmost() = _S_maximum(_M_root());
1612 _M_impl._M_node_count = __x._M_impl._M_node_count;
1617 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1618 typename _Compare,
typename _Alloc>
1619 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1620 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1621 operator=(_Rb_tree&& __x)
1622 noexcept(_Alloc_traits::_S_nothrow_move()
1623 && is_nothrow_move_assignable<_Compare>::value)
1625 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1626 constexpr
bool __move_storage =
1627 _Alloc_traits::_S_propagate_on_move_assign()
1628 || _Alloc_traits::_S_always_equal();
1629 _M_move_assign(__x, __bool_constant<__move_storage>());
1633 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1634 typename _Compare,
typename _Alloc>
1635 template<
typename _Iterator>
1637 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1638 _M_assign_unique(_Iterator __first, _Iterator __last)
1640 _Reuse_or_alloc_node __roan(*
this);
1642 for (; __first != __last; ++__first)
1643 _M_insert_unique_(
end(), *__first, __roan);
1646 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1647 typename _Compare,
typename _Alloc>
1648 template<
typename _Iterator>
1650 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1651 _M_assign_equal(_Iterator __first, _Iterator __last)
1653 _Reuse_or_alloc_node __roan(*
this);
1655 for (; __first != __last; ++__first)
1656 _M_insert_equal_(
end(), *__first, __roan);
1660 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1661 typename _Compare,
typename _Alloc>
1662 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1663 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1664 operator=(
const _Rb_tree& __x)
1669 #if __cplusplus >= 201103L 1670 if (_Alloc_traits::_S_propagate_on_copy_assign())
1672 auto& __this_alloc = this->_M_get_Node_allocator();
1673 auto& __that_alloc = __x._M_get_Node_allocator();
1674 if (!_Alloc_traits::_S_always_equal()
1675 && __this_alloc != __that_alloc)
1680 std::__alloc_on_copy(__this_alloc, __that_alloc);
1685 _Reuse_or_alloc_node __roan(*
this);
1687 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1688 if (__x._M_root() != 0)
1690 _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1691 _M_leftmost() = _S_minimum(_M_root());
1692 _M_rightmost() = _S_maximum(_M_root());
1693 _M_impl._M_node_count = __x._M_impl._M_node_count;
1700 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1701 typename _Compare,
typename _Alloc>
1702 #if __cplusplus >= 201103L 1703 template<
typename _Arg,
typename _NodeGen>
1705 template<
typename _NodeGen>
1707 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1708 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1709 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1710 #
if __cplusplus >= 201103L
1715 _NodeGen& __node_gen)
1717 bool __insert_left = (__x != 0 || __p == _M_end()
1718 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1721 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1723 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1724 this->_M_impl._M_header);
1725 ++_M_impl._M_node_count;
1726 return iterator(__z);
1729 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1730 typename _Compare,
typename _Alloc>
1731 #if __cplusplus >= 201103L 1732 template<
typename _Arg>
1734 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1735 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1736 #if __cplusplus >= 201103L 1737 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1739 _M_insert_lower(_Base_ptr __p,
const _Val& __v)
1742 bool __insert_left = (__p == _M_end()
1743 || !_M_impl._M_key_compare(_S_key(__p),
1744 _KeyOfValue()(__v)));
1746 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1748 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1749 this->_M_impl._M_header);
1750 ++_M_impl._M_node_count;
1751 return iterator(__z);
1754 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1755 typename _Compare,
typename _Alloc>
1756 #if __cplusplus >= 201103L 1757 template<
typename _Arg>
1759 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1760 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1761 #if __cplusplus >= 201103L 1762 _M_insert_equal_lower(_Arg&& __v)
1764 _M_insert_equal_lower(
const _Val& __v)
1767 _Link_type __x = _M_begin();
1768 _Base_ptr __y = _M_end();
1772 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1773 _S_left(__x) : _S_right(__x);
1775 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1778 template<
typename _Key,
typename _Val,
typename _KoV,
1779 typename _Compare,
typename _Alloc>
1780 template<
typename _NodeGen>
1781 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1782 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1783 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1786 _Link_type __top = _M_clone_node(__x, __node_gen);
1787 __top->_M_parent = __p;
1792 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1798 _Link_type __y = _M_clone_node(__x, __node_gen);
1800 __y->_M_parent = __p;
1802 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1810 __throw_exception_again;
1815 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1816 typename _Compare,
typename _Alloc>
1818 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1819 _M_erase(_Link_type __x)
1824 _M_erase(_S_right(__x));
1825 _Link_type __y = _S_left(__x);
1831 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1832 typename _Compare,
typename _Alloc>
1833 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1834 _Compare, _Alloc>::iterator
1835 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1836 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1840 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1841 __y = __x, __x = _S_left(__x);
1843 __x = _S_right(__x);
1844 return iterator(__y);
1847 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1848 typename _Compare,
typename _Alloc>
1849 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1850 _Compare, _Alloc>::const_iterator
1851 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1852 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1853 const _Key& __k)
const 1856 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1857 __y = __x, __x = _S_left(__x);
1859 __x = _S_right(__x);
1860 return const_iterator(__y);
1863 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1864 typename _Compare,
typename _Alloc>
1865 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1866 _Compare, _Alloc>::iterator
1867 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1868 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1872 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1873 __y = __x, __x = _S_left(__x);
1875 __x = _S_right(__x);
1876 return iterator(__y);
1879 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1880 typename _Compare,
typename _Alloc>
1881 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1882 _Compare, _Alloc>::const_iterator
1883 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1884 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1885 const _Key& __k)
const 1888 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1889 __y = __x, __x = _S_left(__x);
1891 __x = _S_right(__x);
1892 return const_iterator(__y);
1895 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1896 typename _Compare,
typename _Alloc>
1897 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1898 _Compare, _Alloc>::iterator,
1899 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1900 _Compare, _Alloc>::iterator>
1901 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1902 equal_range(
const _Key& __k)
1904 _Link_type __x = _M_begin();
1905 _Base_ptr __y = _M_end();
1908 if (_M_impl._M_key_compare(_S_key(__x), __k))
1909 __x = _S_right(__x);
1910 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1911 __y = __x, __x = _S_left(__x);
1914 _Link_type __xu(__x);
1915 _Base_ptr __yu(__y);
1916 __y = __x, __x = _S_left(__x);
1917 __xu = _S_right(__xu);
1918 return pair<iterator,
1919 iterator>(_M_lower_bound(__x, __y, __k),
1920 _M_upper_bound(__xu, __yu, __k));
1923 return pair<iterator, iterator>(iterator(__y),
1927 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1928 typename _Compare,
typename _Alloc>
1929 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1930 _Compare, _Alloc>::const_iterator,
1931 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1932 _Compare, _Alloc>::const_iterator>
1933 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1934 equal_range(
const _Key& __k)
const 1936 _Const_Link_type __x = _M_begin();
1937 _Const_Base_ptr __y = _M_end();
1940 if (_M_impl._M_key_compare(_S_key(__x), __k))
1941 __x = _S_right(__x);
1942 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1943 __y = __x, __x = _S_left(__x);
1946 _Const_Link_type __xu(__x);
1947 _Const_Base_ptr __yu(__y);
1948 __y = __x, __x = _S_left(__x);
1949 __xu = _S_right(__xu);
1950 return pair<const_iterator,
1951 const_iterator>(_M_lower_bound(__x, __y, __k),
1952 _M_upper_bound(__xu, __yu, __k));
1955 return pair<const_iterator, const_iterator>(const_iterator(__y),
1956 const_iterator(__y));
1959 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1960 typename _Compare,
typename _Alloc>
1962 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1964 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1968 if (__t._M_root() != 0)
1970 _M_root() = __t._M_root();
1971 _M_leftmost() = __t._M_leftmost();
1972 _M_rightmost() = __t._M_rightmost();
1973 _M_root()->_M_parent = _M_end();
1974 _M_impl._M_node_count = __t._M_impl._M_node_count;
1976 __t._M_impl._M_reset();
1979 else if (__t._M_root() == 0)
1981 __t._M_root() = _M_root();
1982 __t._M_leftmost() = _M_leftmost();
1983 __t._M_rightmost() = _M_rightmost();
1984 __t._M_root()->_M_parent = __t._M_end();
1985 __t._M_impl._M_node_count = _M_impl._M_node_count;
1991 std::swap(_M_root(),__t._M_root());
1992 std::swap(_M_leftmost(),__t._M_leftmost());
1993 std::swap(_M_rightmost(),__t._M_rightmost());
1995 _M_root()->_M_parent = _M_end();
1996 __t._M_root()->_M_parent = __t._M_end();
1997 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2000 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2002 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2003 __t._M_get_Node_allocator());
2006 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2007 typename _Compare,
typename _Alloc>
2008 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2009 _Compare, _Alloc>::_Base_ptr,
2010 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2011 _Compare, _Alloc>::_Base_ptr>
2012 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2013 _M_get_insert_unique_pos(
const key_type& __k)
2015 typedef pair<_Base_ptr, _Base_ptr> _Res;
2016 _Link_type __x = _M_begin();
2017 _Base_ptr __y = _M_end();
2022 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2023 __x = __comp ? _S_left(__x) : _S_right(__x);
2025 iterator __j = iterator(__y);
2029 return _Res(__x, __y);
2033 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2034 return _Res(__x, __y);
2035 return _Res(__j._M_node, 0);
2038 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2039 typename _Compare,
typename _Alloc>
2040 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2041 _Compare, _Alloc>::_Base_ptr,
2042 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2043 _Compare, _Alloc>::_Base_ptr>
2044 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2045 _M_get_insert_equal_pos(
const key_type& __k)
2047 typedef pair<_Base_ptr, _Base_ptr> _Res;
2048 _Link_type __x = _M_begin();
2049 _Base_ptr __y = _M_end();
2053 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2054 _S_left(__x) : _S_right(__x);
2056 return _Res(__x, __y);
2059 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2060 typename _Compare,
typename _Alloc>
2061 #if __cplusplus >= 201103L 2062 template<
typename _Arg>
2064 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2065 _Compare, _Alloc>::iterator,
bool>
2066 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2067 #if __cplusplus >= 201103L 2068 _M_insert_unique(_Arg&& __v)
2070 _M_insert_unique(
const _Val& __v)
2073 typedef pair<iterator, bool> _Res;
2074 pair<_Base_ptr, _Base_ptr> __res
2075 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2079 _Alloc_node __an(*
this);
2080 return _Res(_M_insert_(__res.first, __res.second,
2081 _GLIBCXX_FORWARD(_Arg, __v), __an),
2085 return _Res(iterator(__res.first),
false);
2088 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2089 typename _Compare,
typename _Alloc>
2090 #if __cplusplus >= 201103L 2091 template<
typename _Arg>
2093 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2094 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2095 #if __cplusplus >= 201103L 2096 _M_insert_equal(_Arg&& __v)
2098 _M_insert_equal(
const _Val& __v)
2101 pair<_Base_ptr, _Base_ptr> __res
2102 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2103 _Alloc_node __an(*
this);
2104 return _M_insert_(__res.first, __res.second,
2105 _GLIBCXX_FORWARD(_Arg, __v), __an);
2108 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2109 typename _Compare,
typename _Alloc>
2110 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2111 _Compare, _Alloc>::_Base_ptr,
2112 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2113 _Compare, _Alloc>::_Base_ptr>
2114 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2115 _M_get_insert_hint_unique_pos(const_iterator __position,
2116 const key_type& __k)
2118 iterator __pos = __position._M_const_cast();
2119 typedef pair<_Base_ptr, _Base_ptr> _Res;
2122 if (__pos._M_node == _M_end())
2125 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2126 return _Res(0, _M_rightmost());
2128 return _M_get_insert_unique_pos(__k);
2130 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2133 iterator __before = __pos;
2134 if (__pos._M_node == _M_leftmost())
2135 return _Res(_M_leftmost(), _M_leftmost());
2136 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2138 if (_S_right(__before._M_node) == 0)
2139 return _Res(0, __before._M_node);
2141 return _Res(__pos._M_node, __pos._M_node);
2144 return _M_get_insert_unique_pos(__k);
2146 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2149 iterator __after = __pos;
2150 if (__pos._M_node == _M_rightmost())
2151 return _Res(0, _M_rightmost());
2152 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2154 if (_S_right(__pos._M_node) == 0)
2155 return _Res(0, __pos._M_node);
2157 return _Res(__after._M_node, __after._M_node);
2160 return _M_get_insert_unique_pos(__k);
2164 return _Res(__pos._M_node, 0);
2167 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2168 typename _Compare,
typename _Alloc>
2169 #if __cplusplus >= 201103L 2170 template<
typename _Arg,
typename _NodeGen>
2172 template<
typename _NodeGen>
2174 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2175 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2176 _M_insert_unique_(const_iterator __position,
2177 #
if __cplusplus >= 201103L
2182 _NodeGen& __node_gen)
2184 pair<_Base_ptr, _Base_ptr> __res
2185 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2188 return _M_insert_(__res.first, __res.second,
2189 _GLIBCXX_FORWARD(_Arg, __v),
2191 return iterator(__res.first);
2194 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2195 typename _Compare,
typename _Alloc>
2196 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2197 _Compare, _Alloc>::_Base_ptr,
2198 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2199 _Compare, _Alloc>::_Base_ptr>
2200 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2201 _M_get_insert_hint_equal_pos(const_iterator __position,
const key_type& __k)
2203 iterator __pos = __position._M_const_cast();
2204 typedef pair<_Base_ptr, _Base_ptr> _Res;
2207 if (__pos._M_node == _M_end())
2210 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2211 return _Res(0, _M_rightmost());
2213 return _M_get_insert_equal_pos(__k);
2215 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2218 iterator __before = __pos;
2219 if (__pos._M_node == _M_leftmost())
2220 return _Res(_M_leftmost(), _M_leftmost());
2221 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2223 if (_S_right(__before._M_node) == 0)
2224 return _Res(0, __before._M_node);
2226 return _Res(__pos._M_node, __pos._M_node);
2229 return _M_get_insert_equal_pos(__k);
2234 iterator __after = __pos;
2235 if (__pos._M_node == _M_rightmost())
2236 return _Res(0, _M_rightmost());
2237 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2239 if (_S_right(__pos._M_node) == 0)
2240 return _Res(0, __pos._M_node);
2242 return _Res(__after._M_node, __after._M_node);
2249 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2250 typename _Compare,
typename _Alloc>
2251 #if __cplusplus >= 201103L 2252 template<
typename _Arg,
typename _NodeGen>
2254 template<
typename _NodeGen>
2256 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2257 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2258 _M_insert_equal_(const_iterator __position,
2259 #
if __cplusplus >= 201103L
2264 _NodeGen& __node_gen)
2266 pair<_Base_ptr, _Base_ptr> __res
2267 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2270 return _M_insert_(__res.first, __res.second,
2271 _GLIBCXX_FORWARD(_Arg, __v),
2274 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2277 #if __cplusplus >= 201103L 2278 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2279 typename _Compare,
typename _Alloc>
2280 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2281 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2282 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2284 bool __insert_left = (__x != 0 || __p == _M_end()
2285 || _M_impl._M_key_compare(_S_key(__z),
2288 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2289 this->_M_impl._M_header);
2290 ++_M_impl._M_node_count;
2291 return iterator(__z);
2294 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2295 typename _Compare,
typename _Alloc>
2296 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2297 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2298 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2300 bool __insert_left = (__p == _M_end()
2301 || !_M_impl._M_key_compare(_S_key(__p),
2304 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2305 this->_M_impl._M_header);
2306 ++_M_impl._M_node_count;
2307 return iterator(__z);
2310 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2311 typename _Compare,
typename _Alloc>
2312 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2313 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2314 _M_insert_equal_lower_node(_Link_type __z)
2316 _Link_type __x = _M_begin();
2317 _Base_ptr __y = _M_end();
2321 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2322 _S_left(__x) : _S_right(__x);
2324 return _M_insert_lower_node(__y, __z);
2327 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2328 typename _Compare,
typename _Alloc>
2329 template<
typename... _Args>
2330 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2331 _Compare, _Alloc>::iterator,
bool>
2332 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2333 _M_emplace_unique(_Args&&... __args)
2335 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2339 typedef pair<iterator, bool> _Res;
2340 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2342 return _Res(_M_insert_node(__res.first, __res.second, __z),
true);
2345 return _Res(iterator(__res.first),
false);
2350 __throw_exception_again;
2354 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2355 typename _Compare,
typename _Alloc>
2356 template<
typename... _Args>
2357 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2358 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2359 _M_emplace_equal(_Args&&... __args)
2361 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2365 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2366 return _M_insert_node(__res.first, __res.second, __z);
2371 __throw_exception_again;
2375 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2376 typename _Compare,
typename _Alloc>
2377 template<
typename... _Args>
2378 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2379 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2380 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2382 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2386 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2389 return _M_insert_node(__res.first, __res.second, __z);
2392 return iterator(__res.first);
2397 __throw_exception_again;
2401 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2402 typename _Compare,
typename _Alloc>
2403 template<
typename... _Args>
2404 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2405 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2406 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2408 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2412 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2415 return _M_insert_node(__res.first, __res.second, __z);
2417 return _M_insert_equal_lower_node(__z);
2422 __throw_exception_again;
2427 template<
typename _Key,
typename _Val,
typename _KoV,
2428 typename _Cmp,
typename _Alloc>
2431 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2432 _M_insert_unique(_II __first, _II __last)
2434 _Alloc_node __an(*
this);
2435 for (; __first != __last; ++__first)
2436 _M_insert_unique_(
end(), *__first, __an);
2439 template<
typename _Key,
typename _Val,
typename _KoV,
2440 typename _Cmp,
typename _Alloc>
2443 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2444 _M_insert_equal(_II __first, _II __last)
2446 _Alloc_node __an(*
this);
2447 for (; __first != __last; ++__first)
2448 _M_insert_equal_(
end(), *__first, __an);
2451 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2452 typename _Compare,
typename _Alloc>
2454 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2455 _M_erase_aux(const_iterator __position)
2458 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2459 (const_cast<_Base_ptr>(__position._M_node),
2460 this->_M_impl._M_header));
2462 --_M_impl._M_node_count;
2465 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2466 typename _Compare,
typename _Alloc>
2468 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2469 _M_erase_aux(const_iterator __first, const_iterator __last)
2471 if (__first ==
begin() && __last ==
end())
2474 while (__first != __last)
2478 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2479 typename _Compare,
typename _Alloc>
2480 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2481 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2482 erase(
const _Key& __x)
2484 pair<iterator, iterator> __p = equal_range(__x);
2485 const size_type __old_size =
size();
2486 erase(__p.first, __p.second);
2487 return __old_size -
size();
2490 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2491 typename _Compare,
typename _Alloc>
2493 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2494 erase(
const _Key* __first,
const _Key* __last)
2496 while (__first != __last)
2500 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2501 typename _Compare,
typename _Alloc>
2502 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2503 _Compare, _Alloc>::iterator
2504 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2505 find(
const _Key& __k)
2507 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2508 return (__j ==
end()
2509 || _M_impl._M_key_compare(__k,
2510 _S_key(__j._M_node))) ?
end() : __j;
2513 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2514 typename _Compare,
typename _Alloc>
2515 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2516 _Compare, _Alloc>::const_iterator
2517 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2518 find(
const _Key& __k)
const 2520 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2521 return (__j ==
end()
2522 || _M_impl._M_key_compare(__k,
2523 _S_key(__j._M_node))) ?
end() : __j;
2526 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2527 typename _Compare,
typename _Alloc>
2528 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2529 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2530 count(
const _Key& __k)
const 2532 pair<const_iterator, const_iterator> __p = equal_range(__k);
2537 _GLIBCXX_PURE
unsigned int 2538 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
2539 const _Rb_tree_node_base* __root)
throw ();
2541 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2542 typename _Compare,
typename _Alloc>
2544 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const 2546 if (_M_impl._M_node_count == 0 ||
begin() ==
end())
2547 return _M_impl._M_node_count == 0 &&
begin() ==
end()
2548 && this->_M_impl._M_header._M_left == _M_end()
2549 && this->_M_impl._M_header._M_right == _M_end();
2551 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2552 for (const_iterator __it =
begin(); __it !=
end(); ++__it)
2554 _Const_Link_type __x =
static_cast<_Const_Link_type
>(__it._M_node);
2555 _Const_Link_type __L = _S_left(__x);
2556 _Const_Link_type __R = _S_right(__x);
2558 if (__x->_M_color == _S_red)
2559 if ((__L && __L->_M_color == _S_red)
2560 || (__R && __R->_M_color == _S_red))
2563 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2565 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2568 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2572 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2574 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2579 #if __cplusplus > 201402L 2581 template<
typename _Key,
typename _Val,
typename _Sel,
typename _Cmp1,
2582 typename _Alloc,
typename _Cmp2>
2583 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2587 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2590 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2591 {
return __tree._M_impl; }
2595 _GLIBCXX_END_NAMESPACE_VERSION
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
Uniform interface to C++98 and C++11 allocators.
constexpr _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.
ISO C++ entities toplevel namespace is std.
size_type size() const
As per Table mumble.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
_GLIBCXX17_CONSTEXPR auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
_GLIBCXX17_CONSTEXPR auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
iterator end()
As per Table mumble.
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.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
iterator begin()
As per Table mumble.
bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.