Parameterization of Containers and Algorithms

Imagine you need a function that adds up the values stored in a collection. Today the collection holds integers. Tomorrow it holds decimal numbers, and the day after it holds some other kind of element. If every one of these cases needed its own separately written function, most of the logic would be copied again and again, changing only the type named in the code.

A function template is a way to avoid that repetition. Instead of writing the function once for each type, you write it once and leave the type open until the function is actually used. The type is a parameter, just like a value passed into an ordinary function, except that the thing being passed is a type rather than a number or a string.

The source gives a concrete illustration: a function that calculates the sum of the element values of any container. Read this as a plan rather than as one fixed function. The job is always the same, which is to walk through the elements and add their values together. What changes from one container to the next is only the kind of element being added.

A function template captures the fixed job and leaves the element type open. The single definition is the pattern. Each time the code uses the pattern with a particular type, a concrete function comes out of it. The diagram below shows one template feeding several concrete functions, with the shared job held in the template itself.

Consider a small function template that returns the larger of two values. Its declaration begins with template and a type parameter named T, and both parameters use T. When the code calls max(3, 7), the type is taken from the arguments, so T becomes int. When the code calls max(2.5, 1.0), T becomes double. The same pattern produces two separate concrete functions, one for each use.

The source points out that templates have more uses than parameterizing a container with an element type. Two uses are singled out. Templates are used extensively to parameterize types, so that a container can hold elements of whatever type the programmer names. Templates are also used to parameterize algorithms, which are the procedures applied to the data. Both appear throughout the standard library.

The same template idea therefore covers two kinds of generality. One concerns what kind of element a container holds. The other concerns the procedure applied to the data. A container such as std::vector is generic over its element type, and an algorithm written as a template can be applied to data of many element types without being rewritten for each one.

Returning to the summing example from the source, the following template walks through a std::vector of any element type and adds the values together. The total starts at a value-initialized T, so the same text works whether T is int or double. Each use with a different element type produces its own concrete function.

The alternative to a template is to write a separate function for each element type. The two approaches differ in how much code is repeated. With separate functions, the logic is copied for every type, and a later change to that logic has to be made in every copy. With one template, the logic lives in a single definition, and each type is supplied only where it is used.