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