Template functions and classes

If polymorphism is one way of writing functions (and classes) that can abstract over different types of things, then templates are the other way. Suppose we were going to write the absolute value function, but we wanted to write versions for float and for int:

float abs(float x) {
  return x < 0 ? -x : x;
}

int abs(int x) {
  return x < 0 ? -x : x;
}

Well that’s not good, we’re writing the exactly same code twice; only the types are different. We can’t use polymorphism here, because int and float aren’t classes: there is no number base class from which they both inherit. The similarity between the two is not a result of inheritance, but rather a kind of coincidence, that int and float both happen to support the same set of operations (comparision, artihmetic). What we’d like is if there was a way to instruct the compiler to do the copy-and-pasting that we did above to write the two functions. In fact, there is:

template<typename T>
T abs(T x) {
  return x < 0 ? -x : x;
}

The new part is template<typename T>. This effectively says that “T stands for the name of a type, in the following definition” — here, the following definition is the definition of the abs funciton. Within the definition of abs we can use T as if it was a type, like int or float or whatever. When we go to actually use abs, like this:

int x = -12;
int y = abs(x);

C++ looks at the argument to abs (x) to see what type it is. Here, x is an int, so that means that T in the template definition above must be int, so it expands the template, by replacing every T with int. This gives a version of abs that is specialized for ints, which is what we want, so C++ uses that and goes along its way. Effectively, C++ copies our code and adds an int-specific overload:

int abs(int x) {
  return x < 0 ? -x : x;
}

If, later on, we do

float a = 4.0;
float b = abs(a);

C++ does the same thing again, except that it first checks the type of a (float) against the int-specific version it made previously, to see if it works, but it doesn’t, so it falls back to the template definition. This time it discovers that T should be float, makes a copy of abs with all the T‘s replaced by float, and then carries on.

Note that T is only a type inside the definition of abs: templates only “cover” a single definition at a time. Something like this not only won’t work, it doesn’t make sense:

template<typename T>
T f(T x) { ... }

T g(T x) { ... }

We also don’t know anything about T: it could be a primitive type like int, a pointer type like char*, a reference, a class type, anything really. The only restrictions on it are those implied by what we do with it: the operations that we do on values of type T define what types can be validly substituted for T.

When we write a template function, it’s a good idea to take a look at it and figure out what the type has to be able to do:

template<typename T>
T abs(T x) {
  return x < 0 ? -x : x;
}

What are all the things we are doing with x here?

Comparing with 0: x < 0. This implies that the type T must have operator<(T, int) defined.
Negation: -x means that operator-(T) must be defined.
We are implicitly copying x, when we take it as an argument, and when we return it, so T must be copyable.

Template specialization is really kind of dumb: C++ doesn’t know, or care, anything about the types that eventually are used to specialize the function. When you actually use abs with some specific type, that’s when it will discover whether or not it actually works:

string name = "Hello";
string what = abs(name);

This will give an error, but an error inside abs, explaining that you can’t compare a string to 0. This is one disadvantage to templates: errors aren’t caught when you write them, only when you use them. You can write totally crazy template code:

template<typename T>
T f(T a, int x) {
  return T + x * "Hello"; 
}

and C++ won’t complain until you actually go to use it:

float x = f(2.0);

The other thing to remember about templates is that they don’t define anything. A template definition is just a cookie-cutter from which “real” definitions will later be created, when you actually use the function and C++ is able to figure out what types should actually be used. This means that templates must be defined before they are used: there is no such thing as a declaration for a template function, the compiler needs the whole function before you can use it. For this reason, template definitions are usually placed in header files, so that they are “defined” at the point where they are included (which is usually at the top of a source file).

We can define template function that have more than one template parameter. To see why this might be useful, let’s think about writing a template version of the + operator: + works on ints, floats, and strings. So to start with, we might write:

template<typename T>
T add(T a, T b) {
  return a + b;
}

But this is actually overly restrictive: it requires that both parameters be the same type. If you do something like

int x = 1;
float y = 2;
float z = add(x,y);

you’ll get a message, because x and y are not the same type. To allow the two parameters to be different types, we can do:

template<typename A, typename B>
... add(A a, B b) {
  return a + b;
}

But what about the return type? If A and B are the same type, then the return type will be that. But what if we have int + float? Then it will be float, but remember that we don’t know anything about the types that will eventually be used for A and B. What we really need is a third parameter, for the return type:

template<typename A, typename B, typename C>
C add(A a, B b) {
  return a + b;
}

This allows for maximum flexibility: A and B can be different types, and the result of adding them together can even be different from either. (Remember that we can overload operator+ with any types we want: nothing says that a + b will return something that is of either type A or type B!) The main problem with this is that in order to use it, you now have to manually write the result type:

float x = add<float>(1, 2.4);

