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