Generic Programming Glossary

associated type
An associated type is a type that is used to describe the requirements of a concept, but is not actually a parameter to the concept. For instance, the reference type returned when dereferencing an Input Iterator is expressed as an associated type. In languages that do not directly support associated types, type parameters can be used instead at some cost to brevity.

A concept contains a set of requirements that describe a family of abstractions, typically data types. Examples of concepts include Input Iterator, Graph, and Equality Comparable.

concept-based overloading
Concept-based overloading selects the most specific algorithm from a set of specializations of a given algorithm.

A constraint is a requirement placed on the type parameters to a generic algorithm. Constraints are typically concept constraints, meaning that the type parameters must model a particular concept.

Lifting is the process by which the differences among multiple, concrete implementations of the same algorithm are abstracted away, producing a generic algorithm.

A model is a type or set of types that meets the requirements of a concept. An integer pointer is a model of the Input Iterator concept. "Model" can also be used as a verb to describe the relationship between a type or set of types and a concept, e.g., an adjacency list models the Graph concept.

Refinement is a hierarchical relationship between two concepts. If B refines A, then the requirements of B are a superset of the requirements of A. Thus, the set of abstractions that model B are a subset of those that model A, i.e., every B is an A.

A requirement is part of a concept that describes the behavior of an abstraction. Requirements tend to be syntactic (e.g., all Input Iterators have a dereference operation), semantic (e.g., one can traverse the sequence of values returned from a Forward Iterator muliple times), or performance-related (e.g., incrementing an Input Iterator occurs in constant amortized time).

retroactive modeling
Retroactive modeling allows types to model concepts without modifying the types in question. Retroactive modeling is very important for reusing existing data structures with new, generic algorithms.

Specialization allows multiple implementations of the same algorithm, each of which has different concept constraints. Typically, one can implement a certain baseline algorithm for a very small, widely applicable concept then implement more efficient, specialized algorithms for richer concepts. In some contexts, "specialization" may also refer to C++ (partial or full) specialization, as for function and class templates.

A taxonomy (or concept taxonomy) is a set of interdependent concepts arranged in a lattice based on their refinement relationships. In some cases, a concept taxonomy will resemble a hierarchy because it will contain only a single refinement tree; more typically, however, a concept taxonomy will will contain several small tree-like structures.