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