C++ can deduce only the types of the arguments, not the return type. We can, however, give C++ some hints as to the return type. The return type of a + b if a and b have different types is called the “common type” of a and b, the type which they could both be converted to. We can get the common type using a type trait:

#include <type_traits>

template<typename A, typename B>
common_type_t<A,B> add(A a, B b)
{
  return a + b;
}

common_type_t is a “type function”. It takes one or more types as (template) parameters and then “returns” their common type. Using this definition, we can use the function naturally:

float x = add(12, 3.4);

common_type_t<float,int> is float, so we don’t need to specify it manually.

Another, newer way to do this is to use a trailing return type. Normally, the return type comes before the function name and arguments, but we can also write it afterwards: this

auto abs(int x) -> int
{
  return x < 0 ? -x : x;
}

is exactly the same as

int abs(int x) {
  return x < 0 ? -x : x;
}

Trailing return style is useful in template functions, where the return type is not fixed, but is computed somehow from the parameters.

template<typename A, typename B>
auto add(A a, B b) -> decltype(a + b)
{
  return a + b;
}

Because C++ hasn’t seen the parameters yet, we can’t put the return type first; it has to go after the parameter list. On the other hand, C++ needs something in the spot where the return type should go, to let it know that this is a function, so we use the keyword auto.

The return type in this case is given by another type-level function, decltype. Decltype takes as its parameter an expression, it “returns” the type that expression would have if it were evaluated. Note that decltype doesn’t actually do the math of a + b; it just asks what would happen if that was done?

In this case, the decltype directly wraps up the expression in the return. It seems like C++ should be able to do this for us, and as of C++17, it can. You can write:

template<typename A, typename B>
auto add(A a, B b)
{
  return a + b;
}

and C++ will use decltype automatically to figure out the correct return type.

We’ve written a swap function before, using both references and pointers, to exchange two values:

void swap(int& x, int& y) {
  int t = x;
  x = y;
  y = t;
}

We can use templates to make a totally generic version of this, that will work on any types:

template<typename T>
void swap(T& x, T& y) {
  T t = x;
  x = y;
  y = t;
}

What does the type need to be able to do in order this to work?

We make a copy of x, so it needs to be copyable. (Sometimes this is called “copy constructible”)
We assign x = y and then y = t, so it needs to be “assignable”. Usually this is called “copy assignable”.

In this case, it makes sense to require both arguments to be the same type: it’s not possible to (e.g.) swap the values in int and float variables without losing data, and swap should not silently lose data.

We can enforce the restriction that T be “copyable” using type traits, specifically enable_if_t. The result looks like this:

template<typename T>
enable_if_t<
  is_copy_assignable_v<T> && is_copy_constructible_v<T>,
  void
>
swap (T& x, T& y) {
  T t = x;
  x = y;
  y = t;
}

The enable_if_t replaces the return type void and it takes two (template) parameters:

The first is a bool expression which should be true when we want to “enable” the function, and false when we want it to be “disabled”. In this case, we want the function to be enabled exactly when T is both copy-constructible and copy-assignable, which we can test for by using the type traits is_copy_assignable_v and is_copy_constructible_v.
The second parameter is the type we want the enable_if to “return” when the expression is true.

What type does enable_if_t “return” if the expression is false? Unlike normal runtime functions, which must always return a value, it’s OK for template type functions to sometimes return a type and sometimes return nothing. If enable_if_t returns nothing, it’s not necessarily an error, it just means that this particular overload for swap doesn’t work, so the compiler ignores it.

When we write something like swap(x,y); the compiler builds a list of all possible functions named swap which could possibly be called (that is, all the ones with two parameters). This includes all the overloaded functions named swap, but also any template functions. It then uses the types of x and y to start eliminating functions from this list: it eliminates any overloads where the types don’t exactly match. For templates, it does something more elaborate: it instantiates the template, and then if the result is not valid code, it eliminates it from the list but does not give an error. It only gives an error in two circumstances:

If, after eliminating everything that doesn’t work, the list is totally empty. This would be the case if we tried to swap two things which just couldn’t be swapped (an int and string, for example).
If, after eliminating everything, there is more than one thing still left, with none more specific than any other. Then, not knowing which you want, C++ gives an error saying that the function call is ambiguous.

What C++ wants to end up with is one candidate which applies to function call.

The property that templates which expand into invalid code do not cause an error but simply “opt themselves out” of consideration is called Substitution Failure Is Not An Error or SFINAE for short. It’s a powerful property which lets us write functions like swap which apply only to certain types, but leave things open for other types to add their own extensions.

Template classes

I said that templates can be applied to a single “definition”, but I didn’t say what kind of definition. Can we create template classes? Yes, we can. Let’s create a template owner class:

template<typename T>
class owner {
  ...
  vector<T> pets;
};

When we create an owner we have to explicitly say what type to use for T, like this:

