• Table of Contents
• Previous Chapter
• Next Chapter

Chapter 23: Advanced Template Use

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: 10.3.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 are usually 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 that may then be tailored to specific types.

But templates allow us to do more than that. If not for compiler implementation limitations, templates could be used to program, at 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 at compile-time:

• Templates allow us to do 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. But 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 all beside the point. In the end we can ask the compiler to compute virtually anything using C++'s template language, including prime numbers....

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.

In addition to template type and template non-type parameters there is a third kind of template parameter, the template template parameter. This kind of template parameter is introduced next, 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 came 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).

23.1: Subtleties

• In section 23.1.1 we apply typename to situations where types nested in templates are returned from member functions of class templates;
• in section 23.1.2 we cover the problem of how to refer to base class templates from derived class templates.

23.1.1: Returning types nested under class templates

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

However, following good practices inline and template members should be implemented below their class interfaces (see section 7.9.1). So we remove the implementation from the interface and put it below the interface:

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

Here typename must once again be used. The general rule being: the keyword typename must be used whenever a type is referred to that is a subtype of a type that itself depends on a template type parameter. When using the inline implementation no such dependency is used as the function's return type is simply Nested. When implementing the function outside of the class interface (which should be considered `good practice') then a specification of the class defining Nested must be provided for the function's return type. So it becomes Outer<T>::Nested which clearly is a type depending on a template type parameter.

Like before, writing typename in front of Outer<T>::Nested removes the compilation error. Thus, the correct implementation of the function nested becomes:

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

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

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

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

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 (and therefore about the particular (here: member) function to call) until instantiation time.

This may 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). When this is used the compiler is informed that we're referring to the type T for which the template was instantiated. Any confusion about which member function to use (the derived class or base class member) is resolved in favor of the derived class member. Alternatively, the base or derived class can explicitly be mentioned (using Base<T> or Derived<T>) as shown in the next example. Note that with the int template type the int specialization is used.

    #include <iostream>

    template <typename T>
    class Base
    {
        public:
            virtual 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();
            virtual void member();
    };
    template <typename T>
    void Derived<T>::member()
    {
        std::cout << "This is Derived<T>::member()\n";
    }
    template <typename T>
    Derived<T>::Derived()
    {
        this->member();         // Using `this' implies using the
                                // type for which T was instantiated
        Derived<T>::member();   // Same: calls the Derived member
        Base<T>::member();      // Same: calls the Base member
        std::cout << "Derived<T>::Derived() completed\n";
    }

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

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

The above example also illustrates the use of virtual member templates (although virtual member templates aren't often used). In the example Base declares a virtual void member and Derived defines its overriding function member. In that case this->member() in Derived::Derived calls, due to member's virtual nature, Derived::member. The statement Base<T>::member(), however, always calls Base's member function and can be used to bypass dynamic polymorphism.

23.1.3: ::template, .template and ->template

But 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 could represent, 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 may have very different meanings. The correct meaning cannot always be determined from the context in which the compiler encounters <. In some situations the compiler does know that < does not represent the less than operator, as when a template parameter list follows the keyword template, e.g.,

    template <typename T, int N>

The special meaning of < when it is 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 looks like this:

    template <typename T1, typename T2>
    class Usage
    {
        public:
            void caller(Outer<T1>::Inner<T2> &obj);
       ...
    };

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

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

    error: expected type-name before '&' token

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

Of course, caller itself is not only just declared, it must also be implemented. Assume that its implementation should call Inner's member nested, instantiated for yet another type X. The class template Usage should therefore receive a third template type parameter, called T3. Assume it has been defined. To implement caller, we write:

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

To tell the compiler that is should interpret <T3> as a type to instantiate, the template keyword must once again be used. This time it is used in the context of the member selection operator. We write .template to inform the compiler that what follows is not a `less than' operator, but rather a type specification. The function's final implementation becomes:

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

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

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

23.2: Template Meta Programming

23.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 intVar = 12;
    ostream &ostr = reinterpret_cast<ostream &>(intVar);

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 exceeding the amount of memory that's actually available to the target type. For this reason it's clearly silly to reinterpret_cast<double *>(&intVar), but reinterpret_cast<char *>(&intVar) could be defensible.

The intent is now to create a new kind of cast, let's call it reinterpret_to_smaller_cast. It should only be allowed to perform a reinterpret_to_smaller_cast if the target type occupies less memory than the source type (note that this exactly the opposite reasoning as used by Alexandrescu (2001), section 2.1).

To start, we construct the following template:

    template<typename Target, typename Source>
    Target &reinterpret_to_smaller_cast(Source &source)
    {
        // determine whether Target is smaller than source
        return reinterpret_cast<Target &>(source);
    }

At the comment an enum-definition is inserted defining a symbol having a suggestive name. A compile-time error results if the required condition is not met and the error message displays the name of the symbol. 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));

    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'
        is not an integer constant

In the above example an enum was used to compute (at 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 then contains a final value, computed by the compiler rather than by executable code as the next sections illustrate. In general, programs shouldn't do run-time what they can do at compile-time and performing complex calculations resulting in constant values is a clear example of this principle.

23.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 defines a type. E.g., vector<int> and vector<double> are different types.

Turning integral values into templates is easily done. Define a template (it does not have to have any contents at all) and store the integral value in an enum:

    template <int x>
    struct IntType
    {
        enum { value = x };
    };

Defining the enum value `value' allows us to retrieve the value used at the instantiation at no cost in storage. Enum values are neither variables nor data members and thus have no address. They are mere values.

It's easy to use the struct IntType. An anonymous or named object can be defined by specifying a value for its int non-type parameter. Example:

    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 << '\n';
    }

    int main()
    {
        cout << "IntType<100>, no object, defines `value': " <<
                IntType<100>::value << "\n";
    }

23.2.2: Selecting alternatives using templates

Like templates storing values templates making choices do not require any code to be executed at run-time. The selection is purely made by the compiler, at compile-time. The essence of template meta programming is that we are not using or relying on any executable code. The result of a template meta program often is executable code, but that code is a function of decisions merely made by the compiler.

Template (member) functions are only instantiated when they are actually used. Consequently we can define specializations of functions that are mutually exclusive. Thus it is possible to define a specialization that can be compiled in situation one, but not in situation two and to define another specialization that can be compiled in situation two, but not in situation one. Using specializations code can be generated that is tailored to the demands of a particular situation.

A feature like this cannot be implemented in run-time executable code. For example, when designing a generic storage class the software engineer may intend to store value class type objects as well as objects of polymorphic class types in the final storage class. Thus the software engineer may conclude that the storage class should contain pointers to objects, rather than the objects themselves. The initial implementation attempt could look like this:

    template <typename Type>
    void Storage::add(Type const &obj)
    {
        d_data.push_back(
            d_ispolymorphic ?
                obj.clone()
            :
                new Type(obj)
        );
    }

Unfortunately, this scheme usually fails as value classes do not define clone member functions and polymorphic base classes should delete their copy constructors (cf. section 7.6). It doesn't matter to the compiler that clone is never called for value classes and that the copy constructor is only available in value classes and not in polymorphic classes. It merely has some code to compile, and can't do that because of missing members. It's as simple as that.

23.2.2.1: Defining overloading members

    template <typename Type, bool isPolymorphic>
    class Storage

Unfortunately we run into a small problem: functions cannot be overloaded by their argument values but only by their argument types. But the small problem may be solved. Realizing that types are defined by the combination of template names and their template arguments we may convert the values true and false into types using the knowledge from section 23.2.1.1 about how to convert integral values to types.

We'll provide one (private) add member with a IntType<true> parameter (implementing the polymorphic class) and another (private) add member with a IntType<false> parameter (implementing the non-polymorphic class).

In addition to these two private members a third (public) member add is defined calling the appropriate private add member by providing an IntType argument, constructed from Storage's template non-type parameter.

Here are the implementations of the three add members:

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

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

23.2.2.2: Class structure as a function of template parameters

Such distinctions 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 generic form of the template:

    template<bool selector, typename FirstType, typename SecondType>
    struct IfElse
    {
        typedef FirstType type;
    };

    template<typename FirstType, typename SecondType>
    struct IfElse<false, FirstType, SecondType>
    {
        typedef SecondType type;
    };

