• Table of Contents
• Previous Chapter
• Next Chapter

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:

• Templates allow us to to integer arithmetic and to save computed values symbolically;
• Templates allow us to make compile-time decisions;
• Templates allow us to do things repeatedly

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 section 20.1.1 the use of the keyword typename is discussed. It is used to distinguish types defined by class templates from members defined by class templates;
• in section 20.1.2 applies typename to situations where types nested in templates are returned from member functions of class templates;
• in section 20.1.3 covers the problem of how to refer to base class templates from derived class templates;
• and section 20.1.4 covers some new syntax: ::template and variants, used to inform the compiler that a name used inside a template is itself a class template.

20.1.1: The keyword `typename'

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

        return t + *ptr;
    }

    demo.cc:4: error: 'ptr' was not declared in this scope

    Type::Ambiguous *ptr;

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

    template <typename Container>
    class Handler
    {
        Container::const_iterator d_it;

        public:
            Handler(Container const &container)
            :
                d_it(container.begin())
            {}
    };

• The typename Container represents any container supporting iterators.
• The container presumably supports a member begin(). The initialization d_it(container.begin()) clearly depends on the template's type parameter, so it's only checked for basic syntactic correctness.
• Likewise, the container presumably supports a subtype const_iterator, defined in the class Container.

    #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
    */

        Container::const_iterator d_it;

    template <typename Container>
    class Handler
    {
        typename Container::const_iterator d_it;
        ...
    };

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

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

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

            Nested nested() const
            {
                return Nested();
            }
    };

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

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

    #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();
    }

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

    #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

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>

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

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

    error: 'class Outer<T1>::Inner' is not a type

    void fun(Outer<T1>::template Inner<T2> &obj);

    error: expected type-name before '&' token

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

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

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

    1 / (sizeof(Target) <= sizeof(Source));

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

    error: enumerator value for 'the_Target_size_exceeds_the_Source_size'
        not integer constant

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

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

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

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

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
        ...

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

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

    template<typename FirstType, typename SecondType>
    struct IfElse<false, FirstType, SecondType>
    {
        typedef SecondType 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 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>());
    }

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

The principle to follow here is:

• Define a specialization implementing the end-condition;
• Define all other steps using recursion.
• Store intermediate values as enum values.

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)!

    template <int n>
    struct Factorial
    {
        enum { value = n * Factorial<n - 1>::value };
    };

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

    int main()
    {
        cout << "The number of permutations of 5 objects = " <<
                Factorial<5>::value << "\n";
    }

    int main()
    {
        cout << "The number of permutations of 5 objects = " <<
                120 << "\n";
    }

20.3: Template template parameters

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

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:

• No special allocation takes place, data is used `as is':

      template <typename Data>
      class PlainAlloc
      {
          template<typename IData>
          friend std::ostream &operator<<(std::ostream &out,
                                          PlainAlloc<IData> const &alloc);
          Data d_data;
  
          public:
              PlainAlloc()
              {}
              PlainAlloc(Data data)
              :
                  d_data(data)
              {}
              PlainAlloc(PlainAlloc<Data> const &other)
              :
                  d_data(other.d_data)
              {}
      };
  

• The seond allocation scheme uses the standard new operator to allocate a new copy of the data:

      template <typename Data>
      class NewAlloc
      {
          template<typename IData>
          friend std::ostream &operator<<(std::ostream &out,
                                          NewAlloc<IData> const &alloc);
          Data *d_data;
  
          public:
              NewAlloc()
              :
                  d_data(0)
              {}
              NewAlloc(Data const &data)
              :
                  d_data(new Data(data))
              {}
              NewAlloc(NewAlloc<Data> const &other)
              :
                  d_data(new Data(*other.d_data))
              {}
              ~NewAlloc()
              {
                  delete d_data;
              }
      };
  

