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