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