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 <bits/int_limits.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  template<typename _Container>
326  constexpr auto
327  ssize(const _Container& __cont)
328  noexcept(noexcept(__cont.size()))
329  -> common_type_t<ptrdiff_t, make_signed_t<decltype(__cont.size())>>
330  {
331  using type = make_signed_t<decltype(__cont.size())>;
332  return static_cast<common_type_t<ptrdiff_t, type>>(__cont.size());
333  }
334 
335  template<typename _Tp, ptrdiff_t _Num>
336  constexpr ptrdiff_t
337  ssize(const _Tp (&)[_Num]) noexcept
338  { return _Num; }
339 
340 #ifdef __cpp_lib_concepts
341 namespace ranges
342 {
343  template<typename>
344  inline constexpr bool disable_sized_range = false;
345 
346  template<typename _Tp>
347  inline constexpr bool enable_borrowed_range = false;
348 
349  namespace __detail
350  {
351  template<integral _Tp>
352  constexpr make_unsigned_t<_Tp>
353  __to_unsigned_like(_Tp __t) noexcept
354  { return __t; }
355 
356  template<typename _Tp, bool _MaxDiff = same_as<_Tp, __max_diff_type>>
357  using __make_unsigned_like_t
358  = conditional_t<_MaxDiff, __max_size_type, make_unsigned_t<_Tp>>;
359 
360  // Part of the constraints of ranges::borrowed_range
361  template<typename _Tp>
362  concept __maybe_borrowed_range
363  = is_lvalue_reference_v<_Tp>
364  || enable_borrowed_range<remove_cvref_t<_Tp>>;
365 
366  } // namespace __detail
367 
368  namespace __cust_access
369  {
370  using std::ranges::__detail::__maybe_borrowed_range;
371  using std::__detail::__class_or_enum;
372 
373  template<typename _Tp>
374  constexpr decay_t<_Tp>
375  __decay_copy(_Tp&& __t)
376  noexcept(is_nothrow_convertible_v<_Tp, decay_t<_Tp>>)
377  { return std::forward<_Tp>(__t); }
378 
379  template<typename _Tp>
380  concept __member_begin = requires(_Tp& __t)
381  {
382  { __decay_copy(__t.begin()) } -> input_or_output_iterator;
383  };
384 
385  void begin(auto&) = delete;
386  void begin(const auto&) = delete;
387 
388  template<typename _Tp>
389  concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>>
390  && requires(_Tp& __t)
391  {
392  { __decay_copy(begin(__t)) } -> input_or_output_iterator;
393  };
394 
395  struct _Begin
396  {
397  private:
398  template<typename _Tp>
399  static constexpr bool
400  _S_noexcept()
401  {
402  if constexpr (is_array_v<remove_reference_t<_Tp>>)
403  return true;
404  else if constexpr (__member_begin<_Tp>)
405  return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
406  else
407  return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
408  }
409 
410  public:
411  template<__maybe_borrowed_range _Tp>
412  requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
413  || __adl_begin<_Tp>
414  constexpr auto
415  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
416  {
417  if constexpr (is_array_v<remove_reference_t<_Tp>>)
418  {
419  static_assert(is_lvalue_reference_v<_Tp>);
420  using _Up = remove_all_extents_t<remove_reference_t<_Tp>>;
421  static_assert(sizeof(_Up) != 0, "not array of incomplete type");
422  return __t + 0;
423  }
424  else if constexpr (__member_begin<_Tp>)
425  return __t.begin();
426  else
427  return begin(__t);
428  }
429  };
430 
431  template<typename _Tp>
432  concept __member_end = requires(_Tp& __t)
433  {
434  { __decay_copy(__t.end()) }
435  -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
436  };
437 
438  void end(auto&) = delete;
439  void end(const auto&) = delete;
440 
441  template<typename _Tp>
442  concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
443  && requires(_Tp& __t)
444  {
445  { __decay_copy(end(__t)) }
446  -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
447  };
448 
449  struct _End
450  {
451  private:
452  template<typename _Tp>
453  static constexpr bool
454  _S_noexcept()
455  {
456  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
457  return true;
458  else if constexpr (__member_end<_Tp>)
459  return noexcept(__decay_copy(std::declval<_Tp&>().end()));
460  else
461  return noexcept(__decay_copy(end(std::declval<_Tp&>())));
462  }
463 
464  public:
465  template<__maybe_borrowed_range _Tp>
466  requires is_bounded_array_v<remove_reference_t<_Tp>> || __member_end<_Tp>
467  || __adl_end<_Tp>
468  constexpr auto
469  operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
470  {
471  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
472  {
473  static_assert(is_lvalue_reference_v<_Tp>);
474  return __t + extent_v<remove_reference_t<_Tp>>;
475  }
476  else if constexpr (__member_end<_Tp>)
477  return __t.end();
478  else
479  return end(__t);
480  }
481  };
482 
483  template<typename _Tp>
484  constexpr decltype(auto)
485  __as_const(_Tp&& __t) noexcept
486  {
487  if constexpr (is_lvalue_reference_v<_Tp>)
488  return static_cast<const remove_reference_t<_Tp>&>(__t);
489  else
490  return static_cast<const _Tp&&>(__t);
491  }
492 
493  struct _CBegin
494  {
495  template<typename _Tp>
496  constexpr auto
497  operator()(_Tp&& __e) const
498  noexcept(noexcept(_Begin{}(__cust_access::__as_const((_Tp&&)__e))))
499  requires requires { _Begin{}(__cust_access::__as_const((_Tp&&)__e)); }
500  {
501  return _Begin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
502  }
503  };
504 
505  struct _CEnd
506  {
507  template<typename _Tp>
508  constexpr auto
509  operator()(_Tp&& __e) const
510  noexcept(noexcept(_End{}(__cust_access::__as_const((_Tp&&)__e))))
511  requires requires { _End{}(__cust_access::__as_const((_Tp&&)__e)); }
512  {
513  return _End{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
514  }
515  };
516 
517  template<typename _Tp>
518  concept __member_rbegin = requires(_Tp& __t)
519  {
520  { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
521  };
522 
523  void rbegin(auto&) = delete;
524  void rbegin(const auto&) = delete;
525 
526  template<typename _Tp>
527  concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
528  && requires(_Tp& __t)
529  {
530  { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
531  };
532 
533  template<typename _Tp>
534  concept __reversable = requires(_Tp& __t)
535  {
536  { _Begin{}(__t) } -> bidirectional_iterator;
537  { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
538  };
539 
540  struct _RBegin
541  {
542  private:
543  template<typename _Tp>
544  static constexpr bool
545  _S_noexcept()
546  {
547  if constexpr (__member_rbegin<_Tp>)
548  return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
549  else if constexpr (__adl_rbegin<_Tp>)
550  return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
551  else
552  {
553  if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
554  {
555  using _It = decltype(_End{}(std::declval<_Tp&>()));
556  // std::reverse_iterator copy-initializes its member.
557  return is_nothrow_copy_constructible_v<_It>;
558  }
559  else
560  return false;
561  }
562  }
563 
564  public:
565  template<__maybe_borrowed_range _Tp>
566  requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
567  constexpr auto
568  operator()(_Tp&& __t) const
569  noexcept(_S_noexcept<_Tp>())
570  {
571  if constexpr (__member_rbegin<_Tp>)
572  return __t.rbegin();
573  else if constexpr (__adl_rbegin<_Tp>)
574  return rbegin(__t);
575  else
576  return std::make_reverse_iterator(_End{}(__t));
577  }
578  };
579 
580  template<typename _Tp>
581  concept __member_rend = requires(_Tp& __t)
582  {
583  { __decay_copy(__t.rend()) }
584  -> sentinel_for<decltype(_RBegin{}(__t))>;
585  };
586 
587  void rend(auto&) = delete;
588  void rend(const auto&) = delete;
589 
590  template<typename _Tp>
591  concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
592  && requires(_Tp& __t)
593  {
594  { __decay_copy(rend(__t)) }
595  -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
596  };
597 
598  struct _REnd
599  {
600  private:
601  template<typename _Tp>
602  static constexpr bool
603  _S_noexcept()
604  {
605  if constexpr (__member_rend<_Tp>)
606  return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
607  else if constexpr (__adl_rend<_Tp>)
608  return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
609  else
610  {
611  if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
612  {
613  using _It = decltype(_Begin{}(std::declval<_Tp&>()));
614  // std::reverse_iterator copy-initializes its member.
615  return is_nothrow_copy_constructible_v<_It>;
616  }
617  else
618  return false;
619  }
620  }
621 
622  public:
623  template<__maybe_borrowed_range _Tp>
624  requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
625  constexpr auto
626  operator()(_Tp&& __t) const
627  noexcept(_S_noexcept<_Tp>())
628  {
629  if constexpr (__member_rend<_Tp>)
630  return __t.rend();
631  else if constexpr (__adl_rend<_Tp>)
632  return rend(__t);
633  else
634  return std::make_reverse_iterator(_Begin{}(__t));
635  }
636  };
637 
638  struct _CRBegin
639  {
640  template<typename _Tp>
641  constexpr auto
642  operator()(_Tp&& __e) const
643  noexcept(noexcept(_RBegin{}(__cust_access::__as_const((_Tp&&)__e))))
644  requires requires { _RBegin{}(__cust_access::__as_const((_Tp&&)__e)); }
645  {
646  return _RBegin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
647  }
648  };
649 
650  struct _CREnd
651  {
652  template<typename _Tp>
653  constexpr auto
654  operator()(_Tp&& __e) const
655  noexcept(noexcept(_REnd{}(__cust_access::__as_const((_Tp&&)__e))))
656  requires requires { _REnd{}(__cust_access::__as_const((_Tp&&)__e)); }
657  {
658  return _REnd{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
659  }
660  };
661 
662  template<typename _Tp>
663  concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
664  && requires(_Tp&& __t)
665  {
666  { __decay_copy(std::forward<_Tp>(__t).size()) }
667  -> __detail::__is_integer_like;
668  };
669 
670  void size(auto&) = delete;
671  void size(const auto&) = delete;
672 
673  template<typename _Tp>
674  concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
675  && !disable_sized_range<remove_cvref_t<_Tp>>
676  && requires(_Tp&& __t)
677  {
678  { __decay_copy(size(std::forward<_Tp>(__t))) }
679  -> __detail::__is_integer_like;
680  };
681 
682  template<typename _Tp>
683  concept __sentinel_size = requires(_Tp&& __t)
684  {
685  { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
686 
687  { _End{}(std::forward<_Tp>(__t)) }
688  -> sized_sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
689  };
690 
691  struct _Size
692  {
693  private:
694  template<typename _Tp>
695  static constexpr bool
696  _S_noexcept()
697  {
698  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
699  return true;
700  else if constexpr (__member_size<_Tp>)
701  return noexcept(__decay_copy(std::declval<_Tp>().size()));
702  else if constexpr (__adl_size<_Tp>)
703  return noexcept(__decay_copy(size(std::declval<_Tp>())));
704  else if constexpr (__sentinel_size<_Tp>)
705  return noexcept(_End{}(std::declval<_Tp>())
706  - _Begin{}(std::declval<_Tp>()));
707  }
708 
709  public:
710  template<typename _Tp>
711  requires is_bounded_array_v<remove_reference_t<_Tp>>
712  || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
713  constexpr auto
714  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
715  {
716  if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
717  {
718  return extent_v<remove_reference_t<_Tp>>;
719  }
720  else if constexpr (__member_size<_Tp>)
721  return std::forward<_Tp>(__e).size();
722  else if constexpr (__adl_size<_Tp>)
723  return size(std::forward<_Tp>(__e));
724  else if constexpr (__sentinel_size<_Tp>)
725  return __detail::__to_unsigned_like(
726  _End{}(std::forward<_Tp>(__e))
727  - _Begin{}(std::forward<_Tp>(__e)));
728  }
729  };
730 
731  struct _SSize
732  {
733  template<typename _Tp>
734  requires requires (_Tp&& __e)
735  {
736  _Begin{}(std::forward<_Tp>(__e));
737  _Size{}(std::forward<_Tp>(__e));
738  }
739  constexpr auto
740  operator()(_Tp&& __e) const
741  noexcept(noexcept(_Size{}(std::forward<_Tp>(__e))))
742  {
743  using __iter_type = decltype(_Begin{}(std::forward<_Tp>(__e)));
744  using __diff_type = iter_difference_t<__iter_type>;
745  using std::__detail::__int_limits;
746  auto __size = _Size{}(std::forward<_Tp>(__e));
747  if constexpr (integral<__diff_type>)
748  {
749  if constexpr (__int_limits<__diff_type>::digits
750  < __int_limits<ptrdiff_t>::digits)
751  return static_cast<ptrdiff_t>(__size);
752  }
753  return static_cast<__diff_type>(__size);
754  }
755  };
756 
757  template<typename _Tp>
758  concept __member_empty = requires(_Tp&& __t)
759  { bool(std::forward<_Tp>(__t).empty()); };
760 
761  template<typename _Tp>
762  concept __size0_empty = requires(_Tp&& __t)
763  { _Size{}(std::forward<_Tp>(__t)) == 0; };
764 
765  template<typename _Tp>
766  concept __eq_iter_empty = requires(_Tp&& __t)
767  {
768  { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
769  bool(_Begin{}(std::forward<_Tp>(__t))
770  == _End{}(std::forward<_Tp>(__t)));
771  };
772 
773  struct _Empty
774  {
775  private:
776  template<typename _Tp>
777  static constexpr bool
778  _S_noexcept()
779  {
780  if constexpr (__member_empty<_Tp>)
781  return noexcept(std::declval<_Tp>().empty());
782  else if constexpr (__size0_empty<_Tp>)
783  return noexcept(_Size{}(std::declval<_Tp>()) == 0);
784  else
785  return noexcept(bool(_Begin{}(std::declval<_Tp>())
786  == _End{}(std::declval<_Tp>())));
787  }
788 
789  public:
790  template<typename _Tp>
791  requires __member_empty<_Tp> || __size0_empty<_Tp>
792  || __eq_iter_empty<_Tp>
793  constexpr auto
794  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
795  {
796  if constexpr (__member_empty<_Tp>)
797  return bool(std::forward<_Tp>(__e).empty());
798  else if constexpr (__size0_empty<_Tp>)
799  return _Size{}(std::forward<_Tp>(__e)) == 0;
800  else
801  return bool(_Begin{}(std::forward<_Tp>(__e))
802  == _End{}(std::forward<_Tp>(__e)));
803  }
804  };
805 
806  template<typename _Tp>
807  concept __pointer_to_object = is_pointer_v<_Tp>
808  && is_object_v<remove_pointer_t<_Tp>>;
809 
810  template<typename _Tp>
811  concept __member_data = is_lvalue_reference_v<_Tp>
812  && requires(_Tp __t) { { __t.data() } -> __pointer_to_object; };
813 
814  template<typename _Tp>
815  concept __begin_data = requires(_Tp&& __t)
816  { { _Begin{}(std::forward<_Tp>(__t)) } -> contiguous_iterator; };
817 
818  struct _Data
819  {
820  private:
821  template<typename _Tp>
822  static constexpr bool
823  _S_noexcept()
824  {
825  if constexpr (__member_data<_Tp>)
826  return noexcept(__decay_copy(std::declval<_Tp>().data()));
827  else
828  return noexcept(_Begin{}(std::declval<_Tp>()));
829  }
830 
831  public:
832  template<__maybe_borrowed_range _Tp>
833  requires __member_data<_Tp> || __begin_data<_Tp>
834  constexpr auto
835  operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>())
836  {
837  if constexpr (__member_data<_Tp>)
838  return __e.data();
839  else
840  return std::to_address(_Begin{}(std::forward<_Tp>(__e)));
841  }
842  };
843 
844  struct _CData
845  {
846  template<typename _Tp>
847  constexpr auto
848  operator()(_Tp&& __e) const
849  noexcept(noexcept(_Data{}(__cust_access::__as_const((_Tp&&)__e))))
850  requires requires { _Data{}(__cust_access::__as_const((_Tp&&)__e)); }
851  {
852  return _Data{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
853  }
854  };
855 
856  } // namespace __cust_access
857 
858  inline namespace __cust
859  {
860  inline constexpr __cust_access::_Begin begin{};
861  inline constexpr __cust_access::_End end{};
862  inline constexpr __cust_access::_CBegin cbegin{};
863  inline constexpr __cust_access::_CEnd cend{};
864  inline constexpr __cust_access::_RBegin rbegin{};
865  inline constexpr __cust_access::_REnd rend{};
866  inline constexpr __cust_access::_CRBegin crbegin{};
867  inline constexpr __cust_access::_CREnd crend{};
868  inline constexpr __cust_access::_Size size{};
869  inline constexpr __cust_access::_SSize ssize{};
870  inline constexpr __cust_access::_Empty empty{};
871  inline constexpr __cust_access::_Data data{};
872  inline constexpr __cust_access::_CData cdata{};
873  }
874 
875  /// [range.range] The range concept.
876  template<typename _Tp>
877  concept range = requires(_Tp& __t)
878  {
879  ranges::begin(__t);
880  ranges::end(__t);
881  };
882 
883  /// [range.range] The borrowed_range concept.
884  template<typename _Tp>
885  concept borrowed_range
886  = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
887 
888  template<typename _Tp>
889  using iterator_t = decltype(ranges::begin(std::declval<_Tp&>()));
890 
891  template<range _Range>
892  using sentinel_t = decltype(ranges::end(std::declval<_Range&>()));
893 
894  template<range _Range>
895  using range_difference_t = iter_difference_t<iterator_t<_Range>>;
896 
897  template<range _Range>
898  using range_value_t = iter_value_t<iterator_t<_Range>>;
899 
900  template<range _Range>
901  using range_reference_t = iter_reference_t<iterator_t<_Range>>;
902 
903  template<range _Range>
904  using range_rvalue_reference_t
905  = iter_rvalue_reference_t<iterator_t<_Range>>;
906 
907  /// [range.sized] The sized_range concept.
908  template<typename _Tp>
909  concept sized_range = range<_Tp>
910  && requires(_Tp& __t) { ranges::size(__t); };
911 
912  template<sized_range _Range>
913  using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
914 
915  // [range.refinements]
916 
917  /// A range for which ranges::begin returns an output iterator.
918  template<typename _Range, typename _Tp>
919  concept output_range
920  = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
921 
922  /// A range for which ranges::begin returns an input iterator.
923  template<typename _Tp>
924  concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
925 
926  /// A range for which ranges::begin returns a forward iterator.
927  template<typename _Tp>
928  concept forward_range
929  = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
930 
931  /// A range for which ranges::begin returns a bidirectional iterator.
932  template<typename _Tp>
933  concept bidirectional_range
934  = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
935 
936  /// A range for which ranges::begin returns a random access iterator.
937  template<typename _Tp>
938  concept random_access_range
939  = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
940 
941  /// A range for which ranges::begin returns a contiguous iterator.
942  template<typename _Tp>
943  concept contiguous_range
944  = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
945  && requires(_Tp& __t)
946  {
947  { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
948  };
949 
950  /// A range for which ranges::begin and ranges::end return the same type.
951  template<typename _Tp>
952  concept common_range
953  = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
954 
955  // [range.iter.ops] range iterator operations
956 
957  template<input_or_output_iterator _It>
958  constexpr void
959  advance(_It& __it, iter_difference_t<_It> __n)
960  {
961  if constexpr (random_access_iterator<_It>)
962  __it += __n;
963  else if constexpr (bidirectional_iterator<_It>)
964  {
965  if (__n > 0)
966  {
967  do
968  {
969  ++__it;
970  }
971  while (--__n);
972  }
973  else if (__n < 0)
974  {
975  do
976  {
977  --__it;
978  }
979  while (++__n);
980  }
981  }
982  else
983  {
984 #ifdef __cpp_lib_is_constant_evaluated
985  if (std::is_constant_evaluated() && __n < 0)
986  throw "attempt to decrement a non-bidirectional iterator";
987 #endif
988  __glibcxx_assert(__n >= 0);
989  while (__n-- > 0)
990  ++__it;
991  }
992  }
993 
994  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
995  constexpr void
996  advance(_It& __it, _Sent __bound)
997  {
998  if constexpr (assignable_from<_It&, _Sent>)
999  __it = std::move(__bound);
1000  else if constexpr (sized_sentinel_for<_Sent, _It>)
1001  ranges::advance(__it, __bound - __it);
1002  else
1003  {
1004  while (__it != __bound)
1005  ++__it;
1006  }
1007  }
1008 
1009  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1010  constexpr iter_difference_t<_It>
1011  advance(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
1012  {
1013  if constexpr (sized_sentinel_for<_Sent, _It>)
1014  {
1015  const auto __diff = __bound - __it;
1016 #ifdef __cpp_lib_is_constant_evaluated
1017  if (std::is_constant_evaluated()
1018  && !(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)))
1019  throw "inconsistent directions for distance and bound";
1020 #endif
1021  // n and bound must not lead in opposite directions:
1022  __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
1023  const auto __absdiff = __diff < 0 ? -__diff : __diff;
1024  const auto __absn = __n < 0 ? -__n : __n;;
1025  if (__absn >= __absdiff)
1026  {
1027  ranges::advance(__it, __bound);
1028  return __n - __diff;
1029  }
1030  else
1031  {
1032  ranges::advance(__it, __n);
1033  return 0;
1034  }
1035  }
1036  else if (__it == __bound || __n == 0)
1037  return iter_difference_t<_It>(0);
1038  else if (__n > 0)
1039  {
1040  iter_difference_t<_It> __m = 0;
1041  do
1042  {
1043  ++__it;
1044  ++__m;
1045  }
1046  while (__m != __n && __it != __bound);
1047  return __n - __m;
1048  }
1049  else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
1050  {
1051  iter_difference_t<_It> __m = 0;
1052  do
1053  {
1054  --__it;
1055  --__m;
1056  }
1057  while (__m != __n && __it != __bound);
1058  return __n - __m;
1059  }
1060  else
1061  {
1062 #ifdef __cpp_lib_is_constant_evaluated
1063  if (std::is_constant_evaluated() && __n < 0)
1064  throw "attempt to decrement a non-bidirectional iterator";
1065 #endif
1066  __glibcxx_assert(__n >= 0);
1067  return __n;
1068  }
1069  }
1070 
1071  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1072  constexpr iter_difference_t<_It>
1073  distance(_It __first, _Sent __last)
1074  {
1075  if constexpr (sized_sentinel_for<_Sent, _It>)
1076  return __last - __first;
1077  else
1078  {
1079  iter_difference_t<_It> __n = 0;
1080  while (__first != __last)
1081  {
1082  ++__first;
1083  ++__n;
1084  }
1085  return __n;
1086  }
1087  }
1088 
1089  template<range _Range>
1090  constexpr range_difference_t<_Range>
1091  distance(_Range&& __r)
1092  {
1093  if constexpr (sized_range<_Range>)
1094  return static_cast<range_difference_t<_Range>>(ranges::size(__r));
1095  else
1096  return ranges::distance(ranges::begin(__r), ranges::end(__r));
1097  }
1098 
1099  template<input_or_output_iterator _It>
1100  constexpr _It
1101  next(_It __x)
1102  {
1103  ++__x;
1104  return __x;
1105  }
1106 
1107  template<input_or_output_iterator _It>
1108  constexpr _It
1109  next(_It __x, iter_difference_t<_It> __n)
1110  {
1111  ranges::advance(__x, __n);
1112  return __x;
1113  }
1114 
1115  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1116  constexpr _It
1117  next(_It __x, _Sent __bound)
1118  {
1119  ranges::advance(__x, __bound);
1120  return __x;
1121  }
1122 
1123  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1124  constexpr _It
1125  next(_It __x, iter_difference_t<_It> __n, _Sent __bound)
1126  {
1127  ranges::advance(__x, __n, __bound);
1128  return __x;
1129  }
1130 
1131  template<bidirectional_iterator _It>
1132  constexpr _It
1133  prev(_It __x)
1134  {
1135  --__x;
1136  return __x;
1137  }
1138 
1139  template<bidirectional_iterator _It>
1140  constexpr _It
1141  prev(_It __x, iter_difference_t<_It> __n)
1142  {
1143  ranges::advance(__x, -__n);
1144  return __x;
1145  }
1146 
1147  template<bidirectional_iterator _It>
1148  constexpr _It
1149  prev(_It __x, iter_difference_t<_It> __n, _It __bound)
1150  {
1151  ranges::advance(__x, -__n, __bound);
1152  return __x;
1153  }
1154 
1155 } // namespace ranges
1156 #endif // library concepts
1157 #endif // C++20
1158 _GLIBCXX_END_NAMESPACE_VERSION
1159 } // namespace
1160 
1161 #endif // C++11
1162 
1163 #endif // _GLIBCXX_RANGE_ACCESS_H
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::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::common_type_t
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
Definition: type_traits:2565
std::make_signed_t
typename make_signed< _Tp >::type make_signed_t
Alias template for make_signed.
Definition: type_traits:1964
std
ISO C++ entities toplevel namespace is std.
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::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::remove_reference_t
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1638
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::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:202
initializer_list
std::make_reverse_iterator
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
Definition: bits/stl_iterator.h:451
std::end
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
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
iterator_concepts.h
std::begin
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
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::reverse_iterator
Definition: bits/stl_iterator.h:110
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::initializer_list
initializer_list
Definition: initializer_list:47
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::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
int_limits.h