The Standard Template Library in C++

Generic programming is the idea of writing one piece of code that works on data of many different types. Learners who have seen this idea in a dynamically checked language often carry a hopeful assumption into C++: that a single generic subroutine will simply accept any kind of data and sort it, with any problems discovered only when the program runs. This article corrects that assumption. C++ does have a powerful and flexible form of generic programming, but it works on different principles, and those principles change where and when errors appear.

Commit to an answer before reading on. The reasoning behind the correct answer is what makes the difference between the Smalltalk style of generic programming and the C++ style visible.

The run-time style of generic programming used in Smalltalk cannot be used in C++ because C++ is a very strongly typed language. Every variable has a type and can hold only data values of that type. A variable declared to hold integers cannot quietly hold a string later on. The kind of generic programming that depends on that flexibility is therefore impossible in C++.

The contrast between the two styles is easiest to see by asking when each one makes its type decisions. The diagram below sets the two approaches side by side.

Strong typing does not remove generic programming from C++. It changes the mechanism. Instead of one subroutine that works with values of any type at run time, C++ provides a way to write a single pattern and let the compiler produce a concrete version for each type that is actually used.

Everything needed to produce a version of a template is known when the program is compiled. Because of this, the compiler can detect a type that does not support a required operation before the program is executed. Strong typing is the reason the check can happen this early: since each value has a fixed type, the compiler can know in advance which operations will be applied to it.

The source uses a helpful comparison: a factory does not itself perform the work of its products. It holds a design and produces concrete items from that design when asked. A subroutine template works the same way. The design is the template; the products are the concrete subroutines the compiler generates from it.

The source describes the compiler's job with a simple sorting example. When a program calls sort on an array of ints, the compiler uses the template to generate a subroutine for sorting arrays of ints. When the same template is called on an array of Card objects, the compiler generates a separate subroutine for sorting arrays of Cards. One template feeds two distinct generated versions, each chosen by the type of the data in the call.

The compiler tries to generate a subroutine from a template, and it succeeds only if the template's operations make sense for the type supplied. The template in the earlier example compares values with >. If that operator is defined for a type, generation succeeds. If it is not, generation fails, and the failure is reported at compile time.

In C++ it is possible to write definitions of operators like > for any type. A programmer can therefore supply a meaning for > that applies to Card values. The template that depends on > can then be used with Cards. This is operator overloading: a user-defined type such as Card supplies the operators a template needs.

Templates are not limited to subroutines. The source explains that C++ also has templates for making classes. A programmer can write a template for a binary tree class, and that single template can generate classes for binary trees of ints, binary trees of strings, binary trees of dates, and so on. The reasoning is the same as for subroutines: one pattern, many concrete classes, each produced for a particular type.

All of the mechanisms described above are available to programmers in a large collection that comes with modern C++. The source calls this collection the Standard Template Library, or STL. It is described as a large number of pre-written templates. The STL is a body of ready-made generic building blocks, so a programmer does not need to write common templates from scratch.

The source is candid that the STL is quite complex, and that many people would say it is much too complex. It also notes that the STL is one of the most interesting features of C++. A reasonable way to approach it is to understand the template mechanism first, since the STL is built from exactly those templates.