libstdc++
ranges_base.h
Go to the documentation of this file.
1 // Core concepts and definitions for <ranges> -*- C++ -*-
2 
3 // Copyright (C) 2019-2023 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/ranges_base.h
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly. @headername{ranges}
28  */
29 
30 #ifndef _GLIBCXX_RANGES_BASE_H
31 #define _GLIBCXX_RANGES_BASE_H 1
32 
33 #pragma GCC system_header
34 
35 #if __cplusplus > 201703L
36 #include <initializer_list>
37 #include <bits/stl_iterator.h>
38 #include <ext/numeric_traits.h>
39 #include <bits/max_size_type.h>
40 
41 #ifdef __cpp_lib_concepts
42 namespace std _GLIBCXX_VISIBILITY(default)
43 {
44 _GLIBCXX_BEGIN_NAMESPACE_VERSION
45 namespace ranges
46 {
47  template<typename>
48  inline constexpr bool disable_sized_range = false;
49 
50  template<typename _Tp>
51  inline constexpr bool enable_borrowed_range = false;
52 
53  namespace __detail
54  {
55  constexpr __max_size_type
56  __to_unsigned_like(__max_size_type __t) noexcept
57  { return __t; }
58 
59  constexpr __max_size_type
60  __to_unsigned_like(__max_diff_type __t) noexcept
61  { return __max_size_type(__t); }
62 
63  template<integral _Tp>
64  constexpr auto
65  __to_unsigned_like(_Tp __t) noexcept
66  { return static_cast<make_unsigned_t<_Tp>>(__t); }
67 
68 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
69  constexpr unsigned __int128
70  __to_unsigned_like(__int128 __t) noexcept
71  { return __t; }
72 
73  constexpr unsigned __int128
74  __to_unsigned_like(unsigned __int128 __t) noexcept
75  { return __t; }
76 #endif
77 
78  template<typename _Tp>
79  using __make_unsigned_like_t
80  = decltype(__detail::__to_unsigned_like(std::declval<_Tp>()));
81 
82  // Part of the constraints of ranges::borrowed_range
83  template<typename _Tp>
84  concept __maybe_borrowed_range
85  = is_lvalue_reference_v<_Tp>
86  || enable_borrowed_range<remove_cvref_t<_Tp>>;
87 
88  } // namespace __detail
89 
90  namespace __cust_access
91  {
92  using std::ranges::__detail::__maybe_borrowed_range;
93  using std::__detail::__range_iter_t;
94 
95  struct _Begin
96  {
97  private:
98  template<typename _Tp>
99  static constexpr bool
100  _S_noexcept()
101  {
102  if constexpr (is_array_v<remove_reference_t<_Tp>>)
103  return true;
104  else if constexpr (__member_begin<_Tp>)
105  return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
106  else
107  return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
108  }
109 
110  public:
111  template<__maybe_borrowed_range _Tp>
112  requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
113  || __adl_begin<_Tp>
114  constexpr auto
115  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
116  {
117  if constexpr (is_array_v<remove_reference_t<_Tp>>)
118  {
119  static_assert(is_lvalue_reference_v<_Tp>);
120  return __t + 0;
121  }
122  else if constexpr (__member_begin<_Tp>)
123  return __t.begin();
124  else
125  return begin(__t);
126  }
127  };
128 
129  template<typename _Tp>
130  concept __member_end = requires(_Tp& __t)
131  {
132  { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>;
133  };
134 
135  // Poison pills so that unqualified lookup doesn't find std::end.
136  void end(auto&) = delete;
137  void end(const auto&) = delete;
138 
139  template<typename _Tp>
140  concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
141  && requires(_Tp& __t)
142  {
143  { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>;
144  };
145 
146  struct _End
147  {
148  private:
149  template<typename _Tp>
150  static constexpr bool
151  _S_noexcept()
152  {
153  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
154  return true;
155  else if constexpr (__member_end<_Tp>)
156  return noexcept(__decay_copy(std::declval<_Tp&>().end()));
157  else
158  return noexcept(__decay_copy(end(std::declval<_Tp&>())));
159  }
160 
161  public:
162  template<__maybe_borrowed_range _Tp>
164  || __member_end<_Tp> || __adl_end<_Tp>
165  constexpr auto
166  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
167  {
168  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
169  {
170  static_assert(is_lvalue_reference_v<_Tp>);
171  return __t + extent_v<remove_reference_t<_Tp>>;
172  }
173  else if constexpr (__member_end<_Tp>)
174  return __t.end();
175  else
176  return end(__t);
177  }
178  };
179 
180  template<typename _Tp>
181  concept __member_rbegin = requires(_Tp& __t)
182  {
183  { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
184  };
185 
186  void rbegin(auto&) = delete;
187  void rbegin(const auto&) = delete;
188 
189  template<typename _Tp>
190  concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
191  && requires(_Tp& __t)
192  {
193  { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
194  };
195 
196  template<typename _Tp>
197  concept __reversable = requires(_Tp& __t)
198  {
199  { _Begin{}(__t) } -> bidirectional_iterator;
200  { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
201  };
202 
203  struct _RBegin
204  {
205  private:
206  template<typename _Tp>
207  static constexpr bool
208  _S_noexcept()
209  {
210  if constexpr (__member_rbegin<_Tp>)
211  return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
212  else if constexpr (__adl_rbegin<_Tp>)
213  return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
214  else
215  {
216  if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
217  {
218  using _It = decltype(_End{}(std::declval<_Tp&>()));
219  // std::reverse_iterator copy-initializes its member.
220  return is_nothrow_copy_constructible_v<_It>;
221  }
222  else
223  return false;
224  }
225  }
226 
227  public:
228  template<__maybe_borrowed_range _Tp>
229  requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
230  constexpr auto
231  operator()[[nodiscard]](_Tp&& __t) const
232  noexcept(_S_noexcept<_Tp&>())
233  {
234  if constexpr (__member_rbegin<_Tp>)
235  return __t.rbegin();
236  else if constexpr (__adl_rbegin<_Tp>)
237  return rbegin(__t);
238  else
239  return std::make_reverse_iterator(_End{}(__t));
240  }
241  };
242 
243  template<typename _Tp>
244  concept __member_rend = requires(_Tp& __t)
245  {
246  { __decay_copy(__t.rend()) }
247  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
248  };
249 
250  void rend(auto&) = delete;
251  void rend(const auto&) = delete;
252 
253  template<typename _Tp>
254  concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
255  && requires(_Tp& __t)
256  {
257  { __decay_copy(rend(__t)) }
258  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
259  };
260 
261  struct _REnd
262  {
263  private:
264  template<typename _Tp>
265  static constexpr bool
266  _S_noexcept()
267  {
268  if constexpr (__member_rend<_Tp>)
269  return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
270  else if constexpr (__adl_rend<_Tp>)
271  return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
272  else
273  {
274  if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
275  {
276  using _It = decltype(_Begin{}(std::declval<_Tp&>()));
277  // std::reverse_iterator copy-initializes its member.
278  return is_nothrow_copy_constructible_v<_It>;
279  }
280  else
281  return false;
282  }
283  }
284 
285  public:
286  template<__maybe_borrowed_range _Tp>
287  requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
288  constexpr auto
289  operator()[[nodiscard]](_Tp&& __t) const
290  noexcept(_S_noexcept<_Tp&>())
291  {
292  if constexpr (__member_rend<_Tp>)
293  return __t.rend();
294  else if constexpr (__adl_rend<_Tp>)
295  return rend(__t);
296  else
297  return std::make_reverse_iterator(_Begin{}(__t));
298  }
299  };
300 
301  template<typename _Tp>
302  concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
303  && requires(_Tp& __t)
304  {
305  { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
306  };
307 
308  void size(auto&) = delete;
309  void size(const auto&) = delete;
310 
311  template<typename _Tp>
312  concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
313  && !disable_sized_range<remove_cvref_t<_Tp>>
314  && requires(_Tp& __t)
315  {
316  { __decay_copy(size(__t)) } -> __detail::__is_integer_like;
317  };
318 
319  template<typename _Tp>
320  concept __sentinel_size = requires(_Tp& __t)
321  {
322  requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
323 
324  { _Begin{}(__t) } -> forward_iterator;
325 
326  { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
327 
328  __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
329  };
330 
331  struct _Size
332  {
333  private:
334  template<typename _Tp>
335  static constexpr bool
336  _S_noexcept()
337  {
338  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
339  return true;
340  else if constexpr (__member_size<_Tp>)
341  return noexcept(__decay_copy(std::declval<_Tp&>().size()));
342  else if constexpr (__adl_size<_Tp>)
343  return noexcept(__decay_copy(size(std::declval<_Tp&>())));
344  else if constexpr (__sentinel_size<_Tp>)
345  return noexcept(_End{}(std::declval<_Tp&>())
346  - _Begin{}(std::declval<_Tp&>()));
347  }
348 
349  public:
350  template<typename _Tp>
351  requires is_bounded_array_v<remove_reference_t<_Tp>>
352  || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
353  constexpr auto
354  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
355  {
356  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
357  return extent_v<remove_reference_t<_Tp>>;
358  else if constexpr (__member_size<_Tp>)
359  return __t.size();
360  else if constexpr (__adl_size<_Tp>)
361  return size(__t);
362  else if constexpr (__sentinel_size<_Tp>)
363  return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
364  }
365  };
366 
367  struct _SSize
368  {
369  // _GLIBCXX_RESOLVE_LIB_DEFECTS
370  // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E)
371  template<typename _Tp>
372  requires requires (_Tp& __t) { _Size{}(__t); }
373  constexpr auto
374  operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t)))
375  {
376  auto __size = _Size{}(__t);
377  using __size_type = decltype(__size);
378  // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>.
379  if constexpr (integral<__size_type>)
380  {
382  if constexpr (__int_traits<__size_type>::__digits
383  < __int_traits<ptrdiff_t>::__digits)
384  return static_cast<ptrdiff_t>(__size);
385  else
386  return static_cast<make_signed_t<__size_type>>(__size);
387  }
388 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
389  // For strict-ansi modes integral<__int128> is false
390  else if constexpr (__detail::__is_int128<__size_type>)
391  return static_cast<__int128>(__size);
392 #endif
393  else // Must be one of __max_diff_type or __max_size_type.
394  return __detail::__max_diff_type(__size);
395  }
396  };
397 
398  template<typename _Tp>
399  concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
400 
401  template<typename _Tp>
402  concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
403 
404  template<typename _Tp>
405  concept __eq_iter_empty = requires(_Tp& __t)
406  {
407  requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
408 
409  { _Begin{}(__t) } -> forward_iterator;
410 
411  bool(_Begin{}(__t) == _End{}(__t));
412  };
413 
414  struct _Empty
415  {
416  private:
417  template<typename _Tp>
418  static constexpr bool
419  _S_noexcept()
420  {
421  if constexpr (__member_empty<_Tp>)
422  return noexcept(bool(std::declval<_Tp&>().empty()));
423  else if constexpr (__size0_empty<_Tp>)
424  return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
425  else
426  return noexcept(bool(_Begin{}(std::declval<_Tp&>())
427  == _End{}(std::declval<_Tp&>())));
428  }
429 
430  public:
431  template<typename _Tp>
432  requires __member_empty<_Tp> || __size0_empty<_Tp>
433  || __eq_iter_empty<_Tp>
434  constexpr bool
435  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
436  {
437  if constexpr (__member_empty<_Tp>)
438  return bool(__t.empty());
439  else if constexpr (__size0_empty<_Tp>)
440  return _Size{}(__t) == 0;
441  else
442  return bool(_Begin{}(__t) == _End{}(__t));
443  }
444  };
445 
446  template<typename _Tp>
447  concept __pointer_to_object = is_pointer_v<_Tp>
448  && is_object_v<remove_pointer_t<_Tp>>;
449 
450  template<typename _Tp>
451  concept __member_data = requires(_Tp& __t)
452  {
453  { __decay_copy(__t.data()) } -> __pointer_to_object;
454  };
455 
456  template<typename _Tp>
457  concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;
458 
459  struct _Data
460  {
461  private:
462  template<typename _Tp>
463  static constexpr bool
464  _S_noexcept()
465  {
466  if constexpr (__member_data<_Tp>)
467  return noexcept(__decay_copy(std::declval<_Tp&>().data()));
468  else
469  return noexcept(_Begin{}(std::declval<_Tp&>()));
470  }
471 
472  public:
473  template<__maybe_borrowed_range _Tp>
474  requires __member_data<_Tp> || __begin_data<_Tp>
475  constexpr auto
476  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
477  {
478  if constexpr (__member_data<_Tp>)
479  return __t.data();
480  else
481  return std::to_address(_Begin{}(__t));
482  }
483  };
484 
485  } // namespace __cust_access
486 
487  inline namespace __cust
488  {
489  inline constexpr __cust_access::_Begin begin{};
490  inline constexpr __cust_access::_End end{};
491  inline constexpr __cust_access::_RBegin rbegin{};
492  inline constexpr __cust_access::_REnd rend{};
493  inline constexpr __cust_access::_Size size{};
494  inline constexpr __cust_access::_SSize ssize{};
495  inline constexpr __cust_access::_Empty empty{};
496  inline constexpr __cust_access::_Data data{};
497  }
498 
499  /// [range.range] The range concept.
500  template<typename _Tp>
501  concept range = requires(_Tp& __t)
502  {
503  ranges::begin(__t);
504  ranges::end(__t);
505  };
506 
507  /// [range.range] The borrowed_range concept.
508  template<typename _Tp>
509  concept borrowed_range
510  = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
511 
512  template<typename _Tp>
513  using iterator_t = std::__detail::__range_iter_t<_Tp>;
514 
515  template<range _Range>
516  using sentinel_t = decltype(ranges::end(std::declval<_Range&>()));
517 
518 #if __cplusplus > 202002L
519  template<range _Range>
520  using const_iterator_t = const_iterator<iterator_t<_Range>>;
521 
522  template<range _Range>
523  using const_sentinel_t = const_sentinel<sentinel_t<_Range>>;
524 
525  template<range _Range>
526  using range_const_reference_t = iter_const_reference_t<iterator_t<_Range>>;
527 #endif
528 
529  template<range _Range>
530  using range_difference_t = iter_difference_t<iterator_t<_Range>>;
531 
532  template<range _Range>
533  using range_value_t = iter_value_t<iterator_t<_Range>>;
534 
535  template<range _Range>
536  using range_reference_t = iter_reference_t<iterator_t<_Range>>;
537 
538  template<range _Range>
539  using range_rvalue_reference_t
540  = iter_rvalue_reference_t<iterator_t<_Range>>;
541 
542  /// [range.sized] The sized_range concept.
543  template<typename _Tp>
544  concept sized_range = range<_Tp>
545  && requires(_Tp& __t) { ranges::size(__t); };
546 
547  template<sized_range _Range>
548  using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
549 
550  template<typename _Derived>
551  requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
552  class view_interface; // defined in <bits/ranges_util.h>
553 
554  namespace __detail
555  {
556  template<typename _Tp, typename _Up>
557  requires (!same_as<_Tp, view_interface<_Up>>)
558  void __is_derived_from_view_interface_fn(const _Tp&,
559  const view_interface<_Up>&); // not defined
560 
561  // Returns true iff _Tp has exactly one public base class that's a
562  // specialization of view_interface.
563  template<typename _Tp>
564  concept __is_derived_from_view_interface
565  = requires (_Tp __t) { __is_derived_from_view_interface_fn(__t, __t); };
566  } // namespace __detail
567 
568  /// [range.view] The ranges::view_base type.
569  struct view_base { };
570 
571  /// [range.view] The ranges::enable_view boolean.
572  template<typename _Tp>
573  inline constexpr bool enable_view = derived_from<_Tp, view_base>
574  || __detail::__is_derived_from_view_interface<_Tp>;
575 
576  /// [range.view] The ranges::view concept.
577  template<typename _Tp>
578  concept view
579  = range<_Tp> && movable<_Tp> && enable_view<_Tp>;
580 
581  // [range.refinements]
582 
583  /// A range for which ranges::begin returns an output iterator.
584  template<typename _Range, typename _Tp>
585  concept output_range
586  = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
587 
588  /// A range for which ranges::begin returns an input iterator.
589  template<typename _Tp>
590  concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
591 
592  /// A range for which ranges::begin returns a forward iterator.
593  template<typename _Tp>
594  concept forward_range
595  = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
596 
597  /// A range for which ranges::begin returns a bidirectional iterator.
598  template<typename _Tp>
599  concept bidirectional_range
600  = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
601 
602  /// A range for which ranges::begin returns a random access iterator.
603  template<typename _Tp>
604  concept random_access_range
605  = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
606 
607  /// A range for which ranges::begin returns a contiguous iterator.
608  template<typename _Tp>
609  concept contiguous_range
610  = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
611  && requires(_Tp& __t)
612  {
613  { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
614  };
615 
616  /// A range for which ranges::begin and ranges::end return the same type.
617  template<typename _Tp>
618  concept common_range
619  = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
620 
621 #if __cplusplus > 202002L
622  template<typename _Tp>
623  concept constant_range
624  = input_range<_Tp> && std::__detail::__constant_iterator<iterator_t<_Tp>>;
625 #endif
626 
627  namespace __cust_access
628  {
629 #if __cplusplus > 202020L
630  template<typename _Range>
631  constexpr auto&
632  __possibly_const_range(_Range& __r) noexcept
633  {
634  if constexpr (constant_range<const _Range> && !constant_range<_Range>)
635  return const_cast<const _Range&>(__r);
636  else
637  return __r;
638  }
639 #else
640  // If _To is an lvalue-reference, return const _Tp&, otherwise const _Tp&&.
641  template<typename _To, typename _Tp>
642  constexpr decltype(auto)
643  __as_const(_Tp& __t) noexcept
644  {
645  static_assert(std::is_same_v<_To&, _Tp&>);
646 
647  if constexpr (is_lvalue_reference_v<_To>)
648  return const_cast<const _Tp&>(__t);
649  else
650  return static_cast<const _Tp&&>(__t);
651  }
652 #endif
653 
654  struct _CBegin
655  {
656 #if __cplusplus > 202002L
657  template<__maybe_borrowed_range _Tp>
658  [[nodiscard]]
659  constexpr auto
660  operator()(_Tp&& __t) const
661  noexcept(noexcept(std::make_const_iterator
662  (ranges::begin(__cust_access::__possibly_const_range(__t)))))
663  requires requires { std::make_const_iterator
664  (ranges::begin(__cust_access::__possibly_const_range(__t))); }
665  {
666  auto& __r = __cust_access::__possibly_const_range(__t);
667  return const_iterator_t<decltype(__r)>(ranges::begin(__r));
668  }
669 #else
670  template<typename _Tp>
671  [[nodiscard]]
672  constexpr auto
673  operator()(_Tp&& __e) const
674  noexcept(noexcept(_Begin{}(__cust_access::__as_const<_Tp>(__e))))
675  requires requires { _Begin{}(__cust_access::__as_const<_Tp>(__e)); }
676  {
677  return _Begin{}(__cust_access::__as_const<_Tp>(__e));
678  }
679 #endif
680  };
681 
682  struct _CEnd final
683  {
684 #if __cplusplus > 202002L
685  template<__maybe_borrowed_range _Tp>
686  [[nodiscard]]
687  constexpr auto
688  operator()(_Tp&& __t) const
689  noexcept(noexcept(std::make_const_sentinel
690  (ranges::end(__cust_access::__possibly_const_range(__t)))))
691  requires requires { std::make_const_sentinel
692  (ranges::end(__cust_access::__possibly_const_range(__t))); }
693  {
694  auto& __r = __cust_access::__possibly_const_range(__t);
695  return const_sentinel_t<decltype(__r)>(ranges::end(__r));
696  }
697 #else
698  template<typename _Tp>
699  [[nodiscard]]
700  constexpr auto
701  operator()(_Tp&& __e) const
702  noexcept(noexcept(_End{}(__cust_access::__as_const<_Tp>(__e))))
703  requires requires { _End{}(__cust_access::__as_const<_Tp>(__e)); }
704  {
705  return _End{}(__cust_access::__as_const<_Tp>(__e));
706  }
707 #endif
708  };
709 
710  struct _CRBegin
711  {
712 #if __cplusplus > 202002L
713  template<__maybe_borrowed_range _Tp>
714  [[nodiscard]]
715  constexpr auto
716  operator()(_Tp&& __t) const
717  noexcept(noexcept(std::make_const_iterator
718  (ranges::rbegin(__cust_access::__possibly_const_range(__t)))))
719  requires requires { std::make_const_iterator
720  (ranges::rbegin(__cust_access::__possibly_const_range(__t))); }
721  {
722  auto& __r = __cust_access::__possibly_const_range(__t);
723  return const_iterator<decltype(ranges::rbegin(__r))>(ranges::rbegin(__r));
724  }
725 #else
726  template<typename _Tp>
727  [[nodiscard]]
728  constexpr auto
729  operator()(_Tp&& __e) const
730  noexcept(noexcept(_RBegin{}(__cust_access::__as_const<_Tp>(__e))))
731  requires requires { _RBegin{}(__cust_access::__as_const<_Tp>(__e)); }
732  {
733  return _RBegin{}(__cust_access::__as_const<_Tp>(__e));
734  }
735 #endif
736  };
737 
738  struct _CREnd
739  {
740 #if __cplusplus > 202002L
741  template<__maybe_borrowed_range _Tp>
742  [[nodiscard]]
743  constexpr auto
744  operator()(_Tp&& __t) const
745  noexcept(noexcept(std::make_const_sentinel
746  (ranges::rend(__cust_access::__possibly_const_range(__t)))))
747  requires requires { std::make_const_sentinel
748  (ranges::rend(__cust_access::__possibly_const_range(__t))); }
749  {
750  auto& __r = __cust_access::__possibly_const_range(__t);
751  return const_sentinel<decltype(ranges::rend(__r))>(ranges::rend(__r));
752  }
753 #else
754  template<typename _Tp>
755  [[nodiscard]]
756  constexpr auto
757  operator()(_Tp&& __e) const
758  noexcept(noexcept(_REnd{}(__cust_access::__as_const<_Tp>(__e))))
759  requires requires { _REnd{}(__cust_access::__as_const<_Tp>(__e)); }
760  {
761  return _REnd{}(__cust_access::__as_const<_Tp>(__e));
762  }
763 #endif
764  };
765 
766  struct _CData
767  {
768 #if __cplusplus > 202002L
769  template<__maybe_borrowed_range _Tp>
770  [[nodiscard]]
771  constexpr const auto*
772  operator()(_Tp&& __t) const
773  noexcept(noexcept(ranges::data(__cust_access::__possibly_const_range(__t))))
774  requires requires { ranges::data(__cust_access::__possibly_const_range(__t)); }
775  { return ranges::data(__cust_access::__possibly_const_range(__t)); }
776 #else
777  template<typename _Tp>
778  [[nodiscard]]
779  constexpr auto
780  operator()(_Tp&& __e) const
781  noexcept(noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e))))
782  requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); }
783  {
784  return _Data{}(__cust_access::__as_const<_Tp>(__e));
785  }
786 #endif
787  };
788 
789  } // namespace __cust_access
790 
791  inline namespace __cust
792  {
793  inline constexpr __cust_access::_CBegin cbegin{};
794  inline constexpr __cust_access::_CEnd cend{};
795  inline constexpr __cust_access::_CRBegin crbegin{};
796  inline constexpr __cust_access::_CREnd crend{};
797  inline constexpr __cust_access::_CData cdata{};
798  }
799 
800  namespace __detail
801  {
802  template<typename _Tp>
803  inline constexpr bool __is_initializer_list = false;
804 
805  template<typename _Tp>
806  inline constexpr bool __is_initializer_list<initializer_list<_Tp>> = true;
807  } // namespace __detail
808 
809  /// A range which can be safely converted to a view.
810  template<typename _Tp>
811  concept viewable_range = range<_Tp>
812  && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
813  || (!view<remove_cvref_t<_Tp>>
814  && (is_lvalue_reference_v<_Tp>
815  || (movable<remove_reference_t<_Tp>>
816  && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>))));
817 
818  // [range.iter.ops] range iterator operations
819 
820  struct __advance_fn final
821  {
822  template<input_or_output_iterator _It>
823  constexpr void
824  operator()(_It& __it, iter_difference_t<_It> __n) const
825  {
826  if constexpr (random_access_iterator<_It>)
827  __it += __n;
828  else if constexpr (bidirectional_iterator<_It>)
829  {
830  if (__n > 0)
831  {
832  do
833  {
834  ++__it;
835  }
836  while (--__n);
837  }
838  else if (__n < 0)
839  {
840  do
841  {
842  --__it;
843  }
844  while (++__n);
845  }
846  }
847  else
848  {
849  // cannot decrement a non-bidirectional iterator
850  __glibcxx_assert(__n >= 0);
851  while (__n-- > 0)
852  ++__it;
853  }
854  }
855 
856  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
857  constexpr void
858  operator()(_It& __it, _Sent __bound) const
859  {
860  if constexpr (assignable_from<_It&, _Sent>)
861  __it = std::move(__bound);
862  else if constexpr (sized_sentinel_for<_Sent, _It>)
863  (*this)(__it, __bound - __it);
864  else
865  {
866  while (__it != __bound)
867  ++__it;
868  }
869  }
870 
871  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
872  constexpr iter_difference_t<_It>
873  operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
874  {
875  if constexpr (sized_sentinel_for<_Sent, _It>)
876  {
877  const auto __diff = __bound - __it;
878 
879  if (__diff == 0)
880  return __n;
881  else if (__diff > 0 ? __n >= __diff : __n <= __diff)
882  {
883  (*this)(__it, __bound);
884  return __n - __diff;
885  }
886  else if (__n != 0) [[likely]]
887  {
888  // n and bound must not lead in opposite directions:
889  __glibcxx_assert((__n < 0) == (__diff < 0));
890 
891  (*this)(__it, __n);
892  return 0;
893  }
894  else
895  return 0;
896  }
897  else if (__it == __bound || __n == 0)
898  return __n;
899  else if (__n > 0)
900  {
901  iter_difference_t<_It> __m = 0;
902  do
903  {
904  ++__it;
905  ++__m;
906  }
907  while (__m != __n && __it != __bound);
908  return __n - __m;
909  }
910  else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
911  {
912  iter_difference_t<_It> __m = 0;
913  do
914  {
915  --__it;
916  --__m;
917  }
918  while (__m != __n && __it != __bound);
919  return __n - __m;
920  }
921  else
922  {
923  // cannot decrement a non-bidirectional iterator
924  __glibcxx_assert(__n >= 0);
925  return __n;
926  }
927  }
928 
929  void operator&() const = delete;
930  };
931 
932  inline constexpr __advance_fn advance{};
933 
934  struct __distance_fn final
935  {
936  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
937  requires (!sized_sentinel_for<_Sent, _It>)
938  constexpr iter_difference_t<_It>
939  operator()[[nodiscard]](_It __first, _Sent __last) const
940  {
941  iter_difference_t<_It> __n = 0;
942  while (__first != __last)
943  {
944  ++__first;
945  ++__n;
946  }
947  return __n;
948  }
949 
950  template<input_or_output_iterator _It, sized_sentinel_for<_It> _Sent>
951  [[nodiscard]]
952  constexpr iter_difference_t<_It>
953  operator()(const _It& __first, const _Sent& __last) const
954  {
955  return __last - __first;
956  }
957 
958  template<range _Range>
959  [[nodiscard]]
960  constexpr range_difference_t<_Range>
961  operator()(_Range&& __r) const
962  {
963  if constexpr (sized_range<_Range>)
964  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
965  else
966  return (*this)(ranges::begin(__r), ranges::end(__r));
967  }
968 
969  void operator&() const = delete;
970  };
971 
972  inline constexpr __distance_fn distance{};
973 
974  struct __next_fn final
975  {
976  template<input_or_output_iterator _It>
977  [[nodiscard]]
978  constexpr _It
979  operator()(_It __x) const
980  {
981  ++__x;
982  return __x;
983  }
984 
985  template<input_or_output_iterator _It>
986  [[nodiscard]]
987  constexpr _It
988  operator()(_It __x, iter_difference_t<_It> __n) const
989  {
990  ranges::advance(__x, __n);
991  return __x;
992  }
993 
994  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
995  [[nodiscard]]
996  constexpr _It
997  operator()(_It __x, _Sent __bound) const
998  {
999  ranges::advance(__x, __bound);
1000  return __x;
1001  }
1002 
1003  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1004  [[nodiscard]]
1005  constexpr _It
1006  operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
1007  {
1008  ranges::advance(__x, __n, __bound);
1009  return __x;
1010  }
1011 
1012  void operator&() const = delete;
1013  };
1014 
1015  inline constexpr __next_fn next{};
1016 
1017  struct __prev_fn final
1018  {
1019  template<bidirectional_iterator _It>
1020  [[nodiscard]]
1021  constexpr _It
1022  operator()(_It __x) const
1023  {
1024  --__x;
1025  return __x;
1026  }
1027 
1028  template<bidirectional_iterator _It>
1029  [[nodiscard]]
1030  constexpr _It
1031  operator()(_It __x, iter_difference_t<_It> __n) const
1032  {
1033  ranges::advance(__x, -__n);
1034  return __x;
1035  }
1036 
1037  template<bidirectional_iterator _It>
1038  [[nodiscard]]
1039  constexpr _It
1040  operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
1041  {
1042  ranges::advance(__x, -__n, __bound);
1043  return __x;
1044  }
1045 
1046  void operator&() const = delete;
1047  };
1048 
1049  inline constexpr __prev_fn prev{};
1050 
1051  /// Type returned by algorithms instead of a dangling iterator or subrange.
1052  struct dangling
1053  {
1054  constexpr dangling() noexcept = default;
1055  template<typename... _Args>
1056  constexpr dangling(_Args&&...) noexcept { }
1057  };
1058 
1059  template<range _Range>
1060  using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
1061  iterator_t<_Range>,
1062  dangling>;
1063 
1064 } // namespace ranges
1065 _GLIBCXX_END_NAMESPACE_VERSION
1066 } // namespace std
1067 #endif // library concepts
1068 #endif // C++20
1069 #endif // _GLIBCXX_RANGES_BASE_H
std::ranges::dangling
Type returned by algorithms instead of a dangling iterator or subrange.
Definition: ranges_base.h:1052
std::ranges::enable_view
constexpr bool enable_view
[range.view] The ranges::enable_view boolean.
Definition: ranges_base.h:573
std::operator&
constexpr bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition: bitset:1553
std::size
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:264
std::rbegin
constexpr auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
Definition: range_access.h:150
std::ranges::sized_range
concept sized_range
[range.sized] The sized_range concept.
Definition: ranges_base.h:544
std::ranges::contiguous_range
concept contiguous_range
A range for which ranges::begin returns a contiguous iterator.
Definition: ranges_base.h:610
std::cbegin
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:126
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1243
std::to_address
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition: ptr_traits.h:250
std::make_reverse_iterator
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
Definition: bits/stl_iterator.h:654
std::ranges::viewable_range
concept viewable_range
A range which can be safely converted to a view.
Definition: ranges_base.h:811
std::ranges::forward_range
concept forward_range
A range for which ranges::begin returns a forward iterator.
Definition: ranges_base.h:595
stl_iterator.h
std::remove_reference_t
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1640
std::ranges::bidirectional_range
concept bidirectional_range
A range for which ranges::begin returns a bidirectional iterator.
Definition: ranges_base.h:600
numeric_traits.h
std::ranges::random_access_range
concept random_access_range
A range for which ranges::begin returns a random access iterator.
Definition: ranges_base.h:605
std::is_unbounded_array_v
constexpr bool is_unbounded_array_v
True for a type that is an array of unknown bound.
Definition: type_traits:3499
std::empty
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:284
std::ranges::view_base
[range.view] The ranges::view_base type.
Definition: ranges_base.h:569
initializer_list
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition: type_traits:2386
std::cend
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:138
std::remove_cvref_t
typename remove_cvref< _Tp >::type remove_cvref_t
Definition: type_traits:3442
std::same_as
concept same_as
[concept.same], concept same_as
Definition: concepts:63
std::ranges::view_interface
The ranges::view_interface class template.
Definition: ranges_base.h:552
max_size_type.h
std::crbegin
constexpr auto crbegin(const _Container &__cont) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
Definition: range_access.h:238
std::is_bounded_array_v
constexpr bool is_bounded_array_v
True for a type that is an array of known bound.
Definition: type_traits:3490
std::ranges::range
concept range
[range.range] The range concept.
Definition: ranges_base.h:501
std::ranges::view
concept view
[range.view] The ranges::view concept.
Definition: ranges_base.h:579
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:148
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:220
std::crend
constexpr auto crend(const _Container &__cont) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
Definition: range_access.h:249
std::data
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
Definition: range_access.h:314
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1221
std
ISO C++ entities toplevel namespace is std.
std::ranges::output_range
concept output_range
A range for which ranges::begin returns an output iterator.
Definition: ranges_base.h:586
std::ranges::input_range
concept input_range
A range for which ranges::begin returns an input iterator.
Definition: ranges_base.h:590
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:97
std::rend
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
Definition: range_access.h:172
__gnu_cxx::__int_traits
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
Definition: ext/numeric_traits.h:138