owner<dog> jsmith;
owner<cat> frodgers;

Because we have to give a single type for T, this implies that this version of owner can only be used for people with a single kind of pet: you can’t mix and match cats and dogs, unless you do something like this:

owner<animal*> aclifton;

How do template classes work? The same way as template functions: C++ takes the type you give, replaces all the occurrences of T with that type, and then expands out a new copy of the class specialized for the given type. That is, the first time you use owner<cat> C++ creates a specialized version of owner that only works on cats. (If you later create other cat-owners it will reuse this definition.)

We’ve actually been using a template class all along: vector! When we write vector<int> we are asking C++ to specialize the template class vector for ints. It either creates or uses an existing specialized version of vector that only works on ints.

Because the template extends over the entire class definition, this means that we can use T anywhere inside the class:

template<typename T>
class owner {
  public:
    void add(T pet) {
      pets.push_back(pet);
    }

  private:
    vector<T> pets;
};

If we want to define a method outside the class, then it’s definition looks a little different. Let’s add a method to check whether an owner owns a particular pet:

template<typename T>
class owner {
  public:
    ...
    bool owns(T pet);
    ...
};

template<typename T>
bool owner<T>::owns(T pet) {
  for(T p : pets)
    if(p == pet)
      return true;

  return false;
}

The method owns is part of the owner class, but the “full” name of the owner class is actually owner<T>. There’s no such thing as just owner. And T isn’t a type on its own, outside of a template definition, so we have to add template<typename T> to introduce it.

Templates add yet another tool to our collection of DRY abstractions. When should you use templates, vs. inheritance and virtual methods? Well, it depends on several factors:

Are all of the things you need to abstract over classes? You can’t use inheritance to abstract over built-in types like int.
Are all of the things you need to abstract over subclasses of a particular parent class? You can only use inheritance within an inheritance chain.
Are all of the things you need to abstract over under your control? You can’t force classes that you didn’t write to inherit from your parent class.
Do you need maximum speed? Templates are somewhat faster at runtime than inheritance/virtual methods, because the compile generates a specialized version of your code for exactly the types you use.
Do you want a smaller program? Because templates are basically just compiler-performed copy and paste, using lots of templates will make your programs bigger.
Do you mind compiler errors? Templates can be responsible for some complete insane error messages, because the errors aren’t detected when you write the template, but much later, when you actually go to use it. Even worse is if you write a template function, that uses another template function: you’ll get the error deep inside the innermost function, rather than the function you actually called! Using enable_if to preemptively disable things that you know won’t work can help with this.

Example: rewriting our set data structure using templates

template<typename T>
class set {
  ...
  using value_type = T; // Type member
};

An aside: const-correctness. We haven’t used it very much, but you can declare variables as const to basically tell C++ that you’re never going to modify what’s in it, and it will enforce that, giving an error message if you try to change it:

const int x = 1; // Only time we can set x's value
x = 2;           // Compiler error

That works fine as long as you are dealing with the built-in types, but for our classes, C++ needs a little help to know whether a given operation is “const safe” or not. For example:

class thing {
  public:
    void print() { 
      ...
    }
};

const thing a;
a.print();    // Allowed, or not?

C++ doesn’t know whether thing::print is safe to use on const things, or will it try to change the thing in question. Consequently, we have to tell C++ that print is const-safe:

class thing {
  public:
    void print() const { 
      ...
    }
};

The keyword const after the method parameter list tells C++ that print does not modify the object it is called on, and thus it is OK to use print on const things. You can even overload a method on const vs. non-const:

class thing {
  public:
    void print() const { cout << "Const"; }
    void print()       { cout << "Mutable"; }
};

thing a;       a.print(); 
const thing b; b.print();

This is useful because sometimes a method can operate more efficiently if it is allowed to modify the object in some insignificant way.

Interestingly enough, you can have const members of a class:

class thing {
  public:
    const int x = 1;
};

Having a member that always has the same value isn’t particularly interesting, but what else could we do, this is obviously not allowed:

class thing {
  public:
    thing(int xx) {
        x = xx; // Error!
    }

    const int x;
};

If you want to initialize const members of a class, you can do it using the parameters to the constructor, but you have to do it in a special way:

class thing {
  public:
    thing(int xx) : x(xx) { }

  const int x;
};

The : x(xx) is called a member initializer list and it’s used for initializing the data members of a class which are either const or references. Both const and & have the property that they can’t be changed after they are created, so you have to do something special to have them as members of classes.

Modifying set to be const-correct…

Functional Programming

Functional programming is a somewhat advanced technique that basically involves treating functions like data, objects that can be passed around. Let’s take a look at an example.

Suppose we have a vector<int> vs and we want to square all the elements:

for(int& v : vs)
  v = v*v;

