C++ Generics (Templates)

Multiparadigm: OOP vs Templates

As Bjarne Stroustrup points out, C++ is a multi-paradigmed language. It supports many different styles of programs, or paradigms, and object-oriented programming is only one of these (See C++ Classes). Some of the others are structured programming, and generic programming. In the last few years C++ experts like Andrei Alexandrescu, Scott Meyers and Herb Sutter promotes the uses of the generic programming and they qualify it as Modern C++ Design.

Here's what say Andrei Alexandrescu about the Modern C++ design:

Modern C++ Design defines and systematically uses generic components - highly flexible design artifacts that are mixable and matchable to obtain rich behaviors with a small, orthogonal body of code.

Three assertions are interesting in his point of view:

• Modern C++ Design defines and systematically uses generic components.
• Highly flexible design.
• Obtain rich behaviors with a small, orthogonal body of code.

On the other side OOP is very popular, inheritance and RTTI are two powerful mechanisms to design the C++ application and many developers prefer this paradigm in favor of the generic programming approach.

Here's the common definition of inheritance:

In object-oriented programming (OOP), inheritance is when an object or class is based on another object (prototypal inheritance) or class (class-based inheritance), using the same implementation (inheriting from an object or class) specifying implementation to maintain the same behavior (realizing an interface; inheriting behavior). It is a mechanism for code reuse and to allow independent extensions of the original software via public classes and interfaces.

Many C++ experts recommend to not overuse the inheritance and the dynamic polymorphism mechanism. After all what's wrong with the inheritance?

Short answer: Very high coupling. What's important is the methods implemented by the type and not the class kind. This makes the generic programming paradigm more natural and flexible.

Non-Type Template Parameters

(From Linuxtopia)

A non-type template parameter must be an integral value that is known at compile time.

Here is how you can make a fixed-size Stack, for instance, by specifying a non-type parameter to be used as the dimension for the underlying array, as follows.

template<class T, size_t N> class Stack {
T data[N]; // Fixed capacity is N
size_t count;
public:
void push(const T& t);
// Etc.
};

You must provide a compile-time constant value for the parameter N when you request an instance of this template, such as

Stack<int, 100> myFixedStack;

Because the value of N is known at compile time, the underlying array (data) can be placed on the runtime stack instead of on the free store. This can improve runtime performance by avoiding the overhead associated with dynamic memory allocation. Following the pattern mentioned earlier, the name of the class above is Stack<int, 100>. This means that each distinct value of N results in a unique class type. For example, Stack<int, 99> is a distinct class from Stack<int, 100>.

The typename Keyword

There are two uses of typename:

• in the declaration of template parameters, and
• before a qualified dependent type.

The first use, i.e. in the declaration of template parameters, goes like this:

template <typename T> ...

The typename and class keywords can be used interchangeably to state that a template parameter is a type variable, as opposed to a non-type template parameter.

The second use of typename is before a qualified dependent type.

What does qualified mean? A qualified name is one that specifies a scope. For instance, in the following C++ program, the references to cout and endl are qualified names:

#include <iostream>

int main()  {
   std::cout << "Hello world!" << std::endl;
}

What is a dependent name? A dependent name is a name that depends on a template parameter. Suppose we have the following declaration (not legal C++):

template <class T>
class MyClass {
   int i;
   vector<int> vi;
   vector<int>::iterator vitr;

   T t;
   vector<T> vt;
   vector<T>::iterator viter;
};

The types of the first three declarations are known at the time of the template declaration. However, the types of the second set of three declarations are not known until the point of instantiation, because they depend on the template parameter T.

Before a qualified dependent type, you need typename

Look at the following example:

template <class T>
void foo() {
   typename T::iterator * iter;
   ...
}

Without typename, there is a C++ parsing rule that says that qualified dependent names should be parsed as non-types even if it leads to a syntax error. Thus if there was a variable called iter in scope, possibly because a class defined as a static variable, the example would be legal; it would just be interpreted as multiplication, probably not what was intended.

