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  template<input_or_output_iterator _It>
678  constexpr void
679  advance(_It& __it, iter_difference_t<_It> __n)
680  {
681  if constexpr (random_access_iterator<_It>)
682  __it += __n;
683  else if constexpr (bidirectional_iterator<_It>)
684  {
685  if (__n > 0)
686  {
687  do
688  {
689  ++__it;
690  }
691  while (--__n);
692  }
693  else if (__n < 0)
694  {
695  do
696  {
697  --__it;
698  }
699  while (++__n);
700  }
701  }
702  else
703  {
704  // cannot decrement a non-bidirectional iterator
705  __glibcxx_assert(__n >= 0);
706  while (__n-- > 0)
707  ++__it;
708  }
709  }
710 
711  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
712  constexpr void
713  advance(_It& __it, _Sent __bound)
714  {
715  if constexpr (assignable_from<_It&, _Sent>)
716  __it = std::move(__bound);
717  else if constexpr (sized_sentinel_for<_Sent, _It>)
718  ranges::advance(__it, __bound - __it);
719  else
720  {
721  while (__it != __bound)
722  ++__it;
723  }
724  }
725 
726  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
727  constexpr iter_difference_t<_It>
728  advance(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
729  {
730  if constexpr (sized_sentinel_for<_Sent, _It>)
731  {
732  const auto __diff = __bound - __it;
733 #ifdef __cpp_lib_is_constant_evaluated
734  if (std::is_constant_evaluated()
735  && !(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)))
736  throw "inconsistent directions for distance and bound";
737 #endif
738  // n and bound must not lead in opposite directions:
739  __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
740  const auto __absdiff = __diff < 0 ? -__diff : __diff;
741  const auto __absn = __n < 0 ? -__n : __n;;
742  if (__absn >= __absdiff)
743  {
744  ranges::advance(__it, __bound);
745  return __n - __diff;
746  }
747  else
748  {
749  ranges::advance(__it, __n);
750  return 0;
751  }
752  }
753  else if (__it == __bound || __n == 0)
754  return iter_difference_t<_It>(0);
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  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
786  constexpr iter_difference_t<_It>
787  distance(_It __first, _Sent __last)
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  distance(_Range&& __r)
806  {
807  if constexpr (sized_range<_Range>)
808  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
809  else
810  return ranges::distance(ranges::begin(__r), ranges::end(__r));
811  }
812 
813  template<input_or_output_iterator _It>
814  constexpr _It
815  next(_It __x)
816  {
817  ++__x;
818  return __x;
819  }
820 
821  template<input_or_output_iterator _It>
822  constexpr _It
823  next(_It __x, iter_difference_t<_It> __n)
824  {
825  ranges::advance(__x, __n);
826  return __x;
827  }
828 
829  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
830  constexpr _It
831  next(_It __x, _Sent __bound)
832  {
833  ranges::advance(__x, __bound);
834  return __x;
835  }
836 
837  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
838  constexpr _It
839  next(_It __x, iter_difference_t<_It> __n, _Sent __bound)
840  {
841  ranges::advance(__x, __n, __bound);
842  return __x;
843  }
844 
845  template<bidirectional_iterator _It>
846  constexpr _It
847  prev(_It __x)
848  {
849  --__x;
850  return __x;
851  }
852 
853  template<bidirectional_iterator _It>
854  constexpr _It
855  prev(_It __x, iter_difference_t<_It> __n)
856  {
857  ranges::advance(__x, -__n);
858  return __x;
859  }
860 
861  template<bidirectional_iterator _It>
862  constexpr _It
863  prev(_It __x, iter_difference_t<_It> __n, _It __bound)
864  {
865  ranges::advance(__x, -__n, __bound);
866  return __x;
867  }
868 
869  /// Type returned by algorithms instead of a dangling iterator or subrange.
870  struct dangling
871  {
872  constexpr dangling() noexcept = default;
873  template<typename... _Args>
874  constexpr dangling(_Args&&...) noexcept { }
875  };
876 
877  template<range _Range>
878  using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
879  iterator_t<_Range>,
880  dangling>;
881 
882 } // namespace ranges
883 _GLIBCXX_END_NAMESPACE_VERSION
884 } // namespace std
885 #endif // library concepts
886 #endif // C++20
887 #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:101
_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>.