30 #ifndef _ITERATOR_CONCEPTS_H
31 #define _ITERATOR_CONCEPTS_H 1
33 #pragma GCC system_header
39 #if __cpp_lib_concepts
40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 struct input_iterator_tag;
45 struct output_iterator_tag;
46 struct forward_iterator_tag;
47 struct bidirectional_iterator_tag;
48 struct random_access_iterator_tag;
49 struct contiguous_iterator_tag;
51 template<
typename _Iterator>
52 struct iterator_traits;
54 template<
typename _Tp> requires is_object_v<_Tp>
55 struct iterator_traits<_Tp*>;
57 template<
typename _Iterator,
typename>
58 struct __iterator_traits;
62 template<
typename _Tp>
63 using __with_ref = _Tp&;
65 template<
typename _Tp>
66 concept __can_reference = requires {
typename __with_ref<_Tp>; };
68 template<
typename _Tp>
69 concept __dereferenceable = requires(_Tp& __t)
71 { *__t } -> __can_reference;
75 template<__detail::__dereferenceable _Tp>
76 using iter_reference_t = decltype(*std::declval<_Tp&>());
80 namespace __cust_imove
84 template<
typename _Tp>
86 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>)
87 && requires(_Tp&& __t) { iter_move(
static_cast<_Tp&&
>(__t)); };
92 template<
typename _Tp>
94 {
using type = iter_reference_t<_Tp>; };
96 template<
typename _Tp>
97 requires __adl_imove<_Tp>
99 {
using type = decltype(iter_move(std::declval<_Tp>())); };
101 template<
typename _Tp>
102 requires (!__adl_imove<_Tp>)
103 && is_lvalue_reference_v<iter_reference_t<_Tp>>
105 {
using type = remove_reference_t<iter_reference_t<_Tp>>&&; };
107 template<
typename _Tp>
108 static constexpr
bool
111 if constexpr (__adl_imove<_Tp>)
112 return noexcept(iter_move(std::declval<_Tp>()));
114 return noexcept(*std::declval<_Tp>());
119 template<std::__detail::__dereferenceable _Tp>
120 using __type =
typename __result<_Tp>::type;
122 template<std::__detail::__dereferenceable _Tp>
123 constexpr __type<_Tp>
124 operator()(_Tp&& __e)
const
125 noexcept(_S_noexcept<_Tp>())
127 if constexpr (__adl_imove<_Tp>)
128 return iter_move(
static_cast<_Tp&&
>(__e));
129 else if constexpr (is_lvalue_reference_v<iter_reference_t<_Tp>>)
130 return static_cast<__type<_Tp>>(*__e);
137 inline namespace __cust
139 inline constexpr __cust_imove::_IMove iter_move{};
143 template<__detail::__dereferenceable _Tp>
145 __can_reference<ranges::__cust_imove::_IMove::__type<_Tp&>>
146 using iter_rvalue_reference_t
147 = ranges::__cust_imove::_IMove::__type<_Tp&>;
149 template<
typename>
struct incrementable_traits { };
151 template<
typename _Tp> requires is_object_v<_Tp>
152 struct incrementable_traits<_Tp*>
153 {
using difference_type = ptrdiff_t; };
155 template<
typename _Iter>
156 struct incrementable_traits<const _Iter>
157 : incrementable_traits<_Iter> { };
159 template<
typename _Tp> requires requires {
typename _Tp::difference_type; }
160 struct incrementable_traits<_Tp>
161 {
using difference_type =
typename _Tp::difference_type; };
163 template<
typename _Tp>
164 requires (!requires {
typename _Tp::difference_type; }
165 && requires(
const _Tp& __a,
const _Tp& __b)
167 requires (!is_void_v<remove_pointer_t<_Tp>>);
168 { __a - __b } -> integral;
170 struct incrementable_traits<_Tp>
172 using difference_type
173 = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>;
176 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
179 struct incrementable_traits<__int128>
180 {
using difference_type = __int128; };
183 struct incrementable_traits<unsigned __int128>
184 {
using difference_type = __int128; };
191 template<
typename _Iter>
192 concept __primary_traits_iter
193 = __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>);
195 template<
typename _Iter,
typename _Tp>
196 struct __iter_traits_impl
197 {
using type = iterator_traits<_Iter>; };
199 template<
typename _Iter,
typename _Tp>
200 requires __primary_traits_iter<_Iter>
201 struct __iter_traits_impl<_Iter, _Tp>
202 {
using type = _Tp; };
205 template<
typename _Iter,
typename _Tp = _Iter>
206 using __iter_traits =
typename __iter_traits_impl<_Iter, _Tp>::type;
208 template<
typename _Tp>
209 using __iter_diff_t =
typename
210 __iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type;
213 template<
typename _Tp>
214 using iter_difference_t = __detail::__iter_diff_t<remove_cvref_t<_Tp>>;
218 template<
typename>
struct __cond_value_type { };
220 template<
typename _Tp> requires is_object_v<_Tp>
221 struct __cond_value_type<_Tp>
222 {
using value_type = remove_cv_t<_Tp>; };
224 template<
typename _Tp>
225 concept __has_member_value_type
226 = requires {
typename _Tp::value_type; };
228 template<
typename _Tp>
229 concept __has_member_element_type
234 template<
typename>
struct indirectly_readable_traits { };
236 template<
typename _Tp>
237 struct indirectly_readable_traits<_Tp*>
238 : __detail::__cond_value_type<_Tp>
241 template<
typename _Iter> requires is_array_v<_Iter>
242 struct indirectly_readable_traits<_Iter>
243 {
using value_type = remove_cv_t<remove_extent_t<_Iter>>; };
245 template<
typename _Iter>
246 struct indirectly_readable_traits<const _Iter>
247 : indirectly_readable_traits<_Iter>
250 template<__detail::__has_member_value_type _Tp>
251 struct indirectly_readable_traits<_Tp>
252 : __detail::__cond_value_type<typename _Tp::value_type>
255 template<__detail::__has_member_element_type _Tp>
256 struct indirectly_readable_traits<_Tp>
257 : __detail::__cond_value_type<typename _Tp::element_type>
262 template<__detail::__has_member_value_type _Tp>
263 requires __detail::__has_member_element_type<_Tp>
264 && same_as<remove_cv_t<typename _Tp::element_type>,
265 remove_cv_t<typename _Tp::value_type>>
266 struct indirectly_readable_traits<_Tp>
267 : __detail::__cond_value_type<typename _Tp::value_type>
272 template<__detail::__has_member_value_type _Tp>
273 requires __detail::__has_member_element_type<_Tp>
274 struct indirectly_readable_traits<_Tp>
279 template<
typename _Tp>
280 using __iter_value_t =
typename
281 __iter_traits<_Tp, indirectly_readable_traits<_Tp>>::value_type;
284 template<
typename _Tp>
285 using iter_value_t = __detail::__iter_value_t<remove_cvref_t<_Tp>>;
291 template<
typename _Iter>
292 concept __cpp17_iterator = requires(_Iter __it)
294 { *__it } -> __can_reference;
295 { ++__it } -> same_as<_Iter&>;
296 { *__it++ } -> __can_reference;
297 } && copyable<_Iter>;
299 template<
typename _Iter>
300 concept __cpp17_input_iterator = __cpp17_iterator<_Iter>
301 && equality_comparable<_Iter>
302 && requires(_Iter __it)
304 typename incrementable_traits<_Iter>::difference_type;
305 typename indirectly_readable_traits<_Iter>::value_type;
306 typename common_reference_t<iter_reference_t<_Iter>&&,
307 typename indirectly_readable_traits<_Iter>::value_type&>;
308 typename common_reference_t<decltype(*__it++)&&,
309 typename indirectly_readable_traits<_Iter>::value_type&>;
310 requires signed_integral<
311 typename incrementable_traits<_Iter>::difference_type>;
314 template<
typename _Iter>
315 concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter>
316 && constructible_from<_Iter>
317 && is_lvalue_reference_v<iter_reference_t<_Iter>>
318 && same_as<remove_cvref_t<iter_reference_t<_Iter>>,
319 typename indirectly_readable_traits<_Iter>::value_type>
320 && requires(_Iter __it)
322 { __it++ } -> convertible_to<const _Iter&>;
323 { *__it++ } -> same_as<iter_reference_t<_Iter>>;
326 template<
typename _Iter>
327 concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter>
328 && requires(_Iter __it)
330 { --__it } -> same_as<_Iter&>;
331 { __it-- } -> convertible_to<const _Iter&>;
332 { *__it-- } -> same_as<iter_reference_t<_Iter>>;
335 template<
typename _Iter>
336 concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter>
337 && totally_ordered<_Iter>
338 && requires(_Iter __it,
339 typename incrementable_traits<_Iter>::difference_type __n)
341 { __it += __n } -> same_as<_Iter&>;
342 { __it -= __n } -> same_as<_Iter&>;
343 { __it + __n } -> same_as<_Iter>;
344 { __n + __it } -> same_as<_Iter>;
345 { __it - __n } -> same_as<_Iter>;
346 { __it - __it } -> same_as<decltype(__n)>;
347 { __it[__n] } -> convertible_to<iter_reference_t<_Iter>>;
350 template<
typename _Iter>
351 concept __iter_with_nested_types = requires {
352 typename _Iter::iterator_category;
353 typename _Iter::value_type;
354 typename _Iter::difference_type;
355 typename _Iter::reference;
358 template<
typename _Iter>
359 concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>;
361 template<
typename _Iter>
362 concept __iter_without_category
363 = !requires {
typename _Iter::iterator_category; };
367 template<
typename _Iterator>
368 requires __detail::__iter_with_nested_types<_Iterator>
369 struct __iterator_traits<_Iterator, void>
372 template<
typename _Iter>
374 {
using type = void; };
376 template<
typename _Iter> requires requires {
typename _Iter::pointer; }
378 {
using type =
typename _Iter::pointer; };
381 using iterator_category =
typename _Iterator::iterator_category;
382 using value_type =
typename _Iterator::value_type;
383 using difference_type =
typename _Iterator::difference_type;
384 using pointer =
typename __ptr<_Iterator>::type;
385 using reference =
typename _Iterator::reference;
388 template<
typename _Iterator>
389 requires __detail::__iter_without_nested_types<_Iterator>
390 && __detail::__cpp17_input_iterator<_Iterator>
391 struct __iterator_traits<_Iterator, void>
394 template<
typename _Iter>
396 {
using type = input_iterator_tag; };
398 template<
typename _Iter>
399 requires requires {
typename _Iter::iterator_category; }
401 {
using type =
typename _Iter::iterator_category; };
403 template<
typename _Iter>
404 requires __detail::__iter_without_category<_Iter>
405 && __detail::__cpp17_randacc_iterator<_Iter>
407 {
using type = random_access_iterator_tag; };
409 template<
typename _Iter>
410 requires __detail::__iter_without_category<_Iter>
411 && __detail::__cpp17_bidi_iterator<_Iter>
413 {
using type = bidirectional_iterator_tag; };
415 template<
typename _Iter>
416 requires __detail::__iter_without_category<_Iter>
417 && __detail::__cpp17_fwd_iterator<_Iter>
419 {
using type = forward_iterator_tag; };
421 template<
typename _Iter>
423 {
using type = void; };
425 template<
typename _Iter> requires requires {
typename _Iter::pointer; }
427 {
using type =
typename _Iter::pointer; };
429 template<
typename _Iter>
430 requires (!requires {
typename _Iter::pointer; }
431 && requires(_Iter& __it) { __it.operator->(); })
433 {
using type = decltype(std::declval<_Iter&>().operator->()); };
435 template<
typename _Iter>
437 {
using type = iter_reference_t<_Iter>; };
439 template<
typename _Iter> requires requires {
typename _Iter::reference; }
441 {
using type =
typename _Iter::reference; };
444 using iterator_category =
typename __cat<_Iterator>::type;
446 =
typename indirectly_readable_traits<_Iterator>::value_type;
447 using difference_type
448 =
typename incrementable_traits<_Iterator>::difference_type;
449 using pointer =
typename __ptr<_Iterator>::type;
450 using reference =
typename __ref<_Iterator>::type;
453 template<
typename _Iterator>
454 requires __detail::__iter_without_nested_types<_Iterator>
455 && __detail::__cpp17_iterator<_Iterator>
456 struct __iterator_traits<_Iterator, void>
459 template<
typename _Iter>
461 {
using type = void; };
463 template<
typename _Iter>
465 {
typename incrementable_traits<_Iter>::difference_type; }
468 using type =
typename incrementable_traits<_Iter>::difference_type;
472 using iterator_category = output_iterator_tag;
473 using value_type = void;
474 using difference_type =
typename __diff<_Iterator>::type;
475 using pointer = void;
476 using reference = void;
481 template<
typename _Iter>
482 struct __iter_concept_impl;
485 template<
typename _Iter>
486 requires requires {
typename __iter_traits<_Iter>::iterator_concept; }
487 struct __iter_concept_impl<_Iter>
488 {
using type =
typename __iter_traits<_Iter>::iterator_concept; };
491 template<
typename _Iter>
492 requires (!requires {
typename __iter_traits<_Iter>::iterator_concept; }
493 && requires {
typename __iter_traits<_Iter>::iterator_category; })
494 struct __iter_concept_impl<_Iter>
495 {
using type =
typename __iter_traits<_Iter>::iterator_category; };
498 template<
typename _Iter>
499 requires (!requires {
typename __iter_traits<_Iter>::iterator_concept; }
500 && !requires {
typename __iter_traits<_Iter>::iterator_category; }
501 && __primary_traits_iter<_Iter>)
502 struct __iter_concept_impl<_Iter>
503 {
using type = random_access_iterator_tag; };
506 template<
typename _Iter>
507 struct __iter_concept_impl
511 template<
typename _Iter>
512 using __iter_concept =
typename __iter_concept_impl<_Iter>::type;
514 template<
typename _In>
515 concept __indirectly_readable_impl = requires
517 typename iter_value_t<_In>;
518 typename iter_reference_t<_In>;
519 typename iter_rvalue_reference_t<_In>;
520 requires same_as<iter_reference_t<const _In>,
521 iter_reference_t<_In>>;
522 requires same_as<iter_rvalue_reference_t<const _In>,
523 iter_rvalue_reference_t<_In>>;
525 && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&>
526 && common_reference_with<iter_reference_t<_In>&&,
527 iter_rvalue_reference_t<_In>&&>
528 && common_reference_with<iter_rvalue_reference_t<_In>&&,
529 const iter_value_t<_In>&>;
534 template<
typename _In>
535 concept indirectly_readable
536 = __detail::__indirectly_readable_impl<remove_cvref_t<_In>>;
538 template<indirectly_readable _Tp>
539 using iter_common_reference_t
540 = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>;
543 template<
typename _Out,
typename _Tp>
544 concept indirectly_writable = requires(_Out&& __o, _Tp&& __t)
546 *__o = std::forward<_Tp>(__t);
547 *std::forward<_Out>(__o) = std::forward<_Tp>(__t);
548 const_cast<const iter_reference_t<_Out>&&
>(*__o)
549 = std::forward<_Tp>(__t);
550 const_cast<const iter_reference_t<_Out>&&
>(*std::forward<_Out>(__o))
551 = std::forward<_Tp>(__t);
554 namespace ranges::__detail
556 class __max_diff_type;
557 class __max_size_type;
559 template<
typename _Tp>
560 concept __is_signed_int128
561 #if __SIZEOF_INT128__
562 = same_as<_Tp, __int128>;
567 template<
typename _Tp>
568 concept __is_unsigned_int128
569 #if __SIZEOF_INT128__
570 = same_as<_Tp, unsigned __int128>;
575 template<
typename _Tp>
576 concept __cv_bool = same_as<const volatile _Tp, const volatile bool>;
578 template<
typename _Tp>
579 concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>;
581 template<
typename _Tp>
582 concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>;
584 template<
typename _Tp>
585 concept __is_integer_like = __integral_nonbool<_Tp>
587 || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>;
589 template<
typename _Tp>
590 concept __is_signed_integer_like = signed_integral<_Tp>
591 || __is_signed_int128<_Tp>
592 || same_as<_Tp, __max_diff_type>;
596 namespace __detail {
using ranges::__detail::__is_signed_integer_like; }
599 template<
typename _Iter>
600 concept weakly_incrementable = default_initializable<_Iter>
602 && requires(_Iter __i)
604 typename iter_difference_t<_Iter>;
605 requires __detail::__is_signed_integer_like<iter_difference_t<_Iter>>;
606 { ++__i } -> same_as<_Iter&>;
610 template<
typename _Iter>
611 concept incrementable = regular<_Iter> && weakly_incrementable<_Iter>
612 && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; };
614 template<
typename _Iter>
615 concept input_or_output_iterator
616 = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
617 && weakly_incrementable<_Iter>;
619 template<
typename _Sent,
typename _Iter>
620 concept sentinel_for = semiregular<_Sent>
621 && input_or_output_iterator<_Iter>
622 && __detail::__weakly_eq_cmp_with<_Sent, _Iter>;
624 template<
typename _Sent,
typename _Iter>
625 inline constexpr
bool disable_sized_sentinel_for =
false;
627 template<
typename _Sent,
typename _Iter>
628 concept sized_sentinel_for = sentinel_for<_Sent, _Iter>
629 && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>>
630 && requires(
const _Iter& __i,
const _Sent& __s)
632 { __s - __i } -> same_as<iter_difference_t<_Iter>>;
633 { __i - __s } -> same_as<iter_difference_t<_Iter>>;
636 template<
typename _Iter>
637 concept input_iterator = input_or_output_iterator<_Iter>
638 && indirectly_readable<_Iter>
639 && requires {
typename __detail::__iter_concept<_Iter>; }
640 && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>;
642 template<
typename _Iter,
typename _Tp>
643 concept output_iterator = input_or_output_iterator<_Iter>
644 && indirectly_writable<_Iter, _Tp>
645 && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); };
647 template<
typename _Iter>
648 concept forward_iterator = input_iterator<_Iter>
649 && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag>
650 && incrementable<_Iter> && sentinel_for<_Iter, _Iter>;
652 template<
typename _Iter>
653 concept bidirectional_iterator = forward_iterator<_Iter>
654 && derived_from<__detail::__iter_concept<_Iter>,
655 bidirectional_iterator_tag>
656 && requires(_Iter __i)
658 { --__i } -> same_as<_Iter&>;
659 { __i-- } -> same_as<_Iter>;
662 template<
typename _Iter>
663 concept random_access_iterator = bidirectional_iterator<_Iter>
664 && derived_from<__detail::__iter_concept<_Iter>,
665 random_access_iterator_tag>
666 && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter>
667 && requires(_Iter __i,
const _Iter __j,
668 const iter_difference_t<_Iter> __n)
670 { __i += __n } -> same_as<_Iter&>;
671 { __j + __n } -> same_as<_Iter>;
672 { __n + __j } -> same_as<_Iter>;
673 { __i -= __n } -> same_as<_Iter&>;
674 { __j - __n } -> same_as<_Iter>;
675 { __j[__n] } -> same_as<iter_reference_t<_Iter>>;
678 template<
typename _Iter>
679 concept contiguous_iterator = random_access_iterator<_Iter>
680 && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag>
681 && is_lvalue_reference_v<iter_reference_t<_Iter>>
682 && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>>
683 && requires(
const _Iter& __i)
685 { std::to_address(__i) }
686 -> same_as<add_pointer_t<iter_reference_t<_Iter>>>;
693 template<
typename _Fn,
typename _Iter>
694 concept indirectly_unary_invocable = indirectly_readable<_Iter>
695 && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&>
696 && invocable<_Fn&, iter_reference_t<_Iter>>
697 && invocable<_Fn&, iter_common_reference_t<_Iter>>
698 && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
699 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
701 template<
typename _Fn,
typename _Iter>
702 concept indirectly_regular_unary_invocable = indirectly_readable<_Iter>
703 && copy_constructible<_Fn>
704 && regular_invocable<_Fn&, iter_value_t<_Iter>&>
705 && regular_invocable<_Fn&, iter_reference_t<_Iter>>
706 && regular_invocable<_Fn&, iter_common_reference_t<_Iter>>
707 && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
708 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
710 template<
typename _Fn,
typename _Iter>
711 concept indirect_unary_predicate = indirectly_readable<_Iter>
712 && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&>
713 && predicate<_Fn&, iter_reference_t<_Iter>>
714 && predicate<_Fn&, iter_common_reference_t<_Iter>>;
716 template<
typename _Fn,
typename _I1,
typename _I2>
717 concept indirect_binary_predicate
718 = indirectly_readable<_I1> && indirectly_readable<_I2>
719 && copy_constructible<_Fn>
720 && predicate<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
721 && predicate<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
722 && predicate<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
723 && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
724 && predicate<_Fn&, iter_common_reference_t<_I1>,
725 iter_common_reference_t<_I2>>;
727 template<
typename _Fn,
typename _I1,
typename _I2 = _I1>
728 concept indirect_equivalence_relation
729 = indirectly_readable<_I1> && indirectly_readable<_I2>
730 && copy_constructible<_Fn>
731 && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
732 && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
733 && equivalence_relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
734 && equivalence_relation<_Fn&, iter_reference_t<_I1>,
735 iter_reference_t<_I2>>
736 && equivalence_relation<_Fn&, iter_common_reference_t<_I1>,
737 iter_common_reference_t<_I2>>;
739 template<
typename _Fn,
typename _I1,
typename _I2 = _I1>
740 concept indirect_strict_weak_order
741 = indirectly_readable<_I1> && indirectly_readable<_I2>
742 && copy_constructible<_Fn>
743 && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
744 && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
745 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
746 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
747 && strict_weak_order<_Fn&, iter_common_reference_t<_I1>,
748 iter_common_reference_t<_I2>>;
750 template<
typename _Fn,
typename... _Is>
751 requires (indirectly_readable<_Is> && ...)
752 && invocable<_Fn, iter_reference_t<_Is>...>
753 using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Is>...>;
756 template<indirectly_readable _Iter,
757 indirectly_regular_unary_invocable<_Iter> _Proj>
760 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
762 indirect_result_t<_Proj&, _Iter>
operator*()
const;
765 template<weakly_incrementable _Iter,
typename _Proj>
766 struct incrementable_traits<projected<_Iter, _Proj>>
767 {
using difference_type = iter_difference_t<_Iter>; };
773 template<
typename _In,
typename _Out>
774 concept indirectly_movable = indirectly_readable<_In>
775 && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
777 template<
typename _In,
typename _Out>
778 concept indirectly_movable_storable = indirectly_movable<_In, _Out>
779 && indirectly_writable<_Out, iter_value_t<_In>>
780 && movable<iter_value_t<_In>>
781 && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>
782 && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
785 template<
typename _In,
typename _Out>
786 concept indirectly_copyable = indirectly_readable<_In>
787 && indirectly_writable<_Out, iter_reference_t<_In>>;
789 template<
typename _In,
typename _Out>
790 concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>
791 && indirectly_writable<_Out, iter_value_t<_In>&>
792 && indirectly_writable<_Out, const iter_value_t<_In>&>
793 && indirectly_writable<_Out, iter_value_t<_In>&&>
794 && indirectly_writable<_Out, const iter_value_t<_In>&&>
795 && copyable<iter_value_t<_In>>
796 && constructible_from<iter_value_t<_In>, iter_reference_t<_In>>
797 && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
801 namespace __cust_iswap
803 template<
typename _It1,
typename _It2>
804 void iter_swap(_It1, _It2) =
delete;
806 template<
typename _Tp,
typename _Up>
808 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>
809 || std::__detail::__class_or_enum<remove_reference_t<_Up>>)
810 && requires(_Tp&& __t, _Up&& __u) {
811 iter_swap(
static_cast<_Tp&&
>(__t),
static_cast<_Up&&
>(__u));
814 template<
typename _Xp,
typename _Yp>
815 constexpr iter_value_t<_Xp>
816 __iter_exchange_move(_Xp&& __x, _Yp&& __y)
817 noexcept(noexcept(iter_value_t<_Xp>(iter_move(__x)))
818 && noexcept(*__x = iter_move(__y)))
820 iter_value_t<_Xp> __old_value(iter_move(__x));
821 *__x = iter_move(__y);
828 template<
typename _Tp,
typename _Up>
829 static constexpr
bool
832 if constexpr (__adl_iswap<_Tp, _Up>)
833 return noexcept(iter_swap(std::declval<_Tp>(),
834 std::declval<_Up>()));
835 else if constexpr (indirectly_readable<_Tp>
836 && indirectly_readable<_Up>
837 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
838 return noexcept(ranges::
swap(*
std::declval<_Tp>(),
839 *
std::declval<_Up>()));
841 return noexcept(*
std::declval<_Tp>()
842 = __iter_exchange_move(
std::declval<_Up>(),
843 std::declval<_Tp>()));
847 template<typename _Tp, typename _Up>
848 requires __adl_iswap<_Tp, _Up>
851 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
852 || (indirectly_movable_storable<_Tp, _Up>
853 && indirectly_movable_storable<_Up, _Tp>)
855 operator()(_Tp&& __e1, _Up&& __e2) const
856 noexcept(_S_noexcept<_Tp, _Up>())
858 if constexpr (__adl_iswap<_Tp, _Up>)
859 iter_swap(
static_cast<_Tp&&
>(__e1),
static_cast<_Up&&
>(__e2));
860 else if constexpr (indirectly_readable<_Tp>
861 && indirectly_readable<_Up>
862 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
863 ranges::
swap(*__e1, *__e2);
865 *__e1 = __iter_exchange_move(__e2, __e1);
870 inline namespace __cust
872 inline constexpr __cust_iswap::_IterSwap iter_swap{};
878 template<
typename _I1,
typename _I2 = _I1>
879 concept indirectly_swappable
880 = indirectly_readable<_I1> && indirectly_readable<_I2>
881 && requires(
const _I1 __i1,
const _I2 __i2)
883 ranges::iter_swap(__i1, __i1);
884 ranges::iter_swap(__i2, __i2);
885 ranges::iter_swap(__i1, __i2);
886 ranges::iter_swap(__i2, __i1);
890 template<
typename _I1,
typename _I2,
typename _Rel,
typename _P1 = identity,
891 typename _P2 = identity>
892 concept indirectly_comparable
893 = indirect_binary_predicate<_Rel, projected<_I1, _P1>,
894 projected<_I2, _P2>>;
897 template<
typename _Iter>
898 concept permutable = forward_iterator<_Iter>
899 && indirectly_movable_storable<_Iter, _Iter>
900 && indirectly_swappable<_Iter, _Iter>;
903 template<
typename _I1,
typename _I2,
typename _Out,
904 typename _Rel = ranges::less,
typename _P1 = identity,
905 typename _P2 = identity>
906 concept mergeable = input_iterator<_I1> && input_iterator<_I2>
907 && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out>
908 && indirectly_copyable<_I2, _Out>
909 && indirect_strict_weak_order<_Rel, projected<_I1, _P1>,
910 projected<_I2, _P2>>;
913 template<
typename _Iter,
typename _Rel = ranges::less,
914 typename _Proj = identity>
915 concept sortable = permutable<_Iter>
916 && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>;
918 struct unreachable_sentinel_t
920 template<weakly_incrementable _It>
921 friend constexpr
bool
922 operator==(unreachable_sentinel_t,
const _It&) noexcept
926 inline constexpr unreachable_sentinel_t unreachable_sentinel{};
928 struct default_sentinel_t { };
929 inline constexpr default_sentinel_t default_sentinel{};
933 template<
typename _Tp>
934 constexpr decay_t<_Tp>
935 __decay_copy(_Tp&& __t)
936 noexcept(is_nothrow_convertible_v<_Tp, decay_t<_Tp>>)
937 {
return std::forward<_Tp>(__t); }
939 template<
typename _Tp>
940 concept __member_begin = requires(_Tp& __t)
942 { __detail::__decay_copy(__t.begin()) } -> input_or_output_iterator;
945 void begin(
auto&) =
delete;
946 void begin(
const auto&) =
delete;
948 template<
typename _Tp>
949 concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>>
950 && requires(_Tp& __t)
952 { __detail::__decay_copy(
begin(__t)) } -> input_or_output_iterator;
957 template<
typename _Tp>
958 requires is_array_v<_Tp> || __member_begin<_Tp&> || __adl_begin<_Tp&>
960 __ranges_begin(_Tp& __t)
962 if constexpr (is_array_v<_Tp>)
964 static_assert(
sizeof(remove_all_extents_t<_Tp>) != 0,
965 "not array of incomplete type");
968 else if constexpr (__member_begin<_Tp&>)
975 template<
typename _Tp>
977 = decltype(__detail::__ranges_begin(std::declval<_Tp&>()));
981 _GLIBCXX_END_NAMESPACE_VERSION
983 #endif // C++20 library concepts
984 #endif // _ITERATOR_CONCEPTS_H