1 // Concepts and traits for use with iterators -*- C++ -*-
3 // Copyright (C) 2019-2024 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/iterator_concepts.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{iterator}
30 #ifndef _ITERATOR_CONCEPTS_H
31 #define _ITERATOR_CONCEPTS_H 1
33 #pragma GCC system_header
35 #if __cplusplus >= 202002L
37 #include <bits/ptr_traits.h> // to_address
38 #include <bits/ranges_cmp.h> // identity, ranges::less
40 namespace std
_GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 /** A sentinel type that can be used to check for the end of a range.
46 * For some iterator types the past-the-end sentinel value is independent
47 * of the underlying sequence, and a default sentinel can be used with them.
48 * For example, a `std::counted_iterator` keeps a count of how many elements
49 * remain, and so checking for the past-the-end value only requires checking
50 * if that count has reached zero. A past-the-end `std::istream_iterator` is
51 * equal to the default-constructed value, which can be easily checked.
53 * Comparing iterators of these types to `std::default_sentinel` is a
54 * convenient way to check if the end has been reached.
58 struct default_sentinel_t
{ };
60 /// A default sentinel value.
61 inline constexpr default_sentinel_t default_sentinel
{};
63 #if __cpp_lib_concepts
64 struct input_iterator_tag
;
65 struct output_iterator_tag
;
66 struct forward_iterator_tag
;
67 struct bidirectional_iterator_tag
;
68 struct random_access_iterator_tag
;
69 struct contiguous_iterator_tag
;
71 template<typename _Iterator
>
72 struct iterator_traits
;
74 template<typename _Tp
> requires is_object_v
<_Tp
>
75 struct iterator_traits
<_Tp
*>;
77 template<typename _Iterator
, typename
>
78 struct __iterator_traits
;
82 template<typename _Tp
>
83 using __with_ref
= _Tp
&;
85 template<typename _Tp
>
86 concept __can_reference
= requires
{ typename __with_ref
<_Tp
>; };
88 template<typename _Tp
>
89 concept __dereferenceable
= requires(_Tp
& __t
)
91 { *__t
} -> __can_reference
;
93 } // namespace __detail
95 template<__detail::__dereferenceable _Tp
>
96 using iter_reference_t
= decltype(*std::declval
<_Tp
&>());
100 /// @cond undocumented
103 void iter_move() = delete;
105 template<typename _Tp
>
107 = (std::__detail::__class_or_enum
<remove_reference_t
<_Tp
>>)
108 && requires(_Tp
&& __t
) { iter_move(static_cast<_Tp
&&>(__t
)); };
113 template<typename _Tp
>
115 { using type
= iter_reference_t
<_Tp
>; };
117 template<typename _Tp
>
118 requires __adl_imove
<_Tp
>
120 { using type
= decltype(iter_move(std::declval
<_Tp
>())); };
122 template<typename _Tp
>
123 requires (!__adl_imove
<_Tp
>)
124 && is_lvalue_reference_v
<iter_reference_t
<_Tp
>>
126 { using type
= remove_reference_t
<iter_reference_t
<_Tp
>>&&; };
128 template<typename _Tp
>
129 static constexpr bool
132 if constexpr (__adl_imove
<_Tp
>)
133 return noexcept(iter_move(std::declval
<_Tp
>()));
135 return noexcept(*std::declval
<_Tp
>());
139 // The result type of iter_move(std::declval<_Tp>())
140 template<std::__detail::__dereferenceable _Tp
>
141 using __type
= typename __result
<_Tp
>::type
;
143 template<std::__detail::__dereferenceable _Tp
>
145 constexpr __type
<_Tp
>
146 operator()(_Tp
&& __e
) const
147 noexcept(_S_noexcept
<_Tp
>())
149 if constexpr (__adl_imove
<_Tp
>)
150 return iter_move(static_cast<_Tp
&&>(__e
));
151 else if constexpr (is_lvalue_reference_v
<iter_reference_t
<_Tp
>>)
152 return static_cast<__type
<_Tp
>>(*__e
);
157 } // namespace __imove
160 inline namespace _Cpo
{
161 inline constexpr __imove::_IterMove iter_move
{};
163 } // namespace ranges
165 template<__detail::__dereferenceable _Tp
>
166 requires
__detail::__can_reference
<ranges::__imove::_IterMove::__type
<_Tp
&>>
167 using iter_rvalue_reference_t
= ranges::__imove::_IterMove::__type
<_Tp
&>;
169 template<typename
> struct incrementable_traits
{ };
171 template<typename _Tp
> requires is_object_v
<_Tp
>
172 struct incrementable_traits
<_Tp
*>
173 { using difference_type
= ptrdiff_t; };
175 template<typename _Iter
>
176 struct incrementable_traits
<const _Iter
>
177 : incrementable_traits
<_Iter
> { };
179 template<typename _Tp
> requires requires
{ typename
_Tp::difference_type
; }
180 struct incrementable_traits
<_Tp
>
181 { using difference_type
= typename
_Tp::difference_type
; };
183 template<typename _Tp
>
184 requires (!requires
{ typename
_Tp::difference_type
; }
185 && requires(const _Tp
& __a
, const _Tp
& __b
)
186 { { __a
- __b
} -> integral
; })
187 struct incrementable_traits
<_Tp
>
189 using difference_type
190 = make_signed_t
<decltype(std::declval
<_Tp
>() - std::declval
<_Tp
>())>;
193 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
194 // __int128 is incrementable even if !integral<__int128>
196 struct incrementable_traits
<__int128
>
197 { using difference_type
= __int128
; };
200 struct incrementable_traits
<unsigned __int128
>
201 { using difference_type
= __int128
; };
206 // An iterator such that iterator_traits<_Iter> names a specialization
207 // generated from the primary template.
208 template<typename _Iter
>
209 concept __primary_traits_iter
210 = __is_base_of(__iterator_traits
<_Iter
, void>, iterator_traits
<_Iter
>);
212 template<typename _Iter
, typename _Tp
>
213 struct __iter_traits_impl
214 { using type
= iterator_traits
<_Iter
>; };
216 template<typename _Iter
, typename _Tp
>
217 requires __primary_traits_iter
<_Iter
>
218 struct __iter_traits_impl
<_Iter
, _Tp
>
219 { using type
= _Tp
; };
222 template<typename _Iter
, typename _Tp
= _Iter
>
223 using __iter_traits
= typename __iter_traits_impl
<_Iter
, _Tp
>::type
;
225 template<typename _Tp
>
226 using __iter_diff_t
= typename
227 __iter_traits
<_Tp
, incrementable_traits
<_Tp
>>::difference_type
;
228 } // namespace __detail
230 template<typename _Tp
>
231 using iter_difference_t
= __detail::__iter_diff_t
<remove_cvref_t
<_Tp
>>;
235 template<typename
> struct __cond_value_type
{ };
237 template<typename _Tp
> requires is_object_v
<_Tp
>
238 struct __cond_value_type
<_Tp
>
239 { using value_type
= remove_cv_t
<_Tp
>; };
241 template<typename _Tp
>
242 concept __has_member_value_type
243 = requires
{ typename
_Tp::value_type
; };
245 template<typename _Tp
>
246 concept __has_member_element_type
247 = requires
{ typename
_Tp::element_type
; };
249 } // namespace __detail
251 template<typename
> struct indirectly_readable_traits
{ };
253 template<typename _Tp
>
254 struct indirectly_readable_traits
<_Tp
*>
255 : __detail::__cond_value_type
<_Tp
>
258 template<typename _Iter
> requires is_array_v
<_Iter
>
259 struct indirectly_readable_traits
<_Iter
>
260 { using value_type
= remove_cv_t
<remove_extent_t
<_Iter
>>; };
262 template<typename _Iter
>
263 struct indirectly_readable_traits
<const _Iter
>
264 : indirectly_readable_traits
<_Iter
>
267 template<__detail::__has_member_value_type _Tp
>
268 struct indirectly_readable_traits
<_Tp
>
269 : __detail::__cond_value_type
<typename
_Tp::value_type
>
272 template<__detail::__has_member_element_type _Tp
>
273 struct indirectly_readable_traits
<_Tp
>
274 : __detail::__cond_value_type
<typename
_Tp::element_type
>
277 // _GLIBCXX_RESOLVE_LIB_DEFECTS
278 // 3446. indirectly_readable_traits ambiguity for types with both [...]
279 template<__detail::__has_member_value_type _Tp
>
280 requires
__detail::__has_member_element_type
<_Tp
>
281 && same_as
<remove_cv_t
<typename
_Tp::element_type
>,
282 remove_cv_t
<typename
_Tp::value_type
>>
283 struct indirectly_readable_traits
<_Tp
>
284 : __detail::__cond_value_type
<typename
_Tp::value_type
>
287 // _GLIBCXX_RESOLVE_LIB_DEFECTS
288 // 3541. indirectly_readable_traits should be SFINAE-friendly for all types
289 template<__detail::__has_member_value_type _Tp
>
290 requires
__detail::__has_member_element_type
<_Tp
>
291 struct indirectly_readable_traits
<_Tp
>
296 template<typename _Tp
>
297 using __iter_value_t
= typename
298 __iter_traits
<_Tp
, indirectly_readable_traits
<_Tp
>>::value_type
;
299 } // namespace __detail
301 template<typename _Tp
>
302 using iter_value_t
= __detail::__iter_value_t
<remove_cvref_t
<_Tp
>>;
306 // _GLIBCXX_RESOLVE_LIB_DEFECTS
307 // 3420. cpp17-iterator should check [type] looks like an iterator first
308 template<typename _Iter
>
309 concept __cpp17_iterator
= requires(_Iter __it
)
311 { *__it
} -> __can_reference
;
312 { ++__it
} -> same_as
<_Iter
&>;
313 { *__it
++ } -> __can_reference
;
314 } && copyable
<_Iter
>;
316 template<typename _Iter
>
317 concept __cpp17_input_iterator
= __cpp17_iterator
<_Iter
>
318 && equality_comparable
<_Iter
>
319 && requires(_Iter __it
)
321 typename incrementable_traits
<_Iter
>::difference_type
;
322 typename indirectly_readable_traits
<_Iter
>::value_type
;
323 typename common_reference_t
<iter_reference_t
<_Iter
>&&,
324 typename indirectly_readable_traits
<_Iter
>::value_type
&>;
325 typename common_reference_t
<decltype(*__it
++)&&,
326 typename indirectly_readable_traits
<_Iter
>::value_type
&>;
327 requires signed_integral
<
328 typename incrementable_traits
<_Iter
>::difference_type
>;
331 template<typename _Iter
>
332 concept __cpp17_fwd_iterator
= __cpp17_input_iterator
<_Iter
>
333 && constructible_from
<_Iter
>
334 && is_lvalue_reference_v
<iter_reference_t
<_Iter
>>
335 && same_as
<remove_cvref_t
<iter_reference_t
<_Iter
>>,
336 typename indirectly_readable_traits
<_Iter
>::value_type
>
337 && requires(_Iter __it
)
339 { __it
++ } -> convertible_to
<const _Iter
&>;
340 { *__it
++ } -> same_as
<iter_reference_t
<_Iter
>>;
343 template<typename _Iter
>
344 concept __cpp17_bidi_iterator
= __cpp17_fwd_iterator
<_Iter
>
345 && requires(_Iter __it
)
347 { --__it
} -> same_as
<_Iter
&>;
348 { __it
-- } -> convertible_to
<const _Iter
&>;
349 { *__it
-- } -> same_as
<iter_reference_t
<_Iter
>>;
352 template<typename _Iter
>
353 concept __cpp17_randacc_iterator
= __cpp17_bidi_iterator
<_Iter
>
354 && totally_ordered
<_Iter
>
355 && requires(_Iter __it
,
356 typename incrementable_traits
<_Iter
>::difference_type __n
)
358 { __it
+= __n
} -> same_as
<_Iter
&>;
359 { __it
-= __n
} -> same_as
<_Iter
&>;
360 { __it
+ __n
} -> same_as
<_Iter
>;
361 { __n
+ __it
} -> same_as
<_Iter
>;
362 { __it
- __n
} -> same_as
<_Iter
>;
363 { __it
- __it
} -> same_as
<decltype(__n
)>;
364 { __it
[__n
] } -> convertible_to
<iter_reference_t
<_Iter
>>;
367 template<typename _Iter
>
368 concept __iter_with_nested_types
= requires
{
369 typename
_Iter::iterator_category
;
370 typename
_Iter::value_type
;
371 typename
_Iter::difference_type
;
372 typename
_Iter::reference
;
375 template<typename _Iter
>
376 concept __iter_without_nested_types
= !__iter_with_nested_types
<_Iter
>;
378 template<typename _Iter
>
379 concept __iter_without_category
380 = !requires
{ typename
_Iter::iterator_category
; };
382 } // namespace __detail
384 template<typename _Iterator
>
385 requires
__detail::__iter_with_nested_types
<_Iterator
>
386 struct __iterator_traits
<_Iterator
, void>
389 template<typename _Iter
>
391 { using type
= void; };
393 template<typename _Iter
> requires requires
{ typename
_Iter::pointer
; }
395 { using type
= typename
_Iter::pointer
; };
398 using iterator_category
= typename
_Iterator::iterator_category
;
399 using value_type
= typename
_Iterator::value_type
;
400 using difference_type
= typename
_Iterator::difference_type
;
401 using pointer
= typename __ptr
<_Iterator
>::type
;
402 using reference
= typename
_Iterator::reference
;
405 template<typename _Iterator
>
406 requires
__detail::__iter_without_nested_types
<_Iterator
>
407 && __detail::__cpp17_input_iterator
<_Iterator
>
408 struct __iterator_traits
<_Iterator
, void>
411 template<typename _Iter
>
413 { using type
= input_iterator_tag
; };
415 template<typename _Iter
>
416 requires requires
{ typename
_Iter::iterator_category
; }
418 { using type
= typename
_Iter::iterator_category
; };
420 template<typename _Iter
>
421 requires
__detail::__iter_without_category
<_Iter
>
422 && __detail::__cpp17_randacc_iterator
<_Iter
>
424 { using type
= random_access_iterator_tag
; };
426 template<typename _Iter
>
427 requires
__detail::__iter_without_category
<_Iter
>
428 && __detail::__cpp17_bidi_iterator
<_Iter
>
430 { using type
= bidirectional_iterator_tag
; };
432 template<typename _Iter
>
433 requires
__detail::__iter_without_category
<_Iter
>
434 && __detail::__cpp17_fwd_iterator
<_Iter
>
436 { using type
= forward_iterator_tag
; };
438 template<typename _Iter
>
440 { using type
= void; };
442 template<typename _Iter
> requires requires
{ typename
_Iter::pointer
; }
444 { using type
= typename
_Iter::pointer
; };
446 template<typename _Iter
>
447 requires (!requires
{ typename
_Iter::pointer
; }
448 && requires(_Iter
& __it
) { __it
.operator->(); })
450 { using type
= decltype(std::declval
<_Iter
&>().operator->()); };
452 template<typename _Iter
>
454 { using type
= iter_reference_t
<_Iter
>; };
456 template<typename _Iter
> requires requires
{ typename
_Iter::reference
; }
458 { using type
= typename
_Iter::reference
; };
461 using iterator_category
= typename __cat
<_Iterator
>::type
;
463 = typename indirectly_readable_traits
<_Iterator
>::value_type
;
464 using difference_type
465 = typename incrementable_traits
<_Iterator
>::difference_type
;
466 using pointer
= typename __ptr
<_Iterator
>::type
;
467 using reference
= typename __ref
<_Iterator
>::type
;
470 template<typename _Iterator
>
471 requires
__detail::__iter_without_nested_types
<_Iterator
>
472 && __detail::__cpp17_iterator
<_Iterator
>
473 struct __iterator_traits
<_Iterator
, void>
476 template<typename _Iter
>
478 { using type
= void; };
480 template<typename _Iter
>
482 { typename incrementable_traits
<_Iter
>::difference_type
; }
485 using type
= typename incrementable_traits
<_Iter
>::difference_type
;
489 using iterator_category
= output_iterator_tag
;
490 using value_type
= void;
491 using difference_type
= typename __diff
<_Iterator
>::type
;
492 using pointer
= void;
493 using reference
= void;
498 template<typename _Iter
>
499 struct __iter_concept_impl
;
501 // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid.
502 template<typename _Iter
>
503 requires requires
{ typename __iter_traits
<_Iter
>::iterator_concept
; }
504 struct __iter_concept_impl
<_Iter
>
505 { using type
= typename __iter_traits
<_Iter
>::iterator_concept
; };
507 // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid.
508 template<typename _Iter
>
509 requires (!requires
{ typename __iter_traits
<_Iter
>::iterator_concept
; }
510 && requires
{ typename __iter_traits
<_Iter
>::iterator_category
; })
511 struct __iter_concept_impl
<_Iter
>
512 { using type
= typename __iter_traits
<_Iter
>::iterator_category
; };
514 // Otherwise, random_access_tag if iterator_traits<I> is not specialized.
515 template<typename _Iter
>
516 requires (!requires
{ typename __iter_traits
<_Iter
>::iterator_concept
; }
517 && !requires
{ typename __iter_traits
<_Iter
>::iterator_category
; }
518 && __primary_traits_iter
<_Iter
>)
519 struct __iter_concept_impl
<_Iter
>
520 { using type
= random_access_iterator_tag
; };
522 // Otherwise, there is no ITER_CONCEPT(I) type.
523 template<typename _Iter
>
524 struct __iter_concept_impl
528 template<typename _Iter
>
529 using __iter_concept
= typename __iter_concept_impl
<_Iter
>::type
;
531 template<typename _In
>
532 concept __indirectly_readable_impl
= requires
534 typename iter_value_t
<_In
>;
535 typename iter_reference_t
<_In
>;
536 typename iter_rvalue_reference_t
<_In
>;
537 requires same_as
<iter_reference_t
<const _In
>,
538 iter_reference_t
<_In
>>;
539 requires same_as
<iter_rvalue_reference_t
<const _In
>,
540 iter_rvalue_reference_t
<_In
>>;
542 && common_reference_with
<iter_reference_t
<_In
>&&, iter_value_t
<_In
>&>
543 && common_reference_with
<iter_reference_t
<_In
>&&,
544 iter_rvalue_reference_t
<_In
>&&>
545 && common_reference_with
<iter_rvalue_reference_t
<_In
>&&,
546 const iter_value_t
<_In
>&>;
548 } // namespace __detail
550 /// Requirements for types that are readable by applying operator*.
551 template<typename _In
>
552 concept indirectly_readable
553 = __detail::__indirectly_readable_impl
<remove_cvref_t
<_In
>>;
555 template<indirectly_readable _Tp
>
556 using iter_common_reference_t
557 = common_reference_t
<iter_reference_t
<_Tp
>, iter_value_t
<_Tp
>&>;
559 /// Requirements for writing a value into an iterator's referenced object.
560 template<typename _Out
, typename _Tp
>
561 concept indirectly_writable
= requires(_Out
&& __o
, _Tp
&& __t
)
563 *__o
= std::forward
<_Tp
>(__t
);
564 *std::forward
<_Out
>(__o
) = std::forward
<_Tp
>(__t
);
565 const_cast<const iter_reference_t
<_Out
>&&>(*__o
)
566 = std::forward
<_Tp
>(__t
);
567 const_cast<const iter_reference_t
<_Out
>&&>(*std::forward
<_Out
>(__o
))
568 = std::forward
<_Tp
>(__t
);
571 namespace ranges::__detail
573 class __max_diff_type
;
574 class __max_size_type
;
577 template<typename _Tp
>
578 concept __is_signed_int128
579 #if __SIZEOF_INT128__
580 = same_as
<_Tp
, __int128
>;
586 template<typename _Tp
>
587 concept __is_unsigned_int128
588 #if __SIZEOF_INT128__
589 = same_as
<_Tp
, unsigned __int128
>;
594 template<typename _Tp
>
595 concept __cv_bool
= same_as
<const volatile _Tp
, const volatile bool>;
597 template<typename _Tp
>
598 concept __integral_nonbool
= integral
<_Tp
> && !__cv_bool
<_Tp
>;
600 template<typename _Tp
>
601 concept __is_int128
= __is_signed_int128
<_Tp
> || __is_unsigned_int128
<_Tp
>;
603 template<typename _Tp
>
604 concept __is_integer_like
= __integral_nonbool
<_Tp
>
606 || same_as
<_Tp
, __max_diff_type
> || same_as
<_Tp
, __max_size_type
>;
608 template<typename _Tp
>
609 concept __is_signed_integer_like
= signed_integral
<_Tp
>
610 || __is_signed_int128
<_Tp
>
611 || same_as
<_Tp
, __max_diff_type
>;
613 } // namespace ranges::__detail
615 namespace __detail
{ using ranges::__detail::__is_signed_integer_like
; }
617 /// Requirements on types that can be incremented with ++.
618 template<typename _Iter
>
619 concept weakly_incrementable
= movable
<_Iter
>
620 && requires(_Iter __i
)
622 typename iter_difference_t
<_Iter
>;
623 requires
__detail::__is_signed_integer_like
<iter_difference_t
<_Iter
>>;
624 { ++__i
} -> same_as
<_Iter
&>;
628 template<typename _Iter
>
629 concept incrementable
= regular
<_Iter
> && weakly_incrementable
<_Iter
>
630 && requires(_Iter __i
) { { __i
++ } -> same_as
<_Iter
>; };
632 template<typename _Iter
>
633 concept input_or_output_iterator
634 = requires(_Iter __i
) { { *__i
} -> __detail::__can_reference
; }
635 && weakly_incrementable
<_Iter
>;
637 template<typename _Sent
, typename _Iter
>
638 concept sentinel_for
= semiregular
<_Sent
>
639 && input_or_output_iterator
<_Iter
>
640 && __detail::__weakly_eq_cmp_with
<_Sent
, _Iter
>;
642 template<typename _Sent
, typename _Iter
>
643 inline constexpr bool disable_sized_sentinel_for
= false;
645 template<typename _Sent
, typename _Iter
>
646 concept sized_sentinel_for
= sentinel_for
<_Sent
, _Iter
>
647 && !disable_sized_sentinel_for
<remove_cv_t
<_Sent
>, remove_cv_t
<_Iter
>>
648 && requires(const _Iter
& __i
, const _Sent
& __s
)
650 { __s
- __i
} -> same_as
<iter_difference_t
<_Iter
>>;
651 { __i
- __s
} -> same_as
<iter_difference_t
<_Iter
>>;
654 template<typename _Iter
>
655 concept input_iterator
= input_or_output_iterator
<_Iter
>
656 && indirectly_readable
<_Iter
>
657 && requires
{ typename
__detail::__iter_concept
<_Iter
>; }
658 && derived_from
<__detail::__iter_concept
<_Iter
>, input_iterator_tag
>;
660 template<typename _Iter
, typename _Tp
>
661 concept output_iterator
= input_or_output_iterator
<_Iter
>
662 && indirectly_writable
<_Iter
, _Tp
>
663 && requires(_Iter __i
, _Tp
&& __t
) { *__i
++ = std::forward
<_Tp
>(__t
); };
665 template<typename _Iter
>
666 concept forward_iterator
= input_iterator
<_Iter
>
667 && derived_from
<__detail::__iter_concept
<_Iter
>, forward_iterator_tag
>
668 && incrementable
<_Iter
> && sentinel_for
<_Iter
, _Iter
>;
670 template<typename _Iter
>
671 concept bidirectional_iterator
= forward_iterator
<_Iter
>
672 && derived_from
<__detail::__iter_concept
<_Iter
>,
673 bidirectional_iterator_tag
>
674 && requires(_Iter __i
)
676 { --__i
} -> same_as
<_Iter
&>;
677 { __i
-- } -> same_as
<_Iter
>;
680 template<typename _Iter
>
681 concept random_access_iterator
= bidirectional_iterator
<_Iter
>
682 && derived_from
<__detail::__iter_concept
<_Iter
>,
683 random_access_iterator_tag
>
684 && totally_ordered
<_Iter
> && sized_sentinel_for
<_Iter
, _Iter
>
685 && requires(_Iter __i
, const _Iter __j
,
686 const iter_difference_t
<_Iter
> __n
)
688 { __i
+= __n
} -> same_as
<_Iter
&>;
689 { __j
+ __n
} -> same_as
<_Iter
>;
690 { __n
+ __j
} -> same_as
<_Iter
>;
691 { __i
-= __n
} -> same_as
<_Iter
&>;
692 { __j
- __n
} -> same_as
<_Iter
>;
693 { __j
[__n
] } -> same_as
<iter_reference_t
<_Iter
>>;
696 template<typename _Iter
>
697 concept contiguous_iterator
= random_access_iterator
<_Iter
>
698 && derived_from
<__detail::__iter_concept
<_Iter
>, contiguous_iterator_tag
>
699 && is_lvalue_reference_v
<iter_reference_t
<_Iter
>>
700 && same_as
<iter_value_t
<_Iter
>, remove_cvref_t
<iter_reference_t
<_Iter
>>>
701 && requires(const _Iter
& __i
)
703 { std::to_address(__i
) }
704 -> same_as
<add_pointer_t
<iter_reference_t
<_Iter
>>>;
707 // [indirectcallable], indirect callable requirements
709 // [indirectcallable.indirectinvocable], indirect callables
711 template<typename _Fn
, typename _Iter
>
712 concept indirectly_unary_invocable
= indirectly_readable
<_Iter
>
713 && copy_constructible
<_Fn
> && invocable
<_Fn
&, iter_value_t
<_Iter
>&>
714 && invocable
<_Fn
&, iter_reference_t
<_Iter
>>
715 && invocable
<_Fn
&, iter_common_reference_t
<_Iter
>>
716 && common_reference_with
<invoke_result_t
<_Fn
&, iter_value_t
<_Iter
>&>,
717 invoke_result_t
<_Fn
&, iter_reference_t
<_Iter
>>>;
719 template<typename _Fn
, typename _Iter
>
720 concept indirectly_regular_unary_invocable
= indirectly_readable
<_Iter
>
721 && copy_constructible
<_Fn
>
722 && regular_invocable
<_Fn
&, iter_value_t
<_Iter
>&>
723 && regular_invocable
<_Fn
&, iter_reference_t
<_Iter
>>
724 && regular_invocable
<_Fn
&, iter_common_reference_t
<_Iter
>>
725 && common_reference_with
<invoke_result_t
<_Fn
&, iter_value_t
<_Iter
>&>,
726 invoke_result_t
<_Fn
&, iter_reference_t
<_Iter
>>>;
728 template<typename _Fn
, typename _Iter
>
729 concept indirect_unary_predicate
= indirectly_readable
<_Iter
>
730 && copy_constructible
<_Fn
> && predicate
<_Fn
&, iter_value_t
<_Iter
>&>
731 && predicate
<_Fn
&, iter_reference_t
<_Iter
>>
732 && predicate
<_Fn
&, iter_common_reference_t
<_Iter
>>;
734 template<typename _Fn
, typename _I1
, typename _I2
>
735 concept indirect_binary_predicate
736 = indirectly_readable
<_I1
> && indirectly_readable
<_I2
>
737 && copy_constructible
<_Fn
>
738 && predicate
<_Fn
&, iter_value_t
<_I1
>&, iter_value_t
<_I2
>&>
739 && predicate
<_Fn
&, iter_value_t
<_I1
>&, iter_reference_t
<_I2
>>
740 && predicate
<_Fn
&, iter_reference_t
<_I1
>, iter_value_t
<_I2
>&>
741 && predicate
<_Fn
&, iter_reference_t
<_I1
>, iter_reference_t
<_I2
>>
742 && predicate
<_Fn
&, iter_common_reference_t
<_I1
>,
743 iter_common_reference_t
<_I2
>>;
745 template<typename _Fn
, typename _I1
, typename _I2
= _I1
>
746 concept indirect_equivalence_relation
747 = indirectly_readable
<_I1
> && indirectly_readable
<_I2
>
748 && copy_constructible
<_Fn
>
749 && equivalence_relation
<_Fn
&, iter_value_t
<_I1
>&, iter_value_t
<_I2
>&>
750 && equivalence_relation
<_Fn
&, iter_value_t
<_I1
>&, iter_reference_t
<_I2
>>
751 && equivalence_relation
<_Fn
&, iter_reference_t
<_I1
>, iter_value_t
<_I2
>&>
752 && equivalence_relation
<_Fn
&, iter_reference_t
<_I1
>,
753 iter_reference_t
<_I2
>>
754 && equivalence_relation
<_Fn
&, iter_common_reference_t
<_I1
>,
755 iter_common_reference_t
<_I2
>>;
757 template<typename _Fn
, typename _I1
, typename _I2
= _I1
>
758 concept indirect_strict_weak_order
759 = indirectly_readable
<_I1
> && indirectly_readable
<_I2
>
760 && copy_constructible
<_Fn
>
761 && strict_weak_order
<_Fn
&, iter_value_t
<_I1
>&, iter_value_t
<_I2
>&>
762 && strict_weak_order
<_Fn
&, iter_value_t
<_I1
>&, iter_reference_t
<_I2
>>
763 && strict_weak_order
<_Fn
&, iter_reference_t
<_I1
>, iter_value_t
<_I2
>&>
764 && strict_weak_order
<_Fn
&, iter_reference_t
<_I1
>, iter_reference_t
<_I2
>>
765 && strict_weak_order
<_Fn
&, iter_common_reference_t
<_I1
>,
766 iter_common_reference_t
<_I2
>>;
768 template<typename _Fn
, typename
... _Is
>
769 requires (indirectly_readable
<_Is
> && ...)
770 && invocable
<_Fn
, iter_reference_t
<_Is
>...>
771 using indirect_result_t
= invoke_result_t
<_Fn
, iter_reference_t
<_Is
>...>;
775 template<typename _Iter
, typename _Proj
>
780 using value_type
= remove_cvref_t
<indirect_result_t
<_Proj
&, _Iter
>>;
781 indirect_result_t
<_Proj
&, _Iter
> operator*() const; // not defined
785 template<weakly_incrementable _Iter
, typename _Proj
>
786 struct __projected
<_Iter
, _Proj
>
790 using value_type
= remove_cvref_t
<indirect_result_t
<_Proj
&, _Iter
>>;
791 using difference_type
= iter_difference_t
<_Iter
>;
792 indirect_result_t
<_Proj
&, _Iter
> operator*() const; // not defined
795 } // namespace __detail
797 /// [projected], projected
798 template<indirectly_readable _Iter
,
799 indirectly_regular_unary_invocable
<_Iter
> _Proj
>
800 using projected
= typename
__detail::__projected
<_Iter
, _Proj
>::__type
;
802 // [alg.req], common algorithm requirements
804 /// [alg.req.ind.move], concept `indirectly_movable`
806 template<typename _In
, typename _Out
>
807 concept indirectly_movable
= indirectly_readable
<_In
>
808 && indirectly_writable
<_Out
, iter_rvalue_reference_t
<_In
>>;
810 template<typename _In
, typename _Out
>
811 concept indirectly_movable_storable
= indirectly_movable
<_In
, _Out
>
812 && indirectly_writable
<_Out
, iter_value_t
<_In
>>
813 && movable
<iter_value_t
<_In
>>
814 && constructible_from
<iter_value_t
<_In
>, iter_rvalue_reference_t
<_In
>>
815 && assignable_from
<iter_value_t
<_In
>&, iter_rvalue_reference_t
<_In
>>;
817 /// [alg.req.ind.copy], concept `indirectly_copyable`
818 template<typename _In
, typename _Out
>
819 concept indirectly_copyable
= indirectly_readable
<_In
>
820 && indirectly_writable
<_Out
, iter_reference_t
<_In
>>;
822 template<typename _In
, typename _Out
>
823 concept indirectly_copyable_storable
= indirectly_copyable
<_In
, _Out
>
824 && indirectly_writable
<_Out
, iter_value_t
<_In
>&>
825 && indirectly_writable
<_Out
, const iter_value_t
<_In
>&>
826 && indirectly_writable
<_Out
, iter_value_t
<_In
>&&>
827 && indirectly_writable
<_Out
, const iter_value_t
<_In
>&&>
828 && copyable
<iter_value_t
<_In
>>
829 && constructible_from
<iter_value_t
<_In
>, iter_reference_t
<_In
>>
830 && assignable_from
<iter_value_t
<_In
>&, iter_reference_t
<_In
>>;
834 /// @cond undocumented
837 template<typename _It1
, typename _It2
>
838 void iter_swap(_It1
, _It2
) = delete;
840 template<typename _Tp
, typename _Up
>
842 = (std::__detail::__class_or_enum
<remove_reference_t
<_Tp
>>
843 || std::__detail::__class_or_enum
<remove_reference_t
<_Up
>>)
844 && requires(_Tp
&& __t
, _Up
&& __u
) {
845 iter_swap(static_cast<_Tp
&&>(__t
), static_cast<_Up
&&>(__u
));
848 template<typename _Xp
, typename _Yp
>
849 constexpr iter_value_t
<_Xp
>
850 __iter_exchange_move(_Xp
&& __x
, _Yp
&& __y
)
851 noexcept(noexcept(iter_value_t
<_Xp
>(iter_move(__x
)))
852 && noexcept(*__x
= iter_move(__y
)))
854 iter_value_t
<_Xp
> __old_value(iter_move(__x
));
855 *__x
= iter_move(__y
);
862 template<typename _Tp
, typename _Up
>
863 static constexpr bool
866 if constexpr (__adl_iswap
<_Tp
, _Up
>)
867 return noexcept(iter_swap(std::declval
<_Tp
>(),
868 std::declval
<_Up
>()));
869 else if constexpr (indirectly_readable
<_Tp
>
870 && indirectly_readable
<_Up
>
871 && swappable_with
<iter_reference_t
<_Tp
>, iter_reference_t
<_Up
>>)
872 return noexcept(ranges::swap(*std::declval
<_Tp
>(),
873 *std::declval
<_Up
>()));
875 return noexcept(*std::declval
<_Tp
>()
876 = __iswap::__iter_exchange_move(std::declval
<_Up
>(),
877 std::declval
<_Tp
>()));
881 template<typename _Tp
, typename _Up
>
882 requires __adl_iswap
<_Tp
, _Up
>
883 || (indirectly_readable
<remove_reference_t
<_Tp
>>
884 && indirectly_readable
<remove_reference_t
<_Up
>>
885 && swappable_with
<iter_reference_t
<_Tp
>, iter_reference_t
<_Up
>>)
886 || (indirectly_movable_storable
<_Tp
, _Up
>
887 && indirectly_movable_storable
<_Up
, _Tp
>)
889 operator()(_Tp
&& __e1
, _Up
&& __e2
) const
890 noexcept(_S_noexcept
<_Tp
, _Up
>())
892 if constexpr (__adl_iswap
<_Tp
, _Up
>)
893 iter_swap(static_cast<_Tp
&&>(__e1
), static_cast<_Up
&&>(__e2
));
894 else if constexpr (indirectly_readable
<_Tp
>
895 && indirectly_readable
<_Up
>
896 && swappable_with
<iter_reference_t
<_Tp
>, iter_reference_t
<_Up
>>)
897 ranges::swap(*__e1
, *__e2
);
899 *__e1
= __iswap::__iter_exchange_move(__e2
, __e1
);
902 } // namespace __iswap
905 inline namespace _Cpo
{
906 inline constexpr __iswap::_IterSwap iter_swap
{};
909 } // namespace ranges
911 /// [alg.req.ind.swap], concept `indirectly_swappable`
912 template<typename _I1
, typename _I2
= _I1
>
913 concept indirectly_swappable
914 = indirectly_readable
<_I1
> && indirectly_readable
<_I2
>
915 && requires(const _I1 __i1
, const _I2 __i2
)
917 ranges::iter_swap(__i1
, __i1
);
918 ranges::iter_swap(__i2
, __i2
);
919 ranges::iter_swap(__i1
, __i2
);
920 ranges::iter_swap(__i2
, __i1
);
923 /// [alg.req.ind.cmp], concept `indirectly_comparable`
924 template<typename _I1
, typename _I2
, typename _Rel
, typename _P1
= identity
,
925 typename _P2
= identity
>
926 concept indirectly_comparable
927 = indirect_binary_predicate
<_Rel
, projected
<_I1
, _P1
>,
928 projected
<_I2
, _P2
>>;
930 /// [alg.req.permutable], concept `permutable`
931 template<typename _Iter
>
932 concept permutable
= forward_iterator
<_Iter
>
933 && indirectly_movable_storable
<_Iter
, _Iter
>
934 && indirectly_swappable
<_Iter
, _Iter
>;
936 /// [alg.req.mergeable], concept `mergeable`
937 template<typename _I1
, typename _I2
, typename _Out
,
938 typename _Rel
= ranges::less
, typename _P1
= identity
,
939 typename _P2
= identity
>
940 concept mergeable
= input_iterator
<_I1
> && input_iterator
<_I2
>
941 && weakly_incrementable
<_Out
> && indirectly_copyable
<_I1
, _Out
>
942 && indirectly_copyable
<_I2
, _Out
>
943 && indirect_strict_weak_order
<_Rel
, projected
<_I1
, _P1
>,
944 projected
<_I2
, _P2
>>;
946 /// [alg.req.sortable], concept `sortable`
947 template<typename _Iter
, typename _Rel
= ranges::less
,
948 typename _Proj
= identity
>
949 concept sortable
= permutable
<_Iter
>
950 && indirect_strict_weak_order
<_Rel
, projected
<_Iter
, _Proj
>>;
952 struct unreachable_sentinel_t
954 template<weakly_incrementable _It
>
955 friend constexpr bool
956 operator==(unreachable_sentinel_t
, const _It
&) noexcept
960 inline constexpr unreachable_sentinel_t unreachable_sentinel
{};
962 // This is the namespace for [range.access] CPOs.
963 namespace ranges::__access
965 using std::__detail::__class_or_enum
;
967 struct _Decay_copy final
969 template<typename _Tp
>
970 constexpr decay_t
<_Tp
>
971 operator()(_Tp
&& __t
) const
972 noexcept(is_nothrow_convertible_v
<_Tp
, decay_t
<_Tp
>>)
973 { return std::forward
<_Tp
>(__t
); }
974 } inline constexpr __decay_copy
{};
976 template<typename _Tp
>
977 concept __member_begin
= requires(_Tp
& __t
)
979 { __decay_copy(__t
.begin()) } -> input_or_output_iterator
;
982 // Poison pill so that unqualified lookup doesn't find std::begin.
983 void begin() = delete;
985 template<typename _Tp
>
986 concept __adl_begin
= __class_or_enum
<remove_reference_t
<_Tp
>>
987 && requires(_Tp
& __t
)
989 { __decay_copy(begin(__t
)) } -> input_or_output_iterator
;
992 // Simplified version of std::ranges::begin that only supports lvalues,
993 // for use by __range_iter_t below.
994 template<typename _Tp
>
995 requires is_array_v
<_Tp
> || __member_begin
<_Tp
&> || __adl_begin
<_Tp
&>
999 if constexpr (is_array_v
<_Tp
>)
1001 else if constexpr (__member_begin
<_Tp
&>)
1006 } // namespace ranges::__access
1010 // Implementation of std::ranges::iterator_t, without using ranges::begin.
1011 template<typename _Tp
>
1012 using __range_iter_t
1013 = decltype(ranges::__access::__begin(std::declval
<_Tp
&>()));
1015 } // namespace __detail
1017 #endif // C++20 library concepts
1018 _GLIBCXX_END_NAMESPACE_VERSION
1021 #endif // _ITERATOR_CONCEPTS_H