Posts C++ notes on function and class templates
Post
Cancel

C++ notes on function and class templates

Consider a function called swap that we can use as follows:

  • calling swap(i, j) places:
    • the value that was in i into j
    • the value that was in j into i

swap is a meaningful operation for objects of many different types. So, it’s a good candidate for function overloading. For example:

1
2
void swap(int &a, int &b);
void swap(string &a, string &b);

For each of these calls, the compiler selects the function whose parameters are the best match for the arguments:

1
2
3
4
5
6
int i, j;
string s, t;

swap(i, j); // calls swap(int &, int &)
swap(s, t); // calls swap(string &, string &)
swap(i, s); // error: no matching function found

So, we would have implementations like:

1
2
3
4
5
6
7
8
9
10
11
void swap(int &a,int &b) {
    int temp{a};
    a = b;
    b = temp;
}

void swap(string &a, string &b) {
    string temp{a};
    a = b;
    b = temp;
}

So, function overloading lets you use the same name for two or more functions. It’s appropriate when those functions perform the same logical operation, but on operands of different types. This can yield libraries that are easier to use. However, overloading, does not spare the effort of writing nearly identical code for each nearly identical function. Hence, function templates.

A function template is a generalization of an algorithm. It is not an actual function. Rather, it’s a single declaration that can generate declarations for similar, but distinct functions. Each generated function implements the algorithm for operands of different types.

So, using our swap as an example:

1
2
template <typename T>
void swap(T &a, T &b);

This is a function template declaration. It provides the compiler enough information to generate calls to swap functions. However, there is no function body.

The corresponding function template definition will look something like:

1
2
3
4
5
6
template <typename T>
void swap(T &a, T &b) {
    T temp {a};
    a = b;
    b = temp;
}

This provides the compiler with enough information to generate a function body. When used with templates < and > are called angle brackets.

In the case of a function template, there are both:

  • a template parameter list - template <typename T>
  • a function parameter list - (T &a, T &b)

The type parameter T is a placeholder for a type argument. Argument substitution happens at compile time. The function parameter a and b are placeholders for argument expressions. Depending on the context the compiler will either pass the arguments at compile time or the program will pass the arguments at run time.

Within a template definition, a template type parameter behaves much like any other type identifier. In particular, a template type parameter has a scope.

The act of generating a function definition from a template is called template instantiation. A function definition generated from a function template is an instantiated function. However, it’s common to call it an instantiation.

A program can all an instantiated function by using the instantiations name as the function name in a call. For example, swap<int> is the name of the instantiated function that swaps two ints:

1
2
3
int i, j;
...
swap<int>(i, j);

To satisfy the call, the compiler automatically instantiates a definition for a function declared as:

1
void swap<int>(int &a, int &b);

A compiler doesn’t instantiate duplicate function definitions. Rather, it instantiates a single function definition for all calls to a particular instantiation:

1
2
3
4
5
6
int i, j;
string s, t, u, v;
...
swap<string>(s, t); // triggers instantiation
swap<string>(u, v); // uses previous instantiation
swap<int>(i, j); // triggers different instantiation

A template can have more than one template parameter:

1
2
template <typename S, typename T>
S find(S first, S last, T const &v);

An instantiation of this template requires two type arguments:

1
i = find<double const *, double>(b, e, x);

You can declare a template type parameter using the keyword class instead of typename:

1
2
template<class T> // means the same as <typename T>
void swap(T &a, T &b);

This swap will still swap objects of class or non-class types.

The keywords class and typename are not interchangeable elsewhere in C++.

A class template is a generalization of an object type. It is not an actual type. Rather, it’s a single declaration that the compiler can use to generate similar, yet, distinct class declarations. A class template can take the place of many classes with similar names and nearly identical attributes.

Consider a non-template class for rational numbers:

1
2
rational r1 {1, 3}; // r1 = 1/3
rational r2 {4, 5}; // r2 = 4/5

This non-template class implements a rational number as a pair of signed long integers. The class definition looks something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
class rational {
public:
    rational();
    rational(long n);
    rational(long n, long d);
    ...
    rational &operator+=(rational const &ro);
    rational &operator -=(rational const &ro);
    ...
private:
    void reduce();
    long num, den;
};

An application might want fractions with different precision. We would have to rename the class rational to something like long_rational or short_rational and so on. We might want to define an unsigned version too.

Instead, consider the template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
class rational {
public:
    rational();
    rational(T n);
    rational(T n, T d);
    ...
    rational &operator+=(rational const &ro);
    rational &operator-=(rational const &ro);
    ...
private:
    void reduce();
    T num, den;
};