The Rules

Here are the rules for the use of typename, pretty complicated by the way.

• typename is prohibited in each of the following scenarios:

  • Outside of a template definition. (Be aware: an explicit template specialization (more commonly called a total specialization, to contrast with partial specializations) is not itself a template, because there are no missing template parameters! Thus typename is always prohibited in a total specialization.)
  • Before an unqualified type, like int or my_thingy_t.
  • When naming a base class. For example, template <class C> class my_class: C::some_base_type { ... }; may not have a typename before C::some_base_type.
  • In a constructor initialization list.
• typename is mandatory before a qualified, dependent name which refers to a type (unless that name is naming a base class, or in an initialization list).
• typename is optional in other scenarios. (In other words, it is optional before a qualified but non-dependent name used within a template, except again when naming a base class or in an initialization list.)

Again, these rules are for standard C++98/03. C++11 loosens the restrictions

typename in C++11

Until C++11, the keyword typename must only be used inside template declarations and definitions and only in contexts in which dependent names can be used. This excludes explicit specialization declarations and explicit instantiation declarations. Afterwards, the keyword typename can be used even outside of templates, as in:

#include <vector>
int main() {
    typedef typename std::vector<T>::const_iterator iter_t; // OK in C++11
    typename std::vector<int> v; // also OK in C++11
    ...
    return 0;
}

Default Template Parameters

Rules for default template parameters are analogous to those for ordinary function paramenters: only the last n template parameters may have defaults. Also, if a forward declaration of a template class or function has default template parameters, its definition does not. See an example.

Template Parameters That Depend On Other Template Parameters

How would you declare a pointarray class to hold points when you know neither the floating point data type for coordinates nor the dimension of the points, but want to provide defaults for POINT being pair<float,float> ?

template <typename F = float, typename POINT = pair<F,F> >
class pointarray {
  // ...
};

Forward Declaration of Template Classes

template <class T1, class T2, class T3> class MyClass;

Now, if MyClass should have default template parameters, these must not be stated in its definition further down in the file. Thus after:

template <class T1, class T2=type2, class T3=type3> class MyClass;

you would start defining MyClass like this:

template <class T1, class T2, class T3> class MyClass {
  // your implementation
};

Template Specialization

By default, a template gives a single definition to be used for every template argument (or combination of template arguments) that a user can think of. This doesn't always make sense for someone writing a template. I might want to say, If the template argument is a pointer, use this implementation; if it is not, use that implementation, or Give an error unless the template argument is a pointer derived from class MyBase.

[...]

Specialization is a way of specifying alternative implementations for different uses of a common interface.

Bjarne Stroustrup

How do you specialize a template? In the general case, you write:

template <class T1, class T2, ... class Tn>

or possibly avail yourself of the default template argument mechanism:

template <class T1=DEFAULT1, ... class Tn=DEFAULTn>

and then declare your class. Suppose you want to specialize for int in place of the first template parameter. You should type:

template <class T2, ... class Tn>
class MyClass<int, T2,... Tn> {
  // your particular implementation here
};

Or would you like to specialize for T1 being constant? Write

class MyClass<const T1, T2,... Tn> {
  // your particular implementation here
};

...

Or would you like to specialize for T1 being of pointer type? Write

class MyClass<T1  *, T2,... Tn> {
  // your particular implementation here
};

...

ProtoValue<const int> ci(-3);
ci.get() =  9;

#define TEMPLECIALIZE_VALUE

template <class T>
class ProtoValue {
  T val;
public:
#ifndef TEMPLECIALIZE_VALUE
  T& get() {return val;};
  ProtoValue<T>& set(const T & t) {val=t; return *this;};
#endif
  const T& get() const {return val;};
  // constructor:
  ProtoValue(T& t) : val(t) {};
};

template <class T>
class Value : public ProtoValue<T> {
public:
#ifdef TEMPLECIALIZE_VALUE
  T& get() {return ProtoValue<T>::val;};
  Value<T>& set(const T & t) {ProtoValue<T>::val=t; return *this;};
#endif
  // constructor:
  Value(T& t) : ProtoValue<T>(t) {};
};

