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 } // namespace __detail
295 template<weakly_incrementable _Winc,
296 semiregular _Bound = unreachable_sentinel_t>
297 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
298 && semiregular<_Winc>
299 class iota_view : public view_interface<iota_view<_Winc, _Bound>>
310 using namespace __detail;
311 if constexpr (__advanceable<_Winc>)
312 return random_access_iterator_tag{};
313 else if constexpr (__decrementable<_Winc>)
314 return bidirectional_iterator_tag{};
315 else if constexpr (incrementable<_Winc>)
316 return forward_iterator_tag{};
318 return input_iterator_tag{};
322 using iterator_category = decltype(_S_iter_cat());
323 using value_type = _Winc;
324 using difference_type = __detail::__iota_diff_t<_Winc>;
326 _Iterator() = default;
329 _Iterator(_Winc __value)
330 : _M_value(__value) { }
333 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
348 operator++(int) requires incrementable<_Winc>
356 operator--() requires __detail::__decrementable<_Winc>
363 operator--(int) requires __detail::__decrementable<_Winc>
371 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
373 using __detail::__is_integer_like;
374 using __detail::__is_signed_integer_like;
375 if constexpr (__is_integer_like<_Winc>
376 && !__is_signed_integer_like<_Winc>)
378 if (__n >= difference_type(0))
379 _M_value += static_cast<_Winc>(__n);
381 _M_value -= static_cast<_Winc>(-__n);
389 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
391 using __detail::__is_integer_like;
392 using __detail::__is_signed_integer_like;
393 if constexpr (__is_integer_like<_Winc>
394 && !__is_signed_integer_like<_Winc>)
396 if (__n >= difference_type(0))
397 _M_value -= static_cast<_Winc>(__n);
399 _M_value += static_cast<_Winc>(-__n);
407 operator[](difference_type __n) const
408 requires __detail::__advanceable<_Winc>
409 { return _Winc(_M_value + __n); }
411 friend constexpr bool
412 operator==(const _Iterator& __x, const _Iterator& __y)
413 requires equality_comparable<_Winc>
414 { return __x._M_value == __y._M_value; }
416 friend constexpr bool
417 operator<(const _Iterator& __x, const _Iterator& __y)
418 requires totally_ordered<_Winc>
419 { return __x._M_value < __y._M_value; }
421 friend constexpr bool
422 operator>(const _Iterator& __x, const _Iterator& __y)
423 requires totally_ordered<_Winc>
424 { return __y < __x; }
426 friend constexpr bool
427 operator<=(const _Iterator& __x, const _Iterator& __y)
428 requires totally_ordered<_Winc>
429 { return !(__y < __x); }
431 friend constexpr bool
432 operator>=(const _Iterator& __x, const _Iterator& __y)
433 requires totally_ordered<_Winc>
434 { return !(__x < __y); }
436 #ifdef __cpp_lib_three_way_comparison
437 friend constexpr auto
438 operator<=>(const _Iterator& __x, const _Iterator& __y)
439 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
440 { return __x._M_value <=> __y._M_value; }
443 friend constexpr _Iterator
444 operator+(_Iterator __i, difference_type __n)
445 requires __detail::__advanceable<_Winc>
446 { return __i += __n; }
448 friend constexpr _Iterator
449 operator+(difference_type __n, _Iterator __i)
450 requires __detail::__advanceable<_Winc>
451 { return __i += __n; }
453 friend constexpr _Iterator
454 operator-(_Iterator __i, difference_type __n)
455 requires __detail::__advanceable<_Winc>
456 { return __i -= __n; }
458 friend constexpr difference_type
459 operator-(const _Iterator& __x, const _Iterator& __y)
460 requires __detail::__advanceable<_Winc>
462 using __detail::__is_integer_like;
463 using __detail::__is_signed_integer_like;
464 using _Dt = difference_type;
465 if constexpr (__is_integer_like<_Winc>)
467 if constexpr (__is_signed_integer_like<_Winc>)
468 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
470 return (__y._M_value > __x._M_value)
471 ? _Dt(-_Dt(__y._M_value - __x._M_value))
472 : _Dt(__x._M_value - __y._M_value);
475 return __x._M_value - __y._M_value;
479 _Winc _M_value = _Winc();
488 _M_equal(const _Iterator& __x) const
489 { return __x._M_value == _M_bound; }
491 _Bound _M_bound = _Bound();
494 _Sentinel() = default;
497 _Sentinel(_Bound __bound)
498 : _M_bound(__bound) { }
500 friend constexpr bool
501 operator==(const _Iterator& __x, const _Sentinel& __y)
502 { return __y._M_equal(__x); }
504 friend constexpr iter_difference_t<_Winc>
505 operator-(const _Iterator& __x, const _Sentinel& __y)
506 requires sized_sentinel_for<_Bound, _Winc>
507 { return __x._M_value - __y._M_bound; }
509 friend constexpr iter_difference_t<_Winc>
510 operator-(const _Sentinel& __x, const _Iterator& __y)
511 requires sized_sentinel_for<_Bound, _Winc>
512 { return -(__y - __x); }
515 _Winc _M_value = _Winc();
516 [[no_unique_address]] _Bound _M_bound = _Bound();
519 iota_view() = default;
522 iota_view(_Winc __value)
527 iota_view(type_identity_t<_Winc> __value,
528 type_identity_t<_Bound> __bound)
529 : _M_value(__value), _M_bound(__bound)
531 if constexpr (totally_ordered_with<_Winc, _Bound>)
532 __glibcxx_assert( bool(__value <= __bound) );
536 begin() const { return _Iterator{_M_value}; }
541 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
542 return unreachable_sentinel;
544 return _Sentinel{_M_bound};
548 end() const requires same_as<_Winc, _Bound>
549 { return _Iterator{_M_bound}; }
553 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
554 || (integral<_Winc> && integral<_Bound>)
555 || sized_sentinel_for<_Bound, _Winc>
557 using __detail::__is_integer_like;
558 using __detail::__to_unsigned_like;
559 if constexpr (integral<_Winc> && integral<_Bound>)
561 using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>;
562 return _Up(_M_bound) - _Up(_M_value);
564 else if constexpr (__is_integer_like<_Winc>)
565 return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
567 return __to_unsigned_like(_M_bound - _M_value);
571 template<typename _Winc, typename _Bound>
572 requires (!__detail::__is_integer_like<_Winc>
573 || !__detail::__is_integer_like<_Bound>
574 || (__detail::__is_signed_integer_like<_Winc>
575 == __detail::__is_signed_integer_like<_Bound>))
576 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
578 template<weakly_incrementable _Winc, semiregular _Bound>
579 inline constexpr bool
580 enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
584 template<typename _Tp>
585 inline constexpr empty_view<_Tp> empty{};
589 template<typename _Tp>
591 operator()(_Tp&& __e) const
592 { return single_view{std::forward<_Tp>(__e)}; }
595 inline constexpr _Single single{};
599 template<typename _Tp>
601 operator()(_Tp&& __e) const
602 { return iota_view{std::forward<_Tp>(__e)}; }
604 template<typename _Tp, typename _Up>
606 operator()(_Tp&& __e, _Up&& __f) const
607 { return iota_view{std::forward<_Tp>(__e), std::forward<_Up>(__f)}; }
610 inline constexpr _Iota iota{};
615 template<typename _Val, typename _CharT, typename _Traits>
616 concept __stream_extractable
617 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
618 } // namespace __detail
620 template<movable _Val, typename _CharT, typename _Traits>
621 requires default_initializable<_Val>
622 && __detail::__stream_extractable<_Val, _CharT, _Traits>
623 class basic_istream_view
624 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
627 basic_istream_view() = default;
630 basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
631 : _M_stream(std::__addressof(__stream))
637 if (_M_stream != nullptr)
638 *_M_stream >> _M_object;
639 return _Iterator{this};
642 constexpr default_sentinel_t
644 { return default_sentinel; }
647 basic_istream<_CharT, _Traits>* _M_stream = nullptr;
648 _Val _M_object = _Val();
653 using iterator_concept = input_iterator_tag;
654 using difference_type = ptrdiff_t;
655 using value_type = _Val;
657 _Iterator() = default;
660 _Iterator(basic_istream_view* __parent) noexcept
661 : _M_parent(__parent)
664 _Iterator(const _Iterator&) = delete;
665 _Iterator(_Iterator&&) = default;
666 _Iterator& operator=(const _Iterator&) = delete;
667 _Iterator& operator=(_Iterator&&) = default;
672 __glibcxx_assert(_M_parent->_M_stream != nullptr);
673 *_M_parent->_M_stream >> _M_parent->_M_object;
684 __glibcxx_assert(_M_parent->_M_stream != nullptr);
685 return _M_parent->_M_object;
689 operator==(const _Iterator& __x, default_sentinel_t)
690 { return __x._M_at_end(); }
693 basic_istream_view* _M_parent = nullptr;
697 { return _M_parent == nullptr || !*_M_parent->_M_stream; }
703 template<typename _Val, typename _CharT, typename _Traits>
704 basic_istream_view<_Val, _CharT, _Traits>
705 istream_view(basic_istream<_CharT, _Traits>& __s)
706 { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
708 // C++20 24.7 [range.adaptors] Range adaptors
714 // Alias for a type that is conditionally present
715 // (and is an empty type otherwise).
716 // Data members using this alias should use [[no_unique_address]] so that
717 // they take no space when not needed.
718 template<bool _Present, typename _Tp>
719 using __maybe_present_t = conditional_t<_Present, _Tp, _Empty>;
721 // Alias for a type that is conditionally const.
722 template<bool _Const, typename _Tp>
723 using __maybe_const_t = conditional_t<_Const, const _Tp, _Tp>;
725 } // namespace __detail
727 namespace views::__adaptor
729 // True if the range adaptor _Adaptor can be applied with _Args.
730 template<typename _Adaptor, typename... _Args>
731 concept __adaptor_invocable
732 = requires { std::declval<_Adaptor>()(declval<_Args>()...); };
734 // True if the range adaptor non-closure _Adaptor can be partially applied
736 template<typename _Adaptor, typename... _Args>
737 concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
738 && (sizeof...(_Args) == _Adaptor::_S_arity - 1)
739 && (constructible_from<decay_t<_Args>, _Args> && ...);
741 template<typename _Adaptor, typename... _Args>
744 template<typename _Lhs, typename _Rhs>
747 // The base class of every range adaptor closure.
748 struct _RangeAdaptorClosure
750 // range | adaptor is equivalent to adaptor(range).
751 template<typename _Self, typename _Range>
752 requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
753 && __adaptor_invocable<_Self, _Range>
754 friend constexpr auto
755 operator|(_Range&& __r, _Self&& __self)
756 { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
758 // Compose the adaptors __lhs and __rhs into a pipeline, returning
759 // another range adaptor closure object.
760 template<typename _Lhs, typename _Rhs>
761 requires derived_from<_Lhs, _RangeAdaptorClosure>
762 && derived_from<_Rhs, _RangeAdaptorClosure>
763 friend constexpr auto
764 operator|(_Lhs __lhs, _Rhs __rhs)
765 { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
768 // The base class of every range adaptor non-closure.
770 // The static data member _Derived::_S_arity must contain the total number of
771 // arguments that the adaptor takes, and the class _Derived must introduce
772 // _RangeAdaptor::operator() into the class scope via a using-declaration.
773 template<typename _Derived>
776 // Partially apply the arguments __args to the range adaptor _Derived,
777 // returning a range adaptor closure object.
778 template<typename... _Args>
779 requires __adaptor_partial_app_viable<_Derived, _Args...>
781 operator()(_Args&&... __args) const
783 return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
787 // A range adaptor closure that represents partial application of
788 // the range adaptor _Adaptor with arguments _Args.
789 template<typename _Adaptor, typename... _Args>
790 struct _Partial : _RangeAdaptorClosure
792 tuple<_Args...> _M_args;
795 _Partial(_Args... __args)
796 : _M_args(std::move(__args)...)
799 // Invoke _Adaptor with arguments __r, _M_args... according to the
800 // value category of the range adaptor closure object.
801 template<typename _Range>
802 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
804 operator()(_Range&& __r) const &
806 auto __forwarder = [&__r] (const auto&... __args) {
807 return _Adaptor{}(std::forward<_Range>(__r), __args...);
809 return std::apply(__forwarder, _M_args);
812 template<typename _Range>
813 requires __adaptor_invocable<_Adaptor, _Range, _Args...>
815 operator()(_Range&& __r) &&
817 auto __forwarder = [&__r] (auto&... __args) {
818 return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...);
820 return std::apply(__forwarder, _M_args);
823 template<typename _Range>
825 operator()(_Range&& __r) const && = delete;
828 // A lightweight specialization of the above primary template for
829 // the common case where _Adaptor accepts a single extra argument.
830 template<typename _Adaptor, typename _Arg>
831 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
837 : _M_arg(std::move(__arg))
840 template<typename _Range>
841 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
843 operator()(_Range&& __r) const &
844 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
846 template<typename _Range>
847 requires __adaptor_invocable<_Adaptor, _Range, _Arg>
849 operator()(_Range&& __r) &&
850 { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
852 template<typename _Range>
854 operator()(_Range&& __r) const && = delete;
857 template<typename _Lhs, typename _Rhs, typename _Range>
858 concept __pipe_invocable
859 = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); };
861 // A range adaptor closure that represents composition of the range
862 // adaptor closures _Lhs and _Rhs.
863 template<typename _Lhs, typename _Rhs>
864 struct _Pipe : _RangeAdaptorClosure
866 [[no_unique_address]] _Lhs _M_lhs;
867 [[no_unique_address]] _Rhs _M_rhs;
870 _Pipe(_Lhs __lhs, _Rhs __rhs)
871 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
874 // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this
875 // range adaptor closure object.
876 template<typename _Range>
877 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
879 operator()(_Range&& __r) const &
880 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
882 template<typename _Range>
883 requires __pipe_invocable<_Lhs, _Rhs, _Range>
885 operator()(_Range&& __r) &&
886 { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); }
888 template<typename _Range>
890 operator()(_Range&& __r) const && = delete;
892 } // namespace views::__adaptor
894 template<range _Range> requires is_object_v<_Range>
895 class ref_view : public view_interface<ref_view<_Range>>
898 _Range* _M_r = nullptr;
900 static void _S_fun(_Range&); // not defined
901 static void _S_fun(_Range&&) = delete;
905 ref_view() noexcept = default;
907 template<__detail::__not_same_as<ref_view> _Tp>
908 requires convertible_to<_Tp, _Range&>
909 && requires { _S_fun(declval<_Tp>()); }
912 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
919 constexpr iterator_t<_Range>
921 { return ranges::begin(*_M_r); }
923 constexpr sentinel_t<_Range>
925 { return ranges::end(*_M_r); }
928 empty() const requires requires { ranges::empty(*_M_r); }
929 { return ranges::empty(*_M_r); }
932 size() const requires sized_range<_Range>
933 { return ranges::size(*_M_r); }
936 data() const requires contiguous_range<_Range>
937 { return ranges::data(*_M_r); }
940 template<typename _Range>
941 ref_view(_Range&) -> ref_view<_Range>;
943 template<typename _Tp>
944 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
950 template<typename _Range>
951 concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
953 template<typename _Range>
954 concept __can_subrange = requires { subrange{std::declval<_Range>()}; };
955 } // namespace __detail
957 struct _All : __adaptor::_RangeAdaptorClosure
959 template<viewable_range _Range>
960 requires view<decay_t<_Range>>
961 || __detail::__can_ref_view<_Range>
962 || __detail::__can_subrange<_Range>
964 operator()(_Range&& __r) const
966 if constexpr (view<decay_t<_Range>>)
967 return std::forward<_Range>(__r);
968 else if constexpr (__detail::__can_ref_view<_Range>)
969 return ref_view{std::forward<_Range>(__r)};
971 return subrange{std::forward<_Range>(__r)};
975 inline constexpr _All all;
977 template<viewable_range _Range>
978 using all_t = decltype(all(std::declval<_Range>()));
981 // The following simple algos are transcribed from ranges_algo.h to avoid
982 // having to include that entire header.
985 template<typename _Iter, typename _Sent, typename _Tp>
987 find(_Iter __first, _Sent __last, const _Tp& __value)
989 while (__first != __last
990 && !(bool)(*__first == __value))
995 template<typename _Iter, typename _Sent, typename _Pred>
997 find_if(_Iter __first, _Sent __last, _Pred __pred)
999 while (__first != __last
1000 && !(bool)std::__invoke(__pred, *__first))
1005 template<typename _Iter, typename _Sent, typename _Pred>
1007 find_if_not(_Iter __first, _Sent __last, _Pred __pred)
1009 while (__first != __last
1010 && (bool)std::__invoke(__pred, *__first))
1015 template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2>
1016 constexpr pair<_Iter1, _Iter2>
1017 mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2)
1019 while (__first1 != __last1 && __first2 != __last2
1020 && (bool)ranges::equal_to{}(*__first1, *__first2))
1025 return { std::move(__first1), std::move(__first2) };
1027 } // namespace __detail
1031 template<range _Range>
1032 struct _CachedPosition
1035 _M_has_value() const
1038 constexpr iterator_t<_Range>
1039 _M_get(const _Range&) const
1041 __glibcxx_assert(false);
1046 _M_set(const _Range&, const iterator_t<_Range>&) const
1050 template<forward_range _Range>
1051 struct _CachedPosition<_Range>
1054 iterator_t<_Range> _M_iter{};
1058 _M_has_value() const
1059 { return _M_iter != iterator_t<_Range>{}; }
1061 constexpr iterator_t<_Range>
1062 _M_get(const _Range&) const
1064 __glibcxx_assert(_M_has_value());
1069 _M_set(const _Range&, const iterator_t<_Range>& __it)
1071 __glibcxx_assert(!_M_has_value());
1076 template<random_access_range _Range>
1077 requires (sizeof(range_difference_t<_Range>)
1078 <= sizeof(iterator_t<_Range>))
1079 struct _CachedPosition<_Range>
1082 range_difference_t<_Range> _M_offset = -1;
1086 _M_has_value() const
1087 { return _M_offset >= 0; }
1089 constexpr iterator_t<_Range>
1090 _M_get(_Range& __r) const
1092 __glibcxx_assert(_M_has_value());
1093 return ranges::begin(__r) + _M_offset;
1097 _M_set(_Range& __r, const iterator_t<_Range>& __it)
1099 __glibcxx_assert(!_M_has_value());
1100 _M_offset = __it - ranges::begin(__r);
1104 } // namespace __detail
1106 template<input_range _Vp,
1107 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1108 requires view<_Vp> && is_object_v<_Pred>
1109 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1117 static constexpr auto
1120 if constexpr (bidirectional_range<_Vp>)
1121 return bidirectional_iterator_tag{};
1122 else if constexpr (forward_range<_Vp>)
1123 return forward_iterator_tag{};
1125 return input_iterator_tag{};
1128 static constexpr auto
1131 using _Cat = typename iterator_traits<_Vp_iter>::iterator_category;
1132 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1133 return bidirectional_iterator_tag{};
1134 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1135 return forward_iterator_tag{};
1142 using _Vp_iter = iterator_t<_Vp>;
1144 _Vp_iter _M_current = _Vp_iter();
1145 filter_view* _M_parent = nullptr;
1148 using iterator_concept = decltype(_S_iter_concept());
1149 using iterator_category = decltype(_S_iter_cat());
1150 using value_type = range_value_t<_Vp>;
1151 using difference_type = range_difference_t<_Vp>;
1153 _Iterator() = default;
1156 _Iterator(filter_view* __parent, _Vp_iter __current)
1157 : _M_current(std::move(__current)),
1163 requires copyable<_Vp_iter>
1164 { return _M_current; }
1168 { return std::move(_M_current); }
1170 constexpr range_reference_t<_Vp>
1172 { return *_M_current; }
1176 requires __detail::__has_arrow<_Vp_iter>
1177 && copyable<_Vp_iter>
1178 { return _M_current; }
1180 constexpr _Iterator&
1183 _M_current = __detail::find_if(std::move(++_M_current),
1184 ranges::end(_M_parent->_M_base),
1185 std::ref(*_M_parent->_M_pred));
1194 operator++(int) requires forward_range<_Vp>
1201 constexpr _Iterator&
1202 operator--() requires bidirectional_range<_Vp>
1206 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1211 operator--(int) requires bidirectional_range<_Vp>
1218 friend constexpr bool
1219 operator==(const _Iterator& __x, const _Iterator& __y)
1220 requires equality_comparable<_Vp_iter>
1221 { return __x._M_current == __y._M_current; }
1223 friend constexpr range_rvalue_reference_t<_Vp>
1224 iter_move(const _Iterator& __i)
1225 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1226 { return ranges::iter_move(__i._M_current); }
1228 friend constexpr void
1229 iter_swap(const _Iterator& __x, const _Iterator& __y)
1230 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1231 requires indirectly_swappable<_Vp_iter>
1232 { ranges::iter_swap(__x._M_current, __y._M_current); }
1238 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1241 __equal(const _Iterator& __i) const
1242 { return __i._M_current == _M_end; }
1245 _Sentinel() = default;
1248 _Sentinel(filter_view* __parent)
1249 : _M_end(ranges::end(__parent->_M_base))
1252 constexpr sentinel_t<_Vp>
1256 friend constexpr bool
1257 operator==(const _Iterator& __x, const _Sentinel& __y)
1258 { return __y.__equal(__x); }
1261 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1262 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1263 _Vp _M_base = _Vp();
1266 filter_view() = default;
1269 filter_view(_Vp __base, _Pred __pred)
1270 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
1274 base() const& requires copy_constructible<_Vp>
1279 { return std::move(_M_base); }
1281 constexpr const _Pred&
1283 { return *_M_pred; }
1288 if (_M_cached_begin._M_has_value())
1289 return {this, _M_cached_begin._M_get(_M_base)};
1291 __glibcxx_assert(_M_pred.has_value());
1292 auto __it = __detail::find_if(ranges::begin(_M_base),
1293 ranges::end(_M_base),
1294 std::ref(*_M_pred));
1295 _M_cached_begin._M_set(_M_base, __it);
1296 return {this, std::move(__it)};
1302 if constexpr (common_range<_Vp>)
1303 return _Iterator{this, ranges::end(_M_base)};
1305 return _Sentinel{this};
1309 template<typename _Range, typename _Pred>
1310 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1316 template<typename _Range, typename _Pred>
1317 concept __can_filter_view
1318 = requires { filter_view{std::declval<_Range>(), std::declval<_Pred>()}; };
1319 } // namespace __detail
1321 struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1323 template<viewable_range _Range, typename _Pred>
1324 requires __detail::__can_filter_view<_Range, _Pred>
1326 operator()(_Range&& __r, _Pred&& __p) const
1328 return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1331 using _RangeAdaptor<_Filter>::operator();
1332 static constexpr int _S_arity = 2;
1335 inline constexpr _Filter filter;
1336 } // namespace views
1338 template<input_range _Vp, copy_constructible _Fp>
1339 requires view<_Vp> && is_object_v<_Fp>
1340 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1341 && std::__detail::__can_reference<invoke_result_t<_Fp&,
1342 range_reference_t<_Vp>>>
1343 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1346 template<bool _Const>
1349 template<bool _Const>
1353 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1354 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1356 static constexpr auto
1359 if constexpr (random_access_range<_Vp>)
1360 return random_access_iterator_tag{};
1361 else if constexpr (bidirectional_range<_Vp>)
1362 return bidirectional_iterator_tag{};
1363 else if constexpr (forward_range<_Vp>)
1364 return forward_iterator_tag{};
1366 return input_iterator_tag{};
1369 static constexpr auto
1372 using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1373 if constexpr (is_lvalue_reference_v<_Res>)
1376 = typename iterator_traits<_Base_iter>::iterator_category;
1377 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1378 return random_access_iterator_tag{};
1383 return input_iterator_tag{};
1386 using _Base_iter = iterator_t<_Base>;
1388 _Base_iter _M_current = _Base_iter();
1389 _Parent* _M_parent = nullptr;
1392 using iterator_concept = decltype(_S_iter_concept());
1393 using iterator_category = decltype(_S_iter_cat());
1395 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1396 using difference_type = range_difference_t<_Base>;
1398 _Iterator() = default;
1401 _Iterator(_Parent* __parent, _Base_iter __current)
1402 : _M_current(std::move(__current)),
1407 _Iterator(_Iterator<!_Const> __i)
1409 && convertible_to<iterator_t<_Vp>, _Base_iter>
1410 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1413 constexpr _Base_iter
1415 requires copyable<_Base_iter>
1416 { return _M_current; }
1418 constexpr _Base_iter
1420 { return std::move(_M_current); }
1422 constexpr decltype(auto)
1424 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1425 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1427 constexpr _Iterator&
1439 operator++(int) requires forward_range<_Base>
1446 constexpr _Iterator&
1447 operator--() requires bidirectional_range<_Base>
1454 operator--(int) requires bidirectional_range<_Base>
1461 constexpr _Iterator&
1462 operator+=(difference_type __n) requires random_access_range<_Base>
1468 constexpr _Iterator&
1469 operator-=(difference_type __n) requires random_access_range<_Base>
1475 constexpr decltype(auto)
1476 operator[](difference_type __n) const
1477 requires random_access_range<_Base>
1478 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1480 friend constexpr bool
1481 operator==(const _Iterator& __x, const _Iterator& __y)
1482 requires equality_comparable<_Base_iter>
1483 { return __x._M_current == __y._M_current; }
1485 friend constexpr bool
1486 operator<(const _Iterator& __x, const _Iterator& __y)
1487 requires random_access_range<_Base>
1488 { return __x._M_current < __y._M_current; }
1490 friend constexpr bool
1491 operator>(const _Iterator& __x, const _Iterator& __y)
1492 requires random_access_range<_Base>
1493 { return __y < __x; }
1495 friend constexpr bool
1496 operator<=(const _Iterator& __x, const _Iterator& __y)
1497 requires random_access_range<_Base>
1498 { return !(__y < __x); }
1500 friend constexpr bool
1501 operator>=(const _Iterator& __x, const _Iterator& __y)
1502 requires random_access_range<_Base>
1503 { return !(__x < __y); }
1505 #ifdef __cpp_lib_three_way_comparison
1506 friend constexpr auto
1507 operator<=>(const _Iterator& __x, const _Iterator& __y)
1508 requires random_access_range<_Base>
1509 && three_way_comparable<_Base_iter>
1510 { return __x._M_current <=> __y._M_current; }
1513 friend constexpr _Iterator
1514 operator+(_Iterator __i, difference_type __n)
1515 requires random_access_range<_Base>
1516 { return {__i._M_parent, __i._M_current + __n}; }
1518 friend constexpr _Iterator
1519 operator+(difference_type __n, _Iterator __i)
1520 requires random_access_range<_Base>
1521 { return {__i._M_parent, __i._M_current + __n}; }
1523 friend constexpr _Iterator
1524 operator-(_Iterator __i, difference_type __n)
1525 requires random_access_range<_Base>
1526 { return {__i._M_parent, __i._M_current - __n}; }
1528 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1529 // 3483. transform_view::iterator's difference is overconstrained
1530 friend constexpr difference_type
1531 operator-(const _Iterator& __x, const _Iterator& __y)
1532 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1533 { return __x._M_current - __y._M_current; }
1535 friend constexpr decltype(auto)
1536 iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1538 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1539 return std::move(*__i);
1544 friend constexpr void
1545 iter_swap(const _Iterator& __x, const _Iterator& __y)
1546 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1547 requires indirectly_swappable<_Base_iter>
1548 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1550 friend _Iterator<!_Const>;
1551 template<bool> friend struct _Sentinel;
1554 template<bool _Const>
1558 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1559 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1561 template<bool _Const2>
1563 __distance_from(const _Iterator<_Const2>& __i) const
1564 { return _M_end - __i._M_current; }
1566 template<bool _Const2>
1568 __equal(const _Iterator<_Const2>& __i) const
1569 { return __i._M_current == _M_end; }
1571 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1574 _Sentinel() = default;
1577 _Sentinel(sentinel_t<_Base> __end)
1582 _Sentinel(_Sentinel<!_Const> __i)
1584 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1585 : _M_end(std::move(__i._M_end))
1588 constexpr sentinel_t<_Base>
1592 template<bool _Const2>
1593 requires sentinel_for<sentinel_t<_Base>,
1594 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1595 friend constexpr bool
1596 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1597 { return __y.__equal(__x); }
1599 template<bool _Const2,
1600 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1601 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1602 friend constexpr range_difference_t<_Base2>
1603 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1604 { return -__y.__distance_from(__x); }
1606 template<bool _Const2,
1607 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1608 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1609 friend constexpr range_difference_t<_Base2>
1610 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1611 { return __y.__distance_from(__x); }
1613 friend _Sentinel<!_Const>;
1616 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1617 _Vp _M_base = _Vp();
1620 transform_view() = default;
1623 transform_view(_Vp __base, _Fp __fun)
1624 : _M_fun(std::move(__fun)), _M_base(std::move(__base))
1628 base() const& requires copy_constructible<_Vp>
1629 { return _M_base ; }
1633 { return std::move(_M_base); }
1635 constexpr _Iterator<false>
1637 { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1639 constexpr _Iterator<true>
1641 requires range<const _Vp>
1642 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1643 { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1645 constexpr _Sentinel<false>
1647 { return _Sentinel<false>{ranges::end(_M_base)}; }
1649 constexpr _Iterator<false>
1650 end() requires common_range<_Vp>
1651 { return _Iterator<false>{this, ranges::end(_M_base)}; }
1653 constexpr _Sentinel<true>
1655 requires range<const _Vp>
1656 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1657 { return _Sentinel<true>{ranges::end(_M_base)}; }
1659 constexpr _Iterator<true>
1661 requires common_range<const _Vp>
1662 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1663 { return _Iterator<true>{this, ranges::end(_M_base)}; }
1666 size() requires sized_range<_Vp>
1667 { return ranges::size(_M_base); }
1670 size() const requires sized_range<const _Vp>
1671 { return ranges::size(_M_base); }
1674 template<typename _Range, typename _Fp>
1675 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1681 template<typename _Range, typename _Fp>
1682 concept __can_transform_view
1683 = requires { transform_view{std::declval<_Range>(), std::declval<_Fp>()}; };
1684 } // namespace __detail
1686 struct _Transform : __adaptor::_RangeAdaptor<_Transform>
1688 template<viewable_range _Range, typename _Fp>
1689 requires __detail::__can_transform_view<_Range, _Fp>
1691 operator()(_Range&& __r, _Fp&& __f) const
1693 return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1696 using _RangeAdaptor<_Transform>::operator();
1697 static constexpr int _S_arity = 2;
1700 inline constexpr _Transform transform;
1701 } // namespace views
1704 class take_view : public view_interface<take_view<_Vp>>
1707 template<bool _Const>
1708 using _CI = counted_iterator<
1709 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1711 template<bool _Const>
1715 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1716 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1719 _Sentinel() = default;
1722 _Sentinel(sentinel_t<_Base> __end)
1727 _Sentinel(_Sentinel<!_Const> __s)
1728 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1729 : _M_end(std::move(__s._M_end))
1732 constexpr sentinel_t<_Base>
1736 friend constexpr bool
1737 operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1738 { return __y.count() == 0 || __y.base() == __x._M_end; }
1740 template<bool _OtherConst = !_Const,
1741 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1742 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1743 friend constexpr bool
1744 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1745 { return __y.count() == 0 || __y.base() == __x._M_end; }
1747 friend _Sentinel<!_Const>;
1750 range_difference_t<_Vp> _M_count = 0;
1751 _Vp _M_base = _Vp();
1754 take_view() = default;
1757 take_view(_Vp base, range_difference_t<_Vp> __count)
1758 : _M_count(std::move(__count)), _M_base(std::move(base))
1762 base() const& requires copy_constructible<_Vp>
1767 { return std::move(_M_base); }
1770 begin() requires (!__detail::__simple_view<_Vp>)
1772 if constexpr (sized_range<_Vp>)
1774 if constexpr (random_access_range<_Vp>)
1775 return ranges::begin(_M_base);
1779 return counted_iterator{ranges::begin(_M_base), __sz};
1783 return counted_iterator{ranges::begin(_M_base), _M_count};
1787 begin() const requires range<const _Vp>
1789 if constexpr (sized_range<const _Vp>)
1791 if constexpr (random_access_range<const _Vp>)
1792 return ranges::begin(_M_base);
1796 return counted_iterator{ranges::begin(_M_base), __sz};
1800 return counted_iterator{ranges::begin(_M_base), _M_count};
1804 end() requires (!__detail::__simple_view<_Vp>)
1806 if constexpr (sized_range<_Vp>)
1808 if constexpr (random_access_range<_Vp>)
1809 return ranges::begin(_M_base) + size();
1811 return default_sentinel;
1814 return _Sentinel<false>{ranges::end(_M_base)};
1818 end() const requires range<const _Vp>
1820 if constexpr (sized_range<const _Vp>)
1822 if constexpr (random_access_range<const _Vp>)
1823 return ranges::begin(_M_base) + size();
1825 return default_sentinel;
1828 return _Sentinel<true>{ranges::end(_M_base)};
1832 size() requires sized_range<_Vp>
1834 auto __n = ranges::size(_M_base);
1835 return std::min(__n, static_cast<decltype(__n)>(_M_count));
1839 size() const requires sized_range<const _Vp>
1841 auto __n = ranges::size(_M_base);
1842 return std::min(__n, static_cast<decltype(__n)>(_M_count));
1846 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1847 // 3447. Deduction guides for take_view and drop_view have different
1849 template<typename _Range>
1850 take_view(_Range&&, range_difference_t<_Range>)
1851 -> take_view<views::all_t<_Range>>;
1853 template<typename _Tp>
1854 inline constexpr bool enable_borrowed_range<take_view<_Tp>>
1855 = enable_borrowed_range<_Tp>;
1861 template<typename _Range, typename _Tp>
1862 concept __can_take_view
1863 = requires { take_view{std::declval<_Range>(), std::declval<_Tp>()}; };
1864 } // namespace __detail
1866 struct _Take : __adaptor::_RangeAdaptor<_Take>
1868 template<viewable_range _Range, typename _Tp>
1869 requires __detail::__can_take_view<_Range, _Tp>
1871 operator()(_Range&& __r, _Tp&& __n) const
1873 return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
1876 using _RangeAdaptor<_Take>::operator();
1877 static constexpr int _S_arity = 2;
1880 inline constexpr _Take take;
1881 } // namespace views
1883 template<view _Vp, typename _Pred>
1884 requires input_range<_Vp> && is_object_v<_Pred>
1885 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
1886 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
1888 template<bool _Const>
1892 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1894 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1895 const _Pred* _M_pred = nullptr;
1898 _Sentinel() = default;
1901 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
1902 : _M_end(__end), _M_pred(__pred)
1906 _Sentinel(_Sentinel<!_Const> __s)
1907 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1908 : _M_end(__s._M_end), _M_pred(__s._M_pred)
1911 constexpr sentinel_t<_Base>
1912 base() const { return _M_end; }
1914 friend constexpr bool
1915 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
1916 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1918 template<bool _OtherConst = !_Const,
1919 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1920 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1921 friend constexpr bool
1922 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
1923 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1925 friend _Sentinel<!_Const>;
1928 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1929 _Vp _M_base = _Vp();
1932 take_while_view() = default;
1935 take_while_view(_Vp base, _Pred __pred)
1936 : _M_pred(std::move(__pred)), _M_base(std::move(base))
1940 base() const& requires copy_constructible<_Vp>
1945 { return std::move(_M_base); }
1947 constexpr const _Pred&
1949 { return *_M_pred; }
1952 begin() requires (!__detail::__simple_view<_Vp>)
1953 { return ranges::begin(_M_base); }
1956 begin() const requires range<const _Vp>
1957 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1958 { return ranges::begin(_M_base); }
1961 end() requires (!__detail::__simple_view<_Vp>)
1962 { return _Sentinel<false>(ranges::end(_M_base),
1963 std::__addressof(*_M_pred)); }
1966 end() const requires range<const _Vp>
1967 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1968 { return _Sentinel<true>(ranges::end(_M_base),
1969 std::__addressof(*_M_pred)); }
1972 template<typename _Range, typename _Pred>
1973 take_while_view(_Range&&, _Pred)
1974 -> take_while_view<views::all_t<_Range>, _Pred>;
1980 template<typename _Range, typename _Pred>
1981 concept __can_take_while_view
1982 = requires { take_while_view{std::declval<_Range>(), std::declval<_Pred>()}; };
1983 } // namespace __detail
1985 struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
1987 template<viewable_range _Range, typename _Pred>
1988 requires __detail::__can_take_while_view<_Range, _Pred>
1990 operator()(_Range&& __r, _Pred&& __p) const
1992 return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1995 using _RangeAdaptor<_TakeWhile>::operator();
1996 static constexpr int _S_arity = 2;
1999 inline constexpr _TakeWhile take_while;
2000 } // namespace views
2003 class drop_view : public view_interface<drop_view<_Vp>>
2006 range_difference_t<_Vp> _M_count = 0;
2007 _Vp _M_base = _Vp();
2009 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2010 // both random_access_range and sized_range. Otherwise, cache its result.
2011 static constexpr bool _S_needs_cached_begin
2012 = !(random_access_range<const _Vp> && sized_range<const _Vp>);
2013 [[no_unique_address]]
2014 __detail::__maybe_present_t<_S_needs_cached_begin,
2015 __detail::_CachedPosition<_Vp>>
2019 drop_view() = default;
2022 drop_view(_Vp __base, range_difference_t<_Vp> __count)
2023 : _M_count(__count), _M_base(std::move(__base))
2024 { __glibcxx_assert(__count >= 0); }
2027 base() const& requires copy_constructible<_Vp>
2032 { return std::move(_M_base); }
2034 // This overload is disabled for simple views with constant-time begin().
2037 requires (!(__detail::__simple_view<_Vp>
2038 && random_access_range<const _Vp>
2039 && sized_range<const _Vp>))
2041 if constexpr (_S_needs_cached_begin)
2042 if (_M_cached_begin._M_has_value())
2043 return _M_cached_begin._M_get(_M_base);
2045 auto __it = ranges::next(ranges::begin(_M_base),
2046 _M_count, ranges::end(_M_base));
2047 if constexpr (_S_needs_cached_begin)
2048 _M_cached_begin._M_set(_M_base, __it);
2052 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2053 // 3482. drop_view's const begin should additionally require sized_range
2056 requires random_access_range<const _Vp> && sized_range<const _Vp>
2058 return ranges::next(ranges::begin(_M_base), _M_count,
2059 ranges::end(_M_base));
2063 end() requires (!__detail::__simple_view<_Vp>)
2064 { return ranges::end(_M_base); }
2067 end() const requires range<const _Vp>
2068 { return ranges::end(_M_base); }
2071 size() requires sized_range<_Vp>
2073 const auto __s = ranges::size(_M_base);
2074 const auto __c = static_cast<decltype(__s)>(_M_count);
2075 return __s < __c ? 0 : __s - __c;
2079 size() const requires sized_range<const _Vp>
2081 const auto __s = ranges::size(_M_base);
2082 const auto __c = static_cast<decltype(__s)>(_M_count);
2083 return __s < __c ? 0 : __s - __c;
2087 template<typename _Range>
2088 drop_view(_Range&&, range_difference_t<_Range>)
2089 -> drop_view<views::all_t<_Range>>;
2091 template<typename _Tp>
2092 inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2093 = enable_borrowed_range<_Tp>;
2099 template<typename _Range, typename _Tp>
2100 concept __can_drop_view
2101 = requires { drop_view{std::declval<_Range>(), std::declval<_Tp>()}; };
2102 } // namespace __detail
2104 struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2106 template<viewable_range _Range, typename _Tp>
2107 requires __detail::__can_drop_view<_Range, _Tp>
2109 operator()(_Range&& __r, _Tp&& __n) const
2111 return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2114 using _RangeAdaptor<_Drop>::operator();
2115 static constexpr int _S_arity = 2;
2118 inline constexpr _Drop drop;
2119 } // namespace views
2121 template<view _Vp, typename _Pred>
2122 requires input_range<_Vp> && is_object_v<_Pred>
2123 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2124 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2127 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2128 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2129 _Vp _M_base = _Vp();
2132 drop_while_view() = default;
2135 drop_while_view(_Vp __base, _Pred __pred)
2136 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
2140 base() const& requires copy_constructible<_Vp>
2145 { return std::move(_M_base); }
2147 constexpr const _Pred&
2149 { return *_M_pred; }
2154 if (_M_cached_begin._M_has_value())
2155 return _M_cached_begin._M_get(_M_base);
2157 auto __it = __detail::find_if_not(ranges::begin(_M_base),
2158 ranges::end(_M_base),
2159 std::cref(*_M_pred));
2160 _M_cached_begin._M_set(_M_base, __it);
2166 { return ranges::end(_M_base); }
2169 template<typename _Range, typename _Pred>
2170 drop_while_view(_Range&&, _Pred)
2171 -> drop_while_view<views::all_t<_Range>, _Pred>;
2173 template<typename _Tp, typename _Pred>
2174 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2175 = enable_borrowed_range<_Tp>;
2181 template<typename _Range, typename _Pred>
2182 concept __can_drop_while_view
2183 = requires { drop_while_view{std::declval<_Range>(), std::declval<_Pred>()}; };
2184 } // namespace __detail
2186 struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2188 template<viewable_range _Range, typename _Pred>
2189 requires __detail::__can_drop_while_view<_Range, _Pred>
2191 operator()(_Range&& __r, _Pred&& __p) const
2193 return drop_while_view{std::forward<_Range>(__r),
2194 std::forward<_Pred>(__p)};
2197 using _RangeAdaptor<_DropWhile>::operator();
2198 static constexpr int _S_arity = 2;
2201 inline constexpr _DropWhile drop_while;
2202 } // namespace views
2204 template<input_range _Vp>
2205 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2206 && (is_reference_v<range_reference_t<_Vp>>
2207 || view<range_value_t<_Vp>>)
2208 class join_view : public view_interface<join_view<_Vp>>
2211 using _InnerRange = range_reference_t<_Vp>;
2213 template<bool _Const>
2216 template<bool _Const>
2220 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2221 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2223 static constexpr bool _S_ref_is_glvalue
2224 = is_reference_v<range_reference_t<_Base>>;
2229 auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2231 if constexpr (_S_ref_is_glvalue)
2234 return (_M_parent->_M_inner = views::all(std::move(__x)));
2237 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2239 auto& __inner = __update_inner(*_M_outer);
2240 _M_inner = ranges::begin(__inner);
2241 if (_M_inner != ranges::end(__inner))
2245 if constexpr (_S_ref_is_glvalue)
2246 _M_inner = _Inner_iter();
2249 static constexpr auto
2252 if constexpr (_S_ref_is_glvalue
2253 && bidirectional_range<_Base>
2254 && bidirectional_range<range_reference_t<_Base>>)
2255 return bidirectional_iterator_tag{};
2256 else if constexpr (_S_ref_is_glvalue
2257 && forward_range<_Base>
2258 && forward_range<range_reference_t<_Base>>)
2259 return forward_iterator_tag{};
2261 return input_iterator_tag{};
2264 static constexpr auto
2268 = typename iterator_traits<_Outer_iter>::iterator_category;
2270 = typename iterator_traits<_Inner_iter>::iterator_category;
2271 if constexpr (_S_ref_is_glvalue
2272 && derived_from<_OuterCat, bidirectional_iterator_tag>
2273 && derived_from<_InnerCat, bidirectional_iterator_tag>)
2274 return bidirectional_iterator_tag{};
2275 else if constexpr (_S_ref_is_glvalue
2276 && derived_from<_OuterCat, forward_iterator_tag>
2277 && derived_from<_InnerCat, forward_iterator_tag>)
2278 return forward_iterator_tag{};
2279 else if constexpr (derived_from<_OuterCat, input_iterator_tag>
2280 && derived_from<_InnerCat, input_iterator_tag>)
2281 return input_iterator_tag{};
2283 return output_iterator_tag{};
2286 using _Outer_iter = iterator_t<_Base>;
2287 using _Inner_iter = iterator_t<range_reference_t<_Base>>;
2289 _Outer_iter _M_outer = _Outer_iter();
2290 _Inner_iter _M_inner = _Inner_iter();
2291 _Parent* _M_parent = nullptr;
2294 using iterator_concept = decltype(_S_iter_concept());
2295 using iterator_category = decltype(_S_iter_cat());
2296 using value_type = range_value_t<range_reference_t<_Base>>;
2297 using difference_type
2298 = common_type_t<range_difference_t<_Base>,
2299 range_difference_t<range_reference_t<_Base>>>;
2301 _Iterator() = default;
2304 _Iterator(_Parent* __parent, _Outer_iter __outer)
2305 : _M_outer(std::move(__outer)),
2310 _Iterator(_Iterator<!_Const> __i)
2312 && convertible_to<iterator_t<_Vp>, _Outer_iter>
2313 && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2314 : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2315 _M_parent(__i._M_parent)
2318 constexpr decltype(auto)
2320 { return *_M_inner; }
2322 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2323 // 3500. join_view::iterator::operator->() is bogus
2324 constexpr _Inner_iter
2326 requires __detail::__has_arrow<_Inner_iter>
2327 && copyable<_Inner_iter>
2328 { return _M_inner; }
2330 constexpr _Iterator&
2333 auto&& __inner_range = [this] () -> decltype(auto) {
2334 if constexpr (_S_ref_is_glvalue)
2337 return _M_parent->_M_inner;
2339 if (++_M_inner == ranges::end(__inner_range))
2353 requires _S_ref_is_glvalue && forward_range<_Base>
2354 && forward_range<range_reference_t<_Base>>
2361 constexpr _Iterator&
2363 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2364 && bidirectional_range<range_reference_t<_Base>>
2365 && common_range<range_reference_t<_Base>>
2367 if (_M_outer == ranges::end(_M_parent->_M_base))
2368 _M_inner = ranges::end(*--_M_outer);
2369 while (_M_inner == ranges::begin(*_M_outer))
2370 _M_inner = ranges::end(*--_M_outer);
2377 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2378 && bidirectional_range<range_reference_t<_Base>>
2379 && common_range<range_reference_t<_Base>>
2386 friend constexpr bool
2387 operator==(const _Iterator& __x, const _Iterator& __y)
2388 requires _S_ref_is_glvalue
2389 && equality_comparable<_Outer_iter>
2390 && equality_comparable<_Inner_iter>
2392 return (__x._M_outer == __y._M_outer
2393 && __x._M_inner == __y._M_inner);
2396 friend constexpr decltype(auto)
2397 iter_move(const _Iterator& __i)
2398 noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2399 { return ranges::iter_move(__i._M_inner); }
2401 friend constexpr void
2402 iter_swap(const _Iterator& __x, const _Iterator& __y)
2403 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2404 { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2406 friend _Iterator<!_Const>;
2407 template<bool> friend struct _Sentinel;
2410 template<bool _Const>
2414 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2415 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2417 template<bool _Const2>
2419 __equal(const _Iterator<_Const2>& __i) const
2420 { return __i._M_outer == _M_end; }
2422 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2425 _Sentinel() = default;
2428 _Sentinel(_Parent* __parent)
2429 : _M_end(ranges::end(__parent->_M_base))
2433 _Sentinel(_Sentinel<!_Const> __s)
2434 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2435 : _M_end(std::move(__s._M_end))
2438 template<bool _Const2>
2439 requires sentinel_for<sentinel_t<_Base>,
2440 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2441 friend constexpr bool
2442 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2443 { return __y.__equal(__x); }
2445 friend _Sentinel<!_Const>;
2448 // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2449 [[no_unique_address]]
2450 __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
2451 views::all_t<_InnerRange>> _M_inner;
2452 _Vp _M_base = _Vp();
2455 join_view() = default;
2458 join_view(_Vp __base)
2459 : _M_base(std::move(__base))
2463 base() const& requires copy_constructible<_Vp>
2468 { return std::move(_M_base); }
2473 constexpr bool __use_const
2474 = (__detail::__simple_view<_Vp>
2475 && is_reference_v<range_reference_t<_Vp>>);
2476 return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2481 requires input_range<const _Vp>
2482 && is_reference_v<range_reference_t<const _Vp>>
2484 return _Iterator<true>{this, ranges::begin(_M_base)};
2490 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2491 && forward_range<_InnerRange>
2492 && common_range<_Vp> && common_range<_InnerRange>)
2493 return _Iterator<__detail::__simple_view<_Vp>>{this,
2494 ranges::end(_M_base)};
2496 return _Sentinel<__detail::__simple_view<_Vp>>{this};
2501 requires input_range<const _Vp>
2502 && is_reference_v<range_reference_t<const _Vp>>
2504 if constexpr (forward_range<const _Vp>
2505 && is_reference_v<range_reference_t<const _Vp>>
2506 && forward_range<range_reference_t<const _Vp>>
2507 && common_range<const _Vp>
2508 && common_range<range_reference_t<const _Vp>>)
2509 return _Iterator<true>{this, ranges::end(_M_base)};
2511 return _Sentinel<true>{this};
2515 template<typename _Range>
2516 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2522 template<typename _Range>
2523 concept __can_join_view
2524 = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
2525 } // namespace __detail
2527 struct _Join : __adaptor::_RangeAdaptorClosure
2529 template<viewable_range _Range>
2530 requires __detail::__can_join_view<_Range>
2532 operator()(_Range&& __r) const
2534 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2535 // 3474. Nesting join_views is broken because of CTAD
2536 return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
2540 inline constexpr _Join join;
2541 } // namespace views
2546 struct __require_constant;
2548 template<typename _Range>
2549 concept __tiny_range = sized_range<_Range>
2551 { typename __require_constant<remove_reference_t<_Range>::size()>; }
2552 && (remove_reference_t<_Range>::size() <= 1);
2555 template<input_range _Vp, forward_range _Pattern>
2556 requires view<_Vp> && view<_Pattern>
2557 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2559 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2560 class split_view : public view_interface<split_view<_Vp, _Pattern>>
2563 template<bool _Const>
2566 template<bool _Const>
2570 using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2571 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2575 { return __current() == ranges::end(_M_parent->_M_base); }
2577 // [range.split.outer] p1
2578 // Many of the following specifications refer to the notional member
2579 // current of outer-iterator. current is equivalent to current_ if
2580 // V models forward_range, and parent_->current_ otherwise.
2582 __current() noexcept
2584 if constexpr (forward_range<_Vp>)
2587 return _M_parent->_M_current;
2591 __current() const noexcept
2593 if constexpr (forward_range<_Vp>)
2596 return _M_parent->_M_current;
2599 _Parent* _M_parent = nullptr;
2601 // XXX: _M_current is present only if "V models forward_range"
2602 [[no_unique_address]]
2603 __detail::__maybe_present_t<forward_range<_Vp>,
2604 iterator_t<_Base>> _M_current;
2607 using iterator_concept = conditional_t<forward_range<_Base>,
2608 forward_iterator_tag,
2609 input_iterator_tag>;
2610 using iterator_category = input_iterator_tag;
2611 using difference_type = range_difference_t<_Base>;
2613 struct value_type : view_interface<value_type>
2616 _OuterIter _M_i = _OuterIter();
2619 value_type() = default;
2622 value_type(_OuterIter __i)
2623 : _M_i(std::move(__i))
2626 constexpr _InnerIter<_Const>
2628 requires copyable<_OuterIter>
2629 { return _InnerIter<_Const>{_M_i}; }
2631 constexpr _InnerIter<_Const>
2633 requires (!copyable<_OuterIter>)
2634 { return _InnerIter<_Const>{std::move(_M_i)}; }
2636 constexpr default_sentinel_t
2638 { return default_sentinel; }
2641 _OuterIter() = default;
2644 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2645 : _M_parent(__parent)
2649 _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2650 requires forward_range<_Base>
2651 : _M_parent(__parent),
2652 _M_current(std::move(__current))
2656 _OuterIter(_OuterIter<!_Const> __i)
2658 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2659 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2662 constexpr value_type
2664 { return value_type{*this}; }
2666 constexpr _OuterIter&
2669 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2670 // 3505. split_view::outer-iterator::operator++ misspecified
2671 const auto __end = ranges::end(_M_parent->_M_base);
2672 if (__current() == __end)
2674 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2675 if (__pbegin == __pend)
2677 else if constexpr (__detail::__tiny_range<_Pattern>)
2679 __current() = __detail::find(std::move(__current()), __end,
2681 if (__current() != __end)
2688 = __detail::mismatch(__current(), __end, __pbegin, __pend);
2694 } while (++__current() != __end);
2698 constexpr decltype(auto)
2701 if constexpr (forward_range<_Base>)
2711 friend constexpr bool
2712 operator==(const _OuterIter& __x, const _OuterIter& __y)
2713 requires forward_range<_Base>
2714 { return __x._M_current == __y._M_current; }
2716 friend constexpr bool
2717 operator==(const _OuterIter& __x, default_sentinel_t)
2718 { return __x.__at_end(); };
2720 friend _OuterIter<!_Const>;
2721 friend _InnerIter<_Const>;
2724 template<bool _Const>
2728 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2733 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2734 auto __end = ranges::end(_M_i._M_parent->_M_base);
2735 if constexpr (__detail::__tiny_range<_Pattern>)
2737 const auto& __cur = _M_i_current();
2740 if (__pcur == __pend)
2741 return _M_incremented;
2742 return *__cur == *__pcur;
2746 auto __cur = _M_i_current();
2749 if (__pcur == __pend)
2750 return _M_incremented;
2753 if (*__cur != *__pcur)
2755 if (++__pcur == __pend)
2757 } while (++__cur != __end);
2762 static constexpr auto
2766 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2767 if constexpr (derived_from<_Cat, forward_iterator_tag>)
2768 return forward_iterator_tag{};
2774 _M_i_current() noexcept
2775 { return _M_i.__current(); }
2778 _M_i_current() const noexcept
2779 { return _M_i.__current(); }
2781 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2782 bool _M_incremented = false;
2785 using iterator_concept
2786 = typename _OuterIter<_Const>::iterator_concept;
2787 using iterator_category = decltype(_S_iter_cat());
2788 using value_type = range_value_t<_Base>;
2789 using difference_type = range_difference_t<_Base>;
2791 _InnerIter() = default;
2794 _InnerIter(_OuterIter<_Const> __i)
2795 : _M_i(std::move(__i))
2798 constexpr decltype(auto)
2800 { return *_M_i_current(); }
2802 constexpr _InnerIter&
2805 _M_incremented = true;
2806 if constexpr (!forward_range<_Base>)
2807 if constexpr (_Pattern::size() == 0)
2813 constexpr decltype(auto)
2816 if constexpr (forward_range<_Vp>)
2826 friend constexpr bool
2827 operator==(const _InnerIter& __x, const _InnerIter& __y)
2828 requires forward_range<_Base>
2829 { return __x._M_i == __y._M_i; }
2831 friend constexpr bool
2832 operator==(const _InnerIter& __x, default_sentinel_t)
2833 { return __x.__at_end(); }
2835 friend constexpr decltype(auto)
2836 iter_move(const _InnerIter& __i)
2837 noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
2838 { return ranges::iter_move(__i._M_i_current()); }
2840 friend constexpr void
2841 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2842 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
2843 __y._M_i_current())))
2844 requires indirectly_swappable<iterator_t<_Base>>
2845 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
2848 _Pattern _M_pattern = _Pattern();
2849 // XXX: _M_current is "present only if !forward_range<V>"
2850 [[no_unique_address]]
2851 __detail::__maybe_present_t<!forward_range<_Vp>,
2852 iterator_t<_Vp>> _M_current;
2853 _Vp _M_base = _Vp();
2857 split_view() = default;
2860 split_view(_Vp __base, _Pattern __pattern)
2861 : _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
2864 template<input_range _Range>
2865 requires constructible_from<_Vp, views::all_t<_Range>>
2866 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2868 split_view(_Range&& __r, range_value_t<_Range> __e)
2869 : _M_pattern(std::move(__e)),
2870 _M_base(views::all(std::forward<_Range>(__r)))
2874 base() const& requires copy_constructible<_Vp>
2879 { return std::move(_M_base); }
2884 if constexpr (forward_range<_Vp>)
2885 return _OuterIter<__detail::__simple_view<_Vp>>{
2886 this, ranges::begin(_M_base)};
2889 _M_current = ranges::begin(_M_base);
2890 return _OuterIter<false>{this};
2895 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
2897 return _OuterIter<true>{this, ranges::begin(_M_base)};
2901 end() requires forward_range<_Vp> && common_range<_Vp>
2903 return _OuterIter<__detail::__simple_view<_Vp>>{
2904 this, ranges::end(_M_base)};
2910 if constexpr (forward_range<_Vp>
2911 && forward_range<const _Vp>
2912 && common_range<const _Vp>)
2913 return _OuterIter<true>{this, ranges::end(_M_base)};
2915 return default_sentinel;
2919 template<typename _Range, typename _Pattern>
2920 split_view(_Range&&, _Pattern&&)
2921 -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
2923 template<input_range _Range>
2924 split_view(_Range&&, range_value_t<_Range>)
2925 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
2931 template<typename _Range, typename _Pattern>
2932 concept __can_split_view
2933 = requires { split_view{std::declval<_Range>(), std::declval<_Pattern>()}; };
2934 } // namespace __detail
2936 struct _Split : __adaptor::_RangeAdaptor<_Split>
2938 template<viewable_range _Range, typename _Pattern>
2939 requires __detail::__can_split_view<_Range, _Pattern>
2941 operator()(_Range&& __r, _Pattern&& __f) const
2943 return split_view{std::forward<_Range>(__r), std::forward<_Pattern>(__f)};
2946 using _RangeAdaptor<_Split>::operator();
2947 static constexpr int _S_arity = 2;
2950 inline constexpr _Split split;
2951 } // namespace views
2957 template<input_or_output_iterator _Iter>
2959 operator()(_Iter __i, iter_difference_t<_Iter> __n) const
2961 if constexpr (random_access_iterator<_Iter>)
2962 return subrange{__i, __i + __n};
2964 return subrange{counted_iterator{std::move(__i), __n},
2969 inline constexpr _Counted counted{};
2970 } // namespace views
2973 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
2974 class common_view : public view_interface<common_view<_Vp>>
2977 _Vp _M_base = _Vp();
2980 common_view() = default;
2983 common_view(_Vp __r)
2984 : _M_base(std::move(__r))
2987 /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
2988 template<viewable_range _Range>
2989 requires (!common_range<_Range>)
2990 && constructible_from<_Vp, views::all_t<_Range>>
2992 common_view(_Range&& __r)
2993 : _M_base(views::all(std::forward<_Range>(__r)))
2998 base() const& requires copy_constructible<_Vp>
3003 { return std::move(_M_base); }
3008 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3009 return ranges::begin(_M_base);
3011 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3012 (ranges::begin(_M_base));
3016 begin() const requires range<const _Vp>
3018 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3019 return ranges::begin(_M_base);
3021 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3022 (ranges::begin(_M_base));
3028 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3029 return ranges::begin(_M_base) + ranges::size(_M_base);
3031 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3032 (ranges::end(_M_base));
3036 end() const requires range<const _Vp>
3038 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3039 return ranges::begin(_M_base) + ranges::size(_M_base);
3041 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3042 (ranges::end(_M_base));
3046 size() requires sized_range<_Vp>
3047 { return ranges::size(_M_base); }
3050 size() const requires sized_range<const _Vp>
3051 { return ranges::size(_M_base); }
3054 template<typename _Range>
3055 common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3057 template<typename _Tp>
3058 inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3059 = enable_borrowed_range<_Tp>;
3065 template<typename _Range>
3066 concept __already_common = common_range<_Range>
3067 && requires { views::all(std::declval<_Range>()); };
3069 template<typename _Range>
3070 concept __can_common_view
3071 = requires { common_view{std::declval<_Range>()}; };
3072 } // namespace __detail
3074 struct _Common : __adaptor::_RangeAdaptorClosure
3076 template<viewable_range _Range>
3077 requires __detail::__already_common<_Range>
3078 || __detail::__can_common_view<_Range>
3080 operator()(_Range&& __r) const
3082 if constexpr (__detail::__already_common<_Range>)
3083 return views::all(std::forward<_Range>(__r));
3085 return common_view{std::forward<_Range>(__r)};
3089 inline constexpr _Common common;
3090 } // namespace views
3093 requires bidirectional_range<_Vp>
3094 class reverse_view : public view_interface<reverse_view<_Vp>>
3097 static constexpr bool _S_needs_cached_begin
3098 = !common_range<_Vp> && !random_access_range<_Vp>;
3100 [[no_unique_address]]
3101 __detail::__maybe_present_t<_S_needs_cached_begin,
3102 __detail::_CachedPosition<_Vp>>
3104 _Vp _M_base = _Vp();
3107 reverse_view() = default;
3110 reverse_view(_Vp __r)
3111 : _M_base(std::move(__r))
3115 base() const& requires copy_constructible<_Vp>
3120 { return std::move(_M_base); }
3122 constexpr reverse_iterator<iterator_t<_Vp>>
3125 if constexpr (_S_needs_cached_begin)
3126 if (_M_cached_begin._M_has_value())
3127 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3129 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3130 if constexpr (_S_needs_cached_begin)
3131 _M_cached_begin._M_set(_M_base, __it);
3132 return std::make_reverse_iterator(std::move(__it));
3136 begin() requires common_range<_Vp>
3137 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3140 begin() const requires common_range<const _Vp>
3141 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3143 constexpr reverse_iterator<iterator_t<_Vp>>
3145 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3148 end() const requires common_range<const _Vp>
3149 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3152 size() requires sized_range<_Vp>
3153 { return ranges::size(_M_base); }
3156 size() const requires sized_range<const _Vp>
3157 { return ranges::size(_M_base); }
3160 template<typename _Range>
3161 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3163 template<typename _Tp>
3164 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3165 = enable_borrowed_range<_Tp>;
3172 inline constexpr bool __is_reversible_subrange = false;
3174 template<typename _Iter, subrange_kind _Kind>
3175 inline constexpr bool
3176 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3177 reverse_iterator<_Iter>,
3181 inline constexpr bool __is_reverse_view = false;
3183 template<typename _Vp>
3184 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3186 template<typename _Range>
3187 concept __can_reverse_view
3188 = requires { reverse_view{std::declval<_Range>()}; };
3189 } // namespace __detail
3191 struct _Reverse : __adaptor::_RangeAdaptorClosure
3193 template<viewable_range _Range>
3194 requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3195 || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3196 || __detail::__can_reverse_view<_Range>
3198 operator()(_Range&& __r) const
3200 using _Tp = remove_cvref_t<_Range>;
3201 if constexpr (__detail::__is_reverse_view<_Tp>)
3202 return std::forward<_Range>(__r).base();
3203 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3205 using _Iter = decltype(ranges::begin(__r).base());
3206 if constexpr (sized_range<_Tp>)
3207 return subrange<_Iter, _Iter, subrange_kind::sized>
3208 {__r.end().base(), __r.begin().base(), __r.size()};
3210 return subrange<_Iter, _Iter, subrange_kind::unsized>
3211 {__r.end().base(), __r.begin().base()};
3214 return reverse_view{std::forward<_Range>(__r)};
3218 inline constexpr _Reverse reverse;
3219 } // namespace views
3223 template<typename _Tp, size_t _Nm>
3224 concept __has_tuple_element = requires(_Tp __t)
3226 typename tuple_size<_Tp>::type;
3227 requires _Nm < tuple_size_v<_Tp>;
3228 typename tuple_element_t<_Nm, _Tp>;
3229 { std::get<_Nm>(__t) }
3230 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3233 template<typename _Tp, size_t _Nm>
3234 concept __returnable_element
3235 = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
3238 template<input_range _Vp, size_t _Nm>
3240 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3241 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3243 && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
3244 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3247 elements_view() = default;
3250 elements_view(_Vp base)
3251 : _M_base(std::move(base))
3255 base() const& requires copy_constructible<_Vp>
3260 { return std::move(_M_base); }
3263 begin() requires (!__detail::__simple_view<_Vp>)
3264 { return _Iterator<false>(ranges::begin(_M_base)); }
3267 begin() const requires range<const _Vp>
3268 { return _Iterator<true>(ranges::begin(_M_base)); }
3271 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3272 { return _Sentinel<false>{ranges::end(_M_base)}; }
3275 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3276 { return _Iterator<false>{ranges::end(_M_base)}; }
3279 end() const requires range<const _Vp>
3280 { return _Sentinel<true>{ranges::end(_M_base)}; }
3283 end() const requires common_range<const _Vp>
3284 { return _Iterator<true>{ranges::end(_M_base)}; }
3287 size() requires sized_range<_Vp>
3288 { return ranges::size(_M_base); }
3291 size() const requires sized_range<const _Vp>
3292 { return ranges::size(_M_base); }
3295 template<bool _Const>
3298 template<bool _Const>
3302 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3304 iterator_t<_Base> _M_current = iterator_t<_Base>();
3306 static constexpr decltype(auto)
3307 _S_get_element(const iterator_t<_Base>& __i)
3309 if constexpr (is_reference_v<range_reference_t<_Base>>)
3310 return std::get<_Nm>(*__i);
3313 using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
3314 return static_cast<_Et>(std::get<_Nm>(*__i));
3318 friend _Iterator<!_Const>;
3321 using iterator_category
3322 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3324 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3325 using difference_type = range_difference_t<_Base>;
3327 _Iterator() = default;
3330 _Iterator(iterator_t<_Base> current)
3331 : _M_current(std::move(current))
3335 _Iterator(_Iterator<!_Const> i)
3336 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3337 : _M_current(std::move(i._M_current))
3340 constexpr iterator_t<_Base>
3342 requires copyable<iterator_t<_Base>>
3343 { return _M_current; }
3345 constexpr iterator_t<_Base>
3347 { return std::move(_M_current); }
3349 constexpr decltype(auto)
3351 { return _S_get_element(_M_current); }
3353 constexpr _Iterator&
3365 operator++(int) requires forward_range<_Base>
3372 constexpr _Iterator&
3373 operator--() requires bidirectional_range<_Base>
3380 operator--(int) requires bidirectional_range<_Base>
3387 constexpr _Iterator&
3388 operator+=(difference_type __n)
3389 requires random_access_range<_Base>
3395 constexpr _Iterator&
3396 operator-=(difference_type __n)
3397 requires random_access_range<_Base>
3403 constexpr decltype(auto)
3404 operator[](difference_type __n) const
3405 requires random_access_range<_Base>
3406 { return _S_get_element(_M_current + __n); }
3408 friend constexpr bool
3409 operator==(const _Iterator& __x, const _Iterator& __y)
3410 requires equality_comparable<iterator_t<_Base>>
3411 { return __x._M_current == __y._M_current; }
3413 friend constexpr bool
3414 operator<(const _Iterator& __x, const _Iterator& __y)
3415 requires random_access_range<_Base>
3416 { return __x._M_current < __y._M_current; }
3418 friend constexpr bool
3419 operator>(const _Iterator& __x, const _Iterator& __y)
3420 requires random_access_range<_Base>
3421 { return __y._M_current < __x._M_current; }
3423 friend constexpr bool
3424 operator<=(const _Iterator& __x, const _Iterator& __y)
3425 requires random_access_range<_Base>
3426 { return !(__y._M_current > __x._M_current); }
3428 friend constexpr bool
3429 operator>=(const _Iterator& __x, const _Iterator& __y)
3430 requires random_access_range<_Base>
3431 { return !(__x._M_current > __y._M_current); }
3433 #ifdef __cpp_lib_three_way_comparison
3434 friend constexpr auto
3435 operator<=>(const _Iterator& __x, const _Iterator& __y)
3436 requires random_access_range<_Base>
3437 && three_way_comparable<iterator_t<_Base>>
3438 { return __x._M_current <=> __y._M_current; }
3441 friend constexpr _Iterator
3442 operator+(const _Iterator& __x, difference_type __y)
3443 requires random_access_range<_Base>
3444 { return _Iterator{__x} += __y; }
3446 friend constexpr _Iterator
3447 operator+(difference_type __x, const _Iterator& __y)
3448 requires random_access_range<_Base>
3449 { return __y + __x; }
3451 friend constexpr _Iterator
3452 operator-(const _Iterator& __x, difference_type __y)
3453 requires random_access_range<_Base>
3454 { return _Iterator{__x} -= __y; }
3456 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3457 // 3483. transform_view::iterator's difference is overconstrained
3458 friend constexpr difference_type
3459 operator-(const _Iterator& __x, const _Iterator& __y)
3460 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3461 { return __x._M_current - __y._M_current; }
3463 friend _Sentinel<_Const>;
3466 template<bool _Const>
3471 _M_equal(const _Iterator<_Const>& __x) const
3472 { return __x._M_current == _M_end; }
3474 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3475 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3478 _Sentinel() = default;
3481 _Sentinel(sentinel_t<_Base> __end)
3482 : _M_end(std::move(__end))
3486 _Sentinel(_Sentinel<!_Const> __other)
3488 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3489 : _M_end(std::move(__other._M_end))
3492 constexpr sentinel_t<_Base>
3496 template<bool _Const2>
3497 requires sentinel_for<sentinel_t<_Base>,
3498 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3499 friend constexpr bool
3500 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3501 { return __y._M_equal(__x); }
3503 template<bool _Const2,
3504 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3505 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3506 friend constexpr range_difference_t<_Base2>
3507 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3508 { return __x._M_current - __y._M_end; }
3510 template<bool _Const2,
3511 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3512 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3513 friend constexpr range_difference_t<_Base>
3514 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3515 { return __x._M_end - __y._M_current; }
3517 friend _Sentinel<!_Const>;
3520 _Vp _M_base = _Vp();
3523 template<typename _Tp, size_t _Nm>
3524 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3525 = enable_borrowed_range<_Tp>;
3527 template<typename _Range>
3528 using keys_view = elements_view<views::all_t<_Range>, 0>;
3530 template<typename _Range>
3531 using values_view = elements_view<views::all_t<_Range>, 1>;
3537 template<size_t _Nm, typename _Range>
3538 concept __can_elements_view
3539 = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
3540 } // namespace __detail
3542 template<size_t _Nm>
3543 struct _Elements : __adaptor::_RangeAdaptorClosure
3545 template<viewable_range _Range>
3546 requires __detail::__can_elements_view<_Nm, _Range>
3548 operator()(_Range&& __r) const
3550 return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
3554 template<size_t _Nm>
3555 inline constexpr _Elements<_Nm> elements;
3556 inline constexpr auto keys = elements<0>;
3557 inline constexpr auto values = elements<1>;
3558 } // namespace views
3560 } // namespace ranges
3562 namespace views = ranges::views;
3564 _GLIBCXX_END_NAMESPACE_VERSION
3566 #endif // library concepts
3568 #endif /* _GLIBCXX_RANGES */