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