1 // <ranges> -*- C++ -*-
3 // Copyright (C) 2019-2021 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
42 #include <initializer_list>
47 #include <bits/ranges_util.h>
48 #include <bits/refwrap.h>
51 * @defgroup ranges Ranges
53 * Components for dealing with ranges of elements.
56 namespace std _GLIBCXX_VISIBILITY(default)
58 _GLIBCXX_BEGIN_NAMESPACE_VERSION
61 // [range.access] customization point objects
62 // [range.req] range and view concepts
63 // [range.dangling] dangling iterator handling
64 // Defined in <bits/ranges_base.h>
66 // [view.interface] View interface
67 // [range.subrange] Sub-ranges
68 // Defined in <bits/ranges_util.h>
70 // C++20 24.6 [range.factories] Range factories
72 /// A view that contains no elements.
73 template<typename _Tp> requires is_object_v<_Tp>
75 : public view_interface<empty_view<_Tp>>
78 static constexpr _Tp* begin() noexcept { return nullptr; }
79 static constexpr _Tp* end() noexcept { return nullptr; }
80 static constexpr _Tp* data() noexcept { return nullptr; }
81 static constexpr size_t size() noexcept { return 0; }
82 static constexpr bool empty() noexcept { return true; }
85 template<typename _Tp>
86 inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true;
90 template<typename _Tp>
91 concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>;
93 template<__boxable _Tp>
94 struct __box : std::optional<_Tp>
96 using std::optional<_Tp>::optional;
100 noexcept(is_nothrow_default_constructible_v<_Tp>)
101 requires default_initializable<_Tp>
102 : std::optional<_Tp>{std::in_place}
105 __box(const __box&) = default;
106 __box(__box&&) = default;
108 using std::optional<_Tp>::operator=;
110 // _GLIBCXX_RESOLVE_LIB_DEFECTS
111 // 3477. Simplify constraints for semiregular-box
113 operator=(const __box& __that)
114 noexcept(is_nothrow_copy_constructible_v<_Tp>)
115 requires (!copyable<_Tp>)
117 if (this != std::__addressof(__that))
120 this->emplace(*__that);
128 operator=(__box&& __that)
129 noexcept(is_nothrow_move_constructible_v<_Tp>)
130 requires (!movable<_Tp>)
132 if (this != std::__addressof(__that))
135 this->emplace(std::move(*__that));
143 // For types which are already copyable, this specialization of the
144 // copyable wrapper stores the object directly without going through
145 // std::optional. It provides just the subset of the primary template's
146 // API that we currently use.
147 template<__boxable _Tp>
148 requires copyable<_Tp> || (is_nothrow_move_constructible_v<_Tp>
149 && is_nothrow_copy_constructible_v<_Tp>)
153 [[no_unique_address]] _Tp _M_value = _Tp();
156 __box() requires default_initializable<_Tp> = default;
159 __box(const _Tp& __t)
160 noexcept(is_nothrow_copy_constructible_v<_Tp>)
166 noexcept(is_nothrow_move_constructible_v<_Tp>)
167 : _M_value(std::move(__t))
170 template<typename... _Args>
171 requires constructible_from<_Tp, _Args...>
173 __box(in_place_t, _Args&&... __args)
174 noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
175 : _M_value(std::forward<_Args>(__args)...)
178 __box(const __box&) = default;
179 __box(__box&&) = default;
180 __box& operator=(const __box&) requires copyable<_Tp> = default;
181 __box& operator=(__box&&) requires copyable<_Tp> = default;
183 // When _Tp is nothrow_copy_constructible but not copy_assignable,
184 // copy assignment is implemented via destroy-then-copy-construct.
186 operator=(const __box& __that) noexcept
188 static_assert(is_nothrow_copy_constructible_v<_Tp>);
189 if (this != std::__addressof(__that))
192 std::construct_at(std::__addressof(_M_value), *__that);
197 // Likewise for move assignment.
199 operator=(__box&& __that) noexcept
201 static_assert(is_nothrow_move_constructible_v<_Tp>);
202 if (this != std::__addressof(__that))
205 std::construct_at(std::__addressof(_M_value), std::move(*__that));
211 has_value() const noexcept
219 operator*() const noexcept
223 operator->() noexcept
224 { return std::__addressof(_M_value); }
227 operator->() const noexcept
228 { return std::__addressof(_M_value); }
230 } // namespace __detail
232 /// A view that contains exactly one element.
233 template<copy_constructible _Tp> requires is_object_v<_Tp>
234 class single_view : public view_interface<single_view<_Tp>>
237 single_view() requires default_initializable<_Tp> = default;
240 single_view(const _Tp& __t)
241 noexcept(is_nothrow_copy_constructible_v<_Tp>)
246 single_view(_Tp&& __t)
247 noexcept(is_nothrow_move_constructible_v<_Tp>)
248 : _M_value(std::move(__t))
251 // _GLIBCXX_RESOLVE_LIB_DEFECTS
252 // 3428. single_view's in place constructor should be explicit
253 template<typename... _Args>
254 requires constructible_from<_Tp, _Args...>
256 single_view(in_place_t, _Args&&... __args)
257 noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
258 : _M_value{in_place, std::forward<_Args>(__args)...}
266 begin() const noexcept
271 { return data() + 1; }
275 { return data() + 1; }
277 static constexpr size_t
283 { return _M_value.operator->(); }
286 data() const noexcept
287 { return _M_value.operator->(); }
290 [[no_unique_address]] __detail::__box<_Tp> _M_value;
293 template<typename _Tp>
294 single_view(_Tp) -> single_view<_Tp>;
298 template<typename _Wp>
299 constexpr auto __to_signed_like(_Wp __w) noexcept
301 if constexpr (!integral<_Wp>)
302 return iter_difference_t<_Wp>();
303 else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
304 return iter_difference_t<_Wp>(__w);
305 else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
306 return ptrdiff_t(__w);
307 else if constexpr (sizeof(long long) > sizeof(_Wp))
308 return (long long)(__w);
309 #ifdef __SIZEOF_INT128__
310 else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
311 return __int128(__w);
314 return __max_diff_type(__w);
317 template<typename _Wp>
318 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
320 template<typename _It>
321 concept __decrementable = incrementable<_It>
324 { --__i } -> same_as<_It&>;
325 { __i-- } -> same_as<_It>;
328 template<typename _It>
329 concept __advanceable = __decrementable<_It> && totally_ordered<_It>
330 && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
332 { __i += __n } -> same_as<_It&>;
333 { __i -= __n } -> same_as<_It&>;
337 { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
340 template<typename _Winc>
341 struct __iota_view_iter_cat
344 template<incrementable _Winc>
345 struct __iota_view_iter_cat<_Winc>
346 { using iterator_category = input_iterator_tag; };
347 } // namespace __detail
349 template<weakly_incrementable _Winc,
350 semiregular _Bound = unreachable_sentinel_t>
351 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
353 class iota_view : public view_interface<iota_view<_Winc, _Bound>>
358 struct _Iterator : __detail::__iota_view_iter_cat<_Winc>
364 using namespace __detail;
365 if constexpr (__advanceable<_Winc>)
366 return random_access_iterator_tag{};
367 else if constexpr (__decrementable<_Winc>)
368 return bidirectional_iterator_tag{};
369 else if constexpr (incrementable<_Winc>)
370 return forward_iterator_tag{};
372 return input_iterator_tag{};
376 using iterator_concept = decltype(_S_iter_concept());
377 // iterator_category defined in __iota_view_iter_cat
378 using value_type = _Winc;
379 using difference_type = __detail::__iota_diff_t<_Winc>;
381 _Iterator() requires default_initializable<_Winc> = default;
384 _Iterator(_Winc __value)
385 : _M_value(__value) { }
388 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
403 operator++(int) requires incrementable<_Winc>
411 operator--() requires __detail::__decrementable<_Winc>
418 operator--(int) requires __detail::__decrementable<_Winc>
426 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
428 using __detail::__is_integer_like;
429 using __detail::__is_signed_integer_like;
430 if constexpr (__is_integer_like<_Winc>
431 && !__is_signed_integer_like<_Winc>)
433 if (__n >= difference_type(0))
434 _M_value += static_cast<_Winc>(__n);
436 _M_value -= static_cast<_Winc>(-__n);
444 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
446 using __detail::__is_integer_like;
447 using __detail::__is_signed_integer_like;
448 if constexpr (__is_integer_like<_Winc>
449 && !__is_signed_integer_like<_Winc>)
451 if (__n >= difference_type(0))
452 _M_value -= static_cast<_Winc>(__n);
454 _M_value += static_cast<_Winc>(-__n);
462 operator[](difference_type __n) const
463 requires __detail::__advanceable<_Winc>
464 { return _Winc(_M_value + __n); }
466 friend constexpr bool
467 operator==(const _Iterator& __x, const _Iterator& __y)
468 requires equality_comparable<_Winc>
469 { return __x._M_value == __y._M_value; }
471 friend constexpr bool
472 operator<(const _Iterator& __x, const _Iterator& __y)
473 requires totally_ordered<_Winc>
474 { return __x._M_value < __y._M_value; }
476 friend constexpr bool
477 operator>(const _Iterator& __x, const _Iterator& __y)
478 requires totally_ordered<_Winc>
479 { return __y < __x; }
481 friend constexpr bool
482 operator<=(const _Iterator& __x, const _Iterator& __y)
483 requires totally_ordered<_Winc>
484 { return !(__y < __x); }
486 friend constexpr bool
487 operator>=(const _Iterator& __x, const _Iterator& __y)
488 requires totally_ordered<_Winc>
489 { return !(__x < __y); }
491 #ifdef __cpp_lib_three_way_comparison
492 friend constexpr auto
493 operator<=>(const _Iterator& __x, const _Iterator& __y)
494 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
495 { return __x._M_value <=> __y._M_value; }
498 friend constexpr _Iterator
499 operator+(_Iterator __i, difference_type __n)
500 requires __detail::__advanceable<_Winc>
506 friend constexpr _Iterator
507 operator+(difference_type __n, _Iterator __i)
508 requires __detail::__advanceable<_Winc>
509 { return __i += __n; }
511 friend constexpr _Iterator
512 operator-(_Iterator __i, difference_type __n)
513 requires __detail::__advanceable<_Winc>
519 friend constexpr difference_type
520 operator-(const _Iterator& __x, const _Iterator& __y)
521 requires __detail::__advanceable<_Winc>
523 using __detail::__is_integer_like;
524 using __detail::__is_signed_integer_like;
525 using _Dt = difference_type;
526 if constexpr (__is_integer_like<_Winc>)
528 if constexpr (__is_signed_integer_like<_Winc>)
529 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
531 return (__y._M_value > __x._M_value)
532 ? _Dt(-_Dt(__y._M_value - __x._M_value))
533 : _Dt(__x._M_value - __y._M_value);
536 return __x._M_value - __y._M_value;
540 _Winc _M_value = _Winc();
550 _M_equal(const _Iterator& __x) const
551 { return __x._M_value == _M_bound; }
554 _M_distance_from(const _Iterator& __x) const
555 { return _M_bound - __x._M_value; }
557 _Bound _M_bound = _Bound();
560 _Sentinel() = default;
563 _Sentinel(_Bound __bound)
564 : _M_bound(__bound) { }
566 friend constexpr bool
567 operator==(const _Iterator& __x, const _Sentinel& __y)
568 { return __y._M_equal(__x); }
570 friend constexpr iter_difference_t<_Winc>
571 operator-(const _Iterator& __x, const _Sentinel& __y)
572 requires sized_sentinel_for<_Bound, _Winc>
573 { return -__y._M_distance_from(__x); }
575 friend constexpr iter_difference_t<_Winc>
576 operator-(const _Sentinel& __x, const _Iterator& __y)
577 requires sized_sentinel_for<_Bound, _Winc>
578 { return __x._M_distance_from(__y); }
583 _Winc _M_value = _Winc();
584 [[no_unique_address]] _Bound _M_bound = _Bound();
587 iota_view() requires default_initializable<_Winc> = default;
590 iota_view(_Winc __value)
595 iota_view(type_identity_t<_Winc> __value,
596 type_identity_t<_Bound> __bound)
597 : _M_value(__value), _M_bound(__bound)
599 if constexpr (totally_ordered_with<_Winc, _Bound>)
600 __glibcxx_assert( bool(__value <= __bound) );
604 iota_view(_Iterator __first, _Iterator __last)
605 requires same_as<_Winc, _Bound>
606 : iota_view(__first._M_value, __last._M_value)
610 iota_view(_Iterator __first, unreachable_sentinel_t __last)
611 requires same_as<_Bound, unreachable_sentinel_t>
612 : iota_view(__first._M_value, __last)
616 iota_view(_Iterator __first, _Sentinel __last)
617 requires (!same_as<_Winc, _Bound>) && (!same_as<_Bound, unreachable_sentinel_t>)
618 : iota_view(__first._M_value, __last._M_bound)
622 begin() const { return _Iterator{_M_value}; }
627 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
628 return unreachable_sentinel;
630 return _Sentinel{_M_bound};
634 end() const requires same_as<_Winc, _Bound>
635 { return _Iterator{_M_bound}; }
639 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
640 || (integral<_Winc> && integral<_Bound>)
641 || sized_sentinel_for<_Bound, _Winc>
643 using __detail::__is_integer_like;
644 using __detail::__to_unsigned_like;
645 if constexpr (integral<_Winc> && integral<_Bound>)
647 using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>;
648 return _Up(_M_bound) - _Up(_M_value);
650 else if constexpr (__is_integer_like<_Winc>)
651 return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
653 return __to_unsigned_like(_M_bound - _M_value);
657 template<typename _Winc, typename _Bound>
658 requires (!__detail::__is_integer_like<_Winc>
659 || !__detail::__is_integer_like<_Bound>
660 || (__detail::__is_signed_integer_like<_Winc>
661 == __detail::__is_signed_integer_like<_Bound>))
662 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
664 template<typename _Winc, typename _Bound>
665 inline constexpr bool
666 enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
670 template<typename _Tp>
671 inline constexpr empty_view<_Tp> empty{};
675 template<typename _Tp>
678 operator()(_Tp&& __e) const
679 noexcept(noexcept(single_view<decay_t<_Tp>>(std::forward<_Tp>(__e))))
680 { return single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)); }
683 inline constexpr _Single single{};
687 template<typename _Tp>
690 operator()(_Tp&& __e) const
691 { return iota_view(std::forward<_Tp>(__e)); }
693 template<typename _Tp, typename _Up>
696 operator()(_Tp&& __e, _Up&& __f) const
697 { return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); }
700 inline constexpr _Iota iota{};
705 template<typename _Val, typename _CharT, typename _Traits>
706 concept __stream_extractable
707 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
708 } // namespace __detail
710 template<movable _Val, typename _CharT,
711 typename _Traits = char_traits<_CharT>>
712 requires default_initializable<_Val>
713 && __detail::__stream_extractable<_Val, _CharT, _Traits>
714 class basic_istream_view
715 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
719 basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
720 : _M_stream(std::__addressof(__stream))
726 *_M_stream >> _M_object;
727 return _Iterator{this};
730 constexpr default_sentinel_t
732 { return default_sentinel; }
735 basic_istream<_CharT, _Traits>* _M_stream;
736 _Val _M_object = _Val();
741 using iterator_concept = input_iterator_tag;
742 using difference_type = ptrdiff_t;
743 using value_type = _Val;
746 _Iterator(basic_istream_view* __parent) noexcept
747 : _M_parent(__parent)
750 _Iterator(const _Iterator&) = delete;
751 _Iterator(_Iterator&&) = default;
752 _Iterator& operator=(const _Iterator&) = delete;
753 _Iterator& operator=(_Iterator&&) = default;
758 *_M_parent->_M_stream >> _M_parent->_M_object;
768 { return _M_parent->_M_object; }
771 operator==(const _Iterator& __x, default_sentinel_t)
772 { return __x._M_at_end(); }
775 basic_istream_view* _M_parent;
779 { return !*_M_parent->_M_stream; }
785 template<typename _Val>
786 using istream_view = basic_istream_view<_Val, char>;
788 template<typename _Val>
789 using wistream_view = basic_istream_view<_Val, wchar_t>;
793 template<typename _Tp>
796 template<typename _CharT, typename _Traits>
799 operator()(basic_istream<_CharT, _Traits>& __e) const
800 { return basic_istream_view<_Tp, _CharT, _Traits>(__e); }
803 template<typename _Tp>
804 inline constexpr _Istream<_Tp> istream;
807 // C++20 24.7 [range.adaptors] Range adaptors
813 // Alias for a type that is conditionally present
814 // (and is an empty type otherwise).
815 // Data members using this alias should use [[no_unique_address]] so that
816 // they take no space when not needed.
817 template<bool _Present, typename _Tp>
818 using __maybe_present_t = __conditional_t<_Present, _Tp, _Empty>;
820 // Alias for a type that is conditionally const.
821 template<bool _Const, typename _Tp>
822 using __maybe_const_t = __conditional_t<_Const, const _Tp, _Tp>;
824 } // namespace __detail
826 namespace views::__adaptor
828 // True if the range adaptor _Adaptor can be applied with _Args.
829 template<typename _Adaptor, typename... _Args>
830 concept __adaptor_invocable
831 = requires { std::declval<_Adaptor>()(declval<_Args>()...); };
833 // True if the range adaptor non-closure _Adaptor can be partially applied
835 template<typename _Adaptor, typename... _Args>
836 concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
837 && (sizeof...(_Args) == _Adaptor::_S_arity - 1)
838 && (constructible_from<decay_t<_Args>, _Args> && ...);
840 template<typename _Adaptor, typename... _Args>
843 template<typename _Lhs, typename _Rhs>
846 // The base class of every range adaptor closure.
848 // The derived class should define the optional static data member
849 // _S_has_simple_call_op to true if the behavior of this adaptor is
850 // independent of the constness/value category of the adaptor object.
851 struct _RangeAdaptorClosure
853 // range | adaptor is equivalent to adaptor(range).
854 template<typename _Self, typename _Range>
855 requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
856 && __adaptor_invocable<_Self, _Range>
857 friend constexpr auto
858 operator|(_Range&& __r, _Self&& __self)
859 { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
861 // Compose the adaptors __lhs and __rhs into a pipeline, returning
862 // another range adaptor closure object.
863 template<typename _Lhs, typename _Rhs>
864 requires derived_from<_Lhs, _RangeAdaptorClosure>
865 && derived_from<_Rhs, _RangeAdaptorClosure>
866 friend constexpr auto
867 operator|(_Lhs __lhs, _Rhs __rhs)
868 { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
871 // The base class of every range adaptor non-closure.
873 // The static data member _Derived::_S_arity must contain the total number of
874 // arguments that the adaptor takes, and the class _Derived must introduce
875 // _RangeAdaptor::operator() into the class scope via a using-declaration.
877 // The optional static data member _Derived::_S_has_simple_extra_args should
878 // be defined to true if the behavior of this adaptor is independent of the
879 // constness/value category of the extra arguments. This data member could
880 // also be defined as a variable template parameterized by the types of the
882 template<typename _Derived>
885 // Partially apply the arguments __args to the range adaptor _Derived,
886 // returning a range adaptor closure object.
887 template<typename... _Args>
888 requires __adaptor_partial_app_viable<_Derived, _Args...>
890 operator()(_Args&&... __args) const
892 return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
896 // True if the range adaptor closure _Adaptor has a simple operator(), i.e.
897 // one that's not overloaded according to constness or value category of the
899 template<typename _Adaptor>
900 concept __closure_has_simple_call_op = _Adaptor::_S_has_simple_call_op;
902 // True if the behavior of the range adaptor non-closure _Adaptor is
903 // independent of the value category of its extra arguments _Args.
904 template<typename _Adaptor, typename... _Args>
905 concept __adaptor_has_simple_extra_args = _Adaptor::_S_has_simple_extra_args
906 || _Adaptor::template _S_has_simple_extra_args<_Args...>;
908 // A range adaptor closure that represents partial application of
909 // the range adaptor _Adaptor with arguments _Args.
910 template<typename _Adaptor, typename... _Args>
911 struct _Partial : _RangeAdaptorClosure
913 tuple<_Args...> _M_args;
916 _Partial(_Args... __args)
917 : _M_args(std::move(__args)...)
920 // Invoke _Adaptor with arguments __r, _M_args... according to the
921 // value category of this _Partial object.
922 template<typename _Range>
923 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
925 operator()(_Range&& __r) const &
927 auto __forwarder = [&__r] (const auto&... __args) {
928 return _Adaptor{}(std::forward<_Range>(__r), __args...);
930 return std::apply(__forwarder, _M_args);
933 template<typename _Range>
934 requires __adaptor_invocable<_Adaptor, _Range, _Args...>
936 operator()(_Range&& __r) &&
938 auto __forwarder = [&__r] (auto&... __args) {
939 return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...);
941 return std::apply(__forwarder, _M_args);
944 template<typename _Range>
946 operator()(_Range&& __r) const && = delete;
949 // A lightweight specialization of the above primary template for
950 // the common case where _Adaptor accepts a single extra argument.
951 template<typename _Adaptor, typename _Arg>
952 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
958 : _M_arg(std::move(__arg))
961 template<typename _Range>
962 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
964 operator()(_Range&& __r) const &
965 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
967 template<typename _Range>
968 requires __adaptor_invocable<_Adaptor, _Range, _Arg>
970 operator()(_Range&& __r) &&
971 { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
973 template<typename _Range>
975 operator()(_Range&& __r) const && = delete;
978 // Partial specialization of the primary template for the case where the extra
979 // arguments of the adaptor can always be safely and efficiently forwarded by
980 // const reference. This lets us get away with a single operator() overload,
981 // which makes overload resolution failure diagnostics more concise.
982 template<typename _Adaptor, typename... _Args>
983 requires __adaptor_has_simple_extra_args<_Adaptor, _Args...>
984 && (is_trivially_copyable_v<_Args> && ...)
985 struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure
987 tuple<_Args...> _M_args;
990 _Partial(_Args... __args)
991 : _M_args(std::move(__args)...)
994 // Invoke _Adaptor with arguments __r, const _M_args&... regardless
995 // of the value category of this _Partial object.
996 template<typename _Range>
997 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
999 operator()(_Range&& __r) const
1001 auto __forwarder = [&__r] (const auto&... __args) {
1002 return _Adaptor{}(std::forward<_Range>(__r), __args...);
1004 return std::apply(__forwarder, _M_args);
1007 static constexpr bool _S_has_simple_call_op = true;
1010 // A lightweight specialization of the above template for the common case
1011 // where _Adaptor accepts a single extra argument.
1012 template<typename _Adaptor, typename _Arg>
1013 requires __adaptor_has_simple_extra_args<_Adaptor, _Arg>
1014 && is_trivially_copyable_v<_Arg>
1015 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
1020 _Partial(_Arg __arg)
1021 : _M_arg(std::move(__arg))
1024 template<typename _Range>
1025 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
1027 operator()(_Range&& __r) const
1028 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
1030 static constexpr bool _S_has_simple_call_op = true;
1033 template<typename _Lhs, typename _Rhs, typename _Range>
1034 concept __pipe_invocable
1035 = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); };
1037 // A range adaptor closure that represents composition of the range
1038 // adaptor closures _Lhs and _Rhs.
1039 template<typename _Lhs, typename _Rhs>
1040 struct _Pipe : _RangeAdaptorClosure
1042 [[no_unique_address]] _Lhs _M_lhs;
1043 [[no_unique_address]] _Rhs _M_rhs;
1046 _Pipe(_Lhs __lhs, _Rhs __rhs)
1047 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
1050 // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this
1051 // range adaptor closure object.
1052 template<typename _Range>
1053 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1055 operator()(_Range&& __r) const &
1056 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1058 template<typename _Range>
1059 requires __pipe_invocable<_Lhs, _Rhs, _Range>
1061 operator()(_Range&& __r) &&
1062 { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); }
1064 template<typename _Range>
1066 operator()(_Range&& __r) const && = delete;
1069 // A partial specialization of the above primary template for the case where
1070 // both adaptor operands have a simple operator(). This in turn lets us
1071 // implement composition using a single simple operator(), which makes
1072 // overload resolution failure diagnostics more concise.
1073 template<typename _Lhs, typename _Rhs>
1074 requires __closure_has_simple_call_op<_Lhs>
1075 && __closure_has_simple_call_op<_Rhs>
1076 struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure
1078 [[no_unique_address]] _Lhs _M_lhs;
1079 [[no_unique_address]] _Rhs _M_rhs;
1082 _Pipe(_Lhs __lhs, _Rhs __rhs)
1083 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
1086 template<typename _Range>
1087 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1089 operator()(_Range&& __r) const
1090 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1092 static constexpr bool _S_has_simple_call_op = true;
1094 } // namespace views::__adaptor
1096 template<range _Range> requires is_object_v<_Range>
1097 class ref_view : public view_interface<ref_view<_Range>>
1102 static void _S_fun(_Range&); // not defined
1103 static void _S_fun(_Range&&) = delete;
1106 template<__detail::__different_from<ref_view> _Tp>
1107 requires convertible_to<_Tp, _Range&>
1108 && requires { _S_fun(declval<_Tp>()); }
1111 noexcept(noexcept(static_cast<_Range&>(std::declval<_Tp>())))
1112 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
1119 constexpr iterator_t<_Range>
1121 { return ranges::begin(*_M_r); }
1123 constexpr sentinel_t<_Range>
1125 { return ranges::end(*_M_r); }
1128 empty() const requires requires { ranges::empty(*_M_r); }
1129 { return ranges::empty(*_M_r); }
1132 size() const requires sized_range<_Range>
1133 { return ranges::size(*_M_r); }
1136 data() const requires contiguous_range<_Range>
1137 { return ranges::data(*_M_r); }
1140 template<typename _Range>
1141 ref_view(_Range&) -> ref_view<_Range>;
1143 template<typename _Tp>
1144 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
1150 template<typename _Range>
1151 concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
1153 template<typename _Range>
1154 concept __can_subrange = requires { subrange{std::declval<_Range>()}; };
1155 } // namespace __detail
1157 struct _All : __adaptor::_RangeAdaptorClosure
1159 template<typename _Range>
1160 static constexpr bool
1163 if constexpr (view<decay_t<_Range>>)
1164 return is_nothrow_constructible_v<decay_t<_Range>, _Range>;
1165 else if constexpr (__detail::__can_ref_view<_Range>)
1168 return noexcept(subrange{std::declval<_Range>()});
1171 template<viewable_range _Range>
1172 requires view<decay_t<_Range>>
1173 || __detail::__can_ref_view<_Range>
1174 || __detail::__can_subrange<_Range>
1176 operator() [[nodiscard]] (_Range&& __r) const
1177 noexcept(_S_noexcept<_Range>())
1179 if constexpr (view<decay_t<_Range>>)
1180 return std::forward<_Range>(__r);
1181 else if constexpr (__detail::__can_ref_view<_Range>)
1182 return ref_view{std::forward<_Range>(__r)};
1184 return subrange{std::forward<_Range>(__r)};
1187 static constexpr bool _S_has_simple_call_op = true;
1190 inline constexpr _All all;
1192 template<viewable_range _Range>
1193 using all_t = decltype(all(std::declval<_Range>()));
1194 } // namespace views
1198 template<typename _Tp>
1199 struct __non_propagating_cache
1201 // When _Tp is not an object type (e.g. is a reference type), we make
1202 // __non_propagating_cache<_Tp> empty rather than ill-formed so that
1203 // users can easily conditionally declare data members with this type
1204 // (such as join_view::_M_inner).
1207 template<typename _Tp>
1208 requires is_object_v<_Tp>
1209 struct __non_propagating_cache<_Tp>
1210 : protected _Optional_base<_Tp>
1212 __non_propagating_cache() = default;
1215 __non_propagating_cache(const __non_propagating_cache&) noexcept
1219 __non_propagating_cache(__non_propagating_cache&& __other) noexcept
1220 { __other._M_reset(); }
1222 constexpr __non_propagating_cache&
1223 operator=(const __non_propagating_cache& __other) noexcept
1225 if (std::__addressof(__other) != this)
1230 constexpr __non_propagating_cache&
1231 operator=(__non_propagating_cache&& __other) noexcept
1238 constexpr __non_propagating_cache&
1239 operator=(_Tp __val)
1242 this->_M_payload._M_construct(std::move(__val));
1247 operator bool() const noexcept
1248 { return this->_M_is_engaged(); }
1251 operator*() noexcept
1252 { return this->_M_get(); }
1254 constexpr const _Tp&
1255 operator*() const noexcept
1256 { return this->_M_get(); }
1258 template<typename _Iter>
1260 _M_emplace_deref(const _Iter& __i)
1263 auto __f = [] (auto& __x) { return *__x; };
1264 this->_M_payload._M_apply(_Optional_func{__f}, __i);
1265 return this->_M_get();
1269 template<range _Range>
1270 struct _CachedPosition
1273 _M_has_value() const
1276 constexpr iterator_t<_Range>
1277 _M_get(const _Range&) const
1279 __glibcxx_assert(false);
1280 __builtin_unreachable();
1284 _M_set(const _Range&, const iterator_t<_Range>&) const
1288 template<forward_range _Range>
1289 struct _CachedPosition<_Range>
1290 : protected __non_propagating_cache<iterator_t<_Range>>
1293 _M_has_value() const
1294 { return this->_M_is_engaged(); }
1296 constexpr iterator_t<_Range>
1297 _M_get(const _Range&) const
1299 __glibcxx_assert(_M_has_value());
1304 _M_set(const _Range&, const iterator_t<_Range>& __it)
1306 __glibcxx_assert(!_M_has_value());
1307 std::construct_at(std::__addressof(this->_M_payload._M_payload),
1309 this->_M_payload._M_engaged = true;
1313 template<random_access_range _Range>
1314 requires (sizeof(range_difference_t<_Range>)
1315 <= sizeof(iterator_t<_Range>))
1316 struct _CachedPosition<_Range>
1319 range_difference_t<_Range> _M_offset = -1;
1322 _CachedPosition() = default;
1325 _CachedPosition(const _CachedPosition&) = default;
1328 _CachedPosition(_CachedPosition&& __other) noexcept
1329 { *this = std::move(__other); }
1331 constexpr _CachedPosition&
1332 operator=(const _CachedPosition&) = default;
1334 constexpr _CachedPosition&
1335 operator=(_CachedPosition&& __other) noexcept
1337 // Propagate the cached offset, but invalidate the source.
1338 _M_offset = __other._M_offset;
1339 __other._M_offset = -1;
1344 _M_has_value() const
1345 { return _M_offset >= 0; }
1347 constexpr iterator_t<_Range>
1348 _M_get(_Range& __r) const
1350 __glibcxx_assert(_M_has_value());
1351 return ranges::begin(__r) + _M_offset;
1355 _M_set(_Range& __r, const iterator_t<_Range>& __it)
1357 __glibcxx_assert(!_M_has_value());
1358 _M_offset = __it - ranges::begin(__r);
1361 } // namespace __detail
1365 template<typename _Base>
1366 struct __filter_view_iter_cat
1369 template<forward_range _Base>
1370 struct __filter_view_iter_cat<_Base>
1376 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1377 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1378 return bidirectional_iterator_tag{};
1379 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1380 return forward_iterator_tag{};
1385 using iterator_category = decltype(_S_iter_cat());
1387 } // namespace __detail
1389 template<input_range _Vp,
1390 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1391 requires view<_Vp> && is_object_v<_Pred>
1392 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1397 struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
1400 static constexpr auto
1403 if constexpr (bidirectional_range<_Vp>)
1404 return bidirectional_iterator_tag{};
1405 else if constexpr (forward_range<_Vp>)
1406 return forward_iterator_tag{};
1408 return input_iterator_tag{};
1413 using _Vp_iter = iterator_t<_Vp>;
1415 _Vp_iter _M_current = _Vp_iter();
1416 filter_view* _M_parent = nullptr;
1419 using iterator_concept = decltype(_S_iter_concept());
1420 // iterator_category defined in __filter_view_iter_cat
1421 using value_type = range_value_t<_Vp>;
1422 using difference_type = range_difference_t<_Vp>;
1424 _Iterator() requires default_initializable<_Vp_iter> = default;
1427 _Iterator(filter_view* __parent, _Vp_iter __current)
1428 : _M_current(std::move(__current)),
1432 constexpr const _Vp_iter&
1433 base() const & noexcept
1434 { return _M_current; }
1438 { return std::move(_M_current); }
1440 constexpr range_reference_t<_Vp>
1442 { return *_M_current; }
1446 requires __detail::__has_arrow<_Vp_iter>
1447 && copyable<_Vp_iter>
1448 { return _M_current; }
1450 constexpr _Iterator&
1453 _M_current = ranges::find_if(std::move(++_M_current),
1454 ranges::end(_M_parent->_M_base),
1455 std::ref(*_M_parent->_M_pred));
1464 operator++(int) requires forward_range<_Vp>
1471 constexpr _Iterator&
1472 operator--() requires bidirectional_range<_Vp>
1476 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1481 operator--(int) requires bidirectional_range<_Vp>
1488 friend constexpr bool
1489 operator==(const _Iterator& __x, const _Iterator& __y)
1490 requires equality_comparable<_Vp_iter>
1491 { return __x._M_current == __y._M_current; }
1493 friend constexpr range_rvalue_reference_t<_Vp>
1494 iter_move(const _Iterator& __i)
1495 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1496 { return ranges::iter_move(__i._M_current); }
1498 friend constexpr void
1499 iter_swap(const _Iterator& __x, const _Iterator& __y)
1500 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1501 requires indirectly_swappable<_Vp_iter>
1502 { ranges::iter_swap(__x._M_current, __y._M_current); }
1508 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1511 __equal(const _Iterator& __i) const
1512 { return __i._M_current == _M_end; }
1515 _Sentinel() = default;
1518 _Sentinel(filter_view* __parent)
1519 : _M_end(ranges::end(__parent->_M_base))
1522 constexpr sentinel_t<_Vp>
1526 friend constexpr bool
1527 operator==(const _Iterator& __x, const _Sentinel& __y)
1528 { return __y.__equal(__x); }
1531 _Vp _M_base = _Vp();
1532 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1533 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1536 filter_view() requires (default_initializable<_Vp>
1537 && default_initializable<_Pred>)
1541 filter_view(_Vp __base, _Pred __pred)
1542 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
1546 base() const& requires copy_constructible<_Vp>
1551 { return std::move(_M_base); }
1553 constexpr const _Pred&
1555 { return *_M_pred; }
1560 if (_M_cached_begin._M_has_value())
1561 return {this, _M_cached_begin._M_get(_M_base)};
1563 __glibcxx_assert(_M_pred.has_value());
1564 auto __it = ranges::find_if(ranges::begin(_M_base),
1565 ranges::end(_M_base),
1566 std::ref(*_M_pred));
1567 _M_cached_begin._M_set(_M_base, __it);
1568 return {this, std::move(__it)};
1574 if constexpr (common_range<_Vp>)
1575 return _Iterator{this, ranges::end(_M_base)};
1577 return _Sentinel{this};
1581 template<typename _Range, typename _Pred>
1582 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1588 template<typename _Range, typename _Pred>
1589 concept __can_filter_view
1590 = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); };
1591 } // namespace __detail
1593 struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1595 template<viewable_range _Range, typename _Pred>
1596 requires __detail::__can_filter_view<_Range, _Pred>
1598 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const
1600 return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
1603 using _RangeAdaptor<_Filter>::operator();
1604 static constexpr int _S_arity = 2;
1605 static constexpr bool _S_has_simple_extra_args = true;
1608 inline constexpr _Filter filter;
1609 } // namespace views
1611 template<input_range _Vp, copy_constructible _Fp>
1612 requires view<_Vp> && is_object_v<_Fp>
1613 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1614 && std::__detail::__can_reference<invoke_result_t<_Fp&,
1615 range_reference_t<_Vp>>>
1616 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1619 template<bool _Const>
1620 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1622 template<bool _Const>
1626 template<bool _Const>
1627 requires forward_range<_Base<_Const>>
1628 struct __iter_cat<_Const>
1634 using _Base = transform_view::_Base<_Const>;
1635 using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1636 if constexpr (is_lvalue_reference_v<_Res>)
1639 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1640 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1641 return random_access_iterator_tag{};
1646 return input_iterator_tag{};
1649 using iterator_category = decltype(_S_iter_cat());
1652 template<bool _Const>
1655 template<bool _Const>
1656 struct _Iterator : __iter_cat<_Const>
1659 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1660 using _Base = transform_view::_Base<_Const>;
1665 if constexpr (random_access_range<_Base>)
1666 return random_access_iterator_tag{};
1667 else if constexpr (bidirectional_range<_Base>)
1668 return bidirectional_iterator_tag{};
1669 else if constexpr (forward_range<_Base>)
1670 return forward_iterator_tag{};
1672 return input_iterator_tag{};
1675 using _Base_iter = iterator_t<_Base>;
1677 _Base_iter _M_current = _Base_iter();
1678 _Parent* _M_parent = nullptr;
1681 using iterator_concept = decltype(_S_iter_concept());
1682 // iterator_category defined in __transform_view_iter_cat
1684 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1685 using difference_type = range_difference_t<_Base>;
1687 _Iterator() requires default_initializable<_Base_iter> = default;
1690 _Iterator(_Parent* __parent, _Base_iter __current)
1691 : _M_current(std::move(__current)),
1696 _Iterator(_Iterator<!_Const> __i)
1698 && convertible_to<iterator_t<_Vp>, _Base_iter>
1699 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1702 constexpr const _Base_iter&
1703 base() const & noexcept
1704 { return _M_current; }
1706 constexpr _Base_iter
1708 { return std::move(_M_current); }
1710 constexpr decltype(auto)
1712 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1713 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1715 constexpr _Iterator&
1727 operator++(int) requires forward_range<_Base>
1734 constexpr _Iterator&
1735 operator--() requires bidirectional_range<_Base>
1742 operator--(int) requires bidirectional_range<_Base>
1749 constexpr _Iterator&
1750 operator+=(difference_type __n) requires random_access_range<_Base>
1756 constexpr _Iterator&
1757 operator-=(difference_type __n) requires random_access_range<_Base>
1763 constexpr decltype(auto)
1764 operator[](difference_type __n) const
1765 requires random_access_range<_Base>
1766 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1768 friend constexpr bool
1769 operator==(const _Iterator& __x, const _Iterator& __y)
1770 requires equality_comparable<_Base_iter>
1771 { return __x._M_current == __y._M_current; }
1773 friend constexpr bool
1774 operator<(const _Iterator& __x, const _Iterator& __y)
1775 requires random_access_range<_Base>
1776 { return __x._M_current < __y._M_current; }
1778 friend constexpr bool
1779 operator>(const _Iterator& __x, const _Iterator& __y)
1780 requires random_access_range<_Base>
1781 { return __y < __x; }
1783 friend constexpr bool
1784 operator<=(const _Iterator& __x, const _Iterator& __y)
1785 requires random_access_range<_Base>
1786 { return !(__y < __x); }
1788 friend constexpr bool
1789 operator>=(const _Iterator& __x, const _Iterator& __y)
1790 requires random_access_range<_Base>
1791 { return !(__x < __y); }
1793 #ifdef __cpp_lib_three_way_comparison
1794 friend constexpr auto
1795 operator<=>(const _Iterator& __x, const _Iterator& __y)
1796 requires random_access_range<_Base>
1797 && three_way_comparable<_Base_iter>
1798 { return __x._M_current <=> __y._M_current; }
1801 friend constexpr _Iterator
1802 operator+(_Iterator __i, difference_type __n)
1803 requires random_access_range<_Base>
1804 { return {__i._M_parent, __i._M_current + __n}; }
1806 friend constexpr _Iterator
1807 operator+(difference_type __n, _Iterator __i)
1808 requires random_access_range<_Base>
1809 { return {__i._M_parent, __i._M_current + __n}; }
1811 friend constexpr _Iterator
1812 operator-(_Iterator __i, difference_type __n)
1813 requires random_access_range<_Base>
1814 { return {__i._M_parent, __i._M_current - __n}; }
1816 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1817 // 3483. transform_view::iterator's difference is overconstrained
1818 friend constexpr difference_type
1819 operator-(const _Iterator& __x, const _Iterator& __y)
1820 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1821 { return __x._M_current - __y._M_current; }
1823 friend constexpr decltype(auto)
1824 iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1826 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1827 return std::move(*__i);
1832 friend _Iterator<!_Const>;
1833 template<bool> friend struct _Sentinel;
1836 template<bool _Const>
1840 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1841 using _Base = transform_view::_Base<_Const>;
1843 template<bool _Const2>
1845 __distance_from(const _Iterator<_Const2>& __i) const
1846 { return _M_end - __i._M_current; }
1848 template<bool _Const2>
1850 __equal(const _Iterator<_Const2>& __i) const
1851 { return __i._M_current == _M_end; }
1853 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1856 _Sentinel() = default;
1859 _Sentinel(sentinel_t<_Base> __end)
1864 _Sentinel(_Sentinel<!_Const> __i)
1866 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1867 : _M_end(std::move(__i._M_end))
1870 constexpr sentinel_t<_Base>
1874 template<bool _Const2>
1875 requires sentinel_for<sentinel_t<_Base>,
1876 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1877 friend constexpr bool
1878 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1879 { return __y.__equal(__x); }
1881 template<bool _Const2,
1882 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1883 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1884 friend constexpr range_difference_t<_Base2>
1885 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1886 { return -__y.__distance_from(__x); }
1888 template<bool _Const2,
1889 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1890 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1891 friend constexpr range_difference_t<_Base2>
1892 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1893 { return __y.__distance_from(__x); }
1895 friend _Sentinel<!_Const>;
1898 _Vp _M_base = _Vp();
1899 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1902 transform_view() requires (default_initializable<_Vp>
1903 && default_initializable<_Fp>)
1907 transform_view(_Vp __base, _Fp __fun)
1908 : _M_base(std::move(__base)), _M_fun(std::move(__fun))
1912 base() const& requires copy_constructible<_Vp>
1913 { return _M_base ; }
1917 { return std::move(_M_base); }
1919 constexpr _Iterator<false>
1921 { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1923 constexpr _Iterator<true>
1925 requires range<const _Vp>
1926 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1927 { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1929 constexpr _Sentinel<false>
1931 { return _Sentinel<false>{ranges::end(_M_base)}; }
1933 constexpr _Iterator<false>
1934 end() requires common_range<_Vp>
1935 { return _Iterator<false>{this, ranges::end(_M_base)}; }
1937 constexpr _Sentinel<true>
1939 requires range<const _Vp>
1940 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1941 { return _Sentinel<true>{ranges::end(_M_base)}; }
1943 constexpr _Iterator<true>
1945 requires common_range<const _Vp>
1946 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1947 { return _Iterator<true>{this, ranges::end(_M_base)}; }
1950 size() requires sized_range<_Vp>
1951 { return ranges::size(_M_base); }
1954 size() const requires sized_range<const _Vp>
1955 { return ranges::size(_M_base); }
1958 template<typename _Range, typename _Fp>
1959 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1965 template<typename _Range, typename _Fp>
1966 concept __can_transform_view
1967 = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); };
1968 } // namespace __detail
1970 struct _Transform : __adaptor::_RangeAdaptor<_Transform>
1972 template<viewable_range _Range, typename _Fp>
1973 requires __detail::__can_transform_view<_Range, _Fp>
1975 operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const
1977 return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f));
1980 using _RangeAdaptor<_Transform>::operator();
1981 static constexpr int _S_arity = 2;
1982 static constexpr bool _S_has_simple_extra_args = true;
1985 inline constexpr _Transform transform;
1986 } // namespace views
1989 class take_view : public view_interface<take_view<_Vp>>
1992 template<bool _Const>
1993 using _CI = counted_iterator<
1994 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1996 template<bool _Const>
2000 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2001 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2004 _Sentinel() = default;
2007 _Sentinel(sentinel_t<_Base> __end)
2012 _Sentinel(_Sentinel<!_Const> __s)
2013 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2014 : _M_end(std::move(__s._M_end))
2017 constexpr sentinel_t<_Base>
2021 friend constexpr bool
2022 operator==(const _CI<_Const>& __y, const _Sentinel& __x)
2023 { return __y.count() == 0 || __y.base() == __x._M_end; }
2025 template<bool _OtherConst = !_Const,
2026 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2027 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2028 friend constexpr bool
2029 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
2030 { return __y.count() == 0 || __y.base() == __x._M_end; }
2032 friend _Sentinel<!_Const>;
2035 _Vp _M_base = _Vp();
2036 range_difference_t<_Vp> _M_count = 0;
2039 take_view() requires default_initializable<_Vp> = default;
2042 take_view(_Vp base, range_difference_t<_Vp> __count)
2043 : _M_base(std::move(base)), _M_count(std::move(__count))
2047 base() const& requires copy_constructible<_Vp>
2052 { return std::move(_M_base); }
2055 begin() requires (!__detail::__simple_view<_Vp>)
2057 if constexpr (sized_range<_Vp>)
2059 if constexpr (random_access_range<_Vp>)
2060 return ranges::begin(_M_base);
2064 return counted_iterator(ranges::begin(_M_base), __sz);
2068 return counted_iterator(ranges::begin(_M_base), _M_count);
2072 begin() const requires range<const _Vp>
2074 if constexpr (sized_range<const _Vp>)
2076 if constexpr (random_access_range<const _Vp>)
2077 return ranges::begin(_M_base);
2081 return counted_iterator(ranges::begin(_M_base), __sz);
2085 return counted_iterator(ranges::begin(_M_base), _M_count);
2089 end() requires (!__detail::__simple_view<_Vp>)
2091 if constexpr (sized_range<_Vp>)
2093 if constexpr (random_access_range<_Vp>)
2094 return ranges::begin(_M_base) + size();
2096 return default_sentinel;
2099 return _Sentinel<false>{ranges::end(_M_base)};
2103 end() const requires range<const _Vp>
2105 if constexpr (sized_range<const _Vp>)
2107 if constexpr (random_access_range<const _Vp>)
2108 return ranges::begin(_M_base) + size();
2110 return default_sentinel;
2113 return _Sentinel<true>{ranges::end(_M_base)};
2117 size() requires sized_range<_Vp>
2119 auto __n = ranges::size(_M_base);
2120 return std::min(__n, static_cast<decltype(__n)>(_M_count));
2124 size() const requires sized_range<const _Vp>
2126 auto __n = ranges::size(_M_base);
2127 return std::min(__n, static_cast<decltype(__n)>(_M_count));
2131 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2132 // 3447. Deduction guides for take_view and drop_view have different
2134 template<typename _Range>
2135 take_view(_Range&&, range_difference_t<_Range>)
2136 -> take_view<views::all_t<_Range>>;
2138 template<typename _Tp>
2139 inline constexpr bool enable_borrowed_range<take_view<_Tp>>
2140 = enable_borrowed_range<_Tp>;
2146 template<typename _Range>
2147 inline constexpr bool __is_empty_view = false;
2149 template<typename _Tp>
2150 inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
2152 template<typename _Range>
2153 inline constexpr bool __is_basic_string_view = false;
2155 template<typename _CharT, typename _Traits>
2156 inline constexpr bool __is_basic_string_view<basic_string_view<_CharT, _Traits>>
2159 template<typename _Range>
2160 inline constexpr bool __is_subrange = false;
2162 template<typename _Iter, typename _Sent, subrange_kind _Kind>
2163 inline constexpr bool __is_subrange<subrange<_Iter, _Sent, _Kind>> = true;
2165 template<typename _Range>
2166 inline constexpr bool __is_iota_view = false;
2168 template<typename _Winc, typename _Bound>
2169 inline constexpr bool __is_iota_view<iota_view<_Winc, _Bound>> = true;
2171 template<typename _Range, typename _Dp>
2172 concept __can_take_view
2173 = requires { take_view(std::declval<_Range>(), std::declval<_Dp>()); };
2174 } // namespace __detail
2176 struct _Take : __adaptor::_RangeAdaptor<_Take>
2178 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
2179 requires __detail::__can_take_view<_Range, _Dp>
2181 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
2183 using _Tp = remove_cvref_t<_Range>;
2184 if constexpr (__detail::__is_empty_view<_Tp>)
2186 else if constexpr (random_access_range<_Tp>
2188 && (std::__detail::__is_span<_Tp>
2189 || __detail::__is_basic_string_view<_Tp>
2190 || __detail::__is_subrange<_Tp>
2191 || __detail::__is_iota_view<_Tp>))
2193 __n = std::min<_Dp>(ranges::distance(__r), __n);
2194 auto __begin = ranges::begin(__r);
2195 auto __end = __begin + __n;
2196 if constexpr (std::__detail::__is_span<_Tp>)
2197 return span<typename _Tp::element_type>(__begin, __end);
2198 else if constexpr (__detail::__is_basic_string_view<_Tp>)
2199 return _Tp(__begin, __end);
2200 else if constexpr (__detail::__is_subrange<_Tp>)
2201 return subrange<iterator_t<_Tp>>(__begin, __end);
2203 return iota_view(*__begin, *__end);
2206 return take_view(std::forward<_Range>(__r), __n);
2209 using _RangeAdaptor<_Take>::operator();
2210 static constexpr int _S_arity = 2;
2211 // The count argument of views::take is not always simple -- it can be
2212 // e.g. a move-only class that's implicitly convertible to the difference
2213 // type. But an integer-like count argument is surely simple.
2214 template<typename _Tp>
2215 static constexpr bool _S_has_simple_extra_args
2216 = ranges::__detail::__is_integer_like<_Tp>;
2219 inline constexpr _Take take;
2220 } // namespace views
2222 template<view _Vp, typename _Pred>
2223 requires input_range<_Vp> && is_object_v<_Pred>
2224 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2225 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2227 template<bool _Const>
2231 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2233 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2234 const _Pred* _M_pred = nullptr;
2237 _Sentinel() = default;
2240 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2241 : _M_end(__end), _M_pred(__pred)
2245 _Sentinel(_Sentinel<!_Const> __s)
2246 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2247 : _M_end(__s._M_end), _M_pred(__s._M_pred)
2250 constexpr sentinel_t<_Base>
2251 base() const { return _M_end; }
2253 friend constexpr bool
2254 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2255 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2257 template<bool _OtherConst = !_Const,
2258 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2259 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2260 friend constexpr bool
2261 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
2262 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2264 friend _Sentinel<!_Const>;
2267 _Vp _M_base = _Vp();
2268 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2271 take_while_view() requires (default_initializable<_Vp>
2272 && default_initializable<_Pred>)
2276 take_while_view(_Vp base, _Pred __pred)
2277 : _M_base(std::move(base)), _M_pred(std::move(__pred))
2281 base() const& requires copy_constructible<_Vp>
2286 { return std::move(_M_base); }
2288 constexpr const _Pred&
2290 { return *_M_pred; }
2293 begin() requires (!__detail::__simple_view<_Vp>)
2294 { return ranges::begin(_M_base); }
2297 begin() const requires range<const _Vp>
2298 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2299 { return ranges::begin(_M_base); }
2302 end() requires (!__detail::__simple_view<_Vp>)
2303 { return _Sentinel<false>(ranges::end(_M_base),
2304 std::__addressof(*_M_pred)); }
2307 end() const requires range<const _Vp>
2308 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2309 { return _Sentinel<true>(ranges::end(_M_base),
2310 std::__addressof(*_M_pred)); }
2313 template<typename _Range, typename _Pred>
2314 take_while_view(_Range&&, _Pred)
2315 -> take_while_view<views::all_t<_Range>, _Pred>;
2321 template<typename _Range, typename _Pred>
2322 concept __can_take_while_view
2323 = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2324 } // namespace __detail
2326 struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
2328 template<viewable_range _Range, typename _Pred>
2329 requires __detail::__can_take_while_view<_Range, _Pred>
2331 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const
2333 return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
2336 using _RangeAdaptor<_TakeWhile>::operator();
2337 static constexpr int _S_arity = 2;
2338 static constexpr bool _S_has_simple_extra_args = true;
2341 inline constexpr _TakeWhile take_while;
2342 } // namespace views
2345 class drop_view : public view_interface<drop_view<_Vp>>
2348 _Vp _M_base = _Vp();
2349 range_difference_t<_Vp> _M_count = 0;
2351 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2352 // both random_access_range and sized_range. Otherwise, cache its result.
2353 static constexpr bool _S_needs_cached_begin
2354 = !(random_access_range<const _Vp> && sized_range<const _Vp>);
2355 [[no_unique_address]]
2356 __detail::__maybe_present_t<_S_needs_cached_begin,
2357 __detail::_CachedPosition<_Vp>>
2361 drop_view() requires default_initializable<_Vp> = default;
2364 drop_view(_Vp __base, range_difference_t<_Vp> __count)
2365 : _M_base(std::move(__base)), _M_count(__count)
2366 { __glibcxx_assert(__count >= 0); }
2369 base() const& requires copy_constructible<_Vp>
2374 { return std::move(_M_base); }
2376 // This overload is disabled for simple views with constant-time begin().
2379 requires (!(__detail::__simple_view<_Vp>
2380 && random_access_range<const _Vp>
2381 && sized_range<const _Vp>))
2383 if constexpr (_S_needs_cached_begin)
2384 if (_M_cached_begin._M_has_value())
2385 return _M_cached_begin._M_get(_M_base);
2387 auto __it = ranges::next(ranges::begin(_M_base),
2388 _M_count, ranges::end(_M_base));
2389 if constexpr (_S_needs_cached_begin)
2390 _M_cached_begin._M_set(_M_base, __it);
2394 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2395 // 3482. drop_view's const begin should additionally require sized_range
2398 requires random_access_range<const _Vp> && sized_range<const _Vp>
2400 return ranges::next(ranges::begin(_M_base), _M_count,
2401 ranges::end(_M_base));
2405 end() requires (!__detail::__simple_view<_Vp>)
2406 { return ranges::end(_M_base); }
2409 end() const requires range<const _Vp>
2410 { return ranges::end(_M_base); }
2413 size() requires sized_range<_Vp>
2415 const auto __s = ranges::size(_M_base);
2416 const auto __c = static_cast<decltype(__s)>(_M_count);
2417 return __s < __c ? 0 : __s - __c;
2421 size() const requires sized_range<const _Vp>
2423 const auto __s = ranges::size(_M_base);
2424 const auto __c = static_cast<decltype(__s)>(_M_count);
2425 return __s < __c ? 0 : __s - __c;
2429 template<typename _Range>
2430 drop_view(_Range&&, range_difference_t<_Range>)
2431 -> drop_view<views::all_t<_Range>>;
2433 template<typename _Tp>
2434 inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2435 = enable_borrowed_range<_Tp>;
2441 template<typename _Range, typename _Dp>
2442 concept __can_drop_view
2443 = requires { drop_view(std::declval<_Range>(), std::declval<_Dp>()); };
2444 } // namespace __detail
2446 struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2448 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
2449 requires __detail::__can_drop_view<_Range, _Dp>
2451 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
2453 using _Tp = remove_cvref_t<_Range>;
2454 if constexpr (__detail::__is_empty_view<_Tp>)
2456 else if constexpr (random_access_range<_Tp>
2458 && (std::__detail::__is_span<_Tp>
2459 || __detail::__is_basic_string_view<_Tp>
2460 || __detail::__is_iota_view<_Tp>
2461 || __detail::__is_subrange<_Tp>))
2463 __n = std::min<_Dp>(ranges::distance(__r), __n);
2464 auto __begin = ranges::begin(__r) + __n;
2465 auto __end = ranges::end(__r);
2466 if constexpr (std::__detail::__is_span<_Tp>)
2467 return span<typename _Tp::element_type>(__begin, __end);
2468 else if constexpr (__detail::__is_subrange<_Tp>)
2470 if constexpr (_Tp::_S_store_size)
2472 using ranges::__detail::__to_unsigned_like;
2473 auto __m = ranges::distance(__r) - __n;
2474 return _Tp(__begin, __end, __to_unsigned_like(__m));
2477 return _Tp(__begin, __end);
2480 return _Tp(__begin, __end);
2483 return drop_view(std::forward<_Range>(__r), __n);
2486 using _RangeAdaptor<_Drop>::operator();
2487 static constexpr int _S_arity = 2;
2488 template<typename _Tp>
2489 static constexpr bool _S_has_simple_extra_args
2490 = _Take::_S_has_simple_extra_args<_Tp>;
2493 inline constexpr _Drop drop;
2494 } // namespace views
2496 template<view _Vp, typename _Pred>
2497 requires input_range<_Vp> && is_object_v<_Pred>
2498 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2499 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2502 _Vp _M_base = _Vp();
2503 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2504 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2507 drop_while_view() requires (default_initializable<_Vp>
2508 && default_initializable<_Pred>)
2512 drop_while_view(_Vp __base, _Pred __pred)
2513 : _M_base(std::move(__base)), _M_pred(std::move(__pred))
2517 base() const& requires copy_constructible<_Vp>
2522 { return std::move(_M_base); }
2524 constexpr const _Pred&
2526 { return *_M_pred; }
2531 if (_M_cached_begin._M_has_value())
2532 return _M_cached_begin._M_get(_M_base);
2534 __glibcxx_assert(_M_pred.has_value());
2535 auto __it = ranges::find_if_not(ranges::begin(_M_base),
2536 ranges::end(_M_base),
2537 std::cref(*_M_pred));
2538 _M_cached_begin._M_set(_M_base, __it);
2544 { return ranges::end(_M_base); }
2547 template<typename _Range, typename _Pred>
2548 drop_while_view(_Range&&, _Pred)
2549 -> drop_while_view<views::all_t<_Range>, _Pred>;
2551 template<typename _Tp, typename _Pred>
2552 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2553 = enable_borrowed_range<_Tp>;
2559 template<typename _Range, typename _Pred>
2560 concept __can_drop_while_view
2561 = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2562 } // namespace __detail
2564 struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2566 template<viewable_range _Range, typename _Pred>
2567 requires __detail::__can_drop_while_view<_Range, _Pred>
2569 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const
2571 return drop_while_view(std::forward<_Range>(__r),
2572 std::forward<_Pred>(__p));
2575 using _RangeAdaptor<_DropWhile>::operator();
2576 static constexpr int _S_arity = 2;
2577 static constexpr bool _S_has_simple_extra_args = true;
2580 inline constexpr _DropWhile drop_while;
2581 } // namespace views
2583 template<input_range _Vp>
2584 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2585 class join_view : public view_interface<join_view<_Vp>>
2588 using _InnerRange = range_reference_t<_Vp>;
2590 template<bool _Const>
2591 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2593 template<bool _Const>
2594 using _Outer_iter = iterator_t<_Base<_Const>>;
2596 template<bool _Const>
2597 using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
2599 template<bool _Const>
2600 static constexpr bool _S_ref_is_glvalue
2601 = is_reference_v<range_reference_t<_Base<_Const>>>;
2603 template<bool _Const>
2607 template<bool _Const>
2608 requires _S_ref_is_glvalue<_Const>
2609 && forward_range<_Base<_Const>>
2610 && forward_range<range_reference_t<_Base<_Const>>>
2611 struct __iter_cat<_Const>
2614 static constexpr auto
2617 using _Outer_iter = join_view::_Outer_iter<_Const>;
2618 using _Inner_iter = join_view::_Inner_iter<_Const>;
2619 using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category;
2620 using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category;
2621 if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
2622 && derived_from<_InnerCat, bidirectional_iterator_tag>
2623 && common_range<range_reference_t<_Base<_Const>>>)
2624 return bidirectional_iterator_tag{};
2625 else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
2626 && derived_from<_InnerCat, forward_iterator_tag>)
2627 return forward_iterator_tag{};
2629 return input_iterator_tag{};
2632 using iterator_category = decltype(_S_iter_cat());
2635 template<bool _Const>
2638 template<bool _Const>
2639 struct _Iterator : __iter_cat<_Const>
2642 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2643 using _Base = join_view::_Base<_Const>;
2645 static constexpr bool _S_ref_is_glvalue
2646 = join_view::_S_ref_is_glvalue<_Const>;
2651 auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& {
2652 if constexpr (_S_ref_is_glvalue)
2655 return _M_parent->_M_inner._M_emplace_deref(__x);
2658 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2660 auto&& __inner = __update_inner(_M_outer);
2661 _M_inner = ranges::begin(__inner);
2662 if (_M_inner != ranges::end(__inner))
2666 if constexpr (_S_ref_is_glvalue)
2667 _M_inner = _Inner_iter();
2670 static constexpr auto
2673 if constexpr (_S_ref_is_glvalue
2674 && bidirectional_range<_Base>
2675 && bidirectional_range<range_reference_t<_Base>>
2676 && common_range<range_reference_t<_Base>>)
2677 return bidirectional_iterator_tag{};
2678 else if constexpr (_S_ref_is_glvalue
2679 && forward_range<_Base>
2680 && forward_range<range_reference_t<_Base>>)
2681 return forward_iterator_tag{};
2683 return input_iterator_tag{};
2686 using _Outer_iter = join_view::_Outer_iter<_Const>;
2687 using _Inner_iter = join_view::_Inner_iter<_Const>;
2689 _Outer_iter _M_outer = _Outer_iter();
2690 _Inner_iter _M_inner = _Inner_iter();
2691 _Parent* _M_parent = nullptr;
2694 using iterator_concept = decltype(_S_iter_concept());
2695 // iterator_category defined in __join_view_iter_cat
2696 using value_type = range_value_t<range_reference_t<_Base>>;
2697 using difference_type
2698 = common_type_t<range_difference_t<_Base>,
2699 range_difference_t<range_reference_t<_Base>>>;
2701 _Iterator() requires (default_initializable<_Outer_iter>
2702 && default_initializable<_Inner_iter>)
2706 _Iterator(_Parent* __parent, _Outer_iter __outer)
2707 : _M_outer(std::move(__outer)),
2712 _Iterator(_Iterator<!_Const> __i)
2714 && convertible_to<iterator_t<_Vp>, _Outer_iter>
2715 && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2716 : _M_outer(std::move(__i._M_outer)), _M_inner(std::move(__i._M_inner)),
2717 _M_parent(__i._M_parent)
2720 constexpr decltype(auto)
2722 { return *_M_inner; }
2724 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2725 // 3500. join_view::iterator::operator->() is bogus
2726 constexpr _Inner_iter
2728 requires __detail::__has_arrow<_Inner_iter>
2729 && copyable<_Inner_iter>
2730 { return _M_inner; }
2732 constexpr _Iterator&
2735 auto&& __inner_range = [this] () -> auto&& {
2736 if constexpr (_S_ref_is_glvalue)
2739 return *_M_parent->_M_inner;
2741 if (++_M_inner == ranges::end(__inner_range))
2755 requires _S_ref_is_glvalue && forward_range<_Base>
2756 && forward_range<range_reference_t<_Base>>
2763 constexpr _Iterator&
2765 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2766 && bidirectional_range<range_reference_t<_Base>>
2767 && common_range<range_reference_t<_Base>>
2769 if (_M_outer == ranges::end(_M_parent->_M_base))
2770 _M_inner = ranges::end(*--_M_outer);
2771 while (_M_inner == ranges::begin(*_M_outer))
2772 _M_inner = ranges::end(*--_M_outer);
2779 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2780 && bidirectional_range<range_reference_t<_Base>>
2781 && common_range<range_reference_t<_Base>>
2788 friend constexpr bool
2789 operator==(const _Iterator& __x, const _Iterator& __y)
2790 requires _S_ref_is_glvalue
2791 && equality_comparable<_Outer_iter>
2792 && equality_comparable<_Inner_iter>
2794 return (__x._M_outer == __y._M_outer
2795 && __x._M_inner == __y._M_inner);
2798 friend constexpr decltype(auto)
2799 iter_move(const _Iterator& __i)
2800 noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2801 { return ranges::iter_move(__i._M_inner); }
2803 friend constexpr void
2804 iter_swap(const _Iterator& __x, const _Iterator& __y)
2805 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2806 requires indirectly_swappable<_Inner_iter>
2807 { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2809 friend _Iterator<!_Const>;
2810 template<bool> friend struct _Sentinel;
2813 template<bool _Const>
2817 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2818 using _Base = join_view::_Base<_Const>;
2820 template<bool _Const2>
2822 __equal(const _Iterator<_Const2>& __i) const
2823 { return __i._M_outer == _M_end; }
2825 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2828 _Sentinel() = default;
2831 _Sentinel(_Parent* __parent)
2832 : _M_end(ranges::end(__parent->_M_base))
2836 _Sentinel(_Sentinel<!_Const> __s)
2837 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2838 : _M_end(std::move(__s._M_end))
2841 template<bool _Const2>
2842 requires sentinel_for<sentinel_t<_Base>,
2843 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2844 friend constexpr bool
2845 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2846 { return __y.__equal(__x); }
2848 friend _Sentinel<!_Const>;
2851 _Vp _M_base = _Vp();
2852 [[no_unique_address]]
2853 __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
2856 join_view() requires default_initializable<_Vp> = default;
2859 join_view(_Vp __base)
2860 : _M_base(std::move(__base))
2864 base() const& requires copy_constructible<_Vp>
2869 { return std::move(_M_base); }
2874 constexpr bool __use_const
2875 = (__detail::__simple_view<_Vp>
2876 && is_reference_v<range_reference_t<_Vp>>);
2877 return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2882 requires input_range<const _Vp>
2883 && is_reference_v<range_reference_t<const _Vp>>
2885 return _Iterator<true>{this, ranges::begin(_M_base)};
2891 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2892 && forward_range<_InnerRange>
2893 && common_range<_Vp> && common_range<_InnerRange>)
2894 return _Iterator<__detail::__simple_view<_Vp>>{this,
2895 ranges::end(_M_base)};
2897 return _Sentinel<__detail::__simple_view<_Vp>>{this};
2902 requires input_range<const _Vp>
2903 && is_reference_v<range_reference_t<const _Vp>>
2905 if constexpr (forward_range<const _Vp>
2906 && is_reference_v<range_reference_t<const _Vp>>
2907 && forward_range<range_reference_t<const _Vp>>
2908 && common_range<const _Vp>
2909 && common_range<range_reference_t<const _Vp>>)
2910 return _Iterator<true>{this, ranges::end(_M_base)};
2912 return _Sentinel<true>{this};
2916 template<typename _Range>
2917 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2923 template<typename _Range>
2924 concept __can_join_view
2925 = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
2926 } // namespace __detail
2928 struct _Join : __adaptor::_RangeAdaptorClosure
2930 template<viewable_range _Range>
2931 requires __detail::__can_join_view<_Range>
2933 operator() [[nodiscard]] (_Range&& __r) const
2935 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2936 // 3474. Nesting join_views is broken because of CTAD
2937 return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
2940 static constexpr bool _S_has_simple_call_op = true;
2943 inline constexpr _Join join;
2944 } // namespace views
2949 struct __require_constant;
2951 template<typename _Range>
2952 concept __tiny_range = sized_range<_Range>
2954 { typename __require_constant<remove_reference_t<_Range>::size()>; }
2955 && (remove_reference_t<_Range>::size() <= 1);
2957 template<typename _Base>
2958 struct __lazy_split_view_outer_iter_cat
2961 template<forward_range _Base>
2962 struct __lazy_split_view_outer_iter_cat<_Base>
2963 { using iterator_category = input_iterator_tag; };
2965 template<typename _Base>
2966 struct __lazy_split_view_inner_iter_cat
2969 template<forward_range _Base>
2970 struct __lazy_split_view_inner_iter_cat<_Base>
2973 static constexpr auto
2976 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2977 if constexpr (derived_from<_Cat, forward_iterator_tag>)
2978 return forward_iterator_tag{};
2983 using iterator_category = decltype(_S_iter_cat());
2987 template<input_range _Vp, forward_range _Pattern>
2988 requires view<_Vp> && view<_Pattern>
2989 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2991 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2992 class lazy_split_view : public view_interface<lazy_split_view<_Vp, _Pattern>>
2995 template<bool _Const>
2996 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2998 template<bool _Const>
3001 template<bool _Const>
3003 : __detail::__lazy_split_view_outer_iter_cat<_Base<_Const>>
3006 using _Parent = __detail::__maybe_const_t<_Const, lazy_split_view>;
3007 using _Base = lazy_split_view::_Base<_Const>;
3011 { return __current() == ranges::end(_M_parent->_M_base) && !_M_trailing_empty; }
3013 // [range.lazy.split.outer] p1
3014 // Many of the following specifications refer to the notional member
3015 // current of outer-iterator. current is equivalent to current_ if
3016 // V models forward_range, and parent_->current_ otherwise.
3018 __current() noexcept
3020 if constexpr (forward_range<_Vp>)
3023 return *_M_parent->_M_current;
3027 __current() const noexcept
3029 if constexpr (forward_range<_Vp>)
3032 return *_M_parent->_M_current;
3035 _Parent* _M_parent = nullptr;
3037 // XXX: _M_current is present only if "V models forward_range"
3038 [[no_unique_address]]
3039 __detail::__maybe_present_t<forward_range<_Vp>,
3040 iterator_t<_Base>> _M_current;
3041 bool _M_trailing_empty = false;
3044 using iterator_concept = __conditional_t<forward_range<_Base>,
3045 forward_iterator_tag,
3046 input_iterator_tag>;
3047 // iterator_category defined in __lazy_split_view_outer_iter_cat
3048 using difference_type = range_difference_t<_Base>;
3050 struct value_type : view_interface<value_type>
3053 _OuterIter _M_i = _OuterIter();
3056 value_type() = default;
3059 value_type(_OuterIter __i)
3060 : _M_i(std::move(__i))
3063 constexpr _InnerIter<_Const>
3065 { return _InnerIter<_Const>{_M_i}; }
3067 constexpr default_sentinel_t
3069 { return default_sentinel; }
3072 _OuterIter() = default;
3075 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
3076 : _M_parent(__parent)
3080 _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
3081 requires forward_range<_Base>
3082 : _M_parent(__parent),
3083 _M_current(std::move(__current))
3087 _OuterIter(_OuterIter<!_Const> __i)
3089 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3090 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
3093 constexpr value_type
3095 { return value_type{*this}; }
3097 constexpr _OuterIter&
3100 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3101 // 3505. lazy_split_view::outer-iterator::operator++ misspecified
3102 const auto __end = ranges::end(_M_parent->_M_base);
3103 if (__current() == __end)
3105 _M_trailing_empty = false;
3108 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
3109 if (__pbegin == __pend)
3111 else if constexpr (__detail::__tiny_range<_Pattern>)
3113 __current() = ranges::find(std::move(__current()), __end,
3115 if (__current() != __end)
3118 if (__current() == __end)
3119 _M_trailing_empty = true;
3126 = ranges::mismatch(__current(), __end, __pbegin, __pend);
3130 if (__current() == __end)
3131 _M_trailing_empty = true;
3134 } while (++__current() != __end);
3138 constexpr decltype(auto)
3141 if constexpr (forward_range<_Base>)
3151 friend constexpr bool
3152 operator==(const _OuterIter& __x, const _OuterIter& __y)
3153 requires forward_range<_Base>
3155 return __x._M_current == __y._M_current
3156 && __x._M_trailing_empty == __y._M_trailing_empty;
3159 friend constexpr bool
3160 operator==(const _OuterIter& __x, default_sentinel_t)
3161 { return __x.__at_end(); };
3163 friend _OuterIter<!_Const>;
3164 friend _InnerIter<_Const>;
3167 template<bool _Const>
3169 : __detail::__lazy_split_view_inner_iter_cat<_Base<_Const>>
3172 using _Base = lazy_split_view::_Base<_Const>;
3177 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
3178 auto __end = ranges::end(_M_i._M_parent->_M_base);
3179 if constexpr (__detail::__tiny_range<_Pattern>)
3181 const auto& __cur = _M_i_current();
3184 if (__pcur == __pend)
3185 return _M_incremented;
3186 return *__cur == *__pcur;
3190 auto __cur = _M_i_current();
3193 if (__pcur == __pend)
3194 return _M_incremented;
3197 if (*__cur != *__pcur)
3199 if (++__pcur == __pend)
3201 } while (++__cur != __end);
3207 _M_i_current() noexcept
3208 { return _M_i.__current(); }
3211 _M_i_current() const noexcept
3212 { return _M_i.__current(); }
3214 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
3215 bool _M_incremented = false;
3218 using iterator_concept
3219 = typename _OuterIter<_Const>::iterator_concept;
3220 // iterator_category defined in __lazy_split_view_inner_iter_cat
3221 using value_type = range_value_t<_Base>;
3222 using difference_type = range_difference_t<_Base>;
3224 _InnerIter() = default;
3227 _InnerIter(_OuterIter<_Const> __i)
3228 : _M_i(std::move(__i))
3231 constexpr const iterator_t<_Base>&
3232 base() const& noexcept
3233 { return _M_i_current(); }
3235 constexpr iterator_t<_Base>
3236 base() && requires forward_range<_Vp>
3237 { return std::move(_M_i_current()); }
3239 constexpr decltype(auto)
3241 { return *_M_i_current(); }
3243 constexpr _InnerIter&
3246 _M_incremented = true;
3247 if constexpr (!forward_range<_Base>)
3248 if constexpr (_Pattern::size() == 0)
3254 constexpr decltype(auto)
3257 if constexpr (forward_range<_Base>)
3267 friend constexpr bool
3268 operator==(const _InnerIter& __x, const _InnerIter& __y)
3269 requires forward_range<_Base>
3270 { return __x._M_i == __y._M_i; }
3272 friend constexpr bool
3273 operator==(const _InnerIter& __x, default_sentinel_t)
3274 { return __x.__at_end(); }
3276 friend constexpr decltype(auto)
3277 iter_move(const _InnerIter& __i)
3278 noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
3279 { return ranges::iter_move(__i._M_i_current()); }
3281 friend constexpr void
3282 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
3283 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
3284 __y._M_i_current())))
3285 requires indirectly_swappable<iterator_t<_Base>>
3286 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
3289 _Vp _M_base = _Vp();
3290 _Pattern _M_pattern = _Pattern();
3291 // XXX: _M_current is "present only if !forward_range<V>"
3292 [[no_unique_address]]
3293 __detail::__maybe_present_t<!forward_range<_Vp>,
3294 __detail::__non_propagating_cache<iterator_t<_Vp>>> _M_current;
3298 lazy_split_view() requires (default_initializable<_Vp>
3299 && default_initializable<_Pattern>)
3303 lazy_split_view(_Vp __base, _Pattern __pattern)
3304 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
3307 template<input_range _Range>
3308 requires constructible_from<_Vp, views::all_t<_Range>>
3309 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3311 lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
3312 : _M_base(views::all(std::forward<_Range>(__r))),
3313 _M_pattern(views::single(std::move(__e)))
3317 base() const& requires copy_constructible<_Vp>
3322 { return std::move(_M_base); }
3327 if constexpr (forward_range<_Vp>)
3329 constexpr bool __simple
3330 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
3331 return _OuterIter<__simple>{this, ranges::begin(_M_base)};
3335 _M_current = ranges::begin(_M_base);
3336 return _OuterIter<false>{this};
3341 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3343 return _OuterIter<true>{this, ranges::begin(_M_base)};
3347 end() requires forward_range<_Vp> && common_range<_Vp>
3349 constexpr bool __simple
3350 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
3351 return _OuterIter<__simple>{this, ranges::end(_M_base)};
3357 if constexpr (forward_range<_Vp>
3358 && forward_range<const _Vp>
3359 && common_range<const _Vp>)
3360 return _OuterIter<true>{this, ranges::end(_M_base)};
3362 return default_sentinel;
3366 template<typename _Range, typename _Pattern>
3367 lazy_split_view(_Range&&, _Pattern&&)
3368 -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3370 template<input_range _Range>
3371 lazy_split_view(_Range&&, range_value_t<_Range>)
3372 -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3378 template<typename _Range, typename _Pattern>
3379 concept __can_lazy_split_view
3380 = requires { lazy_split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3381 } // namespace __detail
3383 struct _LazySplit : __adaptor::_RangeAdaptor<_LazySplit>
3385 template<viewable_range _Range, typename _Pattern>
3386 requires __detail::__can_lazy_split_view<_Range, _Pattern>
3388 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const
3390 return lazy_split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3393 using _RangeAdaptor<_LazySplit>::operator();
3394 static constexpr int _S_arity = 2;
3395 // The pattern argument of views::lazy_split is not always simple -- it can be
3396 // a non-view range, the value category of which affects whether the call
3397 // is well-formed. But a scalar or a view pattern argument is surely
3399 template<typename _Pattern>
3400 static constexpr bool _S_has_simple_extra_args
3401 = is_scalar_v<_Pattern> || (view<_Pattern>
3402 && copy_constructible<_Pattern>);
3405 inline constexpr _LazySplit lazy_split;
3406 } // namespace views
3408 template<forward_range _Vp, forward_range _Pattern>
3409 requires view<_Vp> && view<_Pattern>
3410 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
3412 class split_view : public view_interface<split_view<_Vp, _Pattern>>
3415 _Vp _M_base = _Vp();
3416 _Pattern _M_pattern = _Pattern();
3417 __detail::__non_propagating_cache<subrange<iterator_t<_Vp>>> _M_cached_begin;
3423 split_view() requires (default_initializable<_Vp>
3424 && default_initializable<_Pattern>)
3428 split_view(_Vp __base, _Pattern __pattern)
3429 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
3432 template<forward_range _Range>
3433 requires constructible_from<_Vp, views::all_t<_Range>>
3434 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3436 split_view(_Range&& __r, range_value_t<_Range> __e)
3437 : _M_base(views::all(std::forward<_Range>(__r))),
3438 _M_pattern(views::single(std::move(__e)))
3442 base() const& requires copy_constructible<_Vp>
3447 { return std::move(_M_base); }
3452 if (!_M_cached_begin)
3453 _M_cached_begin = _M_find_next(ranges::begin(_M_base));
3454 return {this, ranges::begin(_M_base), *_M_cached_begin};
3460 if constexpr (common_range<_Vp>)
3461 return _Iterator{this, ranges::end(_M_base), {}};
3463 return _Sentinel{this};
3466 constexpr subrange<iterator_t<_Vp>>
3467 _M_find_next(iterator_t<_Vp> __it)
3469 auto [__b, __e] = ranges::search(subrange(__it, ranges::end(_M_base)), _M_pattern);
3470 if (__b != ranges::end(_M_base) && ranges::empty(_M_pattern))
3482 split_view* _M_parent = nullptr;
3483 iterator_t<_Vp> _M_cur = iterator_t<_Vp>();
3484 subrange<iterator_t<_Vp>> _M_next = subrange<iterator_t<_Vp>>();
3485 bool _M_trailing_empty = false;
3487 friend struct _Sentinel;
3490 using iterator_concept = forward_iterator_tag;
3491 using iterator_category = input_iterator_tag;
3492 using value_type = subrange<iterator_t<_Vp>>;
3493 using difference_type = range_difference_t<_Vp>;
3495 _Iterator() = default;
3498 _Iterator(split_view* __parent,
3499 iterator_t<_Vp> __current,
3500 subrange<iterator_t<_Vp>> __next)
3501 : _M_parent(__parent),
3502 _M_cur(std::move(__current)),
3503 _M_next(std::move(__next))
3506 constexpr iterator_t<_Vp>
3510 constexpr value_type
3512 { return {_M_cur, _M_next.begin()}; }
3514 constexpr _Iterator&
3517 _M_cur = _M_next.begin();
3518 if (_M_cur != ranges::end(_M_parent->_M_base))
3520 _M_cur = _M_next.end();
3521 if (_M_cur == ranges::end(_M_parent->_M_base))
3523 _M_trailing_empty = true;
3524 _M_next = {_M_cur, _M_cur};
3527 _M_next = _M_parent->_M_find_next(_M_cur);
3530 _M_trailing_empty = false;
3542 friend constexpr bool
3543 operator==(const _Iterator& __x, const _Iterator& __y)
3545 return __x._M_cur == __y._M_cur
3546 && __x._M_trailing_empty == __y._M_trailing_empty;
3553 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
3556 _M_equal(const _Iterator& __x) const
3557 { return __x._M_cur == _M_end && !__x._M_trailing_empty; }
3560 _Sentinel() = default;
3563 _Sentinel(split_view* __parent)
3564 : _M_end(ranges::end(__parent->_M_base))
3567 friend constexpr bool
3568 operator==(const _Iterator& __x, const _Sentinel& __y)
3569 { return __y._M_equal(__x); }
3573 template<typename _Range, typename _Pattern>
3574 split_view(_Range&&, _Pattern&&)
3575 -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3577 template<forward_range _Range>
3578 split_view(_Range&&, range_value_t<_Range>)
3579 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3585 template<typename _Range, typename _Pattern>
3586 concept __can_split_view
3587 = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3588 } // namespace __detail
3590 struct _Split : __adaptor::_RangeAdaptor<_Split>
3592 template<viewable_range _Range, typename _Pattern>
3593 requires __detail::__can_split_view<_Range, _Pattern>
3595 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const
3597 return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3600 using _RangeAdaptor<_Split>::operator();
3601 static constexpr int _S_arity = 2;
3602 template<typename _Pattern>
3603 static constexpr bool _S_has_simple_extra_args
3604 = _LazySplit::_S_has_simple_extra_args<_Pattern>;
3607 inline constexpr _Split split;
3608 } // namespace views
3614 template<input_or_output_iterator _Iter>
3616 operator() [[nodiscard]] (_Iter __i, iter_difference_t<_Iter> __n) const
3618 if constexpr (contiguous_iterator<_Iter>)
3619 return span(std::__to_address(__i), __n);
3620 else if constexpr (random_access_iterator<_Iter>)
3621 return subrange(__i, __i + __n);
3623 return subrange(counted_iterator(std::move(__i), __n),
3628 inline constexpr _Counted counted{};
3629 } // namespace views
3632 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3633 class common_view : public view_interface<common_view<_Vp>>
3636 _Vp _M_base = _Vp();
3639 common_view() requires default_initializable<_Vp> = default;
3642 common_view(_Vp __r)
3643 : _M_base(std::move(__r))
3646 /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3647 template<viewable_range _Range>
3648 requires (!common_range<_Range>)
3649 && constructible_from<_Vp, views::all_t<_Range>>
3651 common_view(_Range&& __r)
3652 : _M_base(views::all(std::forward<_Range>(__r)))
3657 base() const& requires copy_constructible<_Vp>
3662 { return std::move(_M_base); }
3667 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3668 return ranges::begin(_M_base);
3670 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3671 (ranges::begin(_M_base));
3675 begin() const requires range<const _Vp>
3677 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3678 return ranges::begin(_M_base);
3680 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3681 (ranges::begin(_M_base));
3687 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3688 return ranges::begin(_M_base) + ranges::size(_M_base);
3690 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3691 (ranges::end(_M_base));
3695 end() const requires range<const _Vp>
3697 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3698 return ranges::begin(_M_base) + ranges::size(_M_base);
3700 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3701 (ranges::end(_M_base));
3705 size() requires sized_range<_Vp>
3706 { return ranges::size(_M_base); }
3709 size() const requires sized_range<const _Vp>
3710 { return ranges::size(_M_base); }
3713 template<typename _Range>
3714 common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3716 template<typename _Tp>
3717 inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3718 = enable_borrowed_range<_Tp>;
3724 template<typename _Range>
3725 concept __already_common = common_range<_Range>
3726 && requires { views::all(std::declval<_Range>()); };
3728 template<typename _Range>
3729 concept __can_common_view
3730 = requires { common_view{std::declval<_Range>()}; };
3731 } // namespace __detail
3733 struct _Common : __adaptor::_RangeAdaptorClosure
3735 template<viewable_range _Range>
3736 requires __detail::__already_common<_Range>
3737 || __detail::__can_common_view<_Range>
3739 operator() [[nodiscard]] (_Range&& __r) const
3741 if constexpr (__detail::__already_common<_Range>)
3742 return views::all(std::forward<_Range>(__r));
3744 return common_view{std::forward<_Range>(__r)};
3747 static constexpr bool _S_has_simple_call_op = true;
3750 inline constexpr _Common common;
3751 } // namespace views
3754 requires bidirectional_range<_Vp>
3755 class reverse_view : public view_interface<reverse_view<_Vp>>
3758 static constexpr bool _S_needs_cached_begin
3759 = !common_range<_Vp> && !(random_access_range<_Vp>
3760 && sized_sentinel_for<sentinel_t<_Vp>,
3763 _Vp _M_base = _Vp();
3764 [[no_unique_address]]
3765 __detail::__maybe_present_t<_S_needs_cached_begin,
3766 __detail::_CachedPosition<_Vp>>
3770 reverse_view() requires default_initializable<_Vp> = default;
3773 reverse_view(_Vp __r)
3774 : _M_base(std::move(__r))
3778 base() const& requires copy_constructible<_Vp>
3783 { return std::move(_M_base); }
3785 constexpr reverse_iterator<iterator_t<_Vp>>
3788 if constexpr (_S_needs_cached_begin)
3789 if (_M_cached_begin._M_has_value())
3790 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3792 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3793 if constexpr (_S_needs_cached_begin)
3794 _M_cached_begin._M_set(_M_base, __it);
3795 return std::make_reverse_iterator(std::move(__it));
3799 begin() requires common_range<_Vp>
3800 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3803 begin() const requires common_range<const _Vp>
3804 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3806 constexpr reverse_iterator<iterator_t<_Vp>>
3808 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3811 end() const requires common_range<const _Vp>
3812 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3815 size() requires sized_range<_Vp>
3816 { return ranges::size(_M_base); }
3819 size() const requires sized_range<const _Vp>
3820 { return ranges::size(_M_base); }
3823 template<typename _Range>
3824 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3826 template<typename _Tp>
3827 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3828 = enable_borrowed_range<_Tp>;
3835 inline constexpr bool __is_reversible_subrange = false;
3837 template<typename _Iter, subrange_kind _Kind>
3838 inline constexpr bool
3839 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3840 reverse_iterator<_Iter>,
3844 inline constexpr bool __is_reverse_view = false;
3846 template<typename _Vp>
3847 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3849 template<typename _Range>
3850 concept __can_reverse_view
3851 = requires { reverse_view{std::declval<_Range>()}; };
3852 } // namespace __detail
3854 struct _Reverse : __adaptor::_RangeAdaptorClosure
3856 template<viewable_range _Range>
3857 requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3858 || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3859 || __detail::__can_reverse_view<_Range>
3861 operator() [[nodiscard]] (_Range&& __r) const
3863 using _Tp = remove_cvref_t<_Range>;
3864 if constexpr (__detail::__is_reverse_view<_Tp>)
3865 return std::forward<_Range>(__r).base();
3866 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3868 using _Iter = decltype(ranges::begin(__r).base());
3869 if constexpr (sized_range<_Tp>)
3870 return subrange<_Iter, _Iter, subrange_kind::sized>
3871 {__r.end().base(), __r.begin().base(), __r.size()};
3873 return subrange<_Iter, _Iter, subrange_kind::unsized>
3874 {__r.end().base(), __r.begin().base()};
3877 return reverse_view{std::forward<_Range>(__r)};
3880 static constexpr bool _S_has_simple_call_op = true;
3883 inline constexpr _Reverse reverse;
3884 } // namespace views
3888 template<typename _Tp, size_t _Nm>
3889 concept __has_tuple_element = requires(_Tp __t)
3891 typename tuple_size<_Tp>::type;
3892 requires _Nm < tuple_size_v<_Tp>;
3893 typename tuple_element_t<_Nm, _Tp>;
3894 { std::get<_Nm>(__t) }
3895 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3898 template<typename _Tp, size_t _Nm>
3899 concept __returnable_element
3900 = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
3903 template<input_range _Vp, size_t _Nm>
3905 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3906 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3908 && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
3909 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3912 elements_view() requires default_initializable<_Vp> = default;
3915 elements_view(_Vp base)
3916 : _M_base(std::move(base))
3920 base() const& requires copy_constructible<_Vp>
3925 { return std::move(_M_base); }
3928 begin() requires (!__detail::__simple_view<_Vp>)
3929 { return _Iterator<false>(ranges::begin(_M_base)); }
3932 begin() const requires range<const _Vp>
3933 { return _Iterator<true>(ranges::begin(_M_base)); }
3936 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3937 { return _Sentinel<false>{ranges::end(_M_base)}; }
3940 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3941 { return _Iterator<false>{ranges::end(_M_base)}; }
3944 end() const requires range<const _Vp>
3945 { return _Sentinel<true>{ranges::end(_M_base)}; }
3948 end() const requires common_range<const _Vp>
3949 { return _Iterator<true>{ranges::end(_M_base)}; }
3952 size() requires sized_range<_Vp>
3953 { return ranges::size(_M_base); }
3956 size() const requires sized_range<const _Vp>
3957 { return ranges::size(_M_base); }
3960 template<bool _Const>
3961 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3963 template<bool _Const>
3967 template<bool _Const>
3968 requires forward_range<_Base<_Const>>
3969 struct __iter_cat<_Const>
3972 static auto _S_iter_cat()
3974 using _Base = elements_view::_Base<_Const>;
3975 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3976 using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
3977 if constexpr (!is_lvalue_reference_v<_Res>)
3978 return input_iterator_tag{};
3979 else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
3980 return random_access_iterator_tag{};
3985 using iterator_category = decltype(_S_iter_cat());
3988 template<bool _Const>
3991 template<bool _Const>
3992 struct _Iterator : __iter_cat<_Const>
3995 using _Base = elements_view::_Base<_Const>;
3997 iterator_t<_Base> _M_current = iterator_t<_Base>();
3999 static constexpr decltype(auto)
4000 _S_get_element(const iterator_t<_Base>& __i)
4002 if constexpr (is_reference_v<range_reference_t<_Base>>)
4003 return std::get<_Nm>(*__i);
4006 using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
4007 return static_cast<_Et>(std::get<_Nm>(*__i));
4014 if constexpr (random_access_range<_Base>)
4015 return random_access_iterator_tag{};
4016 else if constexpr (bidirectional_range<_Base>)
4017 return bidirectional_iterator_tag{};
4018 else if constexpr (forward_range<_Base>)
4019 return forward_iterator_tag{};
4021 return input_iterator_tag{};
4024 friend _Iterator<!_Const>;
4027 using iterator_concept = decltype(_S_iter_concept());
4028 // iterator_category defined in elements_view::__iter_cat
4030 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
4031 using difference_type = range_difference_t<_Base>;
4033 _Iterator() requires default_initializable<iterator_t<_Base>> = default;
4036 _Iterator(iterator_t<_Base> current)
4037 : _M_current(std::move(current))
4041 _Iterator(_Iterator<!_Const> i)
4042 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
4043 : _M_current(std::move(i._M_current))
4046 constexpr const iterator_t<_Base>&
4047 base() const& noexcept
4048 { return _M_current; }
4050 constexpr iterator_t<_Base>
4052 { return std::move(_M_current); }
4054 constexpr decltype(auto)
4056 { return _S_get_element(_M_current); }
4058 constexpr _Iterator&
4070 operator++(int) requires forward_range<_Base>
4077 constexpr _Iterator&
4078 operator--() requires bidirectional_range<_Base>
4085 operator--(int) requires bidirectional_range<_Base>
4092 constexpr _Iterator&
4093 operator+=(difference_type __n)
4094 requires random_access_range<_Base>
4100 constexpr _Iterator&
4101 operator-=(difference_type __n)
4102 requires random_access_range<_Base>
4108 constexpr decltype(auto)
4109 operator[](difference_type __n) const
4110 requires random_access_range<_Base>
4111 { return _S_get_element(_M_current + __n); }
4113 friend constexpr bool
4114 operator==(const _Iterator& __x, const _Iterator& __y)
4115 requires equality_comparable<iterator_t<_Base>>
4116 { return __x._M_current == __y._M_current; }
4118 friend constexpr bool
4119 operator<(const _Iterator& __x, const _Iterator& __y)
4120 requires random_access_range<_Base>
4121 { return __x._M_current < __y._M_current; }
4123 friend constexpr bool
4124 operator>(const _Iterator& __x, const _Iterator& __y)
4125 requires random_access_range<_Base>
4126 { return __y._M_current < __x._M_current; }
4128 friend constexpr bool
4129 operator<=(const _Iterator& __x, const _Iterator& __y)
4130 requires random_access_range<_Base>
4131 { return !(__y._M_current > __x._M_current); }
4133 friend constexpr bool
4134 operator>=(const _Iterator& __x, const _Iterator& __y)
4135 requires random_access_range<_Base>
4136 { return !(__x._M_current > __y._M_current); }
4138 #ifdef __cpp_lib_three_way_comparison
4139 friend constexpr auto
4140 operator<=>(const _Iterator& __x, const _Iterator& __y)
4141 requires random_access_range<_Base>
4142 && three_way_comparable<iterator_t<_Base>>
4143 { return __x._M_current <=> __y._M_current; }
4146 friend constexpr _Iterator
4147 operator+(const _Iterator& __x, difference_type __y)
4148 requires random_access_range<_Base>
4149 { return _Iterator{__x} += __y; }
4151 friend constexpr _Iterator
4152 operator+(difference_type __x, const _Iterator& __y)
4153 requires random_access_range<_Base>
4154 { return __y + __x; }
4156 friend constexpr _Iterator
4157 operator-(const _Iterator& __x, difference_type __y)
4158 requires random_access_range<_Base>
4159 { return _Iterator{__x} -= __y; }
4161 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4162 // 3483. transform_view::iterator's difference is overconstrained
4163 friend constexpr difference_type
4164 operator-(const _Iterator& __x, const _Iterator& __y)
4165 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
4166 { return __x._M_current - __y._M_current; }
4168 template <bool> friend struct _Sentinel;
4171 template<bool _Const>
4175 template<bool _Const2>
4177 _M_equal(const _Iterator<_Const2>& __x) const
4178 { return __x._M_current == _M_end; }
4180 template<bool _Const2>
4182 _M_distance_from(const _Iterator<_Const2>& __i) const
4183 { return _M_end - __i._M_current; }
4185 using _Base = elements_view::_Base<_Const>;
4186 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
4189 _Sentinel() = default;
4192 _Sentinel(sentinel_t<_Base> __end)
4193 : _M_end(std::move(__end))
4197 _Sentinel(_Sentinel<!_Const> __other)
4199 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
4200 : _M_end(std::move(__other._M_end))
4203 constexpr sentinel_t<_Base>
4207 template<bool _Const2>
4208 requires sentinel_for<sentinel_t<_Base>,
4209 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
4210 friend constexpr bool
4211 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
4212 { return __y._M_equal(__x); }
4214 template<bool _Const2,
4215 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
4216 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
4217 friend constexpr range_difference_t<_Base2>
4218 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
4219 { return -__y._M_distance_from(__x); }
4221 template<bool _Const2,
4222 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
4223 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
4224 friend constexpr range_difference_t<_Base2>
4225 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
4226 { return __x._M_distance_from(__y); }
4228 friend _Sentinel<!_Const>;
4231 _Vp _M_base = _Vp();
4234 template<typename _Tp, size_t _Nm>
4235 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
4236 = enable_borrowed_range<_Tp>;
4238 template<typename _Range>
4239 using keys_view = elements_view<views::all_t<_Range>, 0>;
4241 template<typename _Range>
4242 using values_view = elements_view<views::all_t<_Range>, 1>;
4248 template<size_t _Nm, typename _Range>
4249 concept __can_elements_view
4250 = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
4251 } // namespace __detail
4253 template<size_t _Nm>
4254 struct _Elements : __adaptor::_RangeAdaptorClosure
4256 template<viewable_range _Range>
4257 requires __detail::__can_elements_view<_Nm, _Range>
4259 operator() [[nodiscard]] (_Range&& __r) const
4261 return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
4264 static constexpr bool _S_has_simple_call_op = true;
4267 template<size_t _Nm>
4268 inline constexpr _Elements<_Nm> elements;
4269 inline constexpr auto keys = elements<0>;
4270 inline constexpr auto values = elements<1>;
4271 } // namespace views
4273 } // namespace ranges
4275 namespace views = ranges::views;
4277 _GLIBCXX_END_NAMESPACE_VERSION
4279 #endif // library concepts
4281 #endif /* _GLIBCXX_RANGES */