Generic programming with templates

In modern C++, the typical way to write a fully generic algorithm is to implement the algorithm as a template. We're still going to implement the function template in terms of the public member functions .size() and .at(), but we're no longer going to require that the argument arr be of any particular type. Because our new function will be a template, we'll be telling the compiler "I don't care what type arr is. Whatever type it is, just generate a brand-new function (that is, a template instantiation) with that type as its parameter type."

    template<class ContainerModel>
    void double_each_element(ContainerModel& arr)
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

    void test()
    {
      array_of_ints arr;
      double_each_element(arr);

      list_of_ints lst;
      double_each_element(lst);

      std::vector<int> vec = {1, 2, 3};
      double_each_element(vec);
    }

In most cases, it helps us design better programs if we can put down in words exactly what operations must be supported by our template type parameter ContainerModel. That set of operations, taken together, constitutes what's known in C++ as a concept; in this example we might say that the concept Container consists of "having a member function named size that returns the size of the container as an int (or something comparable to int); and having a member function named at that takes an int index (or something implicitly convertible from int) and produces a non-const reference to the index'th element of the container." Whenever some class array_of_ints correctly supplies the operations required by the concept Container, such that array_of_ints is usable with double_each_element, we say that the concrete class array_of_ints is a model of the Container concept. This is why I gave the name ContainerModel to the template type parameter in the preceding example.

It would be more traditional to use the name Container for the template type parameter itself, and I will do that from now on; I just didn't want to start us off on the wrong foot by muddying the distinction between the Container concept and the particular template type parameter to this particular function template that happens to desire as its argument a concrete class that models the Container concept.

When we implement an abstract algorithm using templates, so that the behavior of the algorithm can be parameterized at compile time by any types modeling the appropriate concepts, we say we are doing generic programming.

Notice that our description of the Container concept didn't mention that we expect the type of the contained elements to be int; and not coincidentally, we find that we can now use our generic double_each_element function even with containers that don't hold int!

    std::vector<double> vecd = {1.0, 2.0, 3.0};
    double_each_element(vecd);

This extra level of genericity is one of the big benefits of using C++ templates for generic programming, as opposed to classical polymorphism. Classical polymorphism hides the varying behavior of different classes behind a stable interface signature (for example, .at(i) always returns int&), but once you start messing with varying signatures, classical polymorphism is no longer a good tool for the job.

Another advantage of generic programming is that it offers blazing speed through increased opportunities for inlining. The classically polymorphic example must repeatedly query the container_of_int object's virtual table to find the address of its particular virtual at method, and generally cannot see through the virtual dispatch at compile time. The template function double_each_element<array_of_int> can compile in a direct call to array_of_int::at or even inline the call completely.

Because generic programming with templates can so easily deal with complicated requirements and is so flexible in dealing with types--even primitive types like int, where classical polymorphism fails--the standard library uses templates for all its algorithms and the containers on which they operate. For this reason, the algorithms-and-containers part of the standard library is often referred to as the Standard Template Library or STL.

That's right--technically, the STL is only a small part of the C++ standard library! However, in this book, as in real life, we may occasionally slip up and use the term STL when we mean standard library, or vice versa.

Let's look at a couple more hand-written generic algorithms, before we dive into the standard generic algorithms provided by the STL. Here is a function template count, returning the total number of elements in a container:

    template<class Container>
    int count(const Container& container)
    {
      int sum = 0;
      for (auto&& elt : container) {
        sum += 1;
      }
      return sum;
    }

And here is count_if, which returns the number of elements satisfying a user-supplied predicate function:

    template<class Container, class Predicate>
    int count_if(const Container& container, Predicate pred) 
    { 
      int sum = 0;
      for (auto&& elt : container) {
        if (pred(elt)) {
            sum += 1;
        }
      }
      return sum;
    }

These functions would be used like this:

    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    assert(count(v) == 8);

    int number_above =
      count_if(v, [](int e) { return e > 5; });
    int number_below =
      count_if(v, [](int e) { return e < 5; });

    assert(number_above == 2);
    assert(number_below == 5);

There is so much power packed into that little expression pred(elt)! I encourage you to try re-implementing the count_if function in terms of classical polymorphism, just to get a sense of where the whole thing breaks down. There are a lot of varying signatures hidden under the syntactic sugar of modern C++. For example, the ranged for-loop syntax in our count_if function is converted (or lowered") by the compiler into a for-loop in terms of container.begin() and container.end(), each of which needs to return an iterator whose type is dependent on the type of container itself. For another example, in the generic-programming version, we never specify--we never need to specify--whether pred takes its parameter elt by value or by reference. Try doing that with a virtual bool operator()!

Speaking of iterators: you may have noticed that all of our example functions in this chapter (no matter whether they were monomorphic, polymorphic, or generic) have been expressed in terms of containers. When we wrote count, we counted the elements in the entire container. When we wrote count_if, we counted the matching elements in the entire container. This turns out to be a very natural way to write, especially in modern C++; so much so that we can expect to see container-based algorithms (or their close cousin, range-based algorithms) arriving in C++20 or C++23. However, the STL dates back to the 1990s and pre-modern C++. So, the STL's authors assumed that dealing primarily in containers would be very expensive (due to all those expensive copy-constructions--remember that move semantics and move-construction did not arrive until C++11); and so they designed the STL to deal primarily in a much lighter-weight concept: the iterator. This will be the subject of our next chapter.