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 
2597  _Vp _M_base = _Vp();
2598 
2599  // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>"
2600  [[no_unique_address]]
2601  __detail::__maybe_present_t<!is_reference_v<_InnerRange>,
2602  views::all_t<_InnerRange>> _M_inner;
2603 
2604  public:
2605  join_view() = default;
2606 
2607  constexpr explicit
2608  join_view(_Vp __base)
2609  : _M_base(std::move(__base))
2610  { }
2611 
2612  constexpr _Vp
2613  base() const& requires copy_constructible<_Vp>
2614  { return _M_base; }
2615 
2616  constexpr _Vp
2617  base() &&
2618  { return std::move(_M_base); }
2619 
2620  constexpr auto
2621  begin()
2622  {
2623  constexpr bool __use_const
2624  = (__detail::__simple_view<_Vp>
2625  && is_reference_v<range_reference_t<_Vp>>);
2626  return _Iterator<__use_const>{*this, ranges::begin(_M_base)};
2627  }
2628 
2629  constexpr auto
2630  begin() const
2631  requires input_range<const _Vp>
2632  && is_reference_v<range_reference_t<const _Vp>>
2633  {
2634  return _Iterator<true>{*this, ranges::begin(_M_base)};
2635  }
2636 
2637  constexpr auto
2638  end()
2639  {
2640  if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2641  && forward_range<_InnerRange>
2642  && common_range<_Vp> && common_range<_InnerRange>)
2643  return _Iterator<__detail::__simple_view<_Vp>>{*this,
2644  ranges::end(_M_base)};
2645  else
2646  return _Sentinel<__detail::__simple_view<_Vp>>{*this};
2647  }
2648 
2649  constexpr auto
2650  end() const
2651  requires input_range<const _Vp>
2652  && is_reference_v<range_reference_t<const _Vp>>
2653  {
2654  if constexpr (forward_range<const _Vp>
2655  && is_reference_v<range_reference_t<const _Vp>>
2656  && forward_range<range_reference_t<const _Vp>>
2657  && common_range<const _Vp>
2658  && common_range<range_reference_t<const _Vp>>)
2659  return _Iterator<true>{*this, ranges::end(_M_base)};
2660  else
2661  return _Sentinel<true>{*this};
2662  }
2663  };
2664 
2665  template<typename _Range>
2666  explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2667 
2668  namespace views
2669  {
2670  inline constexpr __adaptor::_RangeAdaptorClosure join
2671  = [] <viewable_range _Range> (_Range&& __r)
2672  {
2673  return join_view{std::forward<_Range>(__r)};
2674  };
2675  } // namespace views
2676 
2677  namespace __detail
2678  {
2679  template<auto>
2680  struct __require_constant;
2681 
2682  template<typename _Range>
2683  concept __tiny_range = sized_range<_Range>
2684  && requires
2685  { typename __require_constant<remove_reference_t<_Range>::size()>; }
2686  && (remove_reference_t<_Range>::size() <= 1);
2687  }
2688 
2689  template<input_range _Vp, forward_range _Pattern>
2690  requires view<_Vp> && view<_Pattern>
2691  && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2692  ranges::equal_to>
2693  && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2694  class split_view : public view_interface<split_view<_Vp, _Pattern>>
2695  {
2696  private:
2697  template<bool _Const>
2698  struct _InnerIter;
2699 
2700  template<bool _Const>
2701  struct _OuterIter
2702  {
2703  private:
2704  using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2705  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2706 
2707  constexpr bool
2708  __at_end() const
2709  { return _M_current == ranges::end(_M_parent->_M_base); }
2710 
2711  // XXX: [24.7.11.3.1]
2712  // Many of the following specifications refer to the notional member
2713  // current of outer-iterator. current is equivalent to current_ if
2714  // V models forward_range, and parent_->current_ otherwise.
2715  constexpr auto&
2716  __current()
2717  {
2718  if constexpr (forward_range<_Vp>)
2719  return _M_current;
2720  else
2721  return _M_parent->_M_current;
2722  }
2723 
2724  constexpr auto&
2725  __current() const
2726  {
2727  if constexpr (forward_range<_Vp>)
2728  return _M_current;
2729  else
2730  return _M_parent->_M_current;
2731  }
2732 
2733  _Parent* _M_parent = nullptr;
2734 
2735  // XXX: _M_current is present only if "V models forward_range"
2736  [[no_unique_address]]
2737  __detail::__maybe_present_t<forward_range<_Vp>,
2738  iterator_t<_Base>> _M_current;
2739 
2740  public:
2741  using iterator_concept = conditional_t<forward_range<_Base>,
2742  forward_iterator_tag,
2743  input_iterator_tag>;
2744  using iterator_category = input_iterator_tag;
2745  using difference_type = range_difference_t<_Base>;
2746 
2747  struct value_type : view_interface<value_type>
2748  {
2749  private:
2750  _OuterIter _M_i = _OuterIter();
2751 
2752  public:
2753  value_type() = default;
2754 
2755  constexpr explicit
2756  value_type(_OuterIter __i)
2757  : _M_i(std::move(__i))
2758  { }
2759 
2760  constexpr _InnerIter<_Const>
2761  begin() const
2762  requires copyable<_OuterIter>
2763  { return _InnerIter<_Const>{_M_i}; }
2764 
2765  constexpr _InnerIter<_Const>
2766  begin()
2767  requires (!copyable<_OuterIter>)
2768  { return _InnerIter<_Const>{std::move(_M_i)}; }
2769 
2770  constexpr default_sentinel_t
2771  end() const
2772  { return default_sentinel; }
2773  };
2774 
2775  _OuterIter() = default;
2776 
2777  constexpr explicit
2778  _OuterIter(_Parent& __parent) requires (!forward_range<_Base>)
2779  : _M_parent(address(__parent))
2780  { }
2781 
2782  constexpr
2783  _OuterIter(_Parent& __parent, iterator_t<_Base> __current)
2784  requires forward_range<_Base>
2785  : _M_parent(std::__addressof(__parent)),
2786  _M_current(std::move(__current))
2787  { }
2788 
2789  constexpr
2790  _OuterIter(_OuterIter<!_Const> __i)
2791  requires _Const
2792  && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2793  : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2794  { }
2795 
2796  constexpr value_type
2797  operator*() const
2798  { return value_type{*this}; }
2799 
2800  constexpr _OuterIter&
2801  operator++()
2802  {
2803  const auto __end = ranges::end(_M_parent->_M_base);
2804  if (_M_current == __end)
2805  return *this;
2806  const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2807  if (__pbegin == __pend)
2808  ++_M_current;
2809  else
2810  do
2811  {
2812  auto [__b, __p]
2813  = __detail::mismatch(std::move(_M_current), __end,
2814  __pbegin, __pend);
2815  _M_current = std::move(__b);
2816  if (__p == __pend)
2817  break;
2818  } while (++_M_current != __end);
2819  return *this;
2820  }
2821 
2822  constexpr decltype(auto)
2823  operator++(int)
2824  {
2825  if constexpr (forward_range<_Base>)
2826  {
2827  auto __tmp = *this;
2828  ++*this;
2829  return __tmp;
2830  }
2831  else
2832  ++*this;
2833  }
2834 
2835  friend constexpr bool
2836  operator==(const _OuterIter& __x, const _OuterIter& __y)
2837  requires forward_range<_Base>
2838  { return __x._M_current == __y._M_current; }
2839 
2840  friend constexpr bool
2841  operator==(const _OuterIter& __x, default_sentinel_t)
2842  { return __x.__at_end(); };
2843 
2844  friend _OuterIter<!_Const>;
2845  friend _InnerIter<_Const>;
2846  };
2847 
2848  template<bool _Const>
2849  struct _InnerIter
2850  {
2851  private:
2852  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2853 
2854  constexpr bool
2855  __at_end() const
2856  {
2857  auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
2858  auto __end = ranges::end(_M_i._M_parent->_M_base);
2859  if constexpr (__detail::__tiny_range<_Pattern>)
2860  {
2861  const auto& __cur = _M_i.__current();
2862  if (__cur == __end)
2863  return true;
2864  if (__pcur == __pend)
2865  return _M_incremented;
2866  return *__cur == *__pcur;
2867  }
2868  else
2869  {
2870  auto __cur = _M_i.__current();
2871  if (__cur == __end)
2872  return true;
2873  if (__pcur == __pend)
2874  return _M_incremented;
2875  do
2876  {
2877  if (*__cur != *__pcur)
2878  return false;
2879  if (++__pcur == __pend)
2880  return true;
2881  } while (++__cur != __end);
2882  return false;
2883  }
2884  }
2885 
2886  static constexpr auto
2887  _S_iter_cat()
2888  {
2889  using _Cat
2890  = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2891  if constexpr (derived_from<_Cat, forward_iterator_tag>)
2892  return forward_iterator_tag{};
2893  else
2894  return _Cat{};
2895  }
2896 
2897  static constexpr decltype(auto)
2898  __iter_move(const _InnerIter& __i = {})
2899  noexcept(noexcept(ranges::iter_move(__i._M_i.__current())))
2900  { return ranges::iter_move(__i._M_i.__current()); }
2901 
2902  static constexpr void
2903  __iter_swap(const _InnerIter& __x = {}, const _InnerIter& __y = {})
2904  noexcept(noexcept(ranges::iter_swap(__x._M_i.__current(),
2905  __y._M_i.__current())))
2906  { ranges::iter_swap(__x._M_i.__current(), __y._M_i.__current()); }
2907 
2908  _OuterIter<_Const> _M_i = _OuterIter<_Const>();
2909  bool _M_incremented = false;
2910 
2911  public:
2912  using iterator_concept
2913  = typename _OuterIter<_Const>::iterator_concept;
2914  using iterator_category = decltype(_S_iter_cat());
2915  using value_type = range_value_t<_Base>;
2916  using difference_type = range_difference_t<_Base>;
2917 
2918  _InnerIter() = default;
2919 
2920  constexpr explicit
2921  _InnerIter(_OuterIter<_Const> __i)
2922  : _M_i(std::move(__i))
2923  { }
2924 
2925  constexpr decltype(auto)
2926  operator*() const
2927  { return *_M_i._M_current; }
2928 
2929  constexpr _InnerIter&
2930  operator++()
2931  {
2932  _M_incremented = true;
2933  if constexpr (!forward_range<_Base>)
2934  if constexpr (_Pattern::size() == 0)
2935  return *this;
2936  ++_M_i.__current();
2937  return *this;
2938  }
2939 
2940  constexpr decltype(auto)
2941  operator++(int)
2942  {
2943  if constexpr (forward_range<_Vp>)
2944  {
2945  auto __tmp = *this;
2946  ++*this;
2947  return __tmp;
2948  }
2949  else
2950  ++*this;
2951  }
2952 
2953  friend constexpr bool
2954  operator==(const _InnerIter& __x, const _InnerIter& __y)
2955  requires forward_range<_Base>
2956  { return __x._M_i == __y._M_i; }
2957 
2958  friend constexpr bool
2959  operator==(const _InnerIter& __x, default_sentinel_t)
2960  { return __x.__at_end(); }
2961 
2962  friend constexpr decltype(auto)
2963  iter_move(const _InnerIter& __i) noexcept(noexcept(__iter_move()))
2964  { return __iter_move(__i); }
2965 
2966  friend constexpr void
2967  iter_swap(const _InnerIter& __x, const _InnerIter& __y)
2968  noexcept(noexcept(__iter_swap()))
2969  requires indirectly_swappable<iterator_t<_Base>>
2970  { __iter_swap(__x, __y); }
2971  };
2972 
2973  _Vp _M_base = _Vp();
2974  _Pattern _M_pattern = _Pattern();
2975 
2976  // XXX: _M_current is "present only if !forward_range<V>"
2977  [[no_unique_address]]
2978  __detail::__maybe_present_t<!forward_range<_Vp>, iterator_t<_Vp>>
2979  _M_current;
2980 
2981 
2982  public:
2983  split_view() = default;
2984 
2985  constexpr
2986  split_view(_Vp __base, _Pattern __pattern)
2987  : _M_base(std::move(__base)), _M_pattern(std::move(__pattern))
2988  { }
2989 
2990  template<input_range _Range>
2991  requires constructible_from<_Vp, views::all_t<_Range>>
2992  && constructible_from<_Pattern, single_view<range_value_t<_Range>>>
2993  constexpr
2994  split_view(_Range&& __r, range_value_t<_Range> __e)
2995  : _M_base(views::all(std::forward<_Range>(__r))),
2996  _M_pattern(std::move(__e))
2997  { }
2998 
2999  constexpr _Vp
3000  base() const& requires copy_constructible<_Vp>
3001  { return _M_base; }
3002 
3003  constexpr _Vp
3004  base() &&
3005  { return std::move(_M_base); }
3006 
3007  constexpr auto
3008  begin()
3009  {
3010  if constexpr (forward_range<_Vp>)
3011  return _OuterIter<__detail::__simple_view<_Vp>>{*this,
3012  ranges::begin(_M_base)};
3013  else
3014  {
3015  _M_current = ranges::begin(_M_base);
3016  return _OuterIter<false>{*this};
3017  }
3018  }
3019 
3020  constexpr auto
3021  begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3022  {
3023  return _OuterIter<true>{*this, ranges::begin(_M_base)};
3024  }
3025 
3026  constexpr auto
3027  end() requires forward_range<_Vp> && common_range<_Vp>
3028  {
3029  return _OuterIter<__detail::__simple_view<_Vp>>{*this, ranges::end(_M_base)};
3030  }
3031 
3032  constexpr auto
3033  end() const
3034  {
3035  if constexpr (forward_range<_Vp>
3036  && forward_range<const _Vp>
3037  && common_range<const _Vp>)
3038  return _OuterIter<true>{*this, ranges::end(_M_base)};
3039  else
3040  return default_sentinel;
3041  }
3042  };
3043 
3044  template<typename _Range, typename _Pred>
3045  split_view(_Range&&, _Pred&&)
3046  -> split_view<views::all_t<_Range>, views::all_t<_Pred>>;
3047 
3048  template<input_range _Range>
3049  split_view(_Range&&, range_value_t<_Range>)
3050  -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3051 
3052  namespace views
3053  {
3054  inline constexpr __adaptor::_RangeAdaptor split
3055  = [] <viewable_range _Range, typename _Fp> (_Range&& __r, _Fp&& __f)
3056  {
3057  return split_view{std::forward<_Range>(__r), std::forward<_Fp>(__f)};
3058  };
3059  } // namespace views
3060 
3061  namespace views
3062  {
3063  struct _Counted
3064  {
3065  template<input_or_output_iterator _Iter>
3066  constexpr auto
3067  operator()(_Iter __i, iter_difference_t<_Iter> __n) const
3068  {
3069  if constexpr (random_access_iterator<_Iter>)
3070  return subrange{__i, __i + __n};
3071  else
3072  return subrange{counted_iterator{std::move(__i), __n},
3073  default_sentinel};
3074  }
3075  };
3076 
3077  inline constexpr _Counted counted{};
3078  } // namespace views
3079 
3080  template<view _Vp>
3081  requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3082  class common_view : public view_interface<common_view<_Vp>>
3083  {
3084  private:
3085  _Vp _M_base = _Vp();
3086 
3087  public:
3088  common_view() = default;
3089 
3090  constexpr explicit
3091  common_view(_Vp __r)
3092  : _M_base(std::move(__r))
3093  { }
3094 
3095  /* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3096  template<viewable_range _Range>
3097  requires (!common_range<_Range>)
3098  && constructible_from<_Vp, views::all_t<_Range>>
3099  constexpr explicit
3100  common_view(_Range&& __r)
3101  : _M_base(views::all(std::forward<_Range>(__r)))
3102  { }
3103  */
3104 
3105  constexpr _Vp
3106  base() const& requires copy_constructible<_Vp>
3107  { return _M_base; }
3108 
3109  constexpr _Vp
3110  base() &&
3111  { return std::move(_M_base); }
3112 
3113  constexpr auto
3114  begin()
3115  {
3116  if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3117  return ranges::begin(_M_base);
3118  else
3119  return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3120  (ranges::begin(_M_base));
3121  }
3122 
3123  constexpr auto
3124  begin() const requires range<const _Vp>
3125  {
3126  if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3127  return ranges::begin(_M_base);
3128  else
3129  return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3130  (ranges::begin(_M_base));
3131  }
3132 
3133  constexpr auto
3134  end()
3135  {
3136  if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3137  return ranges::begin(_M_base) + ranges::size(_M_base);
3138  else
3139  return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3140  (ranges::end(_M_base));
3141  }
3142 
3143  constexpr auto
3144  end() const requires range<const _Vp>
3145  {
3146  if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3147  return ranges::begin(_M_base) + ranges::size(_M_base);
3148  else
3149  return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3150  (ranges::end(_M_base));
3151  }
3152 
3153  constexpr auto
3154  size() requires sized_range<_Vp>
3155  { return ranges::size(_M_base); }
3156 
3157  constexpr auto
3158  size() const requires sized_range<const _Vp>
3159  { return ranges::size(_M_base); }
3160  };
3161 
3162  template<typename _Range>
3163  common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3164 
3165  namespace views
3166  {
3167  inline constexpr __adaptor::_RangeAdaptorClosure common
3168  = [] <viewable_range _Range> (_Range&& __r)
3169  {
3170  if constexpr (common_range<_Range>
3171  && requires { views::all(std::forward<_Range>(__r)); })
3172  return views::all(std::forward<_Range>(__r));
3173  else
3174  return common_view{std::forward<_Range>(__r)};
3175  };
3176 
3177  } // namespace views
3178 
3179  template<view _Vp>
3180  requires bidirectional_range<_Vp>
3181  class reverse_view : public view_interface<reverse_view<_Vp>>
3182  {
3183  private:
3184  _Vp _M_base = _Vp();
3185 
3186  static constexpr bool _S_needs_cached_begin
3187  = !common_range<_Vp> && !random_access_range<_Vp>;
3188  [[no_unique_address]]
3189  __detail::__maybe_present_t<_S_needs_cached_begin,
3190  __detail::_CachedPosition<_Vp>>
3191  _M_cached_begin;
3192 
3193  public:
3194  reverse_view() = default;
3195 
3196  constexpr explicit
3197  reverse_view(_Vp __r)
3198  : _M_base(std::move(__r))
3199  { }
3200 
3201  constexpr _Vp
3202  base() const& requires copy_constructible<_Vp>
3203  { return _M_base; }
3204 
3205  constexpr _Vp
3206  base() &&
3207  { return std::move(_M_base); }
3208 
3209  constexpr reverse_iterator<iterator_t<_Vp>>
3210  begin()
3211  {
3212  if constexpr (_S_needs_cached_begin)
3213  if (_M_cached_begin._M_has_value())
3214  return make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3215 
3216  auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3217  if constexpr (_S_needs_cached_begin)
3218  _M_cached_begin._M_set(_M_base, __it);
3219  return make_reverse_iterator(std::move(__it));
3220  }
3221 
3222  constexpr auto
3223  begin() requires common_range<_Vp>
3224  { return make_reverse_iterator(ranges::end(_M_base)); }
3225 
3226  constexpr auto
3227  begin() const requires common_range<const _Vp>
3228  { return make_reverse_iterator(ranges::end(_M_base)); }
3229 
3230  constexpr reverse_iterator<iterator_t<_Vp>>
3231  end()
3232  { return make_reverse_iterator(ranges::begin(_M_base)); }
3233 
3234  constexpr auto
3235  end() const requires common_range<const _Vp>
3236  { return make_reverse_iterator(ranges::begin(_M_base)); }
3237 
3238  constexpr auto
3239  size() requires sized_range<_Vp>
3240  { return ranges::size(_M_base); }
3241 
3242  constexpr auto
3243  size() const requires sized_range<const _Vp>
3244  { return ranges::size(_M_base); }
3245  };
3246 
3247  template<typename _Range>
3248  reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3249 
3250  namespace views
3251  {
3252  namespace __detail
3253  {
3254  template<typename>
3255  inline constexpr bool __is_reversible_subrange = false;
3256 
3257  template<typename _Iter, subrange_kind _Kind>
3258  inline constexpr bool
3259  __is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3260  reverse_iterator<_Iter>,
3261  _Kind>> = true;
3262 
3263  template<typename>
3264  inline constexpr bool __is_reverse_view = false;
3265 
3266  template<typename _Vp>
3267  inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3268  }
3269 
3270  inline constexpr __adaptor::_RangeAdaptorClosure reverse
3271  = [] <viewable_range _Range> (_Range&& __r)
3272  {
3273  using _Tp = remove_cvref_t<_Range>;
3274  if constexpr (__detail::__is_reverse_view<_Tp>)
3275  return std::forward<_Range>(__r).base();
3276  else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3277  {
3278  using _Iter = decltype(ranges::begin(__r).base());
3279  if constexpr (sized_range<_Tp>)
3280  return subrange<_Iter, _Iter, subrange_kind::sized>
3281  (__r.end().base(), __r.begin().base(), __r.size());
3282  else
3283  return subrange<_Iter, _Iter, subrange_kind::unsized>
3284  (__r.end().base(), __r.begin().base());
3285  }
3286  else
3287  return reverse_view{std::forward<_Range>(__r)};
3288  };
3289  } // namespace views
3290 
3291  namespace __detail
3292  {
3293  template<typename _Tp, size_t _Nm>
3294  concept __has_tuple_element = requires(_Tp __t)
3295  {
3296  typename tuple_size<_Tp>::type;
3297  requires _Nm < tuple_size_v<_Tp>;
3298  typename tuple_element_t<_Nm, _Tp>;
3299  { std::get<_Nm>(__t) }
3300  -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3301  };
3302  }
3303 
3304  template<input_range _Vp, size_t _Nm>
3305  requires view<_Vp>
3306  && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3307  && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3308  _Nm>
3309  class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3310  {
3311  public:
3312  elements_view() = default;
3313 
3314  constexpr explicit
3315  elements_view(_Vp base)
3316  : _M_base(std::move(base))
3317  { }
3318 
3319  constexpr _Vp
3320  base() const& requires copy_constructible<_Vp>
3321  { return _M_base; }
3322 
3323  constexpr _Vp
3324  base() &&
3325  { return std::move(_M_base); }
3326 
3327  constexpr auto
3328  begin() requires (!__detail::__simple_view<_Vp>)
3329  { return _Iterator<false>(ranges::begin(_M_base)); }
3330 
3331  constexpr auto
3332  begin() const requires __detail::__simple_view<_Vp>
3333  { return _Iterator<true>(ranges::begin(_M_base)); }
3334 
3335  constexpr auto
3336  end() requires (!__detail::__simple_view<_Vp>)
3337  { return ranges::end(_M_base); }
3338 
3339  constexpr auto
3340  end() const requires __detail::__simple_view<_Vp>
3341  { return ranges::end(_M_base); }
3342 
3343  constexpr auto
3344  size() requires sized_range<_Vp>
3345  { return ranges::size(_M_base); }
3346 
3347  constexpr auto
3348  size() const requires sized_range<const _Vp>
3349  { return ranges::size(_M_base); }
3350 
3351  private:
3352  template<bool _Const>
3353  struct _Iterator
3354  {
3355  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3356 
3357  iterator_t<_Base> _M_current = iterator_t<_Base>();
3358 
3359  friend _Iterator<!_Const>;
3360 
3361  public:
3362  using iterator_category
3363  = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3364  using value_type
3365  = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3366  using difference_type = range_difference_t<_Base>;
3367 
3368  _Iterator() = default;
3369 
3370  constexpr explicit
3371  _Iterator(iterator_t<_Base> current)
3372  : _M_current(std::move(current))
3373  { }
3374 
3375  constexpr
3376  _Iterator(_Iterator<!_Const> i)
3377  requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3378  : _M_current(std::move(i._M_current))
3379  { }
3380 
3381  constexpr iterator_t<_Base>
3382  base() const&
3383  requires copyable<iterator_t<_Base>>
3384  { return _M_current; }
3385 
3386  constexpr iterator_t<_Base>
3387  base() &&
3388  { return std::move(_M_current); }
3389 
3390  constexpr decltype(auto)
3391  operator*() const
3392  { return std::get<_Nm>(*_M_current); }
3393 
3394  constexpr _Iterator&
3395  operator++()
3396  {
3397  ++_M_current;
3398  return *this;
3399  }
3400 
3401  constexpr void
3402  operator++(int) requires (!forward_range<_Base>)
3403  { ++_M_current; }
3404 
3405  constexpr _Iterator
3406  operator++(int) requires forward_range<_Base>
3407  {
3408  auto __tmp = *this;
3409  ++_M_current;
3410  return __tmp;
3411  }
3412 
3413  constexpr _Iterator&
3414  operator--() requires bidirectional_range<_Base>
3415  {
3416  --_M_current;
3417  return *this;
3418  }
3419 
3420  constexpr _Iterator
3421  operator--(int) requires bidirectional_range<_Base>
3422  {
3423  auto __tmp = *this;
3424  --_M_current;
3425  return __tmp;
3426  }
3427 
3428  constexpr _Iterator&
3429  operator+=(difference_type __n)
3430  requires random_access_range<_Base>
3431  {
3432  _M_current += __n;
3433  return *this;
3434  }
3435 
3436  constexpr _Iterator&
3437  operator-=(difference_type __n)
3438  requires random_access_range<_Base>
3439  {
3440  _M_current -= __n;
3441  return *this;
3442  }
3443 
3444  constexpr decltype(auto)
3445  operator[](difference_type __n) const
3446  requires random_access_range<_Base>
3447  { return std::get<_Nm>(*(_M_current + __n)); }
3448 
3449  friend constexpr bool
3450  operator==(const _Iterator& __x, const _Iterator& __y)
3451  requires equality_comparable<iterator_t<_Base>>
3452  { return __x._M_current == __y._M_current; }
3453 
3454  friend constexpr bool
3455  operator==(const _Iterator& __x, const sentinel_t<_Base>& __y)
3456  { return __x._M_current == __y; }
3457 
3458  friend constexpr bool
3459  operator<(const _Iterator& __x, const _Iterator& __y)
3460  requires random_access_range<_Base>
3461  { return __x._M_current < __y._M_current; }
3462 
3463  friend constexpr bool
3464  operator>(const _Iterator& __x, const _Iterator& __y)
3465  requires random_access_range<_Base>
3466  { return __y._M_current < __x._M_current; }
3467 
3468  friend constexpr bool
3469  operator<=(const _Iterator& __x, const _Iterator& __y)
3470  requires random_access_range<_Base>
3471  { return !(__y._M_current > __x._M_current); }
3472 
3473  friend constexpr bool
3474  operator>=(const _Iterator& __x, const _Iterator& __y)
3475  requires random_access_range<_Base>
3476  { return !(__x._M_current > __y._M_current); }
3477 
3478 #ifdef __cpp_lib_three_way_comparison
3479  friend constexpr auto
3480  operator<=>(const _Iterator& __x, const _Iterator& __y)
3481  requires random_access_range<_Base>
3482  && three_way_comparable<iterator_t<_Base>>
3483  { return __x._M_current <=> __y._M_current; }
3484 #endif
3485 
3486  friend constexpr _Iterator
3487  operator+(const _Iterator& __x, difference_type __y)
3488  requires random_access_range<_Base>
3489  { return _Iterator{__x} += __y; }
3490 
3491  friend constexpr _Iterator
3492  operator+(difference_type __x, const _Iterator& __y)
3493  requires random_access_range<_Base>
3494  { return __y + __x; }
3495 
3496  friend constexpr _Iterator
3497  operator-(const _Iterator& __x, difference_type __y)
3498  requires random_access_range<_Base>
3499  { return _Iterator{__x} -= __y; }
3500 
3501  friend constexpr difference_type
3502  operator-(const _Iterator& __x, const _Iterator& __y)
3503  requires random_access_range<_Base>
3504  { return __x._M_current - __y._M_current; }
3505 
3506  friend constexpr difference_type
3507  operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y)
3508  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3509  { return __x._M_current - __y; }
3510 
3511  friend constexpr difference_type
3512  operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y)
3513  requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
3514  { return -(__y - __x); }
3515  };
3516 
3517  _Vp _M_base = _Vp();
3518  };
3519 
3520  template<typename _Range>
3521  using keys_view = elements_view<views::all_t<_Range>, 0>;
3522 
3523  template<typename _Range>
3524  using values_view = elements_view<views::all_t<_Range>, 1>;
3525 
3526  namespace views
3527  {
3528  template<size_t _Nm>
3529  inline constexpr __adaptor::_RangeAdaptorClosure elements
3530  = [] <viewable_range _Range> (_Range&& __r)
3531  {
3532  using _El = elements_view<views::all_t<_Range>, _Nm>;
3533  return _El{std::forward<_Range>(__r)};
3534  };
3535 
3536  inline constexpr __adaptor::_RangeAdaptorClosure keys = elements<0>;
3537  inline constexpr __adaptor::_RangeAdaptorClosure values = elements<1>;
3538  } // namespace views
3539 
3540 } // namespace ranges
3541 
3542  namespace views = ranges::views;
3543 
3544  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3545  struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
3546  : integral_constant<size_t, 2>
3547  { };
3548 
3549  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3550  struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
3551  { using type = _Iter; };
3552 
3553  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3554  struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
3555  { using type = _Sent; };
3556 
3557  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3558  struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
3559  { using type = _Iter; };
3560 
3561  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
3562  struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
3563  { using type = _Sent; };
3564 
3565 _GLIBCXX_END_NAMESPACE_VERSION
3566 } // namespace
3567 #endif // library concepts
3568 #endif // C++2a
3569 #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