The compiler automatically instantiates class definitions as needed. For example, just use rational<T> with a type argument substituted for T.

A class definition generated from a class template is an instantiated class. For example, rational<long> is the type name for an instantiated class.

We can use the name of a class template instantiation anywhere that we can use any other type name:

1
rational<long> rl {10}; // rl = 10/1

If we need to type out rational<...> in many places, we can typedef it:

1
2
3
4
5
typedef rational<int> irat;
// or the newer
using irat = rational<int>;

irat ri {4, 5}; // ri = 4/5

A container class is an object that holds other objects. For example an array or a linked list. Implementing a container class as a class template with a type parameter for the element type makes sense. The STL provides various container class templates including:

  • list<T> - a doubly-linked list of T objects
  • vector<T> - a variable-length array of T objects
  • set<T> - an ordered set of T objects

A template argument can be the name of another template instantiation. For example, ratios in this case is a list with elements of type rational<int>:

1
list<rational<int> > ratios;

Note the space between the closing angle brackets. It turns out that in C++03 you had to leave the space between consecutive angle brackets:

1
list<rational<int>> ratios; // error in C++03, okay since C++11

A C++03 compiler would have interpreted >> as a shift operator. C++11 fixed this.

The definition for class template member functions can appear outside the class definition:

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T> // begin class definition
class rational {
public:
    rational(T n); // member declared
    ...
}; // end class definition

template <typename T> // begin member definition
rational<T>::rational(T n):
    num {n}, den{1} {
        ...
    } // end member definition

Within the scope of class template rational<T>, you can usually refer to the class member as either rational or rational<T>. That is, the <T> after the class template name is optional. But only in the scope of the class template.

In a member declaration of a class C appearing outside C, the scope of C begins after C:: and ends at the end of the declaration. This is true for class templates as well.

1
2
3
4
5
template <typename T>
rational<T> &
rational<T>::operator+=(rational<T> const &ro) {
    ...
}

Notice that <T> is not optional outside the class template scope, but is optional within the arguments due to the scope.

Additionally, we must omit <T> immediately after ::. If placed outside the class template, definition for rational<T>’s single-parameter constructor looks like:

1
2
3
4
5
template <typename T>
rational<T>::rational(T n):
    num {n}, den{1} {
        ...
    }

If rational<T> has a non-trivial destructor, it would look like:

1
2
3
4
template <typename T>
rational<T>::~rational() {
    ...
}

Recommendation: instead of memorizing all these rules, just write C<T> as just C everywhere inside the scope of a class template C<T>.

We can avoid this syntactic complexity by just defining member functions inside the class template definition:

1
2
3
4
5
6
7
8
9
template <typename T>
class rational {
public:
    ...
    rational(T n):
        num {n}, den{1} {
        }
    ...
};

A class template can have static data members:

1
2
3
4
5
6
template <typename T>
class gadget {
    ...
    static unsigned long counter;
    ...
};

Each instantiation of gadget<T> gets a distinct instance of counter. However, this declaration for counter is not a definition.

In C++17, a static data member can be defined within its class template definition by using the keyword inline:

1
2
3
4
5
6
template <typename T>
class gadget {
    ...
    inline static unsigned long counter = 0;
    ...
};

This permits to put the definition here and the compiler deals with possibilities of duplicates. This ability actually predates C++11, however the definition for a static data member must appear outside its class definition if not using the C++17 method. THe definition for gadget<T>’s counter would look like:

1
2
template <typename T>
unsigned long gadget<T>::counter = 0;

A class template can have members that are types:

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
class list {
public:
    class iterator; // member type declaration
    ...
};

template <typename T> // member type definitions
class list<T>::iterator {
    ...
};

Again, it’s often simpler to define the member type inside the class template definition:

1
2
3
4
5
6
7
template <typename T>
class list {
public:
    class iterator {    // member type definition
        ...
    };
};

Outside the class, we refer to the list’s iterator type by its fully-qualified name. For example, this will declare i as an object of type iterator on a list of string:

1
2
3
4
for (list<string>::iterator i = ls.begin();
    i != ls.end(); ++i){
        ...
    }

Loops like this were the motivation for auto as a type specifier and range-for statements.

A template argument can be an expression rather than a type. For example, the STL provides a class template bitset<N>. It represents a fixed-size sequence of bits. For example:

1
2
bitset<32> b1; // a sequence of 32 bits
bitset<128> b2; // a sequence of 128 bits

The class template definition looks, in part, like:

1
2
3
4
template<size_t N>
class bitset {
    ...
};

<size_t> N is the template parameter list, N is a template non-type parameter. A non-type parameter can have an integral, enumeration, pointer, pointer-to-member, or reference type.

