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