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