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