Chapter 20: Advanced template applications

Don't hesitate to send in feedback: send an e-mail if you like the C++ Annotations; if you think that important material was omitted; if you find errors or typos in the text or the code examples; or if you just feel like e-mailing. Send your e-mail to Frank B. Brokken.

Please state the document version you're referring to, as found in the title (in this document: 7.2.0) and please state chapter and paragraph name or number you're referring to.

All received mail is processed conscientiously, and received suggestions for improvements will usually have been processed by the time a new version of the Annotations is released. Except for the incidental case I will normally not acknowledge the receipt of suggestions for improvements. Please don't interpret this as me not appreciating your efforts.

The main purpose of templates is to provide a generic definition of classes and functions which can then be tailored to specific types when required.

However, templates allow us to do more than that. If not for compiler implementation limitations, templates could be used to program, compile-time, just about anything we use computers for. This remarkable feat, offered by no other current day computer language, stems from the fact that templates allow us to do three things compile-time:

Of course, asking the compiler to compute, e.g., prime numbers, is one thing. It's a completely different thing to do so in an award winning way. Don't expect speed records to be broken when the compiler performs complex calculations for us. But that's al beside the point, which is that we can ask the compiler to compute virtually anything using C++'s template language.

In this chapter these remarkable features of templates are discussed. Following a short overview of subtleties related to templates the main characteristics of template meta programming are introduced.

Following that discussion a third type of template parameter, the template template parameter is introduced, laying the groundwork for the discusion of trait classes and policy classes.

This chapter ends with the discussion of several additional and interesting applications of templates: adapting compiler error messages, conversions to class types and an elaborate example discussing compile-time list processing.

Much of the inspiration for this chapter resulted from two highly recommended books: Andrei Alexandrescu's 2001 book Modern C++ design (Addison-Wesley) and Nicolai Josutis and David Vandevoorde's 2003 book Templates (Addison-Wesley)

20.1: Subtleties

In this section the following topics are covered:

20.1.1: The keyword `typename'

The keyword typename has been used until now to indicate a template type parameter. However, it is also used to disambiguate code inside templates. Consider the following code:
    template <typename Type>
    Type function(Type t)
    {
        Type::Ambiguous *ptr;

        return t + *ptr;
    }
When this code is shown to the compiler, it will complain with an -at first sight puzzling- error message like:
    demo.cc:4: error: 'ptr' was not declared in this scope
The puzzling nature of this error message is that the intention of the programmer was actually to declare a pointer to a type Ambiguous defined within the class template Type. However, the compiler, when confronted with Type::Ambiguous has to make a decision about the nature of this construct. Clearly it cannot inspect Type to find out its true nature, since Type is a template type, and hence its actual definition isn't available yet. The compiler now is confronted with two possibilities: either Type::Ambiguous is a static member of the as yet mysterious template Type, or it is a subtype defined by Type. As the standard specifies that the compiler must assume the former, the statement
    Type::Ambiguous *ptr;
is eventually interpreted as a multiplication of the static member Type::Ambiguous and the (now undeclared) entity ptr. The reason for the error message should now be clear: in this context ptr is unknown.

To disambiguate code in which an identifier refers to a type that is itself a subtype of a template type parameter the keyword typename must be used. Accordingly, the above code is altered into:

    template <typename Type>
    Type function(Type t)
    {
        typename Type::Ambiguous *ptr;

        return t + *ptr;
    }
Classes fairly often define subtypes. When such classes are thought of when designing templates, these subtypes may appear inside the template's definitions as subtypes of template type parameters, requiring the use of the template keyword. E.g., assume a class template Handler defines a typename Container as its type parameter, as well as a data member storing the container's begin() iterator. Furthermore, the class template Handler may offer a constructor accepting any container supporting a begin() member. The skeleton of the class Handler could then be:
    template <typename Container>
    class Handler
    {
        Container::const_iterator d_it;

        public:
            Handler(Container const &container)
            :
                d_it(container.begin())
            {}
    };
What were the considerations we had in mind when designing this class? The final consideration is an indication that typename is required. If this is omitted, and a Handler is instantiated because of the following main() function one again a peculiar compilation error is generated:
    #include "handler.h"
    #include <vector>
    using namespace std;

    int main()
    {
        vector<int> vi;
        Handler<vector<int> > ph(vi);
    }
    /*
        Reported error:

    handler.h:4: error: syntax error before `;' token
    */
Clearly the line
        Container::const_iterator d_it;
in the Handler class causes a problem: it is interpreted by the compiler as a static member instead of a subtype. Again, the problem is solved using typename:
    template <typename Container>
    class Handler
    {
        typename Container::const_iterator d_it;
        ...
    };
An interesting illustration that the compiler indeed assumes X::a to be a member a of the class X is provided by the error message we get when we try to compile main() using the following implementation of Handler's constructor:
    Handler(Container const &container)
    :
        d_it(container.begin())
    {
        size_t x = Container::ios_end;
    }
    /*
        Reported error:

        error: `ios_end' is not a member of type `std::vector<int,
                std::allocator<int> >'
    */

As a final illustration consider what happens if the function template introduced at the beginning of this section doesn't return a Type value, but a Type::Ambiguous value. Again, a subtype of a template type is referred to, and typename is required:

    template <typename Type>
    typename Type::Ambiguous function(Type t)
    {
        return t.ambiguous();
    }
Using typename in the specification of a return type is further discussed in section 20.1.2.

In some cases typename can be avoided by resorting to a typedef. E.g., Iterator, defined using typedef, can be used to indicate the specific type:

    template <typename Container>
    class Handler
    {
        typedef typename Container::const_iterator Iterator;

        Iterator d_it;
        ...
    };

20.1.2: Returning types nested under class templates

Consider the following example in which a nested class, that is not depending on a template parameter, is defined within a template class. Furthermore, the class template member nested() returns an object of the nested class. Note that a (deprecated) in-class member implementation is used. The reason for this will become clear shortly.
    template <typename T>
    class Outer
    {
        public:
            class Nested
            {};

            Nested nested() const
            {
                return Nested();
            }
    };
The above example compiles flawlessly: within the class Outer there is no ambiguity with respect to the meaning of nested()'s return type.

However, since it is advised to implement inline and template members below their class interface (see section 6.3.1), we now remove the implementation from the interface itself, and put it below the interface. Suddenly the compiler refuses to compile our member nested():

    template <typename T>
    class Outer
    {
        public:
            class Nested
            {};

            Nested nested() const;
    };

    template <typename T>
    Outer<T>::Nested Outer<T>::nested() const
    {
        return Nested();
    }
The above implementation of nested() produces an error message like

error: expected constructor, destructor, or type conversion before 'Outer'.

In cases like these the return type (i.e., Outer<T>::Nested) refers to a subtype of Outer<T> rather than to a member of Outer<T>.

As a general rule the following holds true: the keyword typename must be used whenever a type is referred to that is a subtype of a type that is itself depending on a template type parameter. Writing typename in front of Outer<T>::Nested removes the compilation error and therefore the correct implementation of the function nested() becomes:

    template <typename T>
    typename Outer<T>::Nested Outer<T>::nested() const
    {
        return Nested();
    }

20.1.3: Type resolution for base class members

Consider the following example of a template base and a derived class:
    #include <iostream>

    template <typename T>
    class Base
    {
        public:
            void member();
    };

    template <typename T>
    void Base<T>::member()
    {
        std::cout << "This is Base<T>::member()\n";
    }

    template <typename T>
    class Derived: public Base<T>
    {
        public:
            Derived();
    };

    template <typename T>
    Derived<T>::Derived()
    {
        member();
    }
This example won't compile, and the compiler tells us something like:
    error: there are no arguments to 'member' that depend on a template
           parameter, so a declaration of 'member' must be available

At first glance, this error may cause some confusion, since with non-class templates public and protected base class members are immediately available. This also holds true for class templates, but only if the compiler can figure out what we mean. In the above situation, the compiler can't, since it doesn't know for what type T the member function member must be initialized.

To appreciate why this is true, consider the situation where we have defined a specialization:

    template <>
    Base<int>::member()
    {
        std::cout << "This is the int-specialization\n";
    }
Since the compiler, when processing the class Derived, can't be sure that no specialization will be in effect once an instantiation of Derived is called for, it can't decide yet for what type to instantiate member, since member()'s call in Derived::Derived() doesn't require a template type parameter. In cases like these, where no template type parameter is available to determine which type to use, the compiler must be told that it should postpone its decision about the template type parameter to use for member() until instantiation time. This can be implemented in two ways: either by using this, or by explicitly mentioning the base class, instantiated for the derived class's template type(s). In the following main() function both forms are used. Note that with the int template type the int specialization is used.
    #include <iostream>

    template <typename T>
    class Base
    {
        public:
            void member();
    };

        template <typename T>
        void Base<T>::member()
        {
            std::cout << "This is Base<T>::member()\n";
        }

        template <>
        void Base<int>::member()
        {
            std::cout << "This is the int-specialization\n";
        }

    template <typename T>
    class Derived: public Base<T>
    {
        public:
            Derived();
    };

        template <typename T>
        Derived<T>::Derived()
        {
            this->member();         // Using `this' implies <T> at
                                    // instantiation time.
            Base<T>::member();      // Same.
        }

    int main()
    {
        Derived<double> d;
        Derived<int> i;
    }

    /*
        Generated output:
        This is Base<T>::member()
        This is Base<T>::member()
        This is the int-specialization
        This is the int-specialization
    */

