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