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