1// Concepts and traits for use with iterators -*- C++ -*-
2
3// Copyright (C) 2019-2024 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
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}
28 */
29
30#ifndef _ITERATOR_CONCEPTS_H
31#define _ITERATOR_CONCEPTS_H 1
32
33#pragma GCC system_header
34
35#if __cplusplus >= 202002L
36#include <concepts>
37#include <bits/ptr_traits.h> // to_address
38#include <bits/ranges_cmp.h> // identity, ranges::less
39
40namespace std _GLIBCXX_VISIBILITY(default)
41{
42_GLIBCXX_BEGIN_NAMESPACE_VERSION
43
44 /** A sentinel type that can be used to check for the end of a range.
45 *
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.
52 *
53 * Comparing iterators of these types to `std::default_sentinel` is a
54 * convenient way to check if the end has been reached.
55 *
56 * @since C++20
57 */
58 struct default_sentinel_t { };
59
60 /// A default sentinel value.
61 inline constexpr default_sentinel_t default_sentinel{};
62
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;
70
71 template<typename _Iterator>
72 struct iterator_traits;
73
74 template<typename _Tp> requires is_object_v<_Tp>
75 struct iterator_traits<_Tp*>;
76
77 template<typename _Iterator, typename>
78 struct __iterator_traits;
79
80 namespace __detail
81 {
82 template<typename _Tp>
83 using __with_ref = _Tp&;
84
85 template<typename _Tp>
86 concept __can_reference = requires { typename __with_ref<_Tp>; };
87
88 template<typename _Tp>
89 concept __dereferenceable = requires(_Tp& __t)
90 {
91 { *__t } -> __can_reference;
92 };
93 } // namespace __detail
94
95 template<__detail::__dereferenceable _Tp>
96 using iter_reference_t = decltype(*std::declval<_Tp&>());
97
98 namespace ranges
99 {
100 /// @cond undocumented
101 namespace __imove
102 {
103 void iter_move() = delete;
104
105 template<typename _Tp>
106 concept __adl_imove
107 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>)
108 && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); };
109
110 struct _IterMove
111 {
112 private:
113 template<typename _Tp>
114 struct __result
115 { using type = iter_reference_t<_Tp>; };
116
117 template<typename _Tp>
118 requires __adl_imove<_Tp>
119 struct __result<_Tp>
120 { using type = decltype(iter_move(std::declval<_Tp>())); };
121
122 template<typename _Tp>
123 requires (!__adl_imove<_Tp>)
124 && is_lvalue_reference_v<iter_reference_t<_Tp>>
125 struct __result<_Tp>
126 { using type = remove_reference_t<iter_reference_t<_Tp>>&&; };
127
128 template<typename _Tp>
129 static constexpr bool
130 _S_noexcept()
131 {
132 if constexpr (__adl_imove<_Tp>)
133 return noexcept(iter_move(std::declval<_Tp>()));
134 else
135 return noexcept(*std::declval<_Tp>());
136 }
137
138 public:
139 // The result type of iter_move(std::declval<_Tp>())
140 template<std::__detail::__dereferenceable _Tp>
141 using __type = typename __result<_Tp>::type;
142
143 template<std::__detail::__dereferenceable _Tp>
144 [[nodiscard]]
145 constexpr __type<_Tp>
146 operator()(_Tp&& __e) const
147 noexcept(_S_noexcept<_Tp>())
148 {
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);
153 else
154 return *__e;
155 }
156 };
157 } // namespace __imove
158 /// @endcond
159
160 inline namespace _Cpo {
161 inline constexpr __imove::_IterMove iter_move{};
162 }
163 } // namespace ranges
164
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&>;
168
169 template<typename> struct incrementable_traits { };
170
171 template<typename _Tp> requires is_object_v<_Tp>
172 struct incrementable_traits<_Tp*>
173 { using difference_type = ptrdiff_t; };
174
175 template<typename _Iter>
176 struct incrementable_traits<const _Iter>
177 : incrementable_traits<_Iter> { };
178
179 template<typename _Tp> requires requires { typename _Tp::difference_type; }
180 struct incrementable_traits<_Tp>
181 { using difference_type = typename _Tp::difference_type; };
182
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>
188 {
189 using difference_type
190 = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>;
191 };
192
193#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
194 // __int128 is incrementable even if !integral<__int128>
195 template<>
196 struct incrementable_traits<__int128>
197 { using difference_type = __int128; };
198
199 template<>
200 struct incrementable_traits<unsigned __int128>
201 { using difference_type = __int128; };
202#endif
203
204 namespace __detail
205 {
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>);
211
212 template<typename _Iter, typename _Tp>
213 struct __iter_traits_impl
214 { using type = iterator_traits<_Iter>; };
215
216 template<typename _Iter, typename _Tp>
217 requires __primary_traits_iter<_Iter>
218 struct __iter_traits_impl<_Iter, _Tp>
219 { using type = _Tp; };
220
221 // ITER_TRAITS
222 template<typename _Iter, typename _Tp = _Iter>
223 using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type;
224
225 template<typename _Tp>
226 using __iter_diff_t = typename
227 __iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type;
228 } // namespace __detail
229
230 template<typename _Tp>
231 using iter_difference_t = __detail::__iter_diff_t<remove_cvref_t<_Tp>>;
232
233 namespace __detail
234 {
235 template<typename> struct __cond_value_type { };
236
237 template<typename _Tp> requires is_object_v<_Tp>
238 struct __cond_value_type<_Tp>
239 { using value_type = remove_cv_t<_Tp>; };
240
241 template<typename _Tp>
242 concept __has_member_value_type
243 = requires { typename _Tp::value_type; };
244
245 template<typename _Tp>
246 concept __has_member_element_type
247 = requires { typename _Tp::element_type; };
248
249 } // namespace __detail
250
251 template<typename> struct indirectly_readable_traits { };
252
253 template<typename _Tp>
254 struct indirectly_readable_traits<_Tp*>
255 : __detail::__cond_value_type<_Tp>
256 { };
257
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>>; };
261
262 template<typename _Iter>
263 struct indirectly_readable_traits<const _Iter>
264 : indirectly_readable_traits<_Iter>
265 { };
266
267 template<__detail::__has_member_value_type _Tp>
268 struct indirectly_readable_traits<_Tp>
269 : __detail::__cond_value_type<typename _Tp::value_type>
270 { };
271
272 template<__detail::__has_member_element_type _Tp>
273 struct indirectly_readable_traits<_Tp>
274 : __detail::__cond_value_type<typename _Tp::element_type>
275 { };
276
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>
285 { };
286
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>
292 { };
293
294 namespace __detail
295 {
296 template<typename _Tp>
297 using __iter_value_t = typename
298 __iter_traits<_Tp, indirectly_readable_traits<_Tp>>::value_type;
299 } // namespace __detail
300
301 template<typename _Tp>
302 using iter_value_t = __detail::__iter_value_t<remove_cvref_t<_Tp>>;
303
304 namespace __detail
305 {
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)
310 {
311 { *__it } -> __can_reference;
312 { ++__it } -> same_as<_Iter&>;
313 { *__it++ } -> __can_reference;
314 } && copyable<_Iter>;
315
316 template<typename _Iter>
317 concept __cpp17_input_iterator = __cpp17_iterator<_Iter>
318 && equality_comparable<_Iter>
319 && requires(_Iter __it)
320 {
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>;
329 };
330
331 // _GLIBCXX_RESOLVE_LIB_DEFECTS
332 // 3798. Rvalue reference and iterator_category
333 template<typename _Iter>
334 concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter>
335 && constructible_from<_Iter>
336 && is_reference_v<iter_reference_t<_Iter>>
337 && same_as<remove_cvref_t<iter_reference_t<_Iter>>,
338 typename indirectly_readable_traits<_Iter>::value_type>
339 && requires(_Iter __it)
340 {
341 { __it++ } -> convertible_to<const _Iter&>;
342 { *__it++ } -> same_as<iter_reference_t<_Iter>>;
343 };
344
345 template<typename _Iter>
346 concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter>
347 && requires(_Iter __it)
348 {
349 { --__it } -> same_as<_Iter&>;
350 { __it-- } -> convertible_to<const _Iter&>;
351 { *__it-- } -> same_as<iter_reference_t<_Iter>>;
352 };
353
354 template<typename _Iter>
355 concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter>
356 && totally_ordered<_Iter>
357 && requires(_Iter __it,
358 typename incrementable_traits<_Iter>::difference_type __n)
359 {
360 { __it += __n } -> same_as<_Iter&>;
361 { __it -= __n } -> same_as<_Iter&>;
362 { __it + __n } -> same_as<_Iter>;
363 { __n + __it } -> same_as<_Iter>;
364 { __it - __n } -> same_as<_Iter>;
365 { __it - __it } -> same_as<decltype(__n)>;
366 { __it[__n] } -> convertible_to<iter_reference_t<_Iter>>;
367 };
368
369 template<typename _Iter>
370 concept __iter_with_nested_types = requires {
371 typename _Iter::iterator_category;
372 typename _Iter::value_type;
373 typename _Iter::difference_type;
374 typename _Iter::reference;
375 };
376
377 template<typename _Iter>
378 concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>;
379
380 template<typename _Iter>
381 concept __iter_without_category
382 = !requires { typename _Iter::iterator_category; };
383
384 } // namespace __detail
385
386 template<typename _Iterator>
387 requires __detail::__iter_with_nested_types<_Iterator>
388 struct __iterator_traits<_Iterator, void>
389 {
390 private:
391 template<typename _Iter>
392 struct __ptr
393 { using type = void; };
394
395 template<typename _Iter> requires requires { typename _Iter::pointer; }
396 struct __ptr<_Iter>
397 { using type = typename _Iter::pointer; };
398
399 public:
400 using iterator_category = typename _Iterator::iterator_category;
401 using value_type = typename _Iterator::value_type;
402 using difference_type = typename _Iterator::difference_type;
403 using pointer = typename __ptr<_Iterator>::type;
404 using reference = typename _Iterator::reference;
405 };
406
407 template<typename _Iterator>
408 requires __detail::__iter_without_nested_types<_Iterator>
409 && __detail::__cpp17_input_iterator<_Iterator>
410 struct __iterator_traits<_Iterator, void>
411 {
412 private:
413 template<typename _Iter>
414 struct __cat
415 { using type = input_iterator_tag; };
416
417 template<typename _Iter>
418 requires requires { typename _Iter::iterator_category; }
419 struct __cat<_Iter>
420 { using type = typename _Iter::iterator_category; };
421
422 template<typename _Iter>
423 requires __detail::__iter_without_category<_Iter>
424 && __detail::__cpp17_randacc_iterator<_Iter>
425 struct __cat<_Iter>
426 { using type = random_access_iterator_tag; };
427
428 template<typename _Iter>
429 requires __detail::__iter_without_category<_Iter>
430 && __detail::__cpp17_bidi_iterator<_Iter>
431 struct __cat<_Iter>
432 { using type = bidirectional_iterator_tag; };
433
434 template<typename _Iter>
435 requires __detail::__iter_without_category<_Iter>
436 && __detail::__cpp17_fwd_iterator<_Iter>
437 struct __cat<_Iter>
438 { using type = forward_iterator_tag; };
439
440 template<typename _Iter>
441 struct __ptr
442 { using type = void; };
443
444 template<typename _Iter> requires requires { typename _Iter::pointer; }
445 struct __ptr<_Iter>
446 { using type = typename _Iter::pointer; };
447
448 template<typename _Iter>
449 requires (!requires { typename _Iter::pointer; }
450 && requires(_Iter& __it) { __it.operator->(); })
451 struct __ptr<_Iter>
452 { using type = decltype(std::declval<_Iter&>().operator->()); };
453
454 template<typename _Iter>
455 struct __ref
456 { using type = iter_reference_t<_Iter>; };
457
458 template<typename _Iter> requires requires { typename _Iter::reference; }
459 struct __ref<_Iter>
460 { using type = typename _Iter::reference; };
461
462 public:
463 using iterator_category = typename __cat<_Iterator>::type;
464 using value_type
465 = typename indirectly_readable_traits<_Iterator>::value_type;
466 using difference_type
467 = typename incrementable_traits<_Iterator>::difference_type;
468 using pointer = typename __ptr<_Iterator>::type;
469 using reference = typename __ref<_Iterator>::type;
470 };
471
472 template<typename _Iterator>
473 requires __detail::__iter_without_nested_types<_Iterator>
474 && __detail::__cpp17_iterator<_Iterator>
475 struct __iterator_traits<_Iterator, void>
476 {
477 private:
478 template<typename _Iter>
479 struct __diff
480 { using type = void; };
481
482 template<typename _Iter>
483 requires requires
484 { typename incrementable_traits<_Iter>::difference_type; }
485 struct __diff<_Iter>
486 {
487 using type = typename incrementable_traits<_Iter>::difference_type;
488 };
489
490 public:
491 using iterator_category = output_iterator_tag;
492 using value_type = void;
493 using difference_type = typename __diff<_Iterator>::type;
494 using pointer = void;
495 using reference = void;
496 };
497
498 namespace __detail
499 {
500 template<typename _Iter>
501 struct __iter_concept_impl;
502
503 // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid.
504 template<typename _Iter>
505 requires requires { typename __iter_traits<_Iter>::iterator_concept; }
506 struct __iter_concept_impl<_Iter>
507 { using type = typename __iter_traits<_Iter>::iterator_concept; };
508
509 // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid.
510 template<typename _Iter>
511 requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
512 && requires { typename __iter_traits<_Iter>::iterator_category; })
513 struct __iter_concept_impl<_Iter>
514 { using type = typename __iter_traits<_Iter>::iterator_category; };
515
516 // Otherwise, random_access_tag if iterator_traits<I> is not specialized.
517 template<typename _Iter>
518 requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
519 && !requires { typename __iter_traits<_Iter>::iterator_category; }
520 && __primary_traits_iter<_Iter>)
521 struct __iter_concept_impl<_Iter>
522 { using type = random_access_iterator_tag; };
523
524 // Otherwise, there is no ITER_CONCEPT(I) type.
525 template<typename _Iter>
526 struct __iter_concept_impl
527 { };
528
529 // ITER_CONCEPT
530 template<typename _Iter>
531 using __iter_concept = typename __iter_concept_impl<_Iter>::type;
532
533 template<typename _In>
534 concept __indirectly_readable_impl = requires
535 {
536 typename iter_value_t<_In>;
537 typename iter_reference_t<_In>;
538 typename iter_rvalue_reference_t<_In>;
539 requires same_as<iter_reference_t<const _In>,
540 iter_reference_t<_In>>;
541 requires same_as<iter_rvalue_reference_t<const _In>,
542 iter_rvalue_reference_t<_In>>;
543 }
544 && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&>
545 && common_reference_with<iter_reference_t<_In>&&,
546 iter_rvalue_reference_t<_In>&&>
547 && common_reference_with<iter_rvalue_reference_t<_In>&&,
548 const iter_value_t<_In>&>;
549
550 } // namespace __detail
551
552 /// Requirements for types that are readable by applying operator*.
553 template<typename _In>
554 concept indirectly_readable
555 = __detail::__indirectly_readable_impl<remove_cvref_t<_In>>;
556
557 namespace __detail
558 {
559 template<typename _Tp>
560 struct __indirect_value
561 { using type = iter_value_t<_Tp>&; };
562
563 // __indirect_value<projected<_Iter, _Proj>> is defined later.
564 } // namespace __detail
565
566 template<typename _Tp>
567 using __indirect_value_t = typename __detail::__indirect_value<_Tp>::type;
568
569 template<indirectly_readable _Tp>
570 using iter_common_reference_t
571 = common_reference_t<iter_reference_t<_Tp>, __indirect_value_t<_Tp>>;
572
573 /// Requirements for writing a value into an iterator's referenced object.
574 template<typename _Out, typename _Tp>
575 concept indirectly_writable = requires(_Out&& __o, _Tp&& __t)
576 {
577 *__o = std::forward<_Tp>(__t);
578 *std::forward<_Out>(__o) = std::forward<_Tp>(__t);
579 const_cast<const iter_reference_t<_Out>&&>(*__o)
580 = std::forward<_Tp>(__t);
581 const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o))
582 = std::forward<_Tp>(__t);
583 };
584
585 namespace ranges::__detail
586 {
587 class __max_diff_type;
588 class __max_size_type;
589
590 __extension__
591 template<typename _Tp>
592 concept __is_signed_int128
593#if __SIZEOF_INT128__
594 = same_as<_Tp, __int128>;
595#else
596 = false;
597#endif
598
599 __extension__
600 template<typename _Tp>
601 concept __is_unsigned_int128
602#if __SIZEOF_INT128__
603 = same_as<_Tp, unsigned __int128>;
604#else
605 = false;
606#endif
607
608 template<typename _Tp>
609 concept __cv_bool = same_as<const volatile _Tp, const volatile bool>;
610
611 template<typename _Tp>
612 concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>;
613
614 template<typename _Tp>
615 concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>;
616
617 template<typename _Tp>
618 concept __is_integer_like = __integral_nonbool<_Tp>
619 || __is_int128<_Tp>
620 || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>;
621
622 template<typename _Tp>
623 concept __is_signed_integer_like = signed_integral<_Tp>
624 || __is_signed_int128<_Tp>
625 || same_as<_Tp, __max_diff_type>;
626
627 } // namespace ranges::__detail
628
629 namespace __detail { using ranges::__detail::__is_signed_integer_like; }
630
631 /// Requirements on types that can be incremented with ++.
632 template<typename _Iter>
633 concept weakly_incrementable = movable<_Iter>
634 && requires(_Iter __i)
635 {
636 typename iter_difference_t<_Iter>;
637 requires __detail::__is_signed_integer_like<iter_difference_t<_Iter>>;
638 { ++__i } -> same_as<_Iter&>;
639 __i++;
640 };
641
642 template<typename _Iter>
643 concept incrementable = regular<_Iter> && weakly_incrementable<_Iter>
644 && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; };
645
646 template<typename _Iter>
647 concept input_or_output_iterator
648 = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
649 && weakly_incrementable<_Iter>;
650
651 template<typename _Sent, typename _Iter>
652 concept sentinel_for = semiregular<_Sent>
653 && input_or_output_iterator<_Iter>
654 && __detail::__weakly_eq_cmp_with<_Sent, _Iter>;
655
656 template<typename _Sent, typename _Iter>
657 inline constexpr bool disable_sized_sentinel_for = false;
658
659 template<typename _Sent, typename _Iter>
660 concept sized_sentinel_for = sentinel_for<_Sent, _Iter>
661 && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>>
662 && requires(const _Iter& __i, const _Sent& __s)
663 {
664 { __s - __i } -> same_as<iter_difference_t<_Iter>>;
665 { __i - __s } -> same_as<iter_difference_t<_Iter>>;
666 };
667
668 template<typename _Iter>
669 concept input_iterator = input_or_output_iterator<_Iter>
670 && indirectly_readable<_Iter>
671 && requires { typename __detail::__iter_concept<_Iter>; }
672 && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>;
673
674 template<typename _Iter, typename _Tp>
675 concept output_iterator = input_or_output_iterator<_Iter>
676 && indirectly_writable<_Iter, _Tp>
677 && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); };
678
679 template<typename _Iter>
680 concept forward_iterator = input_iterator<_Iter>
681 && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag>
682 && incrementable<_Iter> && sentinel_for<_Iter, _Iter>;
683
684 template<typename _Iter>
685 concept bidirectional_iterator = forward_iterator<_Iter>
686 && derived_from<__detail::__iter_concept<_Iter>,
687 bidirectional_iterator_tag>
688 && requires(_Iter __i)
689 {
690 { --__i } -> same_as<_Iter&>;
691 { __i-- } -> same_as<_Iter>;
692 };
693
694 template<typename _Iter>
695 concept random_access_iterator = bidirectional_iterator<_Iter>
696 && derived_from<__detail::__iter_concept<_Iter>,
697 random_access_iterator_tag>
698 && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter>
699 && requires(_Iter __i, const _Iter __j,
700 const iter_difference_t<_Iter> __n)
701 {
702 { __i += __n } -> same_as<_Iter&>;
703 { __j + __n } -> same_as<_Iter>;
704 { __n + __j } -> same_as<_Iter>;
705 { __i -= __n } -> same_as<_Iter&>;
706 { __j - __n } -> same_as<_Iter>;
707 { __j[__n] } -> same_as<iter_reference_t<_Iter>>;
708 };
709
710 template<typename _Iter>
711 concept contiguous_iterator = random_access_iterator<_Iter>
712 && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag>
713 && is_lvalue_reference_v<iter_reference_t<_Iter>>
714 && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>>
715 && requires(const _Iter& __i)
716 {
717 { std::to_address(__i) }
718 -> same_as<add_pointer_t<iter_reference_t<_Iter>>>;
719 };
720
721 // [indirectcallable], indirect callable requirements
722
723 // [indirectcallable.indirectinvocable], indirect callables
724
725 template<typename _Fn, typename _Iter>
726 concept indirectly_unary_invocable = indirectly_readable<_Iter>
727 && copy_constructible<_Fn> && invocable<_Fn&, __indirect_value_t<_Iter>>
728 && invocable<_Fn&, iter_reference_t<_Iter>>
729 && common_reference_with<invoke_result_t<_Fn&, __indirect_value_t<_Iter>>,
730 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
731
732 template<typename _Fn, typename _Iter>
733 concept indirectly_regular_unary_invocable = indirectly_readable<_Iter>
734 && copy_constructible<_Fn>
735 && regular_invocable<_Fn&, __indirect_value_t<_Iter>>
736 && regular_invocable<_Fn&, iter_reference_t<_Iter>>
737 && common_reference_with<invoke_result_t<_Fn&, __indirect_value_t<_Iter>>,
738 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
739
740 template<typename _Fn, typename _Iter>
741 concept indirect_unary_predicate = indirectly_readable<_Iter>
742 && copy_constructible<_Fn> && predicate<_Fn&, __indirect_value_t<_Iter>>
743 && predicate<_Fn&, iter_reference_t<_Iter>>;
744
745 template<typename _Fn, typename _I1, typename _I2>
746 concept indirect_binary_predicate
747 = indirectly_readable<_I1> && indirectly_readable<_I2>
748 && copy_constructible<_Fn>
749 && predicate<_Fn&, __indirect_value_t<_I1>, __indirect_value_t<_I2>>
750 && predicate<_Fn&, __indirect_value_t<_I1>, iter_reference_t<_I2>>
751 && predicate<_Fn&, iter_reference_t<_I1>, __indirect_value_t<_I2>>
752 && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>;
753
754 template<typename _Fn, typename _I1, typename _I2 = _I1>
755 concept indirect_equivalence_relation
756 = indirectly_readable<_I1> && indirectly_readable<_I2>
757 && copy_constructible<_Fn>
758 && equivalence_relation<_Fn&, __indirect_value_t<_I1>, __indirect_value_t<_I2>>
759 && equivalence_relation<_Fn&, __indirect_value_t<_I1>, iter_reference_t<_I2>>
760 && equivalence_relation<_Fn&, iter_reference_t<_I1>, __indirect_value_t<_I2>>
761 && equivalence_relation<_Fn&, iter_reference_t<_I1>,
762 iter_reference_t<_I2>>;
763
764 template<typename _Fn, typename _I1, typename _I2 = _I1>
765 concept indirect_strict_weak_order
766 = indirectly_readable<_I1> && indirectly_readable<_I2>
767 && copy_constructible<_Fn>
768 && strict_weak_order<_Fn&, __indirect_value_t<_I1>, __indirect_value_t<_I2>>
769 && strict_weak_order<_Fn&, __indirect_value_t<_I1>, iter_reference_t<_I2>>
770 && strict_weak_order<_Fn&, iter_reference_t<_I1>, __indirect_value_t<_I2>>
771 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>;
772
773 template<typename _Fn, typename... _Is>
774 requires (indirectly_readable<_Is> && ...)
775 && invocable<_Fn, iter_reference_t<_Is>...>
776 using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Is>...>;
777
778 namespace __detail
779 {
780 template<typename _Iter, typename _Proj>
781 struct __projected
782 {
783 struct __type
784 {
785 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
786 indirect_result_t<_Proj&, _Iter> operator*() const; // not defined
787
788 // These are used to identify and obtain the template arguments of a
789 // specialization of the 'projected' alias template below.
790 using __projected_Iter = _Iter;
791 using __projected_Proj = _Proj;
792 };
793 };
794
795 template<weakly_incrementable _Iter, typename _Proj>
796 struct __projected<_Iter, _Proj>
797 {
798 struct __type
799 {
800 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
801 using difference_type = iter_difference_t<_Iter>;
802 indirect_result_t<_Proj&, _Iter> operator*() const; // not defined
803
804 using __projected_Iter = _Iter;
805 using __projected_Proj = _Proj;
806 };
807 };
808 } // namespace __detail
809
810 /// [projected], projected
811 template<indirectly_readable _Iter,
812 indirectly_regular_unary_invocable<_Iter> _Proj>
813 using projected = typename __detail::__projected<_Iter, _Proj>::__type;
814
815 // Matches specializations of the 'projected' alias template.
816 template<typename _Tp>
817 requires same_as<_Tp, projected<typename _Tp::__projected_Iter,
818 typename _Tp::__projected_Proj>>
819 struct __detail::__indirect_value<_Tp>
820 {
821 using _Iter = typename _Tp::__projected_Iter;
822 using _Proj = typename _Tp::__projected_Proj;
823 using type = invoke_result_t<_Proj&, __indirect_value_t<_Iter>>;
824 };
825
826 // [alg.req], common algorithm requirements
827
828 /// [alg.req.ind.move], concept `indirectly_movable`
829
830 template<typename _In, typename _Out>
831 concept indirectly_movable = indirectly_readable<_In>
832 && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
833
834 template<typename _In, typename _Out>
835 concept indirectly_movable_storable = indirectly_movable<_In, _Out>
836 && indirectly_writable<_Out, iter_value_t<_In>>
837 && movable<iter_value_t<_In>>
838 && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>
839 && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
840
841 /// [alg.req.ind.copy], concept `indirectly_copyable`
842 template<typename _In, typename _Out>
843 concept indirectly_copyable = indirectly_readable<_In>
844 && indirectly_writable<_Out, iter_reference_t<_In>>;
845
846 template<typename _In, typename _Out>
847 concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>
848 && indirectly_writable<_Out, iter_value_t<_In>&>
849 && indirectly_writable<_Out, const iter_value_t<_In>&>
850 && indirectly_writable<_Out, iter_value_t<_In>&&>
851 && indirectly_writable<_Out, const iter_value_t<_In>&&>
852 && copyable<iter_value_t<_In>>
853 && constructible_from<iter_value_t<_In>, iter_reference_t<_In>>
854 && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
855
856namespace ranges
857{
858 /// @cond undocumented
859 namespace __iswap
860 {
861 template<typename _It1, typename _It2>
862 void iter_swap(_It1, _It2) = delete;
863
864 template<typename _Tp, typename _Up>
865 concept __adl_iswap
866 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>
867 || std::__detail::__class_or_enum<remove_reference_t<_Up>>)
868 && requires(_Tp&& __t, _Up&& __u) {
869 iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u));
870 };
871
872 template<typename _Xp, typename _Yp>
873 constexpr iter_value_t<_Xp>
874 __iter_exchange_move(_Xp&& __x, _Yp&& __y)
875 noexcept(noexcept(iter_value_t<_Xp>(iter_move(__x)))
876 && noexcept(*__x = iter_move(__y)))
877 {
878 iter_value_t<_Xp> __old_value(iter_move(__x));
879 *__x = iter_move(__y);
880 return __old_value;
881 }
882
883 struct _IterSwap
884 {
885 private:
886 template<typename _Tp, typename _Up>
887 static constexpr bool
888 _S_noexcept()
889 {
890 if constexpr (__adl_iswap<_Tp, _Up>)
891 return noexcept(iter_swap(std::declval<_Tp>(),
892 std::declval<_Up>()));
893 else if constexpr (indirectly_readable<_Tp>
894 && indirectly_readable<_Up>
895 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
896 return noexcept(ranges::swap(*std::declval<_Tp>(),
897 *std::declval<_Up>()));
898 else
899 return noexcept(*std::declval<_Tp>()
900 = __iswap::__iter_exchange_move(std::declval<_Up>(),
901 std::declval<_Tp>()));
902 }
903
904 public:
905 template<typename _Tp, typename _Up>
906 requires __adl_iswap<_Tp, _Up>
907 || (indirectly_readable<remove_reference_t<_Tp>>
908 && indirectly_readable<remove_reference_t<_Up>>
909 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
910 || (indirectly_movable_storable<_Tp, _Up>
911 && indirectly_movable_storable<_Up, _Tp>)
912 constexpr void
913 operator()(_Tp&& __e1, _Up&& __e2) const
914 noexcept(_S_noexcept<_Tp, _Up>())
915 {
916 if constexpr (__adl_iswap<_Tp, _Up>)
917 iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2));
918 else if constexpr (indirectly_readable<_Tp>
919 && indirectly_readable<_Up>
920 && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
921 ranges::swap(*__e1, *__e2);
922 else
923 *__e1 = __iswap::__iter_exchange_move(__e2, __e1);
924 }
925 };
926 } // namespace __iswap
927 /// @endcond
928
929 inline namespace _Cpo {
930 inline constexpr __iswap::_IterSwap iter_swap{};
931 }
932
933} // namespace ranges
934
935 /// [alg.req.ind.swap], concept `indirectly_swappable`
936 template<typename _I1, typename _I2 = _I1>
937 concept indirectly_swappable
938 = indirectly_readable<_I1> && indirectly_readable<_I2>
939 && requires(const _I1 __i1, const _I2 __i2)
940 {
941 ranges::iter_swap(__i1, __i1);
942 ranges::iter_swap(__i2, __i2);
943 ranges::iter_swap(__i1, __i2);
944 ranges::iter_swap(__i2, __i1);
945 };
946
947 /// [alg.req.ind.cmp], concept `indirectly_comparable`
948 template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity,
949 typename _P2 = identity>
950 concept indirectly_comparable
951 = indirect_binary_predicate<_Rel, projected<_I1, _P1>,
952 projected<_I2, _P2>>;
953
954 /// [alg.req.permutable], concept `permutable`
955 template<typename _Iter>
956 concept permutable = forward_iterator<_Iter>
957 && indirectly_movable_storable<_Iter, _Iter>
958 && indirectly_swappable<_Iter, _Iter>;
959
960 /// [alg.req.mergeable], concept `mergeable`
961 template<typename _I1, typename _I2, typename _Out,
962 typename _Rel = ranges::less, typename _P1 = identity,
963 typename _P2 = identity>
964 concept mergeable = input_iterator<_I1> && input_iterator<_I2>
965 && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out>
966 && indirectly_copyable<_I2, _Out>
967 && indirect_strict_weak_order<_Rel, projected<_I1, _P1>,
968 projected<_I2, _P2>>;
969
970 /// [alg.req.sortable], concept `sortable`
971 template<typename _Iter, typename _Rel = ranges::less,
972 typename _Proj = identity>
973 concept sortable = permutable<_Iter>
974 && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>;
975
976 struct unreachable_sentinel_t
977 {
978 template<weakly_incrementable _It>
979 friend constexpr bool
980 operator==(unreachable_sentinel_t, const _It&) noexcept
981 { return false; }
982 };
983
984 inline constexpr unreachable_sentinel_t unreachable_sentinel{};
985
986 // This is the namespace for [range.access] CPOs.
987 namespace ranges::__access
988 {
989 using std::__detail::__class_or_enum;
990
991 struct _Decay_copy final
992 {
993 template<typename _Tp>
994 constexpr decay_t<_Tp>
995 operator()(_Tp&& __t) const
996 noexcept(is_nothrow_convertible_v<_Tp, decay_t<_Tp>>)
997 { return std::forward<_Tp>(__t); }
998 } inline constexpr __decay_copy{};
999
1000 template<typename _Tp>
1001 concept __member_begin = requires(_Tp& __t)
1002 {
1003 { __decay_copy(__t.begin()) } -> input_or_output_iterator;
1004 };
1005
1006 // Poison pill so that unqualified lookup doesn't find std::begin.
1007 void begin() = delete;
1008
1009 template<typename _Tp>
1010 concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>>
1011 && requires(_Tp& __t)
1012 {
1013 { __decay_copy(begin(__t)) } -> input_or_output_iterator;
1014 };
1015
1016 // Simplified version of std::ranges::begin that only supports lvalues,
1017 // for use by __range_iter_t below.
1018 template<typename _Tp>
1019 requires is_array_v<_Tp> || __member_begin<_Tp&> || __adl_begin<_Tp&>
1020 auto
1021 __begin(_Tp& __t)
1022 {
1023 if constexpr (is_array_v<_Tp>)
1024 return __t + 0;
1025 else if constexpr (__member_begin<_Tp&>)
1026 return __t.begin();
1027 else
1028 return begin(__t);
1029 }
1030 } // namespace ranges::__access
1031
1032 namespace __detail
1033 {
1034 // Implementation of std::ranges::iterator_t, without using ranges::begin.
1035 template<typename _Tp>
1036 using __range_iter_t
1037 = decltype(ranges::__access::__begin(std::declval<_Tp&>()));
1038
1039 } // namespace __detail
1040
1041#endif // C++20 library concepts
1042_GLIBCXX_END_NAMESPACE_VERSION
1043} // namespace std
1044#endif // C++20
1045#endif // _ITERATOR_CONCEPTS_H
1046