20.1.4: ::template, .template and ->template

In general, the compiler is able to determine the true nature of a name. As discussed in the previous sections, this is not always the case and the software engineer sometimes has to advise the compiler. The typename keyword can often used to that purpose.

However, typename cannot always come to the rescue. While parsing a source, the compiler receives a series of tokens, representing meaningful units of text encountered in the program's source. A token represents, e.g., an identifier or a number. Other tokens represent operators, like =, + or <. It is precisely the last token that may cause problems, as it is used in multiple ways, which cannot always be determined from the context in which the compiler encounters <. Sometimes, however, the compiler will know that < does not represent the less than operator, as in the situation where a template parameter list follows the keyword template, e.g.,

    template <typename T, int N>
Clearly, in this case < does not represent a `less than' operator.

The special meaning of < if preceded by template forms the basis for the syntactic constructs discussed in this section.

Assume the following class has been defined:

    template <typename Type>
    class Outer
    {
        public:
            template <typename InType>
            class Inner
            {
                public:
                    template <typename X>
                    void nested();
            };
    };
Here a class template Outer defines a nested class template Inner, which in turn defines a template member function.

Next, a class template Usage is defined, offering a member function caller() expecting an object of the above Inner type. An initial setup for Usage could be written as follows:

    template <typename T1, typename T2>
    class Usage
    {
        public:
            void fun(Outer<T1>::Inner<T2> &obj);
        ...
    };
The compiler, however, won't accept this. It interprets Outer<T1>::Inner as a class type, which of course doesn't exist. In this situation the compiler generates an error like:
    error: 'class Outer<T1>::Inner' is not a type
To inform the compiler that in this case Inner itself is a template, using the template type parameter <T2>, the ::template construction is required. This tells the compiler that the next < should not be interpreted as a `less than' token, but rather as a template type argument. So, the declaration is modified to:
    void fun(Outer<T1>::template Inner<T2> &obj);
But this still doesn't get us where we want to be: after all Inner<T2> is a type, nested under a class template, depenting on a template type parameter. Actually, the compiler produces a series of error messages here, one of them being like:
    error: expected type-name before '&' token
which nicely indicates what should be done to get it right: add typename:
    void fun(typename Outer<T1>::template Inner<T2> &obj);

Next, fun() itself is not only just declared, it is implemented as well. The implementation should call Inner's member nested() function, instantiated for yet another type X. The class template Usage should now receive a third template type parameter, which can be called T3: let's assume it has been defined. To implement fun(), we start out with:

    void fun(typename Outer<T1>::template Inner<T2> &obj)
    {
        obj.nested<T3>();
    }
However, once again we run into a problem. The compiler once again interprets < as `less than', and expects a logical expression, having as its right-hand side a primary expression instead of a formal template type.

To tell the compiler in situations like these that <T3> should be interpreted as a type to instantiate nested with, the template keyword is used once more. This time it is used in the context of the member selection operator: by writing .template the compiler is informed that what follows is not a `less than' operator, but rather a type specification. The function's final implementation becomes:

    void fun(typename Outer<T1>::template Inner<T2> &obj)
    {
        obj.template nested<T3>();
    }

Instead of value or reference parameters functions may define pointer parameters. If obj would have been defined as a pointer parameter the implementation would use the ->template construction, rather than the .template construction. E.g.,

    void fun(typename Outer<T1>::template Inner<T2> *ptr)
    {
        ptr->template nested<T3>();
    }

20.2: Template Meta Programming

20.2.1: Values according to templates

In template programming values are preferably represented by enum values. Enums are preferred over, e.g., int const values since enums never have any linkage: they are pure symbolic values with no memory representation.

Consider the situation where a programmer must use a cast, say a reinterpret_cast. A problem with a reinterpret_cast is that it is the ultimate way to turn off all compiler checks. All bets are off, and we can write extreme but absolutely pointless reinterpret_cast statements, like

    int value = 12;
    ostream &ostr = reinterpret_cast<ostream &>(value);

Wouldn't it be nice if the compiler would warn us against such oddities by generating an error message? If that's what we'd like the compiler to do, there must be some way to distinguish madness from weirdness. Let's assume we agree on the following distinction: reinterpret casts are never acceptable if the target type represents a larger type than the expression (source) type, since that would immediately result in abusing the amount of memory that's actually available to the target type. In this way we can't allow reinterpet cast from int to double since a double is a larger type than an int.

The intent is now to create a new kind of cast, let's call it reinterpret_to_smaller_cast, which can only be performed if the target type is a smaller type than the source type (note that this exactly the opposite readoning as used by Alexandrescu (2001), section 2.1).

The following template is constructed:

    template<typename Target, typename Source>
    Target &reinterpret_to_smaller_cast(Source &source)
    {
        // determine whether Target is smaller than source
        return reinterpet_cast<Target &>(source);
    }
At the comment an enum-definition is inserted with a suggestive name, resulting in a compile-time error if the condition is not met. A division by zero is clearly not allowed, and noting that a false value represents a zero value, the condition could be:
    1 / (sizeof(Target) <= sizeof(Source));
The interesting part is that this condition doesn't result in any code at all: it's a mere value that's computed by the compiler while compiling the expression. To transform this into a useful error message the expression is assigned to a desciptive enum value, resulting in, e.g.,
    template<typename Target, typename Source>
    Target &reinterpret_to_smaller_cast(Source &source)
    {
        enum
        {
            the_Target_size_exceeds_the_Source_size =
                1 / (sizeof(Target) <= sizeof(Source))
        };
        return reinterpret_cast<Target &>(source);
    }
When reinterpret_to_smaller_cast is used to cast from int to ostream an error is produced by the compiler, like:
    error: enumerator value for 'the_Target_size_exceeds_the_Source_size'
        not integer constant
whereas no error is reported if, e.g., reinterpret_to_smaller_cast<int>(cout) is requested.

In the above example a enum was used to compute compile time a value that is illegal if an assumption is not met. The creative part is finding an appropriate expression.

Enum values are well suited for these situations as they do not consume any memory and their evaluation does not produce any executable code. They can be used to accumulate values too: the resulting enum value will then contain a final value, computed by the compiler rather than by code as the next sections illustrate. In general, programs shouldn't do run-time what they can do compile-time and computing complex calculations resulting in constant values is a clear example of this principle.

20.2.1.1: Converting integral types to types

Another use of values buried inside templates is to `templatize' simple scalar int values. This is primarily useful in situations where a scalar value (often a bool value) is available to select an appropriate member specialization, a situation that will be encountered shortly (section 20.2.2).

Templatizing integral values is based on the fact that a class template together with its template arguments represent a type. E.g., vector<int> and vector<double> are different types.

Templatizing integral values is simply implemented: just define a template, it does not have to have any contents at all, but it customarily has the integral values stored as an enum value:

    template <int x>
    struct IntType
    {
        enum { value = x };
    };
Since IntType does not have any members, but just the enum value, the `class' can be defined as a `struct', saving us from typing public:. Defining the enum value `value' allows us to retrieve the value used at the instantiation at no cost in memory: enum values are not variables or data members, and thus have no address. They are mere values.

Using the struct IntType is easy: just define an anonymous or named object by specifying a value for its int non-type parameter:

    int main()
    {
        IntType<1> it;
        cout << "IntType<1> objects have value: " << it.value << "\n" <<
                "IntType<2> objects are of a different type "
                        "and have values " << IntType<2>().value << endl;
    }

20.2.2: Selecting alternatives using templates

Being able to make choices is an essential feature of programming languages. If we want to be able to `program the compiler' this feature must be present in templates as well. Note again that being able to make choices in templates has nothing to do with run-time execution of programs. The essence of template meta programming is that we're not using or relying on any executable code in our template meta program. Of course, the result will usually be executable code, but the particular code that is produced must be a function of decisions the compiler can make by itself.

Since template (member) functions are only instantiated when they are actually used, we can even define specializations of functions which are mutually exclusive. I.e., it is possible to define a specialization which may be compilable in one situation, but not in another, and a second specialization which is compilable in the other situation, but not in the first situation. This way code can be tailored to the demands of a concrete situation.

A feature like this cannot be implemented in code. For example, when designing a generic storage class the software engineer may have the intention to store value class type objects as well as objects of polymorphic class types in the storage class. From this point of departure the engineer may conclude that the storage class should contain pointers to objects, rather than objects themselves, and the following code may be conceived of:

    template <typename Type>
    void Storage::add(Type const &obj)
    {
        d_data.push_back(
            d_ispolymorphic ?
                obj.clone()
            :
                new Type(obj)
        );
    }
The intent is to use the clone() member function of the Type class if Type is a polymorphic class and the standard copy constructor if Type is a value class.

