笛卡爾產品索引生成器

Question

我需要一個流行的indices trick變體，它可能會產生2個可能長度不同的索引序列的笛卡爾乘積。你能提供一些提示/例子說明如何做到這一點？也許是一個圖書館的鏈接。

編輯：我只能想出這樣的：

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

template <typename T, typename U> 
struct pair 
{ 
    typedef T first; 
    typedef U second; 
}; 

template <std::size_t i> 
using index = std::integral_constant<std::size_t, i>; 

template <std::size_t ON, std::size_t M, std::size_t N, typename ...Ps> 
struct cartesian 
    : std::conditional<bool(N), 
     cartesian<ON, M, N - 1, pair<index<M>, index<N> >, Ps...>, 
     cartesian<ON, M - 1, ON, pair<index<M>, index<N> >, Ps...> 
    >::type 
{ 
}; 

template <std::size_t ON, typename ...Ps> 
struct cartesian<ON, 0, 0, Ps...> 
    : list<pair<index<0>, index<0> >, Ps...> 
{ 
}; 

template <std::size_t M, std::size_t N> 
struct make_cartesian : cartesian<N - 1, M - 1, N - 1> 
{ 
    static_assert(M > 0, "M has to be greater than 0"); 
    static_assert(N > 0, "N has to be greater than 0"); 
}; 

Answer 1

這是一個相當直接和無聊的實現。

#include <cstdlib> 
#include <iostream> 

namespace ct { 

    template <typename, typename> 
    struct pair {}; 

    template <typename... a> 
    struct list {}; 

    template <typename a, typename... b> 
    struct cons_t; 

    template <typename a> 
    struct cons_t<a, list<>> 
    { 
    using type = list<a>; 
    }; 

    template <typename a, typename bh, typename... bt> 
    struct cons_t<a, list<bh, bt...>> 
    { 
    using type = list<a, bh, bt...>; 
    }; 

    template <typename a, typename... b> 
    struct concat_t; 

    template <typename b> 
    struct concat_t<list<>, b> 
    { 
    using type = b; 
    }; 

    template <typename b, typename ah, typename... at> 
    struct concat_t<list<ah, at...>, b> 
    { 
    using type = typename cons_t<ah, typename concat_t<list<at...>, b>::type>::type; 
    }; 

    template <typename a, typename b> 
    using cons = typename cons_t<a,b>::type; 
    template <typename a, typename b> 
    using concat = typename concat_t<a,b>::type; 

    template <typename a, typename b> 
    struct cartesian1; 

    template <typename a> 
    struct cartesian1<a, list<>> 
    { 
    using type = list<>; 
    }; 

    template <typename a, typename bh, typename... bt> 
    struct cartesian1<a, list<bh, bt...>> 
    { 
    using type = cons<pair<a, bh>, typename cartesian1<a, list<bt...>>::type>; 
    }; 

    template <typename a, typename b> 
    struct cartesian_t; 

    template <typename a> 
    struct cartesian_t<list<>, a> 
    { 
    using type = list<>; 
    }; 

    template <typename ah, typename b, typename... at> 
    struct cartesian_t<list<ah, at...>, b> 
    { 
    using type = concat<typename cartesian1<ah, b>::type, 
         typename cartesian_t<list<at...>, b>::type>; 
    }; 

    template <typename a, typename b> 
    using cartesian = typename cartesian_t<a,b>::type; 

    template <size_t x> 
    struct val {}; 

    template <size_t... a> 
    struct vlist {}; 

    template <typename t> 
    struct vlist2list_t; 

    template <> 
    struct vlist2list_t<vlist<>> 
    { 
    using type = list<>; 
    }; 

    template <size_t ah, size_t... at> 
    struct vlist2list_t<vlist<ah, at...>> 
    { 
    using type = cons<val<ah>, typename vlist2list_t<vlist<at...>>::type>; 
    }; 

    template <typename a> 
    using vlist2list = typename vlist2list_t<a>::type; 

    template <size_t...a> 
    using vl = vlist2list<vlist<a...>>; 

    template<size_t x1, size_t x2> 
    std::ostream& operator<< (std::ostream& s, 
          pair<val<x1>, val<x2>> z) 
    { 
    s << "(" << x1 << "," << x2 << ")"; 
    return s; 
    } 


    std::ostream& operator<< (std::ostream& s, 
          list<> z) 
    { 
    s << "[]"; 
    } 

    template <typename ah, typename... at> 
    std::ostream& operator<< (std::ostream& s, 
          list<ah, at...> z) 
    { 
    s << ah() << ":" << list<at...>(); 
    } 

} 

int main() 
{ 
    using a = ct::cartesian<ct::vl<1,2,3>, ct::vl<4,5,6>>; 
    std::cout << a() << std::endl; 
} 

Answer 2

對不起，我錯了。我的意思是：

template<class InIter, class OutIter> 
OutIter cartesian_product(InIter first1, InIter last1, InIter first2, InIter last2, 
OutIter output) { 
for (auto It1 = first1 ; It1 != last1; ++It1) 
    for (auto It2 = first2; It2 != last2; ++It2) 
    *output++ = *It1 * *It2; 
}