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