Unfortunately, this scheme will normally fail to compile as value classes do not define clone() member functions and polymorphic base classes should define their copy constructor in the class's private section. It doesn't matter to the compiler that clone() is never called for value classes and the copy constructor is never called for value type classes: it has some code to compile, and can't do that because of missing members. It's as simple as that.

Template meta programming comes to the rescue. Knowing that template functions are only instantiated when used, we design specializations of our add() function, and provide our class Storage with an additional (in addition to Type itself) template non-type parameter indicating whether we'll use Storage for polymorphic or non-polymorphic classes:

    template <typename Type, bool isPolymorphic>
    class Storage
        ...
and we simply define overloaded versions of our add() member: one implementing the polymorphic class variant expecting true as its argument, and one implementing the value class variant accepting false as its argument.

Again we run into a problem: overloading members cannot be based on argument values, only on types. Fortunately there is a way out: in section 20.2.1.1 it was discussed how to convert integral values to types, and knowledge of how to do this now comes in handy. The strategy is to define two overloaded versions: one defining an IntType<true> parameter, implementing the polymorphic class and one defining an IntType<false> parameter, implementing the polymorphic class. In addition to these overloaded versions of the member function add() the member add() itself calls the appropriate overloaded member by providing an IntType argument, constructed from Storage's template non-type parameter. Here are the implementations:

Declared in Storage's private section:

    template <typename Type, bool isPolymorphic>
    void Storage<Type, isPolymorphic>::add(Type const &obj, IntType<true>)
    {
        d_data.push_back(obj.clone());
    }

    template <typename Type, bool isPolymorphic>
    void Storage<Type, isPolymorphic>::add(Type const &obj, IntType<false>)
    {
        d_data.push_back(new Type(obj));
    }
Declared in Storage's public section:
    template <typename Type, bool isPolymorphic>
    void Storage<Type, isPolymorphic>::add(Type const &obj)
    {
        add(obj, IntType<isPolymorphic>());
    }

In the above example making a selection was made possible by converting a primitive value to a type and then (since each concrete primitive value may be used to construct a different type) using these types to define overloaded versions of template member functions one of which is then called from a (public) member using IntType to construct the appropriate selector type.

Since template members are only instantiated when used, only one of the overloaded private add() members is instantiated. Since the other one is never called compilation errors are prevented.

Some software engineers may have second thoughts when thinking about the Storage class using pointers to store copies of value classes. Their argument could be that value class objects can be stored by value, rather than by pointer. In those cases we'd like to define the actual type used for storing the values as either value types or pointer types. Situations like these frequently occur in template meta programming and the following struct IfElse may be used to obtain one of two types, depending on a bool selector value. First define the general form of the template:

    template<bool selector, typename FirstType, typename SecondType>
    struct IfElse
    {
        typedef FirstType TypeToUse;
    };
Then define a specialization for the case where the selector value is false. Note that the specialized struct has three arguments, matching the template parameters of the above general form. The template<...> specification used with specializations merely define what remaining template parameters are present in the specialization:
    template<typename FirstType, typename SecondType>
    struct IfElse<false, FirstType, SecondType>
    {
        typedef SecondType TypeToUse;
    };
The IfElse struct uses in its second definition a partial specialization to select the FalseType if the selector is false. In all other cases (i.e., selector == true) the less specific generic case is instantiated by the compiler, defining FirstType as the TypeToUse.

The IfElse struct allows us to templatize structural types: our Storage class may use pointers to store copies of polymorphic class type objects, but values to store value class type objects.

    template <typename Type, bool isPolymorphic>
    class Storage
    {
        typedef typename IfElse<isPolymorphic, Type *, Type>::TypeToUse
                DataType;

        std::vector<DataType> d_data;

        private:
            void add(Type const &obj, IntType<true>);
            void add(Type const &obj, IntType<false>);
        public:
            void add(Type const &obj);
    }

    template <typename Type, bool isPolymorphic>
    void Storage<Type, isPolymorphic>::add(Type const &obj, IntType<true>)
    {
        d_data.push_back(obj.clone());
    }

    template <typename Type, bool isPolymorphic>
    void Storage<Type, isPolymorphic>::add(Type const &obj, IntType<false>)
    {
        d_data.push_back(obj);
    }

    template <typename Type, bool isPolymorphic>
    void Storage<Type, isPolymorphic>::add(Type const &obj)
    {
        add(obj, IntType<isPolymorphic>());
    }
The above example uses IfElse's TypeToUse, which is a type defined by IfElse as either FirstType or SecondType to define the actual data type to be used for Storage's std::vector data type. To prevent long data type definitions Storage defines its own type DataType.

The remarkable result in this example is that the structure of the Storage class's data is now depending on its template parameters. Since the isPolymorphic == true situation uses different data types than t(isPolymorphic == false) situation, the overloaded private add() members can utilize this difference immediately. E.g., add(Type const &obj, IntType<false>) now uses direct copy construction to stpre a copy of obj in d_vector.

It is also possible to select a type from more than two alternatives. In that case, IfElse structs can be nested. Remember that these structs never have any effect on the run-time program, which simply is confronted with the appropriate type, conditional to the type that's associated with the selector value. The following example, defining MapType as a map having plain types or pointers for either its key or its value type, illustrates this approach:

    template <typename Key, typename Value, int selector>
    class Storage
    {
        typedef typename IfElse<
                    selector == 1,              // if selector == 1:
                    map<Key, Value>,            // use map<Key, Value>

                    typename IfElse<
                        selector == 2,          // if selector == 2:
                        map<Key, Value *>,      // use map<Key, Value *>

                        typename IfElse<
                            selector == 3,      // if selector == 3:
                            map<Key *, Value>,  // use map<Key *, Value>
                                                // otherwise:
                            map<Key *, Value *> // use map<Key *, Value *>

                        >::TypeToUse
                    >::TypeToUse
                >::TypeToUse
                MapType;

        MapType d_map;

        public:
            void add(Key const &key, Value const &value);
        private:
            void add(Key const &key, Value const &value, IntType<1>);
            ...
    };
    template <typename Key, typename Value, int selector>
    inline void Storage<selector, Key, Value>::add(Key const &key,
                                                   Value const &value)
    {
        add(key, value, IntType<selector>());
    }
The principle used in the above examples is: if different data types are to be used in class templates, depending on template non-type parameters, an IfElse struct can be used to define the appropriate type, and overloaded member functions may utilize knowledge about the appropriate types to optimize their implementations.

Note that the overloaded functions have identical parameter lists as the matching public wrapper function, but add to this parameterlist a specific IntType type, allowing the compiler to select the appropriate overloaded version, based on the template's non-type selector parameter.

20.2.3: Templates: Iterations by Recursion

Since there are no variables in template meta programming, there is no way to implement iteration using templates. However, iterations can always be rewritten as recursions, and since recursions are supported by templates iterations can always be rewritten as (tail) recursions.

The principle to follow here is:

Since the compiler will select a more specialized implementation over a more generic one, by the time it reaches the final recursion it will stop the recursion since the specialization will not rely on recursion anymore.

Most readers will be familiar with the recursive implementation of the mathematical `factorial' operator, indicated by the exclamation mark (!). Factorial n (so: n!) returns the successive products n * (n - 1) * (n - 2) * ... * 1, representing the number of ways n objects can be permuted. Interestingly, the factorial operator is usually defined by a recursive definition:

    n! = (n == 0) ?
            1
        :
            n * (n - 1)!
To compute n! from a template, a template Factorial can be defined using a int n template non-type parameter, and defining a specialization for the case n == 0. The generic implementation uses recursion according to the factorial definition. Furthermore, the Factorial template defines an enum value `value' to contain the its factorial value. Here is the generic definition:
    template <int n>
    struct Factorial
    {
        enum { value = n * Factorial<n - 1>::value };
    };
