如何将向量的笛卡尔积进行泛化？

Question

有一种很好的C++解决方案（实际上有两种解决方案：递归和非递归），可以对一个整数向量向量进行笛卡尔积。为了说明/简化，让我们只关注非递归版本。

我的问题是，如何使用模板将代码推广到像这样的同质向量的std::tuple： {{2,5,9}，{"foo"，"bar"}} 并生成 tuple 的同质向量 {{2，“foo”}，{2，“bar”}，{5，“foo”}，{5，“bar”}，{9，“foo”}，{9，“bar”}} 如果这样做能够使生活更轻松，请假设输入中的内部向量是同质的。因此，不允许这样的输入：{{5，“baz”} {'c'，-2}} 编辑将输入从锯齿状向量更改为元组

- kfmfe04

---

这应该是可行的。创建一个 index<size> 类型的 size_t（基本上是 size_t 的 n 元组）。创建一个序列模板类型，其中包含值为 0 到 #vectors-1。创建一个推断返回元组类型的模板。创建一个递归函数，对返回的笛卡尔积中的每个索引进行循环遍历（传入一个函数来生成给定深度的最大索引）。使用 seq 在 vector 的 index 和 tuple 上进行索引，并将调用包装在 ()... 中，直接构造结果元素的 tuple。然后就完成了。 - Yakk - Adam Nevraumont

我已经写了一半，但是必须去睡觉 :) 这里有一个使用基本技巧的例子，使用序列展开get调用：http://stackoverflow.com/questions/13447063/how-would-i-generate-variadic-parameters/13448540#13448540 以及这里有一堆无法工作的代码，可能包含一些有用的东西：http://ideone.com/reaDYi - Yakk - Adam Nevraumont

Answer 1

更简单的递归解决方案。它将向量作为函数参数，而不是作为元组。此版本不会构建临时元组，而是使用lambda代替。现在它不会进行不必要的复制/移动，并且似乎可以成功优化。

#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";
    }
}

- zch

---

如果我还有一个用于浮点数的fs，一个用于字符的cs和一个用于双精度的ds，那么我应该通过递归调用cross()来组合它，对吗？如果您能提供一个漂亮、干净的答案，我会给您加1分。 - kfmfe04

@zch 解耦 pref 和 out 的类型，用 tie 替换 make_tuple，使用魔法引用迭代 for(auto&& he:h)，这样可以消除大量冗余的拷贝。 - Yakk - Adam Nevraumont

@Yakk，我用lambda表达式稍微不同的方式实现了它，但不再有冗余的副本。我更喜欢新版本。 - zch

这真是太棒了！而且似乎可以使用C++14的constexpr实现！ - Quentin

@TemplateRex，现在有了C++14的通用lambda表达式，很容易做到这一点无需使用std::pair。 - zch

Answer 2

我已经有一段时间没有做这个了，但这是我的第一次尝试。毫无疑问，它可以得到改进。

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);
}

- Keith

---

+1，代码可用 - 我稍微调整了一下才能在gcc 4.7.2上编译通过，但它可以构建并通过OP的测试。 - kfmfe04

这段代码能用于 auto source = std::make_tuple(intPart, stringPart, charPart, floatPart) 吗？ - kfmfe04