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