P2374R1
views::cartesian_product

1. Changes from r0

• Specify the return type of size

• Add design section on the first range argument

2. Motivation

Cartesian product is a fundamental mathematical construct. There should be a cartesian_product_view which generates the cartesian product of any number of ranges, e.g.:

std::vector<int> a,b,c;
for (auto&& ea : a) {
    for (auto&& eb : b) {
        for (auto&& ec : c) {
            use(ea,eb,ec);
        }
    }
}

std::vector<int> a,b,c;
for (auto&& [ea,eb,ec] : std::views::cartesian_product(a,b,c)) {
    use(ea,eb,ec);
}

This is especially useful for composing with other views, or dealing with parameter packs of ranges:

template <std::size_t N = 0, class F, 
          class Res, class Tuple, class... Args>
auto find_tuples_satisfying_impl(
    F f, Res& res, Tuple const& ranges, Args const&... args)
requires(N == std::tuple_size_v<std::remove_cvref_t<Tuple>>) {
  if (std::invoke(f, args...)) {
    res.push_back(std::make_tuple(args...));
  }
}

template <std::size_t N = 0, class F, 
          class Res, class Tuple, class... Args>
auto find_tuples_satisfying_impl(
    F f, Res& res, Tuple const& ranges, Args const&... args) {
  for (auto&& e : std::get<N>(ranges)) {
    find_tuples_satisfying_impl<N+1>(f, res, ranges, args..., e);
  }
}

template <class F, std::ranges::forward_range... Vs>
requires(std::regular_invocable<
          F, std::ranges::range_reference_t<Vs>...>)
auto find_tuples_satisfying(F f, Vs&&... vs) {
  std::vector<std::tuple<std::ranges::range_value_t<Vs>...>> res;
  find_tuples_satisfying_impl(
        f, res, std::tuple(std::forward<Vs&&>(vs)...));
  return res;
}

template <class F, std::ranges::forward_range... Vs>
requires(std::regular_invocable<F, 
          std::ranges::range_reference_t<Vs>...>)
auto find_tuples_satisfying(F f, Vs&&... vs) {
  return std::views::cartesian_product(std::forward<Vs>(vs)...) 
    | std::views::filter([f](auto&& tuple) { return std::apply(f, tuple); });)
    | std::ranges::to<std::vector>(); //given P1206
}

3. Design

3.1. Minimum Range Requirements

3.2. Tuple or pair

3.3. reference_type

3.4. Empty cartesian product view

3.5. Common Range

3.6. Bidirectional Range

We don’t consider non-common, random access, sized ranges as worth supporting, so this paper requires bidirectional and common.

3.7. Random Access Range

We can’t think of too many use-cases for this and it adds a fair bit of implementation burden, but this paper supports the necessary operations.

3.8. Initial Range Argument Special-Casing

• It could be an input range instead of forward range

• It wouldn’t need to be a sized range in order for the cartesian_product_view to be random-access or common

• It wouldn’t need to be common in order for the cartesian_product_view to be bidirectional

However, we don’t consider these use-cases to be strong enough for the inconsistency which they would bring.

3.9. Sized Range

3.10. Naming

3.11. Pipe Support

However, it’s problematic for the same reason as views::zip, in that one cannot distinguish between the usages in a | views::cartesian_product(b, c) and views::cartesian_product(b,c) on its own. As such, this paper does not support this syntax.

4. Implementation

5. Wording

5.1. Cartesian Product view [range.cartesian]

5.1.1. Overview [range.cartesian.overview]

cartesian_product_view presents a view with a value type that represents the cartesian product of the adapted ranges.

The name views::cartesian_product denotes a customization point object. Given a pack of subexpressions Es..., the expression views::cartesian_product(Es...) is expression-equivalent to

• *decay-copy*(views::empty<tuple<>>) if Es is an empty pack,

• otherwise, cartesian_product_view<views::all_t<decltype((Es))>...>(Es...).

