License : Creative Commons Attribution 4.0 International (CC BY-NC-SA 4.0)
Copyright : Frédéric Pennerath, CentraleSupelec
Last modified : February 14, 2024 14:00
Link to the source : mechanism.md

Table of contents

The basics of templates: what, why, when and how

What are templates at a glance?


A first unformal definition

Templates provide the ability to write skeletons of source code that can easily be reused later in various software projects. reconciling three assets:

  • Code reusability

  • Strong typing (robustness at runtime)

  • Performance (at a level that can only be achieved with strong typing)


You already know some examples of template instances:

#include <vector>
#include <unordered_map>
#include <tuple>
#include <algorithm>
...

int main() {
  // Let's create a vector of int.
  std::vector<int> V1;    // Cool!

  // This is strongly typed (compare to Python lists)
  V1.push_back(1); // OK
  V1.push_back("An array of char"); // NOK

  // Can we do the same with pairs of double & boolean.
  std::vector<std::tuple<double, bool>> V2; // Super cool!
  
  // And a vector of hash tables mapping my own class Lecture with string futures
  std::vector<std::unordered_map<Lecture,std::future<std::string>>> V3; // Awesome!!!
  
  // But you even used templates without knowing about them:
  std::sort(V1.begin(), V1.end());
  
  // As this is equivalent to
  std::sort<std::vector<int>::iterator>(V1.begin(), V1.end());
}

How can we define templates?

You already know how to use existing templates but what about defining your own templates?

Let’s take the simple example of class Complex where you want to store real and imaginary parts in an arbitrary numerical type (float, int,double, etc).

// This is a class template parameterized by a type (the scalar type to store real and imaginary parts)

template <typename Scalar> class Complex {
  Scalar re, im; // Now real and imaginary parts have an unknown type
public:
  Complex(Scalar re, Scalar im = Scalar{}) : re(re), im(im) {}
  Complex(const Complex&) = default;
  
  Complex operator*(const Complex&) const;
};

// Example of method definition for a class template

template <typename Scalar>
Complex<Scalar> Complex<Scalar>::operator*(const Complex& other) const {
  return Complex(re * other.re - im * other.im, re * other.im + im * other.re);
}

int main() {
  {
    Complex<double> j { 0., 1. };
    Complex<double> c = j * j; // Great, this works!!!
  }
  {
    Complex<int> j { 0, 1 };
    Complex<int> c = j * j; // Great, this works again!!!
  }

  {
    // Complex<std::string> j { "0", "1" }; // These two lines have been commented as they fail to compile.
    // Complex<std::string> c = j * j; //Can you see why?
  }
}

It is important to distinguish:

How templates work?

A kind of search and replace

Let’s first compile and check the occurrences of class Complex in the symbol table:

$ g++ -std=c++20 complex.cpp -o main
$ nm ./main | c++filt | grep Complex | sort -u

00000000000011ee W Complex<double>::Complex(double, double)
0000000000001222 W Complex<double>::operator*(Complex<double> const&) const
00000000000012ea W Complex<int>::Complex(int, int)
0000000000001312 W Complex<int>::operator*(Complex<int> const&) const

More graphically this looks like:

Symbol table

We observe few things:

What happens:

Compiler do a “kind of” search and replace to produce the following source code.
Important: This process is triggered when templates are instantiated (this is called implicit instantiation).

class Complex<double> {
  double re, im;
public:
  Complex<double>(double re, double im = 0.) : re(re), im(im) {}
  Complex<double> operator*(const Complex<double>& other) const;
};

Complex<double> Complex<double>::operator*(const Complex<double>& other) const {
  return Complex<double>(re * other.re - im * other.im, re * other.im + im * other.re);
}


class Complex<int> {
  int re, im;
public:
  Complex<int>(int re, int im = 0.) : re(re), im(im) {}
  Complex<int> operator*(const Complex<int>& other) const;
};

Complex<int> Complex<int>::operator*(const Complex<int>& other) const {
  return Complex<int>(re * other.re - im * other.im, re * other.im + im * other.re);
}

int main() {
  {
    Complex<double> j { 0., 1. }; // Here implicit instantiation is triggered for Complex<double>
    Complex<double> c = j * j;    // Here nothing is triggered
  }
  {
    Complex<int> j { 0, 1 };  // Here implicit instantiation is triggered for Complex<int>
    Complex<int> c = j * j;   // Here nothing is triggered
  }
}

Why structuring files of a project in a standard way does not work for templates

So far everything was declared in one single .cpp file. In practice we want class template Complex<T> to be declared in a .hpp file:

File Complex.hpp

#pragma once

template <typename Scalar> class Complex {
  Scalar re, im;
public:
  Complex(Scalar re, Scalar im = Scalar{}) : re(re), im(im) {} // imaginary part is by default Scalar{} = 0
  Complex(const Complex&) = default;
  
  Complex operator*(const Complex& other) const;
};

File Complex.cpp

#include "Complex.hpp"

template <typename Scalar>
Complex<Scalar> Complex<Scalar>::operator*(const Complex& other) const {
  return Complex(re * other.re - im * other.im, re * other.im + im * other.re);
}

File main.cpp

#include "Complex.hpp"

int main() {
  {
    Complex<double> j { 0., 1. };
    Complex<double> c = j * j;
  }
  {
    Complex<int> j { 0, 1 };
    Complex<int> c = j * j;
  }
}
Here is what the symbol table contains:

Symbol table

Problem:

Complex.cpp and `main.cpp compile successfully but there is a error when editing links saying that symbols Complex<double>::operator* and Complex<int>::operator* are undefined (symbol U).

This is because:

A bad solution: using explicit instantiation

We can force Complex<double> and Complex<int> to be compiled by using explicit templace instantations.

This can only be done in Complex.cpp where we have all required definitions:

File Complex.cpp

#include "Complex.hpp"

template <typename Scalar>
Complex<Scalar> Complex<Scalar>::operator*(const Complex& other) const {
  return Complex(re * other.re - im * other.im, re * other.im + im * other.re);
}

// Here are the explicit instantiations

template class Complex<double>;
template class Complex<int>;

Here is what the symbol table contains:

Symbol table

Observations:

The good solution: defining templates in header files

There is no more file Complex.cpp, only a header file Complex.hpp that contains both declarations and definitions:

File Complex.hpp

#pragma once

template <typename Scalar> class Complex {
  Scalar re, im;
public:
  Complex(Scalar re, Scalar im = Scalar{}) : re(re), im(im) {}
  Complex(const Complex&) = default;
  
  Complex operator*(const Complex& other) const;
};

// Here comes the definitions:

template <typename Scalar>
Complex<Scalar> Complex<Scalar>::operator*(const Complex& other) const {
  return Complex(re * other.re - im * other.im, re * other.im + im * other.re);
}

We find the first symbol table:

Symbol table

This perfectly works, is flexible and the library code Complex.hpp does not need to be modified.

Why template instances are compiled as weak symbols

How does it work when there are multiple compilation units ?

Imagine a binary made of two .cpp files:

File main.cpp

#include "Complex.hpp"

Complex<double> square(const Complex<double>&);
  
int main() {
  Complex<double> j { 0., 1. };
  Complex<double> res = square(j);
  ...
}

File square.cpp

#include "Complex.hpp"

Complex<double> square(const Complex<double>& c) {
  return c * c;
}

The different symbol tables now look like

Symbol table

Observations

Constructor of Complex<double> is compiled twice…

Preliminary conclusions

Test yourself

Click on questions below to get the correct answer.

Other key facts

Here is a summary of few other ideas to bring home about templates:

Why and when to use templates?

However:

Frédéric Pennerath,