libstdc++
range_access.h
Go to the documentation of this file.
1 // <range_access.h> -*- C++ -*-
2 
3 // Copyright (C) 2010-2020 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/range_access.h
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly. @headername{iterator}
28  */
29 
30 #ifndef _GLIBCXX_RANGE_ACCESS_H
31 #define _GLIBCXX_RANGE_ACCESS_H 1
32 
33 #pragma GCC system_header
34 
35 #if __cplusplus >= 201103L
36 #include <initializer_list>
37 #include <bits/iterator_concepts.h>
38 #include <ext/numeric_traits.h>
39 
40 namespace std _GLIBCXX_VISIBILITY(default)
41 {
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
43 
44  /**
45  * @brief Return an iterator pointing to the first element of
46  * the container.
47  * @param __cont Container.
48  */
49  template<typename _Container>
50  inline _GLIBCXX17_CONSTEXPR auto
51  begin(_Container& __cont) -> decltype(__cont.begin())
52  { return __cont.begin(); }
53 
54  /**
55  * @brief Return an iterator pointing to the first element of
56  * the const container.
57  * @param __cont Container.
58  */
59  template<typename _Container>
60  inline _GLIBCXX17_CONSTEXPR auto
61  begin(const _Container& __cont) -> decltype(__cont.begin())
62  { return __cont.begin(); }
63 
64  /**
65  * @brief Return an iterator pointing to one past the last element of
66  * the container.
67  * @param __cont Container.
68  */
69  template<typename _Container>
70  inline _GLIBCXX17_CONSTEXPR auto
71  end(_Container& __cont) -> decltype(__cont.end())
72  { return __cont.end(); }
73 
74  /**
75  * @brief Return an iterator pointing to one past the last element of
76  * the const container.
77  * @param __cont Container.
78  */
79  template<typename _Container>
80  inline _GLIBCXX17_CONSTEXPR auto
81  end(const _Container& __cont) -> decltype(__cont.end())
82  { return __cont.end(); }
83 
84  /**
85  * @brief Return an iterator pointing to the first element of the array.
86  * @param __arr Array.
87  */
88  template<typename _Tp, size_t _Nm>
89  inline _GLIBCXX14_CONSTEXPR _Tp*
90  begin(_Tp (&__arr)[_Nm])
91  { return __arr; }
92 
93  /**
94  * @brief Return an iterator pointing to one past the last element
95  * of the array.
96  * @param __arr Array.
97  */
98  template<typename _Tp, size_t _Nm>
99  inline _GLIBCXX14_CONSTEXPR _Tp*
100  end(_Tp (&__arr)[_Nm])
101  { return __arr + _Nm; }
102 
103 #if __cplusplus >= 201402L
104 
105  template<typename _Tp> class valarray;
106  // These overloads must be declared for cbegin and cend to use them.
107  template<typename _Tp> _Tp* begin(valarray<_Tp>&);
108  template<typename _Tp> const _Tp* begin(const valarray<_Tp>&);
109  template<typename _Tp> _Tp* end(valarray<_Tp>&);
110  template<typename _Tp> const _Tp* end(const valarray<_Tp>&);
111 
112  /**
113  * @brief Return an iterator pointing to the first element of
114  * the const container.
115  * @param __cont Container.
116  */
117  template<typename _Container>
118  inline constexpr auto
119  cbegin(const _Container& __cont) noexcept(noexcept(std::begin(__cont)))
120  -> decltype(std::begin(__cont))
121  { return std::begin(__cont); }
122 
123  /**
124  * @brief Return an iterator pointing to one past the last element of
125  * the const container.
126  * @param __cont Container.
127  */
128  template<typename _Container>
129  inline constexpr auto
130  cend(const _Container& __cont) noexcept(noexcept(std::end(__cont)))
131  -> decltype(std::end(__cont))
132  { return std::end(__cont); }
133 
134  /**
135  * @brief Return a reverse iterator pointing to the last element of
136  * the container.
137  * @param __cont Container.
138  */
139  template<typename _Container>
140  inline _GLIBCXX17_CONSTEXPR auto
141  rbegin(_Container& __cont) -> decltype(__cont.rbegin())
142  { return __cont.rbegin(); }
143 
144  /**
145  * @brief Return a reverse iterator pointing to the last element of
146  * the const container.
147  * @param __cont Container.
148  */
149  template<typename _Container>
150  inline _GLIBCXX17_CONSTEXPR auto
151  rbegin(const _Container& __cont) -> decltype(__cont.rbegin())
152  { return __cont.rbegin(); }
153 
154  /**
155  * @brief Return a reverse iterator pointing one past the first element of
156  * the container.
157  * @param __cont Container.
158  */
159  template<typename _Container>
160  inline _GLIBCXX17_CONSTEXPR auto
161  rend(_Container& __cont) -> decltype(__cont.rend())
162  { return __cont.rend(); }
163 
164  /**
165  * @brief Return a reverse iterator pointing one past the first element of
166  * the const container.
167  * @param __cont Container.
168  */
169  template<typename _Container>
170  inline _GLIBCXX17_CONSTEXPR auto
171  rend(const _Container& __cont) -> decltype(__cont.rend())
172  { return __cont.rend(); }
173 
174  /**
175  * @brief Return a reverse iterator pointing to the last element of
176  * the array.
177  * @param __arr Array.
178  */
179  template<typename _Tp, size_t _Nm>
180  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Tp*>
181  rbegin(_Tp (&__arr)[_Nm])
182  { return reverse_iterator<_Tp*>(__arr + _Nm); }
183 
184  /**
185  * @brief Return a reverse iterator pointing one past the first element of
186  * the array.
187  * @param __arr Array.
188  */
189  template<typename _Tp, size_t _Nm>
190  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Tp*>
191  rend(_Tp (&__arr)[_Nm])
192  { return reverse_iterator<_Tp*>(__arr); }
193 
194  /**
195  * @brief Return a reverse iterator pointing to the last element of
196  * the initializer_list.
197  * @param __il initializer_list.
198  */
199  template<typename _Tp>
200  inline _GLIBCXX17_CONSTEXPR reverse_iterator<const _Tp*>
202  { return reverse_iterator<const _Tp*>(__il.end()); }
203 
204  /**
205  * @brief Return a reverse iterator pointing one past the first element of
206  * the initializer_list.
207  * @param __il initializer_list.
208  */
209  template<typename _Tp>
210  inline _GLIBCXX17_CONSTEXPR reverse_iterator<const _Tp*>
212  { return reverse_iterator<const _Tp*>(__il.begin()); }
213 
214  /**
215  * @brief Return a reverse iterator pointing to the last element of
216  * the const container.
217  * @param __cont Container.
218  */
219  template<typename _Container>
220  inline _GLIBCXX17_CONSTEXPR auto
221  crbegin(const _Container& __cont) -> decltype(std::rbegin(__cont))
222  { return std::rbegin(__cont); }
223 
224  /**
225  * @brief Return a reverse iterator pointing one past the first element of
226  * the const container.
227  * @param __cont Container.
228  */
229  template<typename _Container>
230  inline _GLIBCXX17_CONSTEXPR auto
231  crend(const _Container& __cont) -> decltype(std::rend(__cont))
232  { return std::rend(__cont); }
233 
234 #endif // C++14
235 
236 #if __cplusplus >= 201703L
237 #define __cpp_lib_nonmember_container_access 201411
238 
239  /**
240  * @brief Return the size of a container.
241  * @param __cont Container.
242  */
243  template <typename _Container>
244  constexpr auto
245  size(const _Container& __cont) noexcept(noexcept(__cont.size()))
246  -> decltype(__cont.size())
247  { return __cont.size(); }
248 
249  /**
250  * @brief Return the size of an array.
251  */
252  template <typename _Tp, size_t _Nm>
253  constexpr size_t
254  size(const _Tp (&)[_Nm]) noexcept
255  { return _Nm; }
256 
257  /**
258  * @brief Return whether a container is empty.
259  * @param __cont Container.
260  */
261  template <typename _Container>
262  [[nodiscard]] constexpr auto
263  empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
264  -> decltype(__cont.empty())
265  { return __cont.empty(); }
266 
267  /**
268  * @brief Return whether an array is empty (always false).
269  */
270  template <typename _Tp, size_t _Nm>
271  [[nodiscard]] constexpr bool
272  empty(const _Tp (&)[_Nm]) noexcept
273  { return false; }
274 
275  /**
276  * @brief Return whether an initializer_list is empty.
277  * @param __il Initializer list.
278  */
279  template <typename _Tp>
280  [[nodiscard]] constexpr bool
281  empty(initializer_list<_Tp> __il) noexcept
282  { return __il.size() == 0;}
283 
284  /**
285  * @brief Return the data pointer of a container.
286  * @param __cont Container.
287  */
288  template <typename _Container>
289  constexpr auto
290  data(_Container& __cont) noexcept(noexcept(__cont.data()))
291  -> decltype(__cont.data())
292  { return __cont.data(); }
293 
294  /**
295  * @brief Return the data pointer of a const container.
296  * @param __cont Container.
297  */
298  template <typename _Container>
299  constexpr auto
300  data(const _Container& __cont) noexcept(noexcept(__cont.data()))
301  -> decltype(__cont.data())
302  { return __cont.data(); }
303 
304  /**
305  * @brief Return the data pointer of an array.
306  * @param __array Array.
307  */
308  template <typename _Tp, size_t _Nm>
309  constexpr _Tp*
310  data(_Tp (&__array)[_Nm]) noexcept
311  { return __array; }
312 
313  /**
314  * @brief Return the data pointer of an initializer list.
315  * @param __il Initializer list.
316  */
317  template <typename _Tp>
318  constexpr const _Tp*
319  data(initializer_list<_Tp> __il) noexcept
320  { return __il.begin(); }
321 
322 #endif // C++17
323 
324 #if __cplusplus > 201703L
325 #define __cpp_lib_ssize 201902L
326  template<typename _Container>
327  constexpr auto
328  ssize(const _Container& __cont)
329  noexcept(noexcept(__cont.size()))
330  -> common_type_t<ptrdiff_t, make_signed_t<decltype(__cont.size())>>
331  {
332  using type = make_signed_t<decltype(__cont.size())>;
333  return static_cast<common_type_t<ptrdiff_t, type>>(__cont.size());
334  }
335 
336  template<typename _Tp, ptrdiff_t _Num>
337  constexpr ptrdiff_t
338  ssize(const _Tp (&)[_Num]) noexcept
339  { return _Num; }
340 
341 #ifdef __cpp_lib_concepts
342 namespace ranges
343 {
344  template<typename>
345  inline constexpr bool disable_sized_range = false;
346 
347  template<typename _Tp>
348  inline constexpr bool enable_borrowed_range = false;
349 
350  template<typename _Tp>
351  extern const bool enable_view;
352 
353  namespace __detail
354  {
355  template<integral _Tp>
356  constexpr make_unsigned_t<_Tp>
357  __to_unsigned_like(_Tp __t) noexcept
358  { return __t; }
359 
360  template<typename _Tp, bool _MaxDiff = same_as<_Tp, __max_diff_type>>
361  using __make_unsigned_like_t
362  = conditional_t<_MaxDiff, __max_size_type, make_unsigned_t<_Tp>>;
363 
364  // Part of the constraints of ranges::borrowed_range
365  template<typename _Tp>
366  concept __maybe_borrowed_range
367  = is_lvalue_reference_v<_Tp>
368  || enable_borrowed_range<remove_cvref_t<_Tp>>;
369 
370  } // namespace __detail
371 
372  namespace __cust_access
373  {
374  using std::ranges::__detail::__maybe_borrowed_range;
375  using std::__detail::__class_or_enum;
376  using std::__detail::__decay_copy;
377  using std::__detail::__member_begin;
378  using std::__detail::__adl_begin;
379 
380  struct _Begin
381  {
382  private:
383  template<typename _Tp>
384  static constexpr bool
385  _S_noexcept()
386  {
387  if constexpr (is_array_v<remove_reference_t<_Tp>>)
388  return true;
389  else if constexpr (__member_begin<_Tp>)
390  return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
391  else
392  return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
393  }
394 
395  public:
396  template<__maybe_borrowed_range _Tp>
397  requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
398  || __adl_begin<_Tp>
399  constexpr auto
400  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
401  {
402  if constexpr (is_array_v<remove_reference_t<_Tp>>)
403  {
404  static_assert(is_lvalue_reference_v<_Tp>);
405  using _Up = remove_all_extents_t<remove_reference_t<_Tp>>;
406  static_assert(sizeof(_Up) != 0, "not array of incomplete type");
407  return __t + 0;
408  }
409  else if constexpr (__member_begin<_Tp>)
410  return __t.begin();
411  else
412  return begin(__t);
413  }
414  };
415 
416  template<typename _Tp>
417  concept __member_end = requires(_Tp& __t)
418  {
419  { __decay_copy(__t.end()) }
420  -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
421  };
422 
423  void end(auto&) = delete;
424  void end(const auto&) = delete;
425 
426  template<typename _Tp>
427  concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
428  && requires(_Tp& __t)
429  {
430  { __decay_copy(end(__t)) }
431  -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
432  };
433 
434  struct _End
435  {
436  private:
437  template<typename _Tp>
438  static constexpr bool
439  _S_noexcept()
440  {
441  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
442  return true;
443  else if constexpr (__member_end<_Tp>)
444  return noexcept(__decay_copy(std::declval<_Tp&>().end()));
445  else
446  return noexcept(__decay_copy(end(std::declval<_Tp&>())));
447  }
448 
449  public:
450  template<__maybe_borrowed_range _Tp>
451  requires is_bounded_array_v<remove_reference_t<_Tp>> || __member_end<_Tp>
452  || __adl_end<_Tp>
453  constexpr auto
454  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
455  {
456  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
457  {
458  static_assert(is_lvalue_reference_v<_Tp>);
459  return __t + extent_v<remove_reference_t<_Tp>>;
460  }
461  else if constexpr (__member_end<_Tp>)
462  return __t.end();
463  else
464  return end(__t);
465  }
466  };
467 
468  template<typename _Tp>
469  constexpr decltype(auto)
470  __as_const(_Tp&& __t) noexcept
471  {
472  if constexpr (is_lvalue_reference_v<_Tp>)
473  return static_cast<const remove_reference_t<_Tp>&>(__t);
474  else
475  return static_cast<const _Tp&&>(__t);
476  }
477 
478  struct _CBegin
479  {
480  template<typename _Tp>
481  constexpr auto
482  operator()(_Tp&& __e) const
483  noexcept(noexcept(_Begin{}(__cust_access::__as_const((_Tp&&)__e))))
484  requires requires { _Begin{}(__cust_access::__as_const((_Tp&&)__e)); }
485  {
486  return _Begin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
487  }
488  };
489 
490  struct _CEnd
491  {
492  template<typename _Tp>
493  constexpr auto
494  operator()(_Tp&& __e) const
495  noexcept(noexcept(_End{}(__cust_access::__as_const((_Tp&&)__e))))
496  requires requires { _End{}(__cust_access::__as_const((_Tp&&)__e)); }
497  {
498  return _End{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
499  }
500  };
501 
502  template<typename _Tp>
503  concept __member_rbegin = requires(_Tp& __t)
504  {
505  { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
506  };
507 
508  void rbegin(auto&) = delete;
509  void rbegin(const auto&) = delete;
510 
511  template<typename _Tp>
512  concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
513  && requires(_Tp& __t)
514  {
515  { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
516  };
517 
518  template<typename _Tp>
519  concept __reversable = requires(_Tp& __t)
520  {
521  { _Begin{}(__t) } -> bidirectional_iterator;
522  { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
523  };
524 
525  struct _RBegin
526  {
527  private:
528  template<typename _Tp>
529  static constexpr bool
530  _S_noexcept()
531  {
532  if constexpr (__member_rbegin<_Tp>)
533  return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
534  else if constexpr (__adl_rbegin<_Tp>)
535  return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
536  else
537  {
538  if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
539  {
540  using _It = decltype(_End{}(std::declval<_Tp&>()));
541  // std::reverse_iterator copy-initializes its member.
542  return is_nothrow_copy_constructible_v<_It>;
543  }
544  else
545  return false;
546  }
547  }
548 
549  public:
550  template<__maybe_borrowed_range _Tp>
551  requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
552  constexpr auto
553  operator()(_Tp&& __t) const
554  noexcept(_S_noexcept<_Tp>())
555  {
556  if constexpr (__member_rbegin<_Tp>)
557  return __t.rbegin();
558  else if constexpr (__adl_rbegin<_Tp>)
559  return rbegin(__t);
560  else
561  return std::make_reverse_iterator(_End{}(__t));
562  }
563  };
564 
565  template<typename _Tp>
566  concept __member_rend = requires(_Tp& __t)
567  {
568  { __decay_copy(__t.rend()) }
569  -> sentinel_for<decltype(_RBegin{}(__t))>;
570  };
571 
572  void rend(auto&) = delete;
573  void rend(const auto&) = delete;
574 
575  template<typename _Tp>
576  concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
577  && requires(_Tp& __t)
578  {
579  { __decay_copy(rend(__t)) }
580  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
581  };
582 
583  struct _REnd
584  {
585  private:
586  template<typename _Tp>
587  static constexpr bool
588  _S_noexcept()
589  {
590  if constexpr (__member_rend<_Tp>)
591  return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
592  else if constexpr (__adl_rend<_Tp>)
593  return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
594  else
595  {
596  if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
597  {
598  using _It = decltype(_Begin{}(std::declval<_Tp&>()));
599  // std::reverse_iterator copy-initializes its member.
600  return is_nothrow_copy_constructible_v<_It>;
601  }
602  else
603  return false;
604  }
605  }
606 
607  public:
608  template<__maybe_borrowed_range _Tp>
609  requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
610  constexpr auto
611  operator()(_Tp&& __t) const
612  noexcept(_S_noexcept<_Tp>())
613  {
614  if constexpr (__member_rend<_Tp>)
615  return __t.rend();
616  else if constexpr (__adl_rend<_Tp>)
617  return rend(__t);
618  else
619  return std::make_reverse_iterator(_Begin{}(__t));
620  }
621  };
622 
623  struct _CRBegin
624  {
625  template<typename _Tp>
626  constexpr auto
627  operator()(_Tp&& __e) const
628  noexcept(noexcept(_RBegin{}(__cust_access::__as_const((_Tp&&)__e))))
629  requires requires { _RBegin{}(__cust_access::__as_const((_Tp&&)__e)); }
630  {
631  return _RBegin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
632  }
633  };
634 
635  struct _CREnd
636  {
637  template<typename _Tp>
638  constexpr auto
639  operator()(_Tp&& __e) const
640  noexcept(noexcept(_REnd{}(__cust_access::__as_const((_Tp&&)__e))))
641  requires requires { _REnd{}(__cust_access::__as_const((_Tp&&)__e)); }
642  {
643  return _REnd{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
644  }
645  };
646 
647  template<typename _Tp>
648  concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
649  && requires(_Tp&& __t)
650  {
651  { __decay_copy(std::forward<_Tp>(__t).size()) }
652  -> __detail::__is_integer_like;
653  };
654 
655  void size(auto&) = delete;
656  void size(const auto&) = delete;
657 
658  template<typename _Tp>
659  concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
660  && !disable_sized_range<remove_cvref_t<_Tp>>
661  && requires(_Tp&& __t)
662  {
663  { __decay_copy(size(std::forward<_Tp>(__t))) }
664  -> __detail::__is_integer_like;
665  };
666 
667  template<typename _Tp>
668  concept __sentinel_size = requires(_Tp&& __t)
669  {
670  { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
671 
672  { _End{}(std::forward<_Tp>(__t)) }
673  -> sized_sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
674  };
675 
676  struct _Size
677  {
678  private:
679  template<typename _Tp>
680  static constexpr bool
681  _S_noexcept()
682  {
683  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
684  return true;
685  else if constexpr (__member_size<_Tp>)
686  return noexcept(__decay_copy(std::declval<_Tp>().size()));
687  else if constexpr (__adl_size<_Tp>)
688  return noexcept(__decay_copy(size(std::declval<_Tp>())));
689  else if constexpr (__sentinel_size<_Tp>)
690  return noexcept(_End{}(std::declval<_Tp>())
691  - _Begin{}(std::declval<_Tp>()));
692  }
693 
694  public:
695  template<typename _Tp>
696  requires is_bounded_array_v<remove_reference_t<_Tp>>
697  || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
698  constexpr auto
699  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
700  {
701  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
702  {
703  return extent_v<remove_reference_t<_Tp>>;
704  }
705  else if constexpr (__member_size<_Tp>)
706  return std::forward<_Tp>(__e).size();
707  else if constexpr (__adl_size<_Tp>)
708  return size(std::forward<_Tp>(__e));
709  else if constexpr (__sentinel_size<_Tp>)
710  return __detail::__to_unsigned_like(
711  _End{}(std::forward<_Tp>(__e))
712  - _Begin{}(std::forward<_Tp>(__e)));
713  }
714  };
715 
716  struct _SSize
717  {
718  template<typename _Tp>
719  requires requires (_Tp&& __e)
720  {
721  _Begin{}(std::forward<_Tp>(__e));
722  _Size{}(std::forward<_Tp>(__e));
723  }
724  constexpr auto
725  operator()(_Tp&& __e) const
726  noexcept(noexcept(_Size{}(std::forward<_Tp>(__e))))
727  {
728  using __iter_type = decltype(_Begin{}(std::forward<_Tp>(__e)));
729  using __diff_type = iter_difference_t<__iter_type>;
730  using __gnu_cxx::__int_traits;
731  auto __size = _Size{}(std::forward<_Tp>(__e));
732  if constexpr (integral<__diff_type>)
733  {
734  if constexpr (__int_traits<__diff_type>::__digits
735  < __int_traits<ptrdiff_t>::__digits)
736  return static_cast<ptrdiff_t>(__size);
737  }
738  return static_cast<__diff_type>(__size);
739  }
740  };
741 
742  template<typename _Tp>
743  concept __member_empty = requires(_Tp&& __t)
744  { bool(std::forward<_Tp>(__t).empty()); };
745 
746  template<typename _Tp>
747  concept __size0_empty = requires(_Tp&& __t)
748  { _Size{}(std::forward<_Tp>(__t)) == 0; };
749 
750  template<typename _Tp>
751  concept __eq_iter_empty = requires(_Tp&& __t)
752  {
753  { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
754  bool(_Begin{}(std::forward<_Tp>(__t))
755  == _End{}(std::forward<_Tp>(__t)));
756  };
757 
758  struct _Empty
759  {
760  private:
761  template<typename _Tp>
762  static constexpr bool
763  _S_noexcept()
764  {
765  if constexpr (__member_empty<_Tp>)
766  return noexcept(std::declval<_Tp>().empty());
767  else if constexpr (__size0_empty<_Tp>)
768  return noexcept(_Size{}(std::declval<_Tp>()) == 0);
769  else
770  return noexcept(bool(_Begin{}(std::declval<_Tp>())
771  == _End{}(std::declval<_Tp>())));
772  }
773 
774  public:
775  template<typename _Tp>
776  requires __member_empty<_Tp> || __size0_empty<_Tp>
777  || __eq_iter_empty<_Tp>
778  constexpr bool
779  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
780  {
781  if constexpr (__member_empty<_Tp>)
782  return bool(std::forward<_Tp>(__e).empty());
783  else if constexpr (__size0_empty<_Tp>)
784  return _Size{}(std::forward<_Tp>(__e)) == 0;
785  else
786  return bool(_Begin{}(std::forward<_Tp>(__e))
787  == _End{}(std::forward<_Tp>(__e)));
788  }
789  };
790 
791  template<typename _Tp>
792  concept __pointer_to_object = is_pointer_v<_Tp>
793  && is_object_v<remove_pointer_t<_Tp>>;
794 
795  template<typename _Tp>
796  concept __member_data = is_lvalue_reference_v<_Tp>
797  && requires(_Tp __t) { { __t.data() } -> __pointer_to_object; };
798 
799  template<typename _Tp>
800  concept __begin_data = requires(_Tp&& __t)
801  { { _Begin{}(std::forward<_Tp>(__t)) } -> contiguous_iterator; };
802 
803  struct _Data
804  {
805  private:
806  template<typename _Tp>
807  static constexpr bool
808  _S_noexcept()
809  {
810  if constexpr (__member_data<_Tp>)
811  return noexcept(__decay_copy(std::declval<_Tp>().data()));
812  else
813  return noexcept(_Begin{}(std::declval<_Tp>()));
814  }
815 
816  public:
817  template<__maybe_borrowed_range _Tp>
818  requires __member_data<_Tp> || __begin_data<_Tp>
819  constexpr auto
820  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
821  {
822  if constexpr (__member_data<_Tp>)
823  return __e.data();
824  else
825  return std::to_address(_Begin{}(std::forward<_Tp>(__e)));
826  }
827  };
828 
829  struct _CData
830  {
831  template<typename _Tp>
832  constexpr auto
833  operator()(_Tp&& __e) const
834  noexcept(noexcept(_Data{}(__cust_access::__as_const((_Tp&&)__e))))
835  requires requires { _Data{}(__cust_access::__as_const((_Tp&&)__e)); }
836  {
837  return _Data{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
838  }
839  };
840 
841  } // namespace __cust_access
842 
843  inline namespace __cust
844  {
845  inline constexpr __cust_access::_Begin begin{};
846  inline constexpr __cust_access::_End end{};
847  inline constexpr __cust_access::_CBegin cbegin{};
848  inline constexpr __cust_access::_CEnd cend{};
849  inline constexpr __cust_access::_RBegin rbegin{};
850  inline constexpr __cust_access::_REnd rend{};
851  inline constexpr __cust_access::_CRBegin crbegin{};
852  inline constexpr __cust_access::_CREnd crend{};
853  inline constexpr __cust_access::_Size size{};
854  inline constexpr __cust_access::_SSize ssize{};
855  inline constexpr __cust_access::_Empty empty{};
856  inline constexpr __cust_access::_Data data{};
857  inline constexpr __cust_access::_CData cdata{};
858  }
859 
860  /// [range.range] The range concept.
861  template<typename _Tp>
862  concept range = requires(_Tp& __t)
863  {
864  ranges::begin(__t);
865  ranges::end(__t);
866  };
867 
868  /// [range.range] The borrowed_range concept.
869  template<typename _Tp>
870  concept borrowed_range
871  = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
872 
873  template<typename _Tp>
874  using iterator_t = std::__detail::__range_iter_t<_Tp>;
875 
876  template<range _Range>
877  using sentinel_t = decltype(ranges::end(std::declval<_Range&>()));
878 
879  template<range _Range>
880  using range_difference_t = iter_difference_t<iterator_t<_Range>>;
881 
882  template<range _Range>
883  using range_value_t = iter_value_t<iterator_t<_Range>>;
884 
885  template<range _Range>
886  using range_reference_t = iter_reference_t<iterator_t<_Range>>;
887 
888  template<range _Range>
889  using range_rvalue_reference_t
890  = iter_rvalue_reference_t<iterator_t<_Range>>;
891 
892  /// [range.sized] The sized_range concept.
893  template<typename _Tp>
894  concept sized_range = range<_Tp>
895  && requires(_Tp& __t) { ranges::size(__t); };
896 
897  template<sized_range _Range>
898  using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
899 
900  // [range.refinements]
901 
902  /// A range for which ranges::begin returns an output iterator.
903  template<typename _Range, typename _Tp>
904  concept output_range
905  = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
906 
907  /// A range for which ranges::begin returns an input iterator.
908  template<typename _Tp>
909  concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
910 
911  /// A range for which ranges::begin returns a forward iterator.
912  template<typename _Tp>
913  concept forward_range
914  = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
915 
916  /// A range for which ranges::begin returns a bidirectional iterator.
917  template<typename _Tp>
918  concept bidirectional_range
919  = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
920 
921  /// A range for which ranges::begin returns a random access iterator.
922  template<typename _Tp>
923  concept random_access_range
924  = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
925 
926  /// A range for which ranges::begin returns a contiguous iterator.
927  template<typename _Tp>
928  concept contiguous_range
929  = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
930  && requires(_Tp& __t)
931  {
932  { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
933  };
934 
935  /// A range for which ranges::begin and ranges::end return the same type.
936  template<typename _Tp>
937  concept common_range
938  = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
939 
940  // [range.iter.ops] range iterator operations
941 
942  template<input_or_output_iterator _It>
943  constexpr void
944  advance(_It& __it, iter_difference_t<_It> __n)
945  {
946  if constexpr (random_access_iterator<_It>)
947  __it += __n;
948  else if constexpr (bidirectional_iterator<_It>)
949  {
950  if (__n > 0)
951  {
952  do
953  {
954  ++__it;
955  }
956  while (--__n);
957  }
958  else if (__n < 0)
959  {
960  do
961  {
962  --__it;
963  }
964  while (++__n);
965  }
966  }
967  else
968  {
969 #ifdef __cpp_lib_is_constant_evaluated
970  if (std::is_constant_evaluated() && __n < 0)
971  throw "attempt to decrement a non-bidirectional iterator";
972 #endif
973  __glibcxx_assert(__n >= 0);
974  while (__n-- > 0)
975  ++__it;
976  }
977  }
978 
979  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
980  constexpr void
981  advance(_It& __it, _Sent __bound)
982  {
983  if constexpr (assignable_from<_It&, _Sent>)
984  __it = std::move(__bound);
985  else if constexpr (sized_sentinel_for<_Sent, _It>)
986  ranges::advance(__it, __bound - __it);
987  else
988  {
989  while (__it != __bound)
990  ++__it;
991  }
992  }
993 
994  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
995  constexpr iter_difference_t<_It>
996  advance(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
997  {
998  if constexpr (sized_sentinel_for<_Sent, _It>)
999  {
1000  const auto __diff = __bound - __it;
1001 #ifdef __cpp_lib_is_constant_evaluated
1002  if (std::is_constant_evaluated()
1003  && !(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)))
1004  throw "inconsistent directions for distance and bound";
1005 #endif
1006  // n and bound must not lead in opposite directions:
1007  __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
1008  const auto __absdiff = __diff < 0 ? -__diff : __diff;
1009  const auto __absn = __n < 0 ? -__n : __n;;
1010  if (__absn >= __absdiff)
1011  {
1012  ranges::advance(__it, __bound);
1013  return __n - __diff;
1014  }
1015  else
1016  {
1017  ranges::advance(__it, __n);
1018  return 0;
1019  }
1020  }
1021  else if (__it == __bound || __n == 0)
1022  return iter_difference_t<_It>(0);
1023  else if (__n > 0)
1024  {
1025  iter_difference_t<_It> __m = 0;
1026  do
1027  {
1028  ++__it;
1029  ++__m;
1030  }
1031  while (__m != __n && __it != __bound);
1032  return __n - __m;
1033  }
1034  else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
1035  {
1036  iter_difference_t<_It> __m = 0;
1037  do
1038  {
1039  --__it;
1040  --__m;
1041  }
1042  while (__m != __n && __it != __bound);
1043  return __n - __m;
1044  }
1045  else
1046  {
1047 #ifdef __cpp_lib_is_constant_evaluated
1048  if (std::is_constant_evaluated() && __n < 0)
1049  throw "attempt to decrement a non-bidirectional iterator";
1050 #endif
1051  __glibcxx_assert(__n >= 0);
1052  return __n;
1053  }
1054  }
1055 
1056  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1057  constexpr iter_difference_t<_It>
1058  distance(_It __first, _Sent __last)
1059  {
1060  if constexpr (sized_sentinel_for<_Sent, _It>)
1061  return __last - __first;
1062  else
1063  {
1064  iter_difference_t<_It> __n = 0;
1065  while (__first != __last)
1066  {
1067  ++__first;
1068  ++__n;
1069  }
1070  return __n;
1071  }
1072  }
1073 
1074  template<range _Range>
1075  constexpr range_difference_t<_Range>
1076  distance(_Range&& __r)
1077  {
1078  if constexpr (sized_range<_Range>)
1079  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
1080  else
1081  return ranges::distance(ranges::begin(__r), ranges::end(__r));
1082  }
1083 
1084  template<input_or_output_iterator _It>
1085  constexpr _It
1086  next(_It __x)
1087  {
1088  ++__x;
1089  return __x;
1090  }
1091 
1092  template<input_or_output_iterator _It>
1093  constexpr _It
1094  next(_It __x, iter_difference_t<_It> __n)
1095  {
1096  ranges::advance(__x, __n);
1097  return __x;
1098  }
1099 
1100  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1101  constexpr _It
1102  next(_It __x, _Sent __bound)
1103  {
1104  ranges::advance(__x, __bound);
1105  return __x;
1106  }
1107 
1108  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1109  constexpr _It
1110  next(_It __x, iter_difference_t<_It> __n, _Sent __bound)
1111  {
1112  ranges::advance(__x, __n, __bound);
1113  return __x;
1114  }
1115 
1116  template<bidirectional_iterator _It>
1117  constexpr _It
1118  prev(_It __x)
1119  {
1120  --__x;
1121  return __x;
1122  }
1123 
1124  template<bidirectional_iterator _It>
1125  constexpr _It
1126  prev(_It __x, iter_difference_t<_It> __n)
1127  {
1128  ranges::advance(__x, -__n);
1129  return __x;
1130  }
1131 
1132  template<bidirectional_iterator _It>
1133  constexpr _It
1134  prev(_It __x, iter_difference_t<_It> __n, _It __bound)
1135  {
1136  ranges::advance(__x, -__n, __bound);
1137  return __x;
1138  }
1139 
1140 } // namespace ranges
1141 #endif // library concepts
1142 #endif // C++20
1143 _GLIBCXX_END_NAMESPACE_VERSION
1144 } // namespace
1145 
1146 #endif // C++11
1147 
1148 #endif // _GLIBCXX_RANGE_ACCESS_H
std::make_signed_t
typename make_signed< _Tp >::type make_signed_t
Alias template for make_signed.
Definition: type_traits:1961
iterator_concepts.h
std::common_type_t
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
Definition: type_traits:2562
numeric_traits.h
std::cend
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
std::begin
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
std::make_reverse_iterator
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
Definition: bits/stl_iterator.h:527
std::remove_reference_t
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1635
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
std::initializer_list
initializer_list
Definition: initializer_list:48
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:202
initializer_list
std::reverse_iterator
Definition: bits/stl_iterator.h:131
std::crend
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
std::rend
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
std
ISO C++ entities toplevel namespace is std.
std::end
constexpr _Tp * end(_Tp(&__arr)[_Nm])
Return an iterator pointing to one past the last element of the array.
Definition: range_access.h:100
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:138
std::begin
constexpr _Tp * begin(_Tp(&__arr)[_Nm])
Return an iterator pointing to the first element of the array.
Definition: range_access.h:90
std::crbegin
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
std::cbegin
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
std::rbegin
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
std::end
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234