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