60 #if __cplusplus >= 201103L
64 namespace std _GLIBCXX_VISIBILITY(default)
66 _GLIBCXX_BEGIN_NAMESPACE_VERSION
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
69 template<
typename _Key,
typename _Compare,
typename _Alloc>
92 template<
typename _Key,
typename _Compare = std::less<_Key>,
93 typename _Alloc = std::allocator<_Key> >
96 #ifdef _GLIBCXX_CONCEPT_CHECKS
98 typedef typename _Alloc::value_type _Alloc_value_type;
99 # if __cplusplus < 201103L
100 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
102 __glibcxx_class_requires4(_Compare,
bool, _Key, _Key,
103 _BinaryFunctionConcept)
104 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
107 #if __cplusplus >= 201103L
108 static_assert(is_same<
typename remove_cv<_Key>::type, _Key>::value,
109 "std::set must have a non-const, non-volatile value_type");
110 # ifdef __STRICT_ANSI__
112 "std::set must have the same value_type as its allocator");
129 rebind<_Key>::other _Key_alloc_type;
131 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
140 typedef typename _Alloc_traits::pointer
pointer;
147 typedef typename _Rep_type::const_iterator
iterator;
155 #if __cplusplus > 201402L
156 using node_type =
typename _Rep_type::node_type;
157 using insert_return_type =
typename _Rep_type::insert_return_type;
164 #if __cplusplus < 201103L
176 set(
const _Compare& __comp,
178 : _M_t(__comp, _Key_alloc_type(__a)) { }
190 template<
typename _InputIterator>
191 set(_InputIterator __first, _InputIterator __last)
193 { _M_t._M_insert_unique(__first, __last); }
207 template<
typename _InputIterator>
208 set(_InputIterator __first, _InputIterator __last,
209 const _Compare& __comp,
211 : _M_t(__comp, _Key_alloc_type(__a))
212 { _M_t._M_insert_unique(__first, __last); }
219 #if __cplusplus < 201103L
223 set(
const set&) =
default;
244 const _Compare& __comp = _Compare(),
246 : _M_t(__comp, _Key_alloc_type(__a))
247 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
252 : _M_t(_Compare(), _Key_alloc_type(__a)) { }
256 : _M_t(__x._M_t, _Key_alloc_type(__a)) { }
261 && _Alloc_traits::_S_always_equal())
262 : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
266 : _M_t(_Compare(), _Key_alloc_type(__a))
267 { _M_t._M_insert_unique(__l.begin(), __l.end()); }
270 template<
typename _InputIterator>
271 set(_InputIterator __first, _InputIterator __last,
273 : _M_t(_Compare(), _Key_alloc_type(__a))
274 { _M_t._M_insert_unique(__first, __last); }
289 #if __cplusplus < 201103L
318 _M_t._M_assign_unique(__l.begin(), __l.end());
328 {
return _M_t.key_comp(); }
332 {
return _M_t.key_comp(); }
345 {
return _M_t.begin(); }
353 end() const _GLIBCXX_NOEXCEPT
354 {
return _M_t.end(); }
363 {
return _M_t.rbegin(); }
372 {
return _M_t.rend(); }
374 #if __cplusplus >= 201103L
382 {
return _M_t.begin(); }
391 {
return _M_t.end(); }
400 {
return _M_t.rbegin(); }
409 {
return _M_t.rend(); }
415 {
return _M_t.empty(); }
420 {
return _M_t.size(); }
425 {
return _M_t.max_size(); }
442 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
443 { _M_t.swap(__x._M_t); }
446 #if __cplusplus >= 201103L
460 template<
typename... _Args>
463 {
return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
486 template<
typename... _Args>
490 return _M_t._M_emplace_hint_unique(__pos,
491 std::forward<_Args>(__args)...);
512 _M_t._M_insert_unique(__x);
516 #if __cplusplus >= 201103L
521 _M_t._M_insert_unique(std::move(__x));
547 {
return _M_t._M_insert_unique_(__position, __x); }
549 #if __cplusplus >= 201103L
552 {
return _M_t._M_insert_unique_(__position, std::move(__x)); }
564 template<
typename _InputIterator>
566 insert(_InputIterator __first, _InputIterator __last)
567 { _M_t._M_insert_unique(__first, __last); }
569 #if __cplusplus >= 201103L
579 { this->
insert(__l.begin(), __l.end()); }
582 #if __cplusplus > 201402L
587 __glibcxx_assert(__pos !=
end());
588 return _M_t.extract(__pos);
594 {
return _M_t.extract(__x); }
599 {
return _M_t._M_reinsert_node_unique(std::move(__nh)); }
604 {
return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
606 template<
typename,
typename>
607 friend class std::_Rb_tree_merge_helper;
609 template<
typename _Compare1>
611 merge(set<_Key, _Compare1, _Alloc>& __source)
613 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
614 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
617 template<
typename _Compare1>
619 merge(set<_Key, _Compare1, _Alloc>&& __source)
622 template<
typename _Compare1>
624 merge(multiset<_Key, _Compare1, _Alloc>& __source)
626 using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>;
627 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));
630 template<
typename _Compare1>
632 merge(multiset<_Key, _Compare1, _Alloc>&& __source)
636 #if __cplusplus >= 201103L
652 _GLIBCXX_ABI_TAG_CXX11
655 {
return _M_t.erase(__position); }
669 { _M_t.erase(__position); }
685 {
return _M_t.erase(__x); }
687 #if __cplusplus >= 201103L
704 _GLIBCXX_ABI_TAG_CXX11
707 {
return _M_t.erase(__first, __last); }
723 { _M_t.erase(__first, __last); }
749 {
return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
751 #if __cplusplus > 201103L
752 template<
typename _Kt>
755 -> decltype(_M_t._M_count_tr(__x))
756 {
return _M_t._M_count_tr(__x); }
776 {
return _M_t.find(__x); }
780 {
return _M_t.find(__x); }
782 #if __cplusplus > 201103L
783 template<
typename _Kt>
786 -> decltype(
iterator{_M_t._M_find_tr(__x)})
787 {
return iterator{_M_t._M_find_tr(__x)}; }
789 template<
typename _Kt>
811 {
return _M_t.lower_bound(__x); }
815 {
return _M_t.lower_bound(__x); }
817 #if __cplusplus > 201103L
818 template<
typename _Kt>
821 -> decltype(
iterator(_M_t._M_lower_bound_tr(__x)))
822 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
824 template<
typename _Kt>
841 {
return _M_t.upper_bound(__x); }
845 {
return _M_t.upper_bound(__x); }
847 #if __cplusplus > 201103L
848 template<
typename _Kt>
851 -> decltype(
iterator(_M_t._M_upper_bound_tr(__x)))
852 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
854 template<
typename _Kt>
857 -> decltype(
iterator(_M_t._M_upper_bound_tr(__x)))
880 {
return _M_t.equal_range(__x); }
884 {
return _M_t.equal_range(__x); }
886 #if __cplusplus > 201103L
887 template<
typename _Kt>
893 template<
typename _Kt>
901 template<
typename _K1,
typename _C1,
typename _A1>
905 template<
typename _K1,
typename _C1,
typename _A1>
910 #if __cpp_deduction_guides >= 201606
912 template<
typename _InputIterator,
914 less<typename iterator_traits<_InputIterator>::value_type>,
915 typename _Allocator =
916 allocator<typename iterator_traits<_InputIterator>::value_type>,
917 typename = _RequireInputIter<_InputIterator>,
918 typename = _RequireAllocator<_Allocator>>
919 set(_InputIterator, _InputIterator,
920 _Compare = _Compare(), _Allocator = _Allocator())
921 -> set<typename iterator_traits<_InputIterator>::value_type,
922 _Compare, _Allocator>;
924 template<
typename _Key,
typename _Compare = less<_Key>,
925 typename _Allocator = allocator<_Key>,
926 typename = _RequireAllocator<_Allocator>>
927 set(initializer_list<_Key>,
928 _Compare = _Compare(), _Allocator = _Allocator())
929 -> set<_Key, _Compare, _Allocator>;
931 template<
typename _InputIterator,
typename _Allocator,
932 typename = _RequireInputIter<_InputIterator>,
933 typename = _RequireAllocator<_Allocator>>
934 set(_InputIterator, _InputIterator, _Allocator)
935 -> set<typename iterator_traits<_InputIterator>::value_type,
936 less<typename iterator_traits<_InputIterator>::value_type>,
939 template<
typename _Key,
typename _Allocator,
940 typename = _RequireAllocator<_Allocator>>
941 set(initializer_list<_Key>, _Allocator)
942 -> set<_Key, less<_Key>, _Allocator>;
956 template<
typename _Key,
typename _Compare,
typename _Alloc>
960 {
return __x._M_t == __y._M_t; }
973 template<
typename _Key,
typename _Compare,
typename _Alloc>
975 operator<(const set<_Key, _Compare, _Alloc>& __x,
977 {
return __x._M_t < __y._M_t; }
980 template<
typename _Key,
typename _Compare,
typename _Alloc>
984 {
return !(__x == __y); }
987 template<
typename _Key,
typename _Compare,
typename _Alloc>
991 {
return __y < __x; }
994 template<
typename _Key,
typename _Compare,
typename _Alloc>
996 operator<=(const set<_Key, _Compare, _Alloc>& __x,
998 {
return !(__y < __x); }
1001 template<
typename _Key,
typename _Compare,
typename _Alloc>
1005 {
return !(__x < __y); }
1008 template<
typename _Key,
typename _Compare,
typename _Alloc>
1011 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1014 _GLIBCXX_END_NAMESPACE_CONTAINER
1016 #if __cplusplus > 201402L
1018 template<
typename _Val,
typename _Cmp1,
typename _Alloc,
typename _Cmp2>
1020 _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2>
1023 friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>;
1026 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
1027 {
return __set._M_t; }
1030 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
1031 {
return __set._M_t; }
1035 _GLIBCXX_END_NAMESPACE_VERSION
set(const allocator_type &__a)
Allocator-extended default constructor.
reverse_iterator crend() const noexcept
auto find(const _Kt &__x) -> decltype(iterator
Tries to locate an element in a set.
A standard container made up of unique keys, which can be retrieved in logarithmic time...
set(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a set with no elements.
reverse_iterator crbegin() const noexcept
reverse_iterator rbegin() const noexcept
iterator cbegin() const noexcept
_Alloc_traits::pointer pointer
Iterator-related typedefs.
set(_InputIterator __first, _InputIterator __last)
Builds a set from a range.
_Rep_type::const_iterator iterator
Iterator-related typedefs.
auto count(const _Kt &__x) const -> decltype(_M_t._M_count_tr(__x))
Finds the number of elements.
_T2 second
first is a copy of the first object
_Key key_type
Public typedefs.
size_type size() const noexcept
Returns the size of the set.
iterator begin() const noexcept
_Alloc_traits::reference reference
Iterator-related typedefs.
_Rep_type::size_type size_type
Iterator-related typedefs.
auto upper_bound(const _Kt &__x) const -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
_T1 first
second_type is the second bound type
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
reverse_iterator rend() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
_Rep_type::const_reverse_iterator const_reverse_iterator
Iterator-related typedefs.
set()=default
Default constructor creates no elements.
_Alloc allocator_type
Public typedefs.
auto lower_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
_Rep_type::const_iterator const_iterator
Iterator-related typedefs.
std::pair< iterator, bool > emplace(_Args &&...__args)
Attempts to build and insert an element into the set.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to insert an element into the set.
_Alloc_traits::const_reference const_reference
Iterator-related typedefs.
is_nothrow_copy_constructible
key_compare key_comp() const
Returns the comparison object with which the set was constructed.
_Compare key_compare
Public typedefs.
_Key value_type
Public typedefs.
auto find(const _Kt &__x) const -> decltype(const_iterator
Tries to locate an element in a set.
auto upper_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
set(_InputIterator __first, _InputIterator __last, const allocator_type &__a)
Allocator-extended range constructor.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the set.
set & operator=(const set &)=default
Set assignment operator.
iterator find(const key_type &__x)
Tries to locate an element in a set.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __position)
Erases an element from a set.
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
set & operator=(initializer_list< value_type > __l)
Set list assignment operator.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
value_compare value_comp() const
Returns the comparison object with which the set was constructed.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
const_iterator find(const key_type &__x) const
Tries to locate an element in a set.
size_type max_size() const noexcept
Returns the maximum size of the set.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from a set.
iterator insert(const_iterator __position, const value_type &__x)
Attempts to insert an element into the set.
size_type count(const key_type &__x) const
Finds the number of elements.
set(const set &__x, const allocator_type &__a)
Allocator-extended copy constructor.
set(set &&__x, const allocator_type &__a) noexcept(is_nothrow_copy_constructible< _Compare >::value &&_Alloc_traits::_S_always_equal())
Allocator-extended move constructor.
set(initializer_list< value_type > __l, const _Compare &__comp=_Compare(), const allocator_type &__a=allocator_type())
Builds a set from an initializer_list.
auto lower_bound(const _Kt &__x) const -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
iterator end() const noexcept
Struct holding two objects of arbitrary type.
iterator cend() const noexcept
bool empty() const noexcept
Returns true if the set is empty.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
allocator_type get_allocator() const noexcept
Returns the allocator object with which the set was constructed.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the set.
auto equal_range(const _Kt &__x) -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
_Rep_type::const_reverse_iterator reverse_iterator
Iterator-related typedefs.
_Rep_type::difference_type difference_type
Iterator-related typedefs.
_Alloc_traits::const_pointer const_pointer
Iterator-related typedefs.
Uniform interface to C++98 and C++11 allocators.
set(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a set from a range.
_Compare value_compare
Public typedefs.
void swap(set &__x) noexcept(/*conditional */)
Swaps data with another set.
auto equal_range(const _Kt &__x) const -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
set(initializer_list< value_type > __l, const allocator_type &__a)
Allocator-extended initialier-list constructor.