What distinguishes an abstract algorithm from a concrete function? This is best shown by example. Let's write a function to multiply each of the elements in an array by 2:

    class array_of_ints {
      int data[10] = {};
      public:
        int size() const { return 10; }
        int& at(int i) { return data[i]; }
    };

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

Our function double_each_element works only with objects of type array_of_int; passing in an object of a different type won't work (nor even compile). We refer to functions like this version of double_each_element as concrete or monomorphic functions. We call them concrete because they are insufficiently abstract for our purposes. Just imagine how painful it would be if the C++ standard library provided a concrete sort routine that worked only on one specific data type!

We can increase the abstraction level of our algorithms via the techniques of classical object-oriented (OO) programming, as seen in languages such as Java and C#. The OO approach is to decide exactly which behaviors we'd like to be customizable, and then declare them as the public virtual member functions of an abstract base class:

    class container_of_ints {
      public:
      virtual int size() const = 0;
      virtual int& at(int) = 0;
    };

    class array_of_ints : public container_of_ints {
      int data[10] = {};
      public:
        int size() const override { return 10; }
        int& at(int i) override { return data[i]; }
    };

    class list_of_ints : public container_of_ints {
      struct node {
        int data;
        node *next;
      };
      node *head_ = nullptr;
      int size_ = 0;
      public:
       int size() const override { return size_; }
       int& at(int i) override {
        if (i >= size_) throw std::out_of_range("at");
        node *p = head_;
        for (int j=0; j < i; ++j) {
          p = p->next;
        }
        return p->data;
      }
      ~list_of_ints();
    };

    void double_each_element(container_of_ints& 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);
    }

Inside test, the two different calls to double_each_element compile because in classical OO terminology, an array_of_ints IS-A container_of_ints (that is, it inherits from container_of_ints and implements the relevant virtual member functions), and a list_of_ints IS-A container_of_ints as well. However, the behavior of any given container_of_ints object is parameterized by its dynamic type; that is, by the table of function pointers associated with this particular object.

Since we can now parameterize the behavior of the double_each_element function without editing its source code directly--simply by passing in objects of different dynamic types--we say that the function has become polymorphic.

But still, this polymorphic function can handle only those types which are descendants of the base class container_of_ints. For example, you couldn't pass a std::vector<int> to this function; you'd get a compile error if you tried. Classical polymorphism is useful, but it does not get us all the way to full genericity.

An advantage of classical (object-oriented) polymorphism is that the source code still bears a one-to-one correspondence with the machine code that is generated by the compiler. At the machine-code level, we still have just one double_each_element function, with one signature and one well-defined entry point. For example, we can take the address of double_each_element as a function pointer.

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.

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.

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.

Both classical polymorphism and generic programming deal with the essential problem of parameterizing the behavior of an algorithm: for example, writing a search function that works with any arbitrary matching operation.

Classical polymorphism tackles that problem by specifying an abstract base class with a closed set of virtual member functions, and writing polymorphic functions that accept pointers or references to instances of concrete classes inheriting from that base class.

Generic programming tackles the same problem by specifying a concept with a closed set of requirements, and instantiating function templates with concrete classes modeling that concept.

Classical polymorphism has trouble with higher-level parameterizations (for example, manipulating function objects of any signature) and with relationships between types (for example, manipulating the elements of an arbitrary container). Therefore, the Standard Template Library uses a great deal of template-based generic programming, and hardly any classical polymorphism.

When you use generic programming, it will help if you keep in mind the conceptual requirements of your types, or even write them down explicitly; but as of C++17, the compiler cannot directly help you check those requirements.