Template Template Parameters

Here’s a good interview question or riddle for seasoned C++ developers. You’re asked to design a set of template functions for automatic conversion of data from one type to another.

First of all, you’re expected to have a function called scalar_convert<T> for converting values of type T to values of another type that depends on T. Part of the assignment is to come up with a mapping between T and the target type without requiring the caller to pass it along as a template parameter.

Next, you’re expected to have a function called vector_convert for converting containers of element type T to the same container of another element type that would be produced by calling scalar_convert<T> on the container’s elements. This method should work not only with std::vector, but with any push_back style container in the STL (e.g. std::list but not std::set).

The first challenge is relatively easy to address. You write a template function that does nothing, and then specialize it for each conversion. To deduce the target type of the conversion, you can use an auxiliary structure that is also specialized for each T, as follows:

template <typename T>
struct convert_traits { typedef T to_type; };

template <>
struct convert_traits<int> { typedef double to_type; };

template <>
struct convert_traits<double> { typedef int to_type; };

Next, you can define scalar_convert<T>’s return value in terms of convert_traits:

template <typename In>
typename convert_traits<In>::to_type scalar_convert(const In&) { return convert_traits<In>::to_type(); }

template <> int scalar_convert<double>(const double& d) { return (int)d; }
template <> double scalar_convert<int>(const int& n) { return n; }

Now that we have that in place, what about the containers? This is the harder part, that warrants the title of this post. One approach would be to have the target container passed by reference and then filled from the source container. This is really trivial:

template <typename In, typename Out>
void convert3(const In& inCont, Out& outCont)
{
    for (In::const_iterator it = inCont.begin(); it != inCont.end(); ++it)
        outCont.push_back(scalar_convert(*it));
}

This leaves to the original scalar_convert<T> all the trouble of specifying what the element type of the target container should be.

What’s much less trivial is the original requirement that you return an instance of the new container filled with the converted elements. After all, how can you create a new instance of a container with a different element type if you don’t know in advance what container it’s going to be?

Enter template template parameters, which are covered in more detail here. Basically, a template template parameter allows you to specify that a template parameter is in fact a template in itself, and has template parameters that you can, in turn, specify.

In our case:

template <typename In, template <typename _X,
                                 typename _Alloc = std::allocator<_X>>
                       class Cont>
Cont<typename convert_traits<In>::to_type> vector_convert(
                                               const Cont<In>& cont)
{
    Cont<typename convert_traits<In>::to_type> converted;
    for (Cont<In>::const_iterator it = cont.begin(); it != cont.end(); ++it)
        converted.push_back(scalar_convert(*it));
    return converted;
}

Whoa.

This looks bad, but if you dissect this function to its constituents it will all make sense. It’s a template function, and its first template parameter is the element type of the source container. The container type itself is called Cont, but it’s not a real type—it can be std::vector or std::list but not std::vector<int> or std::list<double>—it’s just the name of the template class without the template parameter. This Cont type has template parameters of its own: _X which is the element type and _Alloc which is the allocator, conveniently defaulting to the default STL allocator here.

This enables us to declare a new instance of this container, parameterized with the target type from the convert_traits structure, and then push the converted elements into it. (Obviously the previous approach where the output container is passed by reference has its advantages, e.g. it’s probably more efficient and enables multiple conversions into the same container.)