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