5.1. Concepts

First, we'll define an important term that originated in the world of runtime generic programming. A concept is a description of the requirements placed by a generic component on one or more of its arguments. We've already covered a few concepts in this book. For example, the apply1 metafunction that we wrote in Chapter 3 required a first argument that was a Metafunction Class.

A type or group of types that satisfies a concept's requirements is said to model the concept or to be a model of the concept. So plus_f, also from Chapter 3, is a model of Metafunction Class. A concept is said to refine another concept when its requirements are a superset of those of the other concept.

Concept requirements usually come from the following categories.

Valid expressions

C++ expressions that must compile successfully for the objects involved in the expression to be considered models of the concept. For example, an Iterator x is expected to support the expressions ++x and *x.

Associated types

Types that participate in one or more of the valid expressions and that can be computed from the type(s) modeling the concept. Typically, associated types can be accessed either through typedefs nested within a class definition for the modeling type or through a traits class. For example, as described in Chapter 2, an iterator's value type is associated with the iterator through std::iterator_traits.

Invariants

Runtime characteristics of a model's instances that must always be true; that is, all operations on an instance must preserve these characteristics. The invariants often take the form of pre-conditions and post-conditions. For instance, after a Forward Iterator is copied, the copy and the original must compare equal.

Complexity guarantees

Maximum limits on how long the execution of one of the valid expressions will take, or how much of various resources its computation will use. Incrementing an Iterator, for example, is required to have constant complexity.

In this chapter we'll be introducing several new concepts and refinement relationships with associated types and complexity guarantees.