libstdc++
ranges_base.h
Go to the documentation of this file.
1 // Core concepts and definitions for <ranges> -*- C++ -*-
2 
3 // Copyright (C) 2019-2021 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  { _Begin{}(__t) } -> forward_iterator;
387 
388  { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
389 
390  __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
391  };
392 
393  struct _Size
394  {
395  private:
396  template<typename _Tp>
397  static constexpr bool
398  _S_noexcept()
399  {
400  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
401  return true;
402  else if constexpr (__member_size<_Tp>)
403  return noexcept(__decay_copy(std::declval<_Tp&>().size()));
404  else if constexpr (__adl_size<_Tp>)
405  return noexcept(__decay_copy(size(std::declval<_Tp&>())));
406  else if constexpr (__sentinel_size<_Tp>)
407  return noexcept(_End{}(std::declval<_Tp&>())
408  - _Begin{}(std::declval<_Tp&>()));
409  }
410 
411  public:
412  template<typename _Tp>
413  requires is_bounded_array_v<remove_reference_t<_Tp>>
414  || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
415  constexpr auto
416  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
417  {
418  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
419  return extent_v<remove_reference_t<_Tp>>;
420  else if constexpr (__member_size<_Tp>)
421  return __t.size();
422  else if constexpr (__adl_size<_Tp>)
423  return size(__t);
424  else if constexpr (__sentinel_size<_Tp>)
425  return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
426  }
427  };
428 
429  struct _SSize
430  {
431  // _GLIBCXX_RESOLVE_LIB_DEFECTS
432  // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E)
433  template<typename _Tp>
434  requires requires (_Tp& __t) { _Size{}(__t); }
435  constexpr auto
436  operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t)))
437  {
438  auto __size = _Size{}(__t);
439  using __size_type = decltype(__size);
440  // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>.
441  if constexpr (integral<__size_type>)
442  {
444  if constexpr (__int_traits<__size_type>::__digits
445  < __int_traits<ptrdiff_t>::__digits)
446  return static_cast<ptrdiff_t>(__size);
447  else
448  return static_cast<make_signed_t<__size_type>>(__size);
449  }
450 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
451  // For strict-ansi modes integral<__int128> is false
452  else if constexpr (__detail::__is_int128<__size_type>)
453  return static_cast<__int128>(__size);
454 #endif
455  else // Must be one of __max_diff_type or __max_size_type.
456  return __detail::__max_diff_type(__size);
457  }
458  };
459 
460  template<typename _Tp>
461  concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
462 
463  template<typename _Tp>
464  concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
465 
466  template<typename _Tp>
467  concept __eq_iter_empty = requires(_Tp& __t)
468  {
469  { _Begin{}(__t) } -> forward_iterator;
470 
471  bool(_Begin{}(__t) == _End{}(__t));
472  };
473 
474  struct _Empty
475  {
476  private:
477  template<typename _Tp>
478  static constexpr bool
479  _S_noexcept()
480  {
481  if constexpr (__member_empty<_Tp>)
482  return noexcept(bool(std::declval<_Tp&>().empty()));
483  else if constexpr (__size0_empty<_Tp>)
484  return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
485  else
486  return noexcept(bool(_Begin{}(std::declval<_Tp&>())
487  == _End{}(std::declval<_Tp&>())));
488  }
489 
490  public:
491  template<typename _Tp>
492  requires __member_empty<_Tp> || __size0_empty<_Tp>
493  || __eq_iter_empty<_Tp>
494  constexpr bool
495  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
496  {
497  if constexpr (__member_empty<_Tp>)
498  return bool(__t.empty());
499  else if constexpr (__size0_empty<_Tp>)
500  return _Size{}(__t) == 0;
501  else
502  return bool(_Begin{}(__t) == _End{}(__t));
503  }
504  };
505 
506  template<typename _Tp>
507  concept __pointer_to_object = is_pointer_v<_Tp>
508  && is_object_v<remove_pointer_t<_Tp>>;
509 
510  template<typename _Tp>
511  concept __member_data = requires(_Tp& __t)
512  {
513  { __decay_copy(__t.data()) } -> __pointer_to_object;
514  };
515 
516  template<typename _Tp>
517  concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;
518 
519  struct _Data
520  {
521  private:
522  template<typename _Tp>
523  static constexpr bool
524  _S_noexcept()
525  {
526  if constexpr (__member_data<_Tp>)
527  return noexcept(__decay_copy(std::declval<_Tp&>().data()));
528  else
529  return noexcept(_Begin{}(std::declval<_Tp&>()));
530  }
531 
532  public:
533  template<__maybe_borrowed_range _Tp>
534  requires __member_data<_Tp> || __begin_data<_Tp>
535  constexpr auto
536  operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
537  {
538  if constexpr (__member_data<_Tp>)
539  return __t.data();
540  else
541  return std::to_address(_Begin{}(__t));
542  }
543  };
544 
545  struct _CData
546  {
547  template<typename _Tp>
548  [[nodiscard]]
549  constexpr auto
550  operator()(_Tp&& __e) const
551  noexcept(noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e))))
552  requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); }
553  {
554  return _Data{}(__cust_access::__as_const<_Tp>(__e));
555  }
556  };
557 
558  } // namespace __cust_access
559 
560  inline namespace __cust
561  {
562  inline constexpr __cust_access::_Begin begin{};
563  inline constexpr __cust_access::_End end{};
564  inline constexpr __cust_access::_CBegin cbegin{};
565  inline constexpr __cust_access::_CEnd cend{};
566  inline constexpr __cust_access::_RBegin rbegin{};
567  inline constexpr __cust_access::_REnd rend{};
568  inline constexpr __cust_access::_CRBegin crbegin{};
569  inline constexpr __cust_access::_CREnd crend{};
570  inline constexpr __cust_access::_Size size{};
571  inline constexpr __cust_access::_SSize ssize{};
572  inline constexpr __cust_access::_Empty empty{};
573  inline constexpr __cust_access::_Data data{};
574  inline constexpr __cust_access::_CData cdata{};
575  }
576 
577  /// [range.range] The range concept.
578  template<typename _Tp>
579  concept range = requires(_Tp& __t)
580  {
581  ranges::begin(__t);
582  ranges::end(__t);
583  };
584 
585  /// [range.range] The borrowed_range concept.
586  template<typename _Tp>
588  = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
589 
590  template<typename _Tp>
591  using iterator_t = std::__detail::__range_iter_t<_Tp>;
592 
593  template<range _Range>
594  using sentinel_t = decltype(ranges::end(std::declval<_Range&>()));
595 
596  template<range _Range>
597  using range_difference_t = iter_difference_t<iterator_t<_Range>>;
598 
599  template<range _Range>
600  using range_value_t = iter_value_t<iterator_t<_Range>>;
601 
602  template<range _Range>
603  using range_reference_t = iter_reference_t<iterator_t<_Range>>;
604 
605  template<range _Range>
606  using range_rvalue_reference_t
607  = iter_rvalue_reference_t<iterator_t<_Range>>;
608 
609  /// [range.sized] The sized_range concept.
610  template<typename _Tp>
611  concept sized_range = range<_Tp>
612  && requires(_Tp& __t) { ranges::size(__t); };
613 
614  template<sized_range _Range>
615  using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
616 
617  template<typename _Derived>
618  requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
619  class view_interface; // defined in <bits/ranges_util.h>
620 
621  namespace __detail
622  {
623  template<typename _Tp, typename _Up>
624  requires (!same_as<_Tp, view_interface<_Up>>)
625  void __is_derived_from_view_interface_fn(const _Tp&,
626  const view_interface<_Up>&); // not defined
627 
628  // Returns true iff _Tp has exactly one public base class that's a
629  // specialization of view_interface.
630  template<typename _Tp>
631  concept __is_derived_from_view_interface
632  = requires (_Tp __t) { __is_derived_from_view_interface_fn(__t, __t); };
633  }
634 
635  /// [range.view] The ranges::view_base type.
636  struct view_base { };
637 
638  /// [range.view] The ranges::enable_view boolean.
639  template<typename _Tp>
640  inline constexpr bool enable_view = derived_from<_Tp, view_base>
641  || __detail::__is_derived_from_view_interface<_Tp>;
642 
643  /// [range.view] The ranges::view concept.
644  template<typename _Tp>
645  concept view
646  = range<_Tp> && movable<_Tp> && enable_view<_Tp>;
647 
648  // [range.refinements]
649 
650  /// A range for which ranges::begin returns an output iterator.
651  template<typename _Range, typename _Tp>
652  concept output_range
653  = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
654 
655  /// A range for which ranges::begin returns an input iterator.
656  template<typename _Tp>
657  concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
658 
659  /// A range for which ranges::begin returns a forward iterator.
660  template<typename _Tp>
662  = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
663 
664  /// A range for which ranges::begin returns a bidirectional iterator.
665  template<typename _Tp>
667  = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
668 
669  /// A range for which ranges::begin returns a random access iterator.
670  template<typename _Tp>
672  = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
673 
674  /// A range for which ranges::begin returns a contiguous iterator.
675  template<typename _Tp>
677  = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
678  && requires(_Tp& __t)
679  {
680  { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
681  };
682 
683  /// A range for which ranges::begin and ranges::end return the same type.
684  template<typename _Tp>
685  concept common_range
686  = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
687 
688  /// A range which can be safely converted to a view.
689  template<typename _Tp>
690  concept viewable_range = range<_Tp>
691  && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
692  || (!view<remove_cvref_t<_Tp>> && borrowed_range<_Tp>));
693 
694  // [range.iter.ops] range iterator operations
695 
696  struct __advance_fn final
697  {
698  template<input_or_output_iterator _It>
699  constexpr void
700  operator()(_It& __it, iter_difference_t<_It> __n) const
701  {
702  if constexpr (random_access_iterator<_It>)
703  __it += __n;
704  else if constexpr (bidirectional_iterator<_It>)
705  {
706  if (__n > 0)
707  {
708  do
709  {
710  ++__it;
711  }
712  while (--__n);
713  }
714  else if (__n < 0)
715  {
716  do
717  {
718  --__it;
719  }
720  while (++__n);
721  }
722  }
723  else
724  {
725  // cannot decrement a non-bidirectional iterator
726  __glibcxx_assert(__n >= 0);
727  while (__n-- > 0)
728  ++__it;
729  }
730  }
731 
732  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
733  constexpr void
734  operator()(_It& __it, _Sent __bound) const
735  {
736  if constexpr (assignable_from<_It&, _Sent>)
737  __it = std::move(__bound);
738  else if constexpr (sized_sentinel_for<_Sent, _It>)
739  (*this)(__it, __bound - __it);
740  else
741  {
742  while (__it != __bound)
743  ++__it;
744  }
745  }
746 
747  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
748  constexpr iter_difference_t<_It>
749  operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
750  {
751  if constexpr (sized_sentinel_for<_Sent, _It>)
752  {
753  const auto __diff = __bound - __it;
754 
755  // n and bound must not lead in opposite directions:
756  __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
757  const auto __absdiff = __diff < 0 ? -__diff : __diff;
758  const auto __absn = __n < 0 ? -__n : __n;;
759  if (__absn >= __absdiff)
760  {
761  (*this)(__it, __bound);
762  return __n - __diff;
763  }
764  else
765  {
766  (*this)(__it, __n);
767  return 0;
768  }
769  }
770  else if (__it == __bound || __n == 0)
771  return __n;
772  else if (__n > 0)
773  {
774  iter_difference_t<_It> __m = 0;
775  do
776  {
777  ++__it;
778  ++__m;
779  }
780  while (__m != __n && __it != __bound);
781  return __n - __m;
782  }
783  else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
784  {
785  iter_difference_t<_It> __m = 0;
786  do
787  {
788  --__it;
789  --__m;
790  }
791  while (__m != __n && __it != __bound);
792  return __n - __m;
793  }
794  else
795  {
796  // cannot decrement a non-bidirectional iterator
797  __glibcxx_assert(__n >= 0);
798  return __n;
799  }
800  }
801 
802  void operator&() const = delete;
803  };
804 
805  inline constexpr __advance_fn advance{};
806 
807  struct __distance_fn final
808  {
809  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
810  requires (!sized_sentinel_for<_Sent, _It>)
811  constexpr iter_difference_t<_It>
812  operator()[[nodiscard]](_It __first, _Sent __last) const
813  {
814  iter_difference_t<_It> __n = 0;
815  while (__first != __last)
816  {
817  ++__first;
818  ++__n;
819  }
820  return __n;
821  }
822 
823  template<input_or_output_iterator _It, sized_sentinel_for<_It> _Sent>
824  [[nodiscard]]
825  constexpr iter_difference_t<_It>
826  operator()(const _It& __first, const _Sent& __last) const
827  {
828  return __last - __first;
829  }
830 
831  template<range _Range>
832  [[nodiscard]]
833  constexpr range_difference_t<_Range>
834  operator()(_Range&& __r) const
835  {
836  if constexpr (sized_range<_Range>)
837  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
838  else
839  return (*this)(ranges::begin(__r), ranges::end(__r));
840  }
841 
842  void operator&() const = delete;
843  };
844 
845  inline constexpr __distance_fn distance{};
846 
847  struct __next_fn final
848  {
849  template<input_or_output_iterator _It>
850  [[nodiscard]]
851  constexpr _It
852  operator()(_It __x) const
853  {
854  ++__x;
855  return __x;
856  }
857 
858  template<input_or_output_iterator _It>
859  [[nodiscard]]
860  constexpr _It
861  operator()(_It __x, iter_difference_t<_It> __n) const
862  {
863  ranges::advance(__x, __n);
864  return __x;
865  }
866 
867  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
868  [[nodiscard]]
869  constexpr _It
870  operator()(_It __x, _Sent __bound) const
871  {
872  ranges::advance(__x, __bound);
873  return __x;
874  }
875 
876  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
877  [[nodiscard]]
878  constexpr _It
879  operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
880  {
881  ranges::advance(__x, __n, __bound);
882  return __x;
883  }
884 
885  void operator&() const = delete;
886  };
887 
888  inline constexpr __next_fn next{};
889 
890  struct __prev_fn final
891  {
892  template<bidirectional_iterator _It>
893  [[nodiscard]]
894  constexpr _It
895  operator()(_It __x) const
896  {
897  --__x;
898  return __x;
899  }
900 
901  template<bidirectional_iterator _It>
902  [[nodiscard]]
903  constexpr _It
904  operator()(_It __x, iter_difference_t<_It> __n) const
905  {
906  ranges::advance(__x, -__n);
907  return __x;
908  }
909 
910  template<bidirectional_iterator _It>
911  [[nodiscard]]
912  constexpr _It
913  operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
914  {
915  ranges::advance(__x, -__n, __bound);
916  return __x;
917  }
918 
919  void operator&() const = delete;
920  };
921 
922  inline constexpr __prev_fn prev{};
923 
924  /// Type returned by algorithms instead of a dangling iterator or subrange.
925  struct dangling
926  {
927  constexpr dangling() noexcept = default;
928  template<typename... _Args>
929  constexpr dangling(_Args&&...) noexcept { }
930  };
931 
932  template<range _Range>
933  using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
934  iterator_t<_Range>,
935  dangling>;
936 
937 } // namespace ranges
938 _GLIBCXX_END_NAMESPACE_VERSION
939 } // namespace std
940 #endif // library concepts
941 #endif // C++20
942 #endif // _GLIBCXX_RANGES_BASE_H
concept bidirectional_range
A range for which ranges::begin returns a bidirectional iterator.
Definition: ranges_base.h:667
concept forward_range
A range for which ranges::begin returns a forward iterator.
Definition: ranges_base.h:662
constexpr bool enable_view
[range.view] The ranges::enable_view boolean.
Definition: ranges_base.h:640
concept viewable_range
A range which can be safely converted to a view.
Definition: ranges_base.h:690
concept contiguous_range
A range for which ranges::begin returns a contiguous iterator.
Definition: ranges_base.h:677
concept view
[range.view] The ranges::view concept.
Definition: ranges_base.h:646
concept input_range
A range for which ranges::begin returns an input iterator.
Definition: ranges_base.h:657
concept output_range
A range for which ranges::begin returns an output iterator.
Definition: ranges_base.h:653
concept range
[range.range] The range concept.
Definition: ranges_base.h:579
concept random_access_range
A range for which ranges::begin returns a random access iterator.
Definition: ranges_base.h:672
concept sized_range
[range.sized] The sized_range concept.
Definition: ranges_base.h:611
concept common_range
A range for which ranges::begin and ranges::end return the same type.
Definition: ranges_base.h:686
concept borrowed_range
[range.range] The borrowed_range concept.
Definition: ranges_base.h:588
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
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:636
Type returned by algorithms instead of a dangling iterator or subrange.
Definition: ranges_base.h:926