c++ - cartesian product indices generator

Question

I need a variant of the popular indices trick, that does a Cartesian product of 2 sequences of indices of possibly different lengths. Can you give hints/examples on how this might be done? Perhaps a link to a library.

EDIT: I could only come up with this:

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

Here's a rather straightforward and boring implementation.

#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

Sorry for the mistake. I meant:

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