Not too hard, no? But there are lots of other things we might want to do with a vector, lots of operations that fit into the template of “do this to all the things in this vector”. We can write a higher order function that encapsulates this idea:

#include <functional>

int square(int x)    { return x*x; }
int increment(int x) { return x+1; }
int halve(int x)     { return x/2; }

void modify(vector<int>& vs, function<int(int)> f) {
    for(int& v : vs)
        v = f(v);
}

To use this, we can do something like this:

vector<int> data = { ... };
modify(data, square);    // Squares all values
modify(data, increment); // Increments all values
modify(data, halve);     // Halves all values

Let’s think about the different kinds of vector-operating loops we’ve written and look at how they could be abstracted:

Modify a vector in place (above)
Create a new vector from an old one (e.g., by squaring all the elements)
Filter a vector by removing all the elements that don’t satisfy some criteria.
Test whether all/any elements of a vector satisfy some criteria.
Find the first element of a vector that satisfies a criteria and return its location.

Taking each of these in turn:

Creating a new vector is a simple change to modify above, let’s call it rewrite:

 vector<int> rewrite(vector<int> input, function<int(int)> f) {
     vector<int> result;
     for(int i : input)
         result.push_back(f(i));

     return result;
 }

Filtering a vector. Here, we have to decide whether we want to do this “destructively” (modifying the original vector), or “functionally” (creating and returning a new vector). Creating a new vector is generally more useful, as it lets us decide what to do with the output:
```
 vector<int> filter(vector<int> input, function<bool(int)> p) {
     vector<int> result;
     for(int i : input)
         if(p(i))
            result.push_back(i);

     return result;
 } 
```

Testing all/any:

 bool all(vector<int> input, function<bool(int)> p) {
     for(int i : input)
         if(!p(i))
             return false;

     return true;
 } 

 bool any(vector<int> input, function<bool(int)> p) {
     for(int i : input)
         if(p(i))
             return true;

     return false;
 }

Find:

 int find(vector<int> input, function<bool(int)> p) {
     for(int i = 0; i < input.size(); ++i)
         if(p(input.at(i)))
             return i;

     return -1;
 }

The interesting thing with functional programming is that we can “chain” different operations together:

bool odd(int x) { return x % 2 == 1; }

vector<int> r = rewrite(rewrite(filter(vs,odd), square), increment);

This also gives us an interesting use for classes that override the () operator. Here’s a “function” that counts how many times a given int occurs:

class counter {
  public:
    counter(int t) {
        target = t;
    }

    int count() { return c; }

    int operator() (int x) {
        if(x == target)
            c++;

        return x; // Leave values unchanged
    }

  private:
    int target, c = 0;
}

counter c{2}; // Count how many times 2 occurs

modify(vs, c);
cout << c.count(); // How many times?

Lambda functions

Having to write one-off functions like this is a little cumbersome, so we can make use of a new (C++11) C++ feature that lets us write unnamed functions, right where we need them. We can rewrite

modify(vs, square);

into

modify(vs, 
  [](int x) { return x*x; }
);

That’s kind of a soup of punctuation in the middle, so let’s take it apart.

[](int x) { return x*x; } is a lambda expression, sometimes called a lambda function (for historical/mathematical reasons). Its “value” is a function. The type of this function in particular is function<int(int)> as we saw before; i.e., a function that takes a single int parameter and returns an int.
[] the square brackets at the beginning serve two purposes: they tell C++ that this is a lambda, and they enclose the “capture list”. Normally, a lambda has no access to the variables in the enclosing scope (e.g., the lambda above cannot see or use vs) but you can put things here to allow the lambda to access them in various ways.
(int x) is the parameter list of the lambda, just like for a normal function.
{ return x*x; } is the body of the lambda, just like for a normal function.
This lambda has no return type: C++ will figure it out by looking at the return in the body of the lambda (x is an int, therefore x*x is an int and thus return x*x returns an int). If you want to be explicit about the return type of a lambda, you write it like this:
```
 [](int x) -> int { return x*x; }
```

Note that you can save a lambda in a variable and use it later:

function<int(int)> sq = [](int x) { return x*x; } ;

cout << sq(2); // Prints 4

If we rewrite our above “chaining” example to use lambda, we no longer need the separate functions:

vector<int> r = rewrite(
                  rewrite(
                    filter(vs, [](int x) { return x % 2 == 1; }), 
                    [](int x) { return x*x; }), 
                  [](int x) { return x+1; });

We can even write functions, that construct and return new functions:

function<bool(int)> negate(function<bool(int)> f) {
  return [](int x) { return !f(x); }
}

function<bool(int)> even = negate(odd);

You can even write template higher order functions:

template<typename T>
void modify(vector<T> vs, function<T(T)> f) {
    for(T& v : vs)
        v = f(v);
}

This will let us modify a vector containing anything, not just ints!