• The third allocation scheme uses the placement new operator (see section 7.1.4), requesting memory from a common pool of bytes (the implementation of the member request(), obtaining the required amount of memory, is left as an exercise to the reader):

      template<typename Data>
      class PlacementAlloc
      {
          template<typename IData>
          friend std::ostream &operator<<(std::ostream &out,
                                          PlacementAlloc<IData> const &alloc);
          Data *d_data;
  
          static char s_commonPool[];
          static char *s_free;
  
          public:
              PlacementAlloc()
              :
                  d_data(0)
              {}
              PlacementAlloc(Data const &data)
              :
                  d_data(new(request()) Data(data))
              {}
              PlacementAlloc(PlacementAlloc<Data> const &other)
              :
                  d_data(new(request()) Data(*other.d_data))
              {}
              ~PlacementAlloc()
              {
                  d_data->~Data();
              }
          private:
              static char *request();
      };
  

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 ...

    Storage<string, NewAlloc<string> > storage;

20.3.2: Policy classes - II: template template parameters

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 keyword template starts the definition of a template template parameter;
• It is followed, between pointed brackets, a list of template parameters that must be specified for the template template parameter. These parameters may be given names, but these names cannot be used in the subsequent template definition, and are therefore usually omitted. On the other hand, providing formal names may help the reader of the template to understand the kinds of templates that may be specified as template template parameters.
• Template template parameters must match, in numbers and types (template type parameter, template non-type parameter, template template parameter) the template parameters that must be specified for the policy.
• Following the bracketed list the keyword class is provided. In this case, typename cannot be used.
• All parameter values may be provided with default values, as shown in the following example of a hypothetical class template:

      template
      <
          template
          <
              typename = std::string,
              int = 12,
              template
              <
                  typename = int
              >
              class Inner = std::vector
          >
          class Policy
      >
      class Demo
      {
          ...
      };
  

    template <typename Data, template <typename> class Policy>
    class Storage: public Policy<Data>

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

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

    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"));

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

20.3.2.1: The destructor of Policy classes

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

• Destruction of a derived class object using the base class's destructor requires the implementation of a virtual destructor;
• A virtual destructor introduces overhead to a class that normally has no data members, but merely defines behavior: suddenly a vtable is required as well as a data member: a pointer to the vtable;
• Virtual member functions somewhat reduce the efficiency of code; thus virtual member functions using dynamic polymorphism, somewhat counteract the static polymorphism offered by templates;
• Virtual member functions in templates may result in code bloat: once an instantiation of a class's member is required, the class's vtable and all its virtual members must be implemented too.

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

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

    template <typename Data>
    struct Size<Data, Plain>: public Plain<Data>
    {
        size_t size()
        {                           // relies on pointer data members
            return this->second - this->first;
        }
    };

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

20.4: Trait classes

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

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::*)());

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(...);

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

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

    template <typename ClassType>
    static Char2 fun(void (ClassType::*)());

    template <typename NonClassType>
    static char fun(...);

    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

    template <typename Return, typename Argument>
    Return chop(Argument const &arg)
    {
        return Return(arg);
    }

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

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

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

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

    cout << chopper<string>("hello world") << endl;

20.5.2: An empty type

    struct NullType
    {};

20.5.3: Type convertability

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();

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

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

• Both types are identical;
• Base is a public and unambiguous base class of Derived;
• and also, but usually not intended: if Base is void.

    #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 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> >

    TypeList<char,
        TypeList<short,
            TypeList<int, NullType> > >

#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

• If the typelist is empty, its size is zero
• If the typelist is non-empty, its size equals 1 plus the size of its tail.

    size_t c_length(char const *cp)
    {
        return *cp == 0 ? 0 : 1 + c_length(cp + 1);
    }

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:

• If the ListSize's type is empty (i.e., a NullType), its size is 0:

      template <>
      struct ListSize<NullType>
      {
          enum {  size = 0  };
      };
  

• Otherwise, its size will be 1 plus the size of the tail of a TypeList:

  template <typename Head, typename Tail>
  struct ListSize<TypeList<Head, Tail> >
  {
      enum {  size = 1 + ListSize<Tail>::size  };
  };
  

    std::cout << ListSize<TYPELIST_3(int, char, bool)>::size << "\n";

20.6.2: Searching a TypeList