The IfElse template allows us to define class templates whose data organization is conditional to the template's parameters. Using IfElse the Storage class may define pointers to store copies of polymorphic class type objects and values to store value class type objects:

    template <typename Type, bool isPolymorphic>
    class Storage
    {
        typedef typename IfElse<isPolymorphic, Type *, Type>::type
                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 data organization of the Storage class now depends on its template arguments. Since the isPolymorphic == true situation uses different data types than the isPolymorphic == false situation, the overloaded private add members can utilize this difference immediately. E.g., add(Type const &obj, IntType<false>) uses direct copy construction to store a copy of obj in d_vector.

It is also possible to make a selection from multiple types as IfElse structs can be nested. Realize that using IfElse never has any effect on the size or execution time of the final executable program. The final program simply contains the appropriate type, conditional to the type that's eventually selected.

23.2.2.3: An illustrative example

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

                        >::type
                    >::type
                >::type
                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 private add functions define the same parameters as the public add wrapper function, but add a specific IntType type, allowing the compiler to select the appropriate overloaded version based on the template's non-type selector parameter.

23.2.3: Templates: Iterations by Recursion

To implement iterations by (tail) recursion do as follows:

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

Most readers are probably familiar with the recursive implementation of the mathematical `factorial' operator, commonly represented 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 itself 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 };
    };

The recursion ends in a specialization. The compiler selects the specialization (provided for the terminating value 0) instead of the generic implementation whenever possible. Here is the specialization's implementation:

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

23.3: User-defined literals

    template <char ...Chars>
    Type operator "" _identifier()

Its argument must be an int constant, as is also expected by the literal operator defining an unsigned long long int parameter. All the characters of the int constant are passed as individual char non-type template arguments to the literal operator.

For example, if _NM2km is a literal operator function template, it can be called as 80_NM2km. The function template is then actually called as _NM2km<'8', '0'>(). If this function template merely uses template meta programming techniques and only processes integral data then its actions can be performed completely at compile-time. To illustrate this, let's assume NM2km only processes and returns unsigned values.

The function template _NM2km can forward its argument to a class template, defining an enum constant value, and that performs the required computations. Here is the implementation of the variadic literal operator function template _NM2km:

    template <char ... Chars>
    size_t constexpr operator "" _NM2km()
    {
        return static_cast<size_t>(             // forward Chars to NM2km
                NM2km<0, Chars ...>::value * 1.852);
    }

    template <size_t acc, char c, char  ...Chars>
    struct NM2km
    {
        enum
        {
            value = NM2km<10 * acc + c - '0', Chars ...>::value
        };
    };

    template <size_t acc, char c>   // empty parameter pack
    struct NM2km<acc, c>
    {
        enum
        {
            value = 10 * acc + c - '0'
        };
    };

This works fine, but of course not in cases where binary, octal, or hexadecimal values must also be interpreted. In that case we must first determine whether the first character(s) indicate a special number system. This can be determined by the class template NM2kmBase, that is now called from the _NM2km literal operator:

    template <char ... Chars>
    size_t constexpr operator "" _NM2km()
    {
        return static_cast<size_t>(         // forward Chars to NM2kmBase
                NM2kmBase<Chars ...>::value * 1.852);
    }

    template <char ...Chars>
    struct NM2kmBase
    {
        enum
        {
            value = NM2km<10, 0, Chars ...>::value
        };
    };

    template <char ...Chars>
    struct NM2kmBase<'0', Chars ...>        // "0..."
    {
        enum
        {                                   // octal value: base 8
            value = NM2km<8, 0, Chars ...>::value
        };
    };

    template <char ...Chars>
    struct NM2kmBase<'0', 'b', Chars ...>   // "0b..."
    {
        enum
        {                                   // binary value: base 2
            value = NM2km<2, 0, Chars ...>::value
        };
    };

    template <char  ...Chars>
    struct NM2kmBase<'0', 'x', Chars ...>   // "0x..."
    {
        enum
        {                                   // hex value: base 16
            value = NM2km<16, 0, Chars ...>::value
        };
    };

NM2km is implemented as before, albeit that it can now handle various number systems. The conversion from character to numeric value is left to a small support function template, cVal:

    template <char c>
    int constexpr cVal()
    {
        return '0' <= c <= '9' ? c - '0' : 10 + c - 'a';
    }

    template <size_t base, size_t acc, char c, char  ...Chars>
    struct NM2km
    {
        enum
        {
            value = NM2km<base, base * acc + cVal<c>(),
                                        Chars ...>::value
        };
    };

    template <size_t base, size_t acc, char c>
    struct NM2km<base, acc, c>
    {
        enum { value = base * acc + cVal<c>() };
    };

23.4: Template template parameters

The engineer's first reaction could be to develop an all-in Storage class. It could have two data members, a list and a vector, and its constructor could be provided with maybe an enum value indicating whether the data itself or new copies should be stored. The enum value can be used to initialize a series of pointers to member functions performing the requested tasks (e.g., using a vector to store the data or a list to store copies).

Complex, but doable. Then the engineer is asked to modify the class: in the case of new copies a custom-made allocation scheme should be used rather than the standard new operator. He's also asked to allow the use of yet another type of container, in addition to the vector and the list that were already part of the design. Maybe a deque would be preferred or maybe even a stack.

It's clear that the approach aiming at implementing all functionality and all possible combinations in one class doesn't scale. The class Storage soon becomes 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 that might terminate in a fatal error.

Think about 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 offers 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 only appears once the program is running, confusing its users.

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

23.4.1: Policy classes - I

In the previous section the problem of creating a class that might use any of a series of allocation schemes was introduced. These allocation schemes all depend on the actual data type to use, and so the `template reflex' should kick in.

Allocation schemes should probably be defined as template classes, applying the appropriate allocation procedures to the data type at hand. When such allocation schemes are used by the familiar STL containers (like std::vector, std::stack, etc.), then such home-made allocation schemes should probably be derived from std::allocator, to provide for the requirements made by these containers. The class template std::allocator is declared by the <memory> header file and the three allocation schemes developed here were all derived from std::allocator.

Using in-class implementations for brevity the following allocation classes could be defined:

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

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

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

  template <typename Data>
  class NewAlloc: public std::allocator<Data>
  {
      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 9.1.5), requesting memory from a common pool (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: public std::allocator<Data>
  {
      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();
  };
  

To apply the proper allocation scheme to the class Storage, Storage should be designed as a class template itself. The class also needs a template type parameter allowing users to specify the data type.

The data type to be used by a particular allocation scheme could of course be specified when specifying the allocation scheme to use. The class Storage would then have two template type parameters, one for the data type, one for the allocation scheme:

    template <typename Data, typename Scheme>
    class Storage ...

To use the class Storage we would then write, e.g.:

    Storage<string, NewAlloc<string>> storage;

Starting with the C++14 standard using the keyword class in the syntactical form of template template parameters (template <parameter specifications> class Name) is no longer required. From that standard onward, the keyword typename can also be used (e.g., template <parameter specifications> typename Name).

23.4.2: Policy classes - II: template template parameters

To specify an allocation policy, rather than an allocation type for the class Storage we rephrase its class template header: definition starts as follows:

    template <typename Data, template <typename> class Policy>
    class Storage...

• The keyword template, starting the template template parameter;
• The keyword template is followed (between pointed brackets) by a list of template parameters that must be specified for the template template parameter. These parameters may be given names, but names are usually omitted as those names cannot be used in subsequent template definitions. On the other hand, providing formal names may help the reader of the template to understand the kind of templates that must be specified with the template template parameter.
• Template template parameters must match, in numbers and types (i.e., template type parameters, template non-type parameters, template template parameters) the template parameters that must be specified for the policy. This can be tricky, as some templates use default parameters that are hardly ever changed (like the allocation schemes for containers). Programmers may not immediately realize that these defaults exist and be confused when the compiler rejects such templates when trying to pass them as template template parameters for which these additional (default) parameters weren't specified. However, language offers a solution for this problem in the form of template aliases, introduced in section 23.5.
• Following the bracketed list the keyword class must be specified. In this case, typename can not be used. However, in the upcoming C++17 standard this restriction will most likely be removed from the language.
• All parameters may be provided with default arguments. This is shown in the next example of a hypothetical class template:

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

  Here, the class template Demo expects a template template parameter named Policy, expecting three template parameters: a template type parameter (by default std::string); a template non-type parameter (by default having value 12); and Policy itself expects a template template parameter, called Inner, by default using an int as its template type parameter.

The policy operates on the class Storage's data type. Therefore the policy is informed about that data type as well. Our class Storage now begins like this:

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

Our home-made allocation classes do not really provide us with many useful members. Except for the extraction operator they offer no immediate access to the data. This can easily be repaired by adding more members. E.g., the class NewAlloc could be augmented with 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;
        }

Let's use the allocation schemes in some real code. The next example shows how Storage can be defined using some data type and an allocation scheme. We start out again with a class Storage:

    template <typename Data, template <typename> class Allocate>
    class Storage: public std::vector<Data, Allocate<Data>>
    {};

All required functionality is inherited from the vector base class, while the policy is `factored into the equation' using a template template parameter. Here's an example showing how this is done:

    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] << '\n';
    storage[1] = "hello";

    copy(storage.begin(), storage.end(),
         ostream_iterator<NewAlloc<std::string> >(cout, "\n"));

Interestingly, this is not the end of the story. Remember that our 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, like a deque. To implement this, the storage class is parameterized as well, using yet another template template parameter:

    template <typename Data, template <typename> class AllocatonPolicy,
              template <typename, typename> class Container = std::vector>
    class Storage: public Container<Data, AllocationPolicy<Data>>
    {};

23.4.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 pointing to the vtable;
• Virtual member functions somewhat reduce the efficiency of code; virtual member functions use dynamic polymorphism, which in principle is undoing the advantages of static polymorphism as 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.

23.4.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 example 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 structure) 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 simplify the real use of the above templates, a generic wrapper class can be constructed: it uses the Size template matching the actually used storage type (e.g., a std::vector or some plain storage class) 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";
    }

23.5: Template aliases

Template aliases can be used as arguments to template template parameters. This allows us to avoid the `unexpected default parameters' you may encounter when using template template parameters. E.g., defining a template specifying a template <typename> class Container is fine, but it is impossible to specify a container like vector or set as template template argument, as vector and set containers also define a second template parameter, specifying their allocation policy.

Template aliases are defined as using declarations, specifying an alias for an existing (maybe partially or fully specialized) template type. In the following example Vector is defined as an alias for vector:

    template <typename Type>
    using Vector = std::vector<Type>;

    Vector<int> vi;             // same as std::vector<int>
    std::vector<int> vi2(vi);   // copy construction: OK

    template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector: ...

    template <typename Type, template <typename> class Container>
    class Generic: public Container<Type>
    {
        ...
    };

The Vector template alias, however, is defined as a template having one template type parameter, and it uses the vector's default allocator. Consequently, passing a Vector to Generic works fine:

    Generic<int, Vector> giv;       // OK
    Generic<int, std::vector> err;  // won't compile: 2nd argument mismatch

With the aid of a small template alias it is also possible to use a completely different kind of container, like a map, with Generic:

    template <typename Type>
    using MapString = std::map<Type, std::string>;

    Generic<int, MapString> gim;    // uses map<int, string>

23.6: Trait classes

Trait classes are used to make compile-time decisions about types. Trait classes allow us to apply the proper code to the proper data type, be it a pointer, a reference, or a plain value, all this maybe in combination with const. The particular type of data to use can be inferred from the actual type that is specified (or implied) when the template is used. This can be fully automated, not requiring the template writer to make any decision.

Trait classes allow us 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 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 deduce whether or not the actual type is a pointer, a pointer to a member, or a const pointer, and to make comparable deductions in case the actual type is, e.g., an lvalue or rvalue 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 point of departure when defining a trait template is a plain vanilla struct, defining the characteristics of a plain value type like 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, an lvalue reference type or an rvalue reference type (all of which may or may not be const types).

Whatever the actually provided type, 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., an rvalue reference to its built-in 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. Maybe something like this:

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

Although some conclusions can be drawn by combining various enum values (e.g., a plain type is not a pointer or a reference or a rvalue reference or a const), 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
            {
                isPointer = true,
                isConst = false,
                isRef = false,
                isRRef = 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
            {
                isPointer = true,
                isConst = true,
                isRef = false,
                isRRef = false
            };
        };

Several other specializations should be defined: e.g., recognizing const value types or (rvalue) reference types. Eventually all these specializations are implemented as 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:
            BasicTraits(BasicTraits const &other) = delete;

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

            enum
            {
                isPointerType = Basic<TypeParam>::isPointer,
                isReferenceType = Basic<TypeParam>::isRef,
                isRvalueReferenceType = Basic<TypeParam>::isRRef,
                isConst = Basic<TypeParam>::isConst,
                isPlainType = not (isPointerType or isReferenceType or
                                   isRvalueReferenceType or isConst)
            };
    };

