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>
38#include <bits/int_limits.h>
39
40namespace 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
341namespace 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
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
Definition: type_traits:2549
typename make_signed< _Tp >::type make_signed_t
Alias template for make_signed.
Definition: type_traits:1948
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
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
constexpr _Tp * begin(_Tp(&__arr)[_Nm])
Return an iterator pointing to the first element of the array.
Definition: range_access.h:90
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
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr _Tp * end(_Tp(&__arr)[_Nm])
Return an iterator pointing to one past the last element of the array.
Definition: range_access.h:100
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
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
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
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
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
initializer_list