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