#ifdef TEMPLECIALIZE_VALUE
template <class T>
class Value<const T> : public ProtoValue<const T> {
public:
  // constructor:
  Value(const T& t) : ProtoValue<const T>(t) {};
};
#endif

const int i = 33;
Value<const int> vi(i);
vi.get() = 22;
// vi.set(11);
cout << vi.get() << endl;

#include <cmath>
template <typename T>
class value {
  T val;
public:
  operator T   () const {return val;};
  operator T & ()       {return val;};
  value(T v) : val(v) {};
};
template <typename S, typename T>
long double operator^(value<S> l, value<T> r) {return powl(l,r);};
// specializations of binary operator^()
float       operator^(value<      float> l, value<     double> r) {return powf(l,r);};
double      operator^(value<     double> l, value<     double> r) {return pow( l,r);};
long double operator^(value<long double> l, value<long double> r) {return powl(l,r);};

typedef value<int> iv;
iv iv1(9), iv2(11);
iv1 += 3;
cout << "iv(9), iv+=3 -> iv1= " << iv1 << endl;
cout << "value<int>(3) + value<int>(4) = " << value<int>(3) + value<int>(4) << endl;
cout << "-2 ^ 10 = " << (value<float>(-2) ^ value<unsigned int>(10)) << endl;
cout << "3 ^ 3 = " << (value<int>(3) ^ value<int>(3)) << endl;

Member Templates

Most class templates are not themselves templates, and can be defined outside the class without further ado.

Take our List template class.

template <typename T>
bool List<T>::empty() const {
  return head == 0; // 'head' is supposed to be a private member etc.
}

What if we want a constructor that takes a pair of iterators?

We declare the constructor like so:

template <typename T>
class List {
public:
//...
template <typename In>List( In begin, In end );
//...
};

and define it outside the class using two template lines of arguments:

emplate <typename T>// this one's for List
template <typename In>// this one's for the member
List<T>::List( In begin, In end ) : head_( 0 ) {
while( begin != end )
push_front( *begin++ );
reverse();
}

As with other function templates, the compiler will perform argument deduction and instantiate the constructor template as needed

This is a common use of constructor templates in the STL to allow a container to be initialized by a sequence of values drawn from an arbitrary source. Another common use of member templates is to generate copy operationlike constructors and assignment operators:

template <typename T>
class List {
public:
  //...
  template <typename S>
  List( const List<S>&that );
  template <typename S>
  List &operator =( const List<S>&rhs );
  //...
};

Notice the waffle words "copy constructorlike" and "copy assignmentlike" in the above description. This is because a template member is never used to instantiate a copy operation; that is, if T and S are the same type above, then the compiler will not instantiate the member template but will instead write the copy operation itself. In such cases, it's usually best to define the copy operations explicitly in order to forestall officious and often incorrect help from the compiler:

template <typename T>
class List {
public:
  //...
  List( const List &that ); // copy ctor
  List &operator =( const List &rhs ); // copy assignment
  template <typename S>List( const List<S>&that );
  template <typename S>
  List &operator =( const List<S>&rhs );
  //...
};
//...
List<float>data4( data ); // copy ctor
data3 = data2; // copy assignment
data3 = data4; // non-copy assignment from member template

