Help with c++ template templates.

Question

Ok, so I wrote an stl-like algorithm called cartesian_product. For those who don't know, the cartesian product is every possible pair of elements from two sets. So the cartesian product of {1, 2, 3} and {10, 20, 30} is

{(1,10), (1,20), (1,30), (2,10), (2,20), (2,30), (3,10), (3,20), (3,30)}

So the function looks like

template <typename InIt1, typename InIt2, typename OutIt>
void
cartesian_product(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt out)
{
    for (; first1 != last1; ++first1)
     for (InIt2 it = first2; it != last2; ++it)
      *out++ = std::make_pair(*first1, *it);
}

There aren't template typedefs, so I made a traits class to hold the type that the output iterator is from:

template <typename ObjA, typename ObjB, template <typename> class Container>
struct cartesian_product_traits
{
    typedef Container<std::pair<ObjA, ObjB> > type;
};

So then I can say:

typedef cartesian_product_traits<int, int, std::vector>::type IntPairList;
IntPairList my_list;
cartesian_product(v1.begin(), v1.end(), 
                  v2.begin(), v2.end(),
                  std::back_inserter(my_list);

but this doesn't seem to compile. I get a nice error:

error C3201: the template parameter list for class template 'std::vector' does not match the template parameter list for template parameter 'Container'

So I'm stumped. How do I get this to work?

Answer 1

The template parameter list for vector isn't just one element, it takes two:

template < class T, class Allocator = allocator<T> > class vector

so in order to accept vector, you need to have a template template parameter with two blanks:

template <typename ObjA, typename ObjB, template <typename, typename> class Container>
struct cartesian_product_traits

Edited: cut some advice, misread your code.

The way to do this properly would be to use a variadic macro on the template template parameter:

template <typename ObjA, typename ObjB, template <typename ...> class Container>
struct cartesian_product_traits

But that's far away from being a standard. If it were my code, I'd probably just have the consumers pound out the full template:

std::vector< std::pair<int, int> >

is shorter than

cartesian_product_traits<int, int, vector>

and the latter would only help if the definition for a Cartesian product changed.

Answer 2

std::vector's template is actually quite complex (with optional template parameters for allocators &c) -- and other containers in the stdlib aren't any simpler either. In your shoes, I'd make the third parameter of cartesian_product_traits into a plain typename PairsContainer and depend on the caller to go to the small trouble of passing it as a suitable container of pairs.