• If the typelist is equal to NullType, define `index' as -1;
• If the typelist's head element equals the searchtype, define `index' as 0;
• Otherwise define `index' as follows:
  • If searching the searchtype in the typelist's tail results in a index -1, then searchtype is not an element of the typelist, and the (current) index will be set to -1 as well;
  • Otherwise, searchtype was found in the typelist's tail, and the current index will be set to 1 + the index obtained for searchtype on the typelist's tail.

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:

• If the typelist is empty, define `index' as -1:

      template <typename SearchType>
      struct ListSearch<SearchType, NullType>
      {
          enum { index = -1 };
      };
  

• If the typelist's head element equals the searchtype, define `index' as 0. Note how the test is performed by specifying SearchType twice:

      template <typename SearchType, typename Tail>
      struct ListSearch<SearchType, TypeList<SearchType, Tail> >
      {
          enum { index = 0 };
      };
  

• Otherwise define `index' as either -1 (searchtype wasn't found in the typelist's tail) or as 1 + the index obtained from searching the typelist's tail. Note that the implementation uses a private enum value tmp to store the index value obtained from searching the typelist's tail for searchtype:

      template <typename SearchType, typename Head, typename Tail>
      class ListSearch<SearchType, TypeList<Head, Tail> >
      {
          enum { tmp = ListSearch<SearchType, Tail>::index } ;
          public:
              enum { index = tmp == -1 ? -1 : 1 + tmp };
      };
  

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

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):

• The foundation of the algorithm is provided by a declaration of a struct TypeAt, expecting an index and a typelist:

      template <int index, typename Typelist>
      struct TypeAt;
  

• If the typelist equals NullType define the return type as NullType as well:

      template <int index>
      struct TypeAt<index, NullType>
      {
          typedef NullType Type;
      };
  

• If the search index equals 0, define the return type as the typelist's head:

      template <typename Head, typename Tail>
      struct TypeAt<0, TypeList<Head, Tail> >
      {
          typedef Head Type;
      };
  

• Otherwise, define the return type as the return type of the type at offset index - 1 in the typelist's tail. Note the typename following typedef: it is required as the defining type's result type is a nested type:

      template <int index, typename Head, typename Tail>
      struct TypeAt<index, TypeList<Head, Tail> >
      {
          typedef typename TypeAt<index - 1, Tail>::Type Type;
      };
  

    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

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

• The basic template is a struct expecting a typelist and a type to add to the typelist:

      template <typename TypeList, typename NewType>
      struct Append;
  

• Adding NullType:
  • If the type to add is NullType, and the original type is NullType, the result itself is the NullType:

        template <>
        struct Append<NullType, NullType>
        {
            typedef NullType TList;
        };
    

    Note that the simple alternative:

        template <typename TypeList>
        struct Append<TypeList, NullType>
        {
            typedef TypeList Result;
        };
    

    is not a good idea, as it will match all types that are offered as the template's first template type parameter. E.g., Append<int, NullType> would be accepted, but would certainly not result in a TypeList.
  • When attempting to append NullType to an existing TypeList, leave the TypeList as-is:

        template <typename Head, typename Tail>
        struct Append<TypeList<Head, Tail>, NullType>
        {
            typedef TypeList<Head, Tail>  TList;
        };
    

• Appending other types than NullType:
  • If the typelist itself is NullType, the final typelist consists of the typelist containing the new type:

        template <typename NewType>
        struct Append<NullType, NewType>
        {
            typedef TYPELIST_1(NewType) TList;
        };
    

  • Otherwise, the final typelist consists of the head of the initial typelist and the typelist resulting from appending the new type to the intial typelist's tail:

        template <typename Head, typename Tail, typename NewType>
        struct Append<TypeList<Head, Tail>, NewType>
        {
            typedef TypeList<Head, typename Append<Tail, NewType>::TList>
                    TList;
        };
    

    Once again: note that typename is required in front of Append (cf. section 20.1.1)

20.6.5: Erasing from a TypeList

• The basic template is a struct expecting a typelist and a type to erase from the typelist:

      template <typename TypeList, typename EraseType>
      struct Erase;
  

• If the typelist itself is NullType, there's nothing to erase, and NullType is the result:

      template <typename EraseType>
      struct Erase<NullType, EraseType>
      {
          typedef NullType Result;
      };
  

• If the typelist's head equals the type to erase, then the result is the typelist's tail:

      template <typename EraseType, typename Tail>
      struct Erase<TypeList<EraseType, Tail>, EraseType>
      {
          typedef Tail Result;
      };
  

• Otherwise, the result is the typelist's head and the result obtained afdter erasing the type to be erased from the typelist's tail:

      template <typename Head, typename Tail, typename EraseType>
      struct Erase<TypeList<Head, Tail>, EraseType>
      {
          typedef TypeList<Head,
                          typename Erase<Tail, EraseType>::Result> Result;
      };
  //
  
  //ERASEALL
      template <typename TypeList, typename EraseType>
      struct EraseAll: public Erase<TypeList, EraseType>
      {};
  

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.

• First step: note that all alternatives of Erase but one can be used unaltered by EraseAll. So, EraseAll inherits from Erase, using the generic struct's template parameters:

      template <typename TypeList, typename EraseType>
      struct EraseAll: public Erase<TypeList, EraseType>
      {};
  

  Thus, EraseAll is a mere copy of Erase, and it could be used as a synonym of Erase (of course, erasing only the first element).

• Second (and last) step: define a specialization of EraseAll for the case where the type to be removed equals the typelist's head:

      template <typename EraseType, typename Tail>
      struct EraseAll<TypeList<EraseType, Tail>, EraseType>
      {
          typedef typename EraseAll<Tail, EraseType>::Result Result;
      };
  

  Note the EraseAll action on the template's tail.

    #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

• First, the general EraseDuplicates struct is declared. It expects as its single template type a TypeList:

      template <typename TypeList>
      struct EraseDuplicates;
  

• If the typelist is actually a NullType, we're done. The result will remain to be a NullType:

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

• Next, an EraseDuplicates specialization is defined for a true Typelist:

      template <typename Head, typename Tail>
      struct EraseDuplicates<TypeList<Head, Tail> >
      ...
  

  This specialization implements the following reasoning:
  • If EraseDuplicates erases duplicates, then no duplicates will be encountered in the typelist's tail if EraseDuplicates is recursively processes the template's tail. When this recursive call is completed, a typelist is obtained (called, e.g., UniqueTail) not containing any type duplicates in the typelist's tail:

            typedef typename EraseDuplicates<Tail>::Result UniqueTail;
    

  • Of course, the above operation only processed the original typelist's tail. It may still contain duplicate's of the original template's head type. Since that latter type is already there (viz. at the original typelist's head) it can simply be removed from UniqueTail, producing the typelist NewTail:

            typedef typename Erase<UniqueTail, Head>::Result  NewTail;
    

  • Finally, the resulting typelist is the original typelist's head and NewTail:

            typedef TypeList<Head, NewTail>  Result;
    

    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

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:

• Creating classes from a typelist
  Here the aim is to construct a new class consisting of instantiations of an existing basic template for each of the types mentined in a provided typelist;
• Accessing data members from the thus constructed conglomerate class by index, rather than name;
• Tuples, defining structs from typelists, having index-accessible data members for each of the types specified in a typelist.

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

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.

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

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:

• It creates a class hierarchy, having unique Wrap template classes at its final nodes;
• It creates a typelist containing all Wrap base class types in the order in which they were constructed, to allow clients to obtain the Wrap template class wrapper matching a specific type in the provided typelist.

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

• Since the typelist's head is a plain type, it can immediately be used to define a TemplateClass type, which itself is wrapped in a Wrap template class wrapper using the unique index value that was passed to GenScatter.
• The Wrap template class wrapper is then defined as a virtual base class.
• A second hierarchal line starts at the typelist's tail, at the same time incrementing the index, thus ensuring that the next Wrap class will receive the next index value.
• At the end of the class definition the WrapList type is defined as the typelist consisting of the current Wrap wrapper as its head, and the base GenScatter class's WrapList as its tail.

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

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

    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;

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;

    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;

• Table of Contents
• Previous Chapter
• Next Chapter