[range.utility] - C++17 → C++20

Files changed (1) hide show

tmp/tmpsgk6o4n8/{from.md → to.md} +459 -0

tmp/tmpsgk6o4n8/{from.md → to.md} RENAMED Viewed

	@@ -0,0 +1,459 @@

+## Range utilities <a id="range.utility">[[range.utility]]</a>
+The components in this subclause are general utilities for representing
+and manipulating ranges.
+### Helper concepts <a id="range.utility.helpers">[[range.utility.helpers]]</a>
+Many of the types in subclause  [[range.utility]] are specified in terms
+of the following exposition-only concepts:
+``` cpp
+template<class R>
+  concept simple-view =                         // exposition only
+    view<R> && range<const R> &&
+    same_as<iterator_t<R>, iterator_t<const R>> &&
+    same_as<sentinel_t<R>, sentinel_t<const R>>;
+template<class I>
+  concept has-arrow =                           // exposition only
+    input_iterator<I> && (is_pointer_v<I> || requires(I i) { i.operator->(); });
+template<class T, class U>
+  concept not-same-as =                         // exposition only
+    !same_as<remove_cvref_t<T>, remove_cvref_t<U>>;
+```
+### View interface <a id="view.interface">[[view.interface]]</a>
+The class template `view_interface` is a helper for defining `view`-like
+types that offer a container-like interface. It is parameterized with
+the type that is derived from it.
+``` cpp
+namespace std::ranges {
+  template<class D>
+    requires is_class_v<D> && same_as<D, remove_cv_t<D>>
+  class view_interface : public view_base {
+  private:
+    constexpr D& derived() noexcept {                   // exposition only
+      return static_cast<D&>(*this);
+    }
+    constexpr const D& derived() const noexcept {       // exposition only
+      return static_cast<const D&>(*this);
+    }
+  public:
+    constexpr bool empty() requires forward_range<D> {
+      return ranges::begin(derived()) == ranges::end(derived());
+    }
+    constexpr bool empty() const requires forward_range<const D> {
+      return ranges::begin(derived()) == ranges::end(derived());
+    }
+    constexpr explicit operator bool()
+      requires requires { ranges::empty(derived()); } {
+        return !ranges::empty(derived());
+      }
+    constexpr explicit operator bool() const
+      requires requires { ranges::empty(derived()); } {
+        return !ranges::empty(derived());
+      }
+    constexpr auto data() requires contiguous_iterator<iterator_t<D>> {
+      return to_address(ranges::begin(derived()));
+    }
+    constexpr auto data() const
+      requires range<const D> && contiguous_iterator<iterator_t<const D>> {
+        return to_address(ranges::begin(derived()));
+      }
+    constexpr auto size() requires forward_range<D> &&
+      sized_sentinel_for<sentinel_t<D>, iterator_t<D>> {
+        return ranges::end(derived()) - ranges::begin(derived());
+      }
+    constexpr auto size() const requires forward_range<const D> &&
+      sized_sentinel_for<sentinel_t<const D>, iterator_t<const D>> {
+        return ranges::end(derived()) - ranges::begin(derived());
+      }
+    constexpr decltype(auto) front() requires forward_range<D>;
+    constexpr decltype(auto) front() const requires forward_range<const D>;
+    constexpr decltype(auto) back() requires bidirectional_range<D> && common_range<D>;
+    constexpr decltype(auto) back() const
+      requires bidirectional_range<const D> && common_range<const D>;
+    template<random_access_range R = D>
+      constexpr decltype(auto) operator[](range_difference_t<R> n) {
+        return ranges::begin(derived())[n];
+      }
+    template<random_access_range R = const D>
+      constexpr decltype(auto) operator[](range_difference_t<R> n) const {
+        return ranges::begin(derived())[n];
+      }
+  };
+}
+```
+The template parameter `D` for `view_interface` may be an incomplete
+type. Before any member of the resulting specialization of
+`view_interface` other than special member functions is referenced, `D`
+shall be complete, and model both `derived_from<view_interface<D>>` and
+`view`.
+#### Members <a id="view.interface.members">[[view.interface.members]]</a>
+``` cpp
+constexpr decltype(auto) front() requires forward_range<D>;
+constexpr decltype(auto) front() const requires forward_range<const D>;
+```
+*Preconditions:* `!empty()`.
+*Effects:* Equivalent to: `return *ranges::begin(`*`derived`*`());`
+``` cpp
+constexpr decltype(auto) back() requires bidirectional_range<D> && common_range<D>;
+constexpr decltype(auto) back() const
+  requires bidirectional_range<const D> && common_range<const D>;
+```
+*Preconditions:* `!empty()`.
+*Effects:* Equivalent to:
+`return *ranges::prev(ranges::end(`*`derived`*`()));`
+### Sub-ranges <a id="range.subrange">[[range.subrange]]</a>
+The `subrange` class template combines together an iterator and a
+sentinel into a single object that models the `view` concept.
+Additionally, it models the `sized_range` concept when the final
+template parameter is `subrange_kind::sized`.
+``` cpp
+namespace std::ranges {
+  template<class From, class To>
+    concept convertible-to-non-slicing =                    // exposition only
+      convertible_to<From, To> &&
+      !(is_pointer_v<decay_t<From>> &&
+        is_pointer_v<decay_t<To>> &&
+        not-same-as<remove_pointer_t<decay_t<From>>, remove_pointer_t<decay_t<To>>>);
+  template<class T>
+    concept pair-like =                                     // exposition only
+      !is_reference_v<T> && requires(T t) {
+        typename tuple_size<T>::type;                       // ensures tuple_size<T> is complete
+        requires derived_from<tuple_size<T>, integral_constant<size_t, 2>>;
+        typename tuple_element_t<0, remove_const_t<T>>;
+        typename tuple_element_t<1, remove_const_t<T>>;
+        { get<0>(t) } -> convertible_to<const tuple_element_t<0, T>&>;
+        { get<1>(t) } -> convertible_to<const tuple_element_t<1, T>&>;
+      };
+  template<class T, class U, class V>
+    concept pair-like-convertible-from =                    // exposition only
+      !range<T> && pair-like<T> &&
+      constructible_from<T, U, V> &&
+      convertible-to-non-slicing<U, tuple_element_t<0, T>> &&
+      convertible_to<V, tuple_element_t<1, T>>;
+  template<class T>
+    concept iterator-sentinel-pair =                        // exposition only
+      !range<T> && pair-like<T> &&
+      sentinel_for<tuple_element_t<1, T>, tuple_element_t<0, T>>;
+  template<input_or_output_iterator I, sentinel_for<I> S = I, subrange_kind K =
+      sized_sentinel_for<S, I> ? subrange_kind::sized : subrange_kind::unsized>
+    requires (K == subrange_kind::sized || !sized_sentinel_for<S, I>)
+  class subrange : public view_interface<subrange<I, S, K>> {
+  private:
+    static constexpr bool StoreSize =                           // exposition only
+      K == subrange_kind::sized && !sized_sentinel_for<S, I>;
+    I begin_ = I();                                             // exposition only
+    S end_ = S();                                               // exposition only
+    make-unsigned-like-t<iter_difference_t<I>> size_ = 0;       // exposition only; present only
+                                                                // when StoreSize is true
+  public:
+    subrange() = default;
+    constexpr subrange(convertible-to-non-slicing<I> auto i, S s) requires (!StoreSize);
+    constexpr subrange(convertible-to-non-slicing<I> auto i, S s,
+                       make-unsigned-like-t<iter_difference_t<I>> n)
+      requires (K == subrange_kind::sized);
+    template<not-same-as<subrange> R>
+      requires borrowed_range<R> &&
+               convertible-to-non-slicing<iterator_t<R>, I> &&
+               convertible_to<sentinel_t<R>, S>
+    constexpr subrange(R&& r) requires (!StoreSize || sized_range<R>);
+    template<borrowed_range R>
+      requires convertible-to-non-slicing<iterator_t<R>, I> &&
+               convertible_to<sentinel_t<R>, S>
+    constexpr subrange(R&& r, make-unsigned-like-t<iter_difference_t<I>> n)
+      requires (K == subrange_kind::sized)
+        : subrange{ranges::begin(r), ranges::end(r), n}
+    {}
+    template<not-same-as<subrange> PairLike>
+      requires pair-like-convertible-from<PairLike, const I&, const S&>
+    constexpr operator PairLike() const;
+    constexpr I begin() const requires copyable<I>;
+    [[nodiscard]] constexpr I begin() requires (!copyable<I>);
+    constexpr S end() const;
+    constexpr bool empty() const;
+    constexpr make-unsigned-like-t<iter_difference_t<I>> size() const
+      requires (K == subrange_kind::sized);
+    [[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) const &
+      requires forward_iterator<I>;
+    [[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) &&;
+    [[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const
+      requires bidirectional_iterator<I>;
+    constexpr subrange& advance(iter_difference_t<I> n);
+  };
+  template<input_or_output_iterator I, sentinel_for<I> S>
+    subrange(I, S) -> subrange<I, S>;
+  template<input_or_output_iterator I, sentinel_for<I> S>
+    subrange(I, S, make-unsigned-like-t<iter_difference_t<I>>) ->
+      subrange<I, S, subrange_kind::sized>;
+  template<iterator-sentinel-pair P>
+    subrange(P) -> subrange<tuple_element_t<0, P>, tuple_element_t<1, P>>;
+  template<iterator-sentinel-pair P>
+    subrange(P, make-unsigned-like-t<iter_difference_t<tuple_element_t<0, P>>>) ->
+      subrange<tuple_element_t<0, P>, tuple_element_t<1, P>, subrange_kind::sized>;
+  template<borrowed_range R>
+    subrange(R&&) ->
+      subrange<iterator_t<R>, sentinel_t<R>,
+               (sized_range<R> || sized_sentinel_for<sentinel_t<R>, iterator_t<R>>)
+                 ? subrange_kind::sized : subrange_kind::unsized>;
+  template<borrowed_range R>
+    subrange(R&&, make-unsigned-like-t<range_difference_t<R>>) ->
+      subrange<iterator_t<R>, sentinel_t<R>, subrange_kind::sized>;
+  template<size_t N, class I, class S, subrange_kind K>
+    requires (N < 2)
+    constexpr auto get(const subrange<I, S, K>& r);
+  template<size_t N, class I, class S, subrange_kind K>
+    requires (N < 2)
+    constexpr auto get(subrange<I, S, K>&& r);
+}
+namespace std {
+  using ranges::get;
+}
+```
+#### Constructors and conversions <a id="range.subrange.ctor">[[range.subrange.ctor]]</a>
+``` cpp
+constexpr subrange(convertible-to-non-slicing<I> auto i, S s) requires (!StoreSize);
+```
+*Preconditions:* \[`i`, `s`) is a valid range.
+*Effects:* Initializes *begin\_* with `std::move(i)` and *end\_* with
+`s`.
+``` cpp
+constexpr subrange(convertible-to-non-slicing<I> auto i, S s,
+                   make-unsigned-like-t<iter_difference_t<I>> n)
+  requires (K == subrange_kind::sized);
+```
+*Preconditions:* \[`i`, `s`) is a valid range, and
+`n == `*`to-unsigned-like`*`(ranges::distance(i, s))`.
+*Effects:* Initializes *begin\_* with `std::move(i)` and *end\_* with
+`s`. If *StoreSize* is `true`, initializes *size\_* with `n`.
+[*Note 1*: Accepting the length of the range and storing it to later
+return from `size()` enables `subrange` to model `sized_range` even when
+it stores an iterator and sentinel that do not model
+`sized_sentinel_for`. — *end note*]
+``` cpp
+template<not-same-as<subrange> R>
+  requires borrowed_range<R> &&
+           convertible-to-non-slicing<iterator_t<R>, I> &&
+           convertible_to<sentinel_t<R>, S>
+constexpr subrange(R&& r) requires (!StoreSize || sized_range<R>);
+```
+*Effects:* Equivalent to:
+- If *StoreSize* is `true`, `subrange{r, ranges::size(r)}`.
+- Otherwise, `subrange{ranges::begin(r), ranges::end(r)}`.
+``` cpp
+template<not-same-as<subrange> PairLike>
+  requires pair-like-convertible-from<PairLike, const I&, const S&>
+constexpr operator PairLike() const;
+```
+*Effects:* Equivalent to: `return PairLike(`*`begin_`*`, `*`end_`*`);`
+#### Accessors <a id="range.subrange.access">[[range.subrange.access]]</a>
+``` cpp
+constexpr I begin() const requires copyable<I>;
+```
+*Effects:* Equivalent to: `return `*`begin_`*`;`
+``` cpp
+[[nodiscard]] constexpr I begin() requires (!copyable<I>);
+```
+*Effects:* Equivalent to: `return std::move(`*`begin_`*`);`
+``` cpp
+constexpr S end() const;
+```
+*Effects:* Equivalent to: `return `*`end_`*`;`
+``` cpp
+constexpr bool empty() const;
+```
+*Effects:* Equivalent to: `return `*`begin_`*` == `*`end_`*`;`
+``` cpp
+constexpr make-unsigned-like-t<iter_difference_t<I>> size() const
+  requires (K == subrange_kind::sized);
+```
+*Effects:*
+- If *StoreSize* is `true`, equivalent to: `return `*`size_`*`;`
+- Otherwise, equivalent to:
+  `return `*`to-unsigned-like`*`(`*`end_`*` - `*`begin_`*`);`
+``` cpp
+[[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) const &
+  requires forward_iterator<I>;
+```
+*Effects:* Equivalent to:
+``` cpp
+auto tmp = *this;
+tmp.advance(n);
+return tmp;
+```
+``` cpp
+[[nodiscard]] constexpr subrange next(iter_difference_t<I> n = 1) &&;
+```
+*Effects:* Equivalent to:
+``` cpp
+advance(n);
+return std::move(*this);
+```
+``` cpp
+[[nodiscard]] constexpr subrange prev(iter_difference_t<I> n = 1) const
+  requires bidirectional_iterator<I>;
+```
+*Effects:* Equivalent to:
+``` cpp
+auto tmp = *this;
+tmp.advance(-n);
+return tmp;
+```
+``` cpp
+constexpr subrange& advance(iter_difference_t<I> n);
+```
+*Effects:* Equivalent to:
+- If *StoreSize* is `true`,
+  ``` cpp
+  auto d = n - ranges::advance(begin_, n, end_);
+  if (d >= 0)
+    size_ -= to-unsigned-like(d);
+  else
+    size_ += to-unsigned-like(-d);
+  return *this;
+  ```
+- Otherwise,
+  ``` cpp
+  ranges::advance(begin_, n, end_);
+  return *this;
+  ```
+``` cpp
+template<size_t N, class I, class S, subrange_kind K>
+  requires (N < 2)
+  constexpr auto get(const subrange<I, S, K>& r);
+template<size_t N, class I, class S, subrange_kind K>
+  requires (N < 2)
+  constexpr auto get(subrange<I, S, K>&& r);
+```
+*Effects:* Equivalent to:
+``` cpp
+if constexpr (N == 0)
+  return r.begin();
+else
+  return r.end();
+```
+### Dangling iterator handling <a id="range.dangling">[[range.dangling]]</a>
+The tag type `dangling` is used together with the template aliases
+`borrowed_iterator_t` and `borrowed_subrange_t` to indicate that an
+algorithm that typically returns an iterator into or subrange of a
+`range` argument does not return an iterator or subrange which could
+potentially reference a range whose lifetime has ended for a particular
+rvalue `range` argument which does not model `borrowed_range`
+[[range.range]].
+``` cpp
+namespace std::ranges {
+  struct dangling {
+    constexpr dangling() noexcept = default;
+    template<class... Args>
+      constexpr dangling(Args&&...) noexcept { }
+  };
+}
+```
+[*Example 1*:
+``` cpp
+vector<int> f();
+auto result1 = ranges::find(f(), 42);                                   // #1
+static_assert(same_as<decltype(result1), ranges::dangling>);
+auto vec = f();
+auto result2 = ranges::find(vec, 42);                                   // #2
+static_assert(same_as<decltype(result2), vector<int>::iterator>);
+auto result3 = ranges::find(subrange{vec}, 42);                         // #3
+static_assert(same_as<decltype(result3), vector<int>::iterator>);
+```
+The call to `ranges::find` at \#1 returns `ranges::dangling` since `f()`
+is an rvalue `vector`; the `vector` could potentially be destroyed
+before a returned iterator is dereferenced. However, the calls at \#2
+and \#3 both return iterators since the lvalue `vec` and specializations
+of `subrange` model `borrowed_range`.
+— *end example*]

Diff to HTML by rtfpessoa