[range.cartesian] - C++20 → C++23

Files changed (1) hide show

tmp/tmpnwtrk295/{from.md → to.md} +597 -0

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

	@@ -0,0 +1,597 @@

+### Cartesian product view <a id="range.cartesian">[[range.cartesian]]</a>
+#### Overview <a id="range.cartesian.overview">[[range.cartesian.overview]]</a>
+`cartesian_product_view` takes any non-zero number of ranges n and
+produces a view of tuples calculated by the n-ary cartesian product of
+the provided ranges.
+The name `views::cartesian_product` denotes a customization point object
+[[customization.point.object]]. Given a pack of subexpressions `Es`, the
+expression `views::cartesian_product(Es...)` is expression-equivalent to
+- `views::single(tuple())` if `Es` is an empty pack,
+- otherwise,
+  `cartesian_product_view<views::all_t<decltype((Es))>...>(Es...)`.
+[*Example 1*:
+``` cpp
+vector<int> v { 0, 1, 2 };
+for (auto&& [a, b, c] : views::cartesian_product(v, v, v)) {
+  cout << a << ' ' << b << ' ' << c << '\n';
+}
+// The above prints
+// 0 0 0
+// 0 0 1
+// 0 0 2
+// 0 1 0
+// 0 1 1
+// ...
+```
+— *end example*]
+#### Class template `cartesian_product_view` <a id="range.cartesian.view">[[range.cartesian.view]]</a>
+``` cpp
+namespace std::ranges {
+  template<bool Const, class First, class... Vs>
+  concept cartesian-product-is-random-access =          // exposition only
+    (random_access_range<maybe-const<Const, First>> && ... &&
+      (random_access_range<maybe-const<Const, Vs>>
+        && sized_range<maybe-const<Const, Vs>>));
+  template<class R>
+  concept cartesian-product-common-arg =                // exposition only
+    common_range<R> || (sized_range<R> && random_access_range<R>);
+  template<bool Const, class First, class... Vs>
+  concept cartesian-product-is-bidirectional =          // exposition only
+    (bidirectional_range<maybe-const<Const, First>> && ... &&
+      (bidirectional_range<maybe-const<Const, Vs>>
+        && cartesian-product-common-arg<maybe-const<Const, Vs>>));
+  template<class First, class... Vs>
+  concept cartesian-product-is-common =                 // exposition only
+    cartesian-product-common-arg<First>;
+  template<class... Vs>
+  concept cartesian-product-is-sized =                  // exposition only
+    (sized_range<Vs> && ...);
+  template<bool Const, template<class> class FirstSent, class First, class... Vs>
+    concept cartesian-is-sized-sentinel =               // exposition only
+      (sized_sentinel_for<FirstSent<maybe-const<Const, First>>,
+          iterator_t<maybe-const<Const, First>>> && ...
+        && (sized_range<maybe-const<Const, Vs>>
+          && sized_sentinel_for<iterator_t<maybe-const<Const, Vs>>,
+              iterator_t<maybe-const<Const, Vs>>>));
+  template<cartesian-product-common-arg R>
+  constexpr auto cartesian-common-arg-end(R& r) {       // exposition only
+    if constexpr (common_range<R>) {
+      return ranges::end(r);
+    } else {
+      return ranges::begin(r) + ranges::distance(r);
+    }
+  }
+  template<input_range First, forward_range... Vs>
+    requires (view<First> && ... && view<Vs>)
+  class cartesian_product_view : public view_interface<cartesian_product_view<First, Vs...>> {
+  private:
+    tuple<First, Vs...> bases_;                 // exposition only
+    // [range.cartesian.iterator], class template cartesian_product_view::iterator
+    template<bool Const> class iterator;       // exposition only
+  public:
+    constexpr cartesian_product_view() = default;
+    constexpr explicit cartesian_product_view(First first_base, Vs... bases);
+    constexpr iterator<false> begin()
+      requires (!simple-view<First> || ... || !simple-view<Vs>);
+    constexpr iterator<true> begin() const
+      requires (range<const First> && ... && range<const Vs>);
+    constexpr iterator<false> end()
+      requires ((!simple-view<First> || ... || !simple-view<Vs>) &&
+        cartesian-product-is-common<First, Vs...>);
+    constexpr iterator<true> end() const
+      requires cartesian-product-is-common<const First, const Vs...>;
+    constexpr default_sentinel_t end() const noexcept;
+    constexpr see below size()
+      requires cartesian-product-is-sized<First, Vs...>;
+    constexpr see below size() const
+      requires cartesian-product-is-sized<const First, const Vs...>;
+  };
+  template<class... Vs>
+    cartesian_product_view(Vs&&...) -> cartesian_product_view<views::all_t<Vs>...>;
+}
+```
+``` cpp
+constexpr explicit cartesian_product_view(First first_base, Vs... bases);
+```
+*Effects:* Initializes *bases\_* with
+`std::move(first_base), std::move(bases)...`.
+``` cpp
+constexpr iterator<false> begin()
+  requires (!simple-view<First> || ... || !simple-view<Vs>);
+```
+*Effects:* Equivalent to:
+``` cpp
+return iterator<false>(*this, tuple-transform(ranges::begin, bases_));
+```
+``` cpp
+constexpr iterator<true> begin() const
+  requires (range<const First> && ... && range<const Vs>);
+```
+*Effects:* Equivalent to:
+``` cpp
+return iterator<true>(*this, tuple-transform(ranges::begin, bases_));
+```
+``` cpp
+constexpr iterator<false> end()
+  requires ((!simple-view<First> || ... || !simple-view<Vs>)
+    && cartesian-product-is-common<First, Vs...>);
+constexpr iterator<true> end() const
+  requires cartesian-product-is-common<const First, const Vs...>;
+```
+Let:
+- *is-const* be `true` for the const-qualified overload, and `false`
+  otherwise;
+- *is-empty* be `true` if the expression `ranges::empty(rng)` is `true`
+  for any `rng` among the underlying ranges except the first one and
+  `false` otherwise; and
+- *`begin-or-first-end`*`(rng)` be expression-equivalent to
+  *`is-empty`*` ? ranges::begin(rng) : `*`cartesian-common-arg-end`*`(rng)`
+  if `rng` is the first underlying range and `ranges::begin(rng)`
+  otherwise.
+*Effects:* Equivalent to:
+``` cpp
+iterator<is-const> it(*this, tuple-transform(
+  [](auto& rng){ return begin-or-first-end(rng); }, bases_));
+return it;
+```
+``` cpp
+constexpr default_sentinel_t end() const noexcept;
+```
+*Returns:* `default_sentinel`.
+``` cpp
+constexpr see below size()
+  requires cartesian-product-is-sized<First, Vs...>;
+constexpr see below size() const
+  requires cartesian-product-is-sized<const First, const Vs...>;
+```
+The return type is an *implementation-defined* unsigned-integer-like
+type.
+*Recommended practice:* The return type should be the smallest
+unsigned-integer-like type that is sufficiently wide to store the
+product of the maximum sizes of all the underlying ranges, if such a
+type exists.
+Let p be the product of the sizes of all the ranges in *bases\_*.
+*Preconditions:* p can be represented by the return type.
+*Returns:* p.
+#### Class template `cartesian_product_view::iterator` <a id="range.cartesian.iterator">[[range.cartesian.iterator]]</a>
+``` cpp
+namespace std::ranges {
+  template<input_range First, forward_range... Vs>
+    requires (view<First> && ... && view<Vs>)
+  template<bool Const>
+  class cartesian_product_view<First, Vs...>::iterator {
+  public:
+    using iterator_category = input_iterator_tag;
+    using iterator_concept  = see below;
+    using value_type = tuple<range_value_t<maybe-const<Const, First>>,
+      range_value_t<maybe-const<Const, Vs>>...>;
+    using reference = tuple<range_reference_t<maybe-const<Const, First>>,
+      range_reference_t<maybe-const<Const, Vs>>...>;
+    using difference_type = see below;
+    iterator() = default;
+    constexpr iterator(iterator<!Const> i) requires Const &&
+      (convertible_to<iterator_t<First>, iterator_t<const First>> &&
+        ... && convertible_to<iterator_t<Vs>, iterator_t<const Vs>>);
+    constexpr auto operator*() const;
+    constexpr iterator& operator++();
+    constexpr void operator++(int);
+    constexpr iterator operator++(int) requires forward_range<maybe-const<Const, First>>;
+    constexpr iterator& operator--()
+      requires cartesian-product-is-bidirectional<Const, First, Vs...>;
+    constexpr iterator operator--(int)
+      requires cartesian-product-is-bidirectional<Const, First, Vs...>;
+    constexpr iterator& operator+=(difference_type x)
+      requires cartesian-product-is-random-access<Const, First, Vs...>;
+    constexpr iterator& operator-=(difference_type x)
+      requires cartesian-product-is-random-access<Const, First, Vs...>;
+    constexpr reference operator[](difference_type n) const
+      requires cartesian-product-is-random-access<Const, First, Vs...>;
+    friend constexpr bool operator==(const iterator& x, const iterator& y)
+      requires equality_comparable<iterator_t<maybe-const<Const, First>>>;
+    friend constexpr bool operator==(const iterator& x, default_sentinel_t);
+    friend constexpr auto operator<=>(const iterator& x, const iterator& y)
+      requires all-random-access<Const, First, Vs...>;
+    friend constexpr iterator operator+(const iterator& x, difference_type y)
+      requires cartesian-product-is-random-access<Const, First, Vs...>;
+    friend constexpr iterator operator+(difference_type x, const iterator& y)
+      requires cartesian-product-is-random-access<Const, First, Vs...>;
+    friend constexpr iterator operator-(const iterator& x, difference_type y)
+      requires cartesian-product-is-random-access<Const, First, Vs...>;
+    friend constexpr difference_type operator-(const iterator& x, const iterator& y)
+      requires cartesian-is-sized-sentinel<Const, iterator_t, First, Vs...>;
+    friend constexpr difference_type operator-(const iterator& i, default_sentinel_t)
+      requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>;
+    friend constexpr difference_type operator-(default_sentinel_t, const iterator& i)
+      requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>;
+    friend constexpr auto iter_move(const iterator& i) noexcept(see below);
+    friend constexpr void iter_swap(const iterator& l, const iterator& r) noexcept(see below)
+      requires (indirectly_swappable<iterator_t<maybe-const<Const, First>>> && ... &&
+        indirectly_swappable<iterator_t<maybe-const<Const, Vs>>>);
+  private:
+    using Parent = maybe-const<Const, cartesian_product_view>;          // exposition only
+    Parent* parent_ = nullptr;                                          // exposition only
+    tuple<iterator_t<maybe-const<Const, First>>,
+      iterator_t<maybe-const<Const, Vs>>...> current_;                  // exposition only
+    template<size_t N = sizeof...(Vs)>
+      constexpr void next();                                            // exposition only
+    template<size_t N = sizeof...(Vs)>
+      constexpr void prev();                                            // exposition only
+    template<class Tuple>
+      constexpr difference_type distance-from(const Tuple& t) const;    // exposition only
+    constexpr iterator(Parent& parent, tuple<iterator_t<maybe-const<Const, First>>,
+      iterator_t<maybe-const<Const, Vs>>...> current);                  // exposition only
+  };
+}
+```
+`iterator::iterator_concept` is defined as follows:
+- If `cartesian-product-is-random-access<Const, First, Vs...>` is
+  modeled, then `iterator_concept` denotes `random_access_iterator_tag`.
+- Otherwise, if
+  `cartesian-product-is-bidirectional<Const, First, Vs...>` is modeled,
+  then `iterator_concept` denotes `bidirectional_iterator_tag`.
+- Otherwise, if `maybe-const<Const, First>` models `forward_range`, then
+  `iterator_concept` denotes `forward_iterator_tag`.
+- Otherwise, `iterator_concept` denotes `input_iterator_tag`.
+`iterator::difference_type` is an *implementation-defined*
+signed-integer-like type.
+*Recommended practice:* `iterator::difference_type` should be the
+smallest signed-integer-like type that is sufficiently wide to store the
+product of the maximum sizes of all underlying ranges if such a type
+exists.
+``` cpp
+template<size_t N = sizeof...(Vs)>
+  constexpr void next();
+```
+*Effects:* Equivalent to:
+``` cpp
+auto& it = std::get<N>(current_);
+++it;
+if constexpr (N > 0) {
+  if (it == ranges::end(std::get<N>(parent_->bases_))) {
+    it = ranges::begin(std::get<N>(parent_->bases_));
+    next<N - 1>();
+  }
+}
+```
+``` cpp
+template<size_t N = sizeof...(Vs)>
+  constexpr void prev();
+```
+*Effects:* Equivalent to:
+``` cpp
+auto& it = std::get<N>(current_);
+if constexpr (N > 0) {
+  if (it == ranges::begin(std::get<N>(parent_->bases_))) {
+    it = cartesian-common-arg-end(std::get<N>(parent_->bases_));
+    prev<N - 1>();
+  }
+}
+--it;
+```
+``` cpp
+template<class Tuple>
+  constexpr difference_type distance-from(const Tuple& t) const;
+```
+Let:
+- scaled-size(N) be the product of
+  `static_cast<difference_type>(ranges::size(std::get<`N`>(`*`parent_`*`->`*`bases_`*`)))`
+  and scaled-size(N+1) if N ≤ `sizeof...(Vs)`, otherwise
+  `static_cast<difference_type>(1)`;
+- scaled-distance(N) be the product of
+  `static_cast<difference_type>(std::get<`N`>(`*`current_`*`) - std::get<`N`>(t))`
+  and scaled-size(N+1); and
+- *scaled-sum* be the sum of scaled-distance(N) for every integer
+  0 ≤ N ≤ `sizeof...(Vs)`.
+*Preconditions:* *scaled-sum* can be represented by `difference_type`.
+*Returns:* *scaled-sum*.
+``` cpp
+constexpr iterator(Parent& parent, tuple<iterator_t<maybe-const<Const, First>>,
+  iterator_t<maybe-const<Const, Vs>>...> current);
+```
+*Effects:* Initializes *parent\_* with `addressof(parent)` and
+*current\_* with `std::move(current)`.
+``` cpp
+constexpr iterator(iterator<!Const> i) requires Const &&
+  (convertible_to<iterator_t<First>, iterator_t<const First>> &&
+    ... && convertible_to<iterator_t<Vs>, iterator_t<const Vs>>);
+```
+*Effects:* Initializes *parent\_* with `i.`*`parent_`* and *current\_*
+with `std::move(i.`*`current_`*`)`.
+``` cpp
+constexpr auto operator*() const;
+```
+*Effects:* Equivalent to:
+``` cpp
+return tuple-transform([](auto& i) -> decltype(auto) { return *i; }, current_);
+```
+``` cpp
+constexpr iterator& operator++();
+```
+*Effects:* Equivalent to:
+``` cpp
+next();
+return *this;
+```
+``` cpp
+constexpr void operator++(int);
+```
+*Effects:* Equivalent to `++*this`.
+``` cpp
+constexpr iterator operator++(int) requires forward_range<maybe-const<Const, First>>;
+```
+*Effects:* Equivalent to:
+``` cpp
+auto tmp = *this;
+++*this;
+return tmp;
+```
+``` cpp
+constexpr iterator& operator--()
+  requires cartesian-product-is-bidirectional<Const, First, Vs...>;
+```
+*Effects:* Equivalent to:
+``` cpp
+prev();
+return *this;
+```
+``` cpp
+constexpr iterator operator--(int)
+  requires cartesian-product-is-bidirectional<Const, First, Vs...>;
+```
+*Effects:* Equivalent to:
+``` cpp
+auto tmp = *this;
+--*this;
+return tmp;
+```
+``` cpp
+constexpr iterator& operator+=(difference_type x)
+  requires cartesian-product-is-random-access<Const, First, Vs...>;
+```
+Let `orig` be the value of `*this` before the call.
+Let `ret` be:
+- If `x > 0`, the value of `*this` had *next* been called `x` times.
+- Otherwise, if `x < 0`, the value of `*this` had *prev* been called
+  `-x` times.
+- Otherwise, `orig`.
+*Preconditions:* `x` is in the range
+$[\texttt{ranges::distance(*this, ranges::begin(*\textit{parent_}))},$
+$\texttt{ranges::distance(*this, ranges::end(*\textit{parent_}))}]$.
+*Effects:* Sets the value of `*this` to `ret`.
+*Returns:* `*this`.
+*Complexity:* Constant.
+``` cpp
+constexpr iterator& operator-=(difference_type x)
+  requires cartesian-product-is-random-access<Const, First, Vs...>;
+```
+*Effects:* Equivalent to:
+``` cpp
+*this += -x;
+return *this;
+```
+``` cpp
+constexpr reference operator[](difference_type n) const
+  requires cartesian-product-is-random-access<Const, First, Vs...>;
+```
+*Effects:* Equivalent to: `return *((*this) + n);`
+``` cpp
+friend constexpr bool operator==(const iterator& x, const iterator& y)
+  requires equality_comparable<iterator_t<maybe-const<Const, First>>>;
+```
+*Effects:* Equivalent to: `return x.`*`current_`*` == y.`*`current_`*`;`
+``` cpp
+friend constexpr bool operator==(const iterator& x, default_sentinel_t);
+```
+*Returns:* `true` if
+`std::get<`i`>(x.`*`current_`*`) == ranges::end(std::get<`i`>(x.`*`parent_`*`->`*`bases_`*`))`
+is `true` for any integer 0 ≤ i ≤ `sizeof...(Vs)`; otherwise, `false`.
+``` cpp
+friend constexpr auto operator<=>(const iterator& x, const iterator& y)
+  requires all-random-access<Const, First, Vs...>;
+```
+*Effects:* Equivalent to:
+`return x.`*`current_`*` <=> y.`*`current_`*`;`
+``` cpp
+friend constexpr iterator operator+(const iterator& x, difference_type y)
+  requires cartesian-product-is-random-access<Const, First, Vs...>;
+```
+*Effects:* Equivalent to: `return `*`iterator`*`(x) += y;`
+``` cpp
+friend constexpr iterator operator+(difference_type x, const iterator& y)
+  requires cartesian-product-is-random-access<Const, First, Vs...>;
+```
+*Effects:* Equivalent to: `return y + x;`
+``` cpp
+friend constexpr iterator operator-(const iterator& x, difference_type y)
+  requires cartesian-product-is-random-access<Const, First, Vs...>;
+```
+*Effects:* Equivalent to: `return `*`iterator`*`(x) -= y;`
+``` cpp
+friend constexpr difference_type operator-(const iterator& x, const iterator& y)
+  requires cartesian-is-sized-sentinel<Const, iterator_t, First, Vs...>;
+```
+*Effects:* Equivalent to:
+`return x.`*`distance-from`*`(y.`*`current_`*`);`
+``` cpp
+friend constexpr difference_type operator-(const iterator& i, default_sentinel_t)
+  requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>;
+```
+Let *end-tuple* be an object of a type that is a specialization of
+`tuple`, such that:
+- `std::get<0>(`*`end-tuple`*`)` has the same value as
+  `ranges::end(std::get<0>(i.`*`parent_`*`->`*`bases_`*`))`;
+- `std::get<`N`>(`*`end-tuple`*`)` has the same value as
+  `ranges::begin(std::get<`N`>(i.`*`parent_`*`->`*`bases_`*`))` for
+  every integer 1 ≤ N ≤ `sizeof...(Vs)`.
+*Effects:* Equivalent to:
+`return i.`*`distance-from`*`(`*`end-tuple`*`);`
+``` cpp
+friend constexpr difference_type operator-(default_sentinel_t s, const iterator& i)
+  requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>;
+```
+*Effects:* Equivalent to: `return -(i - s);`
+``` cpp
+friend constexpr auto iter_move(const iterator& i) noexcept(see below);
+```
+*Effects:* Equivalent to:
+`return `*`tuple-transform`*`(ranges::iter_move, i.`*`current_`*`);`
+*Remarks:* The exception specification is equivalent to the logical of
+the following expressions:
+- `noexcept(ranges::iter_move(std::get<`N`>(i.`*`current_`*`)))` for
+  every integer 0 ≤ N ≤ `sizeof...(Vs)`,
+- `is_nothrow_move_constructible_v<range_rvalue_reference_t<`*`maybe-const`*`<Const, T>>>`
+  for every type `T` in `First, Vs...`.
+``` cpp
+friend constexpr void iter_swap(const iterator& l, const iterator& r) noexcept(see below)
+  requires (indirectly_swappable<iterator_t<maybe-const<Const, First>>> && ... &&
+        indirectly_swappable<iterator_t<maybe-const<Const, Vs>>>);
+```
+*Effects:* For every integer 0 ≤ i ≤ `sizeof...(Vs)`, performs:
+``` cpp
+ranges::iter_swap(std::get<i>(l.current_), std::get<i>(r.current_))
+```
+*Remarks:* The exception specification is equivalent to the logical of
+the following expressions:
+- `noexcept(ranges::iter_swap(std::get<`i`>(l.`*`current_`*`), std::get<`i`>(r.`*`current_`*`)))`
+  for every integer 0 ≤ i ≤ `sizeof...(Vs)`.

Diff to HTML by rtfpessoa