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