Any nonvirtual member function may be a template (member templates can't be virtual because the combination of these features results in insurmountable technical problems in their implementation). For example, we could implement a sort operation for our list...

Template Template Arguments

We want to implement a Stack template class with an underlying container. Naively:

template <typename T, class Cont>
class Stack {
public:
  ~Stack();
  void push( const T &);
  //...
  private:
  Cont s_;
};

A user of Stack now has to provide two template arguments, an element type and a container type, and the container has to be able to hold objects of the element type. This is confusing, error-prone and a lot of extra work.

It would be much move convenient to just write

template <typename T, template <typename> class Cont>
class Stack {
  Cont<T> its_container;
  //...
}

You can even specify a default container, like this:

template <typename T, template <typename> class Cont = std::deque>
class Stack {
  Cont<T> its_container;
  //...
}

Warning:

If we want to have a chance at being able to specialize with a standard container, we have to do the following:

template <template <typename Element, class Allocator> class Cont>
class Wrapper3;

or equivalently:

template <template <typename,typename>class Cont>
class Wrapper3;

(This declaration says that the template must take two type name arguments.

However, the standard container templates (like std::list) may legally be declared to take more than two parameters...

Metaprogramming Through Templates

Metaprogramming is often effected through templates in C++ .

template <unsigned long N>
struct binary
{
  static unsigned const value
    = binary<N/10>::value << 1   // prepend higher bits
      | N%10;                    // to lowest bit
};
template <>                           // specialization
struct binary<0>                      // terminates recursion
{
  static unsigned const value = 0;
};
unsigned const one   =    binary<1>::value;
unsigned const three =   binary<11>::value;
unsigned const five  =  binary<101>::value;
unsigned const seven =  binary<111>::value;
unsigned const nine  = binary<1001>::value;

unsigned binary(unsigned long N)
{
  return N == 0 ? 0 : N%10 + 2 * binary(N/10);
}

template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::value_type value_type;
  ... four more typedefs
};

some_metafunction<Arg1, Arg2>::type

some_function(arg1, arg2)

Compilation of Template Classes

Compiling template classes is not nearly as straightforward as it should be. While the goal of writing a template class is to improve resusability, this is from the perspective of the programmer.

However, for each kind of template instantiation, the compiler generates specific code for that instantiation. For example, consider the SimpleMap template class, which takes two template parameters.

Suppose in main(), you had the following declarations for SimpleMap:

int main() {
   SimpleMap<string, Movie> x;
   SimpleMap<string, Student> y;
   SimpleMap<int, float> z;
}

Each line of declaration refers to a different instantiation. When you instantiate a template class, you are picking classes for the template class. For example, there is code that is created for SimpleMap<string, Movie>, and there is code created for SimpleMap<string, Student>, and there is also code created for SimpleMap<int, float>.

While most of the code is very similar, each is specific for the two types that the class has been instantiated to. For example, the class methods might refer to the output operator method. The code for printing a Movie, Student, and float are all different.

If you think this is wasteful, you are right. You write template code because you want to avoid writing the same class over and over, but the only change between the classes is the type. You would think that the compiler would somehow try to factor out the common code. For efficiency reasons, it does not do that.

Instead, it creates code for each kind of instantiated type. This is quicker, but it means that for every instantiation of a template class, the compiler must generate new code. If you have N different kinds of instantiations, you will have N different copies of the SimpleMap code, each tailored to the types to which it has been instantiated.

#include <string>
#include "findMin.cpp"    // still include implementation file
#include "SimpleMap.cpp"  // still include implementation file
#include "Movie.h"   // include header file for non-template classes
#include "Student.h" // include header file for non-template classes
// Specific instantiations for function template, findMin
template string  findMin(string arr[], int size);
template Movie   findMin(Movie arr[], int size);
template Student findMin(Student arr[], int size);
// Specific instantiations for class template, SimpleMap
template class SimpleMap<string, Movie>;
template class SimpleMap<string, Student>;
template class SimpleMap<int, float>;

template <typename F>
class A {
  template <typename G> void foo();
};
template <typename F>
void gee();

template class A<float>;
template class A<double>;
template class A<long double>;
template void gee<float>();
template void gee<double>();
template void gee<long double>();

template void A<float>::foo<float>();
template void A<float>::foo<double>();
template void A<float>::foo<long double>();
template void A<double>::foo<float>();
template void A<double>::foo<double>();
template void A<double>::foo<long double>();
template void A<long double>::foo<float>();
template void A<long double>::foo<double>();
template void A<long double>::foo<long double>();