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()(_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>
162  requires is_bounded_array_v<remove_reference_t<_Tp>>
163  || __member_end<_Tp> || __adl_end<_Tp>
164  constexpr auto
165  operator()(_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  constexpr auto
196  operator()(_Tp&& __e) const
197  noexcept(noexcept(_Begin{}(__cust_access::__as_const<_Tp>(__e))))
198  requires requires { _Begin{}(__cust_access::__as_const<_Tp>(__e)); }
199  {
200  return _Begin{}(__cust_access::__as_const<_Tp>(__e));
201  }
202  };
203 
204  struct _CEnd
205  {
206  template<typename _Tp>
207  constexpr auto
208  operator()(_Tp&& __e) const
209  noexcept(noexcept(_End{}(__cust_access::__as_const<_Tp>(__e))))
210  requires requires { _End{}(__cust_access::__as_const<_Tp>(__e)); }
211  {
212  return _End{}(__cust_access::__as_const<_Tp>(__e));
213  }
214  };
215 
216  template<typename _Tp>
217  concept __member_rbegin = requires(_Tp& __t)
218  {
219  { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
220  };
221 
222  void rbegin(auto&) = delete;
223  void rbegin(const auto&) = delete;
224 
225  template<typename _Tp>
226  concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
227  && requires(_Tp& __t)
228  {
229  { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
230  };
231 
232  template<typename _Tp>
233  concept __reversable = requires(_Tp& __t)
234  {
235  { _Begin{}(__t) } -> bidirectional_iterator;
236  { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
237  };
238 
239  struct _RBegin
240  {
241  private:
242  template<typename _Tp>
243  static constexpr bool
244  _S_noexcept()
245  {
246  if constexpr (__member_rbegin<_Tp>)
247  return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
248  else if constexpr (__adl_rbegin<_Tp>)
249  return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
250  else
251  {
252  if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
253  {
254  using _It = decltype(_End{}(std::declval<_Tp&>()));
255  // std::reverse_iterator copy-initializes its member.
256  return is_nothrow_copy_constructible_v<_It>;
257  }
258  else
259  return false;
260  }
261  }
262 
263  public:
264  template<__maybe_borrowed_range _Tp>
265  requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
266  constexpr auto
267  operator()(_Tp&& __t) const
268  noexcept(_S_noexcept<_Tp&>())
269  {
270  if constexpr (__member_rbegin<_Tp>)
271  return __t.rbegin();
272  else if constexpr (__adl_rbegin<_Tp>)
273  return rbegin(__t);
274  else
275  return std::make_reverse_iterator(_End{}(__t));
276  }
277  };
278 
279  template<typename _Tp>
280  concept __member_rend = requires(_Tp& __t)
281  {
282  { __decay_copy(__t.rend()) }
283  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
284  };
285 
286  void rend(auto&) = delete;
287  void rend(const auto&) = delete;
288 
289  template<typename _Tp>
290  concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
291  && requires(_Tp& __t)
292  {
293  { __decay_copy(rend(__t)) }
294  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
295  };
296 
297  struct _REnd
298  {
299  private:
300  template<typename _Tp>
301  static constexpr bool
302  _S_noexcept()
303  {
304  if constexpr (__member_rend<_Tp>)
305  return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
306  else if constexpr (__adl_rend<_Tp>)
307  return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
308  else
309  {
310  if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
311  {
312  using _It = decltype(_Begin{}(std::declval<_Tp&>()));
313  // std::reverse_iterator copy-initializes its member.
314  return is_nothrow_copy_constructible_v<_It>;
315  }
316  else
317  return false;
318  }
319  }
320 
321  public:
322  template<__maybe_borrowed_range _Tp>
323  requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
324  constexpr auto
325  operator()(_Tp&& __t) const
326  noexcept(_S_noexcept<_Tp&>())
327  {
328  if constexpr (__member_rend<_Tp>)
329  return __t.rend();
330  else if constexpr (__adl_rend<_Tp>)
331  return rend(__t);
332  else
333  return std::make_reverse_iterator(_Begin{}(__t));
334  }
335  };
336 
337  struct _CRBegin
338  {
339  template<typename _Tp>
340  constexpr auto
341  operator()(_Tp&& __e) const
342  noexcept(noexcept(_RBegin{}(__cust_access::__as_const<_Tp>(__e))))
343  requires requires { _RBegin{}(__cust_access::__as_const<_Tp>(__e)); }
344  {
345  return _RBegin{}(__cust_access::__as_const<_Tp>(__e));
346  }
347  };
348 
349  struct _CREnd
350  {
351  template<typename _Tp>
352  constexpr auto
353  operator()(_Tp&& __e) const
354  noexcept(noexcept(_REnd{}(__cust_access::__as_const<_Tp>(__e))))
355  requires requires { _REnd{}(__cust_access::__as_const<_Tp>(__e)); }
356  {
357  return _REnd{}(__cust_access::__as_const<_Tp>(__e));
358  }
359  };
360 
361  template<typename _Tp>
362  concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
363  && requires(_Tp& __t)
364  {
365  { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
366  };
367 
368  void size(auto&) = delete;
369  void size(const auto&) = delete;
370 
371  template<typename _Tp>
372  concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
373  && !disable_sized_range<remove_cvref_t<_Tp>>
374  && requires(_Tp& __t)
375  {
376  { __decay_copy(size(__t)) } -> __detail::__is_integer_like;
377  };
378 
379  template<typename _Tp>
380  concept __sentinel_size = requires(_Tp& __t)
381  {
382  requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
383 
384  { _Begin{}(__t) } -> forward_iterator;
385 
386  { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
387 
388  __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
389  };
390 
391  struct _Size
392  {
393  private:
394  template<typename _Tp>
395  static constexpr bool
396  _S_noexcept()
397  {
398  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
399  return true;
400  else if constexpr (__member_size<_Tp>)
401  return noexcept(__decay_copy(std::declval<_Tp&>().size()));
402  else if constexpr (__adl_size<_Tp>)
403  return noexcept(__decay_copy(size(std::declval<_Tp&>())));
404  else if constexpr (__sentinel_size<_Tp>)
405  return noexcept(_End{}(std::declval<_Tp&>())
406  - _Begin{}(std::declval<_Tp&>()));
407  }
408 
409  public:
410  template<typename _Tp>
411  requires is_bounded_array_v<remove_reference_t<_Tp>>
412  || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
413  constexpr auto
414  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
415  {
416  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
417  return extent_v<remove_reference_t<_Tp>>;
418  else if constexpr (__member_size<_Tp>)
419  return __t.size();
420  else if constexpr (__adl_size<_Tp>)
421  return size(__t);
422  else if constexpr (__sentinel_size<_Tp>)
423  return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
424  }
425  };
426 
427  struct _SSize
428  {
429  // _GLIBCXX_RESOLVE_LIB_DEFECTS
430  // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E)
431  template<typename _Tp>
432  requires requires (_Tp& __t) { _Size{}(__t); }
433  constexpr auto
434  operator()(_Tp&& __t) const noexcept(noexcept(_Size{}(__t)))
435  {
436  auto __size = _Size{}(__t);
437  using __size_type = decltype(__size);
438  // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>.
439  if constexpr (integral<__size_type>)
440  {
442  if constexpr (__int_traits<__size_type>::__digits
443  < __int_traits<ptrdiff_t>::__digits)
444  return static_cast<ptrdiff_t>(__size);
445  else
446  return static_cast<make_signed_t<__size_type>>(__size);
447  }
448 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
449  // For strict-ansi modes integral<__int128> is false
450  else if constexpr (__detail::__is_int128<__size_type>)
451  return static_cast<__int128>(__size);
452 #endif
453  else // Must be one of __max_diff_type or __max_size_type.
454  return __detail::__max_diff_type(__size);
455  }
456  };
457 
458  template<typename _Tp>
459  concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
460 
461  template<typename _Tp>
462  concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
463 
464  template<typename _Tp>
465  concept __eq_iter_empty = requires(_Tp& __t)
466  {
467  requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
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()(_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()(_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  constexpr auto
549  operator()(_Tp&& __e) const
550  noexcept(noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e))))
551  requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); }
552  {
553  return _Data{}(__cust_access::__as_const<_Tp>(__e));
554  }
555  };
556 
557  } // namespace __cust_access
558 
559  inline namespace __cust
560  {
561  inline constexpr __cust_access::_Begin begin{};
562  inline constexpr __cust_access::_End end{};
563  inline constexpr __cust_access::_CBegin cbegin{};
564  inline constexpr __cust_access::_CEnd cend{};
565  inline constexpr __cust_access::_RBegin rbegin{};
566  inline constexpr __cust_access::_REnd rend{};
567  inline constexpr __cust_access::_CRBegin crbegin{};
568  inline constexpr __cust_access::_CREnd crend{};
569  inline constexpr __cust_access::_Size size{};
570  inline constexpr __cust_access::_SSize ssize{};
571  inline constexpr __cust_access::_Empty empty{};
572  inline constexpr __cust_access::_Data data{};
573  inline constexpr __cust_access::_CData cdata{};
574  }
575 
576  /// [range.range] The range concept.
577  template<typename _Tp>
578  concept range = requires(_Tp& __t)
579  {
580  ranges::begin(__t);
581  ranges::end(__t);
582  };
583 
584  /// [range.range] The borrowed_range concept.
585  template<typename _Tp>
586  concept borrowed_range
587  = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
588 
589  template<typename _Tp>
590  using iterator_t = std::__detail::__range_iter_t<_Tp>;
591 
592  template<range _Range>
593  using sentinel_t = decltype(ranges::end(std::declval<_Range&>()));
594 
595  template<range _Range>
596  using range_difference_t = iter_difference_t<iterator_t<_Range>>;
597 
598  template<range _Range>
599  using range_value_t = iter_value_t<iterator_t<_Range>>;
600 
601  template<range _Range>
602  using range_reference_t = iter_reference_t<iterator_t<_Range>>;
603 
604  template<range _Range>
605  using range_rvalue_reference_t
606  = iter_rvalue_reference_t<iterator_t<_Range>>;
607 
608  /// [range.sized] The sized_range concept.
609  template<typename _Tp>
610  concept sized_range = range<_Tp>
611  && requires(_Tp& __t) { ranges::size(__t); };
612 
613  template<sized_range _Range>
614  using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
615 
616  /// [range.view] The ranges::view_base type.
617  struct view_base { };
618 
619  /// [range.view] The ranges::enable_view boolean.
620  template<typename _Tp>
621  inline constexpr bool enable_view = derived_from<_Tp, view_base>;
622 
623  /// [range.view] The ranges::view concept.
624  template<typename _Tp>
625  concept view
626  = range<_Tp> && movable<_Tp> && enable_view<_Tp>;
627 
628  // [range.refinements]
629 
630  /// A range for which ranges::begin returns an output iterator.
631  template<typename _Range, typename _Tp>
632  concept output_range
633  = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
634 
635  /// A range for which ranges::begin returns an input iterator.
636  template<typename _Tp>
637  concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
638 
639  /// A range for which ranges::begin returns a forward iterator.
640  template<typename _Tp>
641  concept forward_range
642  = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
643 
644  /// A range for which ranges::begin returns a bidirectional iterator.
645  template<typename _Tp>
646  concept bidirectional_range
647  = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
648 
649  /// A range for which ranges::begin returns a random access iterator.
650  template<typename _Tp>
651  concept random_access_range
652  = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
653 
654  /// A range for which ranges::begin returns a contiguous iterator.
655  template<typename _Tp>
656  concept contiguous_range
657  = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
658  && requires(_Tp& __t)
659  {
660  { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
661  };
662 
663  /// A range for which ranges::begin and ranges::end return the same type.
664  template<typename _Tp>
665  concept common_range
666  = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
667 
668  /// A range which can be safely converted to a view.
669  template<typename _Tp>
670  concept viewable_range = range<_Tp>
671  && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
672  || (!view<remove_cvref_t<_Tp>> && borrowed_range<_Tp>));
673 
674  // [range.iter.ops] range iterator operations
675 
676  struct __advance_fn
677  {
678  template<input_or_output_iterator _It>
679  constexpr void
680  operator()(_It& __it, iter_difference_t<_It> __n) const
681  {
682  if constexpr (random_access_iterator<_It>)
683  __it += __n;
684  else if constexpr (bidirectional_iterator<_It>)
685  {
686  if (__n > 0)
687  {
688  do
689  {
690  ++__it;
691  }
692  while (--__n);
693  }
694  else if (__n < 0)
695  {
696  do
697  {
698  --__it;
699  }
700  while (++__n);
701  }
702  }
703  else
704  {
705  // cannot decrement a non-bidirectional iterator
706  __glibcxx_assert(__n >= 0);
707  while (__n-- > 0)
708  ++__it;
709  }
710  }
711 
712  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
713  constexpr void
714  operator()(_It& __it, _Sent __bound) const
715  {
716  if constexpr (assignable_from<_It&, _Sent>)
717  __it = std::move(__bound);
718  else if constexpr (sized_sentinel_for<_Sent, _It>)
719  (*this)(__it, __bound - __it);
720  else
721  {
722  while (__it != __bound)
723  ++__it;
724  }
725  }
726 
727  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
728  constexpr iter_difference_t<_It>
729  operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
730  {
731  if constexpr (sized_sentinel_for<_Sent, _It>)
732  {
733  const auto __diff = __bound - __it;
734 
735  if (__diff == 0)
736  return __n;
737  else if (__diff > 0 ? __n >= __diff : __n <= __diff)
738  {
739  (*this)(__it, __bound);
740  return __n - __diff;
741  }
742  else if (__n != 0) [[likely]]
743  {
744  // n and bound must not lead in opposite directions:
745  __glibcxx_assert(__n < 0 == __diff < 0);
746 
747  (*this)(__it, __n);
748  return 0;
749  }
750  else
751  return 0;
752  }
753  else if (__it == __bound || __n == 0)
754  return __n;
755  else if (__n > 0)
756  {
757  iter_difference_t<_It> __m = 0;
758  do
759  {
760  ++__it;
761  ++__m;
762  }
763  while (__m != __n && __it != __bound);
764  return __n - __m;
765  }
766  else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
767  {
768  iter_difference_t<_It> __m = 0;
769  do
770  {
771  --__it;
772  --__m;
773  }
774  while (__m != __n && __it != __bound);
775  return __n - __m;
776  }
777  else
778  {
779  // cannot decrement a non-bidirectional iterator
780  __glibcxx_assert(__n >= 0);
781  return __n;
782  }
783  }
784  };
785 
786  inline constexpr __advance_fn advance{};
787 
788  struct __distance_fn
789  {
790  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
791  constexpr iter_difference_t<_It>
792  operator()(_It __first, _Sent __last) const
793  {
794  if constexpr (sized_sentinel_for<_Sent, _It>)
795  return __last - __first;
796  else
797  {
798  iter_difference_t<_It> __n = 0;
799  while (__first != __last)
800  {
801  ++__first;
802  ++__n;
803  }
804  return __n;
805  }
806  }
807 
808  template<range _Range>
809  constexpr range_difference_t<_Range>
810  operator()(_Range&& __r) const
811  {
812  if constexpr (sized_range<_Range>)
813  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
814  else
815  return (*this)(ranges::begin(__r), ranges::end(__r));
816  }
817  };
818 
819  inline constexpr __distance_fn distance{};
820 
821  struct __next_fn
822  {
823  template<input_or_output_iterator _It>
824  constexpr _It
825  operator()(_It __x) const
826  {
827  ++__x;
828  return __x;
829  }
830 
831  template<input_or_output_iterator _It>
832  constexpr _It
833  operator()(_It __x, iter_difference_t<_It> __n) const
834  {
835  ranges::advance(__x, __n);
836  return __x;
837  }
838 
839  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
840  constexpr _It
841  operator()(_It __x, _Sent __bound) const
842  {
843  ranges::advance(__x, __bound);
844  return __x;
845  }
846 
847  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
848  constexpr _It
849  operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
850  {
851  ranges::advance(__x, __n, __bound);
852  return __x;
853  }
854  };
855 
856  inline constexpr __next_fn next{};
857 
858  struct __prev_fn
859  {
860  template<bidirectional_iterator _It>
861  constexpr _It
862  operator()(_It __x) const
863  {
864  --__x;
865  return __x;
866  }
867 
868  template<bidirectional_iterator _It>
869  constexpr _It
870  operator()(_It __x, iter_difference_t<_It> __n) const
871  {
872  ranges::advance(__x, -__n);
873  return __x;
874  }
875 
876  template<bidirectional_iterator _It>
877  constexpr _It
878  operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
879  {
880  ranges::advance(__x, -__n, __bound);
881  return __x;
882  }
883  };
884 
885  inline constexpr __prev_fn prev{};
886 
887  /// Type returned by algorithms instead of a dangling iterator or subrange.
888  struct dangling
889  {
890  constexpr dangling() noexcept = default;
891  template<typename... _Args>
892  constexpr dangling(_Args&&...) noexcept { }
893  };
894 
895  template<range _Range>
896  using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
897  iterator_t<_Range>,
898  dangling>;
899 
900 } // namespace ranges
901 _GLIBCXX_END_NAMESPACE_VERSION
902 } // namespace std
903 #endif // library concepts
904 #endif // C++20
905 #endif // _GLIBCXX_RANGES_BASE_H
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1639
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition: type_traits:2358
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:1239
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1217
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.
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 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: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>.