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