This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

3801. cartesian_product_view::iterator::distance-from ignores the size of last underlying range

Section: 26.7.32.3 [range.cartesian.iterator] Status: WP Submitter: Patrick Palka Opened: 2022-10-25 Last modified: 2023-02-07

Priority: Not Prioritized

View all other issues in [range.cartesian.iterator].

View all issues with WP status.

Discussion:

The helper scaled-size(N) from the wording for P2374R4's cartesian_product_view::iterator::distance-from is recursively specified as:

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);

Intuitively, scaled-size(N) is the size of the cartesian product of all but the first N underlying ranges. Thus scaled-size(sizeof...(Vs)) ought to just yield the size of the last underlying range (since there are 1 + sizeof...(Vs) underlying ranges), but according to this definition it yields 1. Similarly at the other extreme, scaled-size(0) should yield the product of the sizes of all the underlying ranges, but it instead yields that of all but the last underlying range.

For cartesian_product_views of two or more underlying ranges, this causes the relevant operator- overloads to compute wrong distances, e.g. 

int x[] = {1, 2, 3};
auto v = views::cartesian_product(x, x);
auto i = v.begin() + 5;  // *i == {2, 3}
assert(*i == tuple{2, 3});
assert(i - v.begin() == 5); // fails, expects 3, because:
// scaled-sum = scaled-distance(0) + scaled-distance(1)
//            = ((1 - 0) * scaled-size(1)) + ((2 - 0) * scaled-size(2))
//            = 1 + 2 instead of 3 + 2

The recursive condition should probably use <= instead of <.

[2022-11-04; Reflector poll]

Set status to Tentatively Ready after seven votes in favour during reflector poll.

[2022-11-12 Approved at November 2022 meeting in Kona. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4917.

  1. Modify [ranges.cartesian.iterator] as indicated:

    template<class Tuple>
  constexpr difference_type distance-from(Tuple t);

    -7- Let:

    1. (7.1) — 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);

    2. (7.2) — 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

    3. (7.3) — scaled-sum be the sum of scaled-distance(N) for every integer 0 ≤ N ≤ sizeof...(Vs).