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