29#ifndef _GLIBCXX_FLAT_SET
30#define _GLIBCXX_FLAT_SET 1
33#pragma GCC system_header
36#define __glibcxx_want_flat_set
39#ifdef __cpp_lib_flat_set
58namespace std _GLIBCXX_VISIBILITY(default)
60_GLIBCXX_BEGIN_NAMESPACE_VERSION
62 template<
typename _Key,
typename _Compare,
63 typename _KeyContainer>
66 template<
typename _Key,
typename _Compare,
67 typename _KeyContainer>
70 template<
typename _Key,
typename _Compare,
typename _KeyContainer,
bool _Multi>
73 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
74 static_assert(is_nothrow_swappable_v<_KeyContainer>);
76 using _Derived = __conditional_t<_Multi,
77 flat_multiset<_Key, _Compare, _KeyContainer>,
78 flat_set<_Key, _Compare, _KeyContainer>>;
79 using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>;
82 using key_type = _Key;
83 using value_type = _Key;
84 using key_compare = _Compare;
85 using value_compare = _Compare;
86 using reference = value_type&;
87 using const_reference =
const value_type&;
88 using size_type =
typename _KeyContainer::size_type;
89 using difference_type =
typename _KeyContainer::difference_type;
90 using iterator =
typename _KeyContainer::const_iterator;
91 using const_iterator =
typename _KeyContainer::const_iterator;
94 using container_type = _KeyContainer;
97 using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>;
101 container_type* _M_cont;
103 _ClearGuard(container_type&
__cont)
115 { _M_cont =
nullptr; }
119 _M_make_clear_guard()
120 {
return _ClearGuard{this->_M_cont}; }
124 _Flat_set_impl() : _Flat_set_impl(key_compare()) { }
127 _Flat_set_impl(
const key_compare& __comp)
128 : _M_cont(), _M_comp(__comp)
131 _Flat_set_impl(container_type
__cont,
const key_compare& __comp = key_compare())
135 _Flat_set_impl(__sorted_t,
136 container_type
__cont,
const key_compare& __comp = key_compare())
138 { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); }
140 template<__has_input_iter_cat _InputIterator>
141 _Flat_set_impl(_InputIterator __first, _InputIterator __last,
142 const key_compare& __comp = key_compare())
143 : _M_cont(), _M_comp(__comp)
144 { insert(__first, __last); }
146 template<__has_input_iter_cat _InputIterator>
147 _Flat_set_impl(__sorted_t __s,
148 _InputIterator __first, _InputIterator __last,
149 const key_compare& __comp = key_compare())
150 : _M_cont(), _M_comp(__comp)
151 { insert(__s, __first, __last); }
153 template<__detail::__container_compatible_range<value_type> _Rg>
154 _Flat_set_impl(from_range_t, _Rg&& __rg)
155 : _Flat_set_impl(from_range,
std::
forward<_Rg>(__rg), key_compare())
158 template<__detail::__container_compatible_range<value_type> _Rg>
159 _Flat_set_impl(from_range_t, _Rg&& __rg,
const key_compare& __comp)
160 : _Flat_set_impl(__comp)
161 { insert_range(std::forward<_Rg>(__rg)); }
163 _Flat_set_impl(initializer_list<value_type> __il,
164 const key_compare& __comp = key_compare())
165 : _Flat_set_impl(__il.
begin(), __il.
end(), __comp)
168 _Flat_set_impl(__sorted_t __s,
169 initializer_list<value_type> __il,
170 const key_compare& __comp = key_compare())
171 : _Flat_set_impl(__s, __il.
begin(), __il.
end(), __comp)
176 template<__allocator_for<container_type> _Alloc>
178 _Flat_set_impl(
const _Alloc& __a)
179 : _Flat_set_impl(key_compare(), __a)
182 template<__allocator_for<container_type> _Alloc>
183 _Flat_set_impl(
const key_compare& __comp,
const _Alloc& __a)
184 : _M_cont(
std::make_obj_using_allocator<container_type>(__a)),
188 template<__allocator_for<container_type> _Alloc>
189 _Flat_set_impl(
const container_type&
__cont,
const _Alloc& __a)
190 : _Flat_set_impl(
__cont, key_compare(), __a)
193 template<__allocator_for<container_type> _Alloc>
194 _Flat_set_impl(
const container_type&
__cont,
const key_compare& __comp,
196 : _M_cont(
std::make_obj_using_allocator<container_type>(__a,
__cont)),
200 template<__allocator_for<container_type> _Alloc>
201 _Flat_set_impl(__sorted_t __s,
const container_type&
__cont,
const _Alloc& __a)
202 : _Flat_set_impl(__s,
__cont, key_compare(), __a)
205 template<__allocator_for<container_type> _Alloc>
206 _Flat_set_impl(__sorted_t,
const container_type&
__cont,
const key_compare& __comp,
208 : _M_cont(
std::make_obj_using_allocator<container_type>(__a,
__cont)),
210 { _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont, _M_comp)); }
212 template<__allocator_for<container_type> _Alloc>
213 _Flat_set_impl(
const _Derived& __x,
const _Alloc& __a)
214 : _M_cont(
std::make_obj_using_allocator<container_type>(__a, __x._M_cont)),
218 template<__allocator_for<container_type> _Alloc>
219 _Flat_set_impl(_Derived&& __x,
const _Alloc& __a)
220 : _M_cont(
std::make_obj_using_allocator<container_type>(__a,
std::
move(__x._M_cont))),
224 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
225 _Flat_set_impl(_InputIterator __first, _InputIterator __last,
227 : _Flat_set_impl(
std::
move(__first),
std::
move(__last), key_compare(), __a)
230 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
231 _Flat_set_impl(_InputIterator __first, _InputIterator __last,
232 const key_compare& __comp,
234 : _Flat_set_impl(__comp, __a)
235 { insert(__first, __last); }
237 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
238 _Flat_set_impl(__sorted_t __s,
239 _InputIterator __first, _InputIterator __last,
241 : _Flat_set_impl(__s,
std::
move(__first),
std::
move(__last), key_compare(), __a)
244 template<__has_input_iter_cat _InputIterator, __allocator_for<container_type> _Alloc>
245 _Flat_set_impl(__sorted_t __s,
246 _InputIterator __first, _InputIterator __last,
247 const key_compare& __comp,
249 : _Flat_set_impl(__comp, __a)
250 { insert(__s, __first, __last); }
252 template<__detail::__container_compatible_range<value_type> _Rg,
253 __allocator_for<container_type> _Alloc>
254 _Flat_set_impl(from_range_t, _Rg&& __rg,
256 : _Flat_set_impl(from_range,
std::
forward<_Rg>(__rg), key_compare(), __a)
259 template<__detail::__container_compatible_range<value_type> _Rg,
260 __allocator_for<container_type> _Alloc>
261 _Flat_set_impl(from_range_t, _Rg&& __rg,
262 const key_compare& __comp,
264 : _Flat_set_impl(__comp, __a)
265 { insert_range(std::forward<_Rg>(__rg)); }
267 template<__allocator_for<container_type> _Alloc>
268 _Flat_set_impl(initializer_list<value_type> __il,
270 : _Flat_set_impl(__il, key_compare(), __a)
273 template<__allocator_for<container_type> _Alloc>
274 _Flat_set_impl(initializer_list<value_type> __il,
275 const key_compare& __comp,
277 : _Flat_set_impl(__il.
begin(), __il.
end(), __comp, __a)
280 template<__allocator_for<container_type> _Alloc>
281 _Flat_set_impl(__sorted_t __s,
282 initializer_list<value_type> __il,
284 : _Flat_set_impl(__s, __il.
begin(), __il.
end(), key_compare(), __a)
287 template<__allocator_for<container_type> _Alloc>
288 _Flat_set_impl(__sorted_t __s,
289 initializer_list<value_type> __il,
290 const key_compare& __comp,
292 : _Flat_set_impl(__s, __il.
begin(), __il.
end(), __comp, __a)
296 operator=(initializer_list<value_type> __il)
298 auto __guard = _M_make_clear_guard();
301 __guard._M_disable();
302 return static_cast<_Derived&
>(*this);
307 begin() const noexcept
308 {
return _M_cont.begin(); }
312 {
return _M_cont.end(); }
314 const_reverse_iterator
316 {
return const_reverse_iterator(
end()); }
318 const_reverse_iterator
319 rend() const noexcept
320 {
return const_reverse_iterator(
begin()); }
327 cend() const noexcept
330 const_reverse_iterator
334 const_reverse_iterator
335 crend() const noexcept
341 empty() const noexcept
342 {
return _M_cont.empty(); }
345 size() const noexcept
346 {
return _M_cont.size(); }
349 max_size() const noexcept
350 {
return _M_cont.max_size(); }
353 template<
typename _Arg,
typename... _Args>
355 _M_try_emplace(optional<const_iterator> __hint, _Arg&& __arg, _Args&&... __args)
358 auto&& __k = [&] ->
decltype(
auto) {
359 if constexpr (
sizeof...(_Args) == 0
360 && same_as<remove_cvref_t<_Arg>, value_type>)
361 return std::forward<_Arg>(__arg);
363 return value_type(std::forward<_Arg>(__arg),
364 std::forward<_Args>(__args)...);
366 typename container_type::iterator __it;
367 int __r = -1, __s = -1;
368 if (__hint.has_value()
370 || (__r = !_M_comp(__k, (*__hint)[-1])))
372 || (__s = !_M_comp((*__hint)[0], __k))))
374 __it = _M_cont.begin() + (*__hint -
begin());
375 if constexpr (!_Multi)
376 if (__r == 1 && !_M_comp(__it[-1], __k))
377 return {__it - 1,
false};
381 auto __first = _M_cont.begin();
382 auto __last = _M_cont.end();
384 __first += *__hint - _M_cont.begin();
386 __last = __first + (*__hint - _M_cont.begin());
387 if constexpr (_Multi)
391 __it = std::lower_bound(__first, __last, __k, _M_comp);
396 __k, std::not_fn(_M_comp)).base();
399 __it = std::lower_bound(__first, __last, __k, _M_comp);
402 if constexpr (!_Multi)
403 if (__it != _M_cont.end() && !_M_comp(__k, __it[0]))
404 return {__it,
false};
406 auto __guard = _M_make_clear_guard();
407 __it = _M_cont.insert(__it,
std::forward<
decltype(__k)>(__k));
408 __guard._M_disable();
412 template<
typename... _Args>
414 _M_try_emplace(optional<const_iterator> __hint)
415 {
return _M_try_emplace(__hint, value_type()); }
417 template<
typename... _Args>
418 requires is_constructible_v<value_type, _Args...>
420 emplace(_Args&&... __args)
422 auto __r = _M_try_emplace(nullopt, std::forward<_Args>(__args)...);
423 if constexpr (_Multi)
429 template<
typename... _Args>
431 emplace_hint(const_iterator __position, _Args&&... __args)
432 {
return _M_try_emplace(__position, std::forward<_Args>(__args)...).first; }
435 insert(
const value_type& __x)
436 {
return emplace(__x); }
439 insert(value_type&& __x)
443 insert(const_iterator __position,
const value_type& __x)
444 {
return emplace_hint(__position, __x); }
447 insert(const_iterator __position, value_type&& __x)
448 {
return emplace_hint(__position,
std::move(__x)); }
450 template<
typename _Arg>
451 requires is_constructible_v<value_type, _Arg>
454 {
return emplace(std::forward<_Arg>(__x)); }
456 template<
typename _Arg>
457 requires is_constructible_v<value_type, _Arg>
459 insert(const_iterator __position, _Arg&& __x)
460 {
return emplace_hint(__position, std::forward<_Arg>(__x)); }
462 template<__has_input_iter_cat _InputIterator>
464 insert(_InputIterator __first, _InputIterator __last)
466 auto __guard = _M_make_clear_guard();
467 auto __it = _M_cont.insert(_M_cont.end(), __first, __last);
468 std::sort(__it, _M_cont.end(), _M_comp);
469 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
470 if constexpr (!_Multi)
472 __guard._M_disable();
475 template<__has_input_iter_cat _InputIterator>
477 insert(__sorted_t, _InputIterator __first, _InputIterator __last)
479 auto __guard = _M_make_clear_guard();
480 auto __it = _M_cont.insert(_M_cont.end(), __first, __last);
481 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
482 if constexpr (!_Multi)
484 __guard._M_disable();
487 template<__detail::__container_compatible_range<value_type> _Rg>
489 insert_range(_Rg&& __rg)
491 auto __guard = _M_make_clear_guard();
492 typename container_type::iterator __it;
493 if constexpr (
requires { _M_cont.insert_range(_M_cont.end(), __rg); })
494 __it = _M_cont.insert_range(_M_cont.end(), __rg);
495 else if constexpr (ranges::common_range<_Rg>
496 && __has_input_iter_cat<ranges::iterator_t<_Rg>>)
497 __it = _M_cont.insert(_M_cont.end(), ranges::begin(__rg), ranges::end(__rg));
500 size_type __n =
size();
501 auto __first = ranges::begin(__rg);
502 auto __last = ranges::end(__rg);
503 for (; __first != __last; ++__first)
504 _M_cont.emplace_back(*__first);
505 __it = _M_cont.begin() + __n;
507 std::sort(__it, _M_cont.end(), _M_comp);
508 std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
509 if constexpr (!_Multi)
511 __guard._M_disable();
515 insert(initializer_list<value_type> __il)
516 { insert(__il.begin(), __il.end()); }
519 insert(__sorted_t __s, initializer_list<value_type> __il)
520 { insert(__s, __il.begin(), __il.end()); }
525 auto __guard = _M_make_clear_guard();
530 replace(container_type&&
__cont)
532 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(
__cont, _M_comp));
533 auto __guard = _M_make_clear_guard();
535 __guard._M_disable();
539 erase(const_iterator __position)
540 {
return _M_cont.erase(__position); }
543 erase(
const key_type& __x)
544 {
return erase<const key_type&>(__x); }
546 template<
typename _Key2>
547 requires same_as<remove_cvref_t<_Key2>, _Key>
548 || (__transparent_comparator<_Compare>
549 && !is_convertible_v<_Key2, iterator>
550 && !is_convertible_v<_Key2, const_iterator>)
554 auto [__first, __last] = equal_range(std::forward<_Key2>(__x));
555 auto __n = __last - __first;
556 erase(__first, __last);
561 erase(const_iterator __first, const_iterator __last)
562 {
return _M_cont.erase(__first, __last); }
565 swap(_Derived& __x)
noexcept
568 swap(_M_cont, __x._M_cont);
569 swap(_M_comp, __x._M_comp);
590 find(
const key_type& __x)
591 {
return find<key_type>(__x); }
595 find(
const key_type& __x)
const
596 {
return find<key_type>(__x); }
598 template<
typename _Key2>
599 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
602 find(
const _Key2& __x)
604 auto __it = lower_bound(__x);
605 if (__it !=
end() && !_M_comp(__x, *__it))
611 template<
typename _Key2>
612 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
615 find(
const _Key2& __x)
const
617 auto __it = lower_bound(__x);
618 if (__it !=
cend() && !_M_comp(__x, *__it))
626 count(
const key_type& __x)
const
627 {
return count<key_type>(__x); }
629 template<
typename _Key2>
630 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
633 count(
const _Key2& __x)
const
635 if constexpr (!_Multi)
636 return contains<_Key2>(__x);
639 auto [__first, __last] = equal_range(__x);
640 return __last - __first;
646 contains(
const key_type& __x)
const
647 {
return contains<key_type>(__x); }
649 template<
typename _Key2>
650 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
653 contains(
const _Key2& __x)
const
654 {
return find(__x) !=
cend(); }
658 lower_bound(
const key_type& __x)
659 {
return lower_bound<key_type>(__x); }
663 lower_bound(
const key_type& __x)
const
664 {
return lower_bound<key_type>(__x); }
666 template<
typename _Key2>
667 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
670 lower_bound(
const _Key2& __x)
671 {
return std::lower_bound(
begin(),
end(), __x, _M_comp); }
673 template<
typename _Key2>
674 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
677 lower_bound(
const _Key2& __x)
const
678 {
return std::lower_bound(
begin(),
end(), __x, _M_comp); }
682 upper_bound(
const key_type& __x)
683 {
return upper_bound<key_type>(__x); }
687 upper_bound(
const key_type& __x)
const
688 {
return upper_bound<key_type>(__x); }
690 template<
typename _Key2>
691 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
694 upper_bound(
const _Key2& __x)
695 {
return std::upper_bound(
begin(),
end(), __x, _M_comp); }
697 template<
typename _Key2>
698 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
701 upper_bound(
const _Key2& __x)
const
702 {
return std::upper_bound(
begin(),
end(), __x, _M_comp); }
705 pair<iterator, iterator>
706 equal_range(
const key_type& __x)
707 {
return equal_range<key_type>(__x); }
710 pair<const_iterator, const_iterator>
711 equal_range(
const key_type& __x)
const
712 {
return equal_range<key_type>(__x); }
714 template<
typename _Key2>
715 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
717 pair<iterator, iterator>
718 equal_range(
const _Key2& __x)
719 {
return std::equal_range(
begin(),
end(), __x, _M_comp); }
721 template<
typename _Key2>
722 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
724 pair<const_iterator, const_iterator>
725 equal_range(
const _Key2& __x)
const
726 {
return std::equal_range(
begin(),
end(), __x, _M_comp); }
730 operator==(
const _Derived& __x,
const _Derived& __y)
731 {
return std::equal(__x.begin(), __x.end(), __y.begin(), __y.end()); }
733 template<
typename _Up = value_type>
735 friend __detail::__synth3way_t<_Up>
736 operator<=>(
const _Derived& __x,
const _Derived& __y)
739 __y.begin(), __y.end(),
740 __detail::__synth3way);
744 swap(_Derived& __x, _Derived& __y)
noexcept
745 {
return __x.swap(__y); }
747 template<
typename _Predicate>
749 erase_if(_Derived& __c, _Predicate __pred)
751 auto __guard = __c._M_make_clear_guard();
752 auto __first = __c._M_cont.begin();
753 auto __last = __c._M_cont.end();
754 __first = std::remove_if(__first, __last, __pred);
755 auto __n = __last - __first;
756 __c.erase(__first, __last);
757 __guard._M_disable();
762 container_type _M_cont;
763 [[no_unique_address]] _Compare _M_comp;
768 std::sort(_M_cont.begin(), _M_cont.end(), _M_comp);
769 if constexpr (!_Multi)
774 _M_unique()
requires (!_Multi)
778 __key_equiv(key_compare __c) : _M_comp(__c) { }
781 operator()(const_reference __x, const_reference __y)
const
782 {
return !_M_comp(__x, __y) && !_M_comp(__y, __x); }
784 [[no_unique_address]] key_compare _M_comp;
787 auto __first = _M_cont.begin();
788 auto __last = _M_cont.end();
789 __first = std::unique(__first, __last, __key_equiv(_M_comp));
790 _M_cont.erase(__first, __last);
798 template<
typename _Key,
typename _Compare = less<_Key>,
799 typename _KeyContainer = vector<_Key>>
801 :
private _Flat_set_impl<_Key, _Compare, _KeyContainer, false>
803 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, false>;
808 using typename _Impl::key_type;
809 using typename _Impl::value_type;
810 using typename _Impl::key_compare;
811 using typename _Impl::reference;
812 using typename _Impl::const_reference;
813 using typename _Impl::size_type;
814 using typename _Impl::difference_type;
815 using typename _Impl::iterator;
816 using typename _Impl::const_iterator;
817 using typename _Impl::reverse_iterator;
818 using typename _Impl::const_reverse_iterator;
819 using typename _Impl::container_type;
820 using typename _Impl::value_compare;
833 using _Impl::crbegin;
839 using _Impl::max_size;
842 using _Impl::emplace;
843 using _Impl::emplace_hint;
845 using _Impl::insert_range;
846 using _Impl::extract;
847 using _Impl::replace;
853 using _Impl::key_comp;
854 using _Impl::value_comp;
859 using _Impl::contains;
860 using _Impl::lower_bound;
861 using _Impl::upper_bound;
862 using _Impl::equal_range;
865 template<
typename _KeyContainer,
866 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
867 flat_set(_KeyContainer, _Compare = _Compare())
868 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
870 template<
typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
871 flat_set(_KeyContainer, _Alloc)
872 -> flat_set<
typename _KeyContainer::value_type,
873 less<typename _KeyContainer::value_type>, _KeyContainer>;
875 template<
typename _KeyContainer, __not_allocator_like _Compare,
876 __allocator_for<_KeyContainer> _Alloc>
877 flat_set(_KeyContainer, _Compare, _Alloc)
878 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
880 template<
typename _KeyContainer,
881 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
882 flat_set(sorted_unique_t, _KeyContainer, _Compare = _Compare())
883 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
885 template<
typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
886 flat_set(sorted_unique_t, _KeyContainer, _Alloc)
887 -> flat_set<
typename _KeyContainer::value_type,
888 less<typename _KeyContainer::value_type>, _KeyContainer>;
890 template<
typename _KeyContainer, __not_allocator_like _Compare,
891 __allocator_for<_KeyContainer> _Alloc>
892 flat_set(sorted_unique_t, _KeyContainer, _Compare, _Alloc)
893 -> flat_set<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
895 template<__has_input_iter_cat _InputIterator,
896 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
897 flat_set(_InputIterator, _InputIterator, _Compare = _Compare())
898 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
900 template<__has_input_iter_cat _InputIterator,
901 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
902 flat_set(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
903 -> flat_set<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
905 template<ranges::input_range _Rg,
906 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
907 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>>
908 flat_set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
909 -> flat_set<ranges::range_value_t<_Rg>, _Compare,
910 vector<ranges::range_value_t<_Rg>,
911 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
913 template<ranges::input_range _Rg, __allocator_like _Alloc>
914 flat_set(from_range_t, _Rg&&, _Alloc)
915 -> flat_set<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>,
916 vector<ranges::range_value_t<_Rg>,
917 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
919 template<
typename _Key, __not_allocator_like _Compare = less<_Key>>
920 flat_set(initializer_list<_Key>, _Compare = _Compare())
921 -> flat_set<_Key, _Compare>;
923 template<
typename _Key, __not_allocator_like _Compare = less<_Key>>
924 flat_set(sorted_unique_t, initializer_list<_Key>, _Compare = _Compare())
925 -> flat_set<_Key, _Compare>;
927 template<
typename _Key,
typename _Compare,
928 typename _KeyContainer,
typename _Alloc>
929 struct uses_allocator<flat_set<_Key, _Compare, _KeyContainer>, _Alloc>
930 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>>
937 template<
typename _Key,
typename _Compare = less<_Key>,
938 typename _KeyContainer = vector<_Key>>
940 :
private _Flat_set_impl<_Key, _Compare, _KeyContainer, true>
942 using _Impl = _Flat_set_impl<_Key, _Compare, _KeyContainer, true>;
947 using typename _Impl::key_type;
948 using typename _Impl::value_type;
949 using typename _Impl::key_compare;
950 using typename _Impl::reference;
951 using typename _Impl::const_reference;
952 using typename _Impl::size_type;
953 using typename _Impl::difference_type;
954 using typename _Impl::iterator;
955 using typename _Impl::const_iterator;
956 using typename _Impl::reverse_iterator;
957 using typename _Impl::const_reverse_iterator;
958 using typename _Impl::container_type;
959 using typename _Impl::value_compare;
972 using _Impl::crbegin;
978 using _Impl::max_size;
981 using _Impl::emplace;
982 using _Impl::emplace_hint;
984 using _Impl::insert_range;
985 using _Impl::extract;
986 using _Impl::replace;
992 using _Impl::key_comp;
993 using _Impl::value_comp;
998 using _Impl::contains;
999 using _Impl::lower_bound;
1000 using _Impl::upper_bound;
1001 using _Impl::equal_range;
1004 template<
typename _KeyContainer,
1005 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1006 flat_multiset(_KeyContainer, _Compare = _Compare())
1007 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1009 template<
typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1010 flat_multiset(_KeyContainer, _Alloc)
1011 -> flat_multiset<
typename _KeyContainer::value_type,
1012 less<typename _KeyContainer::value_type>, _KeyContainer>;
1014 template<
typename _KeyContainer, __not_allocator_like _Compare,
1015 __allocator_for<_KeyContainer> _Alloc>
1016 flat_multiset(_KeyContainer, _Compare, _Alloc)
1017 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1019 template<
typename _KeyContainer,
1020 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1021 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare = _Compare())
1022 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1024 template<
typename _KeyContainer, __allocator_for<_KeyContainer> _Alloc>
1025 flat_multiset(sorted_equivalent_t, _KeyContainer, _Alloc)
1026 -> flat_multiset<
typename _KeyContainer::value_type,
1027 less<typename _KeyContainer::value_type>, _KeyContainer>;
1029 template<
typename _KeyContainer, __not_allocator_like _Compare,
1030 __allocator_for<_KeyContainer> _Alloc>
1031 flat_multiset(sorted_equivalent_t, _KeyContainer, _Compare, _Alloc)
1032 -> flat_multiset<typename _KeyContainer::value_type, _Compare, _KeyContainer>;
1034 template<__has_input_iter_cat _InputIterator,
1035 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1036 flat_multiset(_InputIterator, _InputIterator, _Compare = _Compare())
1037 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1039 template<__has_input_iter_cat _InputIterator,
1040 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1041 flat_multiset(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
1042 -> flat_multiset<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1044 template<ranges::input_range _Rg,
1045 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
1046 __allocator_like _Alloc = allocator<ranges::range_value_t<_Rg>>>
1047 flat_multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1048 -> flat_multiset<ranges::range_value_t<_Rg>, _Compare,
1049 vector<ranges::range_value_t<_Rg>,
1050 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1052 template<ranges::input_range _Rg, __allocator_like _Alloc>
1053 flat_multiset(from_range_t, _Rg&&, _Alloc)
1054 -> flat_multiset<ranges::range_value_t<_Rg>, less<ranges::range_value_t<_Rg>>,
1055 vector<ranges::range_value_t<_Rg>,
1056 __alloc_rebind<_Alloc, ranges::range_value_t<_Rg>>>>;
1058 template<
typename _Key, __not_allocator_like _Compare = less<_Key>>
1059 flat_multiset(initializer_list<_Key>, _Compare = _Compare())
1060 -> flat_multiset<_Key, _Compare>;
1062 template<
typename _Key, __not_allocator_like _Compare = less<_Key>>
1063 flat_multiset(sorted_equivalent_t, initializer_list<_Key>, _Compare = _Compare())
1064 -> flat_multiset<_Key, _Compare>;
1066 template<
typename _Key,
typename _Compare,
1067 typename _KeyContainer,
typename _Alloc>
1068 struct uses_allocator<flat_multiset<_Key, _Compare, _KeyContainer>, _Alloc>
1069 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>>
1072_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
constexpr auto rbegin(_Container &__cont) noexcept(noexcept(__cont.rbegin())) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto crbegin(const _Container &__cont) noexcept(noexcept(std::rbegin(__cont))) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
constexpr auto rend(_Container &__cont) noexcept(noexcept(__cont.rend())) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
constexpr auto crend(const _Container &__cont) noexcept(noexcept(std::rend(__cont))) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.