5
\$\begingroup\$

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.

New contributor
Vladimir Reshetnikov is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
3
\$\begingroup\$

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);
}
\$\endgroup\$

Your Answer

Vladimir Reshetnikov is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.