A trait class template can be used to obtain the proper type, irrespective of the template type argument provided. It can also be used to select a proper specialization that depends on, e.g., the const-ness of a template type. Example:

     cout <<
      "int: plain type? "     << BasicTraits<int>::isPlainType << "\n"
      "int: ptr? "            << BasicTraits<int>::isPointerType << "\n"
      "int: const? "          << BasicTraits<int>::isConst << "\n"
      "int *: ptr? "          << BasicTraits<int *>::isPointerType << "\n"
      "int const *: ptr? "    << BasicTraits<int const *>::isPointerType <<
                                                                      "\n"
      "int const: const? "    << BasicTraits<int const>::isConst << "\n"
      "int: reference? "      << BasicTraits<int>::isReferenceType << "\n"
      "int &: reference? "    << BasicTraits<int &>::isReferenceType << "\n"
      "int const &: ref ? "   << BasicTraits<int const &>::isReferenceType <<
                                                                        "\n"
      "int const &: const ? " << BasicTraits<int const &>::isConst << "\n"
      "int &&: r-reference? " << BasicTraits<int &&>::isRvalueReferenceType <<
                                                                        "\n"
      "int &&: const? " << BasicTraits<int &&>::isConst << "\n"
      "int const &&: r-ref ? "<< BasicTraits<int const &&>::
                                                isRvalueReferenceType << "\n"
      "int const &&: const ? "<< BasicTraits<int const &&>::isConst << "\n"
        "\n";

     BasicTraits<int *>::ValueType           value = 12;
     BasicTraits<int const *>::RvalueRefType rvalue = int(10);
     BasicTraits<int const &&>::PtrType      ptr = new int(14);
     cout << value << ' ' << rvalue << ' ' << *ptr << '\n';

23.6.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. The class template developer might want to define a specialization when the template's type parameter represents 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 at 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 members syntactic construct. Pointers to members are only available for classes. Using the pointer to member construct as the distinguishing characteristic, a specialization can be developed that uses the pointer to member if available. Another specialization (or the generic template) does something else if the pointer to member construction is not available.

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 specialization can be defined having a parameter which is a pointer to a member function. The generic function template then accepts any other argument. The compiler selects the former (specialized) function when the provided type is a class type as class types may support a pointer to a member. The interesting verb here is `may': the class does not have to define a pointer to member.

Furthermore, the compiler does not actually call any function: we're talking compile-time here. All the compiler does is to select the appropriate function by evaluating a constant expression.

So, our intended function template now looks like this:

    template <typename ClassType>
    static `some returntype'  fun(void (ClassType::*)());

To answer the question we now have a look at the generic function template that should be used when the template's argument is not a class type. The language offers a `worst case' parameter in its ellipsis parameter list. The ellipsis is a final resort the compiler may turn to if everything else fails. The generic function template specifies a plain ellipsis in its parameter list:

    template <typename NonClassType>
    static `some returntype' fun(...);

The question now becomes: what argument can be used for both a pointer to a member and for the ellipsis? Actually, there is such a `one size fits all' argument: 0. The value 0 can be passed as argument value to functions defining an ellipsis parameter and to functions defining a pointers-to-member parameter.

But 0 does not specify a particular class. Therefore, fun must specify an explicit template argument, appearing in our code as fun<Type>(0), with Type being the template type parameter of the trait class.

Now for the return type. The function's return type cannot be a simple value (like true or false). Our eventual intent is to provide the trait class with an enum telling us whether the trait class's template argument represents a class type or not. That enum becomes something like this:

    enum { isClass = some class/non-class distinguishing expression } ;

    enum { isClass = fun<Type>(0) } ;

To determine isClass's value we must find an expression allowing for compile-time discriminations between fun<Type>(...) and fun<Type>(void (Type::*)()).

In situations like these the sizeof operator often is our tool of choice as it is evaluated at compile-time. By defining different sized return types for the two fun declarations we are able to distinguish (at compile-time) which of the two fun alternatives is selected by the compiler.

The char type is by definition a type having size 1. By defining another type containing two consecutive char values a larger type is obtained. A char [2] is of course not a type, but a char[2] can be defined as a data member of a struct, and a struct does define a type. That struct then has 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)) == sizeof(Char2) };

• no fun function template is ever instantiated;
• the compiler considers Type and selects fun's function template specialization if Type is a class type and the generic function template if not;
• From the selected function it determines the return type and thus the return type's size;
• Resulting in the proper evaluation of isClass.

23.6.2: Available type traits

All facilities offered by type_traits are defined in the std namespace (omitted from the examples given below), allowing programmers to determine various characteristics of types and values.

In the description of available type traits the following concepts are encountered:

• arithmetic type: any integral or floating point type;

• class type: not a union type, without non-static data members, without virtual members, without virtual or non-empty base classes;

• compound type:
  • arrays of objects of a given type;
  • functions, which have parameters of a given type returning void or objects;
  • pointers to void, to objects, to functions, or to non-static class members;
  • references to objects or functions;
  • class, union or enumeration types;

• fundamental type: a built-in type;

• integral type: all types whose values represent integral numbers, as well as bool and all built-in types representing (possibly unicode) characters;

• literal type: a literal type is a scalar type; a trivial class type; or an array of literal type elements;

• is_nothrow_... type trait: a type trait to determine whether its template argument supports the specified non-throwing member. Such type traits return false unless noexcept(true) is used at the function's declaration. E.g.,

      struct NoThrow
      {
          NoThrow &operator=(SomeType const &rhs) noexept(true);
      };
  

• trivial type: trivial types are scalar types, trivial class types, arrays of such types and cv-qualified versions of these types;

• trivial class type: a class type having a trivial copy constructor, no non-trivial move constructor, a trivial destructor, a trivial default constructor or at least one constexpr constructor other than the copy or move constructor, and only has non-static data members and base classes of literal types;

• trivial member function: trivial member functions are never declared (other than default) in their class interfaces and (for default constructors or assignment operators) only perform byte-by-byte actions. Here are two examples: struct Pod only has trivial members as it doesn't explicitly declare any member function and its data member is plain old data. struct Nonpod is not plain old data. Although it doesn't explictly declare any member function either, its data member is a std::string, which itself isn't plain old data as std::string has non-trivial constructors:

      struct Pod
      {
          int x;
      };
  
      struct Nonpod
      {
          std::string s;
      };
  

When type-condion applies to a type, it must be a complete type, void, or an array of unknown size;

The following type traits are provided:

• add_const<typename Type>::type to add const to Type;

• add_cv<typename Type>::type to add const volatile to Type;

• add_lvalue_reference<typename Type>::type to add an lvalue reference to Type;

• add_lvalue_reference<typename Type>::type to add an lvalue reference to Type;

• add_pointer<typename Type>::type to add a pointer to Type;

• add_rvalue_reference<typename Type>::type to add an rvalue reference to Type;

• add_volatile<typename Type>::type to add volatile to Type;
• conditional<bool cond, typename TrueType, typename FalseType>::type to conditionally use TrueType if cond is true, FalseType if not;

• enable_if<bool cond, typename Type>::type to conditionally define Type if cond is true;

• has_nothrow_assign<typename Type>::value to determine whether Type has an assignment operator not throwing exceptions;

