A cartesian product of tuples in C++17

Question

I would like to write a function that computes a cartesian product of two tuples in C++17 (the tuples can be of type std::tuple or std::pair, or any other type that can be used with std::apply). The tuples can be of different types and sizes, and the resulting std::tuple has to contain all std::pairs of elements, where the first element of a pair is from the first tuple, and the second element is from the second tuple. The function must be suitable for use in a constexpr context.

My approach is to use std::apply to effectively convert a tuple to a parameter pack, and then to recursively apply a generic lambda to it to build the result. Because a lambda cannot be explicitly recursive, I pass a reference to it to itself as an additional parameter self.

#include <functional>
#include <tuple>
#include <utility>

template<class X, class Y>
constexpr auto cartesian_product(const X& tx, const Y& ty) {
    if constexpr (std::tuple_size_v<X> == 0) return std::make_tuple();
    else return std::apply([&](const auto& ... ys) {
        return std::apply([&](const auto& ... xs) {
            const auto recursive = [&](
                const auto& self, 
                const auto& arg, const auto& ... args) 
            {
                if constexpr (sizeof...(args) == 0)
                    return std::make_tuple(std::make_pair(arg, ys)...);
                else return std::tuple_cat(
                        std::make_tuple(std::make_pair(arg, ys)...), 
                        self(self, args...));
            };
            return recursive(recursive, xs...);
        }, tx);
    }, ty);
}

// Test
constexpr auto x = std::make_tuple('a', 2);
constexpr auto y = std::make_tuple(true, std::optional<long>{});
constexpr auto result = cartesian_product(x, y);

static_assert(result == std::make_tuple(
    std::make_pair('a', true),
    std::make_pair('a', std::optional<long>{}),
    std::make_pair(2,   true),
    std::make_pair(2,   std::optional<long>{})));

I would appreciate any comments or suggestions how to simplify or improve this code.

---

Update: A generalization to an arbitrary number of factors in the cartesian product (the components of the result are now tuples rather than pairs):

#include <functional>
#include <tuple>
#include <utility>

constexpr std::tuple<std::tuple<>> cartesian_product() {
    return {{}};
}

template<class X, class ... Y>
constexpr auto cartesian_product(const X& tx, const Y& ... ty) {
    if constexpr (std::tuple_size_v<X> == 0) return std::make_tuple();
    else return std::apply([&](const auto & ... tuples) {
        return std::apply([&](const auto & ... xxs) {
            const auto recursive = [&](
                const auto& self, 
                const auto& x, const auto& ... xs) 
            {
                    auto tuple = std::make_tuple(
                        std::tuple_cat(std::make_tuple(x), tuples)...);
                    if constexpr (sizeof...(xs) == 0) return tuple;
                    else return std::tuple_cat(std::move(tuple), self(self, xs...));
            };
            return recursive(recursive, xxs...);
        }, tx);
    }, cartesian_product(ty...));
}

constexpr auto x = std::make_tuple('a', 2);
constexpr auto y = std::make_tuple(true, std::optional<long>{});
constexpr auto z = std::make_tuple(1L);
constexpr auto result = cartesian_product(x, y, z);
static_assert(result == std::make_tuple(
    std::make_tuple('a', true, 1L),
    std::make_tuple('a', std::optional<long>{}, 1L),
    std::make_tuple(2,   true, 1L),
    std::make_tuple(2,   std::optional<long>{}, 1L)));

I do not like std::make_tuple(x) part, but do not see a better way to prepend an element to a tuple.

Answer 1

You actually hint at the primary concern with your note about std::make_tuple(), std::tuple_cat() and gradually building up the result.
The point is that you have much copying with a plethora of temporaries going on.

Also, quite a bit of recursion.

Use index_sequences, the power of template parameter pack expansion, and forwarding using std::forward_as_tuple() and you can flatten it, as well as only copy directly from the source to the destination without intermediate steps.

While you are at it, ponder noexcept.

#include <utility>
#include <tuple>

namespace detail {
    template <class T>
    constexpr std::size_t tuple_size_v = std::tuple_size_v<std::decay_t<T>>;

    template <std::size_t I, class T, std::size_t... N>
    static constexpr auto index_helper(std::index_sequence<N...>) noexcept {
        return (1 * ... * (I < N ? tuple_size_v<std::tuple_element_t<N, T>> : 1));
    }
    template <std::size_t N, std::size_t I, class T>
    static constexpr auto index() noexcept {
        return N
            / index_helper<I, T>(std::make_index_sequence<tuple_size_v<T>>())
            % tuple_size_v<std::tuple_element_t<I, T>>;
    }

    template <std::size_t N, class T, std::size_t... I>
    static constexpr auto cartesian_product(T t, std::index_sequence<I...>) noexcept {
        return std::forward_as_tuple(std::get<index<N, I, T>()>(std::get<I>(t))...);
    }
    template <class T, std::size_t... N>
    static constexpr auto cartesian_product(T t, std::index_sequence<N...>) noexcept {
        return std::make_tuple(cartesian_product<N>(t, std::make_index_sequence<tuple_size_v<T>>())...);
    }

    template <class T>
    auto tuple_no_ref(T t)
    { return std::apply([](auto&&... x){ return std::make_tuple(x...); }, t); }
    template <class T>
    auto tuple2_no_ref(T t)
    { return std::apply([](auto&&... x){ return std::make_tuple(tuple_no_ref(x)...); }, t); }
}

template <class... T>
constexpr auto cartesian_product_ref(T&&... t) noexcept {
    constexpr auto N = sizeof...(T) ? (1 * ... * detail::tuple_size_v<T>) : 0;
    return detail::cartesian_product(std::forward_as_tuple(t...), std::make_index_sequence<N>());
}

template <class... T>
constexpr auto cartesian_product(T&&... t)
noexcept(noexcept(decltype(detail::tuple2_no_ref(cartesian_product_ref(t...)))(cartesian_product_ref(t...))))
{
    auto r = cartesian_product_ref(t...);
    using R = decltype(detail::tuple2_no_ref(r));
    return R(r);
}