[Example:

std::vector<int> v { 0, 1, 2 };
for (auto&& [a,b,c] : std::views::cartesian_product(v, v, v)) {
  std::cout << a << ' ' << b << ' ' << c << '\n';
  //0 0 0
  //0 0 1
  //0 0 2
  //0 1 0
  //0 1 1
  //...
}

5.1.2. Class template cartesian_product_view [range.cartesian.view]

namespace std::ranges {
    template <class... Vs>
    concept cartesian-product-is-random-access = //exposition only
      ((random_access_range<Vs> && ...) && 
            (sized_range<Vs> && ...));

    template <class... Vs>
    concept cartesian-product-is-bidirectional = //exposition only
      ((bidirectional_range<Vs> && ...) && (common_range<Vs> && ...));

    template <class... Vs>
    concept cartesian-product-is-common = //exposition only
     (std::ranges::common_range<Vs> && ...)
         || cartesian-product-is-random-access<Vs...>;

    template<class... Ts>
    using tuple-or-pair = decltype([]{            // exposition only
        if constexpr (sizeof...(Ts) == 2) {
            return type_identity<pair<Ts...>>{};
        }
        else {
            return type_identity<tuple<Ts...>>{};
        }
    }())::type;

    template<class F, class Tuple>
    constexpr auto tuple-transform(F&& f, Tuple&& tuple) // exposition only
    {
        return apply([&]<class... Ts>(Ts&&... elements){
            return tuple-or-pair<invoke_result_t<F&, Ts>...>(
                invoke(f, std::forward<Ts>(elements))...
            );
        }, std::forward<Tuple>(tuple));
    }

    template<class F, class Tuple>
    constexpr void tuple-for-each(F&& f, Tuple&& tuple) // exposition only
    {
        apply([&]<class... Ts>(Ts&&... elements){
            (invoke(f, std::forward<Ts>(elements)), ...);
        }, std::forward<Tuple>(tuple));
    }

    template<forward_range... Vs>
    requires (view<Vs> && ...)
    class cartesian_product_view
    : public view_interface<cartesian_product_view<Vs...>> {
    private:
        std::tuple<Vs...> bases_; //exposition only

        template<bool Const>
        struct iterator; //exposition only
        template<bool Const>
        struct sentinel; //exposition only
    public:
        constexpr cartesian_product_view() = default;
        constexpr cartesian_product_view(Vs... bases);

        constexpr iterator<false> begin() requires(!simple_view<Vs> || ...);
        constexpr iterator<true> begin() const requires (range<const Vs> && ...);

        constexpr iterator<false> end() 
        requires ((!simple_view<Vs> || ...) && cartesian-product-is-common<Vs...>);
        constexpr iterator<true> end() const 
        requires(cartesian-product-is-common<const Vs...>);
        constexpr default_sentinel_t end() const 
        requires (!cartesian-product-is-common<const Vs...>);

        constexpr *see below* size() requires (sized_range<Vs> && ...);
        constexpr *see below* size() const requires (sized_range<const Vs> && ...);
    };

    template <class... Vs>
    cartesian_product_view(Vs&&...)->cartesian_product_view<all_t<Vs>...>;
   
    namespace views { inline constexpr unspecified cartesian_product = unspecified; }
   }

}

constexpr cartesian_product_view(Vs... bases);

Effects: Initialises bases_ with std::move(bases)....

constexpr iterator<false> begin() requires(!simple_view<Vs> || ...);

Effects: Equivalent to return iterator<false>(tuple-transform(ranges::begin, bases_));

constexpr iterator<true> begin() requires (range<Vs> && ...);

Effects: Equivalent to return iterator<true>(tuple-transform(ranges::begin, bases_));

constexpr iterator<false> end() 
requires ((!simple_view<Vs> || ...) && cartesian-product-is-common<Vs...>);

Effects: If every range in Vs models random_access_range, equivalent to return begin() + size(). Otherwise equivalent to:

iterator<false> it(tuple-transform(ranges::begin, bases_));
std::get<0>(it.current_) = std::ranges::end(std::get<0>(bases_));
return it;

constexpr iterator<true> end() const 
requires(cartesian-product-is-common<const Vs...>);

Effects: If every range in Vs models random_access_range, equivalent to return begin() + size(). Otherwise equivalent to:

iterator<true> it(tuple-transform(ranges::begin, bases_));
std::get<0>(it.current_) = std::ranges::end(std::get<0>(bases_));
return it;