With non-template functions and classes, we typically place the declarations in headers and definitions in source files. Templates are a bit different. We typically place all template declarations, including definitions, in headers. We rarely place template declarations in source files.

C++ often lets you omit the angle-bracketed template argument list from a call to a function template. That is, the call can use just the template name as the function name:

1
i = abs(j); // abs, not abs<?>

In this case, teh compiler performs template argument deductions. It deduces the template argument(s) from the function call argument(s). Template argument deduction makes a function template look more like an unbounded set of overloaded functions, as in:

1
2
template <typename T>
T abs(T x);

C++ can deduce the type argument for each of these calls:

1
2
3
4
5
int i, j;
float f, g;
...
j = abs(i); // calls abs<int>(i)
g = abs(f); // calls abs<float>(f)

Compilers can deduce template type parameters for function parameters with non-trivial forms. For example, the swap template has two function parameters:

1
2
3
4
5
6
template <typename T>
void swap(T &a, T &b) { // T &, not just T
    T temp(a);
    a = b;
    b = temp;
}

Compilers can not deduce template type parameters from return types alone, as in:

1
2
3
4
5
template <typename T>
T f();
...

int i = f(); // error - can't deduce type

Here, we must specify the type argument explicitly, as in:

1
int i = f<int>(); // ok if stated explicitly

Prior to C++17, type argument deduction applied only to function templates, not to class templates:

1
2
3
rational<int> r1, r2;
swap(r1, r2); // OK
rational<int> r3 (r2); // OK

Prior to C++17, type argument deduction applied only to function templates, not to class templates, as in:

1
2
3
4
rational<int> r1, r2;
swap(r1, r2); // OK
rational<int> r3 (r2); // OK
rational r4 (r1); // error until C++17

In C++17, it deduces rational’s type argument to be int.

The compiler is limited in what it can do when it first encounters a template definition such as:

1
2
3
4
template <typename T>
T foo(T x) {
    ...
}

It can’t generate code for an instantiation. It doesn’t know what T is yet. For the most part, the compiler just scoops up the template and stores it in the symbol table. On this first reading, the compiler can’t detect all possible errors. Nevertheless, it still tried to do as much checking as it can, so it can report error as early as possible.

Thus, a compiler processes each template definition in two phases. The first phase occurs when the compiler parses the template declaration. This happens just once for each template. Each second phase occurs when the compiler instantiates the template for a particular combination of arguments. This happens at each instantiation.

All of the STL container class templates, including the string class template, define member types. Some also define member constants. For example, all standard container class templates define a member type called size_type. The standard string class template, basic_string<T> also defines a constant npos. We need the keyword typename to use them.

For example, consider this imaginary function template. It’s intended to work with any class with string-like behavior:

1
2
3
4
5
template <typename T>
T::size_type munge(T const &a) {
    T::size_type *i(T::npos);
    ...
}

This template works only for a type T that has size_type and npos as members. So, again, the compiler typically encounters this function template definition to any instantiation of the template. It knows only that T represents a type. It does not know that T::size_type is supposed to be a type or that T::npos is supposed to be a constant. It can’t know this until it knows the argument substituted for T in a given instantiation.

Suppose T::size_type is a type and T::npos is a type. Then what is:

1
T::size_type *i(T::npos); // ?

It’s a function declaration of return type T::size_type and parameter list T::npos. It declares i as a function with an unnamed parameter of type T::npos and returning a pointer to T::size_type.

Now, suppoes T::size_type is a type and T::npos is a constant, object or function. Then what is:

1
T::size_type *i(T::npos); // ?

Now this is an object definition. It declares i as an object of type T::size_type* initialized with the value of T::npos.

Now, even further, suppose that T::size_type is not a type and T::npos is not a type. Then what is:

1
T::size_type *i(T::npos); // ?

Then this is actually trying to multiply T::size_type by *i(T::npos). Furthermore, the right-hand side here could be a function call or a function-like cast.

A name appearing in a template whose meaning depends on one or more template parameters is a dependent name. In the munge template, T::size_type and T::npos are dependent names. They depend on template type parameter T. A dependent name may have a different meaning in each instantiation of the template. According to the C++ standard, a name used in a template declaration that is dependent on a template parameter is assumed not to be a type unless the name is qualified by the keyword typename. So, the definition should actually look like this:

1
2
3
4
5
template <typename T>
typename T::size_type munge(T const &a) {
    typename T::size_type *i(T::npos);
    ...
}

Here, we can not use the keyword class, only typename. So the first reading will occur and the compiler will assume that T::size_type is a type.

This post is licensed under CC BY 4.0 by the author.

Recent Update

    Contents