libstdc++
ranges
1// <ranges> -*- C++ -*-
2
3// Copyright (C) 2019-2021 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file include/ranges
26 * This is a Standard C++ Library header.
27 * @ingroup concepts
28 */
29
30#ifndef _GLIBCXX_RANGES
31#define _GLIBCXX_RANGES 1
32
33#if __cplusplus > 201703L
34
35#pragma GCC system_header
36
37#include <concepts>
38
39#if __cpp_lib_concepts
40
41#include <compare>
42#include <initializer_list>
43#include <iterator>
44#include <optional>
45#include <tuple>
46#include <bits/ranges_util.h>
47#include <bits/refwrap.h>
48
49/**
50 * @defgroup ranges Ranges
51 *
52 * Components for dealing with ranges of elements.
53 */
54
55namespace std _GLIBCXX_VISIBILITY(default)
56{
57_GLIBCXX_BEGIN_NAMESPACE_VERSION
58namespace ranges
59{
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>
64
65 // [view.interface] View interface
66 // [range.subrange] Sub-ranges
67 // Defined in <bits/ranges_util.h>
68
69 // C++20 24.6 [range.factories] Range factories
70
71 /// A view that contains no elements.
72 template<typename _Tp> requires is_object_v<_Tp>
73 class empty_view
74 : public view_interface<empty_view<_Tp>>
75 {
76 public:
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; }
82 };
83
84 template<typename _Tp>
85 inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true;
86
87 namespace __detail
88 {
89 template<typename _Tp>
90 concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>;
91
92 template<__boxable _Tp>
93 struct __box : std::optional<_Tp>
94 {
96
97 constexpr
98 __box()
99 noexcept(is_nothrow_default_constructible_v<_Tp>)
100 requires default_initializable<_Tp>
101 : std::optional<_Tp>{std::in_place}
102 { }
103
104 __box(const __box&) = default;
105 __box(__box&&) = default;
106
108
109 // _GLIBCXX_RESOLVE_LIB_DEFECTS
110 // 3477. Simplify constraints for semiregular-box
111 __box&
112 operator=(const __box& __that)
113 noexcept(is_nothrow_copy_constructible_v<_Tp>)
114 requires (!copyable<_Tp>)
115 {
116 if ((bool)__that)
117 this->emplace(*__that);
118 else
119 this->reset();
120 return *this;
121 }
122
123 __box&
124 operator=(__box&& __that)
125 noexcept(is_nothrow_move_constructible_v<_Tp>)
126 requires (!movable<_Tp>)
127 {
128 if ((bool)__that)
129 this->emplace(std::move(*__that));
130 else
131 this->reset();
132 return *this;
133 }
134 };
135
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>
141 struct __box<_Tp>
142 {
143 private:
144 [[no_unique_address]] _Tp _M_value = _Tp();
145
146 public:
147 __box() = default;
148
149 constexpr explicit
150 __box(const _Tp& __t)
151 noexcept(is_nothrow_copy_constructible_v<_Tp>)
152 : _M_value{__t}
153 { }
154
155 constexpr explicit
156 __box(_Tp&& __t)
157 noexcept(is_nothrow_move_constructible_v<_Tp>)
158 : _M_value{std::move(__t)}
159 { }
160
161 template<typename... _Args>
162 requires constructible_from<_Tp, _Args...>
163 constexpr explicit
164 __box(in_place_t, _Args&&... __args)
165 noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
166 : _M_value(std::forward<_Args>(__args)...)
167 { }
168
169 constexpr bool
170 has_value() const noexcept
171 { return true; };
172
173 constexpr _Tp&
174 operator*() noexcept
175 { return _M_value; }
176
177 constexpr const _Tp&
178 operator*() const noexcept
179 { return _M_value; }
180
181 constexpr _Tp*
182 operator->() noexcept
183 { return std::__addressof(_M_value); }
184
185 constexpr const _Tp*
186 operator->() const noexcept
187 { return std::__addressof(_M_value); }
188 };
189 } // namespace __detail
190
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>>
194 {
195 public:
196 single_view() = default;
197
198 constexpr explicit
199 single_view(const _Tp& __t)
200 : _M_value(__t)
201 { }
202
203 constexpr explicit
204 single_view(_Tp&& __t)
205 : _M_value(std::move(__t))
206 { }
207
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...>
212 constexpr explicit
213 single_view(in_place_t, _Args&&... __args)
214 : _M_value{in_place, std::forward<_Args>(__args)...}
215 { }
216
217 constexpr _Tp*
218 begin() noexcept
219 { return data(); }
220
221 constexpr const _Tp*
222 begin() const noexcept
223 { return data(); }
224
225 constexpr _Tp*
226 end() noexcept
227 { return data() + 1; }
228
229 constexpr const _Tp*
230 end() const noexcept
231 { return data() + 1; }
232
233 static constexpr size_t
234 size() noexcept
235 { return 1; }
236
237 constexpr _Tp*
238 data() noexcept
239 { return _M_value.operator->(); }
240
241 constexpr const _Tp*
242 data() const noexcept
243 { return _M_value.operator->(); }
244
245 private:
246 [[no_unique_address]] __detail::__box<_Tp> _M_value;
247 };
248
249 template<typename _Tp>
250 single_view(_Tp) -> single_view<_Tp>;
251
252 namespace __detail
253 {
254 template<typename _Wp>
255 constexpr auto __to_signed_like(_Wp __w) noexcept
256 {
257 if constexpr (!integral<_Wp>)
258 return iter_difference_t<_Wp>();
259 else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
260 return iter_difference_t<_Wp>(__w);
261 else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
262 return ptrdiff_t(__w);
263 else if constexpr (sizeof(long long) > sizeof(_Wp))
264 return (long long)(__w);
265#ifdef __SIZEOF_INT128__
266 else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
267 return __int128(__w);
268#endif
269 else
270 return __max_diff_type(__w);
271 }
272
273 template<typename _Wp>
274 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
275
276 template<typename _It>
277 concept __decrementable = incrementable<_It>
278 && requires(_It __i)
279 {
280 { --__i } -> same_as<_It&>;
281 { __i-- } -> same_as<_It>;
282 };
283
284 template<typename _It>
285 concept __advanceable = __decrementable<_It> && totally_ordered<_It>
286 && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
287 {
288 { __i += __n } -> same_as<_It&>;
289 { __i -= __n } -> same_as<_It&>;
290 _It(__j + __n);
291 _It(__n + __j);
292 _It(__j - __n);
293 { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
294 };
295
296 template<typename _Winc>
297 struct __iota_view_iter_cat
298 { };
299
300 template<incrementable _Winc>
301 struct __iota_view_iter_cat<_Winc>
302 { using iterator_category = input_iterator_tag; };
303 } // namespace __detail
304
305 template<weakly_incrementable _Winc,
306 semiregular _Bound = unreachable_sentinel_t>
307 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
308 && semiregular<_Winc>
309 class iota_view : public view_interface<iota_view<_Winc, _Bound>>
310 {
311 private:
312 struct _Sentinel;
313
314 struct _Iterator : __detail::__iota_view_iter_cat<_Winc>
315 {
316 private:
317 static auto
318 _S_iter_concept()
319 {
320 using namespace __detail;
321 if constexpr (__advanceable<_Winc>)
322 return random_access_iterator_tag{};
323 else if constexpr (__decrementable<_Winc>)
324 return bidirectional_iterator_tag{};
325 else if constexpr (incrementable<_Winc>)
326 return forward_iterator_tag{};
327 else
328 return input_iterator_tag{};
329 }
330
331 public:
332 using iterator_concept = decltype(_S_iter_concept());
333 // iterator_category defined in __iota_view_iter_cat
334 using value_type = _Winc;
335 using difference_type = __detail::__iota_diff_t<_Winc>;
336
337 _Iterator() = default;
338
339 constexpr explicit
340 _Iterator(_Winc __value)
341 : _M_value(__value) { }
342
343 constexpr _Winc
344 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
345 { return _M_value; }
346
347 constexpr _Iterator&
348 operator++()
349 {
350 ++_M_value;
351 return *this;
352 }
353
354 constexpr void
355 operator++(int)
356 { ++*this; }
357
358 constexpr _Iterator
359 operator++(int) requires incrementable<_Winc>
360 {
361 auto __tmp = *this;
362 ++*this;
363 return __tmp;
364 }
365
366 constexpr _Iterator&
367 operator--() requires __detail::__decrementable<_Winc>
368 {
369 --_M_value;
370 return *this;
371 }
372
373 constexpr _Iterator
374 operator--(int) requires __detail::__decrementable<_Winc>
375 {
376 auto __tmp = *this;
377 --*this;
378 return __tmp;
379 }
380
381 constexpr _Iterator&
382 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
383 {
384 using __detail::__is_integer_like;
385 using __detail::__is_signed_integer_like;
386 if constexpr (__is_integer_like<_Winc>
387 && !__is_signed_integer_like<_Winc>)
388 {
389 if (__n >= difference_type(0))
390 _M_value += static_cast<_Winc>(__n);
391 else
392 _M_value -= static_cast<_Winc>(-__n);
393 }
394 else
395 _M_value += __n;
396 return *this;
397 }
398
399 constexpr _Iterator&
400 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
401 {
402 using __detail::__is_integer_like;
403 using __detail::__is_signed_integer_like;
404 if constexpr (__is_integer_like<_Winc>
405 && !__is_signed_integer_like<_Winc>)
406 {
407 if (__n >= difference_type(0))
408 _M_value -= static_cast<_Winc>(__n);
409 else
410 _M_value += static_cast<_Winc>(-__n);
411 }
412 else
413 _M_value -= __n;
414 return *this;
415 }
416
417 constexpr _Winc
418 operator[](difference_type __n) const
419 requires __detail::__advanceable<_Winc>
420 { return _Winc(_M_value + __n); }
421
422 friend constexpr bool
423 operator==(const _Iterator& __x, const _Iterator& __y)
424 requires equality_comparable<_Winc>
425 { return __x._M_value == __y._M_value; }
426
427 friend constexpr bool
428 operator<(const _Iterator& __x, const _Iterator& __y)
429 requires totally_ordered<_Winc>
430 { return __x._M_value < __y._M_value; }
431
432 friend constexpr bool
433 operator>(const _Iterator& __x, const _Iterator& __y)
434 requires totally_ordered<_Winc>
435 { return __y < __x; }
436
437 friend constexpr bool
438 operator<=(const _Iterator& __x, const _Iterator& __y)
439 requires totally_ordered<_Winc>
440 { return !(__y < __x); }
441
442 friend constexpr bool
443 operator>=(const _Iterator& __x, const _Iterator& __y)
444 requires totally_ordered<_Winc>
445 { return !(__x < __y); }
446
447#ifdef __cpp_lib_three_way_comparison
448 friend constexpr auto
449 operator<=>(const _Iterator& __x, const _Iterator& __y)
450 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
451 { return __x._M_value <=> __y._M_value; }
452#endif
453
454 friend constexpr _Iterator
455 operator+(_Iterator __i, difference_type __n)
456 requires __detail::__advanceable<_Winc>
457 { return __i += __n; }
458
459 friend constexpr _Iterator
460 operator+(difference_type __n, _Iterator __i)
461 requires __detail::__advanceable<_Winc>
462 { return __i += __n; }
463
464 friend constexpr _Iterator
465 operator-(_Iterator __i, difference_type __n)
466 requires __detail::__advanceable<_Winc>
467 { return __i -= __n; }
468
469 friend constexpr difference_type
470 operator-(const _Iterator& __x, const _Iterator& __y)
471 requires __detail::__advanceable<_Winc>
472 {
473 using __detail::__is_integer_like;
474 using __detail::__is_signed_integer_like;
475 using _Dt = difference_type;
476 if constexpr (__is_integer_like<_Winc>)
477 {
478 if constexpr (__is_signed_integer_like<_Winc>)
479 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
480 else
481 return (__y._M_value > __x._M_value)
482 ? _Dt(-_Dt(__y._M_value - __x._M_value))
483 : _Dt(__x._M_value - __y._M_value);
484 }
485 else
486 return __x._M_value - __y._M_value;
487 }
488
489 private:
490 _Winc _M_value = _Winc();
491
492 friend _Sentinel;
493 };
494
495 struct _Sentinel
496 {
497 private:
498 constexpr bool
499 _M_equal(const _Iterator& __x) const
500 { return __x._M_value == _M_bound; }
501
502 constexpr auto
503 _M_distance_from(const _Iterator& __x) const
504 { return _M_bound - __x._M_value; }
505
506 _Bound _M_bound = _Bound();
507
508 public:
509 _Sentinel() = default;
510
511 constexpr explicit
512 _Sentinel(_Bound __bound)
513 : _M_bound(__bound) { }
514
515 friend constexpr bool
516 operator==(const _Iterator& __x, const _Sentinel& __y)
517 { return __y._M_equal(__x); }
518
519 friend constexpr iter_difference_t<_Winc>
520 operator-(const _Iterator& __x, const _Sentinel& __y)
521 requires sized_sentinel_for<_Bound, _Winc>
522 { return -__y._M_distance_from(__x); }
523
524 friend constexpr iter_difference_t<_Winc>
525 operator-(const _Sentinel& __x, const _Iterator& __y)
526 requires sized_sentinel_for<_Bound, _Winc>
527 { return __x._M_distance_from(__y); }
528 };
529
530 _Winc _M_value = _Winc();
531 [[no_unique_address]] _Bound _M_bound = _Bound();
532
533 public:
534 iota_view() = default;
535
536 constexpr explicit
537 iota_view(_Winc __value)
538 : _M_value(__value)
539 { }
540
541 constexpr
542 iota_view(type_identity_t<_Winc> __value,
543 type_identity_t<_Bound> __bound)
544 : _M_value(__value), _M_bound(__bound)
545 {
546 if constexpr (totally_ordered_with<_Winc, _Bound>)
547 __glibcxx_assert( bool(__value <= __bound) );
548 }
549
550 constexpr _Iterator
551 begin() const { return _Iterator{_M_value}; }
552
553 constexpr auto
554 end() const
555 {
556 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
557 return unreachable_sentinel;
558 else
559 return _Sentinel{_M_bound};
560 }
561
562 constexpr _Iterator
563 end() const requires same_as<_Winc, _Bound>
564 { return _Iterator{_M_bound}; }
565
566 constexpr auto
567 size() const
568 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
569 || (integral<_Winc> && integral<_Bound>)
570 || sized_sentinel_for<_Bound, _Winc>
571 {
572 using __detail::__is_integer_like;
573 using __detail::__to_unsigned_like;
574 if constexpr (integral<_Winc> && integral<_Bound>)
575 {
576 using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>;
577 return _Up(_M_bound) - _Up(_M_value);
578 }
579 else if constexpr (__is_integer_like<_Winc>)
580 return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
581 else
582 return __to_unsigned_like(_M_bound - _M_value);
583 }
584 };
585
586 template<typename _Winc, typename _Bound>
587 requires (!__detail::__is_integer_like<_Winc>
588 || !__detail::__is_integer_like<_Bound>
589 || (__detail::__is_signed_integer_like<_Winc>
590 == __detail::__is_signed_integer_like<_Bound>))
591 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
592
593 template<weakly_incrementable _Winc, semiregular _Bound>
594 inline constexpr bool
595 enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
596
597namespace views
598{
599 template<typename _Tp>
600 inline constexpr empty_view<_Tp> empty{};
601
602 struct _Single
603 {
604 template<typename _Tp>
605 constexpr auto
606 operator()(_Tp&& __e) const
607 { return single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)); }
608 };
609
610 inline constexpr _Single single{};
611
612 struct _Iota
613 {
614 template<typename _Tp>
615 constexpr auto
616 operator()(_Tp&& __e) const
617 { return iota_view(std::forward<_Tp>(__e)); }
618
619 template<typename _Tp, typename _Up>
620 constexpr auto
621 operator()(_Tp&& __e, _Up&& __f) const
622 { return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); }
623 };
624
625 inline constexpr _Iota iota{};
626} // namespace views
627
628 namespace __detail
629 {
630 template<typename _Val, typename _CharT, typename _Traits>
631 concept __stream_extractable
632 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
633 } // namespace __detail
634
635 template<movable _Val, typename _CharT,
636 typename _Traits = char_traits<_CharT>>
637 requires default_initializable<_Val>
638 && __detail::__stream_extractable<_Val, _CharT, _Traits>
639 class basic_istream_view
640 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
641 {
642 public:
643 basic_istream_view() = default;
644
645 constexpr explicit
646 basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
647 : _M_stream(std::__addressof(__stream))
648 { }
649
650 constexpr auto
651 begin()
652 {
653 if (_M_stream != nullptr)
654 *_M_stream >> _M_object;
655 return _Iterator{this};
656 }
657
658 constexpr default_sentinel_t
659 end() const noexcept
660 { return default_sentinel; }
661
662 private:
663 basic_istream<_CharT, _Traits>* _M_stream = nullptr;
664 _Val _M_object = _Val();
665
666 struct _Iterator
667 {
668 public:
669 using iterator_concept = input_iterator_tag;
670 using difference_type = ptrdiff_t;
671 using value_type = _Val;
672
673 _Iterator() = default;
674
675 constexpr explicit
676 _Iterator(basic_istream_view* __parent) noexcept
677 : _M_parent(__parent)
678 { }
679
680 _Iterator(const _Iterator&) = delete;
681 _Iterator(_Iterator&&) = default;
682 _Iterator& operator=(const _Iterator&) = delete;
683 _Iterator& operator=(_Iterator&&) = default;
684
685 _Iterator&
686 operator++()
687 {
688 __glibcxx_assert(_M_parent->_M_stream != nullptr);
689 *_M_parent->_M_stream >> _M_parent->_M_object;
690 return *this;
691 }
692
693 void
694 operator++(int)
695 { ++*this; }
696
697 _Val&
698 operator*() const
699 {
700 __glibcxx_assert(_M_parent->_M_stream != nullptr);
701 return _M_parent->_M_object;
702 }
703
704 friend bool
705 operator==(const _Iterator& __x, default_sentinel_t)
706 { return __x._M_at_end(); }
707
708 private:
709 basic_istream_view* _M_parent = nullptr;
710
711 bool
712 _M_at_end() const
713 { return _M_parent == nullptr || !*_M_parent->_M_stream; }
714 };
715
716 friend _Iterator;
717 };
718
719 template<typename _Val, typename _CharT, typename _Traits>
720 basic_istream_view<_Val, _CharT, _Traits>
721 istream_view(basic_istream<_CharT, _Traits>& __s)
722 { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
723
724 // C++20 24.7 [range.adaptors] Range adaptors
725
726namespace __detail
727{
728 struct _Empty { };
729
730 // Alias for a type that is conditionally present
731 // (and is an empty type otherwise).
732 // Data members using this alias should use [[no_unique_address]] so that
733 // they take no space when not needed.
734 template<bool _Present, typename _Tp>
735 using __maybe_present_t = conditional_t<_Present, _Tp, _Empty>;
736
737 // Alias for a type that is conditionally const.
738 template<bool _Const, typename _Tp>
739 using __maybe_const_t = conditional_t<_Const, const _Tp, _Tp>;
740
741} // namespace __detail
742
743namespace views::__adaptor
744{
745 // True if the range adaptor _Adaptor can be applied with _Args.
746 template<typename _Adaptor, typename... _Args>
747 concept __adaptor_invocable
748 = requires { std::declval<_Adaptor>()(declval<_Args>()...); };
749
750 // True if the range adaptor non-closure _Adaptor can be partially applied
751 // with _Args.
752 template<typename _Adaptor, typename... _Args>
753 concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
754 && (sizeof...(_Args) == _Adaptor::_S_arity - 1)
755 && (constructible_from<decay_t<_Args>, _Args> && ...);
756
757 template<typename _Adaptor, typename... _Args>
758 struct _Partial;
759
760 template<typename _Lhs, typename _Rhs>
761 struct _Pipe;
762
763 // The base class of every range adaptor closure.
764 //
765 // The derived class should define the optional static data member
766 // _S_has_simple_call_op to true if the behavior of this adaptor is
767 // independent of the constness/value category of the adaptor object.
768 struct _RangeAdaptorClosure
769 {
770 // range | adaptor is equivalent to adaptor(range).
771 template<typename _Self, typename _Range>
772 requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
773 && __adaptor_invocable<_Self, _Range>
774 friend constexpr auto
775 operator|(_Range&& __r, _Self&& __self)
776 { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
777
778 // Compose the adaptors __lhs and __rhs into a pipeline, returning
779 // another range adaptor closure object.
780 template<typename _Lhs, typename _Rhs>
781 requires derived_from<_Lhs, _RangeAdaptorClosure>
782 && derived_from<_Rhs, _RangeAdaptorClosure>
783 friend constexpr auto
784 operator|(_Lhs __lhs, _Rhs __rhs)
785 { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
786 };
787
788 // The base class of every range adaptor non-closure.
789 //
790 // The static data member _Derived::_S_arity must contain the total number of
791 // arguments that the adaptor takes, and the class _Derived must introduce
792 // _RangeAdaptor::operator() into the class scope via a using-declaration.
793 //
794 // The optional static data member _Derived::_S_has_simple_extra_args should
795 // be defined to true if the behavior of this adaptor is independent of the
796 // constness/value category of the extra arguments. This data member could
797 // also be defined as a variable template parameterized by the types of the
798 // extra arguments.
799 template<typename _Derived>
800 struct _RangeAdaptor
801 {
802 // Partially apply the arguments __args to the range adaptor _Derived,
803 // returning a range adaptor closure object.
804 template<typename... _Args>
805 requires __adaptor_partial_app_viable<_Derived, _Args...>
806 constexpr auto
807 operator()(_Args&&... __args) const
808 {
809 return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
810 }
811 };
812
813 // True if the range adaptor closure _Adaptor has a simple operator(), i.e.
814 // one that's not overloaded according to constness or value category of the
815 // _Adaptor object.
816 template<typename _Adaptor>
817 concept __closure_has_simple_call_op = _Adaptor::_S_has_simple_call_op;
818
819 // True if the behavior of the range adaptor non-closure _Adaptor is
820 // independent of the value category of its extra arguments _Args.
821 template<typename _Adaptor, typename... _Args>
822 concept __adaptor_has_simple_extra_args = _Adaptor::_S_has_simple_extra_args
823 || _Adaptor::template _S_has_simple_extra_args<_Args...>;
824
825 // A range adaptor closure that represents partial application of
826 // the range adaptor _Adaptor with arguments _Args.
827 template<typename _Adaptor, typename... _Args>
828 struct _Partial : _RangeAdaptorClosure
829 {
830 tuple<_Args...> _M_args;
831
832 constexpr
833 _Partial(_Args... __args)
834 : _M_args(std::move(__args)...)
835 { }
836
837 // Invoke _Adaptor with arguments __r, _M_args... according to the
838 // value category of this _Partial object.
839 template<typename _Range>
840 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
841 constexpr auto
842 operator()(_Range&& __r) const &
843 {
844 auto __forwarder = [&__r] (const auto&... __args) {
845 return _Adaptor{}(std::forward<_Range>(__r), __args...);
846 };
847 return std::apply(__forwarder, _M_args);
848 }
849
850 template<typename _Range>
851 requires __adaptor_invocable<_Adaptor, _Range, _Args...>
852 constexpr auto
853 operator()(_Range&& __r) &&
854 {
855 auto __forwarder = [&__r] (auto&... __args) {
856 return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...);
857 };
858 return std::apply(__forwarder, _M_args);
859 }
860
861 template<typename _Range>
862 constexpr auto
863 operator()(_Range&& __r) const && = delete;
864 };
865
866 // A lightweight specialization of the above primary template for
867 // the common case where _Adaptor accepts a single extra argument.
868 template<typename _Adaptor, typename _Arg>
869 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
870 {
871 _Arg _M_arg;
872
873 constexpr
874 _Partial(_Arg __arg)
875 : _M_arg(std::move(__arg))
876 { }
877
878 template<typename _Range>
879 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
880 constexpr auto
881 operator()(_Range&& __r) const &
882 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
883
884 template<typename _Range>
885 requires __adaptor_invocable<_Adaptor, _Range, _Arg>
886 constexpr auto
887 operator()(_Range&& __r) &&
888 { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
889
890 template<typename _Range>
891 constexpr auto
892 operator()(_Range&& __r) const && = delete;
893 };
894
895 // Partial specialization of the primary template for the case where the extra
896 // arguments of the adaptor can always be safely and efficiently forwarded by
897 // const reference. This lets us get away with a single operator() overload,
898 // which makes overload resolution failure diagnostics more concise.
899 template<typename _Adaptor, typename... _Args>
900 requires __adaptor_has_simple_extra_args<_Adaptor, _Args...>
901 && (is_trivially_copyable_v<_Args> && ...)
902 struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure
903 {
904 tuple<_Args...> _M_args;
905
906 constexpr
907 _Partial(_Args... __args)
908 : _M_args(std::move(__args)...)
909 { }
910
911 // Invoke _Adaptor with arguments __r, const _M_args&... regardless
912 // of the value category of this _Partial object.
913 template<typename _Range>
914 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
915 constexpr auto
916 operator()(_Range&& __r) const
917 {
918 auto __forwarder = [&__r] (const auto&... __args) {
919 return _Adaptor{}(std::forward<_Range>(__r), __args...);
920 };
921 return std::apply(__forwarder, _M_args);
922 }
923
924 static constexpr bool _S_has_simple_call_op = true;
925 };
926
927 // A lightweight specialization of the above template for the common case
928 // where _Adaptor accepts a single extra argument.
929 template<typename _Adaptor, typename _Arg>
930 requires __adaptor_has_simple_extra_args<_Adaptor, _Arg>
931 && is_trivially_copyable_v<_Arg>
932 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
933 {
934 _Arg _M_arg;
935
936 constexpr
937 _Partial(_Arg __arg)
938 : _M_arg(std::move(__arg))
939 { }
940
941 template<typename _Range>
942 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
943 constexpr auto
944 operator()(_Range&& __r) const
945 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
946
947 static constexpr bool _S_has_simple_call_op = true;
948 };
949
950 template<typename _Lhs, typename _Rhs, typename _Range>
951 concept __pipe_invocable
952 = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); };
953
954 // A range adaptor closure that represents composition of the range
955 // adaptor closures _Lhs and _Rhs.
956 template<typename _Lhs, typename _Rhs>
957 struct _Pipe : _RangeAdaptorClosure
958 {
959 [[no_unique_address]] _Lhs _M_lhs;
960 [[no_unique_address]] _Rhs _M_rhs;
961
962 constexpr
963 _Pipe(_Lhs __lhs, _Rhs __rhs)
964 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
965 { }
966
967 // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this
968 // range adaptor closure object.
969 template<typename _Range>
970 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
971 constexpr auto
972 operator()(_Range&& __r) const &
973 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
974
975 template<typename _Range>
976 requires __pipe_invocable<_Lhs, _Rhs, _Range>
977 constexpr auto
978 operator()(_Range&& __r) &&
979 { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); }
980
981 template<typename _Range>
982 constexpr auto
983 operator()(_Range&& __r) const && = delete;
984 };
985
986 // A partial specialization of the above primary template for the case where
987 // both adaptor operands have a simple operator(). This in turn lets us
988 // implement composition using a single simple operator(), which makes
989 // overload resolution failure diagnostics more concise.
990 template<typename _Lhs, typename _Rhs>
991 requires __closure_has_simple_call_op<_Lhs>
992 && __closure_has_simple_call_op<_Rhs>
993 struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure
994 {
995 [[no_unique_address]] _Lhs _M_lhs;
996 [[no_unique_address]] _Rhs _M_rhs;
997
998 constexpr
999 _Pipe(_Lhs __lhs, _Rhs __rhs)
1000 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
1001 { }
1002
1003 template<typename _Range>
1004 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1005 constexpr auto
1006 operator()(_Range&& __r) const
1007 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1008
1009 static constexpr bool _S_has_simple_call_op = true;
1010 };
1011} // namespace views::__adaptor
1012
1013 template<range _Range> requires is_object_v<_Range>
1014 class ref_view : public view_interface<ref_view<_Range>>
1015 {
1016 private:
1017 _Range* _M_r = nullptr;
1018
1019 static void _S_fun(_Range&); // not defined
1020 static void _S_fun(_Range&&) = delete;
1021
1022 public:
1023 constexpr
1024 ref_view() noexcept = default;
1025
1026 template<__detail::__not_same_as<ref_view> _Tp>
1027 requires convertible_to<_Tp, _Range&>
1028 && requires { _S_fun(declval<_Tp>()); }
1029 constexpr
1030 ref_view(_Tp&& __t)
1031 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
1032 { }
1033
1034 constexpr _Range&
1035 base() const
1036 { return *_M_r; }
1037
1038 constexpr iterator_t<_Range>
1039 begin() const
1040 { return ranges::begin(*_M_r); }
1041
1042 constexpr sentinel_t<_Range>
1043 end() const
1044 { return ranges::end(*_M_r); }
1045
1046 constexpr bool
1047 empty() const requires requires { ranges::empty(*_M_r); }
1048 { return ranges::empty(*_M_r); }
1049
1050 constexpr auto
1051 size() const requires sized_range<_Range>
1052 { return ranges::size(*_M_r); }
1053
1054 constexpr auto
1055 data() const requires contiguous_range<_Range>
1056 { return ranges::data(*_M_r); }
1057 };
1058
1059 template<typename _Range>
1060 ref_view(_Range&) -> ref_view<_Range>;
1061
1062 template<typename _Tp>
1063 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
1064
1065 namespace views
1066 {
1067 namespace __detail
1068 {
1069 template<typename _Range>
1070 concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
1071
1072 template<typename _Range>
1073 concept __can_subrange = requires { subrange{std::declval<_Range>()}; };
1074 } // namespace __detail
1075
1076 struct _All : __adaptor::_RangeAdaptorClosure
1077 {
1078 template<viewable_range _Range>
1079 requires view<decay_t<_Range>>
1080 || __detail::__can_ref_view<_Range>
1081 || __detail::__can_subrange<_Range>
1082 constexpr auto
1083 operator()(_Range&& __r) const
1084 {
1085 if constexpr (view<decay_t<_Range>>)
1086 return std::forward<_Range>(__r);
1087 else if constexpr (__detail::__can_ref_view<_Range>)
1088 return ref_view{std::forward<_Range>(__r)};
1089 else
1090 return subrange{std::forward<_Range>(__r)};
1091 }
1092
1093 static constexpr bool _S_has_simple_call_op = true;
1094 };
1095
1096 inline constexpr _All all;
1097
1098 template<viewable_range _Range>
1099 using all_t = decltype(all(std::declval<_Range>()));
1100 } // namespace views
1101
1102 namespace __detail
1103 {
1104 template<typename _Tp>
1105 struct __non_propagating_cache
1106 {
1107 // When _Tp is not an object type (e.g. is a reference type), we make
1108 // __non_propagating_cache<_Tp> empty rather than ill-formed so that
1109 // users can easily conditionally declare data members with this type
1110 // (such as join_view::_M_inner).
1111 };
1112
1113 template<typename _Tp>
1114 requires is_object_v<_Tp>
1115 struct __non_propagating_cache<_Tp> : protected _Optional_base<_Tp>
1116 {
1117 __non_propagating_cache() = default;
1118
1119 constexpr
1120 __non_propagating_cache(const __non_propagating_cache&) noexcept
1121 { }
1122
1123 constexpr
1124 __non_propagating_cache(__non_propagating_cache&& __other) noexcept
1125 { __other._M_reset(); }
1126
1127 constexpr __non_propagating_cache&
1128 operator=(const __non_propagating_cache& __other) noexcept
1129 {
1130 if (std::__addressof(__other) != this)
1131 this->_M_reset();
1132 return *this;
1133 }
1134
1135 constexpr __non_propagating_cache&
1136 operator=(__non_propagating_cache&& __other) noexcept
1137 {
1138 this->_M_reset();
1139 __other._M_reset();
1140 return *this;
1141 }
1142
1143 constexpr _Tp&
1144 operator*() noexcept
1145 { return this->_M_get(); }
1146
1147 constexpr const _Tp&
1148 operator*() const noexcept
1149 { return this->_M_get(); }
1150
1151 template<typename _Iter>
1152 _Tp&
1153 _M_emplace_deref(const _Iter& __i)
1154 {
1155 this->_M_reset();
1156 // Using _Optional_base::_M_construct to initialize from '*__i'
1157 // would incur an extra move due to the indirection, so we instead
1158 // use placement new directly.
1159 ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i);
1160 this->_M_payload._M_engaged = true;
1161 return this->_M_get();
1162 }
1163 };
1164
1165 template<range _Range>
1166 struct _CachedPosition
1167 {
1168 constexpr bool
1169 _M_has_value() const
1170 { return false; }
1171
1172 constexpr iterator_t<_Range>
1173 _M_get(const _Range&) const
1174 {
1175 __glibcxx_assert(false);
1176 return {};
1177 }
1178
1179 constexpr void
1180 _M_set(const _Range&, const iterator_t<_Range>&) const
1181 { }
1182 };
1183
1184 template<forward_range _Range>
1185 struct _CachedPosition<_Range>
1186 : protected __non_propagating_cache<iterator_t<_Range>>
1187 {
1188 constexpr bool
1189 _M_has_value() const
1190 { return this->_M_is_engaged(); }
1191
1192 constexpr iterator_t<_Range>
1193 _M_get(const _Range&) const
1194 {
1195 __glibcxx_assert(_M_has_value());
1196 return **this;
1197 }
1198
1199 constexpr void
1200 _M_set(const _Range&, const iterator_t<_Range>& __it)
1201 {
1202 __glibcxx_assert(!_M_has_value());
1203 std::construct_at(std::__addressof(this->_M_payload._M_payload),
1204 in_place, __it);
1205 this->_M_payload._M_engaged = true;
1206 }
1207 };
1208
1209 template<random_access_range _Range>
1210 requires (sizeof(range_difference_t<_Range>)
1211 <= sizeof(iterator_t<_Range>))
1212 struct _CachedPosition<_Range>
1213 {
1214 private:
1215 range_difference_t<_Range> _M_offset = -1;
1216
1217 public:
1218 _CachedPosition() = default;
1219
1220 constexpr
1221 _CachedPosition(const _CachedPosition&) = default;
1222
1223 constexpr
1224 _CachedPosition(_CachedPosition&& __other) noexcept
1225 { *this = std::move(__other); }
1226
1227 constexpr _CachedPosition&
1228 operator=(const _CachedPosition&) = default;
1229
1230 constexpr _CachedPosition&
1231 operator=(_CachedPosition&& __other) noexcept
1232 {
1233 // Propagate the cached offset, but invalidate the source.
1234 _M_offset = __other._M_offset;
1235 __other._M_offset = -1;
1236 return *this;
1237 }
1238
1239 constexpr bool
1240 _M_has_value() const
1241 { return _M_offset >= 0; }
1242
1243 constexpr iterator_t<_Range>
1244 _M_get(_Range& __r) const
1245 {
1246 __glibcxx_assert(_M_has_value());
1247 return ranges::begin(__r) + _M_offset;
1248 }
1249
1250 constexpr void
1251 _M_set(_Range& __r, const iterator_t<_Range>& __it)
1252 {
1253 __glibcxx_assert(!_M_has_value());
1254 _M_offset = __it - ranges::begin(__r);
1255 }
1256 };
1257 } // namespace __detail
1258
1259 namespace __detail
1260 {
1261 template<typename _Base>
1262 struct __filter_view_iter_cat
1263 { };
1264
1265 template<forward_range _Base>
1266 struct __filter_view_iter_cat<_Base>
1267 {
1268 private:
1269 static auto
1270 _S_iter_cat()
1271 {
1272 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1273 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1274 return bidirectional_iterator_tag{};
1275 else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1276 return forward_iterator_tag{};
1277 else
1278 return _Cat{};
1279 }
1280 public:
1281 using iterator_category = decltype(_S_iter_cat());
1282 };
1283 } // namespace __detail
1284
1285 template<input_range _Vp,
1286 indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1287 requires view<_Vp> && is_object_v<_Pred>
1288 class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1289 {
1290 private:
1291 struct _Sentinel;
1292
1293 struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
1294 {
1295 private:
1296 static constexpr auto
1297 _S_iter_concept()
1298 {
1299 if constexpr (bidirectional_range<_Vp>)
1300 return bidirectional_iterator_tag{};
1301 else if constexpr (forward_range<_Vp>)
1302 return forward_iterator_tag{};
1303 else
1304 return input_iterator_tag{};
1305 }
1306
1307 friend filter_view;
1308
1309 using _Vp_iter = iterator_t<_Vp>;
1310
1311 _Vp_iter _M_current = _Vp_iter();
1312 filter_view* _M_parent = nullptr;
1313
1314 public:
1315 using iterator_concept = decltype(_S_iter_concept());
1316 // iterator_category defined in __filter_view_iter_cat
1317 using value_type = range_value_t<_Vp>;
1318 using difference_type = range_difference_t<_Vp>;
1319
1320 _Iterator() = default;
1321
1322 constexpr
1323 _Iterator(filter_view* __parent, _Vp_iter __current)
1324 : _M_current(std::move(__current)),
1325 _M_parent(__parent)
1326 { }
1327
1328 constexpr const _Vp_iter&
1329 base() const & noexcept
1330 { return _M_current; }
1331
1332 constexpr _Vp_iter
1333 base() &&
1334 { return std::move(_M_current); }
1335
1336 constexpr range_reference_t<_Vp>
1337 operator*() const
1338 { return *_M_current; }
1339
1340 constexpr _Vp_iter
1341 operator->() const
1342 requires __detail::__has_arrow<_Vp_iter>
1343 && copyable<_Vp_iter>
1344 { return _M_current; }
1345
1346 constexpr _Iterator&
1347 operator++()
1348 {
1349 _M_current = ranges::find_if(std::move(++_M_current),
1350 ranges::end(_M_parent->_M_base),
1351 std::ref(*_M_parent->_M_pred));
1352 return *this;
1353 }
1354
1355 constexpr void
1356 operator++(int)
1357 { ++*this; }
1358
1359 constexpr _Iterator
1360 operator++(int) requires forward_range<_Vp>
1361 {
1362 auto __tmp = *this;
1363 ++*this;
1364 return __tmp;
1365 }
1366
1367 constexpr _Iterator&
1368 operator--() requires bidirectional_range<_Vp>
1369 {
1370 do
1371 --_M_current;
1372 while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1373 return *this;
1374 }
1375
1376 constexpr _Iterator
1377 operator--(int) requires bidirectional_range<_Vp>
1378 {
1379 auto __tmp = *this;
1380 --*this;
1381 return __tmp;
1382 }
1383
1384 friend constexpr bool
1385 operator==(const _Iterator& __x, const _Iterator& __y)
1386 requires equality_comparable<_Vp_iter>
1387 { return __x._M_current == __y._M_current; }
1388
1389 friend constexpr range_rvalue_reference_t<_Vp>
1390 iter_move(const _Iterator& __i)
1391 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1392 { return ranges::iter_move(__i._M_current); }
1393
1394 friend constexpr void
1395 iter_swap(const _Iterator& __x, const _Iterator& __y)
1396 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1397 requires indirectly_swappable<_Vp_iter>
1398 { ranges::iter_swap(__x._M_current, __y._M_current); }
1399 };
1400
1401 struct _Sentinel
1402 {
1403 private:
1404 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1405
1406 constexpr bool
1407 __equal(const _Iterator& __i) const
1408 { return __i._M_current == _M_end; }
1409
1410 public:
1411 _Sentinel() = default;
1412
1413 constexpr explicit
1414 _Sentinel(filter_view* __parent)
1415 : _M_end(ranges::end(__parent->_M_base))
1416 { }
1417
1418 constexpr sentinel_t<_Vp>
1419 base() const
1420 { return _M_end; }
1421
1422 friend constexpr bool
1423 operator==(const _Iterator& __x, const _Sentinel& __y)
1424 { return __y.__equal(__x); }
1425 };
1426
1427 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
1428 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1429 _Vp _M_base = _Vp();
1430
1431 public:
1432 filter_view() = default;
1433
1434 constexpr
1435 filter_view(_Vp __base, _Pred __pred)
1436 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
1437 { }
1438
1439 constexpr _Vp
1440 base() const& requires copy_constructible<_Vp>
1441 { return _M_base; }
1442
1443 constexpr _Vp
1444 base() &&
1445 { return std::move(_M_base); }
1446
1447 constexpr const _Pred&
1448 pred() const
1449 { return *_M_pred; }
1450
1451 constexpr _Iterator
1452 begin()
1453 {
1454 if (_M_cached_begin._M_has_value())
1455 return {this, _M_cached_begin._M_get(_M_base)};
1456
1457 __glibcxx_assert(_M_pred.has_value());
1458 auto __it = ranges::find_if(ranges::begin(_M_base),
1459 ranges::end(_M_base),
1460 std::ref(*_M_pred));
1461 _M_cached_begin._M_set(_M_base, __it);
1462 return {this, std::move(__it)};
1463 }
1464
1465 constexpr auto
1466 end()
1467 {
1468 if constexpr (common_range<_Vp>)
1469 return _Iterator{this, ranges::end(_M_base)};
1470 else
1471 return _Sentinel{this};
1472 }
1473 };
1474
1475 template<typename _Range, typename _Pred>
1476 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1477
1478 namespace views
1479 {
1480 namespace __detail
1481 {
1482 template<typename _Range, typename _Pred>
1483 concept __can_filter_view
1484 = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); };
1485 } // namespace __detail
1486
1487 struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1488 {
1489 template<viewable_range _Range, typename _Pred>
1490 requires __detail::__can_filter_view<_Range, _Pred>
1491 constexpr auto
1492 operator()(_Range&& __r, _Pred&& __p) const
1493 {
1494 return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
1495 }
1496
1497 using _RangeAdaptor<_Filter>::operator();
1498 static constexpr int _S_arity = 2;
1499 static constexpr bool _S_has_simple_extra_args = true;
1500 };
1501
1502 inline constexpr _Filter filter;
1503 } // namespace views
1504
1505 template<input_range _Vp, copy_constructible _Fp>
1506 requires view<_Vp> && is_object_v<_Fp>
1507 && regular_invocable<_Fp&, range_reference_t<_Vp>>
1508 && std::__detail::__can_reference<invoke_result_t<_Fp&,
1509 range_reference_t<_Vp>>>
1510 class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1511 {
1512 private:
1513 template<bool _Const>
1514 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1515
1516 template<bool _Const>
1517 struct __iter_cat
1518 { };
1519
1520 template<bool _Const>
1521 requires forward_range<_Base<_Const>>
1522 struct __iter_cat<_Const>
1523 {
1524 private:
1525 static auto
1526 _S_iter_cat()
1527 {
1528 using _Base = transform_view::_Base<_Const>;
1529 using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1530 if constexpr (is_lvalue_reference_v<_Res>)
1531 {
1532 using _Cat
1533 = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1534 if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1535 return random_access_iterator_tag{};
1536 else
1537 return _Cat{};
1538 }
1539 else
1540 return input_iterator_tag{};
1541 }
1542 public:
1543 using iterator_category = decltype(_S_iter_cat());
1544 };
1545
1546 template<bool _Const>
1547 struct _Sentinel;
1548
1549 template<bool _Const>
1550 struct _Iterator : __iter_cat<_Const>
1551 {
1552 private:
1553 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1554 using _Base = transform_view::_Base<_Const>;
1555
1556 static auto
1557 _S_iter_concept()
1558 {
1559 if constexpr (random_access_range<_Base>)
1560 return random_access_iterator_tag{};
1561 else if constexpr (bidirectional_range<_Base>)
1562 return bidirectional_iterator_tag{};
1563 else if constexpr (forward_range<_Base>)
1564 return forward_iterator_tag{};
1565 else
1566 return input_iterator_tag{};
1567 }
1568
1569 using _Base_iter = iterator_t<_Base>;
1570
1571 _Base_iter _M_current = _Base_iter();
1572 _Parent* _M_parent = nullptr;
1573
1574 public:
1575 using iterator_concept = decltype(_S_iter_concept());
1576 // iterator_category defined in __transform_view_iter_cat
1577 using value_type
1578 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1579 using difference_type = range_difference_t<_Base>;
1580
1581 _Iterator() = default;
1582
1583 constexpr
1584 _Iterator(_Parent* __parent, _Base_iter __current)
1585 : _M_current(std::move(__current)),
1586 _M_parent(__parent)
1587 { }
1588
1589 constexpr
1590 _Iterator(_Iterator<!_Const> __i)
1591 requires _Const
1592 && convertible_to<iterator_t<_Vp>, _Base_iter>
1593 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1594 { }
1595
1596 constexpr const _Base_iter&
1597 base() const & noexcept
1598 { return _M_current; }
1599
1600 constexpr _Base_iter
1601 base() &&
1602 { return std::move(_M_current); }
1603
1604 constexpr decltype(auto)
1605 operator*() const
1606 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1607 { return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1608
1609 constexpr _Iterator&
1610 operator++()
1611 {
1612 ++_M_current;
1613 return *this;
1614 }
1615
1616 constexpr void
1617 operator++(int)
1618 { ++_M_current; }
1619
1620 constexpr _Iterator
1621 operator++(int) requires forward_range<_Base>
1622 {
1623 auto __tmp = *this;
1624 ++*this;
1625 return __tmp;
1626 }
1627
1628 constexpr _Iterator&
1629 operator--() requires bidirectional_range<_Base>
1630 {
1631 --_M_current;
1632 return *this;
1633 }
1634
1635 constexpr _Iterator
1636 operator--(int) requires bidirectional_range<_Base>
1637 {
1638 auto __tmp = *this;
1639 --*this;
1640 return __tmp;
1641 }
1642
1643 constexpr _Iterator&
1644 operator+=(difference_type __n) requires random_access_range<_Base>
1645 {
1646 _M_current += __n;
1647 return *this;
1648 }
1649
1650 constexpr _Iterator&
1651 operator-=(difference_type __n) requires random_access_range<_Base>
1652 {
1653 _M_current -= __n;
1654 return *this;
1655 }
1656
1657 constexpr decltype(auto)
1658 operator[](difference_type __n) const
1659 requires random_access_range<_Base>
1660 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1661
1662 friend constexpr bool
1663 operator==(const _Iterator& __x, const _Iterator& __y)
1664 requires equality_comparable<_Base_iter>
1665 { return __x._M_current == __y._M_current; }
1666
1667 friend constexpr bool
1668 operator<(const _Iterator& __x, const _Iterator& __y)
1669 requires random_access_range<_Base>
1670 { return __x._M_current < __y._M_current; }
1671
1672 friend constexpr bool
1673 operator>(const _Iterator& __x, const _Iterator& __y)
1674 requires random_access_range<_Base>
1675 { return __y < __x; }
1676
1677 friend constexpr bool
1678 operator<=(const _Iterator& __x, const _Iterator& __y)
1679 requires random_access_range<_Base>
1680 { return !(__y < __x); }
1681
1682 friend constexpr bool
1683 operator>=(const _Iterator& __x, const _Iterator& __y)
1684 requires random_access_range<_Base>
1685 { return !(__x < __y); }
1686
1687#ifdef __cpp_lib_three_way_comparison
1688 friend constexpr auto
1689 operator<=>(const _Iterator& __x, const _Iterator& __y)
1690 requires random_access_range<_Base>
1691 && three_way_comparable<_Base_iter>
1692 { return __x._M_current <=> __y._M_current; }
1693#endif
1694
1695 friend constexpr _Iterator
1696 operator+(_Iterator __i, difference_type __n)
1697 requires random_access_range<_Base>
1698 { return {__i._M_parent, __i._M_current + __n}; }
1699
1700 friend constexpr _Iterator
1701 operator+(difference_type __n, _Iterator __i)
1702 requires random_access_range<_Base>
1703 { return {__i._M_parent, __i._M_current + __n}; }
1704
1705 friend constexpr _Iterator
1706 operator-(_Iterator __i, difference_type __n)
1707 requires random_access_range<_Base>
1708 { return {__i._M_parent, __i._M_current - __n}; }
1709
1710 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1711 // 3483. transform_view::iterator's difference is overconstrained
1712 friend constexpr difference_type
1713 operator-(const _Iterator& __x, const _Iterator& __y)
1714 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1715 { return __x._M_current - __y._M_current; }
1716
1717 friend constexpr decltype(auto)
1718 iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1719 {
1720 if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1721 return std::move(*__i);
1722 else
1723 return *__i;
1724 }
1725
1726 friend _Iterator<!_Const>;
1727 template<bool> friend struct _Sentinel;
1728 };
1729
1730 template<bool _Const>
1731 struct _Sentinel
1732 {
1733 private:
1734 using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1735 using _Base = transform_view::_Base<_Const>;
1736
1737 template<bool _Const2>
1738 constexpr auto
1739 __distance_from(const _Iterator<_Const2>& __i) const
1740 { return _M_end - __i._M_current; }
1741
1742 template<bool _Const2>
1743 constexpr bool
1744 __equal(const _Iterator<_Const2>& __i) const
1745 { return __i._M_current == _M_end; }
1746
1747 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1748
1749 public:
1750 _Sentinel() = default;
1751
1752 constexpr explicit
1753 _Sentinel(sentinel_t<_Base> __end)
1754 : _M_end(__end)
1755 { }
1756
1757 constexpr
1758 _Sentinel(_Sentinel<!_Const> __i)
1759 requires _Const
1760 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1761 : _M_end(std::move(__i._M_end))
1762 { }
1763
1764 constexpr sentinel_t<_Base>
1765 base() const
1766 { return _M_end; }
1767
1768 template<bool _Const2>
1769 requires sentinel_for<sentinel_t<_Base>,
1770 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1771 friend constexpr bool
1772 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1773 { return __y.__equal(__x); }
1774
1775 template<bool _Const2,
1776 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1777 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1778 friend constexpr range_difference_t<_Base2>
1779 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1780 { return -__y.__distance_from(__x); }
1781
1782 template<bool _Const2,
1783 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1784 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1785 friend constexpr range_difference_t<_Base2>
1786 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1787 { return __y.__distance_from(__x); }
1788
1789 friend _Sentinel<!_Const>;
1790 };
1791
1792 [[no_unique_address]] __detail::__box<_Fp> _M_fun;
1793 _Vp _M_base = _Vp();
1794
1795 public:
1796 transform_view() = default;
1797
1798 constexpr
1799 transform_view(_Vp __base, _Fp __fun)
1800 : _M_fun(std::move(__fun)), _M_base(std::move(__base))
1801 { }
1802
1803 constexpr _Vp
1804 base() const& requires copy_constructible<_Vp>
1805 { return _M_base ; }
1806
1807 constexpr _Vp
1808 base() &&
1809 { return std::move(_M_base); }
1810
1811 constexpr _Iterator<false>
1812 begin()
1813 { return _Iterator<false>{this, ranges::begin(_M_base)}; }
1814
1815 constexpr _Iterator<true>
1816 begin() const
1817 requires range<const _Vp>
1818 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1819 { return _Iterator<true>{this, ranges::begin(_M_base)}; }
1820
1821 constexpr _Sentinel<false>
1822 end()
1823 { return _Sentinel<false>{ranges::end(_M_base)}; }
1824
1825 constexpr _Iterator<false>
1826 end() requires common_range<_Vp>
1827 { return _Iterator<false>{this, ranges::end(_M_base)}; }
1828
1829 constexpr _Sentinel<true>
1830 end() const
1831 requires range<const _Vp>
1832 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1833 { return _Sentinel<true>{ranges::end(_M_base)}; }
1834
1835 constexpr _Iterator<true>
1836 end() const
1837 requires common_range<const _Vp>
1838 && regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1839 { return _Iterator<true>{this, ranges::end(_M_base)}; }
1840
1841 constexpr auto
1842 size() requires sized_range<_Vp>
1843 { return ranges::size(_M_base); }
1844
1845 constexpr auto
1846 size() const requires sized_range<const _Vp>
1847 { return ranges::size(_M_base); }
1848 };
1849
1850 template<typename _Range, typename _Fp>
1851 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1852
1853 namespace views
1854 {
1855 namespace __detail
1856 {
1857 template<typename _Range, typename _Fp>
1858 concept __can_transform_view
1859 = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); };
1860 } // namespace __detail
1861
1862 struct _Transform : __adaptor::_RangeAdaptor<_Transform>
1863 {
1864 template<viewable_range _Range, typename _Fp>
1865 requires __detail::__can_transform_view<_Range, _Fp>
1866 constexpr auto
1867 operator()(_Range&& __r, _Fp&& __f) const
1868 {
1869 return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f));
1870 }
1871
1872 using _RangeAdaptor<_Transform>::operator();
1873 static constexpr int _S_arity = 2;
1874 static constexpr bool _S_has_simple_extra_args = true;
1875 };
1876
1877 inline constexpr _Transform transform;
1878 } // namespace views
1879
1880 template<view _Vp>
1881 class take_view : public view_interface<take_view<_Vp>>
1882 {
1883 private:
1884 template<bool _Const>
1885 using _CI = counted_iterator<
1886 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1887
1888 template<bool _Const>
1889 struct _Sentinel
1890 {
1891 private:
1892 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1893 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1894
1895 public:
1896 _Sentinel() = default;
1897
1898 constexpr explicit
1899 _Sentinel(sentinel_t<_Base> __end)
1900 : _M_end(__end)
1901 { }
1902
1903 constexpr
1904 _Sentinel(_Sentinel<!_Const> __s)
1905 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1906 : _M_end(std::move(__s._M_end))
1907 { }
1908
1909 constexpr sentinel_t<_Base>
1910 base() const
1911 { return _M_end; }
1912
1913 friend constexpr bool
1914 operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1915 { return __y.count() == 0 || __y.base() == __x._M_end; }
1916
1917 template<bool _OtherConst = !_Const,
1918 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1919 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1920 friend constexpr bool
1921 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1922 { return __y.count() == 0 || __y.base() == __x._M_end; }
1923
1924 friend _Sentinel<!_Const>;
1925 };
1926
1927 range_difference_t<_Vp> _M_count = 0;
1928 _Vp _M_base = _Vp();
1929
1930 public:
1931 take_view() = default;
1932
1933 constexpr
1934 take_view(_Vp base, range_difference_t<_Vp> __count)
1935 : _M_count(std::move(__count)), _M_base(std::move(base))
1936 { }
1937
1938 constexpr _Vp
1939 base() const& requires copy_constructible<_Vp>
1940 { return _M_base; }
1941
1942 constexpr _Vp
1943 base() &&
1944 { return std::move(_M_base); }
1945
1946 constexpr auto
1947 begin() requires (!__detail::__simple_view<_Vp>)
1948 {
1949 if constexpr (sized_range<_Vp>)
1950 {
1951 if constexpr (random_access_range<_Vp>)
1952 return ranges::begin(_M_base);
1953 else
1954 {
1955 auto __sz = size();
1956 return counted_iterator(ranges::begin(_M_base), __sz);
1957 }
1958 }
1959 else
1960 return counted_iterator(ranges::begin(_M_base), _M_count);
1961 }
1962
1963 constexpr auto
1964 begin() const requires range<const _Vp>
1965 {
1966 if constexpr (sized_range<const _Vp>)
1967 {
1968 if constexpr (random_access_range<const _Vp>)
1969 return ranges::begin(_M_base);
1970 else
1971 {
1972 auto __sz = size();
1973 return counted_iterator(ranges::begin(_M_base), __sz);
1974 }
1975 }
1976 else
1977 return counted_iterator(ranges::begin(_M_base), _M_count);
1978 }
1979
1980 constexpr auto
1981 end() requires (!__detail::__simple_view<_Vp>)
1982 {
1983 if constexpr (sized_range<_Vp>)
1984 {
1985 if constexpr (random_access_range<_Vp>)
1986 return ranges::begin(_M_base) + size();
1987 else
1988 return default_sentinel;
1989 }
1990 else
1991 return _Sentinel<false>{ranges::end(_M_base)};
1992 }
1993
1994 constexpr auto
1995 end() const requires range<const _Vp>
1996 {
1997 if constexpr (sized_range<const _Vp>)
1998 {
1999 if constexpr (random_access_range<const _Vp>)
2000 return ranges::begin(_M_base) + size();
2001 else
2002 return default_sentinel;
2003 }
2004 else
2005 return _Sentinel<true>{ranges::end(_M_base)};
2006 }
2007
2008 constexpr auto
2009 size() requires sized_range<_Vp>
2010 {
2011 auto __n = ranges::size(_M_base);
2012 return std::min(__n, static_cast<decltype(__n)>(_M_count));
2013 }
2014
2015 constexpr auto
2016 size() const requires sized_range<const _Vp>
2017 {
2018 auto __n = ranges::size(_M_base);
2019 return std::min(__n, static_cast<decltype(__n)>(_M_count));
2020 }
2021 };
2022
2023 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2024 // 3447. Deduction guides for take_view and drop_view have different
2025 // constraints
2026 template<typename _Range>
2027 take_view(_Range&&, range_difference_t<_Range>)
2028 -> take_view<views::all_t<_Range>>;
2029
2030 template<typename _Tp>
2031 inline constexpr bool enable_borrowed_range<take_view<_Tp>>
2032 = enable_borrowed_range<_Tp>;
2033
2034 namespace views
2035 {
2036 namespace __detail
2037 {
2038 template<typename _Range, typename _Tp>
2039 concept __can_take_view
2040 = requires { take_view(std::declval<_Range>(), std::declval<_Tp>()); };
2041 } // namespace __detail
2042
2043 struct _Take : __adaptor::_RangeAdaptor<_Take>
2044 {
2045 template<viewable_range _Range, typename _Tp>
2046 requires __detail::__can_take_view<_Range, _Tp>
2047 constexpr auto
2048 operator()(_Range&& __r, _Tp&& __n) const
2049 {
2050 return take_view(std::forward<_Range>(__r), std::forward<_Tp>(__n));
2051 }
2052
2053 using _RangeAdaptor<_Take>::operator();
2054 static constexpr int _S_arity = 2;
2055 // The count argument of views::take is not always simple -- it can be
2056 // e.g. a move-only class that's implicitly convertible to the difference
2057 // type. But an integer-like count argument is surely simple.
2058 template<typename _Tp>
2059 static constexpr bool _S_has_simple_extra_args
2060 = ranges::__detail::__is_integer_like<_Tp>;
2061 };
2062
2063 inline constexpr _Take take;
2064 } // namespace views
2065
2066 template<view _Vp, typename _Pred>
2067 requires input_range<_Vp> && is_object_v<_Pred>
2068 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2069 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2070 {
2071 template<bool _Const>
2072 struct _Sentinel
2073 {
2074 private:
2075 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2076
2077 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2078 const _Pred* _M_pred = nullptr;
2079
2080 public:
2081 _Sentinel() = default;
2082
2083 constexpr explicit
2084 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2085 : _M_end(__end), _M_pred(__pred)
2086 { }
2087
2088 constexpr
2089 _Sentinel(_Sentinel<!_Const> __s)
2090 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2091 : _M_end(__s._M_end), _M_pred(__s._M_pred)
2092 { }
2093
2094 constexpr sentinel_t<_Base>
2095 base() const { return _M_end; }
2096
2097 friend constexpr bool
2098 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2099 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2100
2101 template<bool _OtherConst = !_Const,
2102 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2103 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2104 friend constexpr bool
2105 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
2106 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2107
2108 friend _Sentinel<!_Const>;
2109 };
2110
2111 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2112 _Vp _M_base = _Vp();
2113
2114 public:
2115 take_while_view() = default;
2116
2117 constexpr
2118 take_while_view(_Vp base, _Pred __pred)
2119 : _M_pred(std::move(__pred)), _M_base(std::move(base))
2120 { }
2121
2122 constexpr _Vp
2123 base() const& requires copy_constructible<_Vp>
2124 { return _M_base; }
2125
2126 constexpr _Vp
2127 base() &&
2128 { return std::move(_M_base); }
2129
2130 constexpr const _Pred&
2131 pred() const
2132 { return *_M_pred; }
2133
2134 constexpr auto
2135 begin() requires (!__detail::__simple_view<_Vp>)
2136 { return ranges::begin(_M_base); }
2137
2138 constexpr auto
2139 begin() const requires range<const _Vp>
2140 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2141 { return ranges::begin(_M_base); }
2142
2143 constexpr auto
2144 end() requires (!__detail::__simple_view<_Vp>)
2145 { return _Sentinel<false>(ranges::end(_M_base),
2146 std::__addressof(*_M_pred)); }
2147
2148 constexpr auto
2149 end() const requires range<const _Vp>
2150 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2151 { return _Sentinel<true>(ranges::end(_M_base),
2152 std::__addressof(*_M_pred)); }
2153 };
2154
2155 template<typename _Range, typename _Pred>
2156 take_while_view(_Range&&, _Pred)
2157 -> take_while_view<views::all_t<_Range>, _Pred>;
2158
2159 namespace views
2160 {
2161 namespace __detail
2162 {
2163 template<typename _Range, typename _Pred>
2164 concept __can_take_while_view
2165 = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2166 } // namespace __detail
2167
2168 struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
2169 {
2170 template<viewable_range _Range, typename _Pred>
2171 requires __detail::__can_take_while_view<_Range, _Pred>
2172 constexpr auto
2173 operator()(_Range&& __r, _Pred&& __p) const
2174 {
2175 return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
2176 }
2177
2178 using _RangeAdaptor<_TakeWhile>::operator();
2179 static constexpr int _S_arity = 2;
2180 static constexpr bool _S_has_simple_extra_args = true;
2181 };
2182
2183 inline constexpr _TakeWhile take_while;
2184 } // namespace views
2185
2186 template<view _Vp>
2187 class drop_view : public view_interface<drop_view<_Vp>>
2188 {
2189 private:
2190 range_difference_t<_Vp> _M_count = 0;
2191 _Vp _M_base = _Vp();
2192
2193 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2194 // both random_access_range and sized_range. Otherwise, cache its result.
2195 static constexpr bool _S_needs_cached_begin
2196 = !(random_access_range<const _Vp> && sized_range<const _Vp>);
2197 [[no_unique_address]]
2198 __detail::__maybe_present_t<_S_needs_cached_begin,
2199 __detail::_CachedPosition<_Vp>>
2200 _M_cached_begin;
2201
2202 public:
2203 drop_view() = default;
2204
2205 constexpr
2206 drop_view(_Vp __base, range_difference_t<_Vp> __count)
2207 : _M_count(__count), _M_base(std::move(__base))
2208 { __glibcxx_assert(__count >= 0); }
2209
2210 constexpr _Vp
2211 base() const& requires copy_constructible<_Vp>
2212 { return _M_base; }
2213
2214 constexpr _Vp
2215 base() &&
2216 { return std::move(_M_base); }
2217
2218 // This overload is disabled for simple views with constant-time begin().
2219 constexpr auto
2220 begin()
2221 requires (!(__detail::__simple_view<_Vp>
2222 && random_access_range<const _Vp>
2223 && sized_range<const _Vp>))
2224 {
2225 if constexpr (_S_needs_cached_begin)
2226 if (_M_cached_begin._M_has_value())
2227 return _M_cached_begin._M_get(_M_base);
2228
2229 auto __it = ranges::next(ranges::begin(_M_base),
2230 _M_count, ranges::end(_M_base));
2231 if constexpr (_S_needs_cached_begin)
2232 _M_cached_begin._M_set(_M_base, __it);
2233 return __it;
2234 }
2235
2236 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2237 // 3482. drop_view's const begin should additionally require sized_range
2238 constexpr auto
2239 begin() const
2240 requires random_access_range<const _Vp> && sized_range<const _Vp>
2241 {
2242 return ranges::next(ranges::begin(_M_base), _M_count,
2243 ranges::end(_M_base));
2244 }
2245
2246 constexpr auto
2247 end() requires (!__detail::__simple_view<_Vp>)
2248 { return ranges::end(_M_base); }
2249
2250 constexpr auto
2251 end() const requires range<const _Vp>
2252 { return ranges::end(_M_base); }
2253
2254 constexpr auto
2255 size() requires sized_range<_Vp>
2256 {
2257 const auto __s = ranges::size(_M_base);
2258 const auto __c = static_cast<decltype(__s)>(_M_count);
2259 return __s < __c ? 0 : __s - __c;
2260 }
2261
2262 constexpr auto
2263 size() const requires sized_range<const _Vp>
2264 {
2265 const auto __s = ranges::size(_M_base);
2266 const auto __c = static_cast<decltype(__s)>(_M_count);
2267 return __s < __c ? 0 : __s - __c;
2268 }
2269 };
2270
2271 template<typename _Range>
2272 drop_view(_Range&&, range_difference_t<_Range>)
2273 -> drop_view<views::all_t<_Range>>;
2274
2275 template<typename _Tp>
2276 inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2277 = enable_borrowed_range<_Tp>;
2278
2279 namespace views
2280 {
2281 namespace __detail
2282 {
2283 template<typename _Range, typename _Tp>
2284 concept __can_drop_view
2285 = requires { drop_view(std::declval<_Range>(), std::declval<_Tp>()); };
2286 } // namespace __detail
2287
2288 struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2289 {
2290 template<viewable_range _Range, typename _Tp>
2291 requires __detail::__can_drop_view<_Range, _Tp>
2292 constexpr auto
2293 operator()(_Range&& __r, _Tp&& __n) const
2294 {
2295 return drop_view(std::forward<_Range>(__r), std::forward<_Tp>(__n));
2296 }
2297
2298 using _RangeAdaptor<_Drop>::operator();
2299 static constexpr int _S_arity = 2;
2300 template<typename _Tp>
2301 static constexpr bool _S_has_simple_extra_args
2302 = _Take::_S_has_simple_extra_args<_Tp>;
2303 };
2304
2305 inline constexpr _Drop drop;
2306 } // namespace views
2307
2308 template<view _Vp, typename _Pred>
2309 requires input_range<_Vp> && is_object_v<_Pred>
2310 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2311 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2312 {
2313 private:
2314 [[no_unique_address]] __detail::__box<_Pred> _M_pred;
2315 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2316 _Vp _M_base = _Vp();
2317
2318 public:
2319 drop_while_view() = default;
2320
2321 constexpr
2322 drop_while_view(_Vp __base, _Pred __pred)
2323 : _M_pred(std::move(__pred)), _M_base(std::move(__base))
2324 { }
2325
2326 constexpr _Vp
2327 base() const& requires copy_constructible<_Vp>
2328 { return _M_base; }
2329
2330 constexpr _Vp
2331 base() &&
2332 { return std::move(_M_base); }
2333
2334 constexpr const _Pred&
2335 pred() const
2336 { return *_M_pred; }
2337
2338 constexpr auto
2339 begin()
2340 {
2341 if (_M_cached_begin._M_has_value())
2342 return _M_cached_begin._M_get(_M_base);
2343
2344 __glibcxx_assert(_M_pred.has_value());
2345 auto __it = ranges::find_if_not(ranges::begin(_M_base),
2346 ranges::end(_M_base),
2347 std::cref(*_M_pred));
2348 _M_cached_begin._M_set(_M_base, __it);
2349 return __it;
2350 }
2351
2352 constexpr auto
2353 end()
2354 { return ranges::end(_M_base); }
2355 };
2356
2357 template<typename _Range, typename _Pred>
2358 drop_while_view(_Range&&, _Pred)
2359 -> drop_while_view<views::all_t<_Range>, _Pred>;
2360
2361 template<typename _Tp, typename _Pred>
2362 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2363 = enable_borrowed_range<_Tp>;
2364
2365 namespace views
2366 {
2367 namespace __detail
2368 {
2369 template<typename _Range, typename _Pred>
2370 concept __can_drop_while_view
2371 = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2372 } // namespace __detail
2373
2374 struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2375 {
2376 template<viewable_range _Range, typename _Pred>
2377 requires __detail::__can_drop_while_view<_Range, _Pred>
2378 constexpr auto
2379 operator()(_Range&& __r, _Pred&& __p) const
2380 {
2381 return drop_while_view(std::forward<_Range>(__r),
2382 std::forward<_Pred>(__p));
2383 }
2384
2385 using _RangeAdaptor<_DropWhile>::operator();
2386 static constexpr int _S_arity = 2;
2387 static constexpr bool _S_has_simple_extra_args = true;
2388 };
2389
2390 inline constexpr _DropWhile drop_while;
2391 } // namespace views
2392
2393 template<input_range _Vp>
2394 requires view<_Vp> && input_range<range_reference_t<_Vp>>
2395 class join_view : public view_interface<join_view<_Vp>>
2396 {
2397 private:
2398 using _InnerRange = range_reference_t<_Vp>;
2399
2400 template<bool _Const>
2401 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2402
2403 template<bool _Const>
2404 using _Outer_iter = iterator_t<_Base<_Const>>;
2405
2406 template<bool _Const>
2407 using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
2408
2409 template<bool _Const>
2410 static constexpr bool _S_ref_is_glvalue
2411 = is_reference_v<range_reference_t<_Base<_Const>>>;
2412
2413 template<bool _Const>
2414 struct __iter_cat
2415 { };
2416
2417 template<bool _Const>
2418 requires _S_ref_is_glvalue<_Const>
2419 && forward_range<_Base<_Const>>
2420 && forward_range<range_reference_t<_Base<_Const>>>
2421 struct __iter_cat<_Const>
2422 {
2423 private:
2424 static constexpr auto
2425 _S_iter_cat()
2426 {
2427 using _Outer_iter = join_view::_Outer_iter<_Const>;
2428 using _Inner_iter = join_view::_Inner_iter<_Const>;
2429 using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category;
2430 using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category;
2431 if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
2432 && derived_from<_InnerCat, bidirectional_iterator_tag>)
2433 return bidirectional_iterator_tag{};
2434 else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
2435 && derived_from<_InnerCat, forward_iterator_tag>)
2436 return forward_iterator_tag{};
2437 else
2438 return input_iterator_tag{};
2439 }
2440 public:
2441 using iterator_category = decltype(_S_iter_cat());
2442 };
2443
2444 template<bool _Const>
2445 struct _Sentinel;
2446
2447 template<bool _Const>
2448 struct _Iterator : __iter_cat<_Const>
2449 {
2450 private:
2451 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2452 using _Base = join_view::_Base<_Const>;
2453
2454 static constexpr bool _S_ref_is_glvalue
2455 = join_view::_S_ref_is_glvalue<_Const>;
2456
2457 constexpr void
2458 _M_satisfy()
2459 {
2460 auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& {
2461 if constexpr (_S_ref_is_glvalue)
2462 return *__x;
2463 else
2464 return _M_parent->_M_inner._M_emplace_deref(__x);
2465 };
2466
2467 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2468 {
2469 auto&& __inner = __update_inner(_M_outer);
2470 _M_inner = ranges::begin(__inner);
2471 if (_M_inner != ranges::end(__inner))
2472 return;
2473 }
2474
2475 if constexpr (_S_ref_is_glvalue)
2476 _M_inner = _Inner_iter();
2477 }
2478
2479 static constexpr auto
2480 _S_iter_concept()
2481 {
2482 if constexpr (_S_ref_is_glvalue
2483 && bidirectional_range<_Base>
2484 && bidirectional_range<range_reference_t<_Base>>)
2485 return bidirectional_iterator_tag{};
2486 else if constexpr (_S_ref_is_glvalue
2487 && forward_range<_Base>
2488 && forward_range<range_reference_t<_Base>>)
2489 return forward_iterator_tag{};
2490 else
2491 return input_iterator_tag{};
2492 }
2493
2494 using _Outer_iter = join_view::_Outer_iter<_Const>;
2495 using _Inner_iter = join_view::_Inner_iter<_Const>;
2496
2497 _Outer_iter _M_outer = _Outer_iter();
2498 _Inner_iter _M_inner = _Inner_iter();
2499 _Parent* _M_parent = nullptr;
2500
2501 public:
2502 using iterator_concept = decltype(_S_iter_concept());
2503 // iterator_category defined in __join_view_iter_cat
2504 using value_type = range_value_t<range_reference_t<_Base>>;
2505 using difference_type
2506 = common_type_t<range_difference_t<_Base>,
2507 range_difference_t<range_reference_t<_Base>>>;
2508
2509 _Iterator() = default;
2510
2511 constexpr
2512 _Iterator(_Parent* __parent, _Outer_iter __outer)
2513 : _M_outer(std::move(__outer)),
2514 _M_parent(__parent)
2515 { _M_satisfy(); }
2516
2517 constexpr
2518 _Iterator(_Iterator<!_Const> __i)
2519 requires _Const
2520 && convertible_to<iterator_t<_Vp>, _Outer_iter>
2521 && convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2522 : _M_outer(std::move(__i._M_outer)), _M_inner(std::move(__i._M_inner)),
2523 _M_parent(__i._M_parent)
2524 { }
2525
2526 constexpr decltype(auto)
2527 operator*() const
2528 { return *_M_inner; }
2529
2530 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2531 // 3500. join_view::iterator::operator->() is bogus
2532 constexpr _Inner_iter
2533 operator->() const
2534 requires __detail::__has_arrow<_Inner_iter>
2535 && copyable<_Inner_iter>
2536 { return _M_inner; }
2537
2538 constexpr _Iterator&
2539 operator++()
2540 {
2541 auto&& __inner_range = [this] () -> auto&& {
2542 if constexpr (_S_ref_is_glvalue)
2543 return *_M_outer;
2544 else
2545 return *_M_parent->_M_inner;
2546 }();
2547 if (++_M_inner == ranges::end(__inner_range))
2548 {
2549 ++_M_outer;
2550 _M_satisfy();
2551 }
2552 return *this;
2553 }
2554
2555 constexpr void
2556 operator++(int)
2557 { ++*this; }
2558
2559 constexpr _Iterator
2560 operator++(int)
2561 requires _S_ref_is_glvalue && forward_range<_Base>
2562 && forward_range<range_reference_t<_Base>>
2563 {
2564 auto __tmp = *this;
2565 ++*this;
2566 return __tmp;
2567 }
2568
2569 constexpr _Iterator&
2570 operator--()
2571 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2572 && bidirectional_range<range_reference_t<_Base>>
2573 && common_range<range_reference_t<_Base>>
2574 {
2575 if (_M_outer == ranges::end(_M_parent->_M_base))
2576 _M_inner = ranges::end(*--_M_outer);
2577 while (_M_inner == ranges::begin(*_M_outer))
2578 _M_inner = ranges::end(*--_M_outer);
2579 --_M_inner;
2580 return *this;
2581 }
2582
2583 constexpr _Iterator
2584 operator--(int)
2585 requires _S_ref_is_glvalue && bidirectional_range<_Base>
2586 && bidirectional_range<range_reference_t<_Base>>
2587 && common_range<range_reference_t<_Base>>
2588 {
2589 auto __tmp = *this;
2590 --*this;
2591 return __tmp;
2592 }
2593
2594 friend constexpr bool
2595 operator==(const _Iterator& __x, const _Iterator& __y)
2596 requires _S_ref_is_glvalue
2597 && equality_comparable<_Outer_iter>
2598 && equality_comparable<_Inner_iter>
2599 {
2600 return (__x._M_outer == __y._M_outer
2601 && __x._M_inner == __y._M_inner);
2602 }
2603
2604 friend constexpr decltype(auto)
2605 iter_move(const _Iterator& __i)
2606 noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2607 { return ranges::iter_move(__i._M_inner); }
2608
2609 friend constexpr void
2610 iter_swap(const _Iterator& __x, const _Iterator& __y)
2611 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2612 requires indirectly_swappable<_Inner_iter>
2613 { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2614
2615 friend _Iterator<!_Const>;
2616 template<bool> friend struct _Sentinel;
2617 };
2618
2619 template<bool _Const>
2620 struct _Sentinel
2621 {
2622 private:
2623 using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2624 using _Base = join_view::_Base<_Const>;
2625
2626 template<bool _Const2>
2627 constexpr bool
2628 __equal(const _Iterator<_Const2>& __i) const
2629 { return __i._M_outer == _M_end; }
2630
2631 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2632
2633 public:
2634 _Sentinel() = default;
2635
2636 constexpr explicit
2637 _Sentinel(_Parent* __parent)
2638 : _M_end(ranges::end(__parent->_M_base))
2639 { }
2640
2641 constexpr
2642 _Sentinel(_Sentinel<!_Const> __s)
2643 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2644 : _M_end(std::move(__s._M_end))
2645 { }
2646
2647 template<bool _Const2>
2648 requires sentinel_for<sentinel_t<_Base>,
2649 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2650 friend constexpr bool
2651 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2652 { return __y.__equal(__x); }
2653
2654 friend _Sentinel<!_Const>;
2655 };
2656
2657 [[no_unique_address]]
2658 __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
2659 _Vp _M_base = _Vp();
2660
2661 public:
2662 join_view() = default;
2663
2664 constexpr explicit
2665 join_view(_Vp __base)
2666 : _M_base(std::move(__base))
2667 { }
2668
2669 constexpr _Vp
2670 base() const& requires copy_constructible<_Vp>
2671 { return _M_base; }
2672
2673 constexpr _Vp
2674 base() &&
2675 { return std::move(_M_base); }
2676
2677 constexpr auto
2678 begin()
2679 {
2680 constexpr bool __use_const
2681 = (__detail::__simple_view<_Vp>
2682 && is_reference_v<range_reference_t<_Vp>>);
2683 return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2684 }
2685
2686 constexpr auto
2687 begin() const
2688 requires input_range<const _Vp>
2689 && is_reference_v<range_reference_t<const _Vp>>
2690 {
2691 return _Iterator<true>{this, ranges::begin(_M_base)};
2692 }
2693
2694 constexpr auto
2695 end()
2696 {
2697 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2698 && forward_range<_InnerRange>
2699 && common_range<_Vp> && common_range<_InnerRange>)
2700 return _Iterator<__detail::__simple_view<_Vp>>{this,
2701 ranges::end(_M_base)};
2702 else
2703 return _Sentinel<__detail::__simple_view<_Vp>>{this};
2704 }
2705
2706 constexpr auto
2707 end() const
2708 requires input_range<const _Vp>
2709 && is_reference_v<range_reference_t<const _Vp>>
2710 {
2711 if constexpr (forward_range<const _Vp>
2712 && is_reference_v<range_reference_t<const _Vp>>
2713 && forward_range<range_reference_t<const _Vp>>
2714 && common_range<const _Vp>
2715 && common_range<range_reference_t<const _Vp>>)
2716 return _Iterator<true>{this, ranges::end(_M_base)};
2717 else
2718 return _Sentinel<true>{this};
2719 }
2720 };
2721
2722 template<typename _Range>
2723 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2724
2725 namespace views
2726 {
2727 namespace __detail
2728 {
2729 template<typename _Range>
2730 concept __can_join_view
2731 = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
2732 } // namespace __detail
2733
2734 struct _Join : __adaptor::_RangeAdaptorClosure
2735 {
2736 template<viewable_range _Range>
2737 requires __detail::__can_join_view<_Range>
2738 constexpr auto
2739 operator()(_Range&& __r) const
2740 {
2741 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2742 // 3474. Nesting join_views is broken because of CTAD
2743 return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
2744 }
2745
2746 static constexpr bool _S_has_simple_call_op = true;
2747 };
2748
2749 inline constexpr _Join join;
2750 } // namespace views
2751
2752 namespace __detail
2753 {
2754 template<auto>
2755 struct __require_constant;
2756
2757 template<typename _Range>
2758 concept __tiny_range = sized_range<_Range>
2759 && requires
2762
2763 template<typename _Base>
2764 struct __split_view_outer_iter_cat
2765 { };
2766
2767 template<forward_range _Base>
2768 struct __split_view_outer_iter_cat<_Base>
2769 { using iterator_category = input_iterator_tag; };
2770
2771 template<typename _Base>
2772 struct __split_view_inner_iter_cat
2773 { };
2774
2775 template<forward_range _Base>
2776 struct __split_view_inner_iter_cat<_Base>
2777 {
2778 private:
2779 static constexpr auto
2780 _S_iter_cat()
2781 {
2782 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2783 if constexpr (derived_from<_Cat, forward_iterator_tag>)
2784 return forward_iterator_tag{};
2785 else
2786 return _Cat{};
2787 }
2788 public:
2789 using iterator_category = decltype(_S_iter_cat());
2790 };
2791 }
2792
2793 template<input_range _Vp, forward_range _Pattern>
2794 requires view<_Vp> && view<_Pattern>
2795 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2796 ranges::equal_to>
2797 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2798 class split_view : public view_interface<split_view<_Vp, _Pattern>>
2799 {
2800 private:
2801 template<bool _Const>
2802 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2803
2804 template<bool _Const>
2805 struct _InnerIter;
2806
2807 template<bool _Const>
2808 struct _OuterIter
2809 : __detail::__split_view_outer_iter_cat<_Base<_Const>>
2810 {
2811 private:
2812 using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2813 using _Base = split_view::_Base<_Const>;
2814
2815 constexpr bool
2816 __at_end() const
2817 { return __current() == ranges::end(_M_parent->_M_base); }
2818
2819 // [range.split.outer] p1
2820 // Many of the following specifications refer to the notional member
2821 // current of outer-iterator. current is equivalent to current_ if
2822 // V models forward_range, and parent_->current_ otherwise.
2823 constexpr auto&
2824 __current() noexcept
2825 {
2826 if constexpr (forward_range<_Vp>)
2827 return _M_current;
2828 else
2829 return _M_parent->_M_current;
2830 }
2831
2832 constexpr auto&
2833 __current() const noexcept
2834 {
2835 if constexpr (forward_range<_Vp>)
2836 return _M_current;
2837 else
2838 return _M_parent->_M_current;
2839 }
2840
2841 _Parent* _M_parent = nullptr;
2842
2843 // XXX: _M_current is present only if "V models forward_range"
2844 [[no_unique_address]]
2845 __detail::__maybe_present_t<forward_range<_Vp>,
2846 iterator_t<_Base>> _M_current;
2847
2848 public:
2849 using iterator_concept = conditional_t<forward_range<_Base>,
2850 forward_iterator_tag,
2851 input_iterator_tag>;
2852 // iterator_category defined in __split_view_outer_iter_cat
2853 using difference_type = range_difference_t<_Base>;
2854
2855 struct value_type : view_interface<value_type>
2856 {
2857 private:
2858 _OuterIter _M_i = _OuterIter();
2859
2860 public:
2861 value_type() = default;
2862
2863 constexpr explicit
2864 value_type(_OuterIter __i)
2865 : _M_i(std::move(__i))
2866 { }
2867
2868 constexpr _InnerIter<_Const>
2869 begin() const
2870 { return _InnerIter<_Const>{_M_i}; }
2871
2872 constexpr default_sentinel_t
2873 end() const
2874 { return default_sentinel; }
2875 };
2876
2877 _OuterIter() = default;
2878
2879 constexpr explicit
2880 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2881 : _M_parent(__parent)
2882 { }
2883
2884 constexpr
2885 _OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2886 requires forward_range<_Base>
2887 : _M_parent(__parent),
2888 _M_current(std::move(__current))
2889 { }
2890
2891 constexpr
2892 _OuterIter(_OuterIter<!_Const> __i)
2893 requires _Const
2894 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2895 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2896 { }
2897
2898 constexpr value_type
2899 operator*() const
2900 { return value_type{*this}; }
2901
2902 constexpr _OuterIter&
2903 operator++()
2904 {
2905 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2906 // 3505. split_view::outer-iterator::operator++ misspecified
2907 const auto __end = ranges::end(_M_parent->_M_base);
2908 if (__current() == __end)
2909 return *this;
2910 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2911 if (__pbegin == __pend)
2912 ++__current();
2913 else if constexpr (__detail::__tiny_range<_Pattern>)
2914 {
2915 __current() = ranges::find(std::move(__current()), __end,
2916 *__pbegin);
2917 if (__current() != __end)
2918 ++__current();
2919 }
2920 else
2921 do
2922 {
2923 auto [__b, __p]
2924 = ranges::mismatch(__current(), __end, __pbegin, __pend);
2925 if (__p == __pend)
2926 {
2927 __current() = __b;
2928 break;
2929 }
2930 } while (++__current() != __end);
2931 return *this;
2932 }
2933
2934 constexpr decltype(auto)
2935 operator++(int)
2936 {
2937 if constexpr (forward_range<_Base>)
2938 {
2939 auto __tmp = *this;
2940 ++*this;
2941 return __tmp;
2942 }
2943 else
2944 ++*this;
2945 }
2946
2947 friend constexpr bool
2948 operator==(const _OuterIter& __x, const _OuterIter& __y)
2949 requires forward_range<_Base>
2950 { return __x._M_current == __y._M_current; }
2951
2952 friend constexpr bool
2953 operator==(const _OuterIter& __x, default_sentinel_t)
2954 { return __x.__at_end(); };
2955
2956 friend _OuterIter<!_Const>;
2957 friend _InnerIter<_Const>;
2958 };
2959
2960 template<bool _Const>
2961 struct _InnerIter
2962 : __detail::__split_view_inner_iter_cat<_Base<_Const>>
2963 {
2964 private:
2965 using _Base = split_view::_Base<_Const>;
2966
2967 constexpr bool
2968 __at_end() const
2969 {
2970 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2971 auto __end = ranges::end(_M_i._M_parent->_M_base);
2972 if constexpr (__detail::__tiny_range<_Pattern>)
2973 {
2974 const auto& __cur = _M_i_current();
2975 if (__cur == __end)
2976 return true;
2977 if (__pcur == __pend)
2978 return _M_incremented;
2979 return *__cur == *__pcur;
2980 }
2981 else
2982 {
2983 auto __cur = _M_i_current();
2984 if (__cur == __end)
2985 return true;
2986 if (__pcur == __pend)
2987 return _M_incremented;
2988 do
2989 {
2990 if (*__cur != *__pcur)
2991 return false;
2992 if (++__pcur == __pend)
2993 return true;
2994 } while (++__cur != __end);
2995 return false;
2996 }
2997 }
2998
2999 constexpr auto&
3000 _M_i_current() noexcept
3001 { return _M_i.__current(); }
3002
3003 constexpr auto&
3004 _M_i_current() const noexcept
3005 { return _M_i.__current(); }
3006
3007 _OuterIter<_Const> _M_i = _OuterIter<_Const>();
3008 bool _M_incremented = false;
3009
3010 public:
3011 using iterator_concept
3012 = typename _OuterIter<_Const>::iterator_concept;
3013 // iterator_category defined in __split_view_inner_iter_cat
3014 using value_type = range_value_t<_Base>;
3015 using difference_type = range_difference_t<_Base>;
3016
3017 _InnerIter() = default;
3018
3019 constexpr explicit
3020 _InnerIter(_OuterIter<_Const> __i)
3021 : _M_i(std::move(__i))
3022 { }
3023
3024 constexpr const iterator_t<_Base>&
3025 base() const& noexcept
3026 { return _M_i_current(); }
3027
3028 constexpr iterator_t<_Base>
3029 base() &&
3030 { return std::move(_M_i_current()); }
3031
3032 constexpr decltype(auto)
3033 operator*() const
3034 { return *_M_i_current(); }
3035
3036 constexpr _InnerIter&
3037 operator++()
3038 {
3039 _M_incremented = true;
3040 if constexpr (!forward_range<_Base>)
3041 if constexpr (_Pattern::size() == 0)
3042 return *this;
3043 ++_M_i_current();
3044 return *this;
3045 }
3046
3047 constexpr decltype(auto)
3048 operator++(int)
3049 {
3050 if constexpr (forward_range<_Base>)
3051 {
3052 auto __tmp = *this;
3053 ++*this;
3054 return __tmp;
3055 }
3056 else
3057 ++*this;
3058 }
3059
3060 friend constexpr bool
3061 operator==(const _InnerIter& __x, const _InnerIter& __y)
3062 requires forward_range<_Base>
3063 { return __x._M_i == __y._M_i; }
3064
3065 friend constexpr bool
3066 operator==(const _InnerIter& __x, default_sentinel_t)
3067 { return __x.__at_end(); }
3068
3069 friend constexpr decltype(auto)
3070 iter_move(const _InnerIter& __i)
3071 noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
3072 { return ranges::iter_move(__i._M_i_current()); }
3073
3074 friend constexpr void
3075 iter_swap(const _InnerIter& __x, const _InnerIter& __y)
3076 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
3077 __y._M_i_current())))
3078 requires indirectly_swappable<iterator_t<_Base>>
3079 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
3080 };
3081
3082 _Pattern _M_pattern = _Pattern();
3083 // XXX: _M_current is "present only if !forward_range<V>"
3084 [[no_unique_address]]
3085 __detail::__maybe_present_t<!forward_range<_Vp>,
3086 iterator_t<_Vp>> _M_current;
3087 _Vp _M_base = _Vp();
3088
3089
3090 public:
3091 split_view() = default;
3092
3093 constexpr
3094 split_view(_Vp __base, _Pattern __pattern)
3095 : _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
3096 { }
3097
3098 template<input_range _Range>
3099 requires constructible_from<_Vp, views::all_t<_Range>>
3100 && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3101 constexpr
3102 split_view(_Range&& __r, range_value_t<_Range> __e)
3103 : _M_pattern(views::single(std::move(__e))),
3104 _M_base(views::all(std::forward<_Range>(__r)))
3105 { }
3106
3107 constexpr _Vp
3108 base() const& requires copy_constructible<_Vp>
3109 { return _M_base; }
3110
3111 constexpr _Vp
3112 base() &&
3113 { return std::move(_M_base); }
3114
3115 constexpr auto
3116 begin()
3117 {
3118 if constexpr (forward_range<_Vp>)
3119 return _OuterIter<__detail::__simple_view<_Vp>>{
3120 this, ranges::begin(_M_base)};
3121 else
3122 {
3123 _M_current = ranges::begin(_M_base);
3124 return _OuterIter<false>{this};
3125 }
3126 }
3127
3128 constexpr auto
3129 begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3130 {
3131 return _OuterIter<true>{this, ranges::begin(_M_base)};
3132 }
3133
3134 constexpr auto
3135 end() requires forward_range<_Vp> && common_range<_Vp>
3136 {
3137 return _OuterIter<__detail::__simple_view<_Vp>>{
3138 this, ranges::end(_M_base)};
3139 }
3140
3141 constexpr auto
3142 end() const
3143 {
3144 if constexpr (forward_range<_Vp>
3145 && forward_range<const _Vp>
3146 && common_range<const _Vp>)
3147 return _OuterIter<true>{this, ranges::end(_M_base)};
3148 else
3149 return default_sentinel;
3150 }
3151 };
3152
3153 template<typename _Range, typename _Pattern>
3154 split_view(_Range&&, _Pattern&&)
3155 -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3156
3157 template<input_range _Range>
3158 split_view(_Range&&, range_value_t<_Range>)
3159 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3160
3161 namespace views
3162 {
3163 namespace __detail
3164 {
3165 template<typename _Range, typename _Pattern>
3166 concept __can_split_view
3167 = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3168 } // namespace __detail
3169
3170 struct _Split : __adaptor::_RangeAdaptor<_Split>
3171 {
3172 template<viewable_range _Range, typename _Pattern>
3173 requires __detail::__can_split_view<_Range, _Pattern>
3174 constexpr auto
3175 operator()(_Range&& __r, _Pattern&& __f) const
3176 {
3177 return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3178 }
3179
3180 using _RangeAdaptor<_Split>::operator();
3181 static constexpr int _S_arity = 2;
3182 // The pattern argument of views::split is not always simple -- it can be
3183 // a non-view range, the value category of which affects whether the call
3184 // is well-formed. But a scalar or a view pattern argument is surely
3185 // simple.
3186 template<typename _Pattern>
3187 static constexpr bool _S_has_simple_extra_args
3188 = is_scalar_v<_Pattern> || (view<_Pattern>
3189 && copy_constructible<_Pattern>);
3190 };
3191
3192 inline constexpr _Split split;
3193 } // namespace views
3194
3195 namespace views
3196 {
3197 struct _Counted
3198 {
3199 template<input_or_output_iterator _Iter>
3200 constexpr auto
3201 operator()(_Iter __i, iter_difference_t<_Iter> __n) const
3202 {
3203 if constexpr (random_access_iterator<_Iter>)
3204 return subrange(__i, __i + __n);
3205 else
3206 return subrange(counted_iterator(std::move(__i), __n),
3207 default_sentinel);
3208 }
3209 };
3210
3211 inline constexpr _Counted counted{};
3212 } // namespace views
3213
3214 template<view _Vp>
3215 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3216 class common_view : public view_interface<common_view<_Vp>>
3217 {
3218 private:
3219 _Vp _M_base = _Vp();
3220
3221 public:
3222 common_view() = default;
3223
3224 constexpr explicit
3225 common_view(_Vp __r)
3226 : _M_base(std::move(__r))
3227 { }
3228
3229 /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3230 template<viewable_range _Range>
3231 requires (!common_range<_Range>)
3232 && constructible_from<_Vp, views::all_t<_Range>>
3233 constexpr explicit
3234 common_view(_Range&& __r)
3235 : _M_base(views::all(std::forward<_Range>(__r)))
3236 { }
3237 */
3238
3239 constexpr _Vp
3240 base() const& requires copy_constructible<_Vp>
3241 { return _M_base; }
3242
3243 constexpr _Vp
3244 base() &&
3245 { return std::move(_M_base); }
3246
3247 constexpr auto
3248 begin()
3249 {
3250 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3251 return ranges::begin(_M_base);
3252 else
3253 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3254 (ranges::begin(_M_base));
3255 }
3256
3257 constexpr auto
3258 begin() const requires range<const _Vp>
3259 {
3260 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3261 return ranges::begin(_M_base);
3262 else
3263 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3264 (ranges::begin(_M_base));
3265 }
3266
3267 constexpr auto
3268 end()
3269 {
3270 if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3271 return ranges::begin(_M_base) + ranges::size(_M_base);
3272 else
3273 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3274 (ranges::end(_M_base));
3275 }
3276
3277 constexpr auto
3278 end() const requires range<const _Vp>
3279 {
3280 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3281 return ranges::begin(_M_base) + ranges::size(_M_base);
3282 else
3283 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3284 (ranges::end(_M_base));
3285 }
3286
3287 constexpr auto
3288 size() requires sized_range<_Vp>
3289 { return ranges::size(_M_base); }
3290
3291 constexpr auto
3292 size() const requires sized_range<const _Vp>
3293 { return ranges::size(_M_base); }
3294 };
3295
3296 template<typename _Range>
3297 common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3298
3299 template<typename _Tp>
3300 inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3301 = enable_borrowed_range<_Tp>;
3302
3303 namespace views
3304 {
3305 namespace __detail
3306 {
3307 template<typename _Range>
3308 concept __already_common = common_range<_Range>
3309 && requires { views::all(std::declval<_Range>()); };
3310
3311 template<typename _Range>
3312 concept __can_common_view
3313 = requires { common_view{std::declval<_Range>()}; };
3314 } // namespace __detail
3315
3316 struct _Common : __adaptor::_RangeAdaptorClosure
3317 {
3318 template<viewable_range _Range>
3319 requires __detail::__already_common<_Range>
3320 || __detail::__can_common_view<_Range>
3321 constexpr auto
3322 operator()(_Range&& __r) const
3323 {
3324 if constexpr (__detail::__already_common<_Range>)
3325 return views::all(std::forward<_Range>(__r));
3326 else
3327 return common_view{std::forward<_Range>(__r)};
3328 }
3329
3330 static constexpr bool _S_has_simple_call_op = true;
3331 };
3332
3333 inline constexpr _Common common;
3334 } // namespace views
3335
3336 template<view _Vp>
3337 requires bidirectional_range<_Vp>
3338 class reverse_view : public view_interface<reverse_view<_Vp>>
3339 {
3340 private:
3341 static constexpr bool _S_needs_cached_begin
3342 = !common_range<_Vp> && !random_access_range<_Vp>;
3343
3344 [[no_unique_address]]
3345 __detail::__maybe_present_t<_S_needs_cached_begin,
3346 __detail::_CachedPosition<_Vp>>
3347 _M_cached_begin;
3348 _Vp _M_base = _Vp();
3349
3350 public:
3351 reverse_view() = default;
3352
3353 constexpr explicit
3354 reverse_view(_Vp __r)
3355 : _M_base(std::move(__r))
3356 { }
3357
3358 constexpr _Vp
3359 base() const& requires copy_constructible<_Vp>
3360 { return _M_base; }
3361
3362 constexpr _Vp
3363 base() &&
3364 { return std::move(_M_base); }
3365
3366 constexpr reverse_iterator<iterator_t<_Vp>>
3367 begin()
3368 {
3369 if constexpr (_S_needs_cached_begin)
3370 if (_M_cached_begin._M_has_value())
3371 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3372
3373 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3374 if constexpr (_S_needs_cached_begin)
3375 _M_cached_begin._M_set(_M_base, __it);
3377 }
3378
3379 constexpr auto
3380 begin() requires common_range<_Vp>
3381 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3382
3383 constexpr auto
3384 begin() const requires common_range<const _Vp>
3385 { return std::make_reverse_iterator(ranges::end(_M_base)); }
3386
3387 constexpr reverse_iterator<iterator_t<_Vp>>
3388 end()
3389 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3390
3391 constexpr auto
3392 end() const requires common_range<const _Vp>
3393 { return std::make_reverse_iterator(ranges::begin(_M_base)); }
3394
3395 constexpr auto
3396 size() requires sized_range<_Vp>
3397 { return ranges::size(_M_base); }
3398
3399 constexpr auto
3400 size() const requires sized_range<const _Vp>
3401 { return ranges::size(_M_base); }
3402 };
3403
3404 template<typename _Range>
3405 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3406
3407 template<typename _Tp>
3408 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3409 = enable_borrowed_range<_Tp>;
3410
3411 namespace views
3412 {
3413 namespace __detail
3414 {
3415 template<typename>
3416 inline constexpr bool __is_reversible_subrange = false;
3417
3418 template<typename _Iter, subrange_kind _Kind>
3419 inline constexpr bool
3420 __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3421 reverse_iterator<_Iter>,
3422 _Kind>> = true;
3423
3424 template<typename>
3425 inline constexpr bool __is_reverse_view = false;
3426
3427 template<typename _Vp>
3428 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3429
3430 template<typename _Range>
3431 concept __can_reverse_view
3432 = requires { reverse_view{std::declval<_Range>()}; };
3433 } // namespace __detail
3434
3435 struct _Reverse : __adaptor::_RangeAdaptorClosure
3436 {
3437 template<viewable_range _Range>
3438 requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3439 || __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3440 || __detail::__can_reverse_view<_Range>
3441 constexpr auto
3442 operator()(_Range&& __r) const
3443 {
3444 using _Tp = remove_cvref_t<_Range>;
3445 if constexpr (__detail::__is_reverse_view<_Tp>)
3446 return std::forward<_Range>(__r).base();
3447 else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3448 {
3449 using _Iter = decltype(ranges::begin(__r).base());
3450 if constexpr (sized_range<_Tp>)
3451 return subrange<_Iter, _Iter, subrange_kind::sized>
3452 {__r.end().base(), __r.begin().base(), __r.size()};
3453 else
3454 return subrange<_Iter, _Iter, subrange_kind::unsized>
3455 {__r.end().base(), __r.begin().base()};
3456 }
3457 else
3458 return reverse_view{std::forward<_Range>(__r)};
3459 }
3460
3461 static constexpr bool _S_has_simple_call_op = true;
3462 };
3463
3464 inline constexpr _Reverse reverse;
3465 } // namespace views
3466
3467 namespace __detail
3468 {
3469 template<typename _Tp, size_t _Nm>
3470 concept __has_tuple_element = requires(_Tp __t)
3471 {
3472 typename tuple_size<_Tp>::type;
3473 requires _Nm < tuple_size_v<_Tp>;
3474 typename tuple_element_t<_Nm, _Tp>;
3475 { std::get<_Nm>(__t) }
3476 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3477 };
3478
3479 template<typename _Tp, size_t _Nm>
3480 concept __returnable_element
3481 = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
3482 }
3483
3484 template<input_range _Vp, size_t _Nm>
3485 requires view<_Vp>
3486 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3487 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3488 _Nm>
3489 && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
3490 class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3491 {
3492 public:
3493 elements_view() = default;
3494
3495 constexpr explicit
3496 elements_view(_Vp base)
3497 : _M_base(std::move(base))
3498 { }
3499
3500 constexpr _Vp
3501 base() const& requires copy_constructible<_Vp>
3502 { return _M_base; }
3503
3504 constexpr _Vp
3505 base() &&
3506 { return std::move(_M_base); }
3507
3508 constexpr auto
3509 begin() requires (!__detail::__simple_view<_Vp>)
3510 { return _Iterator<false>(ranges::begin(_M_base)); }
3511
3512 constexpr auto
3513 begin() const requires range<const _Vp>
3514 { return _Iterator<true>(ranges::begin(_M_base)); }
3515
3516 constexpr auto
3517 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3518 { return _Sentinel<false>{ranges::end(_M_base)}; }
3519
3520 constexpr auto
3521 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3522 { return _Iterator<false>{ranges::end(_M_base)}; }
3523
3524 constexpr auto
3525 end() const requires range<const _Vp>
3526 { return _Sentinel<true>{ranges::end(_M_base)}; }
3527
3528 constexpr auto
3529 end() const requires common_range<const _Vp>
3530 { return _Iterator<true>{ranges::end(_M_base)}; }
3531
3532 constexpr auto
3533 size() requires sized_range<_Vp>
3534 { return ranges::size(_M_base); }
3535
3536 constexpr auto
3537 size() const requires sized_range<const _Vp>
3538 { return ranges::size(_M_base); }
3539
3540 private:
3541 template<bool _Const>
3542 using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3543
3544 template<bool _Const>
3545 struct __iter_cat
3546 { };
3547
3548 template<bool _Const>
3549 requires forward_range<_Base<_Const>>
3550 struct __iter_cat<_Const>
3551 {
3552 private:
3553 static auto _S_iter_cat()
3554 {
3555 using _Base = elements_view::_Base<_Const>;
3556 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3557 using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
3558 if constexpr (!is_lvalue_reference_v<_Res>)
3559 return input_iterator_tag{};
3560 else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
3561 return random_access_iterator_tag{};
3562 else
3563 return _Cat{};
3564 }
3565 public:
3566 using iterator_category = decltype(_S_iter_cat());
3567 };
3568
3569 template<bool _Const>
3570 struct _Sentinel;
3571
3572 template<bool _Const>
3573 struct _Iterator : __iter_cat<_Const>
3574 {
3575 private:
3576 using _Base = elements_view::_Base<_Const>;
3577
3578 iterator_t<_Base> _M_current = iterator_t<_Base>();
3579
3580 static constexpr decltype(auto)
3581 _S_get_element(const iterator_t<_Base>& __i)
3582 {
3583 if constexpr (is_reference_v<range_reference_t<_Base>>)
3584 return std::get<_Nm>(*__i);
3585 else
3586 {
3587 using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
3588 return static_cast<_Et>(std::get<_Nm>(*__i));
3589 }
3590 }
3591
3592 static auto
3593 _S_iter_concept()
3594 {
3595 if constexpr (random_access_range<_Base>)
3596 return random_access_iterator_tag{};
3597 else if constexpr (bidirectional_range<_Base>)
3598 return bidirectional_iterator_tag{};
3599 else if constexpr (forward_range<_Base>)
3600 return forward_iterator_tag{};
3601 else
3602 return input_iterator_tag{};
3603 }
3604
3605 friend _Iterator<!_Const>;
3606
3607 public:
3608 using iterator_concept = decltype(_S_iter_concept());
3609 // iterator_category defined in elements_view::__iter_cat
3610 using value_type
3611 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3612 using difference_type = range_difference_t<_Base>;
3613
3614 _Iterator() = default;
3615
3616 constexpr explicit
3617 _Iterator(iterator_t<_Base> current)
3618 : _M_current(std::move(current))
3619 { }
3620
3621 constexpr
3622 _Iterator(_Iterator<!_Const> i)
3623 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3624 : _M_current(std::move(i._M_current))
3625 { }
3626
3627 constexpr const iterator_t<_Base>&
3628 base() const& noexcept
3629 { return _M_current; }
3630
3631 constexpr iterator_t<_Base>
3632 base() &&
3633 { return std::move(_M_current); }
3634
3635 constexpr decltype(auto)
3636 operator*() const
3637 { return _S_get_element(_M_current); }
3638
3639 constexpr _Iterator&
3640 operator++()
3641 {
3642 ++_M_current;
3643 return *this;
3644 }
3645
3646 constexpr void
3647 operator++(int)
3648 { ++_M_current; }
3649
3650 constexpr _Iterator
3651 operator++(int) requires forward_range<_Base>
3652 {
3653 auto __tmp = *this;
3654 ++_M_current;
3655 return __tmp;
3656 }
3657
3658 constexpr _Iterator&
3659 operator--() requires bidirectional_range<_Base>
3660 {
3661 --_M_current;
3662 return *this;
3663 }
3664
3665 constexpr _Iterator
3666 operator--(int) requires bidirectional_range<_Base>
3667 {
3668 auto __tmp = *this;
3669 --_M_current;
3670 return __tmp;
3671 }
3672
3673 constexpr _Iterator&
3674 operator+=(difference_type __n)
3675 requires random_access_range<_Base>
3676 {
3677 _M_current += __n;
3678 return *this;
3679 }
3680
3681 constexpr _Iterator&
3682 operator-=(difference_type __n)
3683 requires random_access_range<_Base>
3684 {
3685 _M_current -= __n;
3686 return *this;
3687 }
3688
3689 constexpr decltype(auto)
3690 operator[](difference_type __n) const
3691 requires random_access_range<_Base>
3692 { return _S_get_element(_M_current + __n); }
3693
3694 friend constexpr bool
3695 operator==(const _Iterator& __x, const _Iterator& __y)
3696 requires equality_comparable<iterator_t<_Base>>
3697 { return __x._M_current == __y._M_current; }
3698
3699 friend constexpr bool
3700 operator<(const _Iterator& __x, const _Iterator& __y)
3701 requires random_access_range<_Base>
3702 { return __x._M_current < __y._M_current; }
3703
3704 friend constexpr bool
3705 operator>(const _Iterator& __x, const _Iterator& __y)
3706 requires random_access_range<_Base>
3707 { return __y._M_current < __x._M_current; }
3708
3709 friend constexpr bool
3710 operator<=(const _Iterator& __x, const _Iterator& __y)
3711 requires random_access_range<_Base>
3712 { return !(__y._M_current > __x._M_current); }
3713
3714 friend constexpr bool
3715 operator>=(const _Iterator& __x, const _Iterator& __y)
3716 requires random_access_range<_Base>
3717 { return !(__x._M_current > __y._M_current); }
3718
3719#ifdef __cpp_lib_three_way_comparison
3720 friend constexpr auto
3721 operator<=>(const _Iterator& __x, const _Iterator& __y)
3722 requires random_access_range<_Base>
3723 && three_way_comparable<iterator_t<_Base>>
3724 { return __x._M_current <=> __y._M_current; }
3725#endif
3726
3727 friend constexpr _Iterator
3728 operator+(const _Iterator& __x, difference_type __y)
3729 requires random_access_range<_Base>
3730 { return _Iterator{__x} += __y; }
3731
3732 friend constexpr _Iterator
3733 operator+(difference_type __x, const _Iterator& __y)
3734 requires random_access_range<_Base>
3735 { return __y + __x; }
3736
3737 friend constexpr _Iterator
3738 operator-(const _Iterator& __x, difference_type __y)
3739 requires random_access_range<_Base>
3740 { return _Iterator{__x} -= __y; }
3741
3742 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3743 // 3483. transform_view::iterator's difference is overconstrained
3744 friend constexpr difference_type
3745 operator-(const _Iterator& __x, const _Iterator& __y)
3746 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3747 { return __x._M_current - __y._M_current; }
3748
3749 template <bool> friend struct _Sentinel;
3750 };
3751
3752 template<bool _Const>
3753 struct _Sentinel
3754 {
3755 private:
3756 template<bool _Const2>
3757 constexpr bool
3758 _M_equal(const _Iterator<_Const2>& __x) const
3759 { return __x._M_current == _M_end; }
3760
3761 template<bool _Const2>
3762 constexpr auto
3763 _M_distance_from(const _Iterator<_Const2>& __i) const
3764 { return _M_end - __i._M_current; }
3765
3766 using _Base = elements_view::_Base<_Const>;
3767 sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3768
3769 public:
3770 _Sentinel() = default;
3771
3772 constexpr explicit
3773 _Sentinel(sentinel_t<_Base> __end)
3774 : _M_end(std::move(__end))
3775 { }
3776
3777 constexpr
3778 _Sentinel(_Sentinel<!_Const> __other)
3779 requires _Const
3780 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3781 : _M_end(std::move(__other._M_end))
3782 { }
3783
3784 constexpr sentinel_t<_Base>
3785 base() const
3786 { return _M_end; }
3787
3788 template<bool _Const2>
3789 requires sentinel_for<sentinel_t<_Base>,
3790 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3791 friend constexpr bool
3792 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3793 { return __y._M_equal(__x); }
3794
3795 template<bool _Const2,
3796 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3797 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3798 friend constexpr range_difference_t<_Base2>
3799 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3800 { return -__y._M_distance_from(__x); }
3801
3802 template<bool _Const2,
3803 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3804 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3805 friend constexpr range_difference_t<_Base2>
3806 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3807 { return __x._M_distance_from(__y); }
3808
3809 friend _Sentinel<!_Const>;
3810 };
3811
3812 _Vp _M_base = _Vp();
3813 };
3814
3815 template<typename _Tp, size_t _Nm>
3816 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3817 = enable_borrowed_range<_Tp>;
3818
3819 template<typename _Range>
3820 using keys_view = elements_view<views::all_t<_Range>, 0>;
3821
3822 template<typename _Range>
3823 using values_view = elements_view<views::all_t<_Range>, 1>;
3824
3825 namespace views
3826 {
3827 namespace __detail
3828 {
3829 template<size_t _Nm, typename _Range>
3830 concept __can_elements_view
3831 = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
3832 } // namespace __detail
3833
3834 template<size_t _Nm>
3835 struct _Elements : __adaptor::_RangeAdaptorClosure
3836 {
3837 template<viewable_range _Range>
3838 requires __detail::__can_elements_view<_Nm, _Range>
3839 constexpr auto
3840 operator()(_Range&& __r) const
3841 {
3842 return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
3843 }
3844
3845 static constexpr bool _S_has_simple_call_op = true;
3846 };
3847
3848 template<size_t _Nm>
3849 inline constexpr _Elements<_Nm> elements;
3850 inline constexpr auto keys = elements<0>;
3851 inline constexpr auto values = elements<1>;
3852 } // namespace views
3853
3854} // namespace ranges
3855
3856 namespace views = ranges::views;
3857
3858_GLIBCXX_END_NAMESPACE_VERSION
3859} // namespace
3860#endif // library concepts
3861#endif // C++2a
3862#endif /* _GLIBCXX_RANGES */
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: std/complex:392
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: std/complex:362
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: std/complex:332
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
typename invoke_result< _Fn, _Args... >::type invoke_result_t
std::invoke_result_t
auto declval() noexcept -> decltype(__declval< _Tp >(0))
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
Definition: invoke.h:90
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:77
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1237
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1215
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
constexpr void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
Definition: stl_numeric.h:88
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:263
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition: std/bitset:1444
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
Definition: range_access.h:290
constexpr _Iterator __base(_Iterator __it)
Class template for optional values.
Definition: std/optional:675