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>
46 #include <bits/ranges_util.h>
47 #include <bits/refwrap.h>
50 * @defgroup ranges Ranges
52 * Components for dealing with ranges of elements.
55 namespace std _GLIBCXX_VISIBILITY(default)
57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
60 // [range.access] customization point objects
61 // [range.req] range and view concepts
62 // [range.dangling] dangling iterator handling
63 // Defined in <bits/ranges_base.h>
65 // [view.interface] View interface
66 // [range.subrange] Sub-ranges
67 // Defined in <bits/ranges_util.h>
69 // C++20 24.6 [range.factories] Range factories
71 /// A view that contains no elements.
72 template<typename _Tp> requires is_object_v<_Tp>
74 : public view_interface<empty_view<_Tp>>
77 static constexpr _Tp* begin() noexcept { return nullptr; }
78 static constexpr _Tp* end() noexcept { return nullptr; }
79 static constexpr _Tp* data() noexcept { return nullptr; }
80 static constexpr size_t size() noexcept { return 0; }
81 static constexpr bool empty() noexcept { return true; }
84 template<typename _Tp>
85 inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true;
89 template<typename _Tp>
90 concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>;
92 template<__boxable _Tp>
93 struct __box : std::optional<_Tp>
95 using std::optional<_Tp>::optional;
99 noexcept(is_nothrow_default_constructible_v<_Tp>)
100 requires default_initializable<_Tp>
101 : std::optional<_Tp>{std::in_place}
104 __box(const __box&) = default;
105 __box(__box&&) = default;
107 using std::optional<_Tp>::operator=;
109 // _GLIBCXX_RESOLVE_LIB_DEFECTS
110 // 3477. Simplify constraints for semiregular-box
112 operator=(const __box& __that)
113 noexcept(is_nothrow_copy_constructible_v<_Tp>)
114 requires (!copyable<_Tp>)
117 this->emplace(*__that);
124 operator=(__box&& __that)
125 noexcept(is_nothrow_move_constructible_v<_Tp>)
126 requires (!movable<_Tp>)
129 this->emplace(std::move(*__that));
136 // For types which are already semiregular, this specialization of the
137 // semiregular wrapper stores the object directly without going through
138 // std::optional. It provides just the subset of the primary template's
139 // API that we currently use.
140 template<__boxable _Tp> requires semiregular<_Tp>
144 [[no_unique_address]] _Tp _M_value = _Tp();
150 __box(const _Tp& __t)
151 noexcept(is_nothrow_copy_constructible_v<_Tp>)
157 noexcept(is_nothrow_move_constructible_v<_Tp>)
158 : _M_value{std::move(__t)}
161 template<typename... _Args>
162 requires constructible_from<_Tp, _Args...>
164 __box(in_place_t, _Args&&... __args)
165 noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
166 : _M_value{std::forward<_Args>(__args)...}
170 has_value() const noexcept
178 operator*() const noexcept
182 operator->() noexcept
183 { return &_M_value; }
186 operator->() const noexcept
187 { return &_M_value; }
189 } // namespace __detail
191 /// A view that contains exactly one element.
192 template<copy_constructible _Tp> requires is_object_v<_Tp>
193 class single_view : public view_interface<single_view<_Tp>>
196 single_view() = default;
199 single_view(const _Tp& __t)
204 single_view(_Tp&& __t)
205 : _M_value(std::move(__t))
208 // _GLIBCXX_RESOLVE_LIB_DEFECTS
209 // 3428. single_view's in place constructor should be explicit
210 template<typename... _Args>
211 requires constructible_from<_Tp, _Args...>
213 single_view(in_place_t, _Args&&... __args)
214 : _M_value{in_place, std::forward<_Args>(__args)...}
222 begin() const noexcept
227 { return data() + 1; }
231 { return data() + 1; }
233 static constexpr size_t
239 { return _M_value.operator->(); }
242 data() const noexcept
243 { return _M_value.operator->(); }
246 [[no_unique_address]] __detail::__box<_Tp> _M_value;
251 template<typename _Wp>
252 constexpr auto __to_signed_like(_Wp __w) noexcept
254 if constexpr (!integral<_Wp>)
255 return iter_difference_t<_Wp>();
256 else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
257 return iter_difference_t<_Wp>(__w);
258 else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
259 return ptrdiff_t(__w);
260 else if constexpr (sizeof(long long) > sizeof(_Wp))
261 return (long long)(__w);
262 #ifdef __SIZEOF_INT128__
263 else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
264 return __int128(__w);
267 return __max_diff_type(__w);
270 template<typename _Wp>
271 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
273 template<typename _It>
274 concept __decrementable = incrementable<_It>
277 { --__i } -> same_as<_It&>;
278 { __i-- } -> same_as<_It>;
281 template<typename _It>
282 concept __advanceable = __decrementable<_It> && totally_ordered<_It>
283 && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
285 { __i += __n } -> same_as<_It&>;
286 { __i -= __n } -> same_as<_It&>;
290 { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
293 template<typename _Winc>
294 struct __iota_view_iter_cat
297 template<incrementable _Winc>
298 struct __iota_view_iter_cat<_Winc>
299 { using iterator_category = input_iterator_tag; };
300 } // namespace __detail
302 template<weakly_incrementable _Winc,
303 semiregular _Bound = unreachable_sentinel_t>
304 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
305 && semiregular<_Winc>
306 class iota_view : public view_interface<iota_view<_Winc, _Bound>>
311 struct _Iterator : __detail::__iota_view_iter_cat<_Winc>
317 using namespace __detail;
318 if constexpr (__advanceable<_Winc>)
319 return random_access_iterator_tag{};
320 else if constexpr (__decrementable<_Winc>)
321 return bidirectional_iterator_tag{};
322 else if constexpr (incrementable<_Winc>)
323 return forward_iterator_tag{};
325 return input_iterator_tag{};
329 using iterator_concept = decltype(_S_iter_concept());
330 // iterator_category defined in __iota_view_iter_cat
331 using value_type = _Winc;
332 using difference_type = __detail::__iota_diff_t<_Winc>;
334 _Iterator() = default;
337 _Iterator(_Winc __value)
338 : _M_value(__value) { }
341 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
356 operator++(int) requires incrementable<_Winc>
364 operator--() requires __detail::__decrementable<_Winc>
371 operator--(int) requires __detail::__decrementable<_Winc>
379 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
381 using __detail::__is_integer_like;
382 using __detail::__is_signed_integer_like;
383 if constexpr (__is_integer_like<_Winc>
384 && !__is_signed_integer_like<_Winc>)
386 if (__n >= difference_type(0))
387 _M_value += static_cast<_Winc>(__n);
389 _M_value -= static_cast<_Winc>(-__n);
397 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
399 using __detail::__is_integer_like;
400 using __detail::__is_signed_integer_like;
401 if constexpr (__is_integer_like<_Winc>
402 && !__is_signed_integer_like<_Winc>)
404 if (__n >= difference_type(0))
405 _M_value -= static_cast<_Winc>(__n);
407 _M_value += static_cast<_Winc>(-__n);
415 operator[](difference_type __n) const
416 requires __detail::__advanceable<_Winc>
417 { return _Winc(_M_value + __n); }
419 friend constexpr bool
420 operator==(const _Iterator& __x, const _Iterator& __y)
421 requires equality_comparable<_Winc>
422 { return __x._M_value == __y._M_value; }
424 friend constexpr bool
425 operator<(const _Iterator& __x, const _Iterator& __y)
426 requires totally_ordered<_Winc>
427 { return __x._M_value < __y._M_value; }
429 friend constexpr bool
430 operator>(const _Iterator& __x, const _Iterator& __y)
431 requires totally_ordered<_Winc>
432 { return __y < __x; }
434 friend constexpr bool
435 operator<=(const _Iterator& __x, const _Iterator& __y)
436 requires totally_ordered<_Winc>
437 { return !(__y < __x); }
439 friend constexpr bool
440 operator>=(const _Iterator& __x, const _Iterator& __y)
441 requires totally_ordered<_Winc>
442 { return !(__x < __y); }
444 #ifdef __cpp_lib_three_way_comparison
445 friend constexpr auto
446 operator<=>(const _Iterator& __x, const _Iterator& __y)
447 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
448 { return __x._M_value <=> __y._M_value; }
451 friend constexpr _Iterator
452 operator+(_Iterator __i, difference_type __n)
453 requires __detail::__advanceable<_Winc>
454 { return __i += __n; }
456 friend constexpr _Iterator
457 operator+(difference_type __n, _Iterator __i)
458 requires __detail::__advanceable<_Winc>
459 { return __i += __n; }
461 friend constexpr _Iterator
462 operator-(_Iterator __i, difference_type __n)
463 requires __detail::__advanceable<_Winc>
464 { return __i -= __n; }
466 friend constexpr difference_type
467 operator-(const _Iterator& __x, const _Iterator& __y)
468 requires __detail::__advanceable<_Winc>
470 using __detail::__is_integer_like;
471 using __detail::__is_signed_integer_like;
472 using _Dt = difference_type;
473 if constexpr (__is_integer_like<_Winc>)
475 if constexpr (__is_signed_integer_like<_Winc>)
476 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
478 return (__y._M_value > __x._M_value)
479 ? _Dt(-_Dt(__y._M_value - __x._M_value))
480 : _Dt(__x._M_value - __y._M_value);
483 return __x._M_value - __y._M_value;
487 _Winc _M_value = _Winc();
496 _M_equal(const _Iterator& __x) const
497 { return __x._M_value == _M_bound; }
499 _Bound _M_bound = _Bound();
502 _Sentinel() = default;
505 _Sentinel(_Bound __bound)
506 : _M_bound(__bound) { }
508 friend constexpr bool
509 operator==(const _Iterator& __x, const _Sentinel& __y)
510 { return __y._M_equal(__x); }
512 friend constexpr iter_difference_t<_Winc>
513 operator-(const _Iterator& __x, const _Sentinel& __y)
514 requires sized_sentinel_for<_Bound, _Winc>
515 { return __x._M_value - __y._M_bound; }
517 friend constexpr iter_difference_t<_Winc>
518 operator-(const _Sentinel& __x, const _Iterator& __y)
519 requires sized_sentinel_for<_Bound, _Winc>
520 { return -(__y - __x); }
523 _Winc _M_value = _Winc();
524 [[no_unique_address]] _Bound _M_bound = _Bound();
527 iota_view() = default;
530 iota_view(_Winc __value)
535 iota_view(type_identity_t<_Winc> __value,
536 type_identity_t<_Bound> __bound)
537 : _M_value(__value), _M_bound(__bound)
539 if constexpr (totally_ordered_with<_Winc, _Bound>)
540 __glibcxx_assert( bool(__value <= __bound) );
544 begin() const { return _Iterator{_M_value}; }
549 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
550 return unreachable_sentinel;
552 return _Sentinel{_M_bound};
556 end() const requires same_as<_Winc, _Bound>
557 { return _Iterator{_M_bound}; }
561 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
562 || (integral<_Winc> && integral<_Bound>)
563 || sized_sentinel_for<_Bound, _Winc>
565 using __detail::__is_integer_like;
566 using __detail::__to_unsigned_like;
567 if constexpr (integral<_Winc> && integral<_Bound>)
569 using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>;
570 return _Up(_M_bound) - _Up(_M_value);
572 else if constexpr (__is_integer_like<_Winc>)
573 return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
575 return __to_unsigned_like(_M_bound - _M_value);
579 template<typename _Winc, typename _Bound>
580 requires (!__detail::__is_integer_like<_Winc>
581 || !__detail::__is_integer_like<_Bound>
582 || (__detail::__is_signed_integer_like<_Winc>
583 == __detail::__is_signed_integer_like<_Bound>))
584 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
586 template<weakly_incrementable _Winc, semiregular _Bound>
587 inline constexpr bool
588 enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
592 template<typename _Tp>
593 inline constexpr empty_view<_Tp> empty{};
597 template<typename _Tp>
599 operator()(_Tp&& __e) const
600 { return single_view{std::forward<_Tp>(__e)}; }
603 inline constexpr _Single single{};
607 template<typename _Tp>
609 operator()(_Tp&& __e) const
610 { return iota_view{std::forward<_Tp>(__e)}; }
612 template<typename _Tp, typename _Up>
614 operator()(_Tp&& __e, _Up&& __f) const
615 { return iota_view{std::forward<_Tp>(__e), std::forward<_Up>(__f)}; }
618 inline constexpr _Iota iota{};
623 template<typename _Val, typename _CharT, typename _Traits>
624 concept __stream_extractable
625 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
626 } // namespace __detail
628 template<movable _Val, typename _CharT, typename _Traits>
629 requires default_initializable<_Val>
630 && __detail::__stream_extractable<_Val, _CharT, _Traits>
631 class basic_istream_view
632 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
635 basic_istream_view() = default;
638 basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
639 : _M_stream(std::__addressof(__stream))
645 if (_M_stream != nullptr)
646 *_M_stream >> _M_object;
647 return _Iterator{this};
650 constexpr default_sentinel_t
652 { return default_sentinel; }
655 basic_istream<_CharT, _Traits>* _M_stream = nullptr;
656 _Val _M_object = _Val();
661 using iterator_concept = input_iterator_tag;
662 using difference_type = ptrdiff_t;
663 using value_type = _Val;
665 _Iterator() = default;
668 _Iterator(basic_istream_view* __parent) noexcept
669 : _M_parent(__parent)
672 _Iterator(const _Iterator&) = delete;
673 _Iterator(_Iterator&&) = default;
674 _Iterator& operator=(const _Iterator&) = delete;
675 _Iterator& operator=(_Iterator&&) = default;
680 __glibcxx_assert(_M_parent->_M_stream != nullptr);
681 *_M_parent->_M_stream >> _M_parent->_M_object;
692 __glibcxx_assert(_M_parent->_M_stream != nullptr);
693 return _M_parent->_M_object;
697 operator==(const _Iterator& __x, default_sentinel_t)
698 { return __x._M_at_end(); }
701 basic_istream_view* _M_parent = nullptr;
705 { return _M_parent == nullptr || !*_M_parent->_M_stream; }
711 template<typename _Val, typename _CharT, typename _Traits>
712 basic_istream_view<_Val, _CharT, _Traits>
713 istream_view(basic_istream<_CharT, _Traits>& __s)
714 { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
716 // C++20 24.7 [range.adaptors] Range adaptors
722 // Alias for a type that is conditionally present
723 // (and is an empty type otherwise).
724 // Data members using this alias should use [[no_unique_address]] so that
725 // they take no space when not needed.
726 template<bool _Present, typename _Tp>
727 using __maybe_present_t = conditional_t<_Present, _Tp, _Empty>;
729 // Alias for a type that is conditionally const.
730 template<bool _Const, typename _Tp>
731 using __maybe_const_t = conditional_t<_Const, const _Tp, _Tp>;
733 } // namespace __detail
735 namespace views::__adaptor
737 // True if the range adaptor _Adaptor can be applied with _Args.
738 template<typename _Adaptor, typename... _Args>
739 concept __adaptor_invocable
740 = requires { std::declval<_Adaptor>()(declval<_Args>()...); };
742 // True if the range adaptor non-closure _Adaptor can be partially applied
744 template<typename _Adaptor, typename... _Args>
745 concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
746 && (sizeof...(_Args) == _Adaptor::_S_arity - 1)
747 && (constructible_from<decay_t<_Args>, _Args> && ...);
749 template<typename _Adaptor, typename... _Args>
752 template<typename _Lhs, typename _Rhs>
755 // The base class of every range adaptor closure.
756 struct _RangeAdaptorClosure
758 // range | adaptor is equivalent to adaptor(range).
759 template<typename _Self, typename _Range>
760 requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
761 && __adaptor_invocable<_Self, _Range>
762 friend constexpr auto
763 operator|(_Range&& __r, _Self&& __self)
764 { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
766 // Compose the adaptors __lhs and __rhs into a pipeline, returning
767 // another range adaptor closure object.
768 template<typename _Lhs, typename _Rhs>
769 requires derived_from<_Lhs, _RangeAdaptorClosure>
770 && derived_from<_Rhs, _RangeAdaptorClosure>
771 friend constexpr auto
772 operator|(_Lhs __lhs, _Rhs __rhs)
773 { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
776 // The base class of every range adaptor non-closure.
778 // The static data member _Derived::_S_arity must contain the total number of
779 // arguments that the adaptor takes, and the class _Derived must introduce
780 // _RangeAdaptor::operator() into the class scope via a using-declaration.
781 template<typename _Derived>
784 // Partially apply the arguments __args to the range adaptor _Derived,
785 // returning a range adaptor closure object.
786 template<typename... _Args>
787 requires __adaptor_partial_app_viable<_Derived, _Args...>
789 operator()(_Args&&... __args) const
791 return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
795 // A range adaptor closure that represents partial application of
796 // the range adaptor _Adaptor with arguments _Args.
797 template<typename _Adaptor, typename... _Args>
798 struct _Partial : _RangeAdaptorClosure
800 tuple<_Args...> _M_args;
803 _Partial(_Args... __args)
804 : _M_args(std::move(__args)...)
807 // Invoke _Adaptor with arguments __r, _M_args... according to the
808 // value category of the range adaptor closure object.
809 template<typename _Range>
810 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
812 operator()(_Range&& __r) const &
814 auto __forwarder = [&__r] (const auto&... __args) {
815 return _Adaptor{}(std::forward<_Range>(__r), __args...);
817 return std::apply(__forwarder, _M_args);
820 template<typename _Range>
821 requires __adaptor_invocable<_Adaptor, _Range, _Args...>
823 operator()(_Range&& __r) &&
825 auto __forwarder = [&__r] (auto&... __args) {
826 return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...);
828 return std::apply(__forwarder, _M_args);
831 template<typename _Range>
833 operator()(_Range&& __r) const && = delete;
836 // A lightweight specialization of the above primary template for
837 // the common case where _Adaptor accepts a single extra argument.
838 template<typename _Adaptor, typename _Arg>
839 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
845 : _M_arg(std::move(__arg))
848 template<typename _Range>
849 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
851 operator()(_Range&& __r) const &
852 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
854 template<typename _Range>
855 requires __adaptor_invocable<_Adaptor, _Range, _Arg>
857 operator()(_Range&& __r) &&
858 { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
860 template<typename _Range>
862 operator()(_Range&& __r) const && = delete;
865 template<typename _Lhs, typename _Rhs, typename _Range>
866 concept __pipe_invocable
867 = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); };
869 // A range adaptor closure that represents composition of the range
870 // adaptor closures _Lhs and _Rhs.
871 template<typename _Lhs, typename _Rhs>
872 struct _Pipe : _RangeAdaptorClosure
874 [[no_unique_address]] _Lhs _M_lhs;
875 [[no_unique_address]] _Rhs _M_rhs;
878 _Pipe(_Lhs __lhs, _Rhs __rhs)
879 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
882 // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this
883 // range adaptor closure object.
884 template<typename _Range>
885 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
887 operator()(_Range&& __r) const &
888 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
890 template<typename _Range>
891 requires __pipe_invocable<_Lhs, _Rhs, _Range>
893 operator()(_Range&& __r) &&
894 { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); }
896 template<typename _Range>
898 operator()(_Range&& __r) const && = delete;
900 } // namespace views::__adaptor
902 template<range _Range> requires is_object_v<_Range>
903 class ref_view : public view_interface<ref_view<_Range>>
906 _Range* _M_r = nullptr;
908 static void _S_fun(_Range&); // not defined
909 static void _S_fun(_Range&&) = delete;
913 ref_view() noexcept = default;
915 template<__detail::__not_same_as<ref_view> _Tp>
916 requires convertible_to<_Tp, _Range&>
917 && requires { _S_fun(declval<_Tp>()); }
920 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
927 constexpr iterator_t<_Range>
929 { return ranges::begin(*_M_r); }
931 constexpr sentinel_t<_Range>
933 { return ranges::end(*_M_r); }
936 empty() const requires requires { ranges::empty(*_M_r); }
937 { return ranges::empty(*_M_r); }
940 size() const requires sized_range<_Range>
941 { return ranges::size(*_M_r); }
944 data() const requires contiguous_range<_Range>
945 { return ranges::data(*_M_r); }
948 template<typename _Range>
949 ref_view(_Range&) -> ref_view<_Range>;
951 template<typename _Tp>
952 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
958 template<typename _Range>
959 concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
961 template<typename _Range>
962 concept __can_subrange = requires { subrange{std::declval<_Range>()}; };
963 } // namespace __detail
965 struct _All : __adaptor::_RangeAdaptorClosure
967 template<viewable_range _Range>
968 requires view<decay_t<_Range>>
969 || __detail::__can_ref_view<_Range>
970 || __detail::__can_subrange<_Range>
972 operator()(_Range&& __r) const
974 if constexpr (view<decay_t<_Range>>)
975 return std::forward<_Range>(__r);
976 else if constexpr (__detail::__can_ref_view<_Range>)
977 return ref_view{std::forward<_Range>(__r)};
979 return subrange{std::forward<_Range>(__r)};
983 inline constexpr _All all;
985 template<viewable_range _Range>
986 using all_t = decltype(all(std::declval<_Range>()));
989 // The following simple algos are transcribed from ranges_algo.h to avoid
990 // having to include that entire header.
993 template<typename _Iter, typename _Sent, typename _Tp>
995 find(_Iter __first, _Sent __last, const _Tp& __value)
997 while (__first != __last
998 && !(bool)(*__first == __value))
1003 template<typename _Iter, typename _Sent, typename _Pred>
1005 find_if(_Iter __first, _Sent __last, _Pred __pred)
1007 while (__first != __last
1008 && !(bool)std::__invoke(__pred, *__first))
1013 template<typename _Iter, typename _Sent, typename _Pred>
1015 find_if_not(_Iter __first, _Sent __last, _Pred __pred)
1017 while (__first != __last
1018 && (bool)std::__invoke(__pred, *__first))
1023 template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2>
1024 constexpr pair<_Iter1, _Iter2>
1025 mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2)
1027 while (__first1 != __last1 && __first2 != __last2
1028 && (bool)ranges::equal_to{}(*__first1, *__first2))
1033 return { std::move(__first1), std::move(__first2) };
1035 } // namespace __detail
1039 template<range _Range>
1040 struct _CachedPosition
1043 _M_has_value() const
1046 constexpr iterator_t<_Range>
1047 _M_get(const _Range&) const
1049 __glibcxx_assert(false);
1054 _M_set(const _Range&, const iterator_t<_Range>&) const
1058 template<forward_range _Range>
1059 struct _CachedPosition<_Range>
1062 iterator_t<_Range> _M_iter{};
1066 _M_has_value() const
1067 { return _M_iter != iterator_t<_Range>{}; }
1069 constexpr iterator_t<_Range>
1070 _M_get(const _Range&) const
1072 __glibcxx_assert(_M_has_value());
1077 _M_set(const _Range&, const iterator_t<_Range>& __it)
1079 __glibcxx_assert(!_M_has_value());
1084 template<random_access_range _Range>
1085 requires (sizeof(range_difference_t<_Range>)
1086 <= sizeof(iterator_t<_Range>))
1087 struct _CachedPosition<_Range>
1090 range_difference_t<_Range> _M_offset = -1;
1094 _M_has_value() const
1095 { return _M_offset >= 0; }
1097 constexpr iterator_t<_Range>
1098 _M_get(_Range& __r) const
1100 __glibcxx_assert(_M_has_value());
1101 return ranges::begin(__r) + _M_offset;
1105 _M_set(_Range& __r, const iterator_t<_Range>& __it)
1107 __glibcxx_assert(!_M_has_value());
1108 _M_offset = __it - ranges::begin(__r);
1111 } // namespace __detail
1115 template<typename _Base>
1116 struct __filter_view_iter_cat
1119 template<forward_range _Base>
1120 struct __filter_view_iter_cat<_Base>
1126 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1127 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1128 return bidirectional_iterator_tag{};
1129 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1130 return forward_iterator_tag{};
1135 using iterator_category = decltype(_S_iter_cat());
1137 } // namespace __detail
1139 template<input_range _Vp,
1140 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1141 requires view<_Vp> && is_object_v<_Pred>
1142 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1147 struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
1150 static constexpr auto
1153 if constexpr (bidirectional_range<_Vp>)
1154 return bidirectional_iterator_tag{};
1155 else if constexpr (forward_range<_Vp>)
1156 return forward_iterator_tag{};
1158 return input_iterator_tag{};
1163 using _Vp_iter = iterator_t<_Vp>;
1165 _Vp_iter _M_current = _Vp_iter();
1166 filter_view* _M_parent = nullptr;
1169 using iterator_concept = decltype(_S_iter_concept());
1170 // iterator_category defined in __filter_view_iter_cat
1171 using value_type = range_value_t<_Vp>;
1172 using difference_type = range_difference_t<_Vp>;
1174 _Iterator() = default;
1177 _Iterator(filter_view* __parent, _Vp_iter __current)
1178 : _M_current(std::move(__current)),
1184 requires copyable<_Vp_iter>
1185 { return _M_current; }
1189 { return std::move(_M_current); }
1191 constexpr range_reference_t<_Vp>
1193 { return *_M_current; }
1197 requires __detail::__has_arrow<_Vp_iter>
1198 && copyable<_Vp_iter>
1199 { return _M_current; }
1201 constexpr _Iterator&
1204 _M_current = __detail::find_if(std::move(++_M_current),
1205 ranges::end(_M_parent->_M_base),
1206 std::ref(*_M_parent->_M_pred));
1215 operator++(int) requires forward_range<_Vp>
1222 constexpr _Iterator&
1223 operator--() requires bidirectional_range<_Vp>
1227 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1232 operator--(int) requires bidirectional_range<_Vp>
1239 friend constexpr bool
1240 operator==(const _Iterator& __x, const _Iterator& __y)
1241 requires equality_comparable<_Vp_iter>
1242 { return __x._M_current == __y._M_current; }
1244 friend constexpr range_rvalue_reference_t<_Vp>
1245 iter_move(const _Iterator& __i)
1246 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1247 { return ranges::iter_move(__i._M_current); }
1249 friend constexpr void
1250 iter_swap(const _Iterator& __x, const _Iterator& __y)
1251 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1252 requires indirectly_swappable<_Vp_iter>
1253 { ranges::iter_swap(__x._M_current, __y._M_current); }
1259 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1262 __equal(const _Iterator& __i) const
1263 { return __i._M_current == _M_end; }
1266 _Sentinel() = default;
1269 _Sentinel(filter_view* __parent)
1270 : _M_end(ranges::end(__parent->_M_base))
1273 constexpr sentinel_t<_Vp>
1277 friend constexpr bool
1278 operator==(const _Iterator& __x, const _Sentinel& __y)
1279 { return __y.__equal(__x); }
1282 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1283 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1284 _Vp _M_base = _Vp();
1287 filter_view() = default;
1290 filter_view(_Vp __base, _Pred __pred)
1291 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
1295 base() const& requires copy_constructible<_Vp>
1300 { return std::move(_M_base); }
1302 constexpr const _Pred&
1304 { return *_M_pred; }
1309 if (_M_cached_begin._M_has_value())
1310 return {this, _M_cached_begin._M_get(_M_base)};
1312 __glibcxx_assert(_M_pred.has_value());
1313 auto __it = __detail::find_if(ranges::begin(_M_base),
1314 ranges::end(_M_base),
1315 std::ref(*_M_pred));
1316 _M_cached_begin._M_set(_M_base, __it);
1317 return {this, std::move(__it)};
1323 if constexpr (common_range<_Vp>)
1324 return _Iterator{this, ranges::end(_M_base)};
1326 return _Sentinel{this};
1330 template<typename _Range, typename _Pred>
1331 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1337 template<typename _Range, typename _Pred>
1338 concept __can_filter_view
1339 = requires { filter_view{std::declval<_Range>(), std::declval<_Pred>()}; };
1340 } // namespace __detail
1342 struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1344 template<viewable_range _Range, typename _Pred>
1345 requires __detail::__can_filter_view<_Range, _Pred>
1347 operator()(_Range&& __r, _Pred&& __p) const
1349 return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1352 using _RangeAdaptor<_Filter>::operator();
1353 static constexpr int _S_arity = 2;
1356 inline constexpr _Filter filter;
1357 } // namespace views
1359 template<input_range _Vp, copy_constructible _Fp>
1360 requires view<_Vp> && is_object_v<_Fp>
1361 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1362 && std::__detail::__can_reference<invoke_result_t<_Fp&,
1363 range_reference_t<_Vp>>>
1364 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1367 template<bool _Const>
1368 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1370 template<bool _Const>
1374 template<bool _Const>
1375 requires forward_range<_Base<_Const>>
1376 struct __iter_cat<_Const>
1382 using _Base = transform_view::_Base<_Const>;
1383 using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1384 if constexpr (is_lvalue_reference_v<_Res>)
1387 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1388 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1389 return random_access_iterator_tag{};
1394 return input_iterator_tag{};
1397 using iterator_category = decltype(_S_iter_cat());
1400 template<bool _Const>
1403 template<bool _Const>
1404 struct _Iterator : __iter_cat<_Const>
1407 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1408 using _Base = transform_view::_Base<_Const>;
1413 if constexpr (random_access_range<_Vp>)
1414 return random_access_iterator_tag{};
1415 else if constexpr (bidirectional_range<_Vp>)
1416 return bidirectional_iterator_tag{};
1417 else if constexpr (forward_range<_Vp>)
1418 return forward_iterator_tag{};
1420 return input_iterator_tag{};
1423 using _Base_iter = iterator_t<_Base>;
1425 _Base_iter _M_current = _Base_iter();
1426 _Parent* _M_parent = nullptr;
1429 using iterator_concept = decltype(_S_iter_concept());
1430 // iterator_category defined in __transform_view_iter_cat
1432 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1433 using difference_type = range_difference_t<_Base>;
1435 _Iterator() = default;
1438 _Iterator(_Parent* __parent, _Base_iter __current)
1439 : _M_current(std::move(__current)),
1444 _Iterator(_Iterator<!_Const> __i)
1446 && convertible_to<iterator_t<_Vp>, _Base_iter>
1447 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1450 constexpr _Base_iter
1452 requires copyable<_Base_iter>
1453 { return _M_current; }
1455 constexpr _Base_iter
1457 { return std::move(_M_current); }
1459 constexpr decltype(auto)
1461 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1462 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1464 constexpr _Iterator&
1476 operator++(int) requires forward_range<_Base>
1483 constexpr _Iterator&
1484 operator--() requires bidirectional_range<_Base>
1491 operator--(int) requires bidirectional_range<_Base>
1498 constexpr _Iterator&
1499 operator+=(difference_type __n) requires random_access_range<_Base>
1505 constexpr _Iterator&
1506 operator-=(difference_type __n) requires random_access_range<_Base>
1512 constexpr decltype(auto)
1513 operator[](difference_type __n) const
1514 requires random_access_range<_Base>
1515 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1517 friend constexpr bool
1518 operator==(const _Iterator& __x, const _Iterator& __y)
1519 requires equality_comparable<_Base_iter>
1520 { return __x._M_current == __y._M_current; }
1522 friend constexpr bool
1523 operator<(const _Iterator& __x, const _Iterator& __y)
1524 requires random_access_range<_Base>
1525 { return __x._M_current < __y._M_current; }
1527 friend constexpr bool
1528 operator>(const _Iterator& __x, const _Iterator& __y)
1529 requires random_access_range<_Base>
1530 { return __y < __x; }
1532 friend constexpr bool
1533 operator<=(const _Iterator& __x, const _Iterator& __y)
1534 requires random_access_range<_Base>
1535 { return !(__y < __x); }
1537 friend constexpr bool
1538 operator>=(const _Iterator& __x, const _Iterator& __y)
1539 requires random_access_range<_Base>
1540 { return !(__x < __y); }
1542 #ifdef __cpp_lib_three_way_comparison
1543 friend constexpr auto
1544 operator<=>(const _Iterator& __x, const _Iterator& __y)
1545 requires random_access_range<_Base>
1546 && three_way_comparable<_Base_iter>
1547 { return __x._M_current <=> __y._M_current; }
1550 friend constexpr _Iterator
1551 operator+(_Iterator __i, difference_type __n)
1552 requires random_access_range<_Base>
1553 { return {__i._M_parent, __i._M_current + __n}; }
1555 friend constexpr _Iterator
1556 operator+(difference_type __n, _Iterator __i)
1557 requires random_access_range<_Base>
1558 { return {__i._M_parent, __i._M_current + __n}; }
1560 friend constexpr _Iterator
1561 operator-(_Iterator __i, difference_type __n)
1562 requires random_access_range<_Base>
1563 { return {__i._M_parent, __i._M_current - __n}; }
1565 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1566 // 3483. transform_view::iterator's difference is overconstrained
1567 friend constexpr difference_type
1568 operator-(const _Iterator& __x, const _Iterator& __y)
1569 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1570 { return __x._M_current - __y._M_current; }
1572 friend constexpr decltype(auto)
1573 iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1575 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1576 return std::move(*__i);
1581 friend constexpr void
1582 iter_swap(const _Iterator& __x, const _Iterator& __y)
1583 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1584 requires indirectly_swappable<_Base_iter>
1585 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1587 friend _Iterator<!_Const>;
1588 template<bool> friend struct _Sentinel;
1591 template<bool _Const>
1595 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1596 using _Base = transform_view::_Base<_Const>;
1598 template<bool _Const2>
1600 __distance_from(const _Iterator<_Const2>& __i) const
1601 { return _M_end - __i._M_current; }
1603 template<bool _Const2>
1605 __equal(const _Iterator<_Const2>& __i) const
1606 { return __i._M_current == _M_end; }
1608 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1611 _Sentinel() = default;
1614 _Sentinel(sentinel_t<_Base> __end)
1619 _Sentinel(_Sentinel<!_Const> __i)
1621 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1622 : _M_end(std::move(__i._M_end))
1625 constexpr sentinel_t<_Base>
1629 template<bool _Const2>
1630 requires sentinel_for<sentinel_t<_Base>,
1631 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1632 friend constexpr bool
1633 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1634 { return __y.__equal(__x); }
1636 template<bool _Const2,
1637 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1638 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1639 friend constexpr range_difference_t<_Base2>
1640 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1641 { return -__y.__distance_from(__x); }
1643 template<bool _Const2,
1644 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1645 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1646 friend constexpr range_difference_t<_Base2>
1647 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1648 { return __y.__distance_from(__x); }
1650 friend _Sentinel<!_Const>;
1653 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1654 _Vp _M_base = _Vp();
1657 transform_view() = default;
1660 transform_view(_Vp __base, _Fp __fun)
1661 : _M_fun(std::move(__fun)), _M_base(std::move(__base))
1665 base() const& requires copy_constructible<_Vp>
1666 { return _M_base ; }
1670 { return std::move(_M_base); }
1672 constexpr _Iterator<false>
1674 { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1676 constexpr _Iterator<true>
1678 requires range<const _Vp>
1679 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1680 { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1682 constexpr _Sentinel<false>
1684 { return _Sentinel<false>{ranges::end(_M_base)}; }
1686 constexpr _Iterator<false>
1687 end() requires common_range<_Vp>
1688 { return _Iterator<false>{this, ranges::end(_M_base)}; }
1690 constexpr _Sentinel<true>
1692 requires range<const _Vp>
1693 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1694 { return _Sentinel<true>{ranges::end(_M_base)}; }
1696 constexpr _Iterator<true>
1698 requires common_range<const _Vp>
1699 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1700 { return _Iterator<true>{this, ranges::end(_M_base)}; }
1703 size() requires sized_range<_Vp>
1704 { return ranges::size(_M_base); }
1707 size() const requires sized_range<const _Vp>
1708 { return ranges::size(_M_base); }
1711 template<typename _Range, typename _Fp>
1712 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1718 template<typename _Range, typename _Fp>
1719 concept __can_transform_view
1720 = requires { transform_view{std::declval<_Range>(), std::declval<_Fp>()}; };
1721 } // namespace __detail
1723 struct _Transform : __adaptor::_RangeAdaptor<_Transform>
1725 template<viewable_range _Range, typename _Fp>
1726 requires __detail::__can_transform_view<_Range, _Fp>
1728 operator()(_Range&& __r, _Fp&& __f) const
1730 return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1733 using _RangeAdaptor<_Transform>::operator();
1734 static constexpr int _S_arity = 2;
1737 inline constexpr _Transform transform;
1738 } // namespace views
1741 class take_view : public view_interface<take_view<_Vp>>
1744 template<bool _Const>
1745 using _CI = counted_iterator<
1746 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1748 template<bool _Const>
1752 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1753 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1756 _Sentinel() = default;
1759 _Sentinel(sentinel_t<_Base> __end)
1764 _Sentinel(_Sentinel<!_Const> __s)
1765 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1766 : _M_end(std::move(__s._M_end))
1769 constexpr sentinel_t<_Base>
1773 friend constexpr bool
1774 operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1775 { return __y.count() == 0 || __y.base() == __x._M_end; }
1777 template<bool _OtherConst = !_Const,
1778 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1779 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1780 friend constexpr bool
1781 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1782 { return __y.count() == 0 || __y.base() == __x._M_end; }
1784 friend _Sentinel<!_Const>;
1787 range_difference_t<_Vp> _M_count = 0;
1788 _Vp _M_base = _Vp();
1791 take_view() = default;
1794 take_view(_Vp base, range_difference_t<_Vp> __count)
1795 : _M_count(std::move(__count)), _M_base(std::move(base))
1799 base() const& requires copy_constructible<_Vp>
1804 { return std::move(_M_base); }
1807 begin() requires (!__detail::__simple_view<_Vp>)
1809 if constexpr (sized_range<_Vp>)
1811 if constexpr (random_access_range<_Vp>)
1812 return ranges::begin(_M_base);
1816 return counted_iterator{ranges::begin(_M_base), __sz};
1820 return counted_iterator{ranges::begin(_M_base), _M_count};
1824 begin() const requires range<const _Vp>
1826 if constexpr (sized_range<const _Vp>)
1828 if constexpr (random_access_range<const _Vp>)
1829 return ranges::begin(_M_base);
1833 return counted_iterator{ranges::begin(_M_base), __sz};
1837 return counted_iterator{ranges::begin(_M_base), _M_count};
1841 end() requires (!__detail::__simple_view<_Vp>)
1843 if constexpr (sized_range<_Vp>)
1845 if constexpr (random_access_range<_Vp>)
1846 return ranges::begin(_M_base) + size();
1848 return default_sentinel;
1851 return _Sentinel<false>{ranges::end(_M_base)};
1855 end() const requires range<const _Vp>
1857 if constexpr (sized_range<const _Vp>)
1859 if constexpr (random_access_range<const _Vp>)
1860 return ranges::begin(_M_base) + size();
1862 return default_sentinel;
1865 return _Sentinel<true>{ranges::end(_M_base)};
1869 size() requires sized_range<_Vp>
1871 auto __n = ranges::size(_M_base);
1872 return std::min(__n, static_cast<decltype(__n)>(_M_count));
1876 size() const requires sized_range<const _Vp>
1878 auto __n = ranges::size(_M_base);
1879 return std::min(__n, static_cast<decltype(__n)>(_M_count));
1883 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1884 // 3447. Deduction guides for take_view and drop_view have different
1886 template<typename _Range>
1887 take_view(_Range&&, range_difference_t<_Range>)
1888 -> take_view<views::all_t<_Range>>;
1890 template<typename _Tp>
1891 inline constexpr bool enable_borrowed_range<take_view<_Tp>>
1892 = enable_borrowed_range<_Tp>;
1898 template<typename _Range, typename _Tp>
1899 concept __can_take_view
1900 = requires { take_view{std::declval<_Range>(), std::declval<_Tp>()}; };
1901 } // namespace __detail
1903 struct _Take : __adaptor::_RangeAdaptor<_Take>
1905 template<viewable_range _Range, typename _Tp>
1906 requires __detail::__can_take_view<_Range, _Tp>
1908 operator()(_Range&& __r, _Tp&& __n) const
1910 return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
1913 using _RangeAdaptor<_Take>::operator();
1914 static constexpr int _S_arity = 2;
1917 inline constexpr _Take take;
1918 } // namespace views
1920 template<view _Vp, typename _Pred>
1921 requires input_range<_Vp> && is_object_v<_Pred>
1922 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
1923 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
1925 template<bool _Const>
1929 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1931 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1932 const _Pred* _M_pred = nullptr;
1935 _Sentinel() = default;
1938 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
1939 : _M_end(__end), _M_pred(__pred)
1943 _Sentinel(_Sentinel<!_Const> __s)
1944 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1945 : _M_end(__s._M_end), _M_pred(__s._M_pred)
1948 constexpr sentinel_t<_Base>
1949 base() const { return _M_end; }
1951 friend constexpr bool
1952 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
1953 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1955 template<bool _OtherConst = !_Const,
1956 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1957 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1958 friend constexpr bool
1959 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
1960 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1962 friend _Sentinel<!_Const>;
1965 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1966 _Vp _M_base = _Vp();
1969 take_while_view() = default;
1972 take_while_view(_Vp base, _Pred __pred)
1973 : _M_pred(std::move(__pred)), _M_base(std::move(base))
1977 base() const& requires copy_constructible<_Vp>
1982 { return std::move(_M_base); }
1984 constexpr const _Pred&
1986 { return *_M_pred; }
1989 begin() requires (!__detail::__simple_view<_Vp>)
1990 { return ranges::begin(_M_base); }
1993 begin() const requires range<const _Vp>
1994 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1995 { return ranges::begin(_M_base); }
1998 end() requires (!__detail::__simple_view<_Vp>)
1999 { return _Sentinel<false>(ranges::end(_M_base),
2000 std::__addressof(*_M_pred)); }
2003 end() const requires range<const _Vp>
2004 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2005 { return _Sentinel<true>(ranges::end(_M_base),
2006 std::__addressof(*_M_pred)); }
2009 template<typename _Range, typename _Pred>
2010 take_while_view(_Range&&, _Pred)
2011 -> take_while_view<views::all_t<_Range>, _Pred>;
2017 template<typename _Range, typename _Pred>
2018 concept __can_take_while_view
2019 = requires { take_while_view{std::declval<_Range>(), std::declval<_Pred>()}; };
2020 } // namespace __detail
2022 struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
2024 template<viewable_range _Range, typename _Pred>
2025 requires __detail::__can_take_while_view<_Range, _Pred>
2027 operator()(_Range&& __r, _Pred&& __p) const
2029 return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
2032 using _RangeAdaptor<_TakeWhile>::operator();
2033 static constexpr int _S_arity = 2;
2036 inline constexpr _TakeWhile take_while;
2037 } // namespace views
2040 class drop_view : public view_interface<drop_view<_Vp>>
2043 range_difference_t<_Vp> _M_count = 0;
2044 _Vp _M_base = _Vp();
2046 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2047 // both random_access_range and sized_range. Otherwise, cache its result.
2048 static constexpr bool _S_needs_cached_begin
2049 = !(random_access_range<const _Vp> && sized_range<const _Vp>);
2050 [[no_unique_address]]
2051 __detail::__maybe_present_t<_S_needs_cached_begin,
2052 __detail::_CachedPosition<_Vp>>
2056 drop_view() = default;
2059 drop_view(_Vp __base, range_difference_t<_Vp> __count)
2060 : _M_count(__count), _M_base(std::move(__base))
2061 { __glibcxx_assert(__count >= 0); }
2064 base() const& requires copy_constructible<_Vp>
2069 { return std::move(_M_base); }
2071 // This overload is disabled for simple views with constant-time begin().
2074 requires (!(__detail::__simple_view<_Vp>
2075 && random_access_range<const _Vp>
2076 && sized_range<const _Vp>))
2078 if constexpr (_S_needs_cached_begin)
2079 if (_M_cached_begin._M_has_value())
2080 return _M_cached_begin._M_get(_M_base);
2082 auto __it = ranges::next(ranges::begin(_M_base),
2083 _M_count, ranges::end(_M_base));
2084 if constexpr (_S_needs_cached_begin)
2085 _M_cached_begin._M_set(_M_base, __it);
2089 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2090 // 3482. drop_view's const begin should additionally require sized_range
2093 requires random_access_range<const _Vp> && sized_range<const _Vp>
2095 return ranges::next(ranges::begin(_M_base), _M_count,
2096 ranges::end(_M_base));
2100 end() requires (!__detail::__simple_view<_Vp>)
2101 { return ranges::end(_M_base); }
2104 end() const requires range<const _Vp>
2105 { return ranges::end(_M_base); }
2108 size() requires sized_range<_Vp>
2110 const auto __s = ranges::size(_M_base);
2111 const auto __c = static_cast<decltype(__s)>(_M_count);
2112 return __s < __c ? 0 : __s - __c;
2116 size() const requires sized_range<const _Vp>
2118 const auto __s = ranges::size(_M_base);
2119 const auto __c = static_cast<decltype(__s)>(_M_count);
2120 return __s < __c ? 0 : __s - __c;
2124 template<typename _Range>
2125 drop_view(_Range&&, range_difference_t<_Range>)
2126 -> drop_view<views::all_t<_Range>>;
2128 template<typename _Tp>
2129 inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2130 = enable_borrowed_range<_Tp>;
2136 template<typename _Range, typename _Tp>
2137 concept __can_drop_view
2138 = requires { drop_view{std::declval<_Range>(), std::declval<_Tp>()}; };
2139 } // namespace __detail
2141 struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2143 template<viewable_range _Range, typename _Tp>
2144 requires __detail::__can_drop_view<_Range, _Tp>
2146 operator()(_Range&& __r, _Tp&& __n) const
2148 return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2151 using _RangeAdaptor<_Drop>::operator();
2152 static constexpr int _S_arity = 2;
2155 inline constexpr _Drop drop;
2156 } // namespace views
2158 template<view _Vp, typename _Pred>
2159 requires input_range<_Vp> && is_object_v<_Pred>
2160 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2161 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2164 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2165 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2166 _Vp _M_base = _Vp();
2169 drop_while_view() = default;
2172 drop_while_view(_Vp __base, _Pred __pred)
2173 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
2177 base() const& requires copy_constructible<_Vp>
2182 { return std::move(_M_base); }
2184 constexpr const _Pred&
2186 { return *_M_pred; }
2191 if (_M_cached_begin._M_has_value())
2192 return _M_cached_begin._M_get(_M_base);
2194 auto __it = __detail::find_if_not(ranges::begin(_M_base),
2195 ranges::end(_M_base),
2196 std::cref(*_M_pred));
2197 _M_cached_begin._M_set(_M_base, __it);
2203 { return ranges::end(_M_base); }
2206 template<typename _Range, typename _Pred>
2207 drop_while_view(_Range&&, _Pred)
2208 -> drop_while_view<views::all_t<_Range>, _Pred>;
2210 template<typename _Tp, typename _Pred>
2211 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2212 = enable_borrowed_range<_Tp>;
2218 template<typename _Range, typename _Pred>
2219 concept __can_drop_while_view
2220 = requires { drop_while_view{std::declval<_Range>(), std::declval<_Pred>()}; };
2221 } // namespace __detail
2223 struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2225 template<viewable_range _Range, typename _Pred>
2226 requires __detail::__can_drop_while_view<_Range, _Pred>
2228 operator()(_Range&& __r, _Pred&& __p) const
2230 return drop_while_view{std::forward<_Range>(__r),
2231 std::forward<_Pred>(__p)};
2234 using _RangeAdaptor<_DropWhile>::operator();
2235 static constexpr int _S_arity = 2;
2238 inline constexpr _DropWhile drop_while;
2239 } // namespace views
2241 template<input_range _Vp>
2242 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2243 && (is_reference_v<range_reference_t<_Vp>>
2244 || view<range_value_t<_Vp>>)
2245 class join_view : public view_interface<join_view<_Vp>>
2248 using _InnerRange = range_reference_t<_Vp>;
2250 template<bool _Const>
2251 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2253 template<bool _Const>
2254 using _Outer_iter = iterator_t<_Base<_Const>>;
2256 template<bool _Const>
2257 using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
2259 template<bool _Const>
2260 static constexpr bool _S_ref_is_glvalue
2261 = is_reference_v<range_reference_t<_Base<_Const>>>;
2263 template<bool _Const>
2267 template<bool _Const>
2268 requires _S_ref_is_glvalue<_Const>
2269 && forward_range<_Base<_Const>>
2270 && forward_range<range_reference_t<_Base<_Const>>>
2271 struct __iter_cat<_Const>
2274 static constexpr auto
2277 using _Outer_iter = join_view::_Outer_iter<_Const>;
2278 using _Inner_iter = join_view::_Inner_iter<_Const>;
2279 using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category;
2280 using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category;
2281 if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
2282 && derived_from<_InnerCat, bidirectional_iterator_tag>)
2283 return bidirectional_iterator_tag{};
2284 else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
2285 && derived_from<_InnerCat, forward_iterator_tag>)
2286 return forward_iterator_tag{};
2288 return input_iterator_tag{};
2291 using iterator_category = decltype(_S_iter_cat());
2294 template<bool _Const>
2297 template<bool _Const>
2298 struct _Iterator : __iter_cat<_Const>
2301 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2302 using _Base = join_view::_Base<_Const>;
2304 static constexpr bool _S_ref_is_glvalue
2305 = join_view::_S_ref_is_glvalue<_Const>;
2310 auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2312 if constexpr (_S_ref_is_glvalue)
2315 return (_M_parent->_M_inner = views::all(std::move(__x)));
2318 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2320 auto& __inner = __update_inner(*_M_outer);
2321 _M_inner = ranges::begin(__inner);
2322 if (_M_inner != ranges::end(__inner))
2326 if constexpr (_S_ref_is_glvalue)
2327 _M_inner = _Inner_iter();
2330 static constexpr auto
2333 if constexpr (_S_ref_is_glvalue
2334 && bidirectional_range<_Base>
2335 && bidirectional_range<range_reference_t<_Base>>)
2336 return bidirectional_iterator_tag{};
2337 else if constexpr (_S_ref_is_glvalue
2338 && forward_range<_Base>
2339 && forward_range<range_reference_t<_Base>>)
2340 return forward_iterator_tag{};
2342 return input_iterator_tag{};
2345 using _Outer_iter = join_view::_Outer_iter<_Const>;
2346 using _Inner_iter = join_view::_Inner_iter<_Const>;
2348 _Outer_iter _M_outer = _Outer_iter();
2349 _Inner_iter _M_inner = _Inner_iter();
2350 _Parent* _M_parent = nullptr;
2353 using iterator_concept = decltype(_S_iter_concept());
2354 // iterator_category defined in __join_view_iter_cat
2355 using value_type = range_value_t<range_reference_t<_Base>>;
2356 using difference_type
2357 = common_type_t<range_difference_t<_Base>,
2358 range_difference_t<range_reference_t<_Base>>>;
2360 _Iterator() = default;
2363 _Iterator(_Parent* __parent, _Outer_iter __outer)
2364 : _M_outer(std::move(__outer)),
2369 _Iterator(_Iterator<!_Const> __i)
2371 && convertible_to<iterator_t<_Vp>, _Outer_iter>
2372 && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2373 : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2374 _M_parent(__i._M_parent)
2377 constexpr decltype(auto)
2379 { return *_M_inner; }
2381 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2382 // 3500. join_view::iterator::operator->() is bogus
2383 constexpr _Inner_iter
2385 requires __detail::__has_arrow<_Inner_iter>
2386 && copyable<_Inner_iter>
2387 { return _M_inner; }
2389 constexpr _Iterator&
2392 auto&& __inner_range = [this] () -> decltype(auto) {
2393 if constexpr (_S_ref_is_glvalue)
2396 return _M_parent->_M_inner;
2398 if (++_M_inner == ranges::end(__inner_range))
2412 requires _S_ref_is_glvalue && forward_range<_Base>
2413 && forward_range<range_reference_t<_Base>>
2420 constexpr _Iterator&
2422 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2423 && bidirectional_range<range_reference_t<_Base>>
2424 && common_range<range_reference_t<_Base>>
2426 if (_M_outer == ranges::end(_M_parent->_M_base))
2427 _M_inner = ranges::end(*--_M_outer);
2428 while (_M_inner == ranges::begin(*_M_outer))
2429 _M_inner = ranges::end(*--_M_outer);
2436 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2437 && bidirectional_range<range_reference_t<_Base>>
2438 && common_range<range_reference_t<_Base>>
2445 friend constexpr bool
2446 operator==(const _Iterator& __x, const _Iterator& __y)
2447 requires _S_ref_is_glvalue
2448 && equality_comparable<_Outer_iter>
2449 && equality_comparable<_Inner_iter>
2451 return (__x._M_outer == __y._M_outer
2452 && __x._M_inner == __y._M_inner);
2455 friend constexpr decltype(auto)
2456 iter_move(const _Iterator& __i)
2457 noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2458 { return ranges::iter_move(__i._M_inner); }
2460 friend constexpr void
2461 iter_swap(const _Iterator& __x, const _Iterator& __y)
2462 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2463 { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2465 friend _Iterator<!_Const>;
2466 template<bool> friend struct _Sentinel;
2469 template<bool _Const>
2473 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2474 using _Base = join_view::_Base<_Const>;
2476 template<bool _Const2>
2478 __equal(const _Iterator<_Const2>& __i) const
2479 { return __i._M_outer == _M_end; }
2481 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2484 _Sentinel() = default;
2487 _Sentinel(_Parent* __parent)
2488 : _M_end(ranges::end(__parent->_M_base))
2492 _Sentinel(_Sentinel<!_Const> __s)
2493 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2494 : _M_end(std::move(__s._M_end))
2497 template<bool _Const2>
2498 requires sentinel_for<sentinel_t<_Base>,
2499 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2500 friend constexpr bool
2501 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2502 { return __y.__equal(__x); }
2504 friend _Sentinel<!_Const>;
2507 // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2508 [[no_unique_address]]
2509 __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
2510 views::all_t<_InnerRange>> _M_inner;
2511 _Vp _M_base = _Vp();
2514 join_view() = default;
2517 join_view(_Vp __base)
2518 : _M_base(std::move(__base))
2522 base() const& requires copy_constructible<_Vp>
2527 { return std::move(_M_base); }
2532 constexpr bool __use_const
2533 = (__detail::__simple_view<_Vp>
2534 && is_reference_v<range_reference_t<_Vp>>);
2535 return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2540 requires input_range<const _Vp>
2541 && is_reference_v<range_reference_t<const _Vp>>
2543 return _Iterator<true>{this, ranges::begin(_M_base)};
2549 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2550 && forward_range<_InnerRange>
2551 && common_range<_Vp> && common_range<_InnerRange>)
2552 return _Iterator<__detail::__simple_view<_Vp>>{this,
2553 ranges::end(_M_base)};
2555 return _Sentinel<__detail::__simple_view<_Vp>>{this};
2560 requires input_range<const _Vp>
2561 && is_reference_v<range_reference_t<const _Vp>>
2563 if constexpr (forward_range<const _Vp>
2564 && is_reference_v<range_reference_t<const _Vp>>
2565 && forward_range<range_reference_t<const _Vp>>
2566 && common_range<const _Vp>
2567 && common_range<range_reference_t<const _Vp>>)
2568 return _Iterator<true>{this, ranges::end(_M_base)};
2570 return _Sentinel<true>{this};
2574 template<typename _Range>
2575 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2581 template<typename _Range>
2582 concept __can_join_view
2583 = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
2584 } // namespace __detail
2586 struct _Join : __adaptor::_RangeAdaptorClosure
2588 template<viewable_range _Range>
2589 requires __detail::__can_join_view<_Range>
2591 operator()(_Range&& __r) const
2593 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2594 // 3474. Nesting join_views is broken because of CTAD
2595 return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
2599 inline constexpr _Join join;
2600 } // namespace views
2605 struct __require_constant;
2607 template<typename _Range>
2608 concept __tiny_range = sized_range<_Range>
2610 { typename __require_constant<remove_reference_t<_Range>::size()>; }
2611 && (remove_reference_t<_Range>::size() <= 1);
2613 template<typename _Base>
2614 struct __split_view_outer_iter_cat
2617 template<forward_range _Base>
2618 struct __split_view_outer_iter_cat<_Base>
2619 { using iterator_category = input_iterator_tag; };
2621 template<typename _Base>
2622 struct __split_view_inner_iter_cat
2625 template<forward_range _Base>
2626 struct __split_view_inner_iter_cat<_Base>
2629 static constexpr auto
2632 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2633 if constexpr (derived_from<_Cat, forward_iterator_tag>)
2634 return forward_iterator_tag{};
2639 using iterator_category = decltype(_S_iter_cat());
2643 template<input_range _Vp, forward_range _Pattern>
2644 requires view<_Vp> && view<_Pattern>
2645 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2647 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2648 class split_view : public view_interface<split_view<_Vp, _Pattern>>
2651 template<bool _Const>
2652 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2654 template<bool _Const>
2657 template<bool _Const>
2659 : __detail::__split_view_outer_iter_cat<_Base<_Const>>
2662 using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2663 using _Base = split_view::_Base<_Const>;
2667 { return __current() == ranges::end(_M_parent->_M_base); }
2669 // [range.split.outer] p1
2670 // Many of the following specifications refer to the notional member
2671 // current of outer-iterator. current is equivalent to current_ if
2672 // V models forward_range, and parent_->current_ otherwise.
2674 __current() noexcept
2676 if constexpr (forward_range<_Vp>)
2679 return _M_parent->_M_current;
2683 __current() const noexcept
2685 if constexpr (forward_range<_Vp>)
2688 return _M_parent->_M_current;
2691 _Parent* _M_parent = nullptr;
2693 // XXX: _M_current is present only if "V models forward_range"
2694 [[no_unique_address]]
2695 __detail::__maybe_present_t<forward_range<_Vp>,
2696 iterator_t<_Base>> _M_current;
2699 using iterator_concept = conditional_t<forward_range<_Base>,
2700 forward_iterator_tag,
2701 input_iterator_tag>;
2702 // iterator_category defined in __split_view_outer_iter_cat
2703 using difference_type = range_difference_t<_Base>;
2705 struct value_type : view_interface<value_type>
2708 _OuterIter _M_i = _OuterIter();
2711 value_type() = default;
2714 value_type(_OuterIter __i)
2715 : _M_i(std::move(__i))
2718 constexpr _InnerIter<_Const>
2720 requires copyable<_OuterIter>
2721 { return _InnerIter<_Const>{_M_i}; }
2723 constexpr _InnerIter<_Const>
2725 requires (!copyable<_OuterIter>)
2726 { return _InnerIter<_Const>{std::move(_M_i)}; }
2728 constexpr default_sentinel_t
2730 { return default_sentinel; }
2733 _OuterIter() = default;
2736 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2737 : _M_parent(__parent)
2741 _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2742 requires forward_range<_Base>
2743 : _M_parent(__parent),
2744 _M_current(std::move(__current))
2748 _OuterIter(_OuterIter<!_Const> __i)
2750 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2751 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2754 constexpr value_type
2756 { return value_type{*this}; }
2758 constexpr _OuterIter&
2761 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2762 // 3505. split_view::outer-iterator::operator++ misspecified
2763 const auto __end = ranges::end(_M_parent->_M_base);
2764 if (__current() == __end)
2766 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2767 if (__pbegin == __pend)
2769 else if constexpr (__detail::__tiny_range<_Pattern>)
2771 __current() = __detail::find(std::move(__current()), __end,
2773 if (__current() != __end)
2780 = __detail::mismatch(__current(), __end, __pbegin, __pend);
2786 } while (++__current() != __end);
2790 constexpr decltype(auto)
2793 if constexpr (forward_range<_Base>)
2803 friend constexpr bool
2804 operator==(const _OuterIter& __x, const _OuterIter& __y)
2805 requires forward_range<_Base>
2806 { return __x._M_current == __y._M_current; }
2808 friend constexpr bool
2809 operator==(const _OuterIter& __x, default_sentinel_t)
2810 { return __x.__at_end(); };
2812 friend _OuterIter<!_Const>;
2813 friend _InnerIter<_Const>;
2816 template<bool _Const>
2818 : __detail::__split_view_inner_iter_cat<_Base<_Const>>
2821 using _Base = split_view::_Base<_Const>;
2826 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2827 auto __end = ranges::end(_M_i._M_parent->_M_base);
2828 if constexpr (__detail::__tiny_range<_Pattern>)
2830 const auto& __cur = _M_i_current();
2833 if (__pcur == __pend)
2834 return _M_incremented;
2835 return *__cur == *__pcur;
2839 auto __cur = _M_i_current();
2842 if (__pcur == __pend)
2843 return _M_incremented;
2846 if (*__cur != *__pcur)
2848 if (++__pcur == __pend)
2850 } while (++__cur != __end);
2856 _M_i_current() noexcept
2857 { return _M_i.__current(); }
2860 _M_i_current() const noexcept
2861 { return _M_i.__current(); }
2863 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2864 bool _M_incremented = false;
2867 using iterator_concept
2868 = typename _OuterIter<_Const>::iterator_concept;
2869 // iterator_category defined in __split_view_inner_iter_cat
2870 using value_type = range_value_t<_Base>;
2871 using difference_type = range_difference_t<_Base>;
2873 _InnerIter() = default;
2876 _InnerIter(_OuterIter<_Const> __i)
2877 : _M_i(std::move(__i))
2880 constexpr decltype(auto)
2882 { return *_M_i_current(); }
2884 constexpr _InnerIter&
2887 _M_incremented = true;
2888 if constexpr (!forward_range<_Base>)
2889 if constexpr (_Pattern::size() == 0)
2895 constexpr decltype(auto)
2898 if constexpr (forward_range<_Vp>)
2908 friend constexpr bool
2909 operator==(const _InnerIter& __x, const _InnerIter& __y)
2910 requires forward_range<_Base>
2911 { return __x._M_i == __y._M_i; }
2913 friend constexpr bool
2914 operator==(const _InnerIter& __x, default_sentinel_t)
2915 { return __x.__at_end(); }
2917 friend constexpr decltype(auto)
2918 iter_move(const _InnerIter& __i)
2919 noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
2920 { return ranges::iter_move(__i._M_i_current()); }
2922 friend constexpr void
2923 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2924 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
2925 __y._M_i_current())))
2926 requires indirectly_swappable<iterator_t<_Base>>
2927 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
2930 _Pattern _M_pattern = _Pattern();
2931 // XXX: _M_current is "present only if !forward_range<V>"
2932 [[no_unique_address]]
2933 __detail::__maybe_present_t<!forward_range<_Vp>,
2934 iterator_t<_Vp>> _M_current;
2935 _Vp _M_base = _Vp();
2939 split_view() = default;
2942 split_view(_Vp __base, _Pattern __pattern)
2943 : _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
2946 template<input_range _Range>
2947 requires constructible_from<_Vp, views::all_t<_Range>>
2948 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2950 split_view(_Range&& __r, range_value_t<_Range> __e)
2951 : _M_pattern(std::move(__e)),
2952 _M_base(views::all(std::forward<_Range>(__r)))
2956 base() const& requires copy_constructible<_Vp>
2961 { return std::move(_M_base); }
2966 if constexpr (forward_range<_Vp>)
2967 return _OuterIter<__detail::__simple_view<_Vp>>{
2968 this, ranges::begin(_M_base)};
2971 _M_current = ranges::begin(_M_base);
2972 return _OuterIter<false>{this};
2977 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
2979 return _OuterIter<true>{this, ranges::begin(_M_base)};
2983 end() requires forward_range<_Vp> && common_range<_Vp>
2985 return _OuterIter<__detail::__simple_view<_Vp>>{
2986 this, ranges::end(_M_base)};
2992 if constexpr (forward_range<_Vp>
2993 && forward_range<const _Vp>
2994 && common_range<const _Vp>)
2995 return _OuterIter<true>{this, ranges::end(_M_base)};
2997 return default_sentinel;
3001 template<typename _Range, typename _Pattern>
3002 split_view(_Range&&, _Pattern&&)
3003 -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3005 template<input_range _Range>
3006 split_view(_Range&&, range_value_t<_Range>)
3007 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3013 template<typename _Range, typename _Pattern>
3014 concept __can_split_view
3015 = requires { split_view{std::declval<_Range>(), std::declval<_Pattern>()}; };
3016 } // namespace __detail
3018 struct _Split : __adaptor::_RangeAdaptor<_Split>
3020 template<viewable_range _Range, typename _Pattern>
3021 requires __detail::__can_split_view<_Range, _Pattern>
3023 operator()(_Range&& __r, _Pattern&& __f) const
3025 return split_view{std::forward<_Range>(__r), std::forward<_Pattern>(__f)};
3028 using _RangeAdaptor<_Split>::operator();
3029 static constexpr int _S_arity = 2;
3032 inline constexpr _Split split;
3033 } // namespace views
3039 template<input_or_output_iterator _Iter>
3041 operator()(_Iter __i, iter_difference_t<_Iter> __n) const
3043 if constexpr (random_access_iterator<_Iter>)
3044 return subrange{__i, __i + __n};
3046 return subrange{counted_iterator{std::move(__i), __n},
3051 inline constexpr _Counted counted{};
3052 } // namespace views
3055 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3056 class common_view : public view_interface<common_view<_Vp>>
3059 _Vp _M_base = _Vp();
3062 common_view() = default;
3065 common_view(_Vp __r)
3066 : _M_base(std::move(__r))
3069 /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3070 template<viewable_range _Range>
3071 requires (!common_range<_Range>)
3072 && constructible_from<_Vp, views::all_t<_Range>>
3074 common_view(_Range&& __r)
3075 : _M_base(views::all(std::forward<_Range>(__r)))
3080 base() const& requires copy_constructible<_Vp>
3085 { return std::move(_M_base); }
3090 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3091 return ranges::begin(_M_base);
3093 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3094 (ranges::begin(_M_base));
3098 begin() const requires range<const _Vp>
3100 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3101 return ranges::begin(_M_base);
3103 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3104 (ranges::begin(_M_base));
3110 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3111 return ranges::begin(_M_base) + ranges::size(_M_base);
3113 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3114 (ranges::end(_M_base));
3118 end() const requires range<const _Vp>
3120 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3121 return ranges::begin(_M_base) + ranges::size(_M_base);
3123 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3124 (ranges::end(_M_base));
3128 size() requires sized_range<_Vp>
3129 { return ranges::size(_M_base); }
3132 size() const requires sized_range<const _Vp>
3133 { return ranges::size(_M_base); }
3136 template<typename _Range>
3137 common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3139 template<typename _Tp>
3140 inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3141 = enable_borrowed_range<_Tp>;
3147 template<typename _Range>
3148 concept __already_common = common_range<_Range>
3149 && requires { views::all(std::declval<_Range>()); };
3151 template<typename _Range>
3152 concept __can_common_view
3153 = requires { common_view{std::declval<_Range>()}; };
3154 } // namespace __detail
3156 struct _Common : __adaptor::_RangeAdaptorClosure
3158 template<viewable_range _Range>
3159 requires __detail::__already_common<_Range>
3160 || __detail::__can_common_view<_Range>
3162 operator()(_Range&& __r) const
3164 if constexpr (__detail::__already_common<_Range>)
3165 return views::all(std::forward<_Range>(__r));
3167 return common_view{std::forward<_Range>(__r)};
3171 inline constexpr _Common common;
3172 } // namespace views
3175 requires bidirectional_range<_Vp>
3176 class reverse_view : public view_interface<reverse_view<_Vp>>
3179 static constexpr bool _S_needs_cached_begin
3180 = !common_range<_Vp> && !random_access_range<_Vp>;
3182 [[no_unique_address]]
3183 __detail::__maybe_present_t<_S_needs_cached_begin,
3184 __detail::_CachedPosition<_Vp>>
3186 _Vp _M_base = _Vp();
3189 reverse_view() = default;
3192 reverse_view(_Vp __r)
3193 : _M_base(std::move(__r))
3197 base() const& requires copy_constructible<_Vp>
3202 { return std::move(_M_base); }
3204 constexpr reverse_iterator<iterator_t<_Vp>>
3207 if constexpr (_S_needs_cached_begin)
3208 if (_M_cached_begin._M_has_value())
3209 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3211 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3212 if constexpr (_S_needs_cached_begin)
3213 _M_cached_begin._M_set(_M_base, __it);
3214 return std::make_reverse_iterator(std::move(__it));
3218 begin() requires common_range<_Vp>
3219 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3222 begin() const requires common_range<const _Vp>
3223 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3225 constexpr reverse_iterator<iterator_t<_Vp>>
3227 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3230 end() const requires common_range<const _Vp>
3231 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3234 size() requires sized_range<_Vp>
3235 { return ranges::size(_M_base); }
3238 size() const requires sized_range<const _Vp>
3239 { return ranges::size(_M_base); }
3242 template<typename _Range>
3243 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3245 template<typename _Tp>
3246 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3247 = enable_borrowed_range<_Tp>;
3254 inline constexpr bool __is_reversible_subrange = false;
3256 template<typename _Iter, subrange_kind _Kind>
3257 inline constexpr bool
3258 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3259 reverse_iterator<_Iter>,
3263 inline constexpr bool __is_reverse_view = false;
3265 template<typename _Vp>
3266 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3268 template<typename _Range>
3269 concept __can_reverse_view
3270 = requires { reverse_view{std::declval<_Range>()}; };
3271 } // namespace __detail
3273 struct _Reverse : __adaptor::_RangeAdaptorClosure
3275 template<viewable_range _Range>
3276 requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3277 || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3278 || __detail::__can_reverse_view<_Range>
3280 operator()(_Range&& __r) const
3282 using _Tp = remove_cvref_t<_Range>;
3283 if constexpr (__detail::__is_reverse_view<_Tp>)
3284 return std::forward<_Range>(__r).base();
3285 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3287 using _Iter = decltype(ranges::begin(__r).base());
3288 if constexpr (sized_range<_Tp>)
3289 return subrange<_Iter, _Iter, subrange_kind::sized>
3290 {__r.end().base(), __r.begin().base(), __r.size()};
3292 return subrange<_Iter, _Iter, subrange_kind::unsized>
3293 {__r.end().base(), __r.begin().base()};
3296 return reverse_view{std::forward<_Range>(__r)};
3300 inline constexpr _Reverse reverse;
3301 } // namespace views
3305 template<typename _Tp, size_t _Nm>
3306 concept __has_tuple_element = requires(_Tp __t)
3308 typename tuple_size<_Tp>::type;
3309 requires _Nm < tuple_size_v<_Tp>;
3310 typename tuple_element_t<_Nm, _Tp>;
3311 { std::get<_Nm>(__t) }
3312 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3315 template<typename _Tp, size_t _Nm>
3316 concept __returnable_element
3317 = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
3320 template<input_range _Vp, size_t _Nm>
3322 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3323 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3325 && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
3326 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3329 elements_view() = default;
3332 elements_view(_Vp base)
3333 : _M_base(std::move(base))
3337 base() const& requires copy_constructible<_Vp>
3342 { return std::move(_M_base); }
3345 begin() requires (!__detail::__simple_view<_Vp>)
3346 { return _Iterator<false>(ranges::begin(_M_base)); }
3349 begin() const requires range<const _Vp>
3350 { return _Iterator<true>(ranges::begin(_M_base)); }
3353 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3354 { return _Sentinel<false>{ranges::end(_M_base)}; }
3357 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3358 { return _Iterator<false>{ranges::end(_M_base)}; }
3361 end() const requires range<const _Vp>
3362 { return _Sentinel<true>{ranges::end(_M_base)}; }
3365 end() const requires common_range<const _Vp>
3366 { return _Iterator<true>{ranges::end(_M_base)}; }
3369 size() requires sized_range<_Vp>
3370 { return ranges::size(_M_base); }
3373 size() const requires sized_range<const _Vp>
3374 { return ranges::size(_M_base); }
3377 template<bool _Const>
3378 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3380 template<bool _Const>
3384 template<bool _Const>
3385 requires forward_range<_Base<_Const>>
3386 struct __iter_cat<_Const>
3389 static auto _S_iter_cat()
3391 using _Base = elements_view::_Base<_Const>;
3392 using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category;
3393 using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
3394 if constexpr (!is_lvalue_reference_v<_Res>)
3395 return input_iterator_tag{};
3396 else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
3397 return random_access_iterator_tag{};
3402 using iterator_category = decltype(_S_iter_cat());
3405 template<bool _Const>
3408 template<bool _Const>
3409 struct _Iterator : __iter_cat<_Const>
3412 using _Base = elements_view::_Base<_Const>;
3414 iterator_t<_Base> _M_current = iterator_t<_Base>();
3416 static constexpr decltype(auto)
3417 _S_get_element(const iterator_t<_Base>& __i)
3419 if constexpr (is_reference_v<range_reference_t<_Base>>)
3420 return std::get<_Nm>(*__i);
3423 using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
3424 return static_cast<_Et>(std::get<_Nm>(*__i));
3431 if constexpr (random_access_range<_Vp>)
3432 return random_access_iterator_tag{};
3433 else if constexpr (bidirectional_range<_Vp>)
3434 return bidirectional_iterator_tag{};
3435 else if constexpr (forward_range<_Vp>)
3436 return forward_iterator_tag{};
3438 return input_iterator_tag{};
3441 friend _Iterator<!_Const>;
3444 using iterator_concept = decltype(_S_iter_concept());
3445 // iterator_category defined in elements_view::__iter_cat
3447 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3448 using difference_type = range_difference_t<_Base>;
3450 _Iterator() = default;
3453 _Iterator(iterator_t<_Base> current)
3454 : _M_current(std::move(current))
3458 _Iterator(_Iterator<!_Const> i)
3459 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3460 : _M_current(std::move(i._M_current))
3463 constexpr iterator_t<_Base>
3465 requires copyable<iterator_t<_Base>>
3466 { return _M_current; }
3468 constexpr iterator_t<_Base>
3470 { return std::move(_M_current); }
3472 constexpr decltype(auto)
3474 { return _S_get_element(_M_current); }
3476 constexpr _Iterator&
3488 operator++(int) requires forward_range<_Base>
3495 constexpr _Iterator&
3496 operator--() requires bidirectional_range<_Base>
3503 operator--(int) requires bidirectional_range<_Base>
3510 constexpr _Iterator&
3511 operator+=(difference_type __n)
3512 requires random_access_range<_Base>
3518 constexpr _Iterator&
3519 operator-=(difference_type __n)
3520 requires random_access_range<_Base>
3526 constexpr decltype(auto)
3527 operator[](difference_type __n) const
3528 requires random_access_range<_Base>
3529 { return _S_get_element(_M_current + __n); }
3531 friend constexpr bool
3532 operator==(const _Iterator& __x, const _Iterator& __y)
3533 requires equality_comparable<iterator_t<_Base>>
3534 { return __x._M_current == __y._M_current; }
3536 friend constexpr bool
3537 operator<(const _Iterator& __x, const _Iterator& __y)
3538 requires random_access_range<_Base>
3539 { return __x._M_current < __y._M_current; }
3541 friend constexpr bool
3542 operator>(const _Iterator& __x, const _Iterator& __y)
3543 requires random_access_range<_Base>
3544 { return __y._M_current < __x._M_current; }
3546 friend constexpr bool
3547 operator<=(const _Iterator& __x, const _Iterator& __y)
3548 requires random_access_range<_Base>
3549 { return !(__y._M_current > __x._M_current); }
3551 friend constexpr bool
3552 operator>=(const _Iterator& __x, const _Iterator& __y)
3553 requires random_access_range<_Base>
3554 { return !(__x._M_current > __y._M_current); }
3556 #ifdef __cpp_lib_three_way_comparison
3557 friend constexpr auto
3558 operator<=>(const _Iterator& __x, const _Iterator& __y)
3559 requires random_access_range<_Base>
3560 && three_way_comparable<iterator_t<_Base>>
3561 { return __x._M_current <=> __y._M_current; }
3564 friend constexpr _Iterator
3565 operator+(const _Iterator& __x, difference_type __y)
3566 requires random_access_range<_Base>
3567 { return _Iterator{__x} += __y; }
3569 friend constexpr _Iterator
3570 operator+(difference_type __x, const _Iterator& __y)
3571 requires random_access_range<_Base>
3572 { return __y + __x; }
3574 friend constexpr _Iterator
3575 operator-(const _Iterator& __x, difference_type __y)
3576 requires random_access_range<_Base>
3577 { return _Iterator{__x} -= __y; }
3579 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3580 // 3483. transform_view::iterator's difference is overconstrained
3581 friend constexpr difference_type
3582 operator-(const _Iterator& __x, const _Iterator& __y)
3583 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3584 { return __x._M_current - __y._M_current; }
3586 friend _Sentinel<_Const>;
3589 template<bool _Const>
3594 _M_equal(const _Iterator<_Const>& __x) const
3595 { return __x._M_current == _M_end; }
3597 using _Base = elements_view::_Base<_Const>;
3598 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3601 _Sentinel() = default;
3604 _Sentinel(sentinel_t<_Base> __end)
3605 : _M_end(std::move(__end))
3609 _Sentinel(_Sentinel<!_Const> __other)
3611 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3612 : _M_end(std::move(__other._M_end))
3615 constexpr sentinel_t<_Base>
3619 template<bool _Const2>
3620 requires sentinel_for<sentinel_t<_Base>,
3621 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3622 friend constexpr bool
3623 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3624 { return __y._M_equal(__x); }
3626 template<bool _Const2,
3627 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3628 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3629 friend constexpr range_difference_t<_Base2>
3630 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3631 { return __x._M_current - __y._M_end; }
3633 template<bool _Const2,
3634 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3635 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3636 friend constexpr range_difference_t<_Base>
3637 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3638 { return __x._M_end - __y._M_current; }
3640 friend _Sentinel<!_Const>;
3643 _Vp _M_base = _Vp();
3646 template<typename _Tp, size_t _Nm>
3647 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3648 = enable_borrowed_range<_Tp>;
3650 template<typename _Range>
3651 using keys_view = elements_view<views::all_t<_Range>, 0>;
3653 template<typename _Range>
3654 using values_view = elements_view<views::all_t<_Range>, 1>;
3660 template<size_t _Nm, typename _Range>
3661 concept __can_elements_view
3662 = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
3663 } // namespace __detail
3665 template<size_t _Nm>
3666 struct _Elements : __adaptor::_RangeAdaptorClosure
3668 template<viewable_range _Range>
3669 requires __detail::__can_elements_view<_Nm, _Range>
3671 operator()(_Range&& __r) const
3673 return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
3677 template<size_t _Nm>
3678 inline constexpr _Elements<_Nm> elements;
3679 inline constexpr auto keys = elements<0>;
3680 inline constexpr auto values = elements<1>;
3681 } // namespace views
3683 } // namespace ranges
3685 namespace views = ranges::views;
3687 _GLIBCXX_END_NAMESPACE_VERSION
3689 #endif // library concepts
3691 #endif /* _GLIBCXX_RANGES */