10  Templates

11 Templates

Week 4, Session 2. CSS 342.

11.1 Warmup

Binary Search (#704). The version we previewed in chapter 2 — implement it cleanly. Once you have it for vector<int>, what changes for vector<string>? (Almost nothing — < is defined for string too.) That insight is the seed of this chapter.

int binarySearch(const vector<int>& v, int target) {
  int lo = 0, hi = v.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (v[mid] == target) return mid;
    if (target < v[mid]) hi = mid - 1;
    else lo = mid + 1;
  }
  return -1;
}

11.2 Learning objectives

  1. Write a function template that works for any comparable type.
  2. Write a class template for a simple container.
  3. Explain why template implementations must live in header files (or be explicitly instantiated).
  4. Predict which concrete types a template will or will not compile for based on the operations used.
  5. Connect your use of std::vector<T> back to the template mechanism.

11.3 Motivation: three max functions

int max(int a, int b)       { return a > b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }
string max(string a, string b) { return a > b ? a : b; }

Three functions, identical bodies. Add a float version and you have four. This is the kind of duplication that should make you uncomfortable.

11.4 Function template

template <typename T>
T maxOf(T a, T b) {
  return a > b ? a : b;
}

template <typename T> says: “what follows is parameterized by some type T.” The compiler generates a fresh version for each type you call it with:

maxOf(3, 5);          // T = int
maxOf(2.5, 1.7);      // T = double
maxOf<string>("a", "b");  // T = string, sometimes needs explicit hint

The body must work for all types T you instantiate with. Here, T must support >. If you call maxOf(MyClass{}, MyClass{}) and MyClass has no operator>, you get a compile error — at the instantiation site, not at the template definition.

Template error messages are notoriously bad. A simple missing operator produces 200 lines of compiler output mentioning types you never wrote. The trick is to read the first error and ignore the rest. The first one usually says what is actually missing.

11.5 Class template

template <typename T>
class Pair {
 public:
  Pair(T a, T b) : first_(a), second_(b) {}
  T first() const { return first_; }
  T second() const { return second_; }

 private:
  T first_;
  T second_;
};

Usage:

Pair<int> p1(10, 20);
Pair<string> p2("hello", "world");

Multiple template parameters work too:

template <typename K, typename V>
class Entry {
 public:
  K key;
  V value;
};

Entry<string, int> e{"age", 42};

11.6 Where templates live — the compilation issue

Here is where students hit a brick wall. This does not work:

// Pair.h
template <typename T>
class Pair {
 public:
  Pair(T a, T b);     // declaration only
 private:
  T first_, second_;
};

// Pair.cpp
#include "Pair.h"
template <typename T>
Pair<T>::Pair(T a, T b) : first_(a), second_(b) {}    // definition

Linker error. Why? Because when main.cpp compiles and sees Pair<int>, the compiler generates Pair<int>::Pair(int, int) from the template. But the template body is in Pair.cpp, which is compiled separately. The compiler of Pair.cpp does not know what types to instantiate, so it generates nothing. At link time, main.o calls Pair<int>::Pair(int, int) and no such symbol exists.

11.6.1 Two fixes

Fix 1 — put the implementation in the header:

// Pair.h
template <typename T>
class Pair {
 public:
  Pair(T a, T b) : first_(a), second_(b) {}    // defined inline
  // ... etc.
};

This is what std::vector, std::map, and the rest of the STL do. Open <vector> and you will see massive headers with the implementations inline. That is the cost of templates.

Fix 2 — explicit instantiation in the .cpp:

// Pair.cpp
template <typename T>
Pair<T>::Pair(T a, T b) : first_(a), second_(b) {}

// Force generation of these instantiations:
template class Pair<int>;
template class Pair<string>;

This works only if you can enumerate the types in advance. For a class template meant to be used generically, fix 1 is the answer.

11.7 std::swap — a function template you have already used

template <typename T>
void swap(T& a, T& b) {
  T tmp = a;
  a = b;
  b = tmp;
}

That is it. Three lines and it works for int, string, Box, vector<int> — anything with copy/assign.

11.8 The STL is templates

Every container you have used so far is a template:

  • vector<T>
  • set<T>
  • map<K, V>
  • pair<T1, T2>
  • stack<T>

You have been using templates since week 1. This chapter is just the unmask.

11.9 Try it

Write a function template printAll that takes a vector<T> and prints its elements separated by spaces. Try calling it with vector<int>, vector<string>, and vector<double>.

template <typename T>
void printAll(const vector<T>& v) {
  for (const auto& x : v) cout << x << " ";
  cout << endl;
}

What happens if you call it with vector<Box> (where Box has no operator<<)? Run it. Read the first error line.

11.10 Self-check

1. Why must template implementations usually live in header files?
c. Instantiation happens at the use site; the compiler must see the body there.
2. What does maxOf(3, 5.5) do (given the template above)?
b. Template argument deduction needs a single T. Fix by casting one argument or by writing maxOf<double>(3, 5.5).

11.11 Challenges

  1. Write a function template contains(const vector<T>&, T value) that returns bool.
  2. Write a class template Stack<T> wrapping a vector<T>. Implement push, pop, top, empty, size.
  3. Make your IntList from chapter 7 generic: List<T>. Apply the Rule of Three. Put it all in List.h.

11.12 Where this fits

You can now write generic, reusable containers. Next: the algorithm you cannot write a tree class without — recursion.

You are here Coming up
Function templates, class templates, why they live in headers Chapter 9: recursion