How to convert a tuple of vectors into a vector of tuples using the Cartesian product?

Question

For the purpose of unit testing classes with std::tuple constructors, I'd like to generate a sample of special cases plus random values for the constructor arguments. Say that I have a std::tuple of std::vector<T1> through std::vector<Tn>, (where each of the Ti are different) how can I convert this into a std::vector of the full Cartesian product of all std::tuple<T1, ..., Tn> combinations?

Specifically, I'd like to have a variadic function template that looks something like this:

template<typename... Args>
std::vector<std::tuple<Args...> cartesian_product(std::vector<Args>...)
{
    // template magic or fat mulitple loops?
}

and can be used like this:

// some type to be tested
class MyType
{
    MyType(std::tuple<int, bool, std::string>);
    // bla
};

// test values for each constructor argument
std::tuple< std::vector<int>, std::vector<bool>, std::vector<std::string> > input {
    { 1, 2, 3}, { false, true}, { "Hello", "World"}
};

// should become 3 x 2 x 2 = 12 cases { {1, false, "Hello"}, ... , {3, true, "World"} } 
std::vector< std::tuple<int, bool, std::string> > test_cases = cartesian_product( input );

// can write flat single loop over all cases
for (auto t: test_cases) {
    BOOST_CHECK(MyType(t).my_test());
}

Are there any (Boost) libraries that can do this out-of-the-box? How involved is writing variadic templates for this?

@zch that's great, I even browsed that one, but somehow it didn't look like the full general solution but "only" one for the 2-argument case. Sorry to have missed that (it's deceptively simple!). — TemplateRex, May 15 '13 at 18:40
It's general, I'll add third dimension to example to make it clearer (even though it was mentioned in comment there). — zch, May 15 '13 at 18:53
@zch I tested it, and it does exactly that I want. Really cool trick. — TemplateRex, May 15 '13 at 18:55

Yakk - Adam Nevraumont · Accepted Answer · 2013-05-15T19:03:00.837

http://ideone.com/ThhAoa

Not that tricky:

#include <cstddef>
#include <utility>
#include <vector>
#include <tuple>
#include <string>
#include <iostream>

using std::size_t;

template<size_t...> struct seq {};
template<size_t Min, size_t Max, size_t... s>
struct make_seq:make_seq< Min, Max-1, Max-1, s... > {};
template<size_t Min, size_t... s>
struct make_seq< Min, Min, s... > {
    typedef seq<s...> type;
};
template<size_t Max, size_t Min=0>
using MakeSeq = typename make_seq<Min, Max>::type;

size_t product_size() {
  return 1;
}
template<typename... Sizes>
size_t product_size( size_t x, Sizes... tail ) {
  return x * product_size(tail...);
}
namespace details {
  template<typename max_iterator, typename Lambda>
  void for_each_index( max_iterator mbegin, max_iterator mend, Lambda&& f, std::vector<size_t>& idx ) {
    if (mbegin == mend) {
      f(idx);
    } else {
      for (size_t i = 0; i < *mbegin; ++i) {
        idx.push_back(i);
        for_each_index(mbegin+1, mend, f, idx);
        idx.pop_back();
      }
    }
  }
  template<typename Lambda>
  void for_each_index( std::vector<size_t> const& maxes, Lambda&& f ) {
    std::vector<size_t> idx;
    details::for_each_index( maxes.begin(), maxes.end(), f, idx );
  }
  template<size_t... s, typename... Ts>
  std::vector< std::tuple<Ts...> > does_it_blend( seq<s...>, std::tuple< std::vector<Ts>... >const& input ) {
    std::vector< std::tuple<Ts...> > retval;
    retval.reserve( product_size( std::get<s>(input).size()... ) );
    std::vector<size_t> maxes = {
      (std::get<s>(input).size())...
    };
    for_each_index( maxes, [&](std::vector<size_t> const& idx){
      retval.emplace_back( std::get<s>(input)[idx[s]]... );
    });
    return retval;
  }
}
template<typename... Ts>
std::vector< std::tuple<Ts...> > does_it_blend( std::tuple< std::vector<Ts>... >const& input ) {
  return details::does_it_blend( MakeSeq< sizeof...(Ts) >(), input );
}

int main() {
  std::tuple< std::vector<int>, std::vector<bool>, std::vector<std::string> > input {
    { 1, 2, 3}, { false, true}, { "Hello", "World"}
  };

  // should become 3 x 2 x 2 = 12 cases { {1, false, "Hello"}, ... , {3, true, "World"} } 
  std::vector< std::tuple<int, bool, std::string> > test_cases = does_it_blend( input );

  for( auto&& x:test_cases ) {
    std::cout << std::get<0>(x) << "," << std::get<1>(x) << "," << std::get<2>(x) << "\n";
  }
}

Here I create a function that does a Cartesian product of the possible indexes, then creates the tuples directly in the output container.

I also do the bother of reserving the output size.

Now with less code.

+1 Thanks for this working answer! Compared to the one of @zch (which is 40% of the number of lines of yours), what advantages does it have? — TemplateRex, May 15 '13 at 19:02
@rhalbersma Well, hadn't read that one. One advantage is that I'm `emplace`ing the results directly into the output `std::vector`, while that code does a lot of `move`s and `copy`s on first inspection. — Yakk - Adam Nevraumont, May 15 '13 at 19:07
Well, I accept it of course, nice to know that it can be done in different ways. — TemplateRex, May 15 '13 at 19:12
@rhalbersma The pattern is very similar: I do the build up of the cross product in the indexes, she does it directly in the resulting `tuple`. The two `cross_imp` overloads correspond nearly one-to-one to my `for_each_index`, and `does_it_blend` to her `cross` (I have some extra boilerplate). It would be more similar if I replaced my `maxes` vector with a variardic set of `size_t` maxes. Amusing! — Yakk - Adam Nevraumont, May 15 '13 at 19:34

score 1 · Answer 2 · answered May 15 '13 at 19:50

1

Does this help?

#include <vector>
#include <tuple>
#include <type_traits>

template <typename... T>
struct transpose {};

template <typename... T>
struct transpose<std::tuple<std::vector<T>...>>
{
    using type = std::vector<std::tuple<T...>>;
};

template <typename... T>
struct transpose<std::vector<std::tuple<T...>>>
{
    using type = std::tuple<std::vector<T>...>;
};

int main()
{
    std::tuple<std::vector<int>, std::vector<bool>> var;

    static_assert(
        std::is_same<
            transpose<decltype(var)>::type,
            std::vector<std::tuple<int, bool>>
       >::value, ""
    );
}

answered May 15 '13 at 19:50

David G

94,763
41
167
253

that transforms the types, but how would I use it to transform the actual values in my example `main()` function, and how would this be used for the Cartesian product? – TemplateRex May 15 '13 at 20:11
@rhalbersma I'll try to add an edit in a little while. – David G May 15 '13 at 20:13

How to convert a tuple of vectors into a vector of tuples using the Cartesian product?

2 Answers2