Note how the expression assigning a value to `value' uses constant, compiler determinable values: n is provided, and Factorial<n - 1>() is computed by template meta programming, also resulting in a compiler determinable value. Also note the interpretation of Factorial<n - 1>::value: it is the value defined by the type Factorial<n - 1>; it's not, e.g., the value returned by an object of that type. There are no objects here, simply values defined by types.

To end the resrsion a specialization is required, which will be preferred by the compiler over the generic implementation when its template arguments are present. The specialization can be provided for the value 0:

    template <>
    struct Factorial<0>
    {
        enum { value = 1 };
    };
The Factorial template can be used to determine, compile time, the number of permutations of a fixed number of objects. E.g.,
    int main()
    {
        cout << "The number of permutations of 5 objects = " <<
                Factorial<5>::value << "\n";
    }
Once again, Factorial<5>::value is not evaluated run-time, but compile-time. The above statement is therefore run-time equivalent to:
    int main()
    {
        cout << "The number of permutations of 5 objects = " <<
                120 << "\n";
    }

20.3: Template template parameters

Consider the following situation: a software engineer is asked to design a storage class Storage which is able to store data, which may either make and store copies of the data or store the data as received, and which may either use a vector or a linked list as its underlying storage medium. How should the engineer tackle this request?

The engineer's first reaction could be to develop Storage as a class having two data members, one being a list, another being a vector, and to provide the constructor with maybe an enum value indicating whether the data itself or new copies should be stored using that enum value to set a series of pointers to member functions to activate the appropriate subset of its private member functions, providing public wrapper functions to hide the use of the pointers to members.

Complex, but doable, until the engineer is confronted with a modification of the original question: now the request states that it should also be possible to use -in the case of new copies- a custom-made allocation scheme, rather than the standard new operator, and it should also be possible to use yet another type of container, in addition to the vector and list that were already part of the design. E.g., a queue could be preferred or maybe even a stack.

It's clear that the approach suggesting to have all functionality provided by the class doesn't scale. The class Storage would soon become a monolithic giant which is hard to understand, maintain, test, and deploy.

One of the reasons why the big, all-encompassing class is hard to deploy and understand is that a well-designed class should enforce constraints: the design of the class should, by itself, disallow certain operations, violations of which should be detected by the compiler, rather than by a program, crashing or terminating with a fatal error.

Consider the above request. If the class offers both an interface to access the vector data storage and an interface to access the list data storage, then it's likely that the class will offer an overloaded operator[] member to access elements in the vector. This member, however, will be syntactically present, but semantically invalid when the list data storage is selected, which doesn't support operator[].

Sooner or later, users of the monolithic all-encompassing class Storage will fall into the trap of using operator[] even though they've selected the list as the underlying data storage. The compiler won't be able to detect the error, which will only appear once the program is running, leaving users rather than the engineer flabbergasted.

The question remains: how should the engineer proceed, when confronted with the above questions? It's time to introduce policies.

20.3.1: Policy classes - I

A policy defines (in some contexts: prescribes) a particular kind of behavior. In our context a policy class defines a certain part of the class interface, and it may define inner types, member functions and data members.

In the previous section a problem of how to create a class which might use a series of allocation schemes was introduced. These allocation schemes all depend on the actual data type to be used, and so the `template' reflex should kick in: the allocation schemes should probably be defined as template classes, applying the appropriate allocation procedures to the data type at hand. E.g. (using in-class implementations to save some space), the following three allocation classes could be defined:

The above three classes define policies that may be selected by the user of the class Storage, introduced in the previous section. In addition to this, additional allocation schemes could be implemented by the user as well.

In order to be able to apply the proper allocation scheme to the class Storage it should also be designed as a class template. The class will also need a template type parameter allowing users to specify the data type.

It would be possible to specify the data type with the specification of the allocation scheme, resulting in code like:

    template <typename Data, typename Scheme>
    class Storage ...
and then use Storage, e.g., as follows:
    Storage<string, NewAlloc<string> > storage;
However, this implementation is unnecessarily complex, as it requires the user to specify the data type twice. Instead, the allocation scheme should be specified using a third type of template parameter, not requiring the user to specify the data type with the allocation scheme to use. This third type of template parameter (in addition to the well-known template type parameter and template non-type parameter) is the template template parameter.

20.3.2: Policy classes - II: template template parameters

Template template parameters allow us to specify a class template as a template parameter. By specifying a class template, it is possible to add a certain kind of behavior, called policy to an existing class template.

Consider the class Storage, introduced at the beginning of this section, and consider the allocation classes discussed in the previous section. To specify an allocation policy the class Storage starts its definition as follows:

    template <typename Data, template <typename> class Policy>
    class Storage ...
The second template parameter is the template template parameter. It contains the following elements: Since the policy class should be an inherent part of the class under consideration, it is often deployed as a base class. So, Policy becomes a base class of Storage. Moreover, the policy should operate on the data type to be used with the class Storage. Therefore the policy is handed that data type as well. From this we obtain the following setup:
    template <typename Data, template <typename> class Policy>
    class Storage: public Policy<Data>
This scheme allows us to use the policy's members when implementing the members of the class Storage.

Now the allocation classes do not really offer many useful members: apart from the extraction operator, no immediate access to the data is offered. This can easily be repaired by providing some additional members. E.g., the class NewAlloc could be extended with the following operators, allowing access to and modification of stored data:

        operator Data &()   // optionally add a `const' member too
        {
            return *d_data;
        }
        NewAlloc &operator=(Data const &data)
        {
            *d_data = data;
        }
Other allocation classes can be provided with comparable members.

The next step is to use the allocation schemes in some real code. The following example shows how a storage can be constructed for a data type to be specified and an allocation scheme to be specified. First, define a class Storage:

    template <typename Data, template <typename> class Policy>
    class Storage: public std::vector<Policy<Data> >
    {
    };
That's all there is. All required functionality is offered by the vector base class, while the policy is `factored into the equation' via the template template parameter. Here's an example of its use:
    Storage<std::string, NewAlloc> storage;

    copy(istream_iterator<std::string>(cin), istream_iterator<std::string>(),
            back_inserter(storage));

    cout << "Element index 1 is " << storage[1] << endl;
    storage[1] = "hello";

    copy(storage.begin(), storage.end(),
         ostream_iterator<NewAlloc<std::string> >(cout, "\n"));
Following the construction of a Storage object, the STL copy() function can be used in combination with the back_inserter iterator to add some data to storage. Its elements can be both accessed and modified directly using the index operator, and then NewAlloc<std::string> objects are inserted into cout, again using the STL copy() algorithm.

Interestingly, this is not the end of the story. After all, the intention was to create a class allowing us to specify the storage type as well. What if we don't want to use a vector, but instead would like to use a list?

It's easy to change Storage's setup so that a completely different storage type can be used on request, say a list or a deque. To implement this, the storage class is parameterized as well, again using a template template parameter, that could be given a default value too, as shown in the following redefinition of Storage:

    template <typename Data, template <typename> class Policy,
                             template <typename> class Container =
                                                        std::vector>
    class Storage: public Container< Policy<Data> >
    {
    };
