TMP: how to generalize a Cartesian Product of Vectors?

Question

There is an excellent C++ solution (actually 2 solutions: a recursive and a non-recursive), to a Cartesian Product of a vector of integer vectors. For purposes of illustration/simplicity, let us just focus on the non-recursive version.

My question is, how can one generalize this code with templates to take a std::tuple of homogeneous vectors that looks like this:

{{2,5,9},{"foo","bar"}}

and generate a homogeneous vector of tuple

{{2,"foo"},{2,"bar"},{5,"foo"},{5,"bar"},{9,"foo"},{9,"bar"}}

If it makes life any easier, let us assume that the internal vectors in the input are each homogeneous. So inputs like this are not allowed: {{5,"baz"}{'c',-2}}

EDIT changed input from jagged vector to a tuple

Hautboy

This should be doable. Create an index<size> type of size_t (basically an n-tuple of size_t). Create a sequence template type with the values 0 through #vectors-1 in it. Create a template that deduces the type of the returned tuple. Create a recursive function that foreach's over each and every index in the returned cross product (pass in a function to generate the max index for a given depth). Use the seq to index the get()s on the index and on the tuple of vector, and wrap the call in a ()..., directly constructing the resulting tuple of elements. Then bob's your uncle. – Disproportionate

I wrote about half of it, but have to go to bed. :) Here is a use of the basic technique of using a sequence to unroll get calls: #13447563 and here is a pile of non-working code that might contain something useful: ideone.com/reaDYi – Disproportionate

Answer 1

Simpler recursive solution. It takes vectors as function arguments, not as a tuple. This version doesn't build temporary tuples, but uses lambdas instead. Now it makes no unnecessary copies/moves and seems to get optimized successfully.

#include<tuple>
#include<vector>

// cross_imp(f, v...) means "do `f` for each element of cartesian product of v..."
template<typename F>
inline void cross_imp(F f) {
    f();
}
template<typename F, typename H, typename... Ts>
inline void cross_imp(F f, std::vector<H> const& h,
                           std::vector<Ts> const&... t) {
    for(H const& he: h)
        cross_imp([&](Ts const&... ts){
                      f(he, ts...);
                  }, t...);
}

template<typename... Ts>
std::vector<std::tuple<Ts...>> cross(std::vector<Ts> const&... in) {
    std::vector<std::tuple<Ts...>> res;
    cross_imp([&](Ts const&... ts){
                  res.emplace_back(ts...);
              }, in...);
    return res;
}

#include<iostream>

int main() {
    std::vector<int> is = {2,5,9};
    std::vector<char const*> cps = {"foo","bar"};
    std::vector<double> ds = {1.5, 3.14, 2.71};
    auto res = cross(is, cps, ds);
    for(auto& a: res) {
        std::cout << '{' << std::get<0>(a) << ',' <<
                            std::get<1>(a) << ',' <<
                            std::get<2>(a) << "}\n";
    }
}

Kira

+1 for a nice, clean answer - so, if I also had a fs (for floats), a cs (for chars), and a ds (for doubles), I should compose it by recursively calling cross(), correct? – Hautboy

@Hautboy It's enough to call cross with more arguments. – Kira

PERFECT - I need to dig into your code to understand it better - I'm sure there are lots of techniques I could use in there. ty for taking the time to crank this out. – Hautboy

@Kira Decouple the type of pref and out, replace make_tuple with tie iterate for(auto&& he:h) with magic references, and you'd eliminate a tonne of redundant copies I think. – Disproportionate

@Yakk, I did it slightly differently, by using lambdas, but no redundant copies anymore. I like new version much more. – Kira

@Kira std::vector<Ts> gets copied a few times. :) Throw more & at it, and maybe a const or two... Oh, and cross_imp should be called for_each_cross, as it is a useful function on its own, not just an implementation detail. – Disproportionate

I like your update! I tried to adapt it to a more STL-like iterator only version, something like template<class OutputIt, class InputIt...> void cross_prod(OutputIt res, InputIt ins...). It gets a little tricky to convert a variadic pack of iterators to their value_type in the lambda that does something like *res++ = std::make_tuple( /* insert dereferenced iterators here! */); Any idea how that can be made to work? I can ask a new question if you like. – Getupandgo