constexpr default_sentinel_t end() const 
requires (!cartesian-product-is-common<const Vs...>) {

Effects: Equivalent to return default_sentinel;.

constexpr *see below* size() requires (sized_range<Vs> && ...);
constexpr *see below* size() const requires (sized_range<const Vs> && ...);

The return type is the smallest unsigned integral type that is sufficiently wide to store the product of the maximum sizes of all underlying ranges. If there is no such type, the type is implementation-defined.

Effects: Returns the product of the size of all ranges in bases_.

5.1.3. Class template cartesian_product_view::iterator [ranges.cartesian.iterator]

namespace std::ranges {
template<forward_range... Vs>
requires (view<Vs> && ...)
template<bool Const>
class cartesian_product_view<Vs...>::iterator {
    maybe-const<Const, cartesian_product_view>* parent_; //exposition only
    tuple-or-pair<iterator_t<maybe-const<Const, Vs>>...> current_{}; //exposition only

    template <size_t N = (sizeof...(Vs) - 1)>
    void next(); //exposition only

    template <size_t N = (sizeof...(Vs) - 1)>
    void prev(); //exposition only

public:
    using iterator_category = input_iterator_tag;
    using iterator_concept  = *see below*;
    using value_type = tuple-or-pair<range_value_t<maybe-const<Const, Vs>>...>;
    using difference_type = std::common_type_t<range_difference_t<maybe-const<Const, Vs>>...>;

    iterator() = default;
    constexpr explicit iterator(tuple-or-pair<iterator_t<maybe-const<Const, Vs>>...> current);
    
    constexpr iterator(iterator<!Const> i) requires Const && (std::convertible_to<
            std::ranges::iterator_t<Vs>,
            std::ranges::iterator_t<maybe-const<Const, Vs>>> && ...);

    constexpr auto operator*() const;
    constexpr iterator& operator++();
    constexpr iterator operator++(int);

    constexpr iterator& operator--() 
    requires (cartesian-product-is-bidirectional<maybe-const<Const, Vs>...>);
    constexpr iterator operator--(int) 
    requires (cartesian-product-is-bidirectional<maybe-const<Const, Vs>...>);

    constexpr iterator& operator+=(difference_type x) 
    requires (cartesian-product-is-random-access<maybe-const<Const, Vs>...>);
    constexpr iterator& operator-=(difference_type x) 
    requires (cartesian-product-is-random-access<maybe-const<Const, Vs>...>);

    constexpr reference operator[](difference_type n) const 
    requires (cartesian-product-is-random-access<maybe-const<Const, Vs>...>);

    friend constexpr bool operator==(const iterator& x, const iterator& y) 
    requires (equality_comparable<iterator_t<maybe-const<Const, Vs>>> && ...);

    friend constexpr bool operator==(const iterator& x, const std::default_sentinel_t&);

    friend constexpr auto operator<(const iterator& x, const iterator& y) 
    requires (std::ranges::random_access_range<maybe-const<Const, Vs>> && ...);
    friend constexpr auto operator>(const iterator& x, const iterator& y) 
    requires (std::ranges::random_access_range<maybe-const<Const, Vs>> && ...);
    friend constexpr auto operator<=(const iterator& x, const iterator& y) 
    requires (std::ranges::random_access_range<maybe-const<Const, Vs>> && ...);
    friend constexpr auto operator>=(const iterator& x, const iterator& y) 
    requires (std::ranges::random_access_range<maybe-const<Const, Vs>> && ...);

    friend constexpr auto operator<=>(const iterator& x, const iterator& y)
    requires ((std::ranges::random_access_range<maybe-const<Const, Vs>> && ...) &&               
              (std::ranges::three_way_comparable<maybe-const<Const, Vs>> && ...));

    friend constexpr iterator operator+(const iterator& x, difference_type y) 
    requires (cartesian-product-is-random-access<maybe-const<Const, Vs>...>);
    friend constexpr iterator operator+(difference_type x, const iterator& y) 
    requires (cartesian-product-is-random-access<maybe-const<Const, Vs>...>);
    friend constexpr iterator operator-(const iterator& x, difference_type y) 
    requires (cartesian-product-is-random-access<maybe-const<Const, Vs>...>);
    friend constexpr difference_type operator-(const iterator& x, const iterator& y)
    requires (sized_sentinel_for<iterator_t<maybe-const<Const, Vs>>, iterator_t<maybe-const<Const, Vs>>> && ...);
}
}

iterator::iterator_concept is defined as follows:

• If every type in Vs models random_access_range, then iterator_concept denotes random_access_iterator_tag.

• Otherwise, if every type in Vs models bidirectional_­range, then iterator_concept denotes bidirectional_­iterator_­tag.

• Otherwise, iterator_concept denotes forward_iterator_tag.

template <size_t N = (sizeof...(Vs) - 1)>
void next() //exposition only

Effects: Equivalent to:

auto& it = get<N>(current_);
++it;
if constexpr (N > 0) {
   if (it == ranges::end(get<N>(parent_->bases_))) {
       it = ranges::begin(get<N>(parent->bases_));
       next<N - 1>();
   }
}

template <size_t N = (sizeof...(Vs) - 1)>
void prev() //exposition only

Effects: Equivalent to:

auto& it = std::get<N>(currents_);
if (it == std::ranges::begin(std::get<N>(parent_->bases_))) {
  std::ranges::advance(it, std::ranges::end(std::get<N>(parent_->bases_)));
  if constexpr (N > 0) {
      prev<N - 1>();
  }
}
--it;

constexpr explicit iterator(tuple-or-pair<iterator_t<maybe-const<Const, Vs>>...> current);

Effects: Initializes current_ with std::move(current).

constexpr iterator(iterator<!Const> i)
  requires Const && (convertible_to<iterator_t<Vs>, iterator_t<maybe-const<Const, Vs>>> && ...);

Effects: Initializes current_ with std::move(i.current_).

  constexpr auto operator*() const;

Effects: Equivalent to:

 return tuple-transform([](auto& i) -> decltype(auto) { return *i; }, current_);

constexpr iterator& operator++();

Effects: Equivalent to:

next();
return *this;

constexpr iterator operator++(int);

Effects: Equivalent to:

auto tmp = *this;
++*this;
return tmp;

constexpr iterator& operator--() requires (bidirectional_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to:

prev();
return *this;

constexpr iterator operator--(int) requires (bidirectional_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to:

auto tmp = *this;
--*this;
return tmp;

constexpr iterator& operator+=(difference_type x) requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Sets the position of the iterators in current_:

• If x > 0, as if next was called x times.

• Otherwise, if x < 0, as if prev was called -x times.

• Otherwise, no effect.

constexpr iterator& operator-=(difference_type x) requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to:

*this += -x;
return *this;

constexpr reference operator[](difference_type n) const requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return *((*this) + n);.

friend constexpr bool operator==(const iterator& x, const iterator& y) 
requires (equality_comparable<iterator_t<maybe-const<Const, Vs>>> && ...);

Effects: Equivalent to return x.current_ == y.current_;.

friend constexpr auto operator<(const iterator& x, const iterator& y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return x.current_ < y.current_;.

friend constexpr auto operator>(const iterator& x, const iterator& y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return y < x;.

friend constexpr auto operator<=(const iterator& x, const iterator& y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return !(y < x);.

friend constexpr auto operator>=(const iterator& x, const iterator& y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return !(x < y);.

friend constexpr auto operator<=>(const iterator& x, const iterator& y)
requires (random_access_range<maybe-const<Const, Vs>>&&...)&& (three_way_comparable<maybe-const<Const, Vs>> && ...));

Effects: Equivalent to return x.current_ <=> y.current_;.

friend constexpr iterator operator+(const iterator& x, difference_type y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return iterator{ x } += y;.

friend constexpr iterator operator+(difference_type x, const iterator& y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return y + x;.

friend constexpr iterator operator-(const iterator& x, difference_type y) 
requires (random_access_range<maybe-const<Const, Vs>> && ...);

Effects: Equivalent to return iterator{ x } -= y;.

friend constexpr difference_type operator-(const iterator& x, const iterator& y)
requires (sized_sentinel_for<iterator_t<maybe-const<Const, Vs>>, iterator_t<maybe-const<Const, Vs>>> && ...);

Effects: Let scaled_distance(x,y,N) be the distance between (get<N>(x.current_) - get<N>(y.current_)) * get<N>(x.parent_->bases_). Returns the sum of scaled_distance(x,y,N) for every N in the interval (0, sizeof...(Vs)].

5.1.4. Class template cartesian_product_view::sentinel [ranges.cartesian.sentinel]

template <bool Const>
class sentinel {
    using parent = maybe-const<Const, cartesian_product_view>; //exposition only
    using first_base = decltype(get<0>(std::declval<parent>().bases_)); //exposition only
    sentinel_t<first_base> end_; //exposition only

public:
    sentinel() = default;
    sentinel(std::ranges::sentinel_t<first_base> end);

    friend constexpr bool operator==(sentinel const& s, iterator_t<parent> const& it);

    constexpr sentinel(sentinel<!Const> other) 
    requires Const &&
         (std::convertible_to<std::ranges::sentinel_t<first_base>, std::ranges::sentinel_t<const first_base>>);
};

sentinel(std::ranges::sentinel_t<first_base> end);

Effects: Initialises end_ with std::move(end).

constexpr sentinel(sentinel<!Const> other) 
requires Const &&
    (std::convertible_to<std::ranges::sentinel_t<first_base>, std::ranges::sentinel_t<const first_base>>)
    : end_(other.end_) {}

Effects: Initialises end_ with std::move(other.end_).

friend constexpr bool operator==(sentinel const& s, iterator_t<parent> const& it);

Effects: Equivalent to return get<0>(it.current_) == s.end_;.

6. Acknowledgements

Thank you to Christopher Di Bella, Corentin Jabot, Tim Song, and Barry Revzin for feedback and guidance.