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