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