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 <compare>
42 #include <initializer_list>
43 #include <iterator>
44 #include <limits>
45 #include <optional>
46 
47 /**
48  * @defgroup ranges Ranges
49  *
50  * Components for dealing with ranges of elements.
51  */
52 
53 namespace std _GLIBCXX_VISIBILITY(default)
54 {
55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
56 namespace ranges
57 {
58  // [range.range] The range concept.
59  // [range.sized] The sized_range concept.
60  // Defined in <bits/range_access.h>
61 
62  // [range.refinements]
63  // Defined in <bits/range_access.h>
64 
65  struct view_base { };
66 
67  namespace __detail
68  {
69  template<typename _Tp>
70  concept __deep_const_range = range<_Tp> && range<const _Tp>
71  && same_as<range_reference_t<_Tp>, range_reference_t<const _Tp>>;
72 
73  template<typename _Tp>
74  inline constexpr bool __enable_view_impl
75  = derived_from<_Tp, view_base> || (!__deep_const_range<_Tp>);
76 
77  template<typename _Tp>
78  inline constexpr bool __enable_view_impl<std::initializer_list<_Tp>>
79  = false;
80 
81  } // namespace __detail
82 
83  template<typename _Tp>
84  inline constexpr bool enable_view
85  = __detail::__enable_view_impl<remove_cv_t<_Tp>>;
86 
87  template<typename _Tp>
88  concept view
89  = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
90  && enable_view<_Tp>;
91 
92  /// A range which can be safely converted to a view.
93  template<typename _Tp>
94  concept viewable_range = range<_Tp>
95  && (safe_range<_Tp> || view<decay_t<_Tp>>);
96 
97  namespace __detail
98  {
99  template<typename _Range>
100  concept __simple_view = view<_Range> && range<const _Range>
101  && same_as<iterator_t<_Range>, iterator_t<const _Range>>
102  && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
103 
104  template<typename _It>
105  concept __has_arrow = input_iterator<_It>
106  && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
107 
108  template<typename _Tp, typename _Up>
109  concept __not_same_as
110  = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
111  } // namespace __detail
112 
113  template<typename _Derived>
114  requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
115  class view_interface : public view_base
116  {
117  private:
118  constexpr _Derived& _M_derived() noexcept
119  {
120  static_assert(derived_from<_Derived, view_interface<_Derived>>);
121  static_assert(view<_Derived>);
122  return static_cast<_Derived&>(*this);
123  }
124 
125  constexpr const _Derived& _M_derived() const noexcept
126  {
127  static_assert(derived_from<_Derived, view_interface<_Derived>>);
128  static_assert(view<_Derived>);
129  return static_cast<const _Derived&>(*this);
130  }
131 
132  public:
133  constexpr bool
134  empty() requires forward_range<_Derived>
135  { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
136 
137  constexpr bool
138  empty() const requires forward_range<const _Derived>
139  { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
140 
141  constexpr explicit
142  operator bool() requires requires { ranges::empty(_M_derived()); }
143  { return !ranges::empty(_M_derived()); }
144 
145  constexpr explicit
146  operator bool() const requires requires { ranges::empty(_M_derived()); }
147  { return !ranges::empty(_M_derived()); }
148 
149  constexpr auto
150  data() requires contiguous_iterator<iterator_t<_Derived>>
151  { return to_address(ranges::begin(_M_derived())); }
152 
153  constexpr auto
154  data() const
155  requires range<const _Derived>
156  && contiguous_iterator<iterator_t<const _Derived>>
157  { return to_address(ranges::begin(_M_derived())); }
158 
159  constexpr auto
160  size()
161  requires forward_range<_Derived>
162  && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
163  { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
164 
165  constexpr auto
166  size() const
167  requires forward_range<const _Derived>
168  && sized_sentinel_for<sentinel_t<const _Derived>,
169  iterator_t<const _Derived>>
170  { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
171 
172  constexpr decltype(auto)
173  front() requires forward_range<_Derived>
174  {
175  __glibcxx_assert(!empty());
176  return *ranges::begin(_M_derived());
177  }
178 
179  constexpr decltype(auto)
180  front() const requires forward_range<const _Derived>
181  {
182  __glibcxx_assert(!empty());
183  return *ranges::begin(_M_derived());
184  }
185 
186  constexpr decltype(auto)
187  back()
188  requires bidirectional_range<_Derived> && common_range<_Derived>
189  {
190  __glibcxx_assert(!empty());
191  return *ranges::prev(ranges::end(_M_derived()));
192  }
193 
194  constexpr decltype(auto)
195  back() const
196  requires bidirectional_range<const _Derived>
197  && common_range<const _Derived>
198  {
199  __glibcxx_assert(!empty());
200  return *ranges::prev(ranges::end(_M_derived()));
201  }
202 
203  template<random_access_range _Range = _Derived>
204  constexpr decltype(auto)
205  operator[](range_difference_t<_Range> __n)
206  { return ranges::begin(_M_derived())[__n]; }
207 
208  template<random_access_range _Range = const _Derived>
209  constexpr decltype(auto)
210  operator[](range_difference_t<_Range> __n) const
211  { return ranges::begin(_M_derived())[__n]; }
212  };
213 
214  namespace __detail
215  {
216  template<typename _Tp>
217  concept __pair_like
218  = !is_reference_v<_Tp> && requires(_Tp __t)
219  {
220  typename tuple_size<_Tp>::type;
221  requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
222  typename tuple_element_t<0, remove_const_t<_Tp>>;
223  typename tuple_element_t<1, remove_const_t<_Tp>>;
224  { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
225  { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
226  };
227 
228  template<typename _Tp, typename _Up, typename _Vp>
229  concept __pair_like_convertible_to
230  = !range<_Tp> && __pair_like<remove_reference_t<_Tp>>
231  && requires(_Tp&& __t)
232  {
233  { get<0>(std::forward<_Tp>(__t)) } -> convertible_to<_Up>;
234  { get<1>(std::forward<_Tp>(__t)) } -> convertible_to<_Vp>;
235  };
236 
237  template<typename _Tp, typename _Up, typename _Vp>
238  concept __pair_like_convertible_from
239  = !range<_Tp> && __pair_like<_Tp>
240  && constructible_from<_Tp, _Up, _Vp>;
241 
242  template<typename _Tp>
243  concept __iterator_sentinel_pair
244  = !range<_Tp> && __pair_like<_Tp>
245  && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
246 
247  } // namespace __detail
248 
249  enum class subrange_kind : bool { unsized, sized };
250 
251  template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
252  subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
253  ? subrange_kind::sized : subrange_kind::unsized>
254  requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
255  class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
256  {
257  private:
258  static constexpr bool _S_store_size
259  = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
260 
261  _It _M_begin = _It();
262  _Sent _M_end = _Sent();
263 
264  template<typename, bool = _S_store_size>
265  struct _Size
266  { };
267 
268  template<typename _Tp>
269  struct _Size<_Tp, true>
270  { __detail::__make_unsigned_like_t<_Tp> _M_size; };
271 
272  [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
273 
274  public:
275  subrange() = default;
276 
277  constexpr
278  subrange(_It __i, _Sent __s) requires (!_S_store_size)
279  : _M_begin(std::move(__i)), _M_end(__s)
280  { }
281 
282  constexpr
283  subrange(_It __i, _Sent __s,
284  __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
285  requires (_Kind == subrange_kind::sized)
286  : _M_begin(std::move(__i)), _M_end(__s)
287  {
288  using __detail::__to_unsigned_like;
289  __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
290  if constexpr (_S_store_size)
291  _M_size._M_size = __n;
292  }
293 
294  template<__detail::__not_same_as<subrange> _Rng>
295  requires safe_range<_Rng>
296  && convertible_to<iterator_t<_Rng>, _It>
297  && convertible_to<sentinel_t<_Rng>, _Sent>
298  constexpr
299  subrange(_Rng&& __r) requires (!_S_store_size || sized_range<_Rng>)
300  : subrange{ranges::begin(__r), ranges::end(__r)}
301  {
302  if constexpr (_S_store_size)
303  _M_size._M_size = ranges::size(__r);
304  }
305 
306  template<safe_range _Rng>
307  requires convertible_to<iterator_t<_Rng>, _It>
308  && convertible_to<sentinel_t<_Rng>, _Sent>
309  constexpr
310  subrange(_Rng&& __r,
311  __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
312  requires (_Kind == subrange_kind::sized)
313  : subrange{ranges::begin(__r), ranges::end(__r), __n}
314  { }
315 
316  template<__detail::__not_same_as<subrange> _PairLike>
317  requires __detail::__pair_like_convertible_to<_PairLike, _It, _Sent>
318  constexpr
319  subrange(_PairLike&& __r) requires (!_S_store_size)
320  : subrange{std::get<0>(std::forward<_PairLike>(__r)),
321  std::get<1>(std::forward<_PairLike>(__r))}
322  { }
323 
324  template<__detail::__pair_like_convertible_to<_It, _Sent> _PairLike>
325  constexpr
326  subrange(_PairLike&& __r,
327  __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
328  requires (_Kind == subrange_kind::sized)
329  : subrange{std::get<0>(std::forward<_PairLike>(__r)),
330  std::get<1>(std::forward<_PairLike>(__r)), __n}
331  { }
332 
333  template<__detail::__not_same_as<subrange> _PairLike>
334  requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
335  const _Sent&>
336  constexpr
337  operator _PairLike() const
338  { return _PairLike(_M_begin, _M_end); }
339 
340  constexpr _It
341  begin() const requires copyable<_It>
342  { return _M_begin; }
343 
344  [[nodiscard]] constexpr _It
345  begin() requires (!copyable<_It>)
346  { return std::move(_M_begin); }
347 
348  constexpr _Sent end() const { return _M_end; }
349 
350  constexpr bool empty() const { return _M_begin == _M_end; }
351 
352  constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
353  size() const requires (_Kind == subrange_kind::sized)
354  {
355  if constexpr (_S_store_size)
356  return _M_size._M_size;
357  else
358  return __detail::__to_unsigned_like(_M_end - _M_begin);
359  }
360 
361  [[nodiscard]] constexpr subrange
362  next(iter_difference_t<_It> __n = 1) const &
363  requires forward_iterator<_It>
364  {
365  auto __tmp = *this;
366  __tmp.advance(__n);
367  return __tmp;
368  }
369 
370  [[nodiscard]] constexpr subrange
371  next(iter_difference_t<_It> __n = 1) &&
372  {
373  advance(__n);
374  return std::move(*this);
375  }
376 
377  [[nodiscard]] constexpr subrange
378  prev(iter_difference_t<_It> __n = 1) const
379  requires bidirectional_iterator<_It>
380  {
381  auto __tmp = *this;
382  __tmp.advance(--__n);
383  return __tmp;
384  }
385 
386  constexpr subrange&
387  advance(iter_difference_t<_It> __n)
388  {
389  if constexpr (_S_store_size)
390  {
391  auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
392  if (__d >= 0)
393  _M_size._M_size -= __detail::__to_unsigned_like(__d);
394  else
395  _M_size._M_size += __detail::__to_unsigned_like(-__d);
396  }
397  else
398  ranges::advance(_M_begin, __n, _M_end);
399  return *this;
400  }
401  };
402 
403  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
404  subrange(_It, _Sent,
405  __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
406  -> subrange<_It, _Sent, subrange_kind::sized>;
407 
408  template<__detail::__iterator_sentinel_pair _Pr>
409  subrange(_Pr)
410  -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
411 
412  template<__detail::__iterator_sentinel_pair _Pr>
413  subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
414  tuple_element_t<0, _Pr>>>)
415  -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
416  subrange_kind::sized>;
417 
418  template<safe_range _Rng>
419  subrange(_Rng&&)
420  -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
421  (sized_range<_Rng>
422  || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
423  ? subrange_kind::sized : subrange_kind::unsized>;
424 
425  template<safe_range _Rng>
426  subrange(_Rng&&,
427  __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
428  -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
429 
430  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
431  requires (_Num < 2)
432  constexpr auto
433  get(const subrange<_It, _Sent, _Kind>& __r)
434  {
435  if constexpr (_Num == 0)
436  return __r.begin();
437  else
438  return __r.end();
439  }
440 
441  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
442  requires (_Num < 2)
443  constexpr auto
444  get(subrange<_It, _Sent, _Kind>&& __r)
445  {
446  if constexpr (_Num == 0)
447  return __r.begin();
448  else
449  return __r.end();
450  }
451 
452  template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
453  subrange_kind _Kind>
454  inline constexpr bool
455  enable_safe_range<subrange<_It, _Sent, _Kind>> = true;
456 
457 } // namespace ranges
458 
459  using ranges::get;
460 
461 namespace ranges
462 {
463  /// Type returned by algorithms instead of a dangling iterator or subrange.
464  struct dangling
465  {
466  constexpr dangling() noexcept = default;
467  template<typename... _Args>
468  constexpr dangling(_Args&&...) noexcept { }
469  };
470 
471  template<range _Range>
472  using safe_iterator_t = conditional_t<safe_range<_Range>,
473  iterator_t<_Range>,
474  dangling>;
475 
476  template<range _Range>
477  using safe_subrange_t = conditional_t<safe_range<_Range>,
478  subrange<iterator_t<_Range>>,
479  dangling>;
480 
481  template<typename _Tp> requires is_object_v<_Tp>
482  class empty_view
483  : public view_interface<empty_view<_Tp>>
484  {
485  public:
486  static constexpr _Tp* begin() noexcept { return nullptr; }
487  static constexpr _Tp* end() noexcept { return nullptr; }
488  static constexpr _Tp* data() noexcept { return nullptr; }
489  static constexpr size_t size() noexcept { return 0; }
490  static constexpr bool empty() noexcept { return true; }
491  };
492 
493  template<typename _Tp>
494  inline constexpr bool enable_safe_range<empty_view<_Tp>> = true;
495 
496  namespace __detail
497  {
498  template<copy_constructible _Tp> requires is_object_v<_Tp>
499  struct __box : std::optional<_Tp>
500  {
501  using std::optional<_Tp>::optional;
502 
503  constexpr
504  __box()
505  noexcept(is_nothrow_default_constructible_v<_Tp>)
506  requires default_initializable<_Tp>
507  : std::optional<_Tp>{std::in_place}
508  { }
509 
510  using std::optional<_Tp>::operator=;
511 
512  __box&
513  operator=(const __box& __that)
514  noexcept(is_nothrow_copy_constructible_v<_Tp>)
515  requires (!assignable_from<_Tp&, const _Tp&>)
516  {
517  if ((bool)__that)
518  this->emplace(*__that);
519  else
520  this->reset();
521  return *this;
522  }
523 
524  __box&
525  operator=(__box&& __that)
526  noexcept(is_nothrow_move_constructible_v<_Tp>)
527  requires (!assignable_from<_Tp&, _Tp>)
528  {
529  if ((bool)__that)
530  this->emplace(std::move(*__that));
531  else
532  this->reset();
533  return *this;
534  }
535  };
536 
537  } // namespace __detail
538 
539  /// A view that contains exactly one element.
540  template<copy_constructible _Tp> requires is_object_v<_Tp>
541  class single_view : public view_interface<single_view<_Tp>>
542  {
543  public:
544  single_view() = default;
545 
546  constexpr explicit
547  single_view(const _Tp& __t)
548  : _M_value(__t)
549  { }
550 
551  constexpr explicit
552  single_view(_Tp&& __t)
553  : _M_value(std::move(__t))
554  { }
555 
556  template<typename... _Args>
557  requires constructible_from<_Tp, _Args...>
558  constexpr
559  single_view(in_place_t, _Args&&... __args)
560  : _M_value{in_place, std::forward<_Args>(__args)...}
561  { }
562 
563  constexpr _Tp*
564  begin() noexcept
565  { return data(); }
566 
567  constexpr const _Tp*
568  begin() const noexcept
569  { return data(); }
570 
571  constexpr _Tp*
572  end() noexcept
573  { return data() + 1; }
574 
575  constexpr const _Tp*
576  end() const noexcept
577  { return data() + 1; }
578 
579  static constexpr size_t
580  size() noexcept
581  { return 1; }
582 
583  constexpr _Tp*
584  data() noexcept
585  { return _M_value.operator->(); }
586 
587  constexpr const _Tp*
588  data() const noexcept
589  { return _M_value.operator->(); }
590 
591  private:
592  __detail::__box<_Tp> _M_value;
593  };
594 
595  namespace __detail
596  {
597  template<typename _Wp>
598  constexpr auto __to_signed_like(_Wp __w) noexcept
599  {
600  if constexpr (!integral<_Wp>)
601  return iter_difference_t<_Wp>();
602  else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
603  return iter_difference_t<_Wp>(__w);
604  else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
605  return ptrdiff_t(__w);
606  else if constexpr (sizeof(long long) > sizeof(_Wp))
607  return (long long)(__w);
608 #ifdef __SIZEOF_INT128__
609  else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
610  return __int128(__w);
611 #endif
612  else
613  return __max_diff_type(__w);
614  }
615 
616  template<typename _Wp>
617  using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
618 
619  template<typename _It>
620  concept __decrementable = incrementable<_It>
621  && requires(_It __i)
622  {
623  { --__i } -> same_as<_It&>;
624  { __i-- } -> same_as<_It>;
625  };
626 
627  template<typename _It>
628  concept __advanceable = __decrementable<_It> && totally_ordered<_It>
629  && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
630  {
631  { __i += __n } -> same_as<_It&>;
632  { __i -= __n } -> same_as<_It&>;
633  _It(__j + __n);
634  _It(__n + __j);
635  _It(__j - __n);
636  { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
637  };
638 
639  } // namespace __detail
640 
641  template<weakly_incrementable _Winc,
642  semiregular _Bound = unreachable_sentinel_t>
643  requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
644  class iota_view : public view_interface<iota_view<_Winc, _Bound>>
645  {
646  private:
647  struct _Iterator
648  {
649  private:
650  static auto
651  _S_iter_cat()
652  {
653  using namespace __detail;
654  if constexpr (__advanceable<_Winc>)
655  return random_access_iterator_tag{};
656  else if constexpr (__decrementable<_Winc>)
657  return bidirectional_iterator_tag{};
658  else if constexpr (incrementable<_Winc>)
659  return forward_iterator_tag{};
660  else
661  return input_iterator_tag{};
662  }
663 
664  public:
665  using iterator_category = decltype(_S_iter_cat());
666  using value_type = _Winc;
667  using difference_type = __detail::__iota_diff_t<_Winc>;
668 
669  _Iterator() = default;
670 
671  constexpr explicit
672  _Iterator(_Winc __value)
673  : _M_value(__value) { }
674 
675  constexpr _Winc
676  operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
677  { return _M_value; }
678 
679  constexpr _Iterator&
680  operator++()
681  {
682  ++_M_value;
683  return *this;
684  }
685 
686  constexpr void
687  operator++(int)
688  { ++*this; }
689 
690  constexpr _Iterator
691  operator++(int) requires incrementable<_Winc>
692  {
693  auto __tmp = *this;
694  ++*this;
695  return __tmp;
696  }
697 
698  constexpr _Iterator&
699  operator--() requires __detail::__decrementable<_Winc>
700  {
701  --_M_value;
702  return *this;
703  }
704 
705  constexpr _Iterator
706  operator--(int) requires __detail::__decrementable<_Winc>
707  {
708  auto __tmp = *this;
709  --*this;
710  return __tmp;
711  }
712 
713  constexpr _Iterator&
714  operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
715  {
716  using __detail::__is_integer_like;
717  using __detail::__is_signed_integer_like;
718  if constexpr (__is_integer_like<_Winc>
719  && !__is_signed_integer_like<_Winc>)
720  {
721  if (__n >= difference_type(0))
722  _M_value += static_cast<_Winc>(__n);
723  else
724  _M_value -= static_cast<_Winc>(-__n);
725  }
726  else
727  _M_value += __n;
728  return *this;
729  }
730 
731  constexpr _Iterator&
732  operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
733  {
734  using __detail::__is_integer_like;
735  using __detail::__is_signed_integer_like;
736  if constexpr (__is_integer_like<_Winc>
737  && !__is_signed_integer_like<_Winc>)
738  {
739  if (__n >= difference_type(0))
740  _M_value -= static_cast<_Winc>(__n);
741  else
742  _M_value += static_cast<_Winc>(-__n);
743  }
744  else
745  _M_value -= __n;
746  return *this;
747  }
748 
749  constexpr _Winc
750  operator[](difference_type __n) const
751  requires __detail::__advanceable<_Winc>
752  { return _Winc(_M_value + __n); }
753 
754  friend constexpr bool
755  operator==(const _Iterator& __x, const _Iterator& __y)
756  requires equality_comparable<_Winc>
757  { return __x._M_value == __y._M_value; }
758 
759  friend constexpr bool
760  operator<(const _Iterator& __x, const _Iterator& __y)
761  requires totally_ordered<_Winc>
762  { return __x._M_value < __y._M_value; }
763 
764  friend constexpr bool
765  operator>(const _Iterator& __x, const _Iterator& __y)
766  requires totally_ordered<_Winc>
767  { return __y < __x; }
768 
769  friend constexpr bool
770  operator<=(const _Iterator& __x, const _Iterator& __y)
771  requires totally_ordered<_Winc>
772  { return !(__y < __x); }
773 
774  friend constexpr bool
775  operator>=(const _Iterator& __x, const _Iterator& __y)
776  requires totally_ordered<_Winc>
777  { return !(__x < __y); }
778 
779 #ifdef __cpp_lib_threeway_comparison
780  friend constexpr compare_three_way_result_t<_Winc>
781  operator<=>(const _Iterator& __x, const _Iterator& __y)
782  requires totally_ordered<_Winc> && three_way_comparable<_Winc>
783  { return __x._M_value <=> __y._M_value; }
784 #endif
785 
786  friend constexpr _Iterator
787  operator+(_Iterator __i, difference_type __n)
788  requires __detail::__advanceable<_Winc>
789  { return __i += __n; }
790 
791  friend constexpr _Iterator
792  operator+(difference_type __n, _Iterator __i)
793  requires __detail::__advanceable<_Winc>
794  { return __i += __n; }
795 
796  friend constexpr _Iterator
797  operator-(_Iterator __i, difference_type __n)
798  requires __detail::__advanceable<_Winc>
799  { return __i -= __n; }
800 
801  friend constexpr difference_type
802  operator-(const _Iterator& __x, const _Iterator& __y)
803  requires __detail::__advanceable<_Winc>
804  {
805  using __detail::__is_integer_like;
806  using __detail::__is_signed_integer_like;
807  using _Dt = difference_type;
808  if constexpr (__is_integer_like<_Winc>)
809  {
810  if constexpr (__is_signed_integer_like<_Winc>)
811  return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
812  else
813  return (__y._M_value > __x._M_value)
814  ? _Dt(-_Dt(__y._M_value - __x._M_value))
815  : _Dt(__x._M_value - __y._M_value);
816  }
817  else
818  return __x._M_value - __y._M_value;
819  }
820 
821  private:
822  _Winc _M_value = _Winc();
823  };
824 
825  struct _Sentinel
826  {
827  private:
828  _Bound _M_bound = _Bound();
829 
830  public:
831  _Sentinel() = default;
832 
833  constexpr explicit
834  _Sentinel(_Bound __bound)
835  : _M_bound(__bound) { }
836 
837  friend constexpr bool
838  operator==(const _Iterator& __x, const _Sentinel& __y)
839  { return __x._M_value == __y._M_bound; }
840 
841  friend constexpr iter_difference_t<_Winc>
842  operator-(const _Iterator& __x, const _Sentinel& __y)
843  requires sized_sentinel_for<_Bound, _Winc>
844  { return __x._M_value - __y._M_bound; }
845 
846  friend constexpr iter_difference_t<_Winc>
847  operator-(const _Sentinel& __x, const _Iterator& __y)
848  requires sized_sentinel_for<_Bound, _Winc>
849  { return -(__y - __x); }
850  };
851 
852  _Winc _M_value = _Winc();
853  _Bound _M_bound = _Bound();
854 
855  public:
856  iota_view() = default;
857 
858  constexpr explicit
859  iota_view(_Winc __value)
860  : _M_value(__value)
861  { }
862 
863  constexpr
864  iota_view(type_identity_t<_Winc> __value,
865  type_identity_t<_Bound> __bound)
866  : _M_value(__value), _M_bound(__bound)
867  {
868  if constexpr (totally_ordered_with<_Winc, _Bound>)
869  __glibcxx_assert( bool(__value <= __bound) );
870  }
871 
872  constexpr _Iterator
873  begin() const { return _Iterator{_M_value}; }
874 
875  constexpr auto
876  end() const
877  {
878  if constexpr (same_as<_Bound, unreachable_sentinel_t>)
879  return unreachable_sentinel;
880  else
881  return _Sentinel{_M_bound};
882  }
883 
884  constexpr _Iterator
885  end() const requires same_as<_Winc, _Bound>
886  { return _Iterator{_M_bound}; }
887 
888  constexpr auto
889  size() const
890  requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
891  || (integral<_Winc> && integral<_Bound>)
892  || sized_sentinel_for<_Bound, _Winc>
893  {
894  using __detail::__is_integer_like;
895  using __detail::__to_unsigned_like;
896  if constexpr (__is_integer_like<_Winc> && __is_integer_like<_Bound>)
897  return (_M_value < 0)
898  ? ((_M_bound < 0)
899  ? __to_unsigned_like(-_M_value) - __to_unsigned_like(-_M_bound)
900  : __to_unsigned_like(_M_bound) + __to_unsigned_like(-_M_value))
901  : __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
902  else
903  return __to_unsigned_like(_M_bound - _M_value);
904  }
905  };
906 
907  template<typename _Winc, typename _Bound>
908  requires (!__detail::__is_integer_like<_Winc>
909  || !__detail::__is_integer_like<_Bound>
910  || (__detail::__is_signed_integer_like<_Winc>
911  == __detail::__is_signed_integer_like<_Bound>))
912  iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
913 
914  template<weakly_incrementable _Winc, semiregular _Bound>
915  inline constexpr bool enable_safe_range<iota_view<_Winc, _Bound>> = true;
916 
917 namespace views
918 {
919  template<typename _Tp>
920  inline constexpr empty_view<_Tp> empty{};
921 
922  struct _Single
923  {
924  template<typename _Tp>
925  auto
926  operator()(_Tp&& __e) const
927  { return single_view{std::forward<_Tp>(__e)}; }
928  };
929 
930  inline constexpr _Single single{};
931 
932  struct _Iota
933  {
934  template<typename _Tp>
935  auto
936  operator()(_Tp&& __e) const
937  { return iota_view{std::forward<_Tp>(__e)}; }
938 
939  template<typename _Tp, typename _Up>
940  auto
941  operator()(_Tp&& __e, _Up&& __f) const
942  { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; }
943  };
944 
945  inline constexpr _Iota iota{};
946 
947 } // namespace views
948 } // namespace ranges
949 _GLIBCXX_END_NAMESPACE_VERSION
950 } // namespace
951 #endif // library concepts
952 #endif // C++2a
953 #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::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
std::experimental::fundamentals_v1::in_place
constexpr in_place_t in_place
Tag for in-place construction.
Definition: experimental/optional:77
std
ISO C++ entities toplevel namespace is std.
std::iota
void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
Definition: stl_numeric.h:87
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:202
limits
initializer_list
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::operator+
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:331
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
concepts
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
compare