A cartesian product of tuples in C++17 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 &lt;functional&gt;
#include &lt;tuple&gt;
#include &lt;utility&gt;

template&lt;class X, class Y&gt;
constexpr auto cartesian_product(const X&amp; tx, const Y&amp; ty) {
    if constexpr (std::tuple_size_v&lt;X&gt; == 0) return std::make_tuple();
    else return std::apply([&amp;](const auto&amp; ... ys) {
        return std::apply([&amp;](const auto&amp; ... xs) {
            const auto recursive = [&amp;](
                const auto&amp; self, 
                const auto&amp; arg, const auto&amp; ... 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&lt;long&gt;{});
constexpr auto result = cartesian_product(x, y);

static_assert(result == std::make_tuple(
    std::make_pair('a', true),
    std::make_pair('a', std::optional&lt;long&gt;{}),
    std::make_pair(2,   true),
    std::make_pair(2,   std::optional&lt;long&gt;{})));


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 &lt;functional&gt;
#include &lt;tuple&gt;
#include &lt;utility&gt;

constexpr std::tuple&lt;std::tuple&lt;&gt;&gt; cartesian_product() {
    return {{}};
}

template&lt;class X, class ... Y&gt;
constexpr auto cartesian_product(const X&amp; tx, const Y&amp; ... ty) {
    if constexpr (std::tuple_size_v&lt;X&gt; == 0) return std::make_tuple();
    else return std::apply([&amp;](const auto &amp; ... tuples) {
        return std::apply([&amp;](const auto &amp; ... xxs) {
            const auto recursive = [&amp;](
                const auto&amp; self, 
                const auto&amp; x, const auto&amp; ... 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&lt;long&gt;{});
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&lt;long&gt;{}, 1L),
    std::make_tuple(2,   true, 1L),
    std::make_tuple(2,   std::optional&lt;long&gt;{}, 1L)));


I do not like std::make_tuple(x) part, but do not see a better way to prepend an element to a tuple.
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 &lt;utility&gt;
#include &lt;tuple&gt;

namespace detail {
    template &lt;class T&gt;
    constexpr std::size_t tuple_size_v = std::tuple_size_v&lt;std::decay_t&lt;T&gt;&gt;;

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

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

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

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

template &lt;class... T&gt;
constexpr auto cartesian_product(T&amp;&amp;... 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);
}