Cartesian product of std::tuple

user_9938686 0
Viewed 201

For unit testing a C++17 framework that relies heavily on templates I tried to write helper template classes which generate a Cartesian product of two sets of data types given by two tuples:

**Input**: std::tuple <A, B> std::tuple<C,D,E>

**Expected output**: Cartesian product of the two tuples: 
std::tuple<std::tuple<A,C>, std::tuple<A,D>, std::tuple<A,E>,
std::tuple<B,C>, std::tuple<B,D>, std::tuple<B,E>>

I am aware that Boost MP11 offers such features but I would not like to include a dependency on yet another library just for testing purposes. So far I came up with a pretty straight forward solution which though requires the class to be default-constructible (Try it here!):

template <typename T1, typename T2,
          typename std::enable_if_t<is_tuple_v<T1>>* = nullptr,
          typename std::enable_if_t<is_tuple_v<T2>>* = nullptr>
class CartesianProduct {
  protected:
    CartesianProduct() = delete;
    CartesianProduct(CartesianProduct const&) = delete;
    CartesianProduct(CartesianProduct&&) = delete;
    CartesianProduct& operator=(CartesianProduct const&) = delete;
    CartesianProduct& operator=(CartesianProduct&&) = delete;
    
    template <typename T, typename... Ts,
              typename std::enable_if_t<std::is_default_constructible_v<T>>* = nullptr,
              typename std::enable_if_t<(std::is_default_constructible_v<Ts> && ...)>* = nullptr>
    static constexpr auto innerHelper(T, std::tuple<Ts...>) noexcept {
      return std::make_tuple(std::make_tuple(T{}, Ts{}) ...);
    }
    template <typename... Ts, typename T,
              typename std::enable_if_t<std::is_default_constructible_v<T>>* = nullptr,
              typename std::enable_if_t<(std::is_default_constructible_v<Ts> && ...)>* = nullptr>
    static constexpr auto outerHelper(std::tuple<Ts...>, T) noexcept {
      return std::tuple_cat(innerHelper(Ts{}, T{}) ...);
    }
  public:
    using type = std::decay_t<decltype(outerHelper(std::declval<T1>(), std::declval<T2>()))>;
};
template <typename T1, typename T2>
using CartesianProduct_t = typename CartesianProduct<T1, T2>::type;

Also when trying to instantiate a list of template classes in a similar way (try it here) I have to make the same assumption: I can't apply it to classes which have a protected/private constructor (without a friend declaration) and are not-default-constructible.

Is it possible to lift the restriction of default constructability without turning to an std::integer_sequence and an additional helper class? From what I understand it is not possible to use std::declval<T>() directly in the methods innerHelper and outerHelper (which would solve my issue), as it seems to not be an unevaluated expression anymore. At least GCC complains then about static assertion failed: declval() must not be used! while it seems to compile fine with Clang.

Thank you in advance!

variadic-templates c++17 tuples templates c++
3 Answers

One of the workarounds is to omit the function definition and directly use decltype to infer the return type:

template<typename T1, typename T2>
class CartesianProduct {
  template<typename T, typename... Ts>
  static auto innerHelper(T&&, std::tuple<Ts...>&&) 
  -> decltype(
       std::make_tuple(
         std::make_tuple(std::declval<T>(), std::declval<Ts>())...));

  template <typename... Ts, typename T>
  static auto outerHelper(std::tuple<Ts...>&&, T&&) 
  -> decltype(
       std::tuple_cat(innerHelper(std::declval<Ts>(), std::declval<T>())...));

 public:
  using type = decltype(outerHelper(std::declval<T1>(), std::declval<T2>()));
};

class Example {
  Example() = delete;
  Example(const Example&) = delete;
};

using T1 = std::tuple<Example>;
using T2 = std::tuple<int, double>;
static_assert(
  std::is_same_v<
    CartesianProduct_t<T1, T2>, 
    std::tuple<std::tuple<Example, int>, std::tuple<Example, double>>>);

Demo.

user_116387180

Something along these lines perhaps:

template <typename TupleA, typename TupleB>
struct CartesianProduct {
  static constexpr size_t SizeA = std::tuple_size_v<TupleA>;
  static constexpr size_t SizeB = std::tuple_size_v<TupleB>;
  template <size_t I>
  static constexpr size_t Col = I / SizeB;
  template <size_t I>
  static constexpr size_t Row = I % SizeB;

  template <size_t ... Is>
  static
  std::tuple<
    std::tuple<
      std::tuple_element_t<Col<Is>, TupleA>,
      std::tuple_element_t<Row<Is>, TupleB>
    >...>
  Helper(std::index_sequence<Is...>);

  using type = decltype(Helper(std::make_index_sequence<SizeA*SizeB>{}));
};

Demo

user_16701290

In c++20 because it is shorter. Adding template types should be obvious. Also omitting perfect forwarding boilerplate.

auto cartesian(auto ts0, auto ts1){
  return std::apply([&](auto...t0s){
    return std::tuple_cat([&](auto t0s){ // glue (xk)x(ys...) together
      return std::apply([&](auto...t1s){
        return std::make_tuple(
           std::make_tuple(t0s, t1s)...
        ); // ((xk,y0),(xk,y1),...)
      }, ts1); // turning ts1 into t1s...
    }(t0s)...); // "laundering" the t0s... into t0s non-pack, then gluing
  }, ts0); // turning ts0 into t0s...
}

or something like that.

The first apply splits the first tuple into arguments.

For each of those arguments, we build the tuples ((x,y0),(x,y1),(x,y2)...), then we concatinate them together.

A slight of hand is done to control which ... expansion occurs to what elements; we "launder" the first tuple's arguments through a lambda, so they are a single value not a pack when the second one is expanded.

Then just do

template<class T0, class T1>
using cart_t = decltype( cartesian( std::declval<T0>(), std::declval<T1>() ) );

This does require that the types be copy/movable.

There are two obvious ways around that. The first is to lift the types to tags, do the product, then pull down.

The second is to operate on type lists instead of tuples. It is possible you are using tuples as type lists, so we don't even have to lift it back to tuples.

user_17746670
Related