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::__class_or_enum;
93  using std::__detail::__decay_copy;
94  using std::__detail::__member_begin;
95  using std::__detail::__adl_begin;
96 
97  struct _Begin
98  {
99  private:
100  template<typename _Tp>
101  static constexpr bool
102  _S_noexcept()
103  {
104  if constexpr (is_array_v<remove_reference_t<_Tp>>)
105  return true;
106  else if constexpr (__member_begin<_Tp>)
107  return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
108  else
109  return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
110  }
111 
112  public:
113  template<__maybe_borrowed_range _Tp>
114  requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
115  || __adl_begin<_Tp>
116  constexpr auto
117  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
118  {
119  if constexpr (is_array_v<remove_reference_t<_Tp>>)
120  {
121  static_assert(is_lvalue_reference_v<_Tp>);
122  using _Up = remove_all_extents_t<remove_reference_t<_Tp>>;
123  static_assert(sizeof(_Up) != 0, "not array of incomplete type");
124  return __t + 0;
125  }
126  else if constexpr (__member_begin<_Tp>)
127  return __t.begin();
128  else
129  return begin(__t);
130  }
131  };
132 
133  template<typename _Tp>
134  concept __member_end = requires(_Tp& __t)
135  {
136  { __decay_copy(__t.end()) }
137  -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
138  };
139 
140  void end(auto&) = delete;
141  void end(const auto&) = delete;
142 
143  template<typename _Tp>
144  concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
145  && requires(_Tp& __t)
146  {
147  { __decay_copy(end(__t)) }
148  -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
149  };
150 
151  struct _End
152  {
153  private:
154  template<typename _Tp>
155  static constexpr bool
156  _S_noexcept()
157  {
158  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
159  return true;
160  else if constexpr (__member_end<_Tp>)
161  return noexcept(__decay_copy(std::declval<_Tp&>().end()));
162  else
163  return noexcept(__decay_copy(end(std::declval<_Tp&>())));
164  }
165 
166  public:
167  template<__maybe_borrowed_range _Tp>
168  requires is_bounded_array_v<remove_reference_t<_Tp>> || __member_end<_Tp>
169  || __adl_end<_Tp>
170  constexpr auto
171  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
172  {
173  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
174  {
175  static_assert(is_lvalue_reference_v<_Tp>);
176  return __t + extent_v<remove_reference_t<_Tp>>;
177  }
178  else if constexpr (__member_end<_Tp>)
179  return __t.end();
180  else
181  return end(__t);
182  }
183  };
184 
185  template<typename _Tp>
186  constexpr decltype(auto)
187  __as_const(_Tp&& __t) noexcept
188  {
189  if constexpr (is_lvalue_reference_v<_Tp>)
190  return static_cast<const remove_reference_t<_Tp>&>(__t);
191  else
192  return static_cast<const _Tp&&>(__t);
193  }
194 
195  struct _CBegin
196  {
197  template<typename _Tp>
198  constexpr auto
199  operator()(_Tp&& __e) const
200  noexcept(noexcept(_Begin{}(__cust_access::__as_const((_Tp&&)__e))))
201  requires requires { _Begin{}(__cust_access::__as_const((_Tp&&)__e)); }
202  {
203  return _Begin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
204  }
205  };
206 
207  struct _CEnd
208  {
209  template<typename _Tp>
210  constexpr auto
211  operator()(_Tp&& __e) const
212  noexcept(noexcept(_End{}(__cust_access::__as_const((_Tp&&)__e))))
213  requires requires { _End{}(__cust_access::__as_const((_Tp&&)__e)); }
214  {
215  return _End{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
216  }
217  };
218 
219  template<typename _Tp>
220  concept __member_rbegin = requires(_Tp& __t)
221  {
222  { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
223  };
224 
225  void rbegin(auto&) = delete;
226  void rbegin(const auto&) = delete;
227 
228  template<typename _Tp>
229  concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
230  && requires(_Tp& __t)
231  {
232  { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
233  };
234 
235  template<typename _Tp>
236  concept __reversable = requires(_Tp& __t)
237  {
238  { _Begin{}(__t) } -> bidirectional_iterator;
239  { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
240  };
241 
242  struct _RBegin
243  {
244  private:
245  template<typename _Tp>
246  static constexpr bool
247  _S_noexcept()
248  {
249  if constexpr (__member_rbegin<_Tp>)
250  return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
251  else if constexpr (__adl_rbegin<_Tp>)
252  return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
253  else
254  {
255  if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
256  {
257  using _It = decltype(_End{}(std::declval<_Tp&>()));
258  // std::reverse_iterator copy-initializes its member.
259  return is_nothrow_copy_constructible_v<_It>;
260  }
261  else
262  return false;
263  }
264  }
265 
266  public:
267  template<__maybe_borrowed_range _Tp>
268  requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
269  constexpr auto
270  operator()(_Tp&& __t) const
271  noexcept(_S_noexcept<_Tp>())
272  {
273  if constexpr (__member_rbegin<_Tp>)
274  return __t.rbegin();
275  else if constexpr (__adl_rbegin<_Tp>)
276  return rbegin(__t);
277  else
278  return std::make_reverse_iterator(_End{}(__t));
279  }
280  };
281 
282  template<typename _Tp>
283  concept __member_rend = requires(_Tp& __t)
284  {
285  { __decay_copy(__t.rend()) }
286  -> sentinel_for<decltype(_RBegin{}(__t))>;
287  };
288 
289  void rend(auto&) = delete;
290  void rend(const auto&) = delete;
291 
292  template<typename _Tp>
293  concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
294  && requires(_Tp& __t)
295  {
296  { __decay_copy(rend(__t)) }
297  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
298  };
299 
300  struct _REnd
301  {
302  private:
303  template<typename _Tp>
304  static constexpr bool
305  _S_noexcept()
306  {
307  if constexpr (__member_rend<_Tp>)
308  return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
309  else if constexpr (__adl_rend<_Tp>)
310  return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
311  else
312  {
313  if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
314  {
315  using _It = decltype(_Begin{}(std::declval<_Tp&>()));
316  // std::reverse_iterator copy-initializes its member.
317  return is_nothrow_copy_constructible_v<_It>;
318  }
319  else
320  return false;
321  }
322  }
323 
324  public:
325  template<__maybe_borrowed_range _Tp>
326  requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
327  constexpr auto
328  operator()(_Tp&& __t) const
329  noexcept(_S_noexcept<_Tp>())
330  {
331  if constexpr (__member_rend<_Tp>)
332  return __t.rend();
333  else if constexpr (__adl_rend<_Tp>)
334  return rend(__t);
335  else
336  return std::make_reverse_iterator(_Begin{}(__t));
337  }
338  };
339 
340  struct _CRBegin
341  {
342  template<typename _Tp>
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(std::forward<_Tp>(__e)));
349  }
350  };
351 
352  struct _CREnd
353  {
354  template<typename _Tp>
355  constexpr auto
356  operator()(_Tp&& __e) const
357  noexcept(noexcept(_REnd{}(__cust_access::__as_const((_Tp&&)__e))))
358  requires requires { _REnd{}(__cust_access::__as_const((_Tp&&)__e)); }
359  {
360  return _REnd{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
361  }
362  };
363 
364  template<typename _Tp>
365  concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
366  && requires(_Tp&& __t)
367  {
368  { __decay_copy(std::forward<_Tp>(__t).size()) }
369  -> __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(std::forward<_Tp>(__t))) }
381  -> __detail::__is_integer_like;
382  };
383 
384  template<typename _Tp>
385  concept __sentinel_size = requires(_Tp&& __t)
386  {
387  { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
388 
389  { _End{}(std::forward<_Tp>(__t)) }
390  -> sized_sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__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()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
417  {
418  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
419  {
420  return extent_v<remove_reference_t<_Tp>>;
421  }
422  else if constexpr (__member_size<_Tp>)
423  return std::forward<_Tp>(__e).size();
424  else if constexpr (__adl_size<_Tp>)
425  return size(std::forward<_Tp>(__e));
426  else if constexpr (__sentinel_size<_Tp>)
427  return __detail::__to_unsigned_like(
428  _End{}(std::forward<_Tp>(__e))
429  - _Begin{}(std::forward<_Tp>(__e)));
430  }
431  };
432 
433  struct _SSize
434  {
435  template<typename _Tp>
436  requires requires (_Tp&& __e)
437  {
438  _Begin{}(std::forward<_Tp>(__e));
439  _Size{}(std::forward<_Tp>(__e));
440  }
441  constexpr auto
442  operator()(_Tp&& __e) const
443  noexcept(noexcept(_Size{}(std::forward<_Tp>(__e))))
444  {
445  using __iter_type = decltype(_Begin{}(std::forward<_Tp>(__e)));
446  using __diff_type = iter_difference_t<__iter_type>;
448  auto __size = _Size{}(std::forward<_Tp>(__e));
449  if constexpr (integral<__diff_type>)
450  {
451  if constexpr (__int_traits<__diff_type>::__digits
452  < __int_traits<ptrdiff_t>::__digits)
453  return static_cast<ptrdiff_t>(__size);
454  }
455  return static_cast<__diff_type>(__size);
456  }
457  };
458 
459  template<typename _Tp>
460  concept __member_empty = requires(_Tp&& __t)
461  { bool(std::forward<_Tp>(__t).empty()); };
462 
463  template<typename _Tp>
464  concept __size0_empty = requires(_Tp&& __t)
465  { _Size{}(std::forward<_Tp>(__t)) == 0; };
466 
467  template<typename _Tp>
468  concept __eq_iter_empty = requires(_Tp&& __t)
469  {
470  { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
471  bool(_Begin{}(std::forward<_Tp>(__t))
472  == _End{}(std::forward<_Tp>(__t)));
473  };
474 
475  struct _Empty
476  {
477  private:
478  template<typename _Tp>
479  static constexpr bool
480  _S_noexcept()
481  {
482  if constexpr (__member_empty<_Tp>)
483  return noexcept(std::declval<_Tp>().empty());
484  else if constexpr (__size0_empty<_Tp>)
485  return noexcept(_Size{}(std::declval<_Tp>()) == 0);
486  else
487  return noexcept(bool(_Begin{}(std::declval<_Tp>())
488  == _End{}(std::declval<_Tp>())));
489  }
490 
491  public:
492  template<typename _Tp>
493  requires __member_empty<_Tp> || __size0_empty<_Tp>
494  || __eq_iter_empty<_Tp>
495  constexpr bool
496  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
497  {
498  if constexpr (__member_empty<_Tp>)
499  return bool(std::forward<_Tp>(__e).empty());
500  else if constexpr (__size0_empty<_Tp>)
501  return _Size{}(std::forward<_Tp>(__e)) == 0;
502  else
503  return bool(_Begin{}(std::forward<_Tp>(__e))
504  == _End{}(std::forward<_Tp>(__e)));
505  }
506  };
507 
508  template<typename _Tp>
509  concept __pointer_to_object = is_pointer_v<_Tp>
510  && is_object_v<remove_pointer_t<_Tp>>;
511 
512  template<typename _Tp>
513  concept __member_data = is_lvalue_reference_v<_Tp>
514  && requires(_Tp __t) { { __t.data() } -> __pointer_to_object; };
515 
516  template<typename _Tp>
517  concept __begin_data = requires(_Tp&& __t)
518  { { _Begin{}(std::forward<_Tp>(__t)) } -> contiguous_iterator; };
519 
520  struct _Data
521  {
522  private:
523  template<typename _Tp>
524  static constexpr bool
525  _S_noexcept()
526  {
527  if constexpr (__member_data<_Tp>)
528  return noexcept(__decay_copy(std::declval<_Tp>().data()));
529  else
530  return noexcept(_Begin{}(std::declval<_Tp>()));
531  }
532 
533  public:
534  template<__maybe_borrowed_range _Tp>
535  requires __member_data<_Tp> || __begin_data<_Tp>
536  constexpr auto
537  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
538  {
539  if constexpr (__member_data<_Tp>)
540  return __e.data();
541  else
542  return std::to_address(_Begin{}(std::forward<_Tp>(__e)));
543  }
544  };
545 
546  struct _CData
547  {
548  template<typename _Tp>
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(std::forward<_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>
587  concept borrowed_range
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  /// [range.view] The ranges::view_base type.
618  struct view_base { };
619 
620  /// [range.view] The ranges::enable_view boolean.
621  template<typename _Tp>
622  inline constexpr bool enable_view = derived_from<_Tp, view_base>;
623 
624  /// [range.view] The ranges::view concept.
625  template<typename _Tp>
626  concept view
627  = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
628  && enable_view<_Tp>;
629 
630  // [range.refinements]
631 
632  /// A range for which ranges::begin returns an output iterator.
633  template<typename _Range, typename _Tp>
634  concept output_range
635  = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
636 
637  /// A range for which ranges::begin returns an input iterator.
638  template<typename _Tp>
639  concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
640 
641  /// A range for which ranges::begin returns a forward iterator.
642  template<typename _Tp>
643  concept forward_range
644  = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
645 
646  /// A range for which ranges::begin returns a bidirectional iterator.
647  template<typename _Tp>
648  concept bidirectional_range
649  = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
650 
651  /// A range for which ranges::begin returns a random access iterator.
652  template<typename _Tp>
653  concept random_access_range
654  = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
655 
656  /// A range for which ranges::begin returns a contiguous iterator.
657  template<typename _Tp>
658  concept contiguous_range
659  = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
660  && requires(_Tp& __t)
661  {
662  { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
663  };
664 
665  /// A range for which ranges::begin and ranges::end return the same type.
666  template<typename _Tp>
667  concept common_range
668  = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
669 
670  /// A range which can be safely converted to a view.
671  template<typename _Tp>
672  concept viewable_range = range<_Tp>
673  && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>);
674 
675  // [range.iter.ops] range iterator operations
676 
677  struct __advance_fn
678  {
679  template<input_or_output_iterator _It>
680  constexpr void
681  operator()(_It& __it, iter_difference_t<_It> __n) const
682  {
683  if constexpr (random_access_iterator<_It>)
684  __it += __n;
685  else if constexpr (bidirectional_iterator<_It>)
686  {
687  if (__n > 0)
688  {
689  do
690  {
691  ++__it;
692  }
693  while (--__n);
694  }
695  else if (__n < 0)
696  {
697  do
698  {
699  --__it;
700  }
701  while (++__n);
702  }
703  }
704  else
705  {
706  // cannot decrement a non-bidirectional iterator
707  __glibcxx_assert(__n >= 0);
708  while (__n-- > 0)
709  ++__it;
710  }
711  }
712 
713  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
714  constexpr void
715  operator()(_It& __it, _Sent __bound) const
716  {
717  if constexpr (assignable_from<_It&, _Sent>)
718  __it = std::move(__bound);
719  else if constexpr (sized_sentinel_for<_Sent, _It>)
720  (*this)(__it, __bound - __it);
721  else
722  {
723  while (__it != __bound)
724  ++__it;
725  }
726  }
727 
728  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
729  constexpr iter_difference_t<_It>
730  operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
731  {
732  if constexpr (sized_sentinel_for<_Sent, _It>)
733  {
734  const auto __diff = __bound - __it;
735 
736  // n and bound must not lead in opposite directions:
737  __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
738  const auto __absdiff = __diff < 0 ? -__diff : __diff;
739  const auto __absn = __n < 0 ? -__n : __n;;
740  if (__absn >= __absdiff)
741  {
742  (*this)(__it, __bound);
743  return __n - __diff;
744  }
745  else
746  {
747  (*this)(__it, __n);
748  return 0;
749  }
750  }
751  else if (__it == __bound || __n == 0)
752  return __n;
753  else if (__n > 0)
754  {
755  iter_difference_t<_It> __m = 0;
756  do
757  {
758  ++__it;
759  ++__m;
760  }
761  while (__m != __n && __it != __bound);
762  return __n - __m;
763  }
764  else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
765  {
766  iter_difference_t<_It> __m = 0;
767  do
768  {
769  --__it;
770  --__m;
771  }
772  while (__m != __n && __it != __bound);
773  return __n - __m;
774  }
775  else
776  {
777  // cannot decrement a non-bidirectional iterator
778  __glibcxx_assert(__n >= 0);
779  return __n;
780  }
781  }
782  };
783 
784  inline constexpr __advance_fn advance{};
785 
786  struct __distance_fn
787  {
788  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
789  constexpr iter_difference_t<_It>
790  operator()(_It __first, _Sent __last) const
791  {
792  if constexpr (sized_sentinel_for<_Sent, _It>)
793  return __last - __first;
794  else
795  {
796  iter_difference_t<_It> __n = 0;
797  while (__first != __last)
798  {
799  ++__first;
800  ++__n;
801  }
802  return __n;
803  }
804  }
805 
806  template<range _Range>
807  constexpr range_difference_t<_Range>
808  operator()(_Range&& __r) const
809  {
810  if constexpr (sized_range<_Range>)
811  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
812  else
813  return (*this)(ranges::begin(__r), ranges::end(__r));
814  }
815  };
816 
817  inline constexpr __distance_fn distance{};
818 
819  struct __next_fn
820  {
821  template<input_or_output_iterator _It>
822  constexpr _It
823  operator()(_It __x) const
824  {
825  ++__x;
826  return __x;
827  }
828 
829  template<input_or_output_iterator _It>
830  constexpr _It
831  operator()(_It __x, iter_difference_t<_It> __n) const
832  {
833  ranges::advance(__x, __n);
834  return __x;
835  }
836 
837  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
838  constexpr _It
839  operator()(_It __x, _Sent __bound) const
840  {
841  ranges::advance(__x, __bound);
842  return __x;
843  }
844 
845  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
846  constexpr _It
847  operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
848  {
849  ranges::advance(__x, __n, __bound);
850  return __x;
851  }
852  };
853 
854  inline constexpr __next_fn next{};
855 
856  struct __prev_fn
857  {
858  template<bidirectional_iterator _It>
859  constexpr _It
860  operator()(_It __x) const
861  {
862  --__x;
863  return __x;
864  }
865 
866  template<bidirectional_iterator _It>
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<bidirectional_iterator _It>
875  constexpr _It
876  operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
877  {
878  ranges::advance(__x, -__n, __bound);
879  return __x;
880  }
881  };
882 
883  inline constexpr __prev_fn prev{};
884 
885  /// Type returned by algorithms instead of a dangling iterator or subrange.
886  struct dangling
887  {
888  constexpr dangling() noexcept = default;
889  template<typename... _Args>
890  constexpr dangling(_Args&&...) noexcept { }
891  };
892 
893  template<range _Range>
894  using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
895  iterator_t<_Range>,
896  dangling>;
897 
898 } // namespace ranges
899 _GLIBCXX_END_NAMESPACE_VERSION
900 } // namespace std
901 #endif // library concepts
902 #endif // C++20
903 #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>.