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