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