Line data Source code
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
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 10764 : 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 10764 : 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 :
795 : namespace 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
|
