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