An Introduction to Generic Programming


Concepts describe a set of requirements, which are satisfied by a family of abstractions. The abstractions are typically data types or sets of data types, which we call models. For instance, a pointer is a model of the Iterator concept; alternatively, we can say that a pointer models the Iterator concept.

One of the most important aspects of Generic Programming is that the set of models for a given concept is neither known nor fixed. A given concept is written using a small, known set of models--say, nodes in a linked list and pointers into arrays--but will apply to many, many other data types, such as an pre-order iteration through a binary tree. It is precisely this openness that makes Generic Programming suitable for the design of reusable libraries, because a generic algorithm works equally well with any models of the concepts it requires, whether the algorithm author considered those data types or not. When we developed the sum() algorithm earlier in this introduction, did we realize that it could apply to integers read in from a file, or over a network, or even values generated by repeated calling a random number generator? Any of the data types that perform these operations can be models of the Iterator concept, and therefore will work with our generic sum() algorithm.

Similarly, when a data type is created we do not need to know all of the concepts that it will model. If at some point we find that we need our type to model a new concept, we can implement the required syntax without changing our data type. This ability, called retroactive modeling, allows anyone to adapt existing data types for use in generic algorithms. For instance, look back at how we have added the iterator operations and associated types for pointers: we did not have to modify the definition of pointers at all, nor could we have because they are built-in types. By making all of our requirements external to the data types, we allow retroactive modeling and avoid forcing changes to existing data types.

Previous: Concepts Author: Douglas Gregor Next: Specialization