The earlier example in which a Storage object was used can be used again, without any modifications, for the above redefinition. It clearly can't be used with a list container, as the list lacks operator[]. But that's immediately recognized by the compiler, producing an error if an attempt is made to use operator[] on, e.g., a list (A complete example showing the definition of the allocation classes and the class Storage as well as its use is provided in the Annotation's distribution in the file yo/advancedtemplates/examples/storage.cc.).

20.3.2.1: The destructor of Policy classes

In the previous section policy classes are used as base classes of template classes resulting in the interesting observation that a policy class actually serves as a base class of a derived class Since a policy class may act as a base class, it is thinkable that a pointer or reference to a policy class is used to point or refer to the derived class using the policy.

This situation, although legal, should be avoided for various reasons:

To avoid these drawbacks, it is good practice to prevent using references or pointers to policy classes to refer or point to derived class objects. This is accomplished by providing policy classes with nonvirtual protected destructors. Since the destructor is non-virtual there is no implementation penalty in reduced efficiency or memory overhead, and since it is protected users cannot refer to classes derived from the policy class using a pointer or reference to the policy class.

20.3.3: Structure by Policy

Policy classes usually define behavior, not structure. I.e., policy classes are used to parameterize some aspect of the behavior of classes that are derived from them. However, different policies may imply the use of different data members. Thus a policy class may be used to define both behavior and structure.

By providing a well-defined interface a class derived from a policy class may define member specializations using the different structures of policy classes to their advantage. For example, a plain pointer-based policy class could offer its functionality by resorting to C-style pointer juggling, whereas a vector-based policy class could use the vector's members directly.

In this situation a generic class template Size could be designed expecting a container-like policy using features commonly found in containers, defining the data (and hence the structore) of the container specified in the policy. E.g.:

    template <typename Data, template <typename> class Container>
    struct Size: public Container<Data>
    {
        size_t size()
        {                           // relies on the container's `size()'
                                    // note: can't use `this->size()'
            return Container<Data>::size();
        }
    };
Next, a specialization can be defined to accomodate the specifics of a much simpler storage class using, e.g., plain pointers (the implementation capitalizes on first and second, data members of std::pair. Cf. the example at the end of this section):
    template <typename Data>
    struct Size<Data, Plain>: public Plain<Data>
    {
        size_t size()
        {                           // relies on pointer data members
            return this->second - this->first;
        }
    };
Depending on the intentions of the template's author other members could be implemented as well.

To use the above templates for real, a generic wrapper class can now be constructed: depending on the actual storage type that is used (e.g., a std::vector or some plain storage class) it will use the matching Size template to define its structure:

    template <typename Data, template <typename> class Store>
    class Wrapper: public Size<Data, Store>
    {};

The above classes could now be used as follows (en passant showing an extremely basic Plain class):

    #include <iostream>
    #include <vector>

    template <typename Data>
    struct Plain: public std::pair<Data *, Data *>
    {};

    int main()
    {
        Wrapper<int, std::vector> wiv;
        std::cout << wiv.size() << "\n";

        Wrapper<int, Plain> wis;
        std::cout << wis.size() << "\n";
    }
The wiv object now defines vector-data, the wis object merely defines a std::pair object's data members.

20.4: Trait classes

Scattered over the std namespace trait classes are found. E.g., most C++ programmers will have seen the compiler mentioning `std::char_traits<char>' when performing an illegal operation on std::string objects, as in std::string s(1).

Trait classes are used to make compile-time decisions about types. Traits classes allow the software engineer to apply the proper code to the proper data type, be it a pointer, a reference, or a plain value, all maybe in combination with const. Moreover, the specification of the particular type of data to be used does not have to be made by the template writer, but can be inferred from the actual type that is specified (or implied) when the template is used.

Trait classes allow the software engineer to develop a template <typename Type1, typename Type2, ...> without the need to specify many specializations covering all combinations of, e.g., values, (const) pointers, or (const) references, which would soon result in an unmaintainable exponential explosion of template specializations (e.g., allowing these five different actual types for each template parameter already results in 25 combinations when two template type parameters are used: each must be covered by potentially different specializations).

Having available a trait class, the actual type can be inferred compile time, allowing the compiler to deduct whether or not the actual type is a pointer, a pointer to a member, a const pointer, and make comparable deductions in case the actual type is, e.g., a reference type. This in turn allows us to write templates that define types like argument_type, first_argument_type, second_argument_type and result_type, which are required by several generic algorithms (e.g., count_if()).

A trait class usually performs no behavior. I.e., it has no constructor and no members that can be called. Instead, it defines a series of types and enum values that have certain values depending on the actual type that is passed to the trait class template. The compiler uses one of a set of available specializations to select the one appropriate for an actual template type parameter.

The generic point of departure when defining a trait template is a plain vanilla struct, defining the characteristics of a plain value type, e.g., an int. This sets the stage for specific specializations, modifying the characteristics for any other type that could be specified for the template.

To make matters concrete, assume the intent is to create a trait class BasicTraits telling us whether a type is a plain value type, a pointer type, or a reference type (all of which may or may not be const types).

Moreover, whatever the actual type that's provided, we want to be able to determine the `plain' type (i.e., the type without any modifiers, pointers or references), the `pointer type' and the `reference type', allowing us to define in all cases, e.g., a reference to its basic type, even though we passed a const pointer to that type.

Our point of departure, as mentioned, is a plain struct defining the required parameter. E.g., something like:

        template <typename T>
        struct Basic
        {
            typedef T Type;
            enum
            {
                isValue = true,
                isPointer = false,
                isConst = false
            };
        };

However, often decisions about types can be made using constant logical expressions. Note that the above definition does not contain a `isReference' enumeration value. Such a value is not required as it is implied by the expression not isPointer and not isValue.

Although some conclusions can be drawn by combining various enum values, it is good practice to provide a full implementation of trait classes, not requiring its users to construct these logical expressions themselves. Therefore, the basic decisions in a trait class are usually made by a nested trait class, leaving the task of creating appropriate logical expressions to a surrounding trait class.

So, the struct Basic defines the generic form of our inner trait class. Specializations handle specific details. E.g., a pointer type is recognized by the following specialization:

        template <typename T>
        struct Basic<T *>
        {
            typedef T Type;
            enum
            {
                isValue = false,
                isPointer = true,
                isConst = false
            };
        };

whereas a pointer to a const type is matched with the next specialization:

        template <typename T>
        struct Basic<T const *>
        {
            typedef T Type;
            enum
            {
                isValue = false,
                isPointer = true,
                isConst = true
            };
        };

Several other specializations should be defined: e.g., recognizing const value types or reference types. Eventually all these specializations wind up being nested structs of an outer class BasicTraits, offering the public traits class interface. The outline of the outer trait class is:

    template <typename TypeParam>
    class BasicTraits
    {
        // Define specializations of the template `Base' here

        public:
            typedef typename Basic<TypeParam>::Type ValueType;
            typedef ValueType *PtrType;
            typedef ValueType &RefType;

            enum
            {
                isValueType = Basic<TypeParam>::isValue,
                isPointerType = Basic<TypeParam>::isPointer,
                isReferenceType = not Basic<TypeParam>::isPointer and
                                  not Basic<TypeParam>::isValue,
                isConst = Basic<TypeParam>::isConst
            };
    };

A trait class template can be used to obtain the proper type, irrespective of the template type argument provided, or it can be used to select the proper specialization, depending on, e.g., the const-ness of a template type. The following statements serve as an illustration:

    cout << BasicTraits<int>::isPointerType << " " <<
            BasicTraits<int *>::isPointerType << " " <<
            BasicTraits<int>::isConst << " " <<
            BasicTraits<int>::isReferenceType << " " <<
            BasicTraits<int &>::isReferenceType << " " <<
            BasicTraits<int const>::isConst << " " <<
            BasicTraits<int const *>::isPointerType << " " <<
            BasicTraits<int const *>::isConst << " " <<
            endl;

    BasicTraits<int *>::ValueType value = 12;
    int *otherValue = &value;
    cout << *otherValue << endl;

20.4.1: Distinguishing class from non-class types

In the previous section the TypeTrait trait class was developed. Using specialized versions of a nested struct Type modifiers, pointers, references and values could be distinguished.

Knowing whether a type is a class type or not (e.g., the type represents a primitive type) could also be a useful bit of knowledge to a template developer. E.g, the class template developer might define a specialization for a member knowing the template's type parameter is a class type (maybe using some member function that should be available) and another specialization for non-class types.

This section addresses the question how a trait class can distinguish class types from non-class types.

In order to distinguish classes from non-class types a distinguishing feature that can be used compile-time must be found. It may take some thinking to find such a distinguishing characteristic, but a good candidate eventually is found in the pointer to member syntactic construct, which is available only for classes. Using the pointer to member construct as the distinguishing characteristic, we now look for a construction which uses the pointer to member if available, and does something else if the pointer to member construction is not available.

Note again the rule of thumb that works so well for template meta programming: define a generic situation, and then specialize for the situations you're interested in. It's not a trivial task to apply this rule of thumb here: how can we distinguish a pointer to a member from `a generic situation', not being a pointer to a member? Fortunately, such a distinction is possible: a function template can be provided with a parameter which is a pointer to a member function (defining the `specialization' case), and another function template can be defined so that it accepts any argument. The compiler will then select the latter function in all situations but those in which the provided type is actually a class type, and thus a type which may support a pointer to a member.

Note that the compiler will not call the functions: we're talking compile-time here, and all the compiler does is to select the appropriate function, in order to be able to evaluate a constant expression (defining the value of, e.g, the enum value isClass).

So, our function template will be something like:

    template <typename ClassType>
    static (returntype)   fun(void (ClassType::*)());
Note that in this function `(returntype)' is not yet specified. It will be shortly.

The question about what the return type should be will be answered shortly. Arbitrarily the function's parameter defines a pointer to a member returning void. Note that there's no need for such a function to exist for the concrete class-type that's specified with the traits class, since all the compiler will do is select this function if a class-type was provided to the trait class in which fun() will be nested. In line with this: fun() is only declared, not defined. Furthermore note that fun() is declared as a static member of the trait class, so that there's no need for an actual object when fun() is called.

So far for the class-types. What about the non-class types? For those types a (generic) alternative must be found, one the compiler will select when the actual type is not a class type. Again, the language offers a `worst case' solution in the ellipsis parameter list. The ellipsis is a final resort the compiler may turn to if everything else fails. It's not only used to define (the in C++ deprecated) functions having a variable number of arguments, but it's also used to define the catch-all exception catch clause. Therefore, the `generic case' can be defined as follows:

    template <typename NonClassType>
    static (returntype)   fun(...);
Note that it would be an error to define the generic alternative as a function expecting an int. The compiler, when confronted with alternatives, will favor the simplest, most specified alternative over a more complex, generic one. So, when providing fun() with an argument it will select int when possible, given the nature of the used argument.

The question now becomes: what argument can be used for both a pointer to a member and the generic situation? Actually, there is such a `one size fits all' argument: 0. The value 0 can be used as argument value to initialize not only primitive types, but also to initialize pointers and pointers to members. Therefore, fun will be called as fun<Type>(0), with Type being the template type parameter of the trait class. Here, Type must be specified since the compiler will not be able to determine fun's template type parameter when fun(...) is selected.

Now for the return type: the return type cannot be a simple value (like true or false). When using a simple value the isClass enum value cannot be defined, since

    enum { isClass = fun<Type>(0) } ;
needs to be evaluated to obtain fun's return value, which is clearly not possible as enum values must be determined compile-time.

To allow a compile-time definition of isClass's value the solution must be sought in an expression that discriminates between fun<Type>(...) and fun<Type>(void (Type::*)()). In situations like these sizeof is our tool of choice. The sizeof operator is evaluated compile-time, and so by defining return types that differ in their sizes it is possible to discriminate compile-time among the two fun() alternatives.

The char type is by definition a type having size 1. By defining another type containing two consecutive char values a bigger type is obtained. Now char [2] is not a type, but char[2] can be defined as a data member of a struct which will thus have a size exceeding 1. E.g.,

    struct Char2
    {
        char data[2];
    };
Char2 can be defined as a nested type within our traits class, and the two fun declarations become:
    template <typename ClassType>
    static Char2 fun(void (ClassType::*)());

    template <typename NonClassType>
    static char fun(...);
This, in turn enables us to specify an expression that can be evaluated compile time, allowing the compiler to determine isClass's value:
    enum { isClass = sizeof(fun<Type>(0)) == sizoof(Char2) };

Note, however, that no fun() function template ever makes it to the instantiation stage, but the compiler nonetheless is able to infer what fun's return type will be, given a concrete template type argument. This inference is then used by the compiler to determine the truth of an expression, in turn enabling the compiler to compute the required compile-time constant value isClass, allowing us to determine whether a certain type is or is not a class type. Marvelous!

20.5: More conversions to class types

20.5.1: Types to types

Although class templates may be partially specialized, function templates may not. At times that can be annoying. Assume a function template is available implementing a certain unary operator that could be used with the transform (cf. section 17.4.63) generic algorithm:
    template <typename Return, typename Argument>
    Return chop(Argument const &arg)
    {
        return Return(arg);
    }
Furthermore assume that if Return is std::string then the specified implementation should not be used. Rather, with std::string a second argument 1 should always be provided (e.g., if Argument is a C++ string, a std::string is returned holding a copy of the function's argument, except for the argument's first character, which is chopped off).

Since chop() is a function, it is not possible to use a partial specialization. So it is not possible to specialize for std::string as attempted in the following erroneous implementation:

    template <typename Argument>
    std::string chop<std::string, Argument>(Argument const &arg)
    {
        return string(arg, 1);
    }
it is possible to use overloading, though. Instead of using partial specializations overloaded function templates could be designed:
    template <typename Return, typename Argument>
    Return chop(Argument const &arg, Argument )
    {
        return Return(arg);
    }

    template <typename Argument>
    std::string chop(Argument const &arg, std::string )
    {
        return string(arg, 1);
    }
This way it is possible to distinguish the two cases, but at the expense of a more complex function call (e.g., maybe requiring the use of the bind2nd() binder (cf. section 17.1.4) to bind the second argument to a fixed value) as well as the need to provide a (possibly expensive to construct) dummy argument to allow the compiler to choose among the two overloaded function templates.

Alternatively, overloaded versions could use the IntType template (cf. section 20.2.1.1) to select the proper overloaded version. E.g., IntType<0> could be defined as the type of the second argument of the first overloaded chop() function, and IntType<1> could be used for the second overloaded function. From the point of vieuw of program efficiency this is an attractive option, as the provided IntType objects are extremely lightweight: they contain no data at all. But there's also an obvious disadvantage: there is no intuitively clear association between on the one hand the int value used and on the other hand the intended type.

In situations like these it is more attractive to use another lightweight solution. Instead of using an arbitrary int-to-type association, an intuitively clear and automatic type-to-type association is used. The struct TypeType is a lightweight type wrapper, much like IntType is a lightweight wrapper around an int. Here is its definition:

    template <typename T>
    struct TypeType
    {
        typedef T Type;
    };
This too is a lightweight type as it doesn't have any data fields either. TypeType allows us to use a natural type association for chop()'s second argument. E.g, the overloaded functions can now be defined as follows:
    template <typename Return, typename Argument>
    Return chop(Argument const &arg, TypeType<Argument> )
    {
        return Return(arg);
    }

    template <typename Argument>
    std::string chop(Argument const &arg, TypeType<std::string> )
    {
        return std::string(arg, 1);
    }

Using the above implementations any type can be specified for Result. If it happens to be a std::string the correct overloaded version is automatically selected. E.g.,

    template <typename Result>
    Result chopper(char const *txt)
    {
        return chop(std::string(txt), TypeType<Result>());
    }
Using chopper(), the following statement will produce the text `ello world':
    cout << chopper<string>("hello world") << endl;

20.5.2: An empty type

At times (cf. section 20.6) an empty struct is a useful little tool. It can be used as a type acting analogously to the ASCII-Z (final 0-byte) in C-strings or as a 0-pointer to indicate the end of a linked list. Its definition is simply:
    struct NullType
    {};

20.5.3: Type convertability

In what situations can a type T be used as a `stand in' for another type U? Since C++ is a strongly typed language the answer is surprisingly simple: Ts can be used instead of Us if a T is accepted as argument in cases where Us are requested.

This reasoning is behind the following class which can be used to determine whether a type T can be used where a type U is expected. The interesting part, however, is that no code is actually generated or executed: all decisions can be made by the compiler.

In the second part of this section it will be shown how the code developed in the first part can be used to detect whether a class B is a base class of another clas D. The code developed here closely follows the example provided by Alexandrescu (2001, p. 35).

First, a function is conceived of that will accept a type U to which an alternative type T will be compared. This function returns a value of the as yet unsepcified type Convertible:

    Convertible test(U const &);

The function test() is not implemented; it is merely declared. The idea is that if a type T can be used instead of a type U it can be passed as argument to the above test() function.

If T cannot be used where a U is expected, then the above function will not be used by the compiler. Of course, getting a compiler error is not the kind of `answer' we're looking for and so the next question is what alternative we can offer to the compiler in cases where a T cannot be used as argument to the above function.

C (and C++) offer a very general parameter list, a parameter list that will always be considered acceptable. This parameter list consists of the ellipsis which actually is the worst situation the compiler may encounter: if everything else fails, then the function defining an ellipsis as its parameter list is selected. Normally that's not a productive and type-safe alternative, but in the current situation it is exactly what is needed. When confronted with two alternative function calls, one of which defines the ellipsis parameter list, the compiler will only select the function defining the ellipsis if the alternative(s) can't be used. So we declare an alternative function test(), having the ellipsis as its parameter list, and returning another type, e.g., NotConvertible:

    NotConvertible test(...);

Now, if code passes a value of type T to the test function, the return type will be Convertible if T can be converted to U, and NotConvertible if conversion is not possible.

Two problems still need to be solved: how do we obtain a T argument? The problems here are firstly, that it might not be possible to define a T, as a type T might hide all its constructors and secondly, how can the two return values be distinguished?

Although it might be impossoble to construct a T object, it is fortunately not necessary to construct a T. After all, the intent is to decide compile time whether a type is convertible to another type and not actually to construct such a T value. So another function is declared:

    T makeT();
This mysterious function has the magical power of enticing the compiler into thinking that a T object will come out of it. So, what will happen when the compiler is shown the following code:
    test(makeT())

If T can be converted to U the first function Convertible test(U const &) will be selected by the compiler; otherwise the function NotConvertible test(...) will be selected.

If it is now possible to distinguish Convertible from NotConvertible compile-time then it is possible to determine whether T is convertible to U.

Since Convertible and NotConvertible are values, their sizes are known. If these sizes differ, then the sizeof operator can be used to distinguish the two types; hence it is possible to determine which test() function was selected and hence it is known whether T can be converted to U or not. E.g., if the following expression evaluates as true T is convertible to U:

    sizeof(test(makeT())) == sizeof(Convertible);

The size of a char is well known. By definition it is 1. Using a typedef Convertible can be defined as a synonym of char, thus having size 1. Now NotConvertible must be defined so that it has a different type. E.g.,

    struct NotConvertible
    {
        char array[2];
    };
Note there that a simple typedef char NotConvertible[2] does not work: functions cannot return arrays, but they can return arrays embedded in a structs.

The above can be wrapped up in a template class, having two template type parameters:

    template <typename T, typename U>
    class Conversion
    {
        typedef char Convertible;
        struct NotConvertible
        {
            char array[2];
        };

        static T makeT();
        static Convertible test(U const &);
        static NotConvertible test(...);

        public:
            enum { exists = sizeof(test(makeT())) == sizeof(Convertible) };
            enum { sameType = 0 };
    };

    template <typename T>
    class Conversion<T, T>
    {
        public:
            enum { exists = 1 };
            enum { sameType = 1 };
    };

The above class never results in any run-time execution of code. When used, it merely defines the values 1 or 0 for its exist enum value, depending whether the conversion exists or not. The following example writes 1 0 1 0 when run from a main() function:

    cout <<
        Conversion<ofstream, ostream>::exists << " " <<
        Conversion<ostream, ofstream>::exists << " " <<
        Conversion<int, double>::exists << " " <<
        Conversion<int, string>::exists << " " <<
        endl;

20.5.3.1: Determining inheritance

Now that Conversion has be defined it's easy to determine whether a type Base is a (public) base class of a type Derived. To determine inheritance convertability of (const) pointers is examined. Derived const * can be converted to Base const * if: Preventing the latter, inheritance is determined by inspecting Conversion<Derived const *, Base const *>::exists:
    #define BASE_1st_DERIVED_2nd(Base, Derived) \ 
        (Conversion<Derived const *, Base const *>::exists && \ 
         not Conversion<Base const *, void const *>::sameType)

If code should not consider a class to be its own base class, then the following stricted test is possible, which adds a test for type-equality:

    #define BASE_1st_DERIVED_2nd_STRICT(Base, Derived) \ 
        (BASE_1st_DERIVED_2nd(Base, Derived) && \ 
         not Conversion<Base const *, Derived const *>::sameType)

The following example writes 1: 0, 2: 1, 3: 0, 4: 1, 5: 0 when run from a main() function:

    cout << "\n" <<
        "1: " << BASE_1st_DERIVED_2nd(ofstream, ostream) << ",  " <<
        "2: " << BASE_1st_DERIVED_2nd(ostream, ofstream) << ",  " <<
        "3: " << BASE_1st_DERIVED_2nd(void, ofstream) << ",  " <<
        "4: " << BASE_1st_DERIVED_2nd(ostream, ostream) << ",  " <<
        "5: " << BASE_1st_DERIVED_2nd_STRICT(ostream, ostream) << " " <<
        endl;

20.6: Template TypeList processing

This section serves two purposes. On the one hand it illustrates capabilities of the various meta-programming capabilities of templates, which can be used as a source for inspiration when developing your own templates. On the other hand, it culminates in a concrete example, showing some of the power template meta-programming has.

This section itself was inspired by Andrei Alexandrescu's (2001) book Modern C++ design, and much of this section's structure borrows from Andrei's coverage of typelists.

A typelist is a very simple struct: like a std::pair it consists of two elements, although in this case the typelist does not contain data members, but type definitions. It is defined as follows:

    template <typename First,  typename Second>
    struct TypeList
    {
        typedef First Head;
        typedef Second Tail;
    };

The typelist allows us to store any number of types using a recursive definition. E.g., the three types char, short, int may be stored as follows:

    TypeList<char, Typelist<short, int> >
Although this is a possible representation, usually NullType (cf. section 20.5.2) is used as the final type, acting comparably to a 0-pointer. Using NullType the above three types are represented as follows:
    TypeList<char,
        TypeList<short,
            TypeList<int, NullType> > >
This way to represent lists of types may be accepted by the compiler, but usually not as easily by programmers, who frequently have a hard time putting in the right number of parentheses. Alexandrescu suggest to ease the burden by defining a series of macros, even though macros are generally deprecated in C++. The TYPELIST macros suggested by Alexandrescu allow us to define typelists for varying numbers of types, and they are easily expanded if accommodating larger numbers of types is necessary. Here are the definitions of the first five TYPELIST macros:
#define TYPELIST_1(T1)              TypeList<T1, NullType >
#define TYPELIST_2(T1, T2)          TypeList<T1, TYPELIST_1(T2) >
#define TYPELIST_3(T1, T2, T3)      TypeList<T1, TYPELIST_2(T2, T3) >
#define TYPELIST_4(T1, T2, T3, T4)  TypeList<T1, TYPELIST_3(T2, T3, T4) >
#define TYPELIST_5(T1, T2, T3, T4, T5)  TypeList<T1, TYPELIST_4(T2, T3, T4, T5) >

Note the recursive nature of these macro definitions: recursion is how template meta programs perform iteration and in the upcoming sections implementations heavily depend on recursion. With all solutions to the problems covered by the coming sections a verbal discussion is provided explaining the philosophies that underlie the recursive implementations.

Of course, even here macros are ugly. The macro processor will be confused if a type is somewhat complex, like Wrap<HEAD, idx>. Fortunately situations like these can be prevented using a simple typedef. E.g., typenef Wrap<HEAD, idx> HEADWRAP and then using HEADWRAP instead of the full type definition.

20.6.1: The length of a TypeList

To obtain the length of a typelist the following algorithm can be used: Note how recursion is used to define the length of a typelist. In `normal' C++ code this recursion could be implemented as well, e.g., to determine the length of a plain C (ascii-Z) string, resulting in something like:
    size_t c_length(char const *cp)
    {
        return *cp == 0 ? 0 : 1 + c_length(cp + 1);
    }
In the context of template meta programming the alternatives that are used to execute or terminate recursion are never written in one implementation, but instead specializations are used: each specialization implements an alternative.

The length of a typelist will be determined by a struct ListSize ordinarily expecting a typelist as its template type parameter. It's merely declared, since it turns out that only its specializations are required:

template <typename TypeList>
struct ListSize;

Following the above algorithm specializations are now constructed:

That's all. The size of any typelist can now easily be determined. E.g., assuming all required headers (templates, iostream) have been included then the following statement will (of course) display the value 3:
    std::cout << ListSize<TYPELIST_3(int, char, bool)>::size << "\n";

20.6.2: Searching a TypeList

To determine whether a type (called the searchtype below) is present in a given typelist, an algorithm is used that will either define `index' -1 (if the searchtype is not an element of the typelist ) or it will define `index' as the index of the first occurrence of the searchtype in the typelist. The following algorithm is used:

The implementation again sets out with the declaration of a struct: ListSearch expects two template type parameters: searchtype's type and a typelist:

    template <typename SearchType, typename TypeList>
    struct ListSearch;

Next, specializations are defined implementing the above alternatives:

Assuming all required headers have been included, the following example shows how ListSearch can be used:

    int main()
    {
        std::cout << ListSearch<char, TYPELIST_2(int, char)>::index << "\n";
    }

20.6.3: Selecting from a TypeList

Next the selection of a type from a typelist given its index will be discussed. This is the inverse operation from obtaining the index of a `searchtype', as covered by section 20.6.2.

Rather than defining an enum value, the current algorithm should define a type equal to the type at a given index position. If the type does not exist, the typedef can be made a synonym of NullType since NullType cannot appear in a typelist.

The following algorithm is used (the implementation of the parts is provided immediately following the descriptions of the algorithm's steps):

Assuming all required headers have been included, the following example shows how ListSearch can be used:
    int main()
    {
        typedef TYPELIST_3(int, char, bool) list3;
        enum { test = 2 };

        std::cout <<
            (ListSearch<TypeAt<test, list3>::result, list3>::index == -1 ?
                "Illegal Index\n"
            :
                "Index represents a valid type\n");
    }

20.6.4: Appending to a TypeList

The question of how to add an element to a typelist is handled using the same rule of thumb as used for answering the previous questions: design a recursive algorithm and implement the recursion through specializations.

To append a new type to a typelist, the following algorithm can be used:

20.6.5: Erasing from a TypeList

The opposite from adding, erasing can simply be accomplished as well. Here is the algorithm, erasing the first occurrence of a type to erase from a typelist:

But there's more: what if the intention is to erase all elements from the typelist? In that case also apply Erase to the tail when the type to erase matches the typelist's head. E.g., a struct EraseAll can be defined similarly to Erase, except for the case where the typelist's head matches the type to be removed: in that case EraseAll must also be applied to the typelist's tail, as there may be additional types to be removed in the tail as well.

Since EraseAll closely resembles Erase, let's see how we can use class derivation in combination with specializations to our benefit.

The above two EraseAll definitions are all it takes to create a template that will do the job of erasing all occurrences of a type from a typelist, borrowing most of its code from the already existing Erase template. The effect of EraseAll vs. Erase can be seen when defining either Erase or EraseAll in the following example:
    #include <iostream>
    #include "erase.h"
    #include "listsize.h"

        // change Erase to EraseAll to erase all `int' types below
    #define ERASE Erase

    int main()
    {
        std::cout <<
            ListSize<
                ERASE<TYPELIST_3(int, double, int), int>::Result
            >::size << "\n";
    }

20.6.5.1: Erasing duplicates

So, erasing a type from a typelist can be accomplished. To remove duplicates all `head' elements must be erased from a typelist's tail. To accomplish this, the following algorithm is used, defining the EraseDuplicates template:

Here's the full definition of EraseDuplicates, not exposing UniequeTail and NewTail for cosmetic reasons:
    template <typename TypeList>
    struct EraseDuplicates;

    template <>
    struct EraseDuplicates<NullType>
    {
        typedef NullType  Result;
    };

    template <typename Head, typename Tail>
    class EraseDuplicates<TypeList<Head, Tail> >
    {
        typedef typename EraseDuplicates<Tail>::Result UniqueTail;
        typedef typename Erase<UniqueTail, Head>::Result  NewTail;

        public:
            typedef TypeList<Head, NewTail>  Result;
    };

20.7: Using a TypeList

In the previous sections the definition and some of the features of typelists have been discussed. Most C++ programmers consider typelists both exciting and an intellectual chalenge, honing their skills in the area of recursive programming.

Fortunately, there's more to typelist than a mere intellectual challenge. In this section of the chapter on Advanced Template Applications the following topics will be covered:

Again, much (and more) of the materials covered below is found in Alexandrescu's (2001) book. Hopefully the current section is an tasty appetizer for the main courses offered by Andrei Alexandrescu.

20.7.1: The Wrap and GenScat templates

In this section the template class GenScat will be developed. The purpose of GenScat is to create a new class using on the one hand a basic building block of the class that's finally constructed and on the other hand a series of types that will be fed to the building block.

The building block itself is provided as a template template parameter, and the final class will inherit from all building blocks instantiated for each of the types specified in a provided typelist. However, there is a flaw in this plan.

If the typelist contains two types, say int and double and the building block class is std::vector, then the final GenScat class will inherit from vector<int> and vector<double>. There's nothing wrong with that. But what if the typelist contains two int type specifications? In that case the GenScat class will inherit from two vector<int> classes, and, e.g., vector<int>::size() will cause an ambiguity which is hard to solve. Alexandrescu (2001) in this regard writes (p.67):

There is one major source of annoyance...: you cannot use it when you have duplicate types in your typelist.
.... There is no easy way to solve the ambiguity, [as the eventually derived class/FBB] ends up inheriting [the same base class/FBB] twice.
It is true that the same base class is inherited multiple times when the typelist contains duplicate types, but there is a way around this problem. If instead of inheriting from the plain base classes these base classes would themselves be wrapped in unique classes, then these unique classes can be used to access the base classes by implication: since they are mere wrappers they inherit the functionality of the `true' base classes.

Thus, the problem is shifted from type duplication to finding unique wrappers. Of course, that problem has been solved in principle in section 20.2.1.1, where wrappers around plain int values were introduced. A comparable wrapper can be designed in the context of class derivation. E.g.,

    template <typename Base, int idx>
    struct Wrap: public Base
    {
        Wrap(Base const &base)
        :
            Base(base)
        {}
        Wrap()
        {}
    };

Using Wrap two vector<int> classes can be distinguished easily: Wrap<1, vector<int> > could be used to refer to one of the vectors, Wrap<2, vector<int> > could refer to the other vector. By ensuring that the index values never collide all wrapper types will be unique.

Uniqueness of the Wrap values is implemented by the GenScat class: it is itself a wrapper around the class GenScatter, that will do all the work. GenScat merely seeds GenScatter with an initial value:

    template <typename Type, template <typename> class TemplateClass>
    class GenScat: public GenScatter<Type, TemplateClass, 0>
    {};

20.7.2: The GenScatter template

The interesting part of the exercise is of course the class template GenScatter. In its intended form (which actually turns out to be a specialization) GenScatter takes a typelist, a template class and a index value that is used to ensure uniqueness of the Wrap types.

With these ingredients, GenScatter creates a (fairly complex) class, that itself is normally derived from several GenScatter base classes. Each GenScatter class is eventually derived from a base class which is a Wrap class around the template class instantiated for each of the types in the provided typelist.

This complex arrangement itself causes yet another problem: it would be nice if the top-level derived class could be initialized by base class initializers. However, with normal class derivation indirect base classes cannot be initialized using base class initializers. This is a severe problem: if indirect base classes cannot be initialized by a GenScat class or by a class derived from GenScat, the types in the provided typelist cannot be refence types, as references must be initialized at construction time.

However, an indirect base class can be initialized by a top level derived class if it is a virtual base class (cf. section 14.4.2). The consequence of a virtual base class is that any duplicates of a virtual base class, following different paths in a class hierarchy will be merged into one class.

In the GenScat hierarchy the Wrap template class wrappers are the final (usable) base classes of the hierarchy. By defining these Wrap base classes as virtual base classes they can be initialized by GenScat (or by a class that itself is derived from GenScat), while merging of the Wrap base classes is prevented due to the fact that all Wrap base classes are unique.

It's time for some code. The GenScatter class performs the following tasks:

An illustration showing the layout of the final GenScatter class hierarchy and its subclasses is provided in figure 20.

Figure 20 is shown here.
Figure 20: Layout of a GenScatter class hierarchy


The core definition of GenScatter expects a typelist, a template class and an index:

    template <
        typename Head, typename Tail,
        template <typename> class TemplateClass, int idx
    >
    class GenScatter<TypeList<Head, Tail>, TemplateClass, idx>
    :
        virtual public Wrap<TemplateClass<Head>, idx>,
        public GenScatter<Tail, TemplateClass, idx + 1>
    {
        typedef typename GenScatter<Tail, TemplateClass, idx + 1>::WrapList
                BaseWrapList;
        public:
            typedef TypeList<Wrap<TemplateClass<Head>, idx>, BaseWrapList>
                    WrapList;
    };

GenScatter's main template definition expects a simple type as its first template parameter. Since this is a plain type, the class can immediately define a virtual Wrap template class wrapper as its base class, and it can immediately define the WrapList type as a typelist containing the class's base class:

    template <typename Type, template <typename> class TemplateClass, int idx>
    class GenScatter
    :
        virtual public Wrap<TemplateClass<Type>, idx>
    {
        typedef Wrap<TemplateClass<Type>, idx> Base;

        public:
            typedef TYPELIST_1(Base)    WrapList;
    };

Finally, a specialization to handle the ending NullType is required: it merely defines an empty WrapList:

    template <template <typename> class TemplateClass, int idx>
    class GenScatter<NullType, TemplateClass, idx>
    {
        public:
            typedef NullType WrapList;
    };

Both the Wrap template class wrapper and the GenScatter class can normally be defined in the anonymous namespace, as they are only used at file-scope, by themselves, by GenScatter and by the occasional additional support functions and classes.

20.7.3: Support struct and function

Since the GenScatter class returns a typelist containing all Wrap base classes matching the types in the order in which they appeared in GenScat's typelist, it is attractive to be able to obtain these Wrap base class types by their index numbers. Being able to reach these types by their indices allows, e.g., base class intializations as well as quick access to their respective members.

The class template BaseClass was designed with these thoughts in mind. It uses AtIndex (cf. section 20.6.3) to obtain a particular Wrap base class and returns the latter type as its Type type definition:

template <int idx, typename Derived>
struct BaseClass
{
    typedef typename TypeAt<idx, typename Derived::WrapList>::Type Type;
};

Once a GenScatter object is available, the following function template can be used to obtain a cast-less reference to any of its Wrap policy classes, given its index. Since the index can be matched one-to-one with the GenScatter's typelist, clients should have no problem finding the appropriate index values for a particular problem at hand:

template <int idx, typename Derived>
struct BaseClass
{
    typedef typename TypeAt<idx, typename Derived::WrapList>::Type Type;
};

20.7.4: Using GenScatter

The class template GenScat can be used by itself, to define a simple struct containg various data members. The foundation of such a conglomerate struct could be the following struct Field:
    template <typename Type>
    struct Field
    {
        Type field;

        Field(Type v = Type())
        :
            field(v)
        {}
    };

Such an instant struct could be useful in various situations; due to the nature of the struct Field, all data types would by default be initialized to their natural defaults. E.g., GenScat can be used directly as follows:

    GenScat<TYPELIST_2(int, int), Field> gs;

    base<1>(gs).d_value = 12;
    cout << base<0>(gs).d_value << " " << base<1>(gs).d_value << endl;
The above code, when it is run from main() will write the values 0 and 12, showing that default initialization and assignment to the individual fields is simply implemented.

Useful as this may be, sometimes more refined initializations may be necessary. E.g, an application needs a struct having two int data fields and a reference to a std::string. Since the struct contains a reference field, an initialization is required at construction time. In this case a struct can be derived from GenScat, while providing a constructor for the derived class performing the necessary intiializations. For situations like these, the BaseClass support struct (section 20.7.3) comes in quite handy. Here is the struct MyStruct, derived from the appropriate GenScat template, including its field-initializations:

    struct MyStruct: public
                        GenScat<TYPELIST_3(int, std::string &, int), Field>
    {
        MyStruct(int i, std::string &text, int i2)
        :
            BaseClass<0, MyStruct>::Type(i),
            BaseClass<1, MyStruct>::Type(text),
            BaseClass<2, MyStruct>::Type(i2)
         {}
    };

Note how each of the types in the provided typelist has its order-number mapped to the index used with the BaseClass invocations. Also, since MyStruct is also an object of its base class (GenScat), it can be specified as the Derived argument of BaseClass. Furthermore, from the types specified in the typelist the types of acceptable arguments of the Types to be initialized can be derived. E.g., the string text is passed as argument to Type when initializing the second field.

The following example shows how MyStruct can be used:

    string text("hello");
    MyStruct myStruct(12345, text, 12);

    cout << base<0>(myStruct).field << " " <<
            base<1>(myStruct).field << " " <<
            base<2>(myStruct).field << endl;

    base<0>(myStruct).field = 123;
    base<1>(myStruct).field = "new text";

    cout << base<0>(myStruct).field << "\n" <<
            "`text' now contains: " << text << endl;
When these lines of code are placed in a main() function, and the program is run the following output is produced showing proper initialization, reassignment and reassignment of the refered to string text via the appropriate MyStruct field:
    12345 hello 12
    123
    `text' now contains: new text

As a final example consider the struct Vectors:

struct Vectors: public GenScat<TYPELIST_3(int, std::string, int), std::vector>
{
    Vectors()
    :
        BaseClass<0, Vectors>::Type(std::vector<int>(1)),
        BaseClass<1, Vectors>::Type(std::vector<std::string>(2)),
        BaseClass<2, Vectors>::Type(std::vector<int>(3))
     {}
};

The struct Vectors uses std::vector as its template template parameter, and Vectors objects will thus offer three std::vectors: the first containing ints, the second strings, and the third again ints. Due to the nature of the Wrap template class wrapper, the three std::vector base classes of Vectors must be initialized by std::vector objects, and the constructor simply provides three vectors of varying sizes. Alternatively, the constructor could be furnished with three vector references or three size_t values to allow a more flexible initialization.

A Vectors object could be used as follows, showing that the base support function (cf. section 20.7.3) provides easy access to the vector base class of choice:

    Vectors vects;

    cout << base<0>(vects).size() << " " << base<1>(vects).size() << " " <<
            base<2>(vects).size() << endl;
Running this code fragment produces the output `1 2 3', as expected.