Cartesian product of std::tuple

Question

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!

You can have a look at the `zip::with` example from *cppreference*, it seems to work without any assumptions about constructability of the types [here](https://en.cppreference.com/w/cpp/language/parameter_pack#:~:text=template%3Cclass%20...Args1%3E%20struct%20zip). PS: Obviously not your solution, but just a hint. — Oliver Tale-Yazdi, Dec 18 '21 at 15:45
@OliverTale-Yazdi Thanks for your comment. I was aware of expanding two parameter packs of same length simultaneously: It could be an alternative to my `innerHelper`. I would though be interested in fixing this solution, as I encountered it already a couple of times. So far assuming default-constructible classes has not been a problem (as it has been mainly primitive data types and trait structs) but would be nice to lift this restrictions somehow. — 2b-t, Dec 18 '21 at 15:55
Are you looking for this https://stackoverflow.com/questions/9122028/how-to-create-the-cartesian-product-of-a-type-list — cigien, Dec 18 '21 at 15:55
@cigien It seems similar but is not the exactly what I need. I will have a look at it. Maybe I can adapt it somehow to fit my needs. Thanks! — 2b-t, Dec 18 '21 at 15:59

康桓瑋 · Accepted Answer · 2021-12-18T16:21:46.507

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.

The trailing return type is an excellent idea! This way I do not have the problem with the evaluated expression but can still keep the same logic (also with my other classes that follow a similar design pattern). Thank you very much! — 2b-t, Dec 18 '21 at 16:30

Igor Tandetnik · Answer 2 · 2021-12-18T16:19:34.037

2

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

edited Dec 18 '21 at 16:19

answered Dec 18 '21 at 16:11

Igor Tandetnik

50,461
4
56
85

Nice solution but I will accept the other answer as it addresses the problem with `std::declval` and I can apply his solution also to other classes which I have designed with the same structure. Thanks a lot nonetheless! – 2b-t Dec 18 '21 at 16:26

Yakk - Adam Nevraumont · Answer 3 · 2021-12-19T14:56:37.487

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.

As always a very interesting solution! You are indeed a master of templates, Adam. Thanks a lot! — 2b-t, Dec 18 '21 at 20:44

Cartesian product of std::tuple

3 Answers3