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