1 // <ranges> -*- C++ -*-
3 // Copyright (C) 2019-2020 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file include/ranges
26 * This is a Standard C++ Library header.
30 #ifndef _GLIBCXX_RANGES
31 #define _GLIBCXX_RANGES 1
33 #if __cplusplus > 201703L
35 #pragma GCC system_header
39 #if __cpp_lib_concepts
41 #include <bits/refwrap.h>
43 #include <initializer_list>
50 * @defgroup ranges Ranges
52 * Components for dealing with ranges of elements.
55 namespace std _GLIBCXX_VISIBILITY(default)
57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
60 // [range.range] The range concept.
61 // [range.sized] The sized_range concept.
62 // Defined in <bits/range_access.h>
64 // [range.refinements]
65 // Defined in <bits/range_access.h>
71 template<typename _Tp>
72 concept __deep_const_range = range<_Tp> && range<const _Tp>
73 && same_as<range_reference_t<_Tp>, range_reference_t<const _Tp>>;
75 template<typename _Tp>
76 inline constexpr bool __enable_view_impl
77 = derived_from<_Tp, view_base> || (!__deep_const_range<_Tp>);
79 template<typename _Tp>
80 inline constexpr bool __enable_view_impl<std::initializer_list<_Tp>>
83 } // namespace __detail
85 template<typename _Tp>
86 inline constexpr bool enable_view
87 = __detail::__enable_view_impl<remove_cv_t<_Tp>>;
89 template<typename _Tp>
91 = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
94 /// A range which can be safely converted to a view.
95 template<typename _Tp>
96 concept viewable_range = range<_Tp>
97 && (safe_range<_Tp> || view<remove_cvref_t<_Tp>>);
101 template<typename _Range>
102 concept __simple_view = view<_Range> && range<const _Range>
103 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
104 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
106 template<typename _It>
107 concept __has_arrow = input_iterator<_It>
108 && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
110 template<typename _Tp, typename _Up>
111 concept __not_same_as
112 = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
113 } // namespace __detail
115 template<typename _Derived>
116 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
117 class view_interface : public view_base
120 constexpr _Derived& _M_derived() noexcept
122 static_assert(derived_from<_Derived, view_interface<_Derived>>);
123 static_assert(view<_Derived>);
124 return static_cast<_Derived&>(*this);
127 constexpr const _Derived& _M_derived() const noexcept
129 static_assert(derived_from<_Derived, view_interface<_Derived>>);
130 static_assert(view<_Derived>);
131 return static_cast<const _Derived&>(*this);
136 empty() requires forward_range<_Derived>
137 { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
140 empty() const requires forward_range<const _Derived>
141 { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
144 operator bool() requires requires { ranges::empty(_M_derived()); }
145 { return !ranges::empty(_M_derived()); }
148 operator bool() const requires requires { ranges::empty(_M_derived()); }
149 { return !ranges::empty(_M_derived()); }
152 data() requires contiguous_iterator<iterator_t<_Derived>>
153 { return to_address(ranges::begin(_M_derived())); }
157 requires range<const _Derived>
158 && contiguous_iterator<iterator_t<const _Derived>>
159 { return to_address(ranges::begin(_M_derived())); }
163 requires forward_range<_Derived>
164 && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
165 { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
169 requires forward_range<const _Derived>
170 && sized_sentinel_for<sentinel_t<const _Derived>,
171 iterator_t<const _Derived>>
172 { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
174 constexpr decltype(auto)
175 front() requires forward_range<_Derived>
177 __glibcxx_assert(!empty());
178 return *ranges::begin(_M_derived());
181 constexpr decltype(auto)
182 front() const requires forward_range<const _Derived>
184 __glibcxx_assert(!empty());
185 return *ranges::begin(_M_derived());
188 constexpr decltype(auto)
190 requires bidirectional_range<_Derived> && common_range<_Derived>
192 __glibcxx_assert(!empty());
193 return *ranges::prev(ranges::end(_M_derived()));
196 constexpr decltype(auto)
198 requires bidirectional_range<const _Derived>
199 && common_range<const _Derived>
201 __glibcxx_assert(!empty());
202 return *ranges::prev(ranges::end(_M_derived()));
205 template<random_access_range _Range = _Derived>
206 constexpr decltype(auto)
207 operator[](range_difference_t<_Range> __n)
208 { return ranges::begin(_M_derived())[__n]; }
210 template<random_access_range _Range = const _Derived>
211 constexpr decltype(auto)
212 operator[](range_difference_t<_Range> __n) const
213 { return ranges::begin(_M_derived())[__n]; }
218 template<typename _Tp>
220 = !is_reference_v<_Tp> && requires(_Tp __t)
222 typename tuple_size<_Tp>::type;
223 requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
224 typename tuple_element_t<0, remove_const_t<_Tp>>;
225 typename tuple_element_t<1, remove_const_t<_Tp>>;
226 { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
227 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
230 template<typename _Tp, typename _Up, typename _Vp>
231 concept __pair_like_convertible_to
232 = !range<_Tp> && __pair_like<remove_reference_t<_Tp>>
233 && requires(_Tp&& __t)
235 { get<0>(std::forward<_Tp>(__t)) } -> convertible_to<_Up>;
236 { get<1>(std::forward<_Tp>(__t)) } -> convertible_to<_Vp>;
239 template<typename _Tp, typename _Up, typename _Vp>
240 concept __pair_like_convertible_from
241 = !range<_Tp> && __pair_like<_Tp>
242 && constructible_from<_Tp, _Up, _Vp>;
244 template<typename _Tp>
245 concept __iterator_sentinel_pair
246 = !range<_Tp> && __pair_like<_Tp>
247 && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
249 } // namespace __detail
251 enum class subrange_kind : bool { unsized, sized };
253 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
254 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
255 ? subrange_kind::sized : subrange_kind::unsized>
256 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
257 class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
260 // XXX: gcc complains when using constexpr here
261 static const bool _S_store_size
262 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
264 _It _M_begin = _It();
265 _Sent _M_end = _Sent();
267 template<typename, bool = _S_store_size>
271 template<typename _Tp>
272 struct _Size<_Tp, true>
273 { __detail::__make_unsigned_like_t<_Tp> _M_size; };
275 [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
278 subrange() = default;
281 subrange(_It __i, _Sent __s) requires (!_S_store_size)
282 : _M_begin(std::move(__i)), _M_end(__s)
286 subrange(_It __i, _Sent __s,
287 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
288 requires (_Kind == subrange_kind::sized)
289 : _M_begin(std::move(__i)), _M_end(__s)
291 using __detail::__to_unsigned_like;
292 __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
293 if constexpr (_S_store_size)
294 _M_size._M_size = __n;
297 template<__detail::__not_same_as<subrange> _Rng>
298 requires safe_range<_Rng>
299 && convertible_to<iterator_t<_Rng>, _It>
300 && convertible_to<sentinel_t<_Rng>, _Sent>
302 subrange(_Rng&& __r) requires (!_S_store_size || sized_range<_Rng>)
303 : subrange{ranges::begin(__r), ranges::end(__r)}
305 if constexpr (_S_store_size)
306 _M_size._M_size = ranges::size(__r);
309 template<safe_range _Rng>
310 requires convertible_to<iterator_t<_Rng>, _It>
311 && convertible_to<sentinel_t<_Rng>, _Sent>
314 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
315 requires (_Kind == subrange_kind::sized)
316 : subrange{ranges::begin(__r), ranges::end(__r), __n}
319 template<__detail::__not_same_as<subrange> _PairLike>
320 requires __detail::__pair_like_convertible_to<_PairLike, _It, _Sent>
322 subrange(_PairLike&& __r) requires (!_S_store_size)
323 : subrange{std::get<0>(std::forward<_PairLike>(__r)),
324 std::get<1>(std::forward<_PairLike>(__r))}
327 template<__detail::__pair_like_convertible_to<_It, _Sent> _PairLike>
329 subrange(_PairLike&& __r,
330 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
331 requires (_Kind == subrange_kind::sized)
332 : subrange{std::get<0>(std::forward<_PairLike>(__r)),
333 std::get<1>(std::forward<_PairLike>(__r)), __n}
336 template<__detail::__not_same_as<subrange> _PairLike>
337 requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
340 operator _PairLike() const
341 { return _PairLike(_M_begin, _M_end); }
344 begin() const requires copyable<_It>
347 [[nodiscard]] constexpr _It
348 begin() requires (!copyable<_It>)
349 { return std::move(_M_begin); }
351 constexpr _Sent end() const { return _M_end; }
353 constexpr bool empty() const { return _M_begin == _M_end; }
355 constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
356 size() const requires (_Kind == subrange_kind::sized)
358 if constexpr (_S_store_size)
359 return _M_size._M_size;
361 return __detail::__to_unsigned_like(_M_end - _M_begin);
364 [[nodiscard]] constexpr subrange
365 next(iter_difference_t<_It> __n = 1) const &
366 requires forward_iterator<_It>
373 [[nodiscard]] constexpr subrange
374 next(iter_difference_t<_It> __n = 1) &&
377 return std::move(*this);
380 [[nodiscard]] constexpr subrange
381 prev(iter_difference_t<_It> __n = 1) const
382 requires bidirectional_iterator<_It>
385 __tmp.advance(--__n);
390 advance(iter_difference_t<_It> __n)
392 if constexpr (_S_store_size)
394 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
396 _M_size._M_size -= __detail::__to_unsigned_like(__d);
398 _M_size._M_size += __detail::__to_unsigned_like(-__d);
401 ranges::advance(_M_begin, __n, _M_end);
406 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
408 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
409 -> subrange<_It, _Sent, subrange_kind::sized>;
411 template<__detail::__iterator_sentinel_pair _Pr>
413 -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
415 template<__detail::__iterator_sentinel_pair _Pr>
416 subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
417 tuple_element_t<0, _Pr>>>)
418 -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
419 subrange_kind::sized>;
421 template<safe_range _Rng>
423 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
425 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
426 ? subrange_kind::sized : subrange_kind::unsized>;
428 template<safe_range _Rng>
430 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
431 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
433 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
436 get(const subrange<_It, _Sent, _Kind>& __r)
438 if constexpr (_Num == 0)
444 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
447 get(subrange<_It, _Sent, _Kind>&& __r)
449 if constexpr (_Num == 0)
455 template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
457 inline constexpr bool
458 enable_safe_range<subrange<_It, _Sent, _Kind>> = true;
460 } // namespace ranges
466 /// Type returned by algorithms instead of a dangling iterator or subrange.
469 constexpr dangling() noexcept = default;
470 template<typename... _Args>
471 constexpr dangling(_Args&&...) noexcept { }
474 template<range _Range>
475 using safe_iterator_t = conditional_t<safe_range<_Range>,
479 template<range _Range>
480 using safe_subrange_t = conditional_t<safe_range<_Range>,
481 subrange<iterator_t<_Range>>,
484 template<typename _Tp> requires is_object_v<_Tp>
486 : public view_interface<empty_view<_Tp>>
489 static constexpr _Tp* begin() noexcept { return nullptr; }
490 static constexpr _Tp* end() noexcept { return nullptr; }
491 static constexpr _Tp* data() noexcept { return nullptr; }
492 static constexpr size_t size() noexcept { return 0; }
493 static constexpr bool empty() noexcept { return true; }
496 template<typename _Tp>
497 inline constexpr bool enable_safe_range<empty_view<_Tp>> = true;
501 template<copy_constructible _Tp> requires is_object_v<_Tp>
502 struct __box : std::optional<_Tp>
504 using std::optional<_Tp>::optional;
508 noexcept(is_nothrow_default_constructible_v<_Tp>)
509 requires default_initializable<_Tp>
510 : std::optional<_Tp>{std::in_place}
513 __box(const __box&) = default;
514 __box(__box&&) = default;
516 using std::optional<_Tp>::operator=;
519 operator=(const __box& __that)
520 noexcept(is_nothrow_copy_constructible_v<_Tp>)
521 requires (!assignable_from<_Tp&, const _Tp&>)
524 this->emplace(*__that);
531 operator=(__box&& __that)
532 noexcept(is_nothrow_move_constructible_v<_Tp>)
533 requires (!assignable_from<_Tp&, _Tp>)
536 this->emplace(std::move(*__that));
543 } // namespace __detail
545 /// A view that contains exactly one element.
546 template<copy_constructible _Tp> requires is_object_v<_Tp>
547 class single_view : public view_interface<single_view<_Tp>>
550 single_view() = default;
553 single_view(const _Tp& __t)
558 single_view(_Tp&& __t)
559 : _M_value(std::move(__t))
562 template<typename... _Args>
563 requires constructible_from<_Tp, _Args...>
565 single_view(in_place_t, _Args&&... __args)
566 : _M_value{in_place, std::forward<_Args>(__args)...}
574 begin() const noexcept
579 { return data() + 1; }
583 { return data() + 1; }
585 static constexpr size_t
591 { return _M_value.operator->(); }
594 data() const noexcept
595 { return _M_value.operator->(); }
598 __detail::__box<_Tp> _M_value;
603 template<typename _Wp>
604 constexpr auto __to_signed_like(_Wp __w) noexcept
606 if constexpr (!integral<_Wp>)
607 return iter_difference_t<_Wp>();
608 else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
609 return iter_difference_t<_Wp>(__w);
610 else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
611 return ptrdiff_t(__w);
612 else if constexpr (sizeof(long long) > sizeof(_Wp))
613 return (long long)(__w);
614 #ifdef __SIZEOF_INT128__
615 else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
616 return __int128(__w);
619 return __max_diff_type(__w);
622 template<typename _Wp>
623 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
625 template<typename _It>
626 concept __decrementable = incrementable<_It>
629 { --__i } -> same_as<_It&>;
630 { __i-- } -> same_as<_It>;
633 template<typename _It>
634 concept __advanceable = __decrementable<_It> && totally_ordered<_It>
635 && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
637 { __i += __n } -> same_as<_It&>;
638 { __i -= __n } -> same_as<_It&>;
642 { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
645 } // namespace __detail
647 template<weakly_incrementable _Winc,
648 semiregular _Bound = unreachable_sentinel_t>
649 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
650 class iota_view : public view_interface<iota_view<_Winc, _Bound>>
659 using namespace __detail;
660 if constexpr (__advanceable<_Winc>)
661 return random_access_iterator_tag{};
662 else if constexpr (__decrementable<_Winc>)
663 return bidirectional_iterator_tag{};
664 else if constexpr (incrementable<_Winc>)
665 return forward_iterator_tag{};
667 return input_iterator_tag{};
671 using iterator_category = decltype(_S_iter_cat());
672 using value_type = _Winc;
673 using difference_type = __detail::__iota_diff_t<_Winc>;
675 _Iterator() = default;
678 _Iterator(_Winc __value)
679 : _M_value(__value) { }
682 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
697 operator++(int) requires incrementable<_Winc>
705 operator--() requires __detail::__decrementable<_Winc>
712 operator--(int) requires __detail::__decrementable<_Winc>
720 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
722 using __detail::__is_integer_like;
723 using __detail::__is_signed_integer_like;
724 if constexpr (__is_integer_like<_Winc>
725 && !__is_signed_integer_like<_Winc>)
727 if (__n >= difference_type(0))
728 _M_value += static_cast<_Winc>(__n);
730 _M_value -= static_cast<_Winc>(-__n);
738 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
740 using __detail::__is_integer_like;
741 using __detail::__is_signed_integer_like;
742 if constexpr (__is_integer_like<_Winc>
743 && !__is_signed_integer_like<_Winc>)
745 if (__n >= difference_type(0))
746 _M_value -= static_cast<_Winc>(__n);
748 _M_value += static_cast<_Winc>(-__n);
756 operator[](difference_type __n) const
757 requires __detail::__advanceable<_Winc>
758 { return _Winc(_M_value + __n); }
760 friend constexpr bool
761 operator==(const _Iterator& __x, const _Iterator& __y)
762 requires equality_comparable<_Winc>
763 { return __x._M_value == __y._M_value; }
765 friend constexpr bool
766 operator<(const _Iterator& __x, const _Iterator& __y)
767 requires totally_ordered<_Winc>
768 { return __x._M_value < __y._M_value; }
770 friend constexpr bool
771 operator>(const _Iterator& __x, const _Iterator& __y)
772 requires totally_ordered<_Winc>
773 { return __y < __x; }
775 friend constexpr bool
776 operator<=(const _Iterator& __x, const _Iterator& __y)
777 requires totally_ordered<_Winc>
778 { return !(__y < __x); }
780 friend constexpr bool
781 operator>=(const _Iterator& __x, const _Iterator& __y)
782 requires totally_ordered<_Winc>
783 { return !(__x < __y); }
785 #ifdef __cpp_lib_three_way_comparison
786 friend constexpr auto
787 operator<=>(const _Iterator& __x, const _Iterator& __y)
788 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
789 { return __x._M_value <=> __y._M_value; }
792 friend constexpr _Iterator
793 operator+(_Iterator __i, difference_type __n)
794 requires __detail::__advanceable<_Winc>
795 { return __i += __n; }
797 friend constexpr _Iterator
798 operator+(difference_type __n, _Iterator __i)
799 requires __detail::__advanceable<_Winc>
800 { return __i += __n; }
802 friend constexpr _Iterator
803 operator-(_Iterator __i, difference_type __n)
804 requires __detail::__advanceable<_Winc>
805 { return __i -= __n; }
807 friend constexpr difference_type
808 operator-(const _Iterator& __x, const _Iterator& __y)
809 requires __detail::__advanceable<_Winc>
811 using __detail::__is_integer_like;
812 using __detail::__is_signed_integer_like;
813 using _Dt = difference_type;
814 if constexpr (__is_integer_like<_Winc>)
816 if constexpr (__is_signed_integer_like<_Winc>)
817 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
819 return (__y._M_value > __x._M_value)
820 ? _Dt(-_Dt(__y._M_value - __x._M_value))
821 : _Dt(__x._M_value - __y._M_value);
824 return __x._M_value - __y._M_value;
828 _Winc _M_value = _Winc();
834 _Bound _M_bound = _Bound();
837 _Sentinel() = default;
840 _Sentinel(_Bound __bound)
841 : _M_bound(__bound) { }
843 friend constexpr bool
844 operator==(const _Iterator& __x, const _Sentinel& __y)
845 { return __x._M_value == __y._M_bound; }
847 friend constexpr iter_difference_t<_Winc>
848 operator-(const _Iterator& __x, const _Sentinel& __y)
849 requires sized_sentinel_for<_Bound, _Winc>
850 { return __x._M_value - __y._M_bound; }
852 friend constexpr iter_difference_t<_Winc>
853 operator-(const _Sentinel& __x, const _Iterator& __y)
854 requires sized_sentinel_for<_Bound, _Winc>
855 { return -(__y - __x); }
858 _Winc _M_value = _Winc();
859 _Bound _M_bound = _Bound();
862 iota_view() = default;
865 iota_view(_Winc __value)
870 iota_view(type_identity_t<_Winc> __value,
871 type_identity_t<_Bound> __bound)
872 : _M_value(__value), _M_bound(__bound)
874 if constexpr (totally_ordered_with<_Winc, _Bound>)
876 __glibcxx_assert( bool(__value <= __bound) );
881 begin() const { return _Iterator{_M_value}; }
886 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
887 return unreachable_sentinel;
889 return _Sentinel{_M_bound};
893 end() const requires same_as<_Winc, _Bound>
894 { return _Iterator{_M_bound}; }
898 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
899 || (integral<_Winc> && integral<_Bound>)
900 || sized_sentinel_for<_Bound, _Winc>
902 using __detail::__is_integer_like;
903 using __detail::__to_unsigned_like;
904 if constexpr (__is_integer_like<_Winc> && __is_integer_like<_Bound>)
905 return (_M_value < 0)
907 ? __to_unsigned_like(-_M_value) - __to_unsigned_like(-_M_bound)
908 : __to_unsigned_like(_M_bound) + __to_unsigned_like(-_M_value))
909 : __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
911 return __to_unsigned_like(_M_bound - _M_value);
915 template<typename _Winc, typename _Bound>
916 requires (!__detail::__is_integer_like<_Winc>
917 || !__detail::__is_integer_like<_Bound>
918 || (__detail::__is_signed_integer_like<_Winc>
919 == __detail::__is_signed_integer_like<_Bound>))
920 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
922 template<weakly_incrementable _Winc, semiregular _Bound>
923 inline constexpr bool enable_safe_range<iota_view<_Winc, _Bound>> = true;
927 template<typename _Tp>
928 inline constexpr empty_view<_Tp> empty{};
932 template<typename _Tp>
934 operator()(_Tp&& __e) const
935 { return single_view{std::forward<_Tp>(__e)}; }
938 inline constexpr _Single single{};
942 template<typename _Tp>
944 operator()(_Tp&& __e) const
945 { return iota_view{std::forward<_Tp>(__e)}; }
947 template<typename _Tp, typename _Up>
949 operator()(_Tp&& __e, _Up&& __f) const
950 { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; }
953 inline constexpr _Iota iota{};
958 template<typename _Val, typename _CharT, typename _Traits>
959 concept __stream_extractable
960 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
961 } // namespace __detail
963 template<movable _Val, typename _CharT, typename _Traits>
964 requires default_initializable<_Val>
965 && __detail::__stream_extractable<_Val, _CharT, _Traits>
966 class basic_istream_view
967 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
970 basic_istream_view() = default;
973 basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
974 : _M_stream(std::__addressof(__stream))
980 if (_M_stream != nullptr)
981 *_M_stream >> _M_object;
982 return _Iterator{*this};
985 constexpr default_sentinel_t
987 { return default_sentinel; }
990 basic_istream<_CharT, _Traits>* _M_stream = nullptr;
991 _Val _M_object = _Val();
996 using iterator_category = input_iterator_tag;
997 using difference_type = ptrdiff_t;
998 using value_type = _Val;
1000 _Iterator() = default;
1003 _Iterator(basic_istream_view& __parent) noexcept
1004 : _M_parent(std::__addressof(__parent))
1007 _Iterator(const _Iterator&) = delete;
1008 _Iterator(_Iterator&&) = default;
1009 _Iterator& operator=(const _Iterator&) = delete;
1010 _Iterator& operator=(_Iterator&&) = default;
1015 __glibcxx_assert(_M_parent->_M_stream != nullptr);
1016 *_M_parent->_M_stream >> _M_parent->_M_object;
1027 __glibcxx_assert(_M_parent->_M_stream != nullptr);
1028 return _M_parent->_M_object;
1032 operator==(const _Iterator& __x, default_sentinel_t)
1033 { return __x._M_at_end(); }
1036 basic_istream_view* _M_parent = nullptr;
1040 { return _M_parent == nullptr || !*_M_parent->_M_stream; }
1046 template<typename _Val, typename _CharT, typename _Traits>
1047 basic_istream_view<_Val, _CharT, _Traits>
1048 istream_view(basic_istream<_CharT, _Traits>& __s)
1049 { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
1054 } // namespace __detail
1060 template<typename _Callable>
1061 struct _RangeAdaptorClosure;
1063 template<typename _Callable>
1064 struct _RangeAdaptor
1067 [[no_unique_address]]
1068 conditional_t<!is_default_constructible_v<_Callable>,
1069 _Callable, __detail::_Empty> _M_callable;
1073 _RangeAdaptor(const _Callable& = {})
1074 requires is_default_constructible_v<_Callable>
1078 _RangeAdaptor(_Callable __callable)
1079 requires (!is_default_constructible_v<_Callable>)
1080 : _M_callable(std::move(__callable))
1083 template<typename... _Args>
1084 requires (sizeof...(_Args) >= 1)
1086 operator()(_Args&&... __args) const
1088 if constexpr (is_invocable_v<_Callable, _Args...>)
1090 static_assert(sizeof...(_Args) != 1,
1091 "a _RangeAdaptor that accepts only one argument "
1092 "should be defined as a _RangeAdaptorClosure");
1093 return _Callable{}(std::forward<_Args>(__args)...);
1097 auto __closure = [__args...] <typename _Range> (_Range&& __r) {
1098 return _Callable{}(std::forward<_Range>(__r), __args...);
1100 using _ClosureType = decltype(__closure);
1101 return _RangeAdaptorClosure<_ClosureType>(std::move(__closure));
1106 template<typename _Callable>
1107 struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable>
1109 using _RangeAdaptor<_Callable>::_RangeAdaptor;
1111 template<viewable_range _Range>
1112 requires requires { declval<_Callable>()(declval<_Range>()); }
1114 operator()(_Range&& __r) const
1116 if constexpr (is_default_constructible_v<_Callable>)
1117 return _Callable{}(std::forward<_Range>(__r));
1119 return this->_M_callable(std::forward<_Range>(__r));
1122 template<viewable_range _Range>
1123 requires requires { declval<_Callable>()(declval<_Range>()); }
1124 friend constexpr auto
1125 operator|(_Range&& __r, const _RangeAdaptorClosure& __o)
1126 { return __o(std::forward<_Range>(__r)); }
1128 template<typename _Tp>
1129 friend constexpr auto
1130 operator|(const _RangeAdaptorClosure<_Tp>& __x,
1131 const _RangeAdaptorClosure& __y)
1133 if constexpr (is_default_constructible_v<_Tp>
1134 && is_default_constructible_v<_Callable>)
1136 auto __closure = [] <typename _Up> (_Up&& __e) {
1137 return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){};
1139 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1141 else if constexpr (is_default_constructible_v<_Tp>
1142 && !is_default_constructible_v<_Callable>)
1144 auto __closure = [__y] <typename _Up> (_Up&& __e) {
1145 return std::forward<_Up>(__e) | decltype(__x){} | __y;
1147 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1149 else if constexpr (!is_default_constructible_v<_Tp>
1150 && is_default_constructible_v<_Callable>)
1152 auto __closure = [__x] <typename _Up> (_Up&& __e) {
1153 return std::forward<_Up>(__e) | __x | decltype(__y){};
1155 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1159 auto __closure = [__x, __y] <typename _Up> (_Up&& __e) {
1160 return std::forward<_Up>(__e) | __x | __y;
1162 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
1167 template<typename _Callable>
1168 _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>;
1169 } // namespace __adaptor
1170 } // namespace views
1172 template<range _Range> requires is_object_v<_Range>
1173 class ref_view : public view_interface<ref_view<_Range>>
1176 _Range* _M_r = nullptr;
1178 static void _S_fun(_Range&); // not defined
1179 static void _S_fun(_Range&&) = delete;
1183 ref_view() noexcept = default;
1185 template<__detail::__not_same_as<ref_view> _Tp>
1186 requires convertible_to<_Tp, _Range&>
1187 && requires { _S_fun(declval<_Tp>()); }
1190 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
1197 constexpr iterator_t<_Range>
1199 { return ranges::begin(*_M_r); }
1201 constexpr sentinel_t<_Range>
1203 { return ranges::end(*_M_r); }
1206 empty() const requires requires { ranges::empty(*_M_r); }
1207 { return ranges::empty(*_M_r); }
1210 size() const requires sized_range<_Range>
1211 { return ranges::size(*_M_r); }
1214 data() const requires contiguous_range<_Range>
1215 { return ranges::data(*_M_r); }
1218 template<typename _Range>
1219 ref_view(_Range&) -> ref_view<_Range>;
1221 template<typename _Tp>
1222 inline constexpr bool enable_safe_range<ref_view<_Tp>> = true;
1226 inline constexpr __adaptor::_RangeAdaptorClosure all
1227 = [] <viewable_range _Range> (_Range&& __r)
1229 if constexpr (view<decay_t<_Range>>)
1230 return std::forward<_Range>(__r);
1231 else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; })
1232 return ref_view{std::forward<_Range>(__r)};
1234 return subrange{std::forward<_Range>(__r)};
1236 } // namespace views
1238 template<viewable_range _Range>
1239 using all_view = decltype(views::all(declval<_Range>()));
1241 // XXX: the following algos are copied from ranges_algo.h to avoid a circular
1242 // dependency with that header.
1245 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1246 typename _Proj = identity,
1247 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1249 find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
1251 while (__first != __last
1252 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
1257 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1258 typename _Proj = identity,
1259 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1261 find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
1263 while (__first != __last
1264 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
1269 template<typename _Tp, typename _Proj = identity,
1270 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
1271 _Comp = ranges::less>
1272 constexpr const _Tp&
1273 min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
1275 if (std::__invoke(std::move(__comp),
1276 std::__invoke(__proj, __b),
1277 std::__invoke(__proj, __a)))
1283 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1284 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1285 typename _Pred = ranges::equal_to,
1286 typename _Proj1 = identity, typename _Proj2 = identity>
1287 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
1288 constexpr pair<_Iter1, _Iter2>
1289 mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
1290 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
1292 while (__first1 != __last1 && __first2 != __last2
1293 && (bool)std::__invoke(__pred,
1294 std::__invoke(__proj1, *__first1),
1295 std::__invoke(__proj2, *__first2)))
1300 return { std::move(__first1), std::move(__first2) };
1302 } // namespace __detail
1304 template<input_range _Vp,
1305 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1306 requires view<_Vp> && is_object_v<_Pred>
1307 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1315 static constexpr auto
1318 if constexpr (bidirectional_range<_Vp>)
1319 return bidirectional_iterator_tag{};
1320 else if constexpr (forward_range<_Vp>)
1321 return forward_iterator_tag{};
1323 return input_iterator_tag{};
1326 static constexpr auto
1329 using _Cat = iterator_traits<iterator_t<_Vp>>::iterator_category;
1330 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1331 return bidirectional_iterator_tag{};
1332 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1333 return forward_iterator_tag{};
1340 iterator_t<_Vp> _M_current = iterator_t<_Vp>();
1341 filter_view* _M_parent = nullptr;
1344 using iterator_concept = decltype(_S_iter_concept());
1345 using iterator_category = decltype(_S_iter_cat());
1346 using value_type = range_value_t<_Vp>;
1347 using difference_type = range_difference_t<_Vp>;
1349 _Iterator() = default;
1352 _Iterator(filter_view& __parent, iterator_t<_Vp> __current)
1353 : _M_current(std::move(__current)),
1354 _M_parent(std::__addressof(__parent))
1357 constexpr iterator_t<_Vp>
1359 requires copyable<iterator_t<_Vp>>
1360 { return _M_current; }
1362 constexpr iterator_t<_Vp>
1364 { return std::move(_M_current); }
1366 constexpr range_reference_t<_Vp>
1368 { return *_M_current; }
1370 constexpr iterator_t<_Vp>
1372 requires __detail::__has_arrow<iterator_t<_Vp>>
1373 && copyable<iterator_t<_Vp>>
1374 { return _M_current; }
1376 constexpr _Iterator&
1379 _M_current = __detail::find_if(std::move(++_M_current),
1380 ranges::end(_M_parent->_M_base),
1381 std::ref(*_M_parent->_M_pred));
1390 operator++(int) requires forward_range<_Vp>
1397 constexpr _Iterator&
1398 operator--() requires bidirectional_range<_Vp>
1402 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1407 operator--(int) requires bidirectional_range<_Vp>
1414 friend constexpr bool
1415 operator==(const _Iterator& __x, const _Iterator& __y)
1416 requires equality_comparable<iterator_t<_Vp>>
1417 { return __x._M_current == __y._M_current; }
1419 friend constexpr range_rvalue_reference_t<_Vp>
1420 iter_move(const _Iterator& __i)
1421 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1422 { return ranges::iter_move(__i._M_current); }
1424 friend constexpr void
1425 iter_swap(const _Iterator& __x, const _Iterator& __y)
1426 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1427 requires indirectly_swappable<iterator_t<_Vp>>
1428 { ranges::iter_swap(__x._M_current, __y._M_current); }
1434 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1437 __equal(const _Iterator& __i) const
1438 { return __i._M_current == _M_end; }
1441 _Sentinel() = default;
1444 _Sentinel(filter_view& __parent)
1445 : _M_end(ranges::end(__parent._M_base))
1448 constexpr sentinel_t<_Vp>
1452 friend constexpr bool
1453 operator==(const _Iterator& __x, const _Sentinel& __y)
1454 { return __y.__equal(__x); }
1457 _Vp _M_base = _Vp();
1458 __detail::__box<_Pred> _M_pred;
1461 filter_view() = default;
1464 filter_view(_Vp __base, _Pred __pred)
1465 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
1468 /* XXX: P3280 removes this constructor
1469 template<input_range _Range>
1470 requires viewable_range<_Range>
1471 && constructible_from<_Vp, all_view<_Range>>
1473 filter_view(_Range&& __r, _Pred __pred)
1474 : _M_base(views::all(std::forward<_Range>(__r))),
1475 _M_pred(std::move(__pred))
1480 base() const& requires copy_constructible<_Vp>
1485 { return std::move(_M_base); }
1490 // XXX: we need to cache the result here as per [range.filter.view]
1491 __glibcxx_assert(_M_pred.has_value());
1492 return {*this, __detail::find_if(ranges::begin(_M_base),
1493 ranges::end(_M_base),
1494 std::ref(*_M_pred))};
1500 if constexpr (common_range<_Vp>)
1501 return _Iterator{*this, ranges::end(_M_base)};
1503 return _Sentinel{*this};
1507 template<typename _Range, typename _Pred>
1508 filter_view(_Range&&, _Pred) -> filter_view<all_view<_Range>, _Pred>;
1512 inline constexpr __adaptor::_RangeAdaptor filter
1513 = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
1515 return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1517 } // namespace views
1519 template<input_range _Vp, copy_constructible _Fp>
1520 requires view<_Vp> && is_object_v<_Fp>
1521 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1522 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1525 template<bool _Const>
1528 template<bool _Const>
1533 = conditional_t<_Const, const transform_view, transform_view>;
1534 using _Base = conditional_t<_Const, const _Vp, _Vp>;
1536 static constexpr auto
1539 if constexpr (random_access_range<_Vp>)
1540 return random_access_iterator_tag{};
1541 else if constexpr (bidirectional_range<_Vp>)
1542 return bidirectional_iterator_tag{};
1543 else if constexpr (forward_range<_Vp>)
1544 return forward_iterator_tag{};
1546 return input_iterator_tag{};
1549 static constexpr auto
1552 using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category;
1553 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1554 return random_access_iterator_tag{};
1559 static constexpr decltype(auto)
1560 __iter_move(const _Iterator& __i = {})
1561 noexcept(noexcept(std::__invoke(*__i._M_parent->_M_fun,
1564 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1565 return std::move(*__i);
1570 iterator_t<_Base> _M_current = iterator_t<_Base>();
1571 _Parent* _M_parent = nullptr;
1574 using iterator_concept = decltype(_S_iter_concept());
1575 using iterator_category = decltype(_S_iter_cat());
1577 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1578 using difference_type = range_difference_t<_Base>;
1580 _Iterator() = default;
1583 _Iterator(_Parent& __parent, iterator_t<_Base> __current)
1584 : _M_current(std::move(__current)),
1585 _M_parent(std::__addressof(__parent))
1589 _Iterator(_Iterator<!_Const> __i)
1591 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
1592 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1595 constexpr iterator_t<_Base>
1597 requires copyable<iterator_t<_Base>>
1598 { return _M_current; }
1600 constexpr iterator_t<_Base>
1602 { return std::move(_M_current); }
1604 constexpr decltype(auto)
1606 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1608 constexpr _Iterator&
1620 operator++(int) requires forward_range<_Base>
1627 constexpr _Iterator&
1628 operator--() requires bidirectional_range<_Base>
1635 operator--(int) requires bidirectional_range<_Base>
1642 constexpr _Iterator&
1643 operator+=(difference_type __n) requires random_access_range<_Base>
1649 constexpr _Iterator&
1650 operator-=(difference_type __n) requires random_access_range<_Base>
1656 constexpr decltype(auto)
1657 operator[](difference_type __n) const
1658 requires random_access_range<_Base>
1659 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1661 friend constexpr bool
1662 operator==(const _Iterator& __x, const _Iterator& __y)
1663 requires equality_comparable<iterator_t<_Base>>
1664 { return __x._M_current == __y._M_current; }
1666 friend constexpr bool
1667 operator<(const _Iterator& __x, const _Iterator& __y)
1668 requires random_access_range<_Base>
1669 { return __x._M_current < __y._M_current; }
1671 friend constexpr bool
1672 operator>(const _Iterator& __x, const _Iterator& __y)
1673 requires random_access_range<_Base>
1674 { return __y < __x; }
1676 friend constexpr bool
1677 operator<=(const _Iterator& __x, const _Iterator& __y)
1678 requires random_access_range<_Base>
1679 { return !(__y < __x); }
1681 friend constexpr bool
1682 operator>=(const _Iterator& __x, const _Iterator& __y)
1683 requires random_access_range<_Base>
1684 { return !(__x < __y); }
1686 #ifdef __cpp_lib_three_way_comparison
1687 friend constexpr auto
1688 operator<=>(const _Iterator& __x, const _Iterator& __y)
1689 requires random_access_range<_Base>
1690 && three_way_comparable<iterator_t<_Base>>
1691 { return __x._M_current <=> __y._M_current; }
1694 friend constexpr _Iterator
1695 operator+(_Iterator __i, difference_type __n)
1696 requires random_access_range<_Base>
1697 { return {*__i._M_parent, __i._M_current + __n}; }
1699 friend constexpr _Iterator
1700 operator+(difference_type __n, _Iterator __i)
1701 requires random_access_range<_Base>
1702 { return {*__i._M_parent, __i._M_current + __n}; }
1704 friend constexpr _Iterator
1705 operator-(_Iterator __i, difference_type __n)
1706 requires random_access_range<_Base>
1707 { return {*__i._M_parent, __i._M_current - __n}; }
1709 friend constexpr difference_type
1710 operator-(const _Iterator& __x, const _Iterator& __y)
1711 requires random_access_range<_Base>
1712 { return __x._M_current - __y._M_current; }
1714 friend constexpr decltype(auto)
1715 iter_move(const _Iterator& __i) noexcept(noexcept(__iter_move()))
1716 { return __iter_move(__i); }
1718 friend constexpr void
1719 iter_swap(const _Iterator& __x, const _Iterator& __y)
1720 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1721 requires indirectly_swappable<iterator_t<_Base>>
1722 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1724 friend _Sentinel<_Const>;
1727 template<bool _Const>
1732 = conditional_t<_Const, const transform_view, transform_view>;
1733 using _Base = conditional_t<_Const, const _Vp, _Vp>;
1735 constexpr range_difference_t<_Base>
1736 __distance_from(const _Iterator<_Const>& __i) const
1737 { return _M_end - __i._M_current; }
1740 __equal(const _Iterator<_Const>& __i) const
1741 { return __i._M_current == _M_end; }
1743 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1746 _Sentinel() = default;
1749 _Sentinel(sentinel_t<_Base> __end)
1754 _Sentinel(_Sentinel<!_Const> __i)
1756 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1757 : _M_end(std::move(__i._M_end))
1760 constexpr sentinel_t<_Base>
1764 friend constexpr bool
1765 operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
1766 { return __y.__equal(__x); }
1768 friend constexpr range_difference_t<_Base>
1769 operator-(const _Iterator<_Const>& __x, const _Sentinel& __y)
1770 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
1771 { return -__y.__distance_from(__x); }
1773 friend constexpr range_difference_t<_Base>
1774 operator-(const _Sentinel& __y, const _Iterator<_Const>& __x)
1775 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
1776 { return __y.__distance_from(__x); }
1779 _Vp _M_base = _Vp();
1780 __detail::__box<_Fp> _M_fun;
1783 transform_view() = default;
1786 transform_view(_Vp __base, _Fp __fun)
1787 : _M_base(std::move(__base)), _M_fun(std::move(__fun))
1790 /* XXX: P3280 removes this constructor
1791 template<input_range _Range>
1792 requires viewable_range<_Range>
1793 && constructible_from<_Vp, all_view<_Range>>
1795 transform_view(_Range&& __r, _Fp __fun)
1796 : _M_base(views::all(std::forward<_Range>(__r)))
1802 base() const& requires copy_constructible<_Vp>
1803 { return _M_base ; }
1807 { return std::move(_M_base); }
1809 constexpr _Iterator<false>
1811 { return _Iterator<false>{*this, ranges::begin(_M_base)}; }
1813 constexpr _Iterator<true>
1815 requires range<const _Vp>
1816 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1817 { return _Iterator<true>{*this, ranges::begin(_M_base)}; }
1819 constexpr _Sentinel<false>
1821 { return _Sentinel<false>{ranges::end(_M_base)}; }
1823 constexpr _Iterator<false>
1824 end() requires common_range<_Vp>
1825 { return _Iterator<false>{*this, ranges::end(_M_base)}; }
1827 constexpr _Sentinel<true>
1829 requires range<const _Vp>
1830 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1831 { return _Sentinel<true>{ranges::end(_M_base)}; }
1833 constexpr _Iterator<true>
1835 requires common_range<const _Vp>
1836 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1837 { return _Iterator<true>{*this, ranges::end(_M_base)}; }
1840 size() requires sized_range<_Vp>
1841 { return ranges::size(_M_base); }
1844 size() const requires sized_range<const _Vp>
1845 { return ranges::size(_M_base); }
1848 template<typename _Range, typename _Fp>
1849 transform_view(_Range&&, _Fp) -> transform_view<all_view<_Range>, _Fp>;
1853 inline constexpr __adaptor::_RangeAdaptor transform
1854 = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
1856 return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1858 } // namespace views
1861 class take_view : public view_interface<take_view<_Vp>>
1864 template<bool _Const>
1868 using _Base = conditional_t<_Const, const _Vp, _Vp>;
1869 using _CI = counted_iterator<iterator_t<_Base>>;
1871 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1874 _Sentinel() = default;
1877 _Sentinel(sentinel_t<_Base> __end)
1882 _Sentinel(_Sentinel<!_Const> __s)
1883 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1884 : _M_end(std::move(__s._M_end))
1887 constexpr sentinel_t<_Base>
1891 friend constexpr bool operator==(const _CI& __y, const _Sentinel& __x)
1892 { return __y.count() == 0 || __y.base() == __x._M_end; }
1895 _Vp _M_base = _Vp();
1896 range_difference_t<_Vp> _M_count = 0;
1899 take_view() = default;
1902 take_view(_Vp base, range_difference_t<_Vp> __count)
1903 : _M_base(std::move(base)), _M_count(std::move(__count))
1906 /* XXX: P3280 removes this constructor
1907 template<viewable_range _Range>
1908 requires constructible_from<_Vp, all_view<_Range>>
1910 take_view(_Range&& __r, range_difference_t<_Vp> __count)
1911 : _M_base(views::all(std::forward<_Range>(__r))), _M_count(__count)
1916 base() const& requires copy_constructible<_Vp>
1921 { return std::move(_M_base); }
1924 begin() requires (!__detail::__simple_view<_Vp>)
1926 if constexpr (sized_range<_Vp>)
1928 if constexpr (random_access_range<_Vp>)
1929 return ranges::begin(_M_base);
1931 return counted_iterator{ranges::begin(_M_base), size()};
1934 return counted_iterator{ranges::begin(_M_base), _M_count};
1938 begin() const requires range<const _Vp>
1940 if constexpr (sized_range<const _Vp>)
1942 if constexpr (random_access_range<const _Vp>)
1943 return ranges::begin(_M_base);
1945 return counted_iterator{ranges::begin(_M_base), size()};
1948 return counted_iterator{ranges::begin(_M_base), _M_count};
1952 end() requires (!__detail::__simple_view<_Vp>)
1954 if constexpr (sized_range<_Vp>)
1956 if constexpr (random_access_range<_Vp>)
1957 return ranges::begin(_M_base) + size();
1959 return default_sentinel;
1962 return _Sentinel<false>{ranges::end(_M_base)};
1966 end() const requires range<const _Vp>
1968 if constexpr (sized_range<const _Vp>)
1970 if constexpr (random_access_range<const _Vp>)
1971 return ranges::begin(_M_base) + size();
1973 return default_sentinel;
1976 return _Sentinel<true>{ranges::end(_M_base)};
1980 size() requires sized_range<_Vp>
1982 auto __n = ranges::size(_M_base);
1983 return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
1987 size() const requires sized_range<const _Vp>
1989 auto __n = ranges::size(_M_base);
1990 return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
1994 template<range _Range>
1995 take_view(_Range&&, range_difference_t<_Range>)
1996 -> take_view<all_view<_Range>>;
2000 inline constexpr __adaptor::_RangeAdaptor take
2001 = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2003 return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2005 } // namespace views
2007 template<view _Vp, typename _Pred>
2008 requires input_range<_Vp> && is_object_v<_Pred>
2009 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2010 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2012 template<bool _Const>
2016 using _Base = conditional_t<_Const, const _Vp, _Vp>;
2018 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2019 const _Pred* _M_pred = nullptr;
2022 _Sentinel() = default;
2025 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2026 : _M_end(__end), _M_pred(__pred)
2030 _Sentinel(_Sentinel<!_Const> __s)
2031 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2032 : _M_end(__s._M_end), _M_pred(__s._M_pred)
2035 constexpr sentinel_t<_Base>
2036 base() const { return _M_end; }
2038 friend constexpr bool
2039 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2040 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2044 __detail::__box<_Pred> _M_pred;
2047 take_while_view() = default;
2050 take_while_view(_Vp base, _Pred __pred)
2051 : _M_base(std::move(base)), _M_pred(std::move(__pred))
2056 base() const& requires copy_constructible<_Vp>
2061 { return std::move(_M_base); }
2063 constexpr const _Pred&
2065 { return *_M_pred; }
2068 begin() requires (!__detail::__simple_view<_Vp>)
2069 { return ranges::begin(_M_base); }
2072 begin() const requires range<const _Vp>
2073 { return ranges::begin(_M_base); }
2076 end() requires (!__detail::__simple_view<_Vp>)
2077 { return _Sentinel<false>(ranges::end(_M_base),
2078 std::__addressof(*_M_pred)); }
2081 end() const requires range<const _Vp>
2082 { return _Sentinel<true>(ranges::end(_M_base),
2083 std::__addressof(*_M_pred)); }
2086 template<typename _Range, typename _Pred>
2087 take_while_view(_Range&&, _Pred)
2088 -> take_while_view<all_view<_Range>, _Pred>;
2092 inline constexpr __adaptor::_RangeAdaptor take_while
2093 = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2095 return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
2097 } // namespace views
2100 class drop_view : public view_interface<drop_view<_Vp>>
2104 range_difference_t<_Vp> _M_count;
2107 drop_view() = default;
2110 drop_view(_Vp __base, range_difference_t<_Vp> __count)
2111 : _M_base(std::move(__base)), _M_count(__count)
2112 { __glibcxx_assert(__count >= 0); }
2115 base() const& requires copy_constructible<_Vp>
2120 { return std::move(_M_base); }
2123 begin() requires (!(__detail::__simple_view<_Vp>
2124 && random_access_range<_Vp>))
2126 // XXX: we need to cache the result here as per [range.drop.view]
2127 return ranges::next(ranges::begin(_M_base), _M_count,
2128 ranges::end(_M_base));
2132 begin() const requires random_access_range<const _Vp>
2134 return ranges::next(ranges::begin(_M_base), _M_count,
2135 ranges::end(_M_base));
2139 end() requires (!__detail::__simple_view<_Vp>)
2140 { return ranges::end(_M_base); }
2143 end() const requires range<const _Vp>
2144 { return ranges::end(_M_base); }
2147 size() requires sized_range<_Vp>
2149 const auto __s = ranges::size(_M_base);
2150 const auto __c = static_cast<decltype(__s)>(_M_count);
2151 return __s < __c ? 0 : __s - __c;
2155 size() const requires sized_range<const _Vp>
2157 const auto __s = ranges::size(_M_base);
2158 const auto __c = static_cast<decltype(__s)>(_M_count);
2159 return __s < __c ? 0 : __s - __c;
2163 template<typename _Range>
2164 drop_view(_Range&&, range_difference_t<_Range>)
2165 -> drop_view<all_view<_Range>>;
2169 inline constexpr __adaptor::_RangeAdaptor drop
2170 = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2172 return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2174 } // namespace views
2176 template<view _Vp, typename _Pred>
2177 requires input_range<_Vp> && is_object_v<_Pred>
2178 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2179 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2183 __detail::__box<_Pred> _M_pred;
2186 drop_while_view() = default;
2189 drop_while_view(_Vp __base, _Pred __pred)
2190 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
2194 base() const& requires copy_constructible<_Vp>
2199 { return std::move(_M_base); }
2201 constexpr const _Pred&
2203 { return *_M_pred; }
2208 // XXX: we need to cache the result here as per [range.drop.while.view]
2209 return __detail::find_if_not(ranges::begin(_M_base),
2210 ranges::end(_M_base),
2211 std::cref(*_M_pred));
2216 { return ranges::end(_M_base); }
2219 template<typename _Range, typename _Pred>
2220 drop_while_view(_Range&&, _Pred)
2221 -> drop_while_view<all_view<_Range>, _Pred>;
2225 inline constexpr __adaptor::_RangeAdaptor drop_while
2226 = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2228 return drop_while_view{std::forward<_Range>(__r),
2229 std::forward<_Pred>(__p)};
2231 } // namespace views
2233 template<input_range _Vp>
2234 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2235 && (is_reference_v<range_reference_t<_Vp>>
2236 || view<range_value_t<_Vp>>)
2237 class join_view : public view_interface<join_view<_Vp>>
2240 using _InnerRange = range_reference_t<_Vp>;
2242 template<bool _Const>
2245 template<bool _Const>
2249 using _Parent = conditional_t<_Const, const join_view, join_view>;
2250 using _Base = conditional_t<_Const, const _Vp, _Vp>;
2252 static constexpr bool _S_ref_is_glvalue
2253 = is_reference_v<range_reference_t<_Base>>;
2258 auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2260 if constexpr (_S_ref_is_glvalue)
2263 return (_M_parent->_M_inner = views::all(std::move(__x)));
2266 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2268 auto& inner = __update_inner(*_M_outer);
2269 _M_inner = ranges::begin(inner);
2270 if (_M_inner != ranges::end(inner))
2274 if constexpr (_S_ref_is_glvalue)
2275 _M_inner = iterator_t<range_reference_t<_Base>>();
2278 static constexpr auto
2281 if constexpr (_S_ref_is_glvalue
2282 && bidirectional_range<_Base>
2283 && bidirectional_range<range_reference_t<_Base>>)
2284 return bidirectional_iterator_tag{};
2285 else if constexpr (_S_ref_is_glvalue
2286 && forward_range<_Base>
2287 && forward_range<range_reference_t<_Base>>)
2288 return forward_iterator_tag{};
2290 return input_iterator_tag{};
2293 static constexpr auto
2297 = iterator_traits<iterator_t<_Base>>::iterator_category;
2299 = iterator_traits<iterator_t<range_reference_t<_Base>>>
2300 ::iterator_category;
2301 if constexpr (_S_ref_is_glvalue
2302 && derived_from<_OuterCat, bidirectional_iterator_tag>
2303 && derived_from<_InnerCat, bidirectional_iterator_tag>)
2304 return bidirectional_iterator_tag{};
2305 else if constexpr (_S_ref_is_glvalue
2306 && derived_from<_OuterCat, forward_iterator_tag>
2307 && derived_from<_InnerCat, forward_iterator_tag>)
2308 return forward_iterator_tag{};
2309 else if constexpr (derived_from<_OuterCat, input_iterator_tag>
2310 && derived_from<_InnerCat, input_iterator_tag>)
2311 return input_iterator_tag{};
2313 return output_iterator_tag{};
2316 iterator_t<_Base> _M_outer = iterator_t<_Base>();
2317 iterator_t<range_reference_t<_Base>> _M_inner
2318 = iterator_t<range_reference_t<_Base>>();
2319 _Parent* _M_parent = nullptr;
2322 using iterator_concept = decltype(_S_iter_concept());
2323 using iterator_category = decltype(_S_iter_cat());
2324 using value_type = range_value_t<range_reference_t<_Base>>;
2325 using difference_type
2326 = common_type_t<range_difference_t<_Base>,
2327 range_difference_t<range_reference_t<_Base>>>;
2329 _Iterator() = default;
2331 // XXX: had to change the type of __outer from iterator_t<_Vp> to
2332 // iterator_t<_Base> here, a possible defect in the spec?
2334 _Iterator(_Parent& __parent, iterator_t<_Base> __outer)
2335 : _M_outer(std::move(__outer)),
2336 _M_parent(std::__addressof(__parent))
2340 _Iterator(_Iterator<!_Const> __i)
2342 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2343 && convertible_to<iterator_t<_InnerRange>,
2344 iterator_t<range_reference_t<_Base>>>
2345 : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2346 _M_parent(__i._M_parent)
2349 constexpr decltype(auto)
2351 { return *_M_inner; }
2353 constexpr iterator_t<_Base>
2355 requires __detail::__has_arrow<iterator_t<_Base>>
2356 && copyable<iterator_t<_Base>>
2357 { return _M_inner; }
2359 constexpr _Iterator&
2362 auto&& __inner_range = [this] () -> decltype(auto) {
2363 if constexpr (_S_ref_is_glvalue)
2366 return _M_parent->_M_inner;
2368 if (++_M_inner == ranges::end(__inner_range))
2382 requires _S_ref_is_glvalue && forward_range<_Base>
2383 && forward_range<range_reference_t<_Base>>
2390 constexpr _Iterator&
2392 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2393 && bidirectional_range<range_reference_t<_Base>>
2395 if (_M_outer == ranges::end(_M_parent->_M_base))
2396 _M_inner = ranges::end(*--_M_outer);
2397 while (_M_inner == ranges::begin(*_M_outer))
2398 _M_inner = ranges::end(*--_M_outer);
2405 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2406 && bidirectional_range<range_reference_t<_Base>>
2413 friend constexpr bool
2414 operator==(const _Iterator& __x, const _Iterator& __y)
2415 requires _S_ref_is_glvalue
2416 && equality_comparable<iterator_t<_Base>>
2417 && equality_comparable<iterator_t<range_reference_t<_Base>>>
2419 return (__x._M_outer == __y._M_outer
2420 && __x._M_inner == __y._M_inner);
2423 friend constexpr decltype(auto)
2424 iter_move(const _Iterator& __i)
2425 noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2426 { return ranges::iter_move(__i._M_inner); }
2428 friend constexpr void
2429 iter_swap(const _Iterator& __x, const _Iterator& __y)
2430 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2431 { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2433 friend _Sentinel<_Const>;
2436 template<bool _Const>
2440 using _Parent = conditional_t<_Const, const join_view, join_view>;
2441 using _Base = conditional_t<_Const, const _Vp, _Vp>;
2444 __equal(const _Iterator<_Const>& __i) const
2445 { return __i._M_outer == _M_end; }
2447 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2450 _Sentinel() = default;
2453 _Sentinel(_Parent& __parent)
2454 : _M_end(ranges::end(__parent._M_base))
2458 _Sentinel(_Sentinel<!_Const> __s)
2459 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2460 : _M_end(std::move(__s._M_end))
2463 friend constexpr bool
2464 operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
2465 { return __y.__equal(__x); }
2468 _Vp _M_base = _Vp();
2470 // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2471 // Applied P3278 and made this field mutable.
2472 [[no_unique_address]] mutable
2473 conditional_t<!is_reference_v<_InnerRange>,
2474 all_view<_InnerRange>, __detail::_Empty> _M_inner;
2477 join_view() = default;
2480 join_view(_Vp __base)
2481 : _M_base(std::move(__base))
2484 /* XXX: P3280 removes this constructor
2485 template<input_range _Range>
2486 requires viewable_range<_Range>
2487 && constructible_from<_Vp, all_view<_Range>>
2489 join_view(_Range&& __r)
2490 : _M_base(views::all(std::forward<_Range>(__r)))
2495 base() const& requires copy_constructible<_Vp>
2500 { return std::move(_M_base); }
2505 return _Iterator<__detail::__simple_view<_Vp>>{*this,
2506 ranges::begin(_M_base)};
2511 requires input_range<const _Vp>
2512 && is_reference_v<range_reference_t<const _Vp>>
2514 return _Iterator<true>{*this, ranges::begin(_M_base)};
2520 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2521 && forward_range<_InnerRange>
2522 && common_range<_Vp> && common_range<_InnerRange>)
2523 return _Iterator<__detail::__simple_view<_Vp>>{*this,
2524 ranges::end(_M_base)};
2526 return _Sentinel<__detail::__simple_view<_Vp>>{*this};
2531 requires input_range<const _Vp>
2532 && is_reference_v<range_reference_t<const _Vp>>
2534 if constexpr (forward_range<const _Vp>
2535 && is_reference_v<range_reference_t<const _Vp>>
2536 && forward_range<range_reference_t<const _Vp>>
2537 && common_range<const _Vp>
2538 && common_range<range_reference_t<const _Vp>>)
2539 return _Iterator<true>{*this, ranges::end(_M_base)};
2541 return _Sentinel<true>{*this};
2545 template<typename _Range>
2546 explicit join_view(_Range&&) -> join_view<all_view<_Range>>;
2550 inline constexpr __adaptor::_RangeAdaptorClosure join
2551 = [] <viewable_range _Range> (_Range&& __r)
2553 return join_view{std::forward<_Range>(__r)};
2555 } // namespace views
2560 struct __require_constant;
2562 template<typename _Range>
2563 concept __tiny_range = sized_range<_Range>
2565 { typename __require_constant<remove_reference_t<_Range>::size()>; }
2566 && (remove_reference_t<_Range>::size() <= 1);
2569 template<input_range _Vp, forward_range _Pattern>
2570 requires view<_Vp> && view<_Pattern>
2571 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2573 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2574 class split_view : public view_interface<split_view<_Vp, _Pattern>>
2577 template<bool _Const>
2580 template<bool _Const>
2584 using _Parent = conditional_t<_Const, const split_view, split_view>;
2585 using _Base = conditional_t<_Const, const _Vp, _Vp>;
2589 { return _M_current == ranges::end(_M_parent->_M_base); }
2591 // XXX: [24.7.11.3.1]
2592 // Many of the following specifications refer to the notional member
2593 // current of outer-iterator. current is equivalent to current_ if
2594 // V models forward_range, and parent_->current_ otherwise.
2598 if constexpr (forward_range<_Vp>)
2601 return _M_parent->_M_current;
2607 if constexpr (forward_range<_Vp>)
2610 return _M_parent->_M_current;
2613 _Parent* _M_parent = nullptr;
2615 // XXX: _M_current is present only if "V models forward_range"
2616 [[no_unique_address]]
2617 conditional_t<forward_range<_Vp>,
2618 iterator_t<_Base>, __detail::_Empty> _M_current;
2621 using iterator_concept = conditional_t<forward_range<_Base>,
2622 forward_iterator_tag,
2623 input_iterator_tag>;
2624 using iterator_category = input_iterator_tag;
2625 using difference_type = range_difference_t<_Base>;
2627 struct value_type : view_interface<value_type>
2630 _OuterIter _M_i = _OuterIter();
2633 value_type() = default;
2636 value_type(_OuterIter __i)
2637 : _M_i(std::move(__i))
2640 constexpr _InnerIter<_Const>
2642 requires copyable<_OuterIter>
2643 { return _InnerIter<_Const>{_M_i}; }
2645 constexpr _InnerIter<_Const>
2647 requires (!copyable<_OuterIter>)
2648 { return _InnerIter<_Const>{std::move(_M_i)}; }
2650 constexpr default_sentinel_t
2652 { return default_sentinel; }
2655 _OuterIter() = default;
2658 _OuterIter(_Parent& __parent) requires (!forward_range<_Base>)
2659 : _M_parent(address(__parent))
2663 _OuterIter(_Parent& __parent, iterator_t<_Base> __current)
2664 requires forward_range<_Base>
2665 : _M_parent(std::__addressof(__parent)),
2666 _M_current(std::move(__current))
2670 _OuterIter(_OuterIter<!_Const> __i)
2672 && convertible_to<iterator_t<_Vp>, iterator_t<const _Vp>>
2673 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2676 constexpr value_type
2678 { return value_type{*this}; }
2680 constexpr _OuterIter&
2683 const auto __end = ranges::end(_M_parent->_M_base);
2684 if (_M_current == __end)
2686 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2687 if (__pbegin == __pend)
2693 = __detail::mismatch(std::move(_M_current), __end,
2695 _M_current = std::move(__b);
2698 } while (++_M_current != __end);
2702 constexpr decltype(auto)
2705 if constexpr (forward_range<_Base>)
2715 friend constexpr bool
2716 operator==(const _OuterIter& __x, const _OuterIter& __y)
2717 requires forward_range<_Base>
2718 { return __x._M_current == __y._M_current; }
2720 friend constexpr bool
2721 operator==(const _OuterIter& __x, default_sentinel_t)
2722 { return __x.__at_end(); };
2724 friend _InnerIter<_Const>;
2727 template<bool _Const>
2731 using _Base = conditional_t<_Const, const _Vp, _Vp>;
2736 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2737 auto __end = ranges::end(_M_i._M_parent->_M_base);
2738 if constexpr (__detail::__tiny_range<_Pattern>)
2740 const auto& __cur = _M_i.__current();
2743 if (__pcur == __pend)
2744 return _M_incremented;
2745 return *__cur == *__pcur;
2749 auto __cur = _M_i.__current();
2752 if (__pcur == __pend)
2753 return _M_incremented;
2756 if (*__cur != *__pcur)
2758 if (++__pcur == __pend)
2760 } while (++__cur != __end);
2765 static constexpr auto
2768 using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category;
2769 if constexpr (derived_from<_Cat, forward_iterator_tag>)
2770 return forward_iterator_tag{};
2775 static constexpr decltype(auto)
2776 __iter_move(const _InnerIter& __i = {})
2777 noexcept(noexcept(ranges::iter_move(__i._M_i.__current())))
2778 { return ranges::iter_move(__i._M_i.__current()); }
2780 static constexpr void
2781 __iter_swap(const _InnerIter& __x = {}, const _InnerIter& __y = {})
2782 noexcept(noexcept(ranges::iter_swap(__x._M_i.__current(),
2783 __y._M_i.__current())))
2784 { ranges::iter_swap(__x._M_i.__current(), __y._M_i.__current()); }
2786 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2787 bool _M_incremented = false;
2790 using iterator_concept = typename _OuterIter<_Const>::iterator_concept;
2791 using iterator_category = decltype(_S_iter_cat());
2792 using value_type = range_value_t<_Base>;
2793 using difference_type = range_difference_t<_Base>;
2795 _InnerIter() = default;
2798 _InnerIter(_OuterIter<_Const> __i)
2799 : _M_i(std::move(__i))
2802 constexpr decltype(auto)
2804 { return *_M_i._M_current; }
2806 constexpr _InnerIter&
2809 _M_incremented = true;
2810 if constexpr (!forward_range<_Base>)
2811 if constexpr (_Pattern::size() == 0)
2817 constexpr decltype(auto)
2820 if constexpr (forward_range<_Vp>)
2830 friend constexpr bool
2831 operator==(const _InnerIter& __x, const _InnerIter& __y)
2832 requires forward_range<_Base>
2833 { return __x._M_i.__current() == __y._M_i.__current(); }
2835 friend constexpr bool
2836 operator==(const _InnerIter& __x, default_sentinel_t)
2837 { return __x.__at_end(); }
2839 friend constexpr decltype(auto)
2840 iter_move(const _InnerIter& __i) noexcept(noexcept(__iter_move()))
2841 { return __iter_move(__i); }
2843 friend constexpr void
2844 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2845 noexcept(noexcept(__iter_swap()))
2846 requires indirectly_swappable<iterator_t<_Base>>
2847 { __iter_swap(__x, __y); }
2850 _Vp _M_base = _Vp();
2851 _Pattern _M_pattern = _Pattern();
2853 // XXX: _M_current is "present only if !forward_range<V>"
2854 [[no_unique_address]]
2855 conditional_t<!forward_range<_Vp>,
2856 iterator_t<_Vp>, __detail::_Empty> _M_current;
2860 split_view() = default;
2863 split_view(_Vp __base, _Pattern __pattern)
2864 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
2867 /* XXX: P3280 removes this constructor
2868 template<input_range _Range, forward_range _Pred>
2869 requires constructible_from<_Vp, all_view<_Range>>
2870 && constructible_from<_Pattern, all_view<_Pred>>
2872 split_view(_Range&& __r, _Pred&& __p)
2873 : _M_base(views::all(std::forward<_Range>(__r))),
2874 _M_pattern(views::all(std::forward<_Pred>(__p)))
2878 template<input_range _Range>
2879 requires constructible_from<_Vp, all_view<_Range>>
2880 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2882 split_view(_Range&& __r, range_value_t<_Range> __e)
2883 : _M_base(views::all(std::forward<_Range>(__r))),
2884 _M_pattern(std::move(__e))
2888 base() const& requires copy_constructible<_Vp>
2893 { return std::move(_M_base); }
2898 if constexpr (forward_range<_Vp>)
2899 return _OuterIter<__detail::__simple_view<_Vp>>{*this,
2900 ranges::begin(_M_base)};
2903 _M_current = ranges::begin(_M_base);
2904 return _OuterIter<false>{*this};
2909 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
2911 return _OuterIter<true>{*this, ranges::begin(_M_base)};
2915 end() requires forward_range<_Vp> && common_range<_Vp>
2917 return _OuterIter<__detail::__simple_view<_Vp>>{*this, ranges::end(_M_base)};
2923 if constexpr (forward_range<_Vp>
2924 && forward_range<const _Vp>
2925 && common_range<const _Vp>)
2926 return _OuterIter<true>{*this, ranges::end(_M_base)};
2928 return default_sentinel;
2932 template<typename _Range, typename _Pred>
2933 split_view(_Range&&, _Pred&&)
2934 -> split_view<all_view<_Range>, all_view<_Pred>>;
2936 template<input_range _Range>
2937 split_view(_Range&&, range_value_t<_Range>)
2938 -> split_view<all_view<_Range>, single_view<range_value_t<_Range>>>;
2942 inline constexpr __adaptor::_RangeAdaptor split
2943 = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
2945 return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
2947 } // namespace views
2953 template<input_or_output_iterator _Iter>
2955 operator()(_Iter __i, iter_difference_t<_Iter> __n) const
2957 if constexpr (random_access_iterator<_Iter>)
2958 return subrange{__i, __i + __n};
2960 return subrange{counted_iterator{std::move(__i), __n},
2965 inline constexpr _Counted counted{};
2966 } // namespace views
2969 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
2970 class common_view : public view_interface<common_view<_Vp>>
2973 _Vp _M_base = _Vp();
2976 common_view() = default;
2979 common_view(_Vp __r)
2980 : _M_base(std::move(__r))
2983 /* XXX: P3280 doesn't remove this constructor, but I think it should?
2984 template<viewable_range _Range>
2985 requires (!common_range<_Range>) && constructible_from<_Vp, all_view<_Range>>
2987 common_view(_Range&& __r)
2988 : _M_base(views::all(std::forward<_Range>(__r)))
2993 base() const& requires copy_constructible<_Vp>
2998 { return std::move(_M_base); }
3003 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3004 return ranges::begin(_M_base);
3006 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3007 (ranges::begin(_M_base));
3011 begin() const requires range<const _Vp>
3013 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3014 return ranges::begin(_M_base);
3016 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3017 (ranges::begin(_M_base));
3023 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3024 return ranges::begin(_M_base) + ranges::size(_M_base);
3026 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3027 (ranges::end(_M_base));
3031 end() const requires range<const _Vp>
3033 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3034 return ranges::begin(_M_base) + ranges::size(_M_base);
3036 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3037 (ranges::end(_M_base));
3041 size() requires sized_range<_Vp>
3042 { return ranges::size(_M_base); }
3045 size() const requires sized_range<const _Vp>
3046 { return ranges::size(_M_base); }
3049 template<typename _Range>
3050 common_view(_Range&&) -> common_view<all_view<_Range>>;
3054 inline constexpr __adaptor::_RangeAdaptorClosure common
3055 = [] <viewable_range _Range> (_Range&& __r)
3057 if constexpr (common_range<_Range>
3058 && requires { views::all(std::forward<_Range>(__r)); })
3059 return views::all(std::forward<_Range>(__r));
3061 return common_view{std::forward<_Range>(__r)};
3064 } // namespace views
3067 requires bidirectional_range<_Vp>
3068 class reverse_view : public view_interface<reverse_view<_Vp>>
3071 _Vp _M_base = _Vp();
3074 reverse_view() = default;
3077 reverse_view(_Vp __r)
3078 : _M_base(std::move(__r))
3081 /* XXX: P3280 removes this constructor
3082 template<viewable_range _Range>
3083 requires bidirectional_range<_Range> && constructible_from<_Vp, all_view<_Range>>
3085 reverse_view(_Range&& __r)
3086 : _M_base(views::all(std::forward<_Range>(__r)))
3091 base() const& requires copy_constructible<_Vp>
3096 { return std::move(_M_base); }
3098 constexpr reverse_iterator<iterator_t<_Vp>>
3101 // XXX: we need to cache the result here as per [range.reverse.view]
3102 return make_reverse_iterator(ranges::next(ranges::begin(_M_base),
3103 ranges::end(_M_base)));
3107 begin() requires common_range<_Vp>
3108 { return make_reverse_iterator(ranges::end(_M_base)); }
3111 begin() const requires common_range<const _Vp>
3112 { return make_reverse_iterator(ranges::end(_M_base)); }
3114 constexpr reverse_iterator<iterator_t<_Vp>>
3116 { return make_reverse_iterator(ranges::begin(_M_base)); }
3119 end() const requires common_range<const _Vp>
3120 { return make_reverse_iterator(ranges::begin(_M_base)); }
3123 size() requires sized_range<_Vp>
3124 { return ranges::size(_M_base); }
3127 size() const requires sized_range<const _Vp>
3128 { return ranges::size(_M_base); }
3131 template<typename _Range>
3132 reverse_view(_Range&&) -> reverse_view<all_view<_Range>>;
3139 inline constexpr bool __is_reversible_subrange = false;
3141 template<typename _Iter, subrange_kind _Kind>
3142 inline constexpr bool
3143 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3144 reverse_iterator<_Iter>,
3148 inline constexpr bool __is_reverse_view = false;
3150 template<typename _Vp>
3151 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3154 inline constexpr __adaptor::_RangeAdaptorClosure reverse
3155 = [] <viewable_range _Range> (_Range&& __r)
3157 using _Tp = remove_cvref_t<_Range>;
3158 if constexpr (__detail::__is_reverse_view<_Tp>)
3159 return std::forward<_Range>(__r).base();
3160 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3162 using _Iter = decltype(ranges::begin(__r).base());
3163 if constexpr (sized_range<_Tp>)
3164 return subrange<_Iter, _Iter, subrange_kind::sized>
3165 (__r.end().base(), __r.begin().base(), __r.size());
3167 return subrange<_Iter, _Iter, subrange_kind::unsized>
3168 (__r.end().base(), __r.begin().base());
3171 return reverse_view{std::forward<_Range>(__r)};
3173 } // namespace views
3177 template<typename _Tp, size_t _Nm>
3178 concept __has_tuple_element = requires(_Tp __t)
3180 typename tuple_size<_Tp>::type;
3181 requires _Nm < tuple_size_v<_Tp>;
3182 typename tuple_element_t<_Nm, _Tp>;
3183 // XXX: we applied P3323 here
3184 { std::get<_Nm>(__t) }
3185 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3189 template<input_range _Vp, size_t _Nm>
3191 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3192 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3194 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3197 elements_view() = default;
3200 elements_view(_Vp base)
3201 : _M_base(std::move(base))
3205 base() const& requires copy_constructible<_Vp>
3210 { return std::move(_M_base); }
3213 begin() requires (!__detail::__simple_view<_Vp>)
3214 { return _Iterator<false>(ranges::begin(_M_base)); }
3217 begin() const requires __detail::__simple_view<_Vp>
3218 { return _Iterator<true>(ranges::begin(_M_base)); }
3221 end() requires (!__detail::__simple_view<_Vp>)
3222 { return ranges::end(_M_base); }
3225 end() const requires __detail::__simple_view<_Vp>
3226 { return ranges::end(_M_base); }
3229 size() requires sized_range<_Vp>
3230 { return ranges::size(_M_base); }
3233 size() const requires sized_range<const _Vp>
3234 { return ranges::size(_M_base); }
3237 template<bool _Const>
3240 using _Base = conditional_t<_Const, const _Vp, _Vp>;
3242 iterator_t<_Base> _M_current;
3244 friend _Iterator<!_Const>;
3247 using iterator_category
3248 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3250 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3251 using difference_type = range_difference_t<_Base>;
3253 _Iterator() = default;
3256 _Iterator(iterator_t<_Base> current)
3257 : _M_current(std::move(current))
3261 _Iterator(_Iterator<!_Const> i)
3262 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3263 : _M_current(std::move(i._M_current))
3266 constexpr iterator_t<_Base>
3268 requires copyable<iterator_t<_Base>>
3269 { return _M_current; }
3271 constexpr iterator_t<_Base>
3273 { return std::move(_M_current); }
3275 constexpr decltype(auto)
3277 { return std::get<_Nm>(*_M_current); }
3279 constexpr _Iterator&
3287 operator++(int) requires (!forward_range<_Base>)
3291 operator++(int) requires forward_range<_Base>
3298 constexpr _Iterator&
3299 operator--() requires bidirectional_range<_Base>
3306 operator--(int) requires bidirectional_range<_Base>
3313 constexpr _Iterator&
3314 operator+=(difference_type __n)
3315 requires random_access_range<_Base>
3321 constexpr _Iterator&
3322 operator-=(difference_type __n)
3323 requires random_access_range<_Base>
3329 constexpr decltype(auto)
3330 operator[](difference_type __n) const
3331 requires random_access_range<_Base>
3332 { return std::get<_Nm>(*(_M_current + __n)); }
3334 friend constexpr bool
3335 operator==(const _Iterator& __x, const _Iterator& __y)
3336 requires equality_comparable<iterator_t<_Base>>
3337 { return __x._M_current == __y._M_current; }
3339 friend constexpr bool
3340 operator==(const _Iterator& __x, const sentinel_t<_Base>& __y)
3341 { return __x._M_current == __y; }
3343 friend constexpr bool
3344 operator<(const _Iterator& __x, const _Iterator& __y)
3345 requires random_access_range<_Base>
3346 { return __x._M_current < __y._M_current; }
3348 friend constexpr bool
3349 operator>(const _Iterator& __x, const _Iterator& __y)
3350 requires random_access_range<_Base>
3351 { return __y._M_current < __x._M_current; }
3353 friend constexpr bool
3354 operator<=(const _Iterator& __x, const _Iterator& __y)
3355 requires random_access_range<_Base>
3356 { return !(__y._M_current > __x._M_current); }
3358 friend constexpr bool
3359 operator>=(const _Iterator& __x, const _Iterator& __y)
3360 requires random_access_range<_Base>
3361 { return !(__x._M_current > __y._M_current); }
3363 #ifdef __cpp_lib_three_way_comparison
3364 friend constexpr auto
3365 operator<=>(const _Iterator& __x, const _Iterator& __y)
3366 requires random_access_range<_Base>
3367 && three_way_comparable<iterator_t<_Base>>
3368 { return __x._M_current <=> __y._M_current; }
3371 friend constexpr _Iterator
3372 operator+(const _Iterator& __x, difference_type __y)
3373 requires random_access_range<_Base>
3374 { return _Iterator{__x} += __y; }
3376 friend constexpr _Iterator
3377 operator+(difference_type __x, const _Iterator& __y)
3378 requires random_access_range<_Base>
3379 { return __y + __x; }
3381 friend constexpr _Iterator
3382 operator-(const _Iterator& __x, difference_type __y)
3383 requires random_access_range<_Base>
3384 { return _Iterator{__x} -= __y; }
3386 friend constexpr difference_type
3387 operator-(const _Iterator& __x, const _Iterator& __y)
3388 requires random_access_range<_Base>
3389 { return __x._M_current - __y._M_current; }
3391 friend constexpr difference_type
3392 operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y)
3393 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3394 { return __x._M_current - __y; }
3396 friend constexpr difference_type
3397 operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y)
3398 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3399 { return -(__y - __x); }
3402 _Vp _M_base = _Vp();
3405 template<typename _Range>
3406 using keys_view = elements_view<all_view<_Range>, 0>;
3408 template<typename _Range>
3409 using values_view = elements_view<all_view<_Range>, 1>;
3413 template<size_t _Nm>
3414 inline constexpr __adaptor::_RangeAdaptorClosure elements
3415 = [] <viewable_range _Range> (_Range&& __r)
3417 return elements_view<all_view<_Range>, _Nm>{std::forward<_Range>(__r)};
3420 inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
3421 inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
3422 } // namespace views
3424 } // namespace ranges
3426 namespace views = ranges::views;
3428 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3429 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
3430 : integral_constant<size_t, 2>
3433 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3434 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
3435 { using type = _Iter; };
3437 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3438 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
3439 { using type = _Sent; };
3441 _GLIBCXX_END_NAMESPACE_VERSION
3443 #endif // library concepts
3445 #endif /* _GLIBCXX_RANGES */