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