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