@rhalbersma, like this ? – Kira

Ah great! I tried to do it without std::pair around the iterators and then of course I got double counting when inserting into the tuple. Here is a slightly rewritten version that passes all iterators by value to the lambdas (using [=] and mutable) and does some renaming as well. Thanks again for your great answer, this is a really useful tool for unit-testing (generate a bunch of objects based on the Cartesian product of constructor argument ranges). – Getupandgo

What the hell, this is awesome ! And it seems doable with C++14 constexprs too ! – Sprage

@TemplateRex, now with C++14 generic lambdas it's quite easy to do it without std::pair. – Kira

Answer 2

Been a while since I've been doing this, but here's a first attempt. No doubt it can be improved.

template<unsigned fixedIndex, class T>
class DynamicTupleGetter
{
    typedef typename std::tuple_element<fixedIndex, T>::type RetType;
public:
    static RetType get(unsigned dynIndex, const T& tupleInstance)
    {
        const RetType& ret = std::get<fixedIndex>(tupleInstance);

        if (fixedIndex == dynIndex)
            return ret;
        return DynamicTupleGetter<fixedIndex - 1, T>::get(dynIndex, tupleInstance);
    }

};

template<class T>
class DynamicTupleGetter<0, T>
{
    typedef typename std::tuple_element<0, T>::type RetType;
public:
    static RetType get(unsigned dynIndex, const T& tupleInstance)
    {
        assert(dynIndex == 0);
        return std::get<0>(tupleInstance);
    }
};
template<class Source>
struct Converter
{
    typedef typename std::tuple_element<0, Source>::type Zeroth;
    typedef typename std::tuple_element<1, Source>::type First;

    static const size_t size0 = std::tuple_size<Zeroth>::value;
    static const size_t size1 = std::tuple_size<First>::value;

    static const size_t  outerProductSize = size0 * size1;

    typedef typename std::tuple_element<0, Zeroth>::type BaseType0;
    typedef typename std::tuple_element<0, First>::type BaseType1;
    typedef typename std::tuple<BaseType0, BaseType1> EntryType;

    typedef std::array<EntryType, outerProductSize> DestinationType;

    DestinationType create(const Source& source)
    {
        Zeroth zeroth = std::get<0>(source);
        First first = std::get<1>(source);
        typedef typename DynamicTupleGetter<size0 -1, Zeroth> ZerothGetter;
        typedef typename DynamicTupleGetter<size1 -1, First> FirstGetter;
        DestinationType result;
        size_t resultIndex = 0;
        for(size_t i = 0; i < size0; ++i)
            for(size_t j = 0; j < size1; ++j)
            {
                std::get<0>(result[resultIndex]) = ZerothGetter::get(i, zeroth) ;        
                std::get<1>(result[resultIndex]) = FirstGetter::get(j, first); 
                ++resultIndex;
            }
            return result;
    }


};


template<class T>
void create(const T& source)
{
    Converter<T> converter;

    Converter<T>::DestinationType result = converter.create(source);

    std::cout << std::get<0>(std::get<3>(result)) << "," << std::get<1>(std::get<3>(result)) << std::endl;
}


auto intPart = std::make_tuple(2,5,9);
auto stringPart = std::make_tuple("foo","bar");
auto source = std::make_tuple(intPart, stringPart);

void f()
{
    create(source);
}

Fausta

+1 for working code - I had to tweak it a tiny bit to get it to compile on gcc 4.7.2, but it builds and passes the test in the OP. – Hautboy

will this code work for auto source = std::make_tuple( intPart, stringPart, charPart, floatPart )? – Hautboy

Answer 3

In C++23, the easiest solution is std::views::cartesian_product:

std::vector<int> ints{1, 2, 3};
std::vector<std::string_view> strings{"foo","bar"};

for (auto [x, str] : std::views::cartesian_product(ints, strings)) {
    std::println("{} {}", x, str);
}

This code prints

1 foo
1 bar
2 foo
2 bar
3 foo
3 bar

See live example at Compiler Explorer.

Caren