• has_nothrow_copy_constructor<typename Type>::value to determine whether Type has a copy constructor not throwing exceptions;

• has_nothrow_default_constructor<typename Type>::value to determine whether Type has a constructor not throwing exceptions;

• has_nothrow_destructor<typename Type>::value to determine whether Type has a destructor not throwing exceptions;

• has_trivial_assign<typename Type>::value to determine whether Type has a trivial assignment operator;

• has_trivial_copy_constructor<typename Type>::value to determine whether Type has a trivial copy constructor;

• has_trivial_default_constructor<typename Type>::value to determine whether Type has a trivial default constructor;

• has_trivial_destructor<typename Type>::value to determine whether Type has a trivial destructor;

• has_virtual_destructor<typename Type>::value to determine whether Type has a virtual destructor;

• is_abstract<typename Type>::value to determine whether Type is an abstract type (e.g., an abstract base class) (type-condition applies);

• is_arithmetic<typename Type>::value to determine whether Type is an arithmetic type;

• is_array<typename Type>::value to determine whether Type is an array type;

• is_assignable<typename To, typename From>::value to determine whether an object of type From can be assigned to an object of type To (type-condition applies);

• is_base_of<typename Base, typename Derived>::value to determine whether Base is a base class of type Derived;

• is_class<typename Type>::value to determine whether Type is a class type;

• is_compound<typename Type>::value to determine whether Type is a compound type;

• is_const<typename Type>::value to determine whether Type is a const type;

• is_constructible<typename Type, typename ...Args>::value to determine whether Type is constructible from arguments in the Args parameter pack (type-condition applies to all types in Args);

• is_convertible<typename From, typename To>::value to determine whether a type From may be converted to a type To using a static_cast;

• is_copy_assignable<typename Type>::value to determine whether Type supports copy assignment (type-condition applies);

• is_copy_constructible<typename Type>::value to determine whether Type supports copy construction (type-condition applies);

• is_default_constructible<typename Type>::value to determine whether Type supports a default constructor (type-condition applies);

• is_destructible<typename Type>::value to determine whether Type has a non-deleted destructor (type-condition applies);

• is_empty<typename Type>::value to determine whether Type is a class type (not a union type), without non-static data members, virtual members, virtual or non-empty base classes (type-condition applies);

• is_enum<typename Type>::value to determine whether Type is an enum type;

• is_floating_point<typename Type>::value to determine whether Type is a floating point type;

• is_function<typename Type>::value to determine whether Type is a function type;

• is_fundamental<typename Type>::value to determine whether Type is a fundamental type;

• is_integral<typename Type>::value to determine whether Type is an integral type;

• is_literal_type<typename Type>::value to determine whether Type is a literal type (type-condition applies);

• is_lvalue_reference<typename Type>::value to determine whether Type is an lvalue reference;

• is_member_function_pointer<typename Type>::value to determine whether Type is a pointer to a non-static member function;

• is_member_object_pointer<typename Type>::value to determine whether Type is a pointer to a non-static data member;

• is_member_pointer<typename Type>::value to determine whether Type is a pointer to a member function;

• is_move_assignable<typename Type>::value to determine whether Type supports move assignment (type-condition applies);

• is_move_constructible<typename Type>::value to determine whether Type supports move construction (type-condition applies);

• is_nothrow_assignable<typename To, typename From>::value to determine whether Type supports an assignment operator not throwing exceptions (type-condition applies).

• is_nothrow_constructible<typename Type, typename ...Args>::value to determine whether a Type object can be constructed from arguments of types mentioned in the parameter pack not throwing exceptions (type-condition applies);

• is_nothrow_copy_assignable<typename Type>::value to determine whether Type supports a copy-assignment operator not throwing exceptions (type-condition applies);

• is_nothrow_copy_constructible<typename Type>::value to determine whether Type supports copy construction not throwing exceptions (type-condition applies);

• is_nothrow_default_constructible<typename Type>::value to determine whether Type supports a default constructor not throwing exceptions (type-condition applies);

• is_nothrow_destructible<typename Type>::value to determine whether Type supports a destructor not throwing exceptions (type-condition applies).

• is_nothrow_move_assignable<typename Type>::value to determine whether Type supports move assignment not throwing exceptions (type-condition applies);

• is_nothrow_move_constructible<typename Type>::value to determine whether Type supports a move constructor not throwing exceptions (type-condition applies);

• is_object<typename Type>::value to determine whether Type is an object (in contrast to scalar) type;

• is_pod<typename Type>::value to determine whether Type is plain old data (type-condition applies);

• is_pointer<typename Type>::value to determine whether Type is a pointer type;

• is_polymorphic<typename Type>::value to determine whether Type is a polymorphic type (type-condition applies);

• is_reference<typename Type>::value to determine whether Type is an (lvalue or rvalue) reference;

• is_rvalue_reference<typename Type>::value to determine whether Type is an rvalue reference;

• is_same<typename First, typename Second>::value to determine whether types First and Second are identical;

• is_scalar<typename Type>::value to determine whether Type is a scalar type (in contrast to an object type);

• is_signed<typename Type>::value to determine whether Type is a signed type;

• is_standard_layout<typename Type>::value to determine whether Type offers the standard layout (type-condition applies);

• is_trivial<typename Type>::value to determine whether Type is a trivial type (type-condition applies);

• is_trivially_assignable<typename Dest, typename Src>::value to determine whether an object or value of type Src can trivially be assigned to an object of type Dest (type-condition applies);

• is_trivially_constructible<typename Type, typename ...Args>::value to determine whether Type is trivially constructible from arguments in the Args parameter pack (type-condition applies to all types in Args);

• is_trivially_copy_assignable<typename Type>::value to determine whether Type supports a trivial assignment operator (type-condition applies);

• is_trivially_copy_constructible<typename Type>::value to determine whether Type is trivially copy-constructible (type-condition applies);

• is_trivially_copyable<typename Type>::value to determine whether Type is trivially copyable (type-condition applies);

• is_trivially_default_constructible<typename Type>::value to determine whether Type supports a trivial default constructor (type-condition applies);

• is_trivially_default_destructible<typename Type>::value to determine whether Type supports a trivial default destructor (type-condition applies);

• is_trivially_move_assignable<typename Type>::value to determine whether Type supports a trivial assignment operator (type-condition applies);

• is_trivially_move_constructible<typename Type>::value to determine whether Type is trivially move-constructible (type-condition applies);

• is_union<typename Type>::value to determine whether Type is a union type;

• is_unsigned<typename Type>::value to determine whether Type is an unsigned type;

• is_void<typename Type>::value to determine whether Type is void;

• is_volatile<typename Type>::value to determine whether Type is a volatile qualified type;

• make_signed<typename Type>::type to construct a signed type;

• make_unsigned<typename Type>::type to construct an unsigned type;

• remove_all_extents<typename Type>::type if Type is a (possibly multidimensional) array of ElementType values or objects then typedef type equals ElementType;

• remove_const<typename Type>::type to remove const from Type;

• remove_cv<typename Type>::type to remove const and/or volatile from Type;

• remove_extent<typename Type>::type if Type is an array of ElementType values or objects then typedef type equals ElementType. With multi-dimensional arrays ElementType is the type of the array from which its first array dimension has been removed;

• remove_pointer<typename Type>::type to remove a pointer from Type;

• remove_reference<typename Type>::type to remove a reference from Type;

• remove_volatile<typename Type>::type to remove volatile from Type;

23.7: Using `noexcept' when offering the `strong guarantee'

