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