1 // Concepts and traits for use with iterators -*- C++ -*-
2
3 // Copyright (C) 2019-2023 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
40 namespace 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 namespace __cust_imove
101 {
102 void iter_move();
103
104 template<typename _Tp>
105 concept __adl_imove
106 = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>)
107 && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); };
108
109 struct _IMove
110 {
111 private:
112 template<typename _Tp>
113 struct __result
114 { using type = iter_reference_t<_Tp>; };
115
116 template<typename _Tp>
117 requires __adl_imove<_Tp>
118 struct __result<_Tp>
119 { using type = decltype(iter_move(std::declval<_Tp>())); };
120
121 template<typename _Tp>
122 requires (!__adl_imove<_Tp>)
123 && is_lvalue_reference_v<iter_reference_t<_Tp>>
124 struct __result<_Tp>
125 { using type = remove_reference_t<iter_reference_t<_Tp>>&&; };
126
127 template<typename _Tp>
128 static constexpr bool
129 _S_noexcept()
130 {
131 if constexpr (__adl_imove<_Tp>)
132 return noexcept(iter_move(std::declval<_Tp>()));
133 else
134 return noexcept(*std::declval<_Tp>());
135 }
136
137 public:
138 // The result type of iter_move(std::declval<_Tp>())
139 template<std::__detail::__dereferenceable _Tp>
140 using __type = typename __result<_Tp>::type;
141
142 template<std::__detail::__dereferenceable _Tp>
143 [[nodiscard]]
144 constexpr __type<_Tp>
145 operator()(_Tp&& __e) const
146 noexcept(_S_noexcept<_Tp>())
147 {
148 if constexpr (__adl_imove<_Tp>)
149 return iter_move(static_cast<_Tp&&>(__e));
150 else if constexpr (is_lvalue_reference_v<iter_reference_t<_Tp>>)
151 return static_cast<__type<_Tp>>(*__e);
152 else
153 return *__e;
154 }
155 };
156 } // namespace __cust_imove
157
158 inline namespace __cust
159 {
160 inline constexpr __cust_imove::_IMove iter_move{};
161 } // inline namespace __cust
162 } // namespace ranges
163
164 template<__detail::__dereferenceable _Tp>
165 requires __detail::
166 __can_reference<ranges::__cust_imove::_IMove::__type<_Tp&>>
167 using iter_rvalue_reference_t
168 = ranges::__cust_imove::_IMove::__type<_Tp&>;
169
170 template<typename> struct incrementable_traits { };
171
172 template<typename _Tp> requires is_object_v<_Tp>
173 struct incrementable_traits<_Tp*>
174 { using difference_type = ptrdiff_t; };
175
176 template<typename _Iter>
177 struct incrementable_traits<const _Iter>
178 : incrementable_traits<_Iter> { };
179
180 template<typename _Tp> requires requires { typename _Tp::difference_type; }
181 struct incrementable_traits<_Tp>
182 { using difference_type = typename _Tp::difference_type; };
183
184 template<typename _Tp>
185 requires (!requires { typename _Tp::difference_type; }
186 && requires(const _Tp& __a, const _Tp& __b)
187 { { __a - __b } -> integral; })
188 struct incrementable_traits<_Tp>
189 {
190 using difference_type
191 = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>;
192 };
193
194 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
195 // __int128 is incrementable even if !integral<__int128>
196 template<>
197 struct incrementable_traits<__int128>
198 { using difference_type = __int128; };
199
200 template<>
201 struct incrementable_traits<unsigned __int128>
202 { using difference_type = __int128; };
203 #endif
204
205 namespace __detail
206 {
207 // An iterator such that iterator_traits<_Iter> names a specialization
208 // generated from the primary template.
209 template<typename _Iter>
210 concept __primary_traits_iter
211 = __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>);
212
213 template<typename _Iter, typename _Tp>
214 struct __iter_traits_impl
215 { using type = iterator_traits<_Iter>; };
216
217 template<typename _Iter, typename _Tp>
218 requires __primary_traits_iter<_Iter>
219 struct __iter_traits_impl<_Iter, _Tp>
220 { using type = _Tp; };
221
222 // ITER_TRAITS
223 template<typename _Iter, typename _Tp = _Iter>
224 using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type;
225
226 template<typename _Tp>
227 using __iter_diff_t = typename
228 __iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type;
229 } // namespace __detail
230
231 template<typename _Tp>
232 using iter_difference_t = __detail::__iter_diff_t<remove_cvref_t<_Tp>>;
233
234 namespace __detail
235 {
236 template<typename> struct __cond_value_type { };
237
238 template<typename _Tp> requires is_object_v<_Tp>
239 struct __cond_value_type<_Tp>
240 { using value_type = remove_cv_t<_Tp>; };
241
242 template<typename _Tp>
243 concept __has_member_value_type
244 = requires { typename _Tp::value_type; };
245
246 template<typename _Tp>
247 concept __has_member_element_type
248 = requires { typename _Tp::element_type; };
249
250 } // namespace __detail
251
252 template<typename> struct indirectly_readable_traits { };
253
254 template<typename _Tp>
255 struct indirectly_readable_traits<_Tp*>
256 : __detail::__cond_value_type<_Tp>
257 { };
258
259 template<typename _Iter> requires is_array_v<_Iter>
260 struct indirectly_readable_traits<_Iter>
261 { using value_type = remove_cv_t<remove_extent_t<_Iter>>; };
262
263 template<typename _Iter>
264 struct indirectly_readable_traits<const _Iter>
265 : indirectly_readable_traits<_Iter>
266 { };
267
268 template<__detail::__has_member_value_type _Tp>
269 struct indirectly_readable_traits<_Tp>
270 : __detail::__cond_value_type<typename _Tp::value_type>
271 { };
272
273 template<__detail::__has_member_element_type _Tp>
274 struct indirectly_readable_traits<_Tp>
275 : __detail::__cond_value_type<typename _Tp::element_type>
276 { };
277
278 // _GLIBCXX_RESOLVE_LIB_DEFECTS
279 // 3446. indirectly_readable_traits ambiguity for types with both [...]
280 template<__detail::__has_member_value_type _Tp>
281 requires __detail::__has_member_element_type<_Tp>
282 && same_as<remove_cv_t<typename _Tp::element_type>,
283 remove_cv_t<typename _Tp::value_type>>
284 struct indirectly_readable_traits<_Tp>
285 : __detail::__cond_value_type<typename _Tp::value_type>
286 { };
287
288 // _GLIBCXX_RESOLVE_LIB_DEFECTS
289 // 3541. indirectly_readable_traits should be SFINAE-friendly for all types
290 template<__detail::__has_member_value_type _Tp>
291 requires __detail::__has_member_element_type<_Tp>
292 struct indirectly_readable_traits<_Tp>
293 { };
294
295 namespace __detail
296 {
297 template<typename _Tp>
298 using __iter_value_t = typename
299 __iter_traits<_Tp, indirectly_readable_traits<_Tp>>::value_type;
300 } // namespace __detail
301
302 template<typename _Tp>
303 using iter_value_t = __detail::__iter_value_t<remove_cvref_t<_Tp>>;
304
305 namespace __detail
306 {
307 // _GLIBCXX_RESOLVE_LIB_DEFECTS
308 // 3420. cpp17-iterator should check [type] looks like an iterator first
309 template<typename _Iter>
310 concept __cpp17_iterator = requires(_Iter __it)
311 {
312 { *__it } -> __can_reference;
313 { ++__it } -> same_as<_Iter&>;
314 { *__it++ } -> __can_reference;
315 } && copyable<_Iter>;
316
317 template<typename _Iter>
318 concept __cpp17_input_iterator = __cpp17_iterator<_Iter>
319 && equality_comparable<_Iter>
320 && requires(_Iter __it)
321 {
322 typename incrementable_traits<_Iter>::difference_type;
323 typename indirectly_readable_traits<_Iter>::value_type;
324 typename common_reference_t<iter_reference_t<_Iter>&&,
325 typename indirectly_readable_traits<_Iter>::value_type&>;
326 typename common_reference_t<decltype(*__it++)&&,
327 typename indirectly_readable_traits<_Iter>::value_type&>;
328 requires signed_integral<
329 typename incrementable_traits<_Iter>::difference_type>;
330 };
331
332 template<typename _Iter>
333 concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter>
334 && constructible_from<_Iter>
335 && is_lvalue_reference_v<iter_reference_t<_Iter>>
336 && same_as<remove_cvref_t<iter_reference_t<_Iter>>,
337 typename indirectly_readable_traits<_Iter>::value_type>
338 && requires(_Iter __it)
339 {
340 { __it++ } -> convertible_to<const _Iter&>;
341 { *__it++ } -> same_as<iter_reference_t<_Iter>>;
342 };
343
344 template<typename _Iter>
345 concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter>
346 && requires(_Iter __it)
347 {
348 { --__it } -> same_as<_Iter&>;
349 { __it-- } -> convertible_to<const _Iter&>;
350 { *__it-- } -> same_as<iter_reference_t<_Iter>>;
351 };
352
353 template<typename _Iter>
354 concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter>
355 && totally_ordered<_Iter>
356 && requires(_Iter __it,
357 typename incrementable_traits<_Iter>::difference_type __n)
358 {
359 { __it += __n } -> same_as<_Iter&>;
360 { __it -= __n } -> same_as<_Iter&>;
361 { __it + __n } -> same_as<_Iter>;
362 { __n + __it } -> same_as<_Iter>;
363 { __it - __n } -> same_as<_Iter>;
364 { __it - __it } -> same_as<decltype(__n)>;
365 { __it[__n] } -> convertible_to<iter_reference_t<_Iter>>;
366 };
367
368 template<typename _Iter>
369 concept __iter_with_nested_types = requires {
370 typename _Iter::iterator_category;
371 typename _Iter::value_type;
372 typename _Iter::difference_type;
373 typename _Iter::reference;
374 };
375
376 template<typename _Iter>
377 concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>;
378
379 template<typename _Iter>
380 concept __iter_without_category
381 = !requires { typename _Iter::iterator_category; };
382
383 } // namespace __detail
384
385 template<typename _Iterator>
386 requires __detail::__iter_with_nested_types<_Iterator>
387 struct __iterator_traits<_Iterator, void>
388 {
389 private:
390 template<typename _Iter>
391 struct __ptr
392 { using type = void; };
393
394 template<typename _Iter> requires requires { typename _Iter::pointer; }
395 struct __ptr<_Iter>
396 { using type = typename _Iter::pointer; };
397
398 public:
399 using iterator_category = typename _Iterator::iterator_category;
400 using value_type = typename _Iterator::value_type;
401 using difference_type = typename _Iterator::difference_type;
402 using pointer = typename __ptr<_Iterator>::type;
403 using reference = typename _Iterator::reference;
404 };
405
406 template<typename _Iterator>
407 requires __detail::__iter_without_nested_types<_Iterator>
408 && __detail::__cpp17_input_iterator<_Iterator>
409 struct __iterator_traits<_Iterator, void>
410 {
411 private:
412 template<typename _Iter>
413 struct __cat
414 { using type = input_iterator_tag; };
415
416 template<typename _Iter>
417 requires requires { typename _Iter::iterator_category; }
418 struct __cat<_Iter>
419 { using type = typename _Iter::iterator_category; };
420
421 template<typename _Iter>
422 requires __detail::__iter_without_category<_Iter>
423 && __detail::__cpp17_randacc_iterator<_Iter>
424 struct __cat<_Iter>
425 { using type = random_access_iterator_tag; };
426
427 template<typename _Iter>
428 requires __detail::__iter_without_category<_Iter>
429 && __detail::__cpp17_bidi_iterator<_Iter>
430 struct __cat<_Iter>
431 { using type = bidirectional_iterator_tag; };
432
433 template<typename _Iter>
434 requires __detail::__iter_without_category<_Iter>
435 && __detail::__cpp17_fwd_iterator<_Iter>
436 struct __cat<_Iter>
437 { using type = forward_iterator_tag; };
438
439 template<typename _Iter>
440 struct __ptr
441 { using type = void; };
442
443 template<typename _Iter> requires requires { typename _Iter::pointer; }
444 struct __ptr<_Iter>
445 { using type = typename _Iter::pointer; };
446
447 template<typename _Iter>
448 requires (!requires { typename _Iter::pointer; }
449 && requires(_Iter& __it) { __it.operator->(); })
450 struct __ptr<_Iter>
451 { using type = decltype(std::declval<_Iter&>().operator->()); };
452
453 template<typename _Iter>
454 struct __ref
455 { using type = iter_reference_t<_Iter>; };
456
457 template<typename _Iter> requires requires { typename _Iter::reference; }
458 struct __ref<_Iter>
459 { using type = typename _Iter::reference; };
460
461 public:
462 using iterator_category = typename __cat<_Iterator>::type;
463 using value_type
464 = typename indirectly_readable_traits<_Iterator>::value_type;
465 using difference_type
466 = typename incrementable_traits<_Iterator>::difference_type;
467 using pointer = typename __ptr<_Iterator>::type;
468 using reference = typename __ref<_Iterator>::type;
469 };
470
471 template<typename _Iterator>
472 requires __detail::__iter_without_nested_types<_Iterator>
473 && __detail::__cpp17_iterator<_Iterator>
474 struct __iterator_traits<_Iterator, void>
475 {
476 private:
477 template<typename _Iter>
478 struct __diff
479 { using type = void; };
480
481 template<typename _Iter>
482 requires requires
483 { typename incrementable_traits<_Iter>::difference_type; }
484 struct __diff<_Iter>
485 {
486 using type = typename incrementable_traits<_Iter>::difference_type;
487 };
488
489 public:
490 using iterator_category = output_iterator_tag;
491 using value_type = void;
492 using difference_type = typename __diff<_Iterator>::type;
493 using pointer = void;
494 using reference = void;
495 };
496
497 namespace __detail
498 {
499 template<typename _Iter>
500 struct __iter_concept_impl;
501
502 // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid.
503 template<typename _Iter>
504 requires requires { typename __iter_traits<_Iter>::iterator_concept; }
505 struct __iter_concept_impl<_Iter>
506 { using type = typename __iter_traits<_Iter>::iterator_concept; };
507
508 // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid.
509 template<typename _Iter>
510 requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
511 && requires { typename __iter_traits<_Iter>::iterator_category; })
512 struct __iter_concept_impl<_Iter>
513 { using type = typename __iter_traits<_Iter>::iterator_category; };
514
515 // Otherwise, random_access_tag if iterator_traits<I> is not specialized.
516 template<typename _Iter>
517 requires (!requires { typename __iter_traits<_Iter>::iterator_concept; }
518 && !requires { typename __iter_traits<_Iter>::iterator_category; }
519 && __primary_traits_iter<_Iter>)
520 struct __iter_concept_impl<_Iter>
521 { using type = random_access_iterator_tag; };
522
523 // Otherwise, there is no ITER_CONCEPT(I) type.
524 template<typename _Iter>
525 struct __iter_concept_impl
526 { };
527
528 // ITER_CONCEPT
529 template<typename _Iter>
530 using __iter_concept = typename __iter_concept_impl<_Iter>::type;
531
532 template<typename _In>
533 concept __indirectly_readable_impl = requires
534 {
535 typename iter_value_t<_In>;
536 typename iter_reference_t<_In>;
537 typename iter_rvalue_reference_t<_In>;
538 requires same_as<iter_reference_t<const _In>,
539 iter_reference_t<_In>>;
540 requires same_as<iter_rvalue_reference_t<const _In>,
541 iter_rvalue_reference_t<_In>>;
542 }
543 && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&>
544 && common_reference_with<iter_reference_t<_In>&&,
545 iter_rvalue_reference_t<_In>&&>
546 && common_reference_with<iter_rvalue_reference_t<_In>&&,
547 const iter_value_t<_In>&>;
548
549 } // namespace __detail
550
551 /// Requirements for types that are readable by applying operator*.
552 template<typename _In>
553 concept indirectly_readable
554 = __detail::__indirectly_readable_impl<remove_cvref_t<_In>>;
555
556 template<indirectly_readable _Tp>
557 using iter_common_reference_t
558 = common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>;
559
560 /// Requirements for writing a value into an iterator's referenced object.
561 template<typename _Out, typename _Tp>
562 concept indirectly_writable = requires(_Out&& __o, _Tp&& __t)
563 {
564 *__o = std::forward<_Tp>(__t);
565 *std::forward<_Out>(__o) = std::forward<_Tp>(__t);
566 const_cast<const iter_reference_t<_Out>&&>(*__o)
567 = std::forward<_Tp>(__t);
568 const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o))
569 = std::forward<_Tp>(__t);
570 };
571
572 namespace ranges::__detail
573 {
574 class __max_diff_type;
575 class __max_size_type;
576
577 __extension__
578 template<typename _Tp>
579 concept __is_signed_int128
580 #if __SIZEOF_INT128__
581 = same_as<_Tp, __int128>;
582 #else
583 = false;
584 #endif
585
586 __extension__
587 template<typename _Tp>
588 concept __is_unsigned_int128
589 #if __SIZEOF_INT128__
590 = same_as<_Tp, unsigned __int128>;
591 #else
592 = false;
593 #endif
594
595 template<typename _Tp>
596 concept __cv_bool = same_as<const volatile _Tp, const volatile bool>;
597
598 template<typename _Tp>
599 concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>;
600
601 template<typename _Tp>
602 concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>;
603
604 template<typename _Tp>
605 concept __is_integer_like = __integral_nonbool<_Tp>
606 || __is_int128<_Tp>
607 || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>;
608
609 template<typename _Tp>
610 concept __is_signed_integer_like = signed_integral<_Tp>
611 || __is_signed_int128<_Tp>
612 || same_as<_Tp, __max_diff_type>;
613
614 } // namespace ranges::__detail
615
616 namespace __detail { using ranges::__detail::__is_signed_integer_like; }
617
618 /// Requirements on types that can be incremented with ++.
619 template<typename _Iter>
620 concept weakly_incrementable = movable<_Iter>
621 && requires(_Iter __i)
622 {
623 typename iter_difference_t<_Iter>;
624 requires __detail::__is_signed_integer_like<iter_difference_t<_Iter>>;
625 { ++__i } -> same_as<_Iter&>;
626 __i++;
627 };
628
629 template<typename _Iter>
630 concept incrementable = regular<_Iter> && weakly_incrementable<_Iter>
631 && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; };
632
633 template<typename _Iter>
634 concept input_or_output_iterator
635 = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
636 && weakly_incrementable<_Iter>;
637
638 template<typename _Sent, typename _Iter>
639 concept sentinel_for = semiregular<_Sent>
640 && input_or_output_iterator<_Iter>
641 && __detail::__weakly_eq_cmp_with<_Sent, _Iter>;
642
643 template<typename _Sent, typename _Iter>
644 inline constexpr bool disable_sized_sentinel_for = false;
645
646 template<typename _Sent, typename _Iter>
647 concept sized_sentinel_for = sentinel_for<_Sent, _Iter>
648 && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>>
649 && requires(const _Iter& __i, const _Sent& __s)
650 {
651 { __s - __i } -> same_as<iter_difference_t<_Iter>>;
652 { __i - __s } -> same_as<iter_difference_t<_Iter>>;
653 };
654
655 template<typename _Iter>
656 concept input_iterator = input_or_output_iterator<_Iter>
657 && indirectly_readable<_Iter>
658 && requires { typename __detail::__iter_concept<_Iter>; }
659 && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>;
660
661 template<typename _Iter, typename _Tp>
662 concept output_iterator = input_or_output_iterator<_Iter>
663 && indirectly_writable<_Iter, _Tp>
664 && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); };
665
666 template<typename _Iter>
667 concept forward_iterator = input_iterator<_Iter>
668 && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag>
669 && incrementable<_Iter> && sentinel_for<_Iter, _Iter>;
670
671 template<typename _Iter>
672 concept bidirectional_iterator = forward_iterator<_Iter>
673 && derived_from<__detail::__iter_concept<_Iter>,
674 bidirectional_iterator_tag>
675 && requires(_Iter __i)
676 {
677 { --__i } -> same_as<_Iter&>;
678 { __i-- } -> same_as<_Iter>;
679 };
680
681 template<typename _Iter>
682 concept random_access_iterator = bidirectional_iterator<_Iter>
683 && derived_from<__detail::__iter_concept<_Iter>,
684 random_access_iterator_tag>
685 && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter>
686 && requires(_Iter __i, const _Iter __j,
687 const iter_difference_t<_Iter> __n)
688 {
689 { __i += __n } -> same_as<_Iter&>;
690 { __j + __n } -> same_as<_Iter>;
691 { __n + __j } -> same_as<_Iter>;
692 { __i -= __n } -> same_as<_Iter&>;
693 { __j - __n } -> same_as<_Iter>;
694 { __j[__n] } -> same_as<iter_reference_t<_Iter>>;
695 };
696
697 template<typename _Iter>
698 concept contiguous_iterator = random_access_iterator<_Iter>
699 && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag>
700 && is_lvalue_reference_v<iter_reference_t<_Iter>>
701 && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>>
702 && requires(const _Iter& __i)
703 {
704 { std::to_address(__i) }
705 -> same_as<add_pointer_t<iter_reference_t<_Iter>>>;
706 };
707
708 // [indirectcallable], indirect callable requirements
709
710 // [indirectcallable.indirectinvocable], indirect callables
711
712 template<typename _Fn, typename _Iter>
713 concept indirectly_unary_invocable = indirectly_readable<_Iter>
714 && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&>
715 && invocable<_Fn&, iter_reference_t<_Iter>>
716 && invocable<_Fn&, iter_common_reference_t<_Iter>>
717 && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
718 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
719
720 template<typename _Fn, typename _Iter>
721 concept indirectly_regular_unary_invocable = indirectly_readable<_Iter>
722 && copy_constructible<_Fn>
723 && regular_invocable<_Fn&, iter_value_t<_Iter>&>
724 && regular_invocable<_Fn&, iter_reference_t<_Iter>>
725 && regular_invocable<_Fn&, iter_common_reference_t<_Iter>>
726 && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>,
727 invoke_result_t<_Fn&, iter_reference_t<_Iter>>>;
728
729 template<typename _Fn, typename _Iter>
730 concept indirect_unary_predicate = indirectly_readable<_Iter>
731 && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&>
732 && predicate<_Fn&, iter_reference_t<_Iter>>
733 && predicate<_Fn&, iter_common_reference_t<_Iter>>;
734
735 template<typename _Fn, typename _I1, typename _I2>
736 concept indirect_binary_predicate
737 = indirectly_readable<_I1> && indirectly_readable<_I2>
738 && copy_constructible<_Fn>
739 && predicate<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
740 && predicate<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
741 && predicate<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
742 && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
743 && predicate<_Fn&, iter_common_reference_t<_I1>,
744 iter_common_reference_t<_I2>>;
745
746 template<typename _Fn, typename _I1, typename _I2 = _I1>
747 concept indirect_equivalence_relation
748 = indirectly_readable<_I1> && indirectly_readable<_I2>
749 && copy_constructible<_Fn>
750 && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
751 && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
752 && equivalence_relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
753 && equivalence_relation<_Fn&, iter_reference_t<_I1>,
754 iter_reference_t<_I2>>
755 && equivalence_relation<_Fn&, iter_common_reference_t<_I1>,
756 iter_common_reference_t<_I2>>;
757
758 template<typename _Fn, typename _I1, typename _I2 = _I1>
759 concept indirect_strict_weak_order
760 = indirectly_readable<_I1> && indirectly_readable<_I2>
761 && copy_constructible<_Fn>
762 && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&>
763 && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>>
764 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&>
765 && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>>
766 && strict_weak_order<_Fn&, iter_common_reference_t<_I1>,
767 iter_common_reference_t<_I2>>;
768
769 template<typename _Fn, typename... _Is>
770 requires (indirectly_readable<_Is> && ...)
771 && invocable<_Fn, iter_reference_t<_Is>...>
772 using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Is>...>;
773
774 namespace __detail
775 {
776 template<typename _Iter, typename _Proj>
777 struct __projected
778 {
779 struct __type
780 {
781 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
782 indirect_result_t<_Proj&, _Iter> operator*() const; // not defined
783 };
784 };
785
786 template<weakly_incrementable _Iter, typename _Proj>
787 struct __projected<_Iter, _Proj>
788 {
789 struct __type
790 {
791 using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>;
792 using difference_type = iter_difference_t<_Iter>;
793 indirect_result_t<_Proj&, _Iter> operator*() const; // not defined
794 };
795 };
796 } // namespace __detail
797
798 /// [projected], projected
799 template<indirectly_readable _Iter,
800 indirectly_regular_unary_invocable<_Iter> _Proj>
801 using projected = typename __detail::__projected<_Iter, _Proj>::__type;
802
803 // [alg.req], common algorithm requirements
804
805 /// [alg.req.ind.move], concept `indirectly_movable`
806
807 template<typename _In, typename _Out>
808 concept indirectly_movable = indirectly_readable<_In>
809 && indirectly_writable<_Out, iter_rvalue_reference_t<_In>>;
810
811 template<typename _In, typename _Out>
812 concept indirectly_movable_storable = indirectly_movable<_In, _Out>
813 && indirectly_writable<_Out, iter_value_t<_In>>
814 && movable<iter_value_t<_In>>
815 && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>>
816 && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>;
817
818 /// [alg.req.ind.copy], concept `indirectly_copyable`
819 template<typename _In, typename _Out>
820 concept indirectly_copyable = indirectly_readable<_In>
821 && indirectly_writable<_Out, iter_reference_t<_In>>;
822
823 template<typename _In, typename _Out>
824 concept indirectly_copyable_storable = indirectly_copyable<_In, _Out>
825 && indirectly_writable<_Out, iter_value_t<_In>&>
826 && indirectly_writable<_Out, const iter_value_t<_In>&>
827 && indirectly_writable<_Out, iter_value_t<_In>&&>
828 && indirectly_writable<_Out, const iter_value_t<_In>&&>
829 && copyable<iter_value_t<_In>>
830 && constructible_from<iter_value_t<_In>, iter_reference_t<_In>>
831 && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
832
833 namespace ranges
834 {
835 namespace __cust_iswap
836 {
837 template<typename _It1, typename _It2>
838 void iter_swap(_It1, _It2) = delete;
839
840 template<typename _Tp, typename _Up>
841 concept __adl_iswap
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));
846 };
847
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)))
853 {
854 iter_value_t<_Xp> __old_value(iter_move(__x));
855 *__x = iter_move(__y);
856 return __old_value;
857 }
858
859 struct _IterSwap
860 {
861 private:
862 template<typename _Tp, typename _Up>
863 static constexpr bool
864 _S_noexcept()
865 {
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>()));
874 else
875 return noexcept(*std::declval<_Tp>()
876 = __iter_exchange_move(std::declval<_Up>(),
877 std::declval<_Tp>()));
878 }
879
880 public:
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>)
888 constexpr void
889 operator()(_Tp&& __e1, _Up&& __e2) const
890 noexcept(_S_noexcept<_Tp, _Up>())
891 {
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);
898 else
899 *__e1 = __iter_exchange_move(__e2, __e1);
900 }
901 };
902 } // namespace __cust_iswap
903
904 inline namespace __cust
905 {
906 inline constexpr __cust_iswap::_IterSwap iter_swap{};
907 } // inline namespace __cust
908
909 } // namespace ranges
910
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)
916 {
917 ranges::iter_swap(__i1, __i1);
918 ranges::iter_swap(__i2, __i2);
919 ranges::iter_swap(__i1, __i2);
920 ranges::iter_swap(__i2, __i1);
921 };
922
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>>;
929
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>;
935
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>>;
945
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>>;
951
952 struct unreachable_sentinel_t
953 {
954 template<weakly_incrementable _It>
955 friend constexpr bool
956 operator==(unreachable_sentinel_t, const _It&) noexcept
957 { return false; }
958 };
959
960 inline constexpr unreachable_sentinel_t unreachable_sentinel{};
961
962 // This is the namespace for [range.access] CPOs.
963 namespace ranges::__cust_access
964 {
965 using std::__detail::__class_or_enum;
966
967 struct _Decay_copy final
968 {
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{};
975
976 template<typename _Tp>
977 concept __member_begin = requires(_Tp& __t)
978 {
979 { __decay_copy(__t.begin()) } -> input_or_output_iterator;
980 };
981
982 // Poison pills so that unqualified lookup doesn't find std::begin.
983 void begin(auto&) = delete;
984 void begin(const auto&) = delete;
985
986 template<typename _Tp>
987 concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>>
988 && requires(_Tp& __t)
989 {
990 { __decay_copy(begin(__t)) } -> input_or_output_iterator;
991 };
992
993 // Simplified version of std::ranges::begin that only supports lvalues,
994 // for use by __range_iter_t below.
995 template<typename _Tp>
996 requires is_array_v<_Tp> || __member_begin<_Tp&> || __adl_begin<_Tp&>
997 auto
998 __begin(_Tp& __t)
999 {
1000 if constexpr (is_array_v<_Tp>)
1001 return __t + 0;
1002 else if constexpr (__member_begin<_Tp&>)
1003 return __t.begin();
1004 else
1005 return begin(__t);
1006 }
1007 } // namespace ranges::__cust_access
1008
1009 namespace __detail
1010 {
1011 // Implementation of std::ranges::iterator_t, without using ranges::begin.
1012 template<typename _Tp>
1013 using __range_iter_t
1014 = decltype(ranges::__cust_access::__begin(std::declval<_Tp&>()));
1015
1016 } // namespace __detail
1017
1018 #endif // C++20 library concepts
1019 _GLIBCXX_END_NAMESPACE_VERSION
1020 } // namespace std
1021 #endif // C++20
1022 #endif // _ITERATOR_CONCEPTS_H