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
731 template<typename _Tp>
732 inline constexpr auto
733 __maybe_refwrap(_Tp& __arg)
734 { return reference_wrapper<_Tp>{__arg}; }
736 template<typename _Tp>
737 inline constexpr auto
738 __maybe_refwrap(const _Tp& __arg)
739 { return reference_wrapper<const _Tp>{__arg}; }
741 template<typename _Tp>
742 inline constexpr decltype(auto)
743 __maybe_refwrap(_Tp&& __arg)
744 { return std::forward<_Tp>(__arg); }
746 template<typename _Callable>
747 struct _RangeAdaptorClosure;
749 template<typename _Callable>
753 [[no_unique_address]]
754 __detail::__maybe_present_t<!is_default_constructible_v<_Callable>,
755 _Callable> _M_callable;
759 _RangeAdaptor(const _Callable& = {})
760 requires is_default_constructible_v<_Callable>
764 _RangeAdaptor(_Callable __callable)
765 requires (!is_default_constructible_v<_Callable>)
766 : _M_callable(std::move(__callable))
769 template<typename... _Args>
770 requires (sizeof...(_Args) >= 1)
772 operator()(_Args&&... __args) const
774 // [range.adaptor.object]: If a range adaptor object accepts more
775 // than one argument, then the following expressions are equivalent:
777 // (1) adaptor(range, args...)
778 // (2) adaptor(args...)(range)
779 // (3) range | adaptor(args...)
781 // In this case, adaptor(args...) is a range adaptor closure object.
783 // We handle (1) and (2) here, and (3) is just a special case of a
784 // more general case already handled by _RangeAdaptorClosure.
785 if constexpr (is_invocable_v<_Callable, _Args...>)
787 static_assert(sizeof...(_Args) != 1,
788 "a _RangeAdaptor that accepts only one argument "
789 "should be defined as a _RangeAdaptorClosure");
790 // Here we handle adaptor(range, args...) -- just forward all
791 // arguments to the underlying adaptor routine.
792 return _Callable{}(std::forward<_Args>(__args)...);
796 // Here we handle adaptor(args...)(range).
797 // Given args..., we return a _RangeAdaptorClosure that takes a
798 // range argument, such that (2) is equivalent to (1).
800 // We need to be careful about how we capture args... in this
801 // closure. By using __maybe_refwrap, we capture lvalue
802 // references by reference (through a reference_wrapper) and
803 // otherwise capture by value.
805 = [...__args(__maybe_refwrap(std::forward<_Args>(__args)))]
806 <typename _Range> (_Range&& __r) {
807 // This static_cast has two purposes: it forwards a
808 // reference_wrapper<T> capture as a T&, and otherwise
809 // forwards the captured argument as an rvalue.
810 return _Callable{}(std::forward<_Range>(__r),
811 (static_cast<unwrap_reference_t
812 <remove_const_t<decltype(__args)>>>
815 using _ClosureType = decltype(__closure);
816 return _RangeAdaptorClosure<_ClosureType>(std::move(__closure));
821 template<typename _Callable>
822 _RangeAdaptor(_Callable) -> _RangeAdaptor<_Callable>;
824 template<typename _Callable>
825 struct _RangeAdaptorClosure : public _RangeAdaptor<_Callable>
827 using _RangeAdaptor<_Callable>::_RangeAdaptor;
829 template<viewable_range _Range>
830 requires requires { declval<_Callable>()(declval<_Range>()); }
832 operator()(_Range&& __r) const
834 if constexpr (is_default_constructible_v<_Callable>)
835 return _Callable{}(std::forward<_Range>(__r));
837 return this->_M_callable(std::forward<_Range>(__r));
840 template<viewable_range _Range>
841 requires requires { declval<_Callable>()(declval<_Range>()); }
842 friend constexpr auto
843 operator|(_Range&& __r, const _RangeAdaptorClosure& __o)
844 { return __o(std::forward<_Range>(__r)); }
846 template<typename _Tp>
847 friend constexpr auto
848 operator|(const _RangeAdaptorClosure<_Tp>& __x,
849 const _RangeAdaptorClosure& __y)
851 if constexpr (is_default_constructible_v<_Tp>
852 && is_default_constructible_v<_Callable>)
854 auto __closure = [] <typename _Up> (_Up&& __e) {
855 return std::forward<_Up>(__e) | decltype(__x){} | decltype(__y){};
857 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
859 else if constexpr (is_default_constructible_v<_Tp>
860 && !is_default_constructible_v<_Callable>)
862 auto __closure = [__y] <typename _Up> (_Up&& __e) {
863 return std::forward<_Up>(__e) | decltype(__x){} | __y;
865 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
867 else if constexpr (!is_default_constructible_v<_Tp>
868 && is_default_constructible_v<_Callable>)
870 auto __closure = [__x] <typename _Up> (_Up&& __e) {
871 return std::forward<_Up>(__e) | __x | decltype(__y){};
873 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
877 auto __closure = [__x, __y] <typename _Up> (_Up&& __e) {
878 return std::forward<_Up>(__e) | __x | __y;
880 return _RangeAdaptorClosure<decltype(__closure)>(__closure);
885 template<typename _Callable>
886 _RangeAdaptorClosure(_Callable) -> _RangeAdaptorClosure<_Callable>;
887 } // namespace __adaptor
890 template<range _Range> requires is_object_v<_Range>
891 class ref_view : public view_interface<ref_view<_Range>>
894 _Range* _M_r = nullptr;
896 static void _S_fun(_Range&); // not defined
897 static void _S_fun(_Range&&) = delete;
901 ref_view() noexcept = default;
903 template<__detail::__not_same_as<ref_view> _Tp>
904 requires convertible_to<_Tp, _Range&>
905 && requires { _S_fun(declval<_Tp>()); }
908 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
915 constexpr iterator_t<_Range>
917 { return ranges::begin(*_M_r); }
919 constexpr sentinel_t<_Range>
921 { return ranges::end(*_M_r); }
924 empty() const requires requires { ranges::empty(*_M_r); }
925 { return ranges::empty(*_M_r); }
928 size() const requires sized_range<_Range>
929 { return ranges::size(*_M_r); }
932 data() const requires contiguous_range<_Range>
933 { return ranges::data(*_M_r); }
936 template<typename _Range>
937 ref_view(_Range&) -> ref_view<_Range>;
939 template<typename _Tp>
940 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
944 inline constexpr __adaptor::_RangeAdaptorClosure all
945 = [] <viewable_range _Range> (_Range&& __r)
947 if constexpr (view<decay_t<_Range>>)
948 return std::forward<_Range>(__r);
949 else if constexpr (requires { ref_view{std::forward<_Range>(__r)}; })
950 return ref_view{std::forward<_Range>(__r)};
952 return subrange{std::forward<_Range>(__r)};
955 template<viewable_range _Range>
956 using all_t = decltype(all(std::declval<_Range>()));
960 // XXX: the following algos are copied from ranges_algo.h to avoid a circular
961 // dependency with that header.
964 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
965 typename _Proj = identity,
966 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
968 find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
970 while (__first != __last
971 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
976 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
977 typename _Proj = identity,
978 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
980 find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
982 while (__first != __last
983 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
988 template<typename _Tp, typename _Proj = identity,
989 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
990 _Comp = ranges::less>
992 min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
994 if (std::__invoke(std::move(__comp),
995 std::__invoke(__proj, __b),
996 std::__invoke(__proj, __a)))
1002 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1003 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1004 typename _Pred = ranges::equal_to,
1005 typename _Proj1 = identity, typename _Proj2 = identity>
1006 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
1007 constexpr pair<_Iter1, _Iter2>
1008 mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
1009 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
1011 while (__first1 != __last1 && __first2 != __last2
1012 && (bool)std::__invoke(__pred,
1013 std::__invoke(__proj1, *__first1),
1014 std::__invoke(__proj2, *__first2)))
1019 return { std::move(__first1), std::move(__first2) };
1021 } // namespace __detail
1025 template<range _Range>
1026 struct _CachedPosition
1029 _M_has_value() const
1032 constexpr iterator_t<_Range>
1033 _M_get(const _Range&) const
1035 __glibcxx_assert(false);
1040 _M_set(const _Range&, const iterator_t<_Range>&) const
1044 template<forward_range _Range>
1045 struct _CachedPosition<_Range>
1048 iterator_t<_Range> _M_iter{};
1052 _M_has_value() const
1053 { return _M_iter != iterator_t<_Range>{}; }
1055 constexpr iterator_t<_Range>
1056 _M_get(const _Range&) const
1058 __glibcxx_assert(_M_has_value());
1063 _M_set(const _Range&, const iterator_t<_Range>& __it)
1065 __glibcxx_assert(!_M_has_value());
1070 template<random_access_range _Range>
1071 requires (sizeof(range_difference_t<_Range>)
1072 <= sizeof(iterator_t<_Range>))
1073 struct _CachedPosition<_Range>
1076 range_difference_t<_Range> _M_offset = -1;
1080 _M_has_value() const
1081 { return _M_offset >= 0; }
1083 constexpr iterator_t<_Range>
1084 _M_get(_Range& __r) const
1086 __glibcxx_assert(_M_has_value());
1087 return ranges::begin(__r) + _M_offset;
1091 _M_set(_Range& __r, const iterator_t<_Range>& __it)
1093 __glibcxx_assert(!_M_has_value());
1094 _M_offset = __it - ranges::begin(__r);
1098 } // namespace __detail
1100 template<input_range _Vp,
1101 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1102 requires view<_Vp> && is_object_v<_Pred>
1103 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1111 static constexpr auto
1114 if constexpr (bidirectional_range<_Vp>)
1115 return bidirectional_iterator_tag{};
1116 else if constexpr (forward_range<_Vp>)
1117 return forward_iterator_tag{};
1119 return input_iterator_tag{};
1122 static constexpr auto
1125 using _Cat = typename iterator_traits<_Vp_iter>::iterator_category;
1126 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1127 return bidirectional_iterator_tag{};
1128 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1129 return forward_iterator_tag{};
1136 using _Vp_iter = iterator_t<_Vp>;
1138 _Vp_iter _M_current = _Vp_iter();
1139 filter_view* _M_parent = nullptr;
1142 using iterator_concept = decltype(_S_iter_concept());
1143 using iterator_category = decltype(_S_iter_cat());
1144 using value_type = range_value_t<_Vp>;
1145 using difference_type = range_difference_t<_Vp>;
1147 _Iterator() = default;
1150 _Iterator(filter_view* __parent, _Vp_iter __current)
1151 : _M_current(std::move(__current)),
1157 requires copyable<_Vp_iter>
1158 { return _M_current; }
1162 { return std::move(_M_current); }
1164 constexpr range_reference_t<_Vp>
1166 { return *_M_current; }
1170 requires __detail::__has_arrow<_Vp_iter>
1171 && copyable<_Vp_iter>
1172 { return _M_current; }
1174 constexpr _Iterator&
1177 _M_current = __detail::find_if(std::move(++_M_current),
1178 ranges::end(_M_parent->_M_base),
1179 std::ref(*_M_parent->_M_pred));
1188 operator++(int) requires forward_range<_Vp>
1195 constexpr _Iterator&
1196 operator--() requires bidirectional_range<_Vp>
1200 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1205 operator--(int) requires bidirectional_range<_Vp>
1212 friend constexpr bool
1213 operator==(const _Iterator& __x, const _Iterator& __y)
1214 requires equality_comparable<_Vp_iter>
1215 { return __x._M_current == __y._M_current; }
1217 friend constexpr range_rvalue_reference_t<_Vp>
1218 iter_move(const _Iterator& __i)
1219 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1220 { return ranges::iter_move(__i._M_current); }
1222 friend constexpr void
1223 iter_swap(const _Iterator& __x, const _Iterator& __y)
1224 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1225 requires indirectly_swappable<_Vp_iter>
1226 { ranges::iter_swap(__x._M_current, __y._M_current); }
1232 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1235 __equal(const _Iterator& __i) const
1236 { return __i._M_current == _M_end; }
1239 _Sentinel() = default;
1242 _Sentinel(filter_view* __parent)
1243 : _M_end(ranges::end(__parent->_M_base))
1246 constexpr sentinel_t<_Vp>
1250 friend constexpr bool
1251 operator==(const _Iterator& __x, const _Sentinel& __y)
1252 { return __y.__equal(__x); }
1255 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1256 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1257 _Vp _M_base = _Vp();
1260 filter_view() = default;
1263 filter_view(_Vp __base, _Pred __pred)
1264 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
1268 base() const& requires copy_constructible<_Vp>
1273 { return std::move(_M_base); }
1275 constexpr const _Pred&
1277 { return *_M_pred; }
1282 if (_M_cached_begin._M_has_value())
1283 return {this, _M_cached_begin._M_get(_M_base)};
1285 __glibcxx_assert(_M_pred.has_value());
1286 auto __it = __detail::find_if(ranges::begin(_M_base),
1287 ranges::end(_M_base),
1288 std::ref(*_M_pred));
1289 _M_cached_begin._M_set(_M_base, __it);
1290 return {this, std::move(__it)};
1296 if constexpr (common_range<_Vp>)
1297 return _Iterator{this, ranges::end(_M_base)};
1299 return _Sentinel{this};
1303 template<typename _Range, typename _Pred>
1304 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1308 inline constexpr __adaptor::_RangeAdaptor filter
1309 = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
1311 return filter_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1313 } // namespace views
1315 template<input_range _Vp, copy_constructible _Fp>
1316 requires view<_Vp> && is_object_v<_Fp>
1317 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1318 && std::__detail::__can_reference<invoke_result_t<_Fp&,
1319 range_reference_t<_Vp>>>
1320 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1323 template<bool _Const>
1326 template<bool _Const>
1330 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1331 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1333 static constexpr auto
1336 if constexpr (random_access_range<_Vp>)
1337 return random_access_iterator_tag{};
1338 else if constexpr (bidirectional_range<_Vp>)
1339 return bidirectional_iterator_tag{};
1340 else if constexpr (forward_range<_Vp>)
1341 return forward_iterator_tag{};
1343 return input_iterator_tag{};
1346 static constexpr auto
1349 using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1350 if constexpr (is_lvalue_reference_v<_Res>)
1353 = typename iterator_traits<_Base_iter>::iterator_category;
1354 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1355 return random_access_iterator_tag{};
1360 return input_iterator_tag{};
1363 using _Base_iter = iterator_t<_Base>;
1365 _Base_iter _M_current = _Base_iter();
1366 _Parent* _M_parent = nullptr;
1369 using iterator_concept = decltype(_S_iter_concept());
1370 using iterator_category = decltype(_S_iter_cat());
1372 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1373 using difference_type = range_difference_t<_Base>;
1375 _Iterator() = default;
1378 _Iterator(_Parent* __parent, _Base_iter __current)
1379 : _M_current(std::move(__current)),
1384 _Iterator(_Iterator<!_Const> __i)
1386 && convertible_to<iterator_t<_Vp>, _Base_iter>
1387 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1390 constexpr _Base_iter
1392 requires copyable<_Base_iter>
1393 { return _M_current; }
1395 constexpr _Base_iter
1397 { return std::move(_M_current); }
1399 constexpr decltype(auto)
1401 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1402 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1404 constexpr _Iterator&
1416 operator++(int) requires forward_range<_Base>
1423 constexpr _Iterator&
1424 operator--() requires bidirectional_range<_Base>
1431 operator--(int) requires bidirectional_range<_Base>
1438 constexpr _Iterator&
1439 operator+=(difference_type __n) requires random_access_range<_Base>
1445 constexpr _Iterator&
1446 operator-=(difference_type __n) requires random_access_range<_Base>
1452 constexpr decltype(auto)
1453 operator[](difference_type __n) const
1454 requires random_access_range<_Base>
1455 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1457 friend constexpr bool
1458 operator==(const _Iterator& __x, const _Iterator& __y)
1459 requires equality_comparable<_Base_iter>
1460 { return __x._M_current == __y._M_current; }
1462 friend constexpr bool
1463 operator<(const _Iterator& __x, const _Iterator& __y)
1464 requires random_access_range<_Base>
1465 { return __x._M_current < __y._M_current; }
1467 friend constexpr bool
1468 operator>(const _Iterator& __x, const _Iterator& __y)
1469 requires random_access_range<_Base>
1470 { return __y < __x; }
1472 friend constexpr bool
1473 operator<=(const _Iterator& __x, const _Iterator& __y)
1474 requires random_access_range<_Base>
1475 { return !(__y < __x); }
1477 friend constexpr bool
1478 operator>=(const _Iterator& __x, const _Iterator& __y)
1479 requires random_access_range<_Base>
1480 { return !(__x < __y); }
1482 #ifdef __cpp_lib_three_way_comparison
1483 friend constexpr auto
1484 operator<=>(const _Iterator& __x, const _Iterator& __y)
1485 requires random_access_range<_Base>
1486 && three_way_comparable<_Base_iter>
1487 { return __x._M_current <=> __y._M_current; }
1490 friend constexpr _Iterator
1491 operator+(_Iterator __i, difference_type __n)
1492 requires random_access_range<_Base>
1493 { return {__i._M_parent, __i._M_current + __n}; }
1495 friend constexpr _Iterator
1496 operator+(difference_type __n, _Iterator __i)
1497 requires random_access_range<_Base>
1498 { return {__i._M_parent, __i._M_current + __n}; }
1500 friend constexpr _Iterator
1501 operator-(_Iterator __i, difference_type __n)
1502 requires random_access_range<_Base>
1503 { return {__i._M_parent, __i._M_current - __n}; }
1505 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1506 // 3483. transform_view::iterator's difference is overconstrained
1507 friend constexpr difference_type
1508 operator-(const _Iterator& __x, const _Iterator& __y)
1509 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1510 { return __x._M_current - __y._M_current; }
1512 friend constexpr decltype(auto)
1513 iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1515 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1516 return std::move(*__i);
1521 friend constexpr void
1522 iter_swap(const _Iterator& __x, const _Iterator& __y)
1523 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1524 requires indirectly_swappable<_Base_iter>
1525 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1527 friend _Iterator<!_Const>;
1528 template<bool> friend struct _Sentinel;
1531 template<bool _Const>
1535 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1536 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1538 template<bool _Const2>
1540 __distance_from(const _Iterator<_Const2>& __i) const
1541 { return _M_end - __i._M_current; }
1543 template<bool _Const2>
1545 __equal(const _Iterator<_Const2>& __i) const
1546 { return __i._M_current == _M_end; }
1548 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1551 _Sentinel() = default;
1554 _Sentinel(sentinel_t<_Base> __end)
1559 _Sentinel(_Sentinel<!_Const> __i)
1561 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1562 : _M_end(std::move(__i._M_end))
1565 constexpr sentinel_t<_Base>
1569 template<bool _Const2>
1570 requires sentinel_for<sentinel_t<_Base>,
1571 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1572 friend constexpr bool
1573 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1574 { return __y.__equal(__x); }
1576 template<bool _Const2,
1577 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1578 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1579 friend constexpr range_difference_t<_Base2>
1580 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1581 { return -__y.__distance_from(__x); }
1583 template<bool _Const2,
1584 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1585 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1586 friend constexpr range_difference_t<_Base2>
1587 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1588 { return __y.__distance_from(__x); }
1590 friend _Sentinel<!_Const>;
1593 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1594 _Vp _M_base = _Vp();
1597 transform_view() = default;
1600 transform_view(_Vp __base, _Fp __fun)
1601 : _M_fun(std::move(__fun)), _M_base(std::move(__base))
1605 base() const& requires copy_constructible<_Vp>
1606 { return _M_base ; }
1610 { return std::move(_M_base); }
1612 constexpr _Iterator<false>
1614 { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1616 constexpr _Iterator<true>
1618 requires range<const _Vp>
1619 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1620 { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1622 constexpr _Sentinel<false>
1624 { return _Sentinel<false>{ranges::end(_M_base)}; }
1626 constexpr _Iterator<false>
1627 end() requires common_range<_Vp>
1628 { return _Iterator<false>{this, ranges::end(_M_base)}; }
1630 constexpr _Sentinel<true>
1632 requires range<const _Vp>
1633 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1634 { return _Sentinel<true>{ranges::end(_M_base)}; }
1636 constexpr _Iterator<true>
1638 requires common_range<const _Vp>
1639 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1640 { return _Iterator<true>{this, ranges::end(_M_base)}; }
1643 size() requires sized_range<_Vp>
1644 { return ranges::size(_M_base); }
1647 size() const requires sized_range<const _Vp>
1648 { return ranges::size(_M_base); }
1651 template<typename _Range, typename _Fp>
1652 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1656 inline constexpr __adaptor::_RangeAdaptor transform
1657 = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
1659 return transform_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
1661 } // namespace views
1664 class take_view : public view_interface<take_view<_Vp>>
1667 template<bool _Const>
1668 using _CI = counted_iterator<
1669 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1671 template<bool _Const>
1675 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1676 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1679 _Sentinel() = default;
1682 _Sentinel(sentinel_t<_Base> __end)
1687 _Sentinel(_Sentinel<!_Const> __s)
1688 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1689 : _M_end(std::move(__s._M_end))
1692 constexpr sentinel_t<_Base>
1696 friend constexpr bool
1697 operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1698 { return __y.count() == 0 || __y.base() == __x._M_end; }
1700 template<bool _OtherConst = !_Const,
1701 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1702 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1703 friend constexpr bool
1704 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1705 { return __y.count() == 0 || __y.base() == __x._M_end; }
1707 friend _Sentinel<!_Const>;
1710 range_difference_t<_Vp> _M_count = 0;
1711 _Vp _M_base = _Vp();
1714 take_view() = default;
1717 take_view(_Vp base, range_difference_t<_Vp> __count)
1718 : _M_count(std::move(__count)), _M_base(std::move(base))
1722 base() const& requires copy_constructible<_Vp>
1727 { return std::move(_M_base); }
1730 begin() requires (!__detail::__simple_view<_Vp>)
1732 if constexpr (sized_range<_Vp>)
1734 if constexpr (random_access_range<_Vp>)
1735 return ranges::begin(_M_base);
1739 return counted_iterator{ranges::begin(_M_base), __sz};
1743 return counted_iterator{ranges::begin(_M_base), _M_count};
1747 begin() const requires range<const _Vp>
1749 if constexpr (sized_range<const _Vp>)
1751 if constexpr (random_access_range<const _Vp>)
1752 return ranges::begin(_M_base);
1756 return counted_iterator{ranges::begin(_M_base), __sz};
1760 return counted_iterator{ranges::begin(_M_base), _M_count};
1764 end() requires (!__detail::__simple_view<_Vp>)
1766 if constexpr (sized_range<_Vp>)
1768 if constexpr (random_access_range<_Vp>)
1769 return ranges::begin(_M_base) + size();
1771 return default_sentinel;
1774 return _Sentinel<false>{ranges::end(_M_base)};
1778 end() const requires range<const _Vp>
1780 if constexpr (sized_range<const _Vp>)
1782 if constexpr (random_access_range<const _Vp>)
1783 return ranges::begin(_M_base) + size();
1785 return default_sentinel;
1788 return _Sentinel<true>{ranges::end(_M_base)};
1792 size() requires sized_range<_Vp>
1794 auto __n = ranges::size(_M_base);
1795 return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
1799 size() const requires sized_range<const _Vp>
1801 auto __n = ranges::size(_M_base);
1802 return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
1806 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1807 // 3447. Deduction guides for take_view and drop_view have different
1809 template<typename _Range>
1810 take_view(_Range&&, range_difference_t<_Range>)
1811 -> take_view<views::all_t<_Range>>;
1813 template<typename _Tp>
1814 inline constexpr bool enable_borrowed_range<take_view<_Tp>>
1815 = enable_borrowed_range<_Tp>;
1819 inline constexpr __adaptor::_RangeAdaptor take
1820 = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
1822 return take_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
1824 } // namespace views
1826 template<view _Vp, typename _Pred>
1827 requires input_range<_Vp> && is_object_v<_Pred>
1828 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
1829 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
1831 template<bool _Const>
1835 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1837 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1838 const _Pred* _M_pred = nullptr;
1841 _Sentinel() = default;
1844 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
1845 : _M_end(__end), _M_pred(__pred)
1849 _Sentinel(_Sentinel<!_Const> __s)
1850 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1851 : _M_end(__s._M_end), _M_pred(__s._M_pred)
1854 constexpr sentinel_t<_Base>
1855 base() const { return _M_end; }
1857 friend constexpr bool
1858 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
1859 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1861 template<bool _OtherConst = !_Const,
1862 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1863 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1864 friend constexpr bool
1865 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
1866 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
1868 friend _Sentinel<!_Const>;
1871 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1872 _Vp _M_base = _Vp();
1875 take_while_view() = default;
1878 take_while_view(_Vp base, _Pred __pred)
1879 : _M_pred(std::move(__pred)), _M_base(std::move(base))
1883 base() const& requires copy_constructible<_Vp>
1888 { return std::move(_M_base); }
1890 constexpr const _Pred&
1892 { return *_M_pred; }
1895 begin() requires (!__detail::__simple_view<_Vp>)
1896 { return ranges::begin(_M_base); }
1899 begin() const requires range<const _Vp>
1900 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1901 { return ranges::begin(_M_base); }
1904 end() requires (!__detail::__simple_view<_Vp>)
1905 { return _Sentinel<false>(ranges::end(_M_base),
1906 std::__addressof(*_M_pred)); }
1909 end() const requires range<const _Vp>
1910 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
1911 { return _Sentinel<true>(ranges::end(_M_base),
1912 std::__addressof(*_M_pred)); }
1915 template<typename _Range, typename _Pred>
1916 take_while_view(_Range&&, _Pred)
1917 -> take_while_view<views::all_t<_Range>, _Pred>;
1921 inline constexpr __adaptor::_RangeAdaptor take_while
1922 = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
1924 return take_while_view{std::forward<_Range>(__r), std::forward<_Pred>(__p)};
1926 } // namespace views
1929 class drop_view : public view_interface<drop_view<_Vp>>
1932 range_difference_t<_Vp> _M_count = 0;
1933 _Vp _M_base = _Vp();
1935 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
1936 // both random_access_range and sized_range. Otherwise, cache its result.
1937 static constexpr bool _S_needs_cached_begin
1938 = !(random_access_range<const _Vp> && sized_range<const _Vp>);
1939 [[no_unique_address]]
1940 __detail::__maybe_present_t<_S_needs_cached_begin,
1941 __detail::_CachedPosition<_Vp>>
1945 drop_view() = default;
1948 drop_view(_Vp __base, range_difference_t<_Vp> __count)
1949 : _M_count(__count), _M_base(std::move(__base))
1950 { __glibcxx_assert(__count >= 0); }
1953 base() const& requires copy_constructible<_Vp>
1958 { return std::move(_M_base); }
1960 // This overload is disabled for simple views with constant-time begin().
1963 requires (!(__detail::__simple_view<_Vp>
1964 && random_access_range<const _Vp>
1965 && sized_range<const _Vp>))
1967 if constexpr (_S_needs_cached_begin)
1968 if (_M_cached_begin._M_has_value())
1969 return _M_cached_begin._M_get(_M_base);
1971 auto __it = ranges::next(ranges::begin(_M_base),
1972 _M_count, ranges::end(_M_base));
1973 if constexpr (_S_needs_cached_begin)
1974 _M_cached_begin._M_set(_M_base, __it);
1978 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1979 // 3482. drop_view's const begin should additionally require sized_range
1982 requires random_access_range<const _Vp> && sized_range<const _Vp>
1984 return ranges::next(ranges::begin(_M_base), _M_count,
1985 ranges::end(_M_base));
1989 end() requires (!__detail::__simple_view<_Vp>)
1990 { return ranges::end(_M_base); }
1993 end() const requires range<const _Vp>
1994 { return ranges::end(_M_base); }
1997 size() requires sized_range<_Vp>
1999 const auto __s = ranges::size(_M_base);
2000 const auto __c = static_cast<decltype(__s)>(_M_count);
2001 return __s < __c ? 0 : __s - __c;
2005 size() const requires sized_range<const _Vp>
2007 const auto __s = ranges::size(_M_base);
2008 const auto __c = static_cast<decltype(__s)>(_M_count);
2009 return __s < __c ? 0 : __s - __c;
2013 template<typename _Range>
2014 drop_view(_Range&&, range_difference_t<_Range>)
2015 -> drop_view<views::all_t<_Range>>;
2017 template<typename _Tp>
2018 inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2019 = enable_borrowed_range<_Tp>;
2023 inline constexpr __adaptor::_RangeAdaptor drop
2024 = [] <viewable_range _Range, typename _Tp> (_Range&& __r, _Tp&& __n)
2026 return drop_view{std::forward<_Range>(__r), std::forward<_Tp>(__n)};
2028 } // namespace views
2030 template<view _Vp, typename _Pred>
2031 requires input_range<_Vp> && is_object_v<_Pred>
2032 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2033 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2036 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2037 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2038 _Vp _M_base = _Vp();
2041 drop_while_view() = default;
2044 drop_while_view(_Vp __base, _Pred __pred)
2045 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
2049 base() const& requires copy_constructible<_Vp>
2054 { return std::move(_M_base); }
2056 constexpr const _Pred&
2058 { return *_M_pred; }
2063 if (_M_cached_begin._M_has_value())
2064 return _M_cached_begin._M_get(_M_base);
2066 auto __it = __detail::find_if_not(ranges::begin(_M_base),
2067 ranges::end(_M_base),
2068 std::cref(*_M_pred));
2069 _M_cached_begin._M_set(_M_base, __it);
2075 { return ranges::end(_M_base); }
2078 template<typename _Range, typename _Pred>
2079 drop_while_view(_Range&&, _Pred)
2080 -> drop_while_view<views::all_t<_Range>, _Pred>;
2082 template<typename _Tp, typename _Pred>
2083 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2084 = enable_borrowed_range<_Tp>;
2088 inline constexpr __adaptor::_RangeAdaptor drop_while
2089 = [] <viewable_range _Range, typename _Pred> (_Range&& __r, _Pred&& __p)
2091 return drop_while_view{std::forward<_Range>(__r),
2092 std::forward<_Pred>(__p)};
2094 } // namespace views
2096 template<input_range _Vp>
2097 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2098 && (is_reference_v<range_reference_t<_Vp>>
2099 || view<range_value_t<_Vp>>)
2100 class join_view : public view_interface<join_view<_Vp>>
2103 using _InnerRange = range_reference_t<_Vp>;
2105 template<bool _Const>
2108 template<bool _Const>
2112 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2113 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2115 static constexpr bool _S_ref_is_glvalue
2116 = is_reference_v<range_reference_t<_Base>>;
2121 auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto&
2123 if constexpr (_S_ref_is_glvalue)
2126 return (_M_parent->_M_inner = views::all(std::move(__x)));
2129 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2131 auto& __inner = __update_inner(*_M_outer);
2132 _M_inner = ranges::begin(__inner);
2133 if (_M_inner != ranges::end(__inner))
2137 if constexpr (_S_ref_is_glvalue)
2138 _M_inner = _Inner_iter();
2141 static constexpr auto
2144 if constexpr (_S_ref_is_glvalue
2145 && bidirectional_range<_Base>
2146 && bidirectional_range<range_reference_t<_Base>>)
2147 return bidirectional_iterator_tag{};
2148 else if constexpr (_S_ref_is_glvalue
2149 && forward_range<_Base>
2150 && forward_range<range_reference_t<_Base>>)
2151 return forward_iterator_tag{};
2153 return input_iterator_tag{};
2156 static constexpr auto
2160 = typename iterator_traits<_Outer_iter>::iterator_category;
2162 = typename iterator_traits<_Inner_iter>::iterator_category;
2163 if constexpr (_S_ref_is_glvalue
2164 && derived_from<_OuterCat, bidirectional_iterator_tag>
2165 && derived_from<_InnerCat, bidirectional_iterator_tag>)
2166 return bidirectional_iterator_tag{};
2167 else if constexpr (_S_ref_is_glvalue
2168 && derived_from<_OuterCat, forward_iterator_tag>
2169 && derived_from<_InnerCat, forward_iterator_tag>)
2170 return forward_iterator_tag{};
2171 else if constexpr (derived_from<_OuterCat, input_iterator_tag>
2172 && derived_from<_InnerCat, input_iterator_tag>)
2173 return input_iterator_tag{};
2175 return output_iterator_tag{};
2178 using _Outer_iter = iterator_t<_Base>;
2179 using _Inner_iter = iterator_t<range_reference_t<_Base>>;
2181 _Outer_iter _M_outer = _Outer_iter();
2182 _Inner_iter _M_inner = _Inner_iter();
2183 _Parent* _M_parent = nullptr;
2186 using iterator_concept = decltype(_S_iter_concept());
2187 using iterator_category = decltype(_S_iter_cat());
2188 using value_type = range_value_t<range_reference_t<_Base>>;
2189 using difference_type
2190 = common_type_t<range_difference_t<_Base>,
2191 range_difference_t<range_reference_t<_Base>>>;
2193 _Iterator() = default;
2196 _Iterator(_Parent* __parent, _Outer_iter __outer)
2197 : _M_outer(std::move(__outer)),
2202 _Iterator(_Iterator<!_Const> __i)
2204 && convertible_to<iterator_t<_Vp>, _Outer_iter>
2205 && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2206 : _M_outer(std::move(__i._M_outer)), _M_inner(__i._M_inner),
2207 _M_parent(__i._M_parent)
2210 constexpr decltype(auto)
2212 { return *_M_inner; }
2214 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2215 // 3500. join_view::iterator::operator->() is bogus
2216 constexpr _Inner_iter
2218 requires __detail::__has_arrow<_Inner_iter>
2219 && copyable<_Inner_iter>
2220 { return _M_inner; }
2222 constexpr _Iterator&
2225 auto&& __inner_range = [this] () -> decltype(auto) {
2226 if constexpr (_S_ref_is_glvalue)
2229 return _M_parent->_M_inner;
2231 if (++_M_inner == ranges::end(__inner_range))
2245 requires _S_ref_is_glvalue && forward_range<_Base>
2246 && forward_range<range_reference_t<_Base>>
2253 constexpr _Iterator&
2255 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2256 && bidirectional_range<range_reference_t<_Base>>
2257 && common_range<range_reference_t<_Base>>
2259 if (_M_outer == ranges::end(_M_parent->_M_base))
2260 _M_inner = ranges::end(*--_M_outer);
2261 while (_M_inner == ranges::begin(*_M_outer))
2262 _M_inner = ranges::end(*--_M_outer);
2269 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2270 && bidirectional_range<range_reference_t<_Base>>
2271 && common_range<range_reference_t<_Base>>
2278 friend constexpr bool
2279 operator==(const _Iterator& __x, const _Iterator& __y)
2280 requires _S_ref_is_glvalue
2281 && equality_comparable<_Outer_iter>
2282 && equality_comparable<_Inner_iter>
2284 return (__x._M_outer == __y._M_outer
2285 && __x._M_inner == __y._M_inner);
2288 friend constexpr decltype(auto)
2289 iter_move(const _Iterator& __i)
2290 noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2291 { return ranges::iter_move(__i._M_inner); }
2293 friend constexpr void
2294 iter_swap(const _Iterator& __x, const _Iterator& __y)
2295 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2296 { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2298 friend _Iterator<!_Const>;
2299 template<bool> friend struct _Sentinel;
2302 template<bool _Const>
2306 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2307 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2309 template<bool _Const2>
2311 __equal(const _Iterator<_Const2>& __i) const
2312 { return __i._M_outer == _M_end; }
2314 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2317 _Sentinel() = default;
2320 _Sentinel(_Parent* __parent)
2321 : _M_end(ranges::end(__parent->_M_base))
2325 _Sentinel(_Sentinel<!_Const> __s)
2326 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2327 : _M_end(std::move(__s._M_end))
2330 template<bool _Const2>
2331 requires sentinel_for<sentinel_t<_Base>,
2332 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2333 friend constexpr bool
2334 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2335 { return __y.__equal(__x); }
2337 friend _Sentinel<!_Const>;
2340 // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2341 [[no_unique_address]]
2342 __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
2343 views::all_t<_InnerRange>> _M_inner;
2344 _Vp _M_base = _Vp();
2347 join_view() = default;
2350 join_view(_Vp __base)
2351 : _M_base(std::move(__base))
2355 base() const& requires copy_constructible<_Vp>
2360 { return std::move(_M_base); }
2365 constexpr bool __use_const
2366 = (__detail::__simple_view<_Vp>
2367 && is_reference_v<range_reference_t<_Vp>>);
2368 return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2373 requires input_range<const _Vp>
2374 && is_reference_v<range_reference_t<const _Vp>>
2376 return _Iterator<true>{this, ranges::begin(_M_base)};
2382 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2383 && forward_range<_InnerRange>
2384 && common_range<_Vp> && common_range<_InnerRange>)
2385 return _Iterator<__detail::__simple_view<_Vp>>{this,
2386 ranges::end(_M_base)};
2388 return _Sentinel<__detail::__simple_view<_Vp>>{this};
2393 requires input_range<const _Vp>
2394 && is_reference_v<range_reference_t<const _Vp>>
2396 if constexpr (forward_range<const _Vp>
2397 && is_reference_v<range_reference_t<const _Vp>>
2398 && forward_range<range_reference_t<const _Vp>>
2399 && common_range<const _Vp>
2400 && common_range<range_reference_t<const _Vp>>)
2401 return _Iterator<true>{this, ranges::end(_M_base)};
2403 return _Sentinel<true>{this};
2407 template<typename _Range>
2408 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2412 inline constexpr __adaptor::_RangeAdaptorClosure join
2413 = [] <viewable_range _Range> (_Range&& __r)
2415 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2416 // 3474. Nesting join_views is broken because of CTAD
2417 return join_view<views::all_t<_Range>>{std::forward<_Range>(__r)};
2419 } // namespace views
2424 struct __require_constant;
2426 template<typename _Range>
2427 concept __tiny_range = sized_range<_Range>
2429 { typename __require_constant<remove_reference_t<_Range>::size()>; }
2430 && (remove_reference_t<_Range>::size() <= 1);
2433 template<input_range _Vp, forward_range _Pattern>
2434 requires view<_Vp> && view<_Pattern>
2435 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2437 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2438 class split_view : public view_interface<split_view<_Vp, _Pattern>>
2441 template<bool _Const>
2444 template<bool _Const>
2448 using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2449 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2453 { return __current() == ranges::end(_M_parent->_M_base); }
2455 // [range.split.outer] p1
2456 // Many of the following specifications refer to the notional member
2457 // current of outer-iterator. current is equivalent to current_ if
2458 // V models forward_range, and parent_->current_ otherwise.
2460 __current() noexcept
2462 if constexpr (forward_range<_Vp>)
2465 return _M_parent->_M_current;
2469 __current() const noexcept
2471 if constexpr (forward_range<_Vp>)
2474 return _M_parent->_M_current;
2477 _Parent* _M_parent = nullptr;
2479 // XXX: _M_current is present only if "V models forward_range"
2480 [[no_unique_address]]
2481 __detail::__maybe_present_t<forward_range<_Vp>,
2482 iterator_t<_Base>> _M_current;
2485 using iterator_concept = conditional_t<forward_range<_Base>,
2486 forward_iterator_tag,
2487 input_iterator_tag>;
2488 using iterator_category = input_iterator_tag;
2489 using difference_type = range_difference_t<_Base>;
2491 struct value_type : view_interface<value_type>
2494 _OuterIter _M_i = _OuterIter();
2497 value_type() = default;
2500 value_type(_OuterIter __i)
2501 : _M_i(std::move(__i))
2504 constexpr _InnerIter<_Const>
2506 requires copyable<_OuterIter>
2507 { return _InnerIter<_Const>{_M_i}; }
2509 constexpr _InnerIter<_Const>
2511 requires (!copyable<_OuterIter>)
2512 { return _InnerIter<_Const>{std::move(_M_i)}; }
2514 constexpr default_sentinel_t
2516 { return default_sentinel; }
2519 _OuterIter() = default;
2522 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2523 : _M_parent(__parent)
2527 _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2528 requires forward_range<_Base>
2529 : _M_parent(__parent),
2530 _M_current(std::move(__current))
2534 _OuterIter(_OuterIter<!_Const> __i)
2536 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2537 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2540 constexpr value_type
2542 { return value_type{*this}; }
2544 constexpr _OuterIter&
2547 const auto __end = ranges::end(_M_parent->_M_base);
2548 if (__current() == __end)
2550 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2551 if (__pbegin == __pend)
2557 = __detail::mismatch(std::move(__current()), __end,
2559 __current() = std::move(__b);
2562 } while (++__current() != __end);
2566 constexpr decltype(auto)
2569 if constexpr (forward_range<_Base>)
2579 friend constexpr bool
2580 operator==(const _OuterIter& __x, const _OuterIter& __y)
2581 requires forward_range<_Base>
2582 { return __x._M_current == __y._M_current; }
2584 friend constexpr bool
2585 operator==(const _OuterIter& __x, default_sentinel_t)
2586 { return __x.__at_end(); };
2588 friend _OuterIter<!_Const>;
2589 friend _InnerIter<_Const>;
2592 template<bool _Const>
2596 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2601 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2602 auto __end = ranges::end(_M_i._M_parent->_M_base);
2603 if constexpr (__detail::__tiny_range<_Pattern>)
2605 const auto& __cur = _M_i_current();
2608 if (__pcur == __pend)
2609 return _M_incremented;
2610 return *__cur == *__pcur;
2614 auto __cur = _M_i_current();
2617 if (__pcur == __pend)
2618 return _M_incremented;
2621 if (*__cur != *__pcur)
2623 if (++__pcur == __pend)
2625 } while (++__cur != __end);
2630 static constexpr auto
2634 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2635 if constexpr (derived_from<_Cat, forward_iterator_tag>)
2636 return forward_iterator_tag{};
2642 _M_i_current() noexcept
2643 { return _M_i.__current(); }
2646 _M_i_current() const noexcept
2647 { return _M_i.__current(); }
2649 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2650 bool _M_incremented = false;
2653 using iterator_concept
2654 = typename _OuterIter<_Const>::iterator_concept;
2655 using iterator_category = decltype(_S_iter_cat());
2656 using value_type = range_value_t<_Base>;
2657 using difference_type = range_difference_t<_Base>;
2659 _InnerIter() = default;
2662 _InnerIter(_OuterIter<_Const> __i)
2663 : _M_i(std::move(__i))
2666 constexpr decltype(auto)
2668 { return *_M_i_current(); }
2670 constexpr _InnerIter&
2673 _M_incremented = true;
2674 if constexpr (!forward_range<_Base>)
2675 if constexpr (_Pattern::size() == 0)
2681 constexpr decltype(auto)
2684 if constexpr (forward_range<_Vp>)
2694 friend constexpr bool
2695 operator==(const _InnerIter& __x, const _InnerIter& __y)
2696 requires forward_range<_Base>
2697 { return __x._M_i == __y._M_i; }
2699 friend constexpr bool
2700 operator==(const _InnerIter& __x, default_sentinel_t)
2701 { return __x.__at_end(); }
2703 friend constexpr decltype(auto)
2704 iter_move(const _InnerIter& __i)
2705 noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
2706 { return ranges::iter_move(__i._M_i_current()); }
2708 friend constexpr void
2709 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2710 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
2711 __y._M_i_current())))
2712 requires indirectly_swappable<iterator_t<_Base>>
2713 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
2716 _Pattern _M_pattern = _Pattern();
2717 // XXX: _M_current is "present only if !forward_range<V>"
2718 [[no_unique_address]]
2719 __detail::__maybe_present_t<!forward_range<_Vp>,
2720 iterator_t<_Vp>> _M_current;
2721 _Vp _M_base = _Vp();
2725 split_view() = default;
2728 split_view(_Vp __base, _Pattern __pattern)
2729 : _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
2732 template<input_range _Range>
2733 requires constructible_from<_Vp, views::all_t<_Range>>
2734 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2736 split_view(_Range&& __r, range_value_t<_Range> __e)
2737 : _M_pattern(std::move(__e)),
2738 _M_base(views::all(std::forward<_Range>(__r)))
2742 base() const& requires copy_constructible<_Vp>
2747 { return std::move(_M_base); }
2752 if constexpr (forward_range<_Vp>)
2753 return _OuterIter<__detail::__simple_view<_Vp>>{
2754 this, ranges::begin(_M_base)};
2757 _M_current = ranges::begin(_M_base);
2758 return _OuterIter<false>{this};
2763 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
2765 return _OuterIter<true>{this, ranges::begin(_M_base)};
2769 end() requires forward_range<_Vp> && common_range<_Vp>
2771 return _OuterIter<__detail::__simple_view<_Vp>>{
2772 this, ranges::end(_M_base)};
2778 if constexpr (forward_range<_Vp>
2779 && forward_range<const _Vp>
2780 && common_range<const _Vp>)
2781 return _OuterIter<true>{this, ranges::end(_M_base)};
2783 return default_sentinel;
2787 template<typename _Range, typename _Pred>
2788 split_view(_Range&&, _Pred&&)
2789 -> split_view<views::all_t<_Range>, views::all_t<_Pred>>;
2791 template<input_range _Range>
2792 split_view(_Range&&, range_value_t<_Range>)
2793 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
2797 inline constexpr __adaptor::_RangeAdaptor split
2798 = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
2800 return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
2802 } // namespace views
2808 template<input_or_output_iterator _Iter>
2810 operator()(_Iter __i, iter_difference_t<_Iter> __n) const
2812 if constexpr (random_access_iterator<_Iter>)
2813 return subrange{__i, __i + __n};
2815 return subrange{counted_iterator{std::move(__i), __n},
2820 inline constexpr _Counted counted{};
2821 } // namespace views
2824 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
2825 class common_view : public view_interface<common_view<_Vp>>
2828 _Vp _M_base = _Vp();
2831 common_view() = default;
2834 common_view(_Vp __r)
2835 : _M_base(std::move(__r))
2838 /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
2839 template<viewable_range _Range>
2840 requires (!common_range<_Range>)
2841 && constructible_from<_Vp, views::all_t<_Range>>
2843 common_view(_Range&& __r)
2844 : _M_base(views::all(std::forward<_Range>(__r)))
2849 base() const& requires copy_constructible<_Vp>
2854 { return std::move(_M_base); }
2859 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
2860 return ranges::begin(_M_base);
2862 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
2863 (ranges::begin(_M_base));
2867 begin() const requires range<const _Vp>
2869 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
2870 return ranges::begin(_M_base);
2872 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
2873 (ranges::begin(_M_base));
2879 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
2880 return ranges::begin(_M_base) + ranges::size(_M_base);
2882 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
2883 (ranges::end(_M_base));
2887 end() const requires range<const _Vp>
2889 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
2890 return ranges::begin(_M_base) + ranges::size(_M_base);
2892 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
2893 (ranges::end(_M_base));
2897 size() requires sized_range<_Vp>
2898 { return ranges::size(_M_base); }
2901 size() const requires sized_range<const _Vp>
2902 { return ranges::size(_M_base); }
2905 template<typename _Range>
2906 common_view(_Range&&) -> common_view<views::all_t<_Range>>;
2908 template<typename _Tp>
2909 inline constexpr bool enable_borrowed_range<common_view<_Tp>>
2910 = enable_borrowed_range<_Tp>;
2914 inline constexpr __adaptor::_RangeAdaptorClosure common
2915 = [] <viewable_range _Range> (_Range&& __r)
2917 if constexpr (common_range<_Range>
2918 && requires { views::all(std::forward<_Range>(__r)); })
2919 return views::all(std::forward<_Range>(__r));
2921 return common_view{std::forward<_Range>(__r)};
2924 } // namespace views
2927 requires bidirectional_range<_Vp>
2928 class reverse_view : public view_interface<reverse_view<_Vp>>
2931 static constexpr bool _S_needs_cached_begin
2932 = !common_range<_Vp> && !random_access_range<_Vp>;
2934 [[no_unique_address]]
2935 __detail::__maybe_present_t<_S_needs_cached_begin,
2936 __detail::_CachedPosition<_Vp>>
2938 _Vp _M_base = _Vp();
2941 reverse_view() = default;
2944 reverse_view(_Vp __r)
2945 : _M_base(std::move(__r))
2949 base() const& requires copy_constructible<_Vp>
2954 { return std::move(_M_base); }
2956 constexpr reverse_iterator<iterator_t<_Vp>>
2959 if constexpr (_S_needs_cached_begin)
2960 if (_M_cached_begin._M_has_value())
2961 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
2963 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
2964 if constexpr (_S_needs_cached_begin)
2965 _M_cached_begin._M_set(_M_base, __it);
2966 return std::make_reverse_iterator(std::move(__it));
2970 begin() requires common_range<_Vp>
2971 { return std::make_reverse_iterator(ranges::end(_M_base)); }
2974 begin() const requires common_range<const _Vp>
2975 { return std::make_reverse_iterator(ranges::end(_M_base)); }
2977 constexpr reverse_iterator<iterator_t<_Vp>>
2979 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
2982 end() const requires common_range<const _Vp>
2983 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
2986 size() requires sized_range<_Vp>
2987 { return ranges::size(_M_base); }
2990 size() const requires sized_range<const _Vp>
2991 { return ranges::size(_M_base); }
2994 template<typename _Range>
2995 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
2997 template<typename _Tp>
2998 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
2999 = enable_borrowed_range<_Tp>;
3006 inline constexpr bool __is_reversible_subrange = false;
3008 template<typename _Iter, subrange_kind _Kind>
3009 inline constexpr bool
3010 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3011 reverse_iterator<_Iter>,
3015 inline constexpr bool __is_reverse_view = false;
3017 template<typename _Vp>
3018 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3021 inline constexpr __adaptor::_RangeAdaptorClosure reverse
3022 = [] <viewable_range _Range> (_Range&& __r)
3024 using _Tp = remove_cvref_t<_Range>;
3025 if constexpr (__detail::__is_reverse_view<_Tp>)
3026 return std::forward<_Range>(__r).base();
3027 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3029 using _Iter = decltype(ranges::begin(__r).base());
3030 if constexpr (sized_range<_Tp>)
3031 return subrange<_Iter, _Iter, subrange_kind::sized>
3032 (__r.end().base(), __r.begin().base(), __r.size());
3034 return subrange<_Iter, _Iter, subrange_kind::unsized>
3035 (__r.end().base(), __r.begin().base());
3038 return reverse_view{std::forward<_Range>(__r)};
3040 } // namespace views
3044 template<typename _Tp, size_t _Nm>
3045 concept __has_tuple_element = requires(_Tp __t)
3047 typename tuple_size<_Tp>::type;
3048 requires _Nm < tuple_size_v<_Tp>;
3049 typename tuple_element_t<_Nm, _Tp>;
3050 { std::get<_Nm>(__t) }
3051 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3055 template<input_range _Vp, size_t _Nm>
3057 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3058 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3060 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3063 elements_view() = default;
3066 elements_view(_Vp base)
3067 : _M_base(std::move(base))
3071 base() const& requires copy_constructible<_Vp>
3076 { return std::move(_M_base); }
3079 begin() requires (!__detail::__simple_view<_Vp>)
3080 { return _Iterator<false>(ranges::begin(_M_base)); }
3083 begin() const requires range<const _Vp>
3084 { return _Iterator<true>(ranges::begin(_M_base)); }
3087 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3088 { return _Sentinel<false>{ranges::end(_M_base)}; }
3091 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3092 { return _Iterator<false>{ranges::end(_M_base)}; }
3095 end() const requires range<const _Vp>
3096 { return _Sentinel<true>{ranges::end(_M_base)}; }
3099 end() const requires common_range<const _Vp>
3100 { return _Iterator<true>{ranges::end(_M_base)}; }
3103 size() requires sized_range<_Vp>
3104 { return ranges::size(_M_base); }
3107 size() const requires sized_range<const _Vp>
3108 { return ranges::size(_M_base); }
3111 template<bool _Const>
3114 template<bool _Const>
3117 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3119 iterator_t<_Base> _M_current = iterator_t<_Base>();
3121 friend _Iterator<!_Const>;
3124 using iterator_category
3125 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3127 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3128 using difference_type = range_difference_t<_Base>;
3130 _Iterator() = default;
3133 _Iterator(iterator_t<_Base> current)
3134 : _M_current(std::move(current))
3138 _Iterator(_Iterator<!_Const> i)
3139 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3140 : _M_current(std::move(i._M_current))
3143 constexpr iterator_t<_Base>
3145 requires copyable<iterator_t<_Base>>
3146 { return _M_current; }
3148 constexpr iterator_t<_Base>
3150 { return std::move(_M_current); }
3152 constexpr decltype(auto)
3154 { return std::get<_Nm>(*_M_current); }
3156 constexpr _Iterator&
3164 operator++(int) requires (!forward_range<_Base>)
3168 operator++(int) requires forward_range<_Base>
3175 constexpr _Iterator&
3176 operator--() requires bidirectional_range<_Base>
3183 operator--(int) requires bidirectional_range<_Base>
3190 constexpr _Iterator&
3191 operator+=(difference_type __n)
3192 requires random_access_range<_Base>
3198 constexpr _Iterator&
3199 operator-=(difference_type __n)
3200 requires random_access_range<_Base>
3206 constexpr decltype(auto)
3207 operator[](difference_type __n) const
3208 requires random_access_range<_Base>
3209 { return std::get<_Nm>(*(_M_current + __n)); }
3211 friend constexpr bool
3212 operator==(const _Iterator& __x, const _Iterator& __y)
3213 requires equality_comparable<iterator_t<_Base>>
3214 { return __x._M_current == __y._M_current; }
3216 friend constexpr bool
3217 operator<(const _Iterator& __x, const _Iterator& __y)
3218 requires random_access_range<_Base>
3219 { return __x._M_current < __y._M_current; }
3221 friend constexpr bool
3222 operator>(const _Iterator& __x, const _Iterator& __y)
3223 requires random_access_range<_Base>
3224 { return __y._M_current < __x._M_current; }
3226 friend constexpr bool
3227 operator<=(const _Iterator& __x, const _Iterator& __y)
3228 requires random_access_range<_Base>
3229 { return !(__y._M_current > __x._M_current); }
3231 friend constexpr bool
3232 operator>=(const _Iterator& __x, const _Iterator& __y)
3233 requires random_access_range<_Base>
3234 { return !(__x._M_current > __y._M_current); }
3236 #ifdef __cpp_lib_three_way_comparison
3237 friend constexpr auto
3238 operator<=>(const _Iterator& __x, const _Iterator& __y)
3239 requires random_access_range<_Base>
3240 && three_way_comparable<iterator_t<_Base>>
3241 { return __x._M_current <=> __y._M_current; }
3244 friend constexpr _Iterator
3245 operator+(const _Iterator& __x, difference_type __y)
3246 requires random_access_range<_Base>
3247 { return _Iterator{__x} += __y; }
3249 friend constexpr _Iterator
3250 operator+(difference_type __x, const _Iterator& __y)
3251 requires random_access_range<_Base>
3252 { return __y + __x; }
3254 friend constexpr _Iterator
3255 operator-(const _Iterator& __x, difference_type __y)
3256 requires random_access_range<_Base>
3257 { return _Iterator{__x} -= __y; }
3259 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3260 // 3483. transform_view::iterator's difference is overconstrained
3261 friend constexpr difference_type
3262 operator-(const _Iterator& __x, const _Iterator& __y)
3263 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3264 { return __x._M_current - __y._M_current; }
3266 friend _Sentinel<_Const>;
3269 template<bool _Const>
3274 _M_equal(const _Iterator<_Const>& __x) const
3275 { return __x._M_current == _M_end; }
3277 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3278 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3281 _Sentinel() = default;
3284 _Sentinel(sentinel_t<_Base> __end)
3285 : _M_end(std::move(__end))
3289 _Sentinel(_Sentinel<!_Const> __other)
3291 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3292 : _M_end(std::move(__other._M_end))
3295 constexpr sentinel_t<_Base>
3299 template<bool _Const2>
3300 requires sentinel_for<sentinel_t<_Base>,
3301 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3302 friend constexpr bool
3303 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3304 { return __y._M_equal(__x); }
3306 template<bool _Const2,
3307 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3308 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3309 friend constexpr range_difference_t<_Base2>
3310 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3311 { return __x._M_current - __y._M_end; }
3313 template<bool _Const2,
3314 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3315 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3316 friend constexpr range_difference_t<_Base>
3317 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3318 { return __x._M_end - __y._M_current; }
3320 friend _Sentinel<!_Const>;
3323 _Vp _M_base = _Vp();
3326 template<typename _Tp, size_t _Nm>
3327 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3328 = enable_borrowed_range<_Tp>;
3330 template<typename _Range>
3331 using keys_view = elements_view<views::all_t<_Range>, 0>;
3333 template<typename _Range>
3334 using values_view = elements_view<views::all_t<_Range>, 1>;
3338 template<size_t _Nm>
3339 inline constexpr __adaptor::_RangeAdaptorClosure elements
3340 = [] <viewable_range _Range> (_Range&& __r)
3342 using _El = elements_view<views::all_t<_Range>, _Nm>;
3343 return _El{std::forward<_Range>(__r)};
3346 inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
3347 inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
3348 } // namespace views
3350 } // namespace ranges
3352 namespace views = ranges::views;
3354 _GLIBCXX_END_NAMESPACE_VERSION
3356 #endif // library concepts
3358 #endif /* _GLIBCXX_RANGES */