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