• First, usually on a temporary object, all operations that may throw are performed (which doesn't affect the target object)
• Then, the target object is modified using operations that offer the nothrow guarantee.

The actions in the first step might be made move aware by using std::move (e.g., to assign the source's values to a (possibly temporary) destination). However, using std::move can easily affect the source (e.g., when extending the source's memory, moving the existing data to its new locations), which breaks the first step's assumption, as the target object is now modified.

In this case (and generally) the move operation should not be allowed to throw exceptions. This, in turn, implies that it is difficult to write code which must offer a non-throwing moving constructor, if it uses (external) data types over which the moving constructor has no control. E.g.,

    template <typename Type>
    class MyClass
    {
        Type d_f;
        public:
            MyClass() = default;
            MyClass(MyClass &&tmp)
            :
                d_f(move(tmp.d_f))
            {}
    };

    MyClass<Foreign> s2(move(MyClass<Foreign>()));

If templates are able to detect whether Type has non-throwing move constructors then their implementations may be optimized by calling these move constructors (already modifying their targets in the first part of code offering the strong guarantee) in situations where otherwise the non-modifying, but more expensive copy constructor has to be used.

The noexcept keyword was introduced to allow such templates to perform such optimizations. As with throw lists, checking for noexcept is a run-time check, but the consequence of violating a noexept declaration are more serious than violating a throw list: violating noexcept results in calling std::terminate, terminating the program, possibly without unwinding the stack. In the context of the previous example, the following code is flawlessly accepted by the compiler, demonstrating that there is no compile-time checking of noexcept:

    class Foreign
    {
        public:
            Foreign() = default;
            Foreign(Foreign const &other) noexcept
            {
                throw 1;
            }
    };

    terminate called after throwing an instance of 'int'
    Abort

Keep in mind that the current purpose of noexcept is to allow templates to optimize their code by using move operations where the code must also be able to offer the string exception guarantee. Since noexcept also offers the conditional noexcept(condition) syntax (with noexcept(true) and noexcept having identical semantics), noexcept can be made conditional to the `noexcepting' nature of template types. Note that this is not possible with throw lists.

The following rules of thumb by be used to decide whether or not to use noexcept in your code:

• General rule: don't use noexcept (this is identical to the advise given for throw lists);
• Default implementations of constructors, copy- and move-assignment operators and destructors are provided with noexcept(true) if the compiler can deduct that composing types also offer noexcept(true), allowing template optimizations using move operations where possible.
• Functions provided with noexcept declarations may still throw exceptions (see the example given above). In the end noexcept merely means that if such a function throws an exception std::terminate rather than std::unexpected is called.
• Functions previously provided with an empty throw list (throw()) should now be provided with noexcept(true).
• noexcept specifications are required when using the following std traits (declared in the <type_traits> header file):
  • is_nothrow_constructible
  • is_nothrow_default_constructible
  • is_nothrow_move_constructible
  • is_nothrow_copy_constructible
  • is_nothrow_assignable
  • is_nothrow_move_assignable
  • is_nothrow_copy_assignable
  • is_nothrow_destructible
  These type traits provide the member constant value which is true if the class (and possibly its argument type list) matches the characteristic after which the trait was named. E.g., if MyClass(string const &) noexcept is a constructor, then

      std::is_nothrow_constructible<MyClass, string>::value
  

  equals true. For the named members (like is_nothrow_move_constructible) parameter types do not have to be specified, as they are implied. E.g.,

      std::is_nothrow_move_constructible<MyClass>::value
  

  returns true if the move constructor has the noexcept modifier.

23.8: More conversions to class types

23.8.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 define a partial specialization like this:

    template <typename Argument>        // This won't compile!
    std::string chop<std::string, Argument>(Argument const &arg)
    {
        return string(arg, 1);
    }

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

Instead of providing a string dummy argument the functions could use the IntType template (cf. section 23.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 view of program efficiency this is an attractive option, as the provided IntType objects are extremely lightweight. IntType objects contain no data at all. But there's also an obvious disadvantage as there is no intuitively clear association between the int value used and the intended type.

Instead of defining arbitrary IntType types it is more attractive to use another lightweight solution, using an automatic type-to-type association. The struct TypeType is a lightweight type wrapper, much like IntType. 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);
    }

    template <typename Result>
    Result chop(char const *txt)    // char const * could also be a 2nd
    {                               // template type parameter
        return chop(std::string(txt), TypeType<Result>());
    }

    cout << chop<string>("hello world") << '\n';

23.8.2: An empty type

    struct NullType
    {};

23.8.3: Type convertibility

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 is that no code is actually generated or executed. All decisions are made by the compiler.

In the second part of this section we'll show how the code developed in the first part can be used to detect whether a class B is a base class of another class D (the is_base_of template (cf. section 23.6.2) also provides an answer to this question). The code developed here closely follows the example provided by Alexandrescu (2001, p. 35).

First, a function test is designed accepting a type U. The function test returns a value of the as yet unknown type Convertible:

    Convertible test(U const &);

The function test is never implemented. It is only declared. If a type T can be used instead of a type U then T can also be passed as argument to the above test function.

On the other hand, if the alternate type T cannot be used where a U is expected, then the compiler won't be able to use the above test function. Instead, it uses an alternative function that has a lower selection priority but that can always be used with any T type.

C (and C++) offer a very general parameter list, a parameter list that is always considered acceptable. This parameter list is the familiar ellipsis which represents the worst case the compiler may encounter. If everything else fails, then the function defining an ellipsis as its parameter list is selected.

Usually that's not a productive alternative, but in the current situation it is exactly what is needed. When confronted with two candidate functions, one of which defines an ellipsis parameter, the compiler selects the function defining the ellipsis parameter only if the alternative(s) can't be used.

Following the above reasoning an alternative function test(...) is declared as well. This alternate function does not return a Convertible value but a NotConvertible value:

    NotConvertible test(...);

If test's argument is of type T and if T can be converted to U then test's return type is Convertible. Otherwise NotConvertible is returned.

This situation clearly shows similarities with the situation encountered in section 23.6.1 where the value isClass had to be determined compile time. Here two related problems must be solved:

• how do we obtain a T argument? This is more difficult than might be expected at first sight as it might not be possible to define a T. If type T does not define any constructor then no T object can be defined.
• how can Convertible be distinguished from NotConvertible?

By simply declaring a function returning a T we can tell the compiler where it should assume a T:

    T makeT();

    T const &makeT();

Next we pass a T const & to test: following code:

    test(makeT())

The second problem, distinguishing Convertible from NotConvertible is solved exactly the way isClass could be determined in section 23.6.1, viz. by making their sizes different. Having done so the following expression determines whether T is convertible from U or not:

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

The above can be summarized in a class template LconvertibleToR, having two template type parameters:

    template <typename T, typename U>
    class LconvertibleToR
    {
        struct Char2
        {
            char array[2];
        };
        static T const &makeT();
        static char test(U const &);
        static Char2 test(...);

        public:
            LconvertibleToR(LconvertibleToR const &other) = delete;
            enum { yes = sizeof(test(makeT())) == sizeof(char) };
            enum { sameType = 0 };
    };

    template <typename T>
    class LconvertibleToR<T, T>
    {
        public:
            LconvertibleToR(LconvertibleToR const &other) = delete;
            enum { yes = 1 };
            enum { sameType = 1 };
    };

As the class template deletes its copy constructor no object can be created. Only its enum values can be interrogated. The next example writes 1 0 1 0 when run from a main function:

    cout <<
        LconvertibleToR<ofstream, ostream>::yes << " " <<
        LconvertibleToR<ostream, ofstream>::yes << " " <<
        LconvertibleToR<int, double>::yes << " " <<
        LconvertibleToR<int, string>::yes <<
        "\n";

23.8.3.1: Determining inheritance

Inheritance is determined by inspecting convertibility of (const) pointers. Derived const * can be converted to Base const * if

• both types are identical;
• Base is a public and unambiguous base class of Derived;
• and (usually not intended) if Base is void.

    template <typename Base, typename Derived>
    struct LBaseRDerived
    {
        LBaseRDerived(LBaseRDerived const &) = delete;
        enum {
            yes =
                LconvertibleToR<Derived const *, Base const *>::yes &&
                not LconvertibleToR<Base const *, void const *>::sameType
        };
    };

If code should not consider a class to be its own base class, then the trait class LBaseRtrulyDerived can be used to perform a strict test. This trait class adds a test for type-equality:

    template <typename Base, typename Derived>
    struct LBaseRtrulyDerived
    {
        LBaseRtrulyDerived(LBaseRtrulyDerived const &) = delete;
        enum {
            yes =
                LBaseRDerived<Base, Derived>::yes &&
                not LconvertibleToR<Base const *, Derived const *>::sameType
        };
    };

Example: the next statement displays 1: 0, 2: 1, 3: 0, 4: 1, 5: 0 when executed from a main function:

    cout << "\n" <<
        "1: " << LBaseRDerived<ofstream, ostream>::yes << ",  " <<
        "2: " << LBaseRDerived<ostream, ofstream>::yes << ",  " <<
        "3: " << LBaseRDerived<void, ofstream>::yes << ",  " <<
        "4: " << LBaseRDerived<ostream, ostream>::yes << ",  " <<
        "5: " << LBaseRtrulyDerived<ostream, ostream>::yes <<
        "\n";

23.9: Template TypeList processing

This section itself was inspired by Andrei Alexandrescu's (2001) book Modern C++ design. It diverts from Alexandrescu's book in its use of variadic templates which were not yet available when he wrote his book. Even so, the algorithms used by Alexandrescu are still useful when using variadic templates.

C++ offers the tuple to store and retrieve values of multiple types. Here the focus is merely on processing types. A simple struct TypeList is going to be used as our working horse for the upcoming subsections. Here is its definition:

    template <typename ...Types>
    struct TypeList
    {
        TypeList(TypeList const &) = delete;
        enum { size = sizeof ...(Types) };
    };

A typelist allows us to store any number of types. Here is an example storing the three types char, short, int in a TypeList:

    TypeList<char, short, int>

23.9.1: The length of a TypeList

    std::cout << TypeList<int, char, bool>::size << '\n';

However, it's illustrative to see how the number of types specified with a TypeList could be determined if sizeof hadn't been available.

To obtain the number of types that were specified with a TypeList the following algorithm is used:

• If the TypeList contains no types, its size equals zero;
• If the TypeList contains types, its size equals 1 plus the number of types that follow its first type.

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

The number of types that are specified in a TypeList can be computed using the following alternate implementation of TypeList, using a generic struct declaration and two specialization for the empty and non-empty TypeList (cf. the above description of the algorithm):

    template <typename ...Types>
    struct TypeList;

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

23.9.2: Searching a TypeList

• If the TypeList is empty, `index' is -1;
• If the TypeList's first element equals SearchType, `index' is 0;
• Otherwise `index' is:
  • -1 if searching for SearchType in TypeList's tail results in `index' == -1;
  • Otherwise (SearchType was found in TypeList's tail) index is set to 1 + the index obtained when searching for SearchType in the TypeList's tail.

    template <typename ...Types>
    struct ListSearch
    {
        ListSearch(ListSearch const &) = delete;
    };

Specializations handle the alternatives mentioned with the algorithm:

• If TypeList is empty, `index' is -1:

      template <typename SearchType>
      struct ListSearch<SearchType, TypeList<>>
      {
          ListSearch(ListSearch const &) = delete;
          enum { index = -1 };
      };
  

• If TypeList's head equals SearchType, `index' is 0. Note that SearchType is explicitly mentioned as the TypeList's first element:

      template <typename SearchType, typename ...Tail>
      struct ListSearch<SearchType, TypeList<SearchType, Tail...>>
      {
          ListSearch(ListSearch const &) = delete;
          enum { index = 0 };
      };
  

• Otherwise a search is performed on the TypeList's tail. The index value returned by this search is stored in a tmp enum value, which is then used to determine index's value.

      template <typename SearchType, typename Head, typename ...Tail>
      struct ListSearch<SearchType, TypeList<Head, Tail...> >
      {
          ListSearch(ListSearch const &) = delete;
          enum {tmp = ListSearch<SearchType, TypeList<Tail...>>::index};
          enum {index = tmp == -1 ? -1 : 1 + tmp};
      };
  

    std::cout <<
        ListSearch<char, TypeList<int, char, bool>>::index << "\n" <<
        ListSearch<float, TypeList<int, char, bool>>::index << "\n";

23.9.3: Selecting from a TypeList

The algorithm is implemented using a struct TypeAt. TypeAt uses a typedef to define the type matching a given index. But the index might be out of bounds. In that case we have several options:

• Use a static_assert to stop the compilation. This is an appropriate action if the index should simply not be out of bounds;
• Define a local type (e.g., Null) that should not be used as a type in the TypeList. This type is going to be returned when the index is out of bounds. Using this local type as one of the types in a TypeList is considered an error as its would conflict with the special meaning of Null as the type returned at an invalid index.
  To prevent Null from being returned by TypeAt a static_assert is used to catch the Null type when it is encountered while evaluating TypeAt;
• The struct TypeAt may define an enum value validIndex set to true if the index was valid and set to false if not.

• The foundation consists of a variadic template struct TypeAt, expecting an index and a TypeList:

      template <size_t index, typename Typelist>
      struct TypeAt;
  

• If the typelist is empty a static_assert ends the compilation

      template <size_t index>
      struct TypeAt<index, TypeList<>>
      {
          static_assert(index < 0, "TypeAt index out of bounds");
          typedef TypeAt Type;
      };
  

• If the search index equals 0, define Type as the first type in the TypeList:

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

• Otherwise, Type is defined as Type defined by TypeAt<index - 1> operating on the TypeList's tail:

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

    typedef TypeList<int, char, bool> list3;

//    TypeAt<3, list3>::Type invalid;
    TypeAt<0, list3>::Type intVariable = 13;
    TypeAt<2, list3>::Type boolVariable = true;

    cout << "The size of the first type is " <<
                sizeof(TypeAt<0, list3>::Type) << ", "
            "the size of the third type is " <<
                sizeof(TypeAt<2, list3>::Type) << "\n";

    if (typeid(TypeAt<1, list3>::Type) == typeid(char))
        cout << "The typelist's 2nd type is char\n";

    if (typeid(TypeAt<2, list3>::Type) != typeid(char))
        cout << "The typelist's 3nd type is not char\n";

23.9.4: Prefixing/Appending to a TypeList

Here are the declarations of the two variadic template structs:

    template <typename ...Types>
    struct Append;

    template <typename ...Types>
    struct Prefix;

To append or prefix a new type to a typelist, specializations expect a typelist and a type to add. Then, they simply define a new TypeList also including the new type. The Append specialization shows that a template pack does not have to be used as the first argument when defining another variadic template type:

    template <typename NewType, typename ...Types>
    struct Append<TypeList<Types...>, NewType>
    {
        typedef TypeList<Types..., NewType> List;
    };

    template <typename NewType, typename ...Types>
    struct Prefix<NewType, TypeList<Types...>>
    {
        typedef TypeList<NewType, Types...> List;
    };

23.9.5: Erasing from a TypeList

• The type to erase is specified, and the first occurrence of that type is removed from the TypeList;
• The index of the type to erase is specified, and the type at that index position is erased from the TypeList;
• The type to erase is specified, and all occurrences of that type are removed from the TypeList.
• As a variant of erasure: we may want to erase all multiply occurring types in a TypeList, keeping each type only once.

23.9.5.1: Erasing the first occurrence

• The foundation of the algorithm consists of a struct template Erase expecting the type to erase and a TypeList:

      template <typename EraseType, typename TypeList>
      struct Erase;
  

• If the typelist is empty, there's nothing to erase, and an empty TypeList results:

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

• If the TypeList's head matches the type to erase, then List becomes a TypeList containing the original TypeList's tail types:

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

• In all other cases the erase operation is applied to the TypeList's tail. This results in a TypeList to which the orginal TypeList's head must be prefixed. The TypeList returned by the prefix operation is then returned as Erase::List:

      template <typename EraseType, typename Head, typename ...Tail>
      struct Erase<EraseType, TypeList<Head, Tail...>>
      {
          typedef typename
              Prefix<Head,
                  typename Erase<EraseType, TypeList<Tail...>>::List
              >::List List;
      };
  

    cout <<
            Erase<int, TypeList<char, double, int>>::List::size << '\n' <<
            Erase<char, TypeList<int>>::List::size << '\n' <<
            Erase<int, TypeList<int>>::List::size << '\n' <<
            Erase<int, TypeList<>>::List::size << "\n";

23.9.5.2: Erasing a type by its index

• The foundation of the algorithm consists of a struct template EraseIdx expecting the index of the type to erase and a TypeList:

      template <size_t idx, typename TypeList>
      struct EraseIdx;
  

• If the typelist is empty, there's nothing to erase, and an empty TypeList results:

      template <size_t idx>
      struct EraseIdx<idx, TypeList<>>
      {
          typedef TypeList<> List;
      };
  

• The recursion otherwise ends once idx becomes 0. At that point the TypeList's first type is ignored and List is initialized to a TypeList containing the types in the orginal TypeList's tail:

      template <typename EraseType, typename ...Tail>
      struct EraseIdx<0, TypeList<EraseType, Tail...>>
      {
          typedef TypeList<Tail...> List;
      };
  

• In all other cases EraseIdx is applied to the TypeList's tail, providing it with a decremented value of idx. To the resulting TypeList the orginal TypeList's head is prefixed. The TypeList returned by the prefix operation is then returned as EraseIdx::List:

      template <size_t idx, typename Head, typename ...Tail>
      struct EraseIdx<idx, TypeList<Head, Tail...>>
      {
          typedef typename Prefix<
                      Head,
                      typename EraseIdx<idx - 1, TypeList<Tail...>>::List
                  >::List List;
      };
  

    if
    (
        typeid(TypeAt<2,
                EraseIdx<1,
                   TypeList<int, char, size_t, double, int>>::List
                >::Type
        )
        == typeid(double)
    )
        cout << "the third type is now a double\n";

23.9.5.3: Erasing all occurrences of a type

Here is the algorithm, described in a slightly different order than Erase's algorithm:

• If the TypeList is empty, there's nothing to erase, and an empty TypeList results. This is exactly what we do with Erase, so we can use inheritance to prevent us from having to duplicate elements of a template meta program:

      template <size_t idx>
      struct EraseIdx<idx, TypeList<>>
      {
          typedef TypeList<> List;
      };
  

• The foundation of the algorithm is therefore a struct template EraseAll expecting the type to erase and a TypeList that is derived from Erase, thus already offering the empty TypeList handling specialization:

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

• If TypeList's head matches EraseType EraseAll is also applied to the TypeList's tail, thus removing all occurrences of EraseType from TypeList:

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

• In all other cases (i.e., TypeList's head does not match EraseType) EraseAll is applied to the TypeList's tail. The returned TypeList consists of the original TypeList's initial type and the types of the TypeList returned by the recursive EraseAll call:

      template <typename EraseType, typename Head, typename ...Tail>
      struct EraseAll<EraseType, TypeList<Head, Tail...>>
      {
          typedef typename Prefix<
              Head,
              typename EraseAll<EraseType, TypeList<Tail...>>::List
          >::List List;
      };
  

    cout <<
        "After erasing size_t from "
            "TypeList<char, int, size_t, double, size_t>\n"
            "it contains " <<
                EraseAll<size_t,
                         TypeList<char, int, size_t, double, size_t>
                >::List::size << " types\n";

23.9.5.4: Erasing duplicates

• First, the generic EraseDup struct template is declared. EraseDup structures define a type List representing the TypeList that they generate. EraseDup calls expect a TypeList as their template type parameters:

      template <typename TypeList>
      struct EraseDup;
  

• If the TypeList is empty it can be returned empty and we're done:

      template <>
      struct EraseDup<TypeList<>>
      {
          typedef TypeList<> List;
      };
  

• In all other cases
  • EraseDup is first applied to the original TypeList's tail. By definition this results in a TypeList from which all duplicates have been removed;
  • The TypeList returned by the previous step might contain the original TypeList's initial type. If so, it is removed by applying Erase on the returned TypeList, specifying the original TypeList's initial type as the type to remove;
  • The returned TypeList consists of the original TypeList's initial type to which the types of the TypeList produced by the previous step are appended.
  This specialization is implemented like this:

      template <typename Head, typename ...Tail>
      struct EraseDup<TypeList<Head, Tail...>>
      {
          typedef typename EraseDup<TypeList<Tail...>>::List UniqueTail;
          typedef typename Erase<Head, UniqueTail>::List NewTail;
  
          typedef typename Prefix<Head, NewTail>::List List;
      };
  

    cout <<
        "After erasing duplicates from "
             "TypeList<double, char, int, size_t, int, double, size_t>\n"
        "it contains " <<
        EraseDup<
            TypeList<double, char, int, size_t, int, double, size_t>
        >::List::size << " types\n";

23.10: Using a TypeList

But there's more to typelist than a mere intellectual challenge. In the final sections of this chapter the following topics are 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 mentioned in a provided typelist;
• Accessing data members from the thus constructed conglomerate class by index, rather than name.

23.10.1: The Wrap and Multi class templates

In fact, the types that are specified with Multi aren't that interesting. They primarily serve to `seed' the class Policy. Therefore, rather than forwarding Multi's types to MultiBase they are passed to Policy and the sequence of Policy<Type> types is then forwarded to MultiBase. Multi's constructor expects initialization values for its various Policy<Type>s which are perfectly forwarded to MultiBase.

The class Multi (implementing its constructor in-class to save some space) shows how a template pack can be wrapped into a policy. Here is Multi's definition:

    template <template <typename> class Policy, typename ...Types>
    struct Multi: public MultiBase<0, Policy<Types>...>
    {
        typedef TypeList<Types...> PlainTypes;
        typedef MultiBase<0, Policy<Types>...> Base;

        enum { size = PlainTypes::size };

        Multi(Policy<Types> &&...types)
        :
            MultiBase<0, Policy<Types>...>(
                            std::forward<Policy<Types>>(types)...)
        {}
    };

Unfortunately, the design as described contains some flaws.

• As the Policy template template parameter is defined as template <typename> class Policy it can only accept policies expecting one type argument. Contrary to this, std::vector is a template expecting two template arguments, the second one defining the allocation scheme used by std::vector. This allocation scheme is hardly ever changed, and most applications merely define objects of types like vector<int>, vector<string> etc.. Template template parameters must, however, be specified with the correct number and types of required template parameters so vector can't be specified as a policy for Multi. This can be solved by wrapping a more complex template in a simpler wrapper template, like so:

      template <class Type>
      struct Vector: public std::vector<Type>
      {
          Vector(std::initializer_list<Type> iniValues)
          :
              std::vector<Type>(iniValues)
          {}
      };
  

  Now Vector provides std::vector's second parameter using its default template argument. Alternatively, a template using declaration could be used.

• If the TypeList contains two types like int and double and the policy class is Vector, then the MultiBase class eventually inherits from vector<int> and vector<double>. But if the TypeList contains identical types, like two int type specifications MultiBase would inherit from two vector<int> classes. Classes cannot be derived from identical base classes as that would make it impossible to distinguish among their members. Regarding this, Alexandrescu (2001) 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.

    template <size_t nr, typename Type>
    struct UWrap: public Type
    {
        UWrap(Type const &type)
        :
            Type(type)
        {}
    };

Using UWrap it's easy to distinguish, e.g., two vector<int> classes: UWrap<0, vector<int>> could refer to the first vector<int>, UWrap<1, vector<int>> to the second vector.

Uniqueness of the various UWrap types is assured by the class template MultiBase as discussed in the next section.

It must also be possible to initialize a Multi class object. Its constructor therefore expects the initialization values for all its Policy values. So if a Multi is defined for Vector, int, string then its constructor can receive the matching initialization values. E.g.,

    Multi<Vector, int, string> mvis({1, 2, 3}, {"one", "two", "three"});

23.10.2: The MultiBase class template

MultiBase itself has no concept of a Policy. To MultiBase the world appears to consist of a simple template pack whose types are used to define a class from. In addition to the PolicyTypes template pack, MultiBase also defines a size_t nr non-type parameter that is used to create unique UWrap types. Here is MultiBase's generic class declaration:

    template <size_t nr, typename ...PolicyTypes>
    struct MultiBase;

Two specializations handle all possible MultiBase invocations. One specialization is a recursive template. This template handles the first type of MultiBase's template parameter pack and recursively uses itself to handle the remaining types. The second specialization is invoked once the template parameter pack is exhausted and does nothing. Here is the definition of the latter specialization:

    template <size_t nr>
    struct MultiBase<nr>
    {};

The recursively defined specialization is the interesting one. It performs the following tasks:

• It is derived from a unique UWrap type. The uniqueness is guaranteerd by using MultiBase's nr parameter when defining UWrap. In addition to nr the UWrap class receives the first type of the template parameter pack made available to MultiBase;
• It is also recursively derived from itself. The recursive MultiBase type is defined using as its first template argument an incremented nr value (thus ensuring the uniqueness of the UWrap types defined by recursive MultiWrap types). Its second template argument is the tail of the template parameter pack made available to MultiBase

MultiBase's constructor simply receives the initialization values that were (originally) passed to the Multi object. Perfect forwarding is used to accomplish this. MultiBase's constructor passes its first parameter value to its UWrap base class, also using perfect forwarding. MultiBase's recursive definition is:

    template <size_t nr, typename PolicyT1, typename ...PolicyTypes>
    struct MultiBase<nr, PolicyT1, PolicyTypes...> :
                                public UWrap<nr, PolicyT1>,
                                public MultiBase<nr + 1, PolicyTypes...>
    {
        typedef PolicyT1 Type;
        typedef MultiBase<nr + 1, typename PolicyTypes...> Base;

        MultiBase(PolicyT1 && policyt1, PolicyTypes &&...policytypes)
        :
            UWrap<nr, PolicyT1>(std::forward<PolicyT1>(policyt1)),
            MultiBase<nr + 1, PolicyTypes...>(
                              std::forward<PolicyTypes>(policytypes)...)
        {}
    };

23.10.3: Support templates

These three type definitions allow us to access the types from which the Multi object was created as well as the values of those types.

The class template typeAt, is a pure template meta program class template (it has no run-time executable code). It expects a size_t idx template argument specifying the index of the policy type in a Multi type object as well as a Multi class type. It defines the type Type as the Type defined by Multi's MultiBase<idx, ...> base class. Example:

    typeAt<0, Multi<Vector, int, double>>::Type // Type is vector<int>

The class template typeAt defines (and uses) a nested class template PolType doing all the work. PolType's generic definition specifies two template parameters: an index used to specify the index of the requested type and a typename initialized by a MultiBase type argument. PolType's recursive definition recursively reduces its index non-type parameter, passing the next base class in MultiBase's inheritance tree to the recursive call. As PolType eventually defines the type Type to be the requested policy type the recursive definition defines its Type as the type defined by the recursive call. The final (non-recursive) specialization defines the initial policy type of the MultiBase type as Type. Here is typeAt's definition:

    template <size_t index, typename Multi>
    class typeAt
    {
        template <size_t idx, typename MultiBase>
        struct PolType;

        template <size_t idx,
                  size_t nr, typename PolicyT1, typename ...PolicyTypes>
        struct PolType<idx, MultiBase<nr, PolicyT1, PolicyTypes...>>
        {
            typedef typename PolType<
                idx - 1, MultiBase<nr + 1, PolicyTypes...>>::Type Type;
        };

        template <size_t nr, typename PolicyT1, typename ...PolicyTypes>
        struct PolType<0, MultiBase<nr, PolicyT1, PolicyTypes...>>
        {
            typedef PolicyT1 Type;
        };
    public:
        typeAt(typeAt const &) = delete;
        typedef typename PolType<index, typename Multi::Base>::Type Type;
    };

The types specified by Multi's parameter pack can also be retrieved using a second helper class template: plainTypeAt. Example:

    plainTypeAt<0, Multi<Vector, int, double>>::Type // Type is int

    template <size_t index, typename Multi>
    class plainTypeAt
    {
        template <size_t idx, typename List>
        struct At;

        template <size_t idx, typename Head, typename ...Tail>
        struct At<idx, TypeList<Head, Tail...>>
        {
            typedef typename At<idx - 1, TypeList<Tail...>>::Type Type;
        };

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

    public:
        plainTypeAt(plainTypeAt const &) = delete;
        typedef typename At<index, typename Multi::PlainTypes>::Type Type;
    };

Arguably the neatest support template is get. This is a function template defining size_t idx as its first template parameter and typename Multi as its second template parameter. The function template get defines one function parameter: a reference to a Multi, so it can deduct Multi's type by itself. Knowing that it's a Multi, we reason that it is also a UWrap<nr, PolicyType> and therefore also a PolicyType, as the latter class is defined as a base class of UWrap.

Since class type objects can initialize references to their base classes the PolicyType & can be initialized by an appropriate UWrap reference, which in turn can be initialized by a Multi object. Since we can determine PolicyType using TypeAt (note that evaluating typename typeAt<idx, Multi>::Type is a purely compile-time matter), the get function can very well be implemented inline by a single return statement:

    template <size_t idx, typename Multi>
    inline typename typeAt<idx, Multi>::Type &get(Multi &multi)
    {
        return static_cast<
                UWrap<idx, typename typeAt<idx, Multi>::Type> &>(multi);
    }

The intermediate UWrap cast is required to disambiguate between identical policy types (like two vector<int> types). As UWrap is uniquely determined by its nr template argument and this is the number argument that is passed to get ambiguities can easily be prevented.

23.10.4: Using Multi

A word of warning is in place. To reduce the size of the developed classes they were designed in a minimalist way. For example, the get function template cannot be used with Multi const objects and there is no default, or move constructor available for Multi types. Multi was designed to illustrate some of the possibilities of template meta programming and hopefully Multi's implementation served that purpose well. But can it be used? If so, how?

This section provides some annotated examples. They may be concatenated to define a series of statements that could be placed in a main function's body, which would result in a working program.

• A simple Policy could be defined:

      template <typename Type>
      struct Policy
      {
          Type d_type;
          Policy(Type &&type)
          :
              d_type(std::forward<Type>(type))
          {}
      };
  

  Policy defines a data member and it can be used to define Multi objects:

      Multi<Policy, string> ms(Policy<string>("hello"));
      Multi<Policy, string, string> ms2s(Policy<string>("hello"),
                                         Policy<string>("world"));
  
  
       typedef Multi<Policy, string, int> MPSI;
       MPSI mpsi(string("hello"), 4);
  

• To obtain the number of types defined by a Multi class or object either use the ::size enum value (using the Multi class) or the .size member (using the Multi object):

      cout << "There are " << MPSI::size << " types in MPSI\n"
              "There are " << mpsi.size << " types in mpsi\n";
  

• Variables of constituting types can be defined using plainTypeAt:

      plainTypeAt<0, MPSI>::Type sx = "String type";
      plainTypeAt<1, MPSI>::Type ix = 12;
  

• Raw static casts can be used to obtain the constituent type:

      cout << static_cast<Policy<string> &>(mpsi).d_type << '\n' <<
              static_cast<Policy<int> &>(mpsi).d_type << '\n';
  

• However, this won't work when the template parameter pack contains identical types, as a cast can't distinguish between identical Policy<Type> types. In that case get still works fine:

      typedef Multi<Policy, int, int> MPII;
      MPII mpii(4, 18);
  
      cout << get<0>(mpii).d_type << ' ' << get<1>(mpii).d_type << '\n';
  

• Here is an example wrapping a std::vector in a Vector:

      typedef Multi<Vector, int, double> MVID;
      MVID mi({1, 2, 3}, {1.2, 3.4, 5.6, 7.8});
  

• Such a vector can be defined by its Multi type:

      typeAt<0, Multi<Vector, int>>::Type vi = {1, 2, 3};
  

• Knowing that a Vector is a std::vector, the reference returned by get support index operators that can be used as left hand side or right hand side operands:

      cout << get<0>(mi)[2] << '\n';
      get<1>(mi)[3] = get<0>(mi)[0];
      cout << get<1>(mi)[3] << '\n';
  

23.11: Expression Templates

Assume we are processing std::vector objects. Vectors may be assigned to each other, but that's about it. We've seen (cf. section 12.4.2) that its member functions tend to operate on the current vector, but arithmetic operations like addition, subtraction, multiplication and the like cannot be applied to pairs of vectors.

Furtunately implementing, e.g., the addition operator for vectors is not particularly difficult. If VecType is our vector type, then implementing free functions like VecType operator+(VecType const &lhs, VecType const &rhs) and VecType operator+(VecType &&lhs, VecType const &rhs) performing the additions is a simple exercise (cf. chapter 11).

Now consider an expression like one + two + three + four. It takes four steps to compute this sum: first, tmp = one is computed, creating the eventual return value. The vector tmp is an (in practice anonymous) temporary variable. Then tmp += two is computed, followed by tmp += three, and finally by tmp += four, obtaining the final result (of course we shouldn't implement std::vector::operator+= as the std namespace is off-limits to us, and we shouldn't derive a class from std::vector offering operator+= according to Liskov's Substitution Principle (cf. section 14.7), but we could get around that, and here we simply assume operator+= is available).

Here's how we might implement operator+= for VecType:

    VecType &VecType::operator+=(VecType const &rhs)
    {
        for (size_t idx = 0, end = size(); idx != end; ++idx)
            (*this)[idx] += rhs[idx];
        return *this;
    }

If instead we could manage to perform the evaluations `row by row', each vector element would be accessed only once. This would dramatically cut down on our index evaluations. We would only need to perform approx. n * k index expression evaluations.

Expression templates allow us to achieve precisely this kind of optimization. We'll have a look at their design and implementation in the coming sections.

23.11.1: Designing an Expression Template

Expression templates allow us to avoid many of these evaluations. When using expression templates these templates may access the vectors, but their elements are not accessed during addition operations.

Assuming our expression template is named ET, and we want to add one + two + three, then the first + operator merely creates ET(one, two). Note that no addition is actually performed, ET merely stores (constant) references to one (becoming ET's lhs data member) and two (becoming ET's rhs data member). In general, ET stores references to the two arguments that are passed to its constructor.

At the next addition operator another ET is created. Its constructor arguments are, respectively, the ET object that has just been constructed for one and two, and the vector three. Again, no addition is performed by the ET objects.

This algorithm easily generalizes to any number of vectors. Parentheses can also be used. E.g., (one + two) + (three + four) results in

    ET(ET(one, two), ET(three, four))

Presumably, at some point we want to obtain the sum of the vectors. For this the expression template is provided with a conversion operator, converting the ET object to a vector, or maybe an assignment operator doing the same.

The conversion operator looks like this:

    operator ET::VecType() const
    {                                                        
        VecType retVal;
        retVal.reserve(size());

        for (size_t ix = 0, end = size(); ix != end; ++ix)
            new(&retVal[ix]) value_type((*this)[ix]);
                                                     
        return retVal;
    }

ET's index operator simply adds the values returned by the corresponding index expressions of its lhs and rhs data members. If a data member refers to a vector then the corresponding vector element is used, adding it to the other data member's value. If a data member itself refers to an ET object, then that nested ET object's index operator performs the same addition on its own data members, returning their sum. So, an expression like (*this)[0] returns first[0] + second[0] + third[0], and the computed sum is then stored in retVal[0] using placement new.

In this case the required number of index expression evaluations are n * k (for the n elements of the k vectors) plus n (for the n elements of retVal, adding up to (k + 1) * n).

Since (k + 1) * n < 2 * k * n for k > 1 expression templates evaluate the requested addition more efficiently than the traditional implementation of operator+. An additional benefit of using expression templates is that they do not create additional temporary vector objects when parenthesized expressions are used.

23.11.2: Implementing an Expression Template

Starting point is a simple main function, in which several IntVect objects are added. E.g.,

    int main()
    {
        IntVect one;
        IntVect two;
        IntVect three;
        IntVect four;
        
        // ... assume the IntVects somehow receive values

        four = one + two + three + four;
    }

    template<typename LHS, typename RHS>
    BinExpr<LHS, RHS, plus>  operator+(LHS const &lhs, RHS const &rhs)
    {
        return BinExpr<LHS, RHS, plus>(lhs, rhs);
    }

Our expression template is called BinExpr. It has three template type parameters: two object types and a template template parameter performing the requested operation. Its declaration looks like this:

    template<typename LHS, typename RHS, template<typename> class Operation>
    struct BinExpr;

BinExpr's constructor initializes constant references to lhs and rhs. Its in-class implementation is

    BinExpr(LHS const &lhs, RHS const &rhs)
    :
        d_lhs(lhs),
        d_rhs(rhs)
    {}

To retrieve the resulting IntVect a conversion operator is defined. We already encountered its implentation (in the previous section). Here is it, as an in-class implemented BinExpr member:

    operator ObjType() const
    {                                                        
        ObjType retVal;
        retVal.reserve(size());

        for (size_t idx = 0, end = size(); idx != end; ++idx)
            new(&retVal[idx]) value_type((*this)[idx]);
                                                     
        return retVal;
    }

    size_t size() const
    {
        return d_lhs.size();
    }

The only remaining member to implement is operator[]. Since it receives an index, it only needs to perform the requested operation on the corresponding index elements of its d_lhs and d_rhs data members. The beauty of expression templates is that if either one itself is a BinExpr that expression template in turn calls its operator[], eventually performing the requested operation on all corresponding elements of all IntVect objects. Here is its implementation:

    value_type operator[](size_t ix) const
    {
        static Operation<value_type> operation;

        return operation(d_lhs[ix], d_rhs[ix]);
    }

So, it's about time to have a look at ObjType and value_type. We do that in the next section.

23.11.3: The BasicType trait class and ordering classes

In expressions like one + two + three, the BinExpr expression template receives two IntVect objects. This is always true: the BinExpr that is first constructed receives two IntVect objects. In this case ObjType is simply LHS, and ObjType::value_type is also available: either value_type is already defined by LHS or BinExpr requires that it defines type value_type.

Since arguments to BinExpr objects are not always of the basic ObjType type (BinExpr objects at the next nesting level receive at least one BinExpr argument) we need a way to determine ObjType from a BinExpr. For this we use a trait class. The trait class BasicType receives a typename template argument, and equates its type ObjType to the received template type argument:

    template<typename Type>
    struct BasicType
    {
        typedef Type ObjType;
    };

    template<typename LHS, typename RHS, template<typename> class Operation>
    struct BasicType<BinExpr<LHS, RHS, Operation>>
    {
        typedef typename BinExpr<LHS, RHS, Operation>::ObjType ObjType;
    };

Since BinExpr requires that ObjType::value_type is a defined type, value_type has automatically been taken care of.

As BinExpr refers to BasicType and BasicType refers to BinExpr somewhere we must provide a forward declaration. As BinExpr's declaration has already been provided, we start with that declaration, resulting in:

    BinExpr's declaration

    BasicType's definition

    BasicType's specialization (for BinExpr)

    template<typename LHS, typename RHS, template<typename> class Operation>
    class BinExpr 
    {
        LHS const &d_lhs;
        RHS const &d_rhs;

        public:
            typedef typename BasicType<RHS>::DataType DataType;
            typedef typename DataType::value_type value_type;

            // all BinExpr member functions
    };

• Table of Contents
• Previous Chapter
• Next Chapter