The C++ Programming Language (2013)

Part III: Abstraction Mechanisms

24. Generic Programming

Now is a good time to put your work on a firm theoretical basis.

– Sam Morgan

• Introduction

• Algorithms and Lifting

• Concepts

Discovering a Concept; Concepts and Constraints

• Making Concepts Concrete

Axioms; Multi-argument Concepts; Value Concepts; Constraints Checks; Template Definition Checking

• Advice

24.1. Introduction

What are templates for? In other words, what programming techniques are effective when you use templates? Templates offer:

• The ability to pass types (as well as values and templates) as arguments without loss of information. This implies excellent opportunities for inlining, of which current implementations take great advantage.

• Delayed type checking (done at instantiation time). This implies opportunities to weave together information from different contexts.

• The ability to pass constant values as arguments. This implies the ability to do compile-time computation.

In other words, templates provide a powerful mechanism for compile-time computation and type manipulation that can lead to very compact and efficient code. Remember that types (classes) can contain both code and values.

The first and most common use of templates is to support generic programming, that is, programming focused on the design, implementation, and use of general algorithms. Here, “general” means that an algorithm can be designed to accept a wide variety of types as long as they meet the algorithm’s requirements on its arguments. The template is C++’s main support for generic programming. Templates provide (compile-time) parametric polymorphism.

There are many definitions of “generic programming.” Thus, the term can be confusing. However, in the context of C++, “generic programming” implies an emphasis on the design of general algorithms implemented using templates.

Focusing more on generative techniques (seeing templates as type and function generators) and relying on type functions to express compile-time computation are called template metaprogramming, which is the subject of Chapter 28.

The type checking provided for templates checks the use of arguments in the template definition rather than against an explicit interface (in a template declaration). This provides a compile-time variant of what is often called duck typing (“If it walks like a duck and it quacks like a duck, it’s a duck”). Or – using more technical terminology – we operate on values, and the presence and meaning of an operation depend solely on its operand values. This differs from the alternative view that objects have types, which determine the presence and meaning of operations. Values “live” in objects. This is the way objects (e.g., variables) work in C++, and only values that meet an object’s requirements can be put into it. What is done at compile time using templates does not involve objects, only values. In particular, there are no variables at compile time. Thus, template programming resembles programming in dynamically-typed programming languages, but the run-time cost is zero, and errors that in a run-time typed language manifest themselves as exceptions become compile-time errors in C++.

A key aspect of generic programming, metaprogramming, and probably all uses of templates is the uniform handling of built-in types and user-defined types. For example, an accumulate() operation does not care whether the types of values it adds up are ints, complex<double>s, orMatrixes. What it cares about is that they can be added using the + operator. The use of a type as a template argument does not imply or require the use of a class hierarchy or any form of run-time self-identification of the type of an object. This is logically pleasing and essential for high-performance applications.

This section focuses on two aspects of generic programming:

• Lifting: generalizing an algorithm to allow the greatest (reasonable) range of argument types (§24.2), that is, to limit an algorithm’s (or a class’s) dependency on properties to what is essential

• Concepts: carefully and precisely specifying the requirements of an algorithm (or a class) on its arguments (§24.3)

24.2. Algorithms and Lifting

A function template is a generalization of an ordinary function in the sense that it can perform its actions on a variety of data types and use a variety of operations passed as arguments to implement those actions. An algorithm is a procedure or formula for solving a problem: a finite series of computation steps to produce a result. Thus, a function template is often called an algorithm.

How do we get from a function doing specific operations on specific data to an algorithm doing more general operations on a variety of data types? The most effective way of getting a good algorithm is to generalize from one – and preferably more – concrete example. Such generalization is called lifting: that is, lifting a general algorithm from specific functions. It is important to go from the concrete to the abstract while maintaining performance and keeping an eye on what is reasonable. Overly clever programmers can generalize to an absurd extent to try to cover every eventuality. Thus, trying to abstract from first principles in the absence of concrete examples typically leads to bloated, hard-to-use code.

I will illustrate the process of lifting by a concrete example. Consider:

double add_all(double* array, int n)
// one concrete algorithm on array of doubles
{
double s {0};
for (int i = 0; i<n; ++i)
s = s + array[i];
return s;
}

Obviously, this computes the sum of the doubles in the argument array. Also consider:

struct Node {
Node* next;
int data;
};

int sum_elements(Node* first, Node* last)
// another concrete algorithm on list of ints
{
int s = 0;
while (first!=last) {
s += first–>data;
first = first–>next;
}
return s;
}

This computes the sum of the ints in the singly-linked list implemented by the Nodes.

These two code fragments differ in detail and in style, but an experienced programmer will immediately say, “Well, this is just two implementations of the accumulate algorithm.” This is a popular algorithm. Like most popular algorithms, it has many names, including reduce, fold, sum, and aggregate. However, let us try to develop a general algorithm from the two concrete examples in stages, so as to get a feel for the process of lifting. First we try to abstract away the data types so that we don’t have to be specific about

• double vs. int, or

• array vs. linked list.

To do so, I write some pseudo code:

// pseudo code:

T sum(data)
// somehow parameterize by the value type and the container type
{
T s = 0
while (not at end) {
s = s + current value
get next data element
}
return s
}

To make this concrete, we need three operations to access the “container” data structure:

• Not at end

• Get current value

• Get next data element

For the actual data, we also need three operations:

• Initialize to zero

• Add

• Return the result

Obviously, this is rather imprecise, but we can turn it into code:

// concrete STL-like code:

template<typename Iter, typename
Val sum(Iter first, Iter last)
{
Val s = 0;
while (first!=last) {
s = s + *first;
++first;
}
return s;
}

Here, I took advantage of knowing the usual STL way of representing a sequence of values (§4.5). The sequence is represented as a pair of iterators supporting three operations:

• * for accessing the current value

• ++ for moving forward to the next element

• != for comparing iterators to check if we are at the end of a sequence

We now have an algorithm (a function template) that can be used for both arrays and linked lists and for both ints and doubles. The array example works immediately because double* is an example of an iterator:

double ad[] = {1,2,3,4};
double s = sum<double*>(ad,ad+4);

To use the handcrafted singly-linked list, we need to provide an iterator for it. Given a few operations, a Node* can be the iterator:

struct Node { Node* next; int data; };

Node* operator++(Node* p) { return p–>next; }
int operator*(Node* p) { return p–>data; }
Node* end(lst) { return nullptr; }

void test(Node* lst)
{
int s = sum<int*>(lst,end(lst));
}

I use the nullptr as the end iterator. I use an explicit template argument (here, <int>) to allow a caller to specify the type to use for the accumulator variable.

What we have so far is more general than a lot of real-world code. For example, sum() would work for lists of floating-point numbers (of all precisions), for arrays of integers (of all ranges), and for many other types, such as a vector<char>. Importantly, sum() is as efficient as the handcrafted functions we started from. We do not want to achieve generality at the cost of performance.

The experienced programmer will note that sum() can be generalized further. In particular, the use of an extra template argument is awkward, and we required the initial value 0. We can solve that by letting the caller supply an initial value and then deduce Val:

template<typename Iter, typename Val>
Val accumulate(Iter first, Iter last, Val s)
{
while (first!=last) {
s = s + *first;
++first;
}
return s;
}

double ad[] = {1,2,3,4};
double s1 = accumulate(ad,ad+4,0.0); // accumulate in a double
double s2 = accumulate(ad,ad+4,0); // accumulate in an int

But why +? We sometimes want to multiply elements. In fact, there seem to be quite a few operations we might want to apply to the elements of a sequence. This leads to a further generalization:

template<typename Iter, typename Val, typename Oper>
Val accumulate(Iter first, Iter last, Val s, Oper op)
{
while (first!=last) {
s = op(s,*first);
++first;
}
return s;
}

We now use the argument op to combine element values with the accumulator. For example:

double ad[] = {1,2,3,4};
double s1 = accumulate(ad,ad+4,0.0,std::plus<double>); // as before
double s2 = accumulate(ad,ad+4,1.0,std::multiply<double>);

The standard library provides common operations, such as plus and multiply, as function objects to be used as arguments. Here, we see the utility of having the caller supply the initial value: 0 and * don’t go well together for accumulation. The standard library offers a further generalization of accumulate() that allows a user to provide an alternative to = for combining the result of the “addition” and the accumulator (§40.6).

Lifting is a skill that requires knowledge of an application domain and some experience. The most important single guide for designing algorithms is to lift them from concrete examples without adding features (notation or run-time cost) that would impair their use. The standard-library algorithms are the results of lifting done with great attention to performance issues.

24.3. Concepts

What are a template’s requirements for its arguments? In other words, what does the template code assume about its argument types? Or conversely, what must a type provide to be acceptable as an argument to a template? The possibilities are infinite because we can build classes and templates with arbitrary properties, for example:

• Types that provide – but not +

• Types that can copy but not move values

• Types for which copy operations does not copy (§17.5.1.3)

• Types for which == compares equality and others for which compare() does that

• Types that define addition as a member function plus() and others that define it as a non-member function operator+()

In that direction lies chaos. If every class has a unique interface, it becomes difficult to write templates that can take many different types. Conversely, if each template’s requirements are unique, it becomes difficult to define types that can be used with many templates. We would have to remember and keep track of a multitude of interfaces; that’s feasible for a tiny program, but unmanageable for real-world libraries and programs. What we need to do is to identify a small number of concepts (sets of requirements) that can be used for many templates and many types as arguments. The ideal is a kind of “plug compatibility” as we know it from the physical world, with a small number of standard plug designs.

24.3.1. Discovering a Concept

As an example, consider the String class template from §23.2:

template<typename C>
class String {
// ...
};

What is required of a type, X, for it to be used as an argument to String: String<X>? More generally, what does it take to be a character in such a character string class? An experienced designer will have a small number of likely answers to that question and start the design based on those. However, let us consider how we might answer it from first principles. We proceed through three stages of analysis:

[1] First, we look at our (initial) implementation and determine which properties (operations, functions, member types, etc.) it uses from its parameter types (and the meaning of those operations). The resulting list is the minimal requirements for that particular template implementation.

[2] Next, we look at plausible alternative template implementations and list their requirements on their template arguments. Doing so, we may decide that we should place more or stricter requirements on the template arguments to allow for alternative implementations. Alternatively, we might decide to prefer an implementation that makes fewer and/or simpler requirements.

[3] Finally, we look at the resulting list (or lists) of required properties and compare it to lists of requirements (concepts) that we have used for other templates. We try to find simple, preferably common, concepts that can express what would otherwise be many long lists of requirements. The aim here is to make our design benefit from general work on classification. The resulting concepts are easier to give meaningful names and easier to remember. They should also maximize the degree of interoperability of templates and types by limiting variations in concepts to what is essential.

The first two steps are – for fundamental reasons – very similar to the way we generalize (“lift”) concrete algorithms into generic algorithms (§24.2). The last step counteracts the temptation to provide each algorithm with a set of argument requirements that exactly match its implementation. Such requirement lists are overspecialized and not stable: each change to the implementation would imply changes to the requirements documented as part of the algorithm’s interface.

For String<C>, first consider the operations actually performed on the parameter C by the implementation of String (§19.3). That will be the minimal set of requirements for that implementation of String:

[1] Cs are copied by copy assignment and copy initialization.

[2] String compares Cs using == and !=.

[3] String makes arrays of Cs (that implies default construction of Cs).

[4] String takes the address of Cs.

[5] Cs are destroyed when a String is destroyed.

[6] String has >> and << operators that somehow must read and write Cs.

Requirements [4] and [5] are technical requirements that we usually assume for all data types, and I will not discuss types that fail to meet them; such types are almost all overly clever artifacts. The first requirement – that values can be copied – is not true for a few important types, such asstd::unique_ptr, that represent real resources (§5.2.1, §34.3.1). However, it is true for almost all “ordinary types,” so we require it. The ability to invoke a copy operation goes together with the semantic requirement that a copy really is a copy of the original, that is, that – except for taking the address – the two copies behave identically. Therefore, the ability to copy usually (as for our String) goes together with the requirement to provide == with the usual semantics.

By requiring assignment, we imply that a const type cannot be used as a template argument. For example, String<const char> is not guaranteed to work. That’s fine in this case, as in most cases. Having assignment means that an algorithm can use temporary variables of its argument type, create containers of objects of an argument type, etc. It does not imply that we cannot use const to specify interfaces. For example:

template<typename T>
bool operator==(const String<T>& s1, const String<T>& s2)
{
if (s1.size()!=s2.size()) return false;
for (auto i = 0; i!=s1.size(); ++i)
if (s1[i]!=s2[i]) return false;
return true;
}

For String<X> we require that objects of type X can be copied. Independently, through the consts in its argument types, operator==() promises not to write to the X elements.

Should we require a move for an element type C? After all, we provide move operations for String<C>. We could, but it’s not essential: what we do with a C can be handled by copying, and if some copy is implicitly turned into a move (e.g., when we returned a C), so much the better. In particular, potentially important examples, such as String<String<char>>, will work fine (correctly and efficiently) without adding move operations to the requirements.

So far, so good, but the last requirement (that we can read and write Cs using >> and <<) seems excessive. Do we really read and write every kind of string? Maybe it would be better to say that if we read and write a String<X>, then X must provide >> and <<? That is, instead of placing a requirement on C for the whole String, we require it (only) for Strings that we actually read and write.

This is an important and fundamental design choice: we can place a requirement on class template arguments (so that they apply to all class members) or just to template arguments on individual class function members. The latter is more flexible, but also more verbose (we have to express the requirement for each function that needs it) and harder for a programmer to remember.

Looking at the list of requirements so far, I note the absence of a couple of operations that are common for “ordinary characters” in “ordinary strings”:

[1] No ordering (e.g., <)

[2] No conversion to an integer value

After this initial analysis we can consider which “well-known concepts” (§24.3.2) our lists of requirements relate to. The central concept for “ordinary types” is regular. A regular type is a type that

• you can copy (using assignment or initialization) with the proper copy semantics (§17.5.1.3),

• you can default construct,

• doesn’t have problems with various minor technical requirements (such as taking the address of a variable),

• you can compare for equality (using == and !=).

That seems an excellent choice for our String template arguments. I considered leaving out the equality comparisons but decided that copying without equality is rarely useful. Typically, Regular is the safe bet, and thinking about the meaning of == can help avoid errors in the definition of copying. All the built-in types are regular.

But does it make sense to leave out ordering (<) for String? Consider how we use strings. The desired use of a template (such as String) should determine its requirements on its arguments. We do compare strings extensively, and in addition we use comparisons indirectly when we sort sequences of strings, we put strings into sets, etc. Also, the standard-library string does provide <. It is usually a good idea to look to the standard for inspiration. So, we require not just Regular for our String, but also ordering. That’s the concept Ordered.

Interestingly, there has been quite some debate on whether Regular should require < or not. It seems that most types related to numbers have a natural order. For example, characters are encoded in bit patterns that can be interpreted as integers, and any sequence of values can be lexicographically ordered. However, many types do not have a natural order (e.g., complex numbers and images) even though we could define one. Other types have several natural orderings, but no unique best ordering (e.g., records may be ordered by name or by address). Finally, some (reasonable) types simply don’t have an order. For example, consider:

enum class rsp { rock, scissors, paper };

The rock-scissors-and-paper game critically depends on

• scissors<rock,

• rock<paper, and

• paper<scissors.

However, our String is not supposed to take an arbitrary type as its character type; it is supposed to take a type that supports string operations (such as comparisons, sorting, and I/O), so I decided to require ordering.

Adding a default constructor and the == and < operator, to our requirements for String’s template argument allows us to provide several useful operations for String. In fact, the more we require of a template argument type, the easier the various tasks become for the template implementer and the more services the template can offer to its users. On the other hand, it is important not to load down a template with requirements that are only used rarely and by specific operations: each requirement places a burden on the implementer of argument types and limits the set of types that can be used as arguments. So, for String<X> we require:

• Ordered<X>

• >> and << for X (only) if we use String<X>’s >> and <<

• Convertibility to an integer (only) if we define and use a conversion operation from X

So far, we have expressed our requirement of a character type for String in terms of syntactic properties, such as X must provide copy operations, ==, and <. In addition, we must require that these operations have the right semantics; for example, a copy operation makes a copy, == (equality) compares for equality, and < (less than) provides ordering. Often, this semantics involves relations among the operations. For example, for the standard library, we have (§31.2.2.1):

• The result of a copy compares equal to anything the original compares equal to (a==b implies T{a}==T{b}) and the copy is independent of its source (§17.5.1.3).

• A less-than comparison (e.g., <) provides a strict weak order (§31.2.2.1).

The semantics are defined in English text or (better still) mathematics, but unfortunately we have no way of expressing semantic requirements in C++ itself (but see §24.4.1). For the standard library, you can find the semantic requirements written in formalized English in the ISO standard.

24.3.2. Concepts and Constraints

A concept is not an arbitrary collection of properties. Most lists of properties of a type (or a set of types) do not define a coherent and useful concept. To be useful as a concept, a list of requirements has to reflect the needs of a set of algorithms or a set of operations of a template class. In many fields of endeavor, people have designed or discovered concepts describing the fundamental concepts of the field (the technical use of the word “concept” in C++ was chosen with this common usage in mind). There seem to be surprisingly few concepts that make sense. For example, algebra builds on concepts such as monad, field, and ring, whereas the STL relies on concepts such as forward iterator, bidirectional iterator, and random-access iterator. Finding a new concept in a field is a major accomplishment; it is not something you should expect to do every year. Mostly, you find concepts by examining the foundational texts of a field of study or an application domain. The set of concepts used in this book are described in §24.4.4.

“Concepts” is a very general idea that does not inherently have anything to do with templates. Even K&R C [Kernighan,1978] had concepts in the sense that signed integral type is the language’s generalization of the idea of an integer in memory. Our requirements on template arguments are concepts (however expressed), so most interesting issues related to concepts come in the context of templates.

I see a concept as a carefully crafted entity that reflects fundamental properties of an application domain. Consequently, there should be only few concepts, and these can act as a guideline for the design of algorithms and types. The analogy is with physical plugs and sockets; we want the minimal number to simplify our lives and to keep design and construction costs down. This ideal can conflict with the ideal of minimal requirements for each individual generic algorithm (§24.2) and each individual parameterized class. Furthermore, the ideal can conflict with the ideal of providing absolutely minimal interfaces to classes (§16.2.3) and even with what some programmers regard as their right to write their code “exactly as they like.” However, we don’t get plug compatibility without effort and some form of standard.

I set the bar for being a concept very high: I require generality, some stability, usability across many algorithms, semantic consistency, and more. In fact, many simple constraints that we’d like for template arguments don’t qualify as concepts according to my criteria. I think that is unavoidable. In particular, we write many templates that do not reflect general algorithms or widely applicable types. Instead, they are implementation details, and their arguments only have to reflect the necessary details of a template intended for a single use in a single implementation of something. I call requirements for such template arguments constraints or (if you must) ad hoc concepts. One way to look at constraints is to consider them incomplete (partial) specifications of an interface. Often, a partial specification can be useful and much better than no specification.

As an example, consider a library for experimenting with balancing strategies for balanced binary trees. The tree takes a Balancer as a template argument:

template<typename Node, typename Balance>
struct node_base { // base of balanced tree
// ...
}

A balancer is simply a class that provides three operations on nodes. For example:

struct Red_black_balance {
// ...
template<typename Node> static void add_fixup(Node* x);
template<typename Node> static void touch(Node* x);
template<typename Node> static void detach(Node* x);
};

Obviously, we’d like to say what’s required of node_base’s arguments, but a balancer is not meant to be a widely used and easily understood interface; it’s meant to be used only as a detail of a particular implementation of balanced trees. This idea of a balancer (I hesitate to use the word “concept”) is unlikely to be used elsewhere or even to survive a major rewrite of the balanced tree implementation unchanged. It would be hard to pin down the exact semantics of a balancer. For starters, the semantics of Balancer would critically depend on the semantics of Node. In those aspects, a Balancer differs from a proper concept, such as Random_access_iterator. We can, however, still use the minimal specification of a balancer, “provides those three functions on nodes,” as a constraint on arguments to a node_base.

Note the way “semantics” keep cropping up in the discussion of concepts. I find that “Can I write out a semiformal semantics?” to be the question that is most helpful when it comes to deciding whether something is a concept or simply an ad hoc collection of constraints on a type (or set of types). If I can write out a meaningful semantic specification, I have a concept. If not, what I have is a constraint that may be useful but shouldn’t be expected to be stable or widely useful.

24.4. Making Concepts Concrete

Unfortunately, C++ does not have specific language facilities for directly expressing concepts. However, handling “concepts” as a design notion only and presenting them informally as comments is not ideal. For starters, compilers do not understand comments, so requirements expressed only as comments must be checked by the programmer and cannot help the compiler provide good error messages. Experience shows that even though concepts cannot be represented perfectly without direct language support, we can approximate them using code that performs compile-time checks of template argument properties.

A concept is a predicate; that is, we think of a concept as a compile-time function that looks at a set of template arguments and returns true if they meet the concept’s requirements and false if they don’t. So, we implement a concept as a constexpr function. Here, I will use the termconstraints check to refer to a call of a constexpr predicate that checks a concept for a set of types and values. In contrast to proper concepts, a constraints check does not deal with semantic issues; it simply checks assumptions about syntactic properties.

Consider our String; its character type argument is supposed to be Ordered:

template<typename C>
class String {
static_assert(Ordered<C>(),"String's character type is not ordered");
// ...
};

When String<X> is instantiated for a type X, the static_assert will be executed by the compiler. If Ordered<X>() returns true, the compilation proceeds, generating exactly the code it would have done without the assert. Otherwise, the error message is produced.

At first glance, this looks rather reasonable for a workaround. I’d rather have said:

template<Ordered C>
class String {
// ...
};

However, that is for the future, so let us see how to define the predicate Ordered<T>():

template<typename T>
constexpr bool Ordered()
{
return Regular<T>() && Totally_ordered<T>();
}

That is, a type is Ordered if it is both Regular and Totally_ordered. Let us “dig down” to see what that means:

template<typename T>
constexpr bool Totally_ordered()
{
return Equality_comparable<T>() // has == and !=
&& Has_less<T>()&& Boolean<Less_result<T>>()
&& Has_greater<T>() && Boolean<Greater_result<T>>()
&& Has_less_equal<T>() && Boolean<Less_equal_result<T>>()
&& Has_greater_equal<T>() && Boolean<Greater_equal_result<T>>();
}

template<typename T>
constexpr bool Equality_comparable()
{
return Has_equal<T>() && Boolean<Equal_result<T>>()
&& Has_not_equal<T>() && Boolean<Not_equal_result<T>>();
}

So, a type T is ordered if it is regular and provides the usual six comparison operations. The comparison operations have to deliver results that can be converted to bool. The comparison operators are also supposed to have their proper mathematical meaning. The C++ standard precisely specifies what that means (§31.2.2.1, §iso.25.4).

Has_equals is implemented using enable_if and the techniques described in §28.4.4.

I capitalize my constraints names (e.g., Regular) even though doing so violates my “house style” of capitalizing type and template names, but not functions. However, concepts are even more fundamental than types, so I feel a need to emphasize them. I also keep them in a separate namespace (Estd) in the hope that very similar names will eventually become part of the language or the standard library.

Digging a bit further into the set of useful concepts, we can define Regular:

template<typename T>
constexpr bool Regular()
{
return Semiregular<T>() && Equality_comparable<T>();
}

Equality_comparable gives us == and !=. Semiregular is the concept that express the notion of a type that doesn’t have unusual technical restrictions:

template<typename T>
constexpr bool Semiregular()
{
return Destructible<T>()
&& Default_constructible<T>()
&& Move_constructible<T>()
&& Move_assignable<T>()
&& Copy_constructible<T>()
&& Copy_assignable<T>();
}

A Semiregular can be both moved and copied. That describes most types, but there are examples of types that cannot be copied, such as unique_ptr. However, I don’t know of useful types that can be copied but not moved. Types that can neither be moved nor copied, such as type_info(§22.5), are very rare and tend to reflect system properties.

We can also use constraints checks for functions; for example:

template<typename C>
ostream& operator<<(ostream& out, String<C>& s)
{
static_assert(Streamable<C>(),"String's character not streamable");
out << '"';
for (int i=0; i!=s.size(); ++i) cout << s[i];
out << '"';
}

The concept Streamable needed by String’s output operator << requires its argument C to provide the output operator <<:

template<typename T>
constexpr bool Streamable()
{
return Input_streamable<T>() && Output_streamable<T>();
}

That is, Streamable tests that we can use the standard stream I/O (§4.3, Chapter 38) for a type.

Checking concepts through constraints-check templates has obvious weaknesses:

• Constraints checks are placed in definitions, but they really belong in declarations. That is, a concept is part of the interface to an abstraction, but a constraints check can be used only in its implementation.

• The checking of constraints occurs as part of the instantiation of the constraints-check template. Therefore, the checking may occur later than we would like. In particular, we would have preferred for a constraints check to be guaranteed to be done by the compiler at the point of the first call, but that is impossible without language changes.

• We can forget to insert a constraints check (especially for a function template).

• The compiler does not check that a template implementation uses only the properties specified in its concepts. Thus, a template implementation may pass the constraints check, yet still fail to type check.

• We do not specify semantic properties in a way that a compiler can understand (e.g., we use comments).

Adding constraints checks makes the requirements on template arguments explicit, and if a constraints check is well designed, it leads to more comprehensible error messages. If we forget to insert constraints checks, we are back to the ordinary type checking of the code generated by template instantiation. That can be unfortunate, but it is not disastrous. These constraints checks are a technique for making checking of designs based on concepts more robust, rather than an integral part of the type system.

If we want to, we can place constraints checks almost anywhere. For example, to guarantee that a particular type is checked against a particular concept, we could place constraints checks in a namespace scope (e.g., the global scope). For example:

static_assert(Ordered<std::string>,"std::string is not Ordered"); // will succeed
static_assert(Ordered<String<char>>,"String<char> is not Ordered"); // will fail

The first static_assert checks if the standard string is Ordered (it is, because it provides ==, !=, and <). The second checks if our String is Ordered (it is not, because I “forgot” to define <). Using such a global check will perform the constraints check independently of whether we actually use that particular specialization of a template in the program. Depending on our aims, that can be an advantage or a bother. Such a check forces type checking to be done at a specific point in the program; that is usually good for error isolation. Also, such checks can help unit testing. However, for programs using a number of libraries, explicit checks quickly become unmanageable.

Being Regular is an ideal for a type. We can copy objects of regular types, put them into vectors and arrays, compare them, etc. If a type is Ordered, we can also use its objects in sets, sort sequences of such objects, etc. So, we go back and improve our String to make it Ordered. In particular, we add < to provide a lexicographical ordering:

template<typename C>
bool operator<(const String<C>& s1, const String<C>& s2)
{
static_assert(Ordered<C>(),"String's character type not ordered");
bool eq = true;
for (int i=0; i!=s1.size() && i!=s2.size(); ++i) {
if (s2[i]<s1[i]) return false;
if (s1[i]<s2[i]) eq = false; // not s1==s2
}
if (s2.size()<s1.size()) return false; // s2 is shorter than s1
if (s1.size()==s2.size() && eq) return false; // s1==s2
return true;
}

24.4.1. Axioms

As in mathematics, an axiom is something we can’t prove. It is something we assume to be true. In the context of requirements for template arguments, we use “axiom” in that sense to refer to semantic properties. We use an axiom to state what a class or an algorithm assumes about its set of inputs. An axiom, however expressed, represents an algorithm’s or class’s expectations of (assumptions about) its arguments. We cannot in general test to see whether an axiom holds for values of a type (that is one reason we refer to them as axioms). Furthermore, an axiom is only required to hold for the values actually used by an algorithm. For example, an algorithm can carefully avoid dereferencing null pointers or copying a floating-point NaN. If so, it could have axioms that require pointers to be dereferenceable and floating-point values to be copyable. Alternatively, axioms can be written with the general assumption that singular values (e.g., NaN and nullptr) violate some precondition, so that they need not be considered.

C++ does not (currently) have any way of expressing axioms, but as for concepts, we can make our idea of a concept a bit more concrete than a comment or some text in a design document.

Consider how we might express some of the key semantic requirements for a type to be regular:

template<typename T>
bool Copy_equality(T x) // semantics of copy construction
{
return T{x}==x; // a copy compares equal to what it is a copy of
}

template<typename T>
bool Copy_assign_equality(T x, T& y) // semantics of assignment
{
return (y=x, y==x); // the result of an assignment compares equal to the source of the assignment
}

In other words, copy operations make copies.

template<typename T>
bool Move_effect(T x, T& y) // semantics of move
{
return (x==y ? T{std::move(x)}==y) : true) && can_destroy(y);
}

template<typename T>
bool Move_assign_effect(T x, T& y, T& z) // semantics of move assignment
{
return (y==z ? (x=std::move(y), x==z)) : true) && can_destroy(y);
}

In other words, a move operation yields a value that compares equal to whatever the source of the move operation compared equal to, and the source of the move can be destroyed.

These axioms are represented as executable code. We might use them for testing, but most importantly, we have to think harder to express them than we would have to simply write a comment. The resulting axioms are more precisely stated than would have been the case in “ordinary English.” Basically, we can express such pseudo axioms using first-order predicate logic.

24.4.2. Multi-argument Concepts

When looking at a single-argument concept and applying it to a type, it looks very much as if we are doing conventional type checking and that the concept is the type of a type. That’s part of the story, but only a part. Often, we find that relationships among argument types are essential for correct specification and use. Consider the standard-library find() algorithm:

template<typename Iter, typename Val>
Iter find(Iter b, Iter e, Val x);

The Iter template argument must be an input iterator, and we can (relatively) easily define a constraints-check template for that concept.

So far, so good, but find() depends critically on comparing x to elements of the sequence [b:e). We need to specify that comparison is required; that is, we need to state that Val and and the value type of the input iterator are equality comparable. That requires a two-argument version ofEquality_comparable:

template<typename A, typename B>
constexpr bool Equality_comparable(A a, B b)
{

return Common<T, U>()
&& Totally_ordered<T>()
&& Totally_ordered<U>()
&& Totally_ordered<Common_type<T,U>>()
&& Has_less<T,U>() && Boolean<Less_result<T,U>>()
&& Has_less<U,T>() && Boolean<Less_result<U,T>>()
&& Has_greater<T,U>() && Boolean<Greater_result<T,U>>()
&& Has_greater<U,T>() && Boolean<Greater_result<U,T>>()
&& Has_less_equal<T,U>() && Boolean<Less_equal_result<T,U>>()
&& Has_less_equal<U,T>() && Boolean<Less_equal_result<U,T>>()
&& Has_greater_equal<T,U>() && Boolean<Greater_equal_result<T,U>>()
&& Has_greater_equal<U,T>() && Boolean<Greater_equal_result<U,T>>();
};

This is rather verbose for a simple concept. However, I wanted to be explicit about all of the operators and about the symmetry of their use rather than burying the complexity in a generalization.

Given that, we can define find():

template<typename Iter, typename Val>
Iter find(Iter b, Iter e, Val x)
{
static_assert(Input_iterator<Iter>(),"find() requires an input iterator");
static_assert(Equality_comparable<Value_type<Iter>,Val>(),
"find()'s iterator and value arguments must match");

while (b!=e) {
if (*b==x) return b;
++b;
}
return b;
}

Multi-argument concepts are particularly common and useful when specifying generic algorithms. This is also the area where you find the greatest number of concepts and the greatest need to specify new concepts (as opposed to picking “standard ones” from a catalog of common concepts). The variations among well-defined types appear to be somewhat more limited than the variations among algorithms’ requirements on their arguments.

24.4.3. Value Concepts

Concepts can express arbitrary (syntactic) requirements on a set of template arguments. In particular, a template argument can be an integer value, so concepts can take integer arguments. For example, we can write a constraints check to test that a value template argument is small:

template<int N>
constexpr bool Small_size()
{
return N<=8;
}

A more realistic example would be a concept for which the numeric argument was just one among others. For example:

constexpr int stack_limit = 2048;

template<typename T,int N>
constexpr bool Stackable() // T is regular and N elements of T can fit on a small stack
{
return Regular<T>() && sizeof(T)*N<=stack_limit;
}

This implements a notion of “small enough to be stack allocated.” It might be used like this:

template<typename T, int N>
struct Buffer {
// ...
};

template<typename T, int N>
void fct()
{
static_assert(Stackable<T,N>(),"fct() buffer won't fit on stack");
Buffer<T,N> buf;
// ...
}

Compared to the fundamental concepts for types, value concepts tend to be small and ad hoc.

24.4.4. Constraints Checks

The constraints checks used in this book can be found on the book’s support site. They are not part of a standard, and I hope that in the future they will be replaced by a proper language mechanism. However, they can be useful for thinking about template and type design and reflect the de facto concepts in the standard library. They should go in a separate namespace to avoid interfering with possible future language features and alternative implementations of the idea of concepts. I use namespace Estd, but that may be an alias (§14.4.2). Here are a few constraints checks that you might find useful:

• Input_iterator<X>: X is an iterator that we can use only once to traverse a sequence (forward using ++), reading each element once only.

• Output_iterator<X>: X is an iterator that we can use only once to traverse a sequence (forward using ++), writing each element once only.

• Forward_iterator<X>: X is an iterator that we can use to traverse a sequence (forward using ++). This is what a singly-linked list (e.g., forward_list) naturally supports.

• Bidirectional_iterator<X>: X is an iterator that we can move both forward (using ++) and backward (using ––). This is what a doubly-linked list (e.g., list) naturally supports.

• Random_access_iterator<X>: X is an iterator that we can use to traverse a sequence (forward and backward) and to randomly access elements using subscripting and positioning using += and –=. This is what an array naturally supports.

• Equality_comparable<X,Y>:An X can be compared with a Y using == and !=.

• Totally_ordered<X,Y>: X and Y are Equality_comparable and an X can be compared with a Y using <, <=, > and >=.

• Semiregular<X>: Xs can be copied, default constructed, allocated on the free store, and are free of minor annoying technical restrictions.

• Regular<X>: Xs are Semiregular and can be compared using equality. The standard-library containers require their elements to be regular.

• Ordered<X>: Xs are Regular and Totally_ordered. The standard-library associative containers require their elements to be ordered unless you explicitly provide a comparison operation.

• Assignable<X,Y>:A Y can be assigned to an X using =.

• Predicate<F,X>:An F can be called for an X yielding a bool.

• Streamable<X>:An X can be read and written using iostreams.

• Movable<X>: An X can be moved; that is, it has a move constructor and a move assignment. In addition, an X is addressable and destructible.

• Copyable<X>:An X is Movable and can also be copied.

• Convertible<X,Y>:An X can be implicitly converted to a Y.

• Common<X,Y>: An X and a Y can unambiguously be converted to a common type called Common_type<X,Y>. This is a formalization of the language rule for compatibility of operands to ?: (§11.1.3). For example, Common_type<Base*,Derived*> is Base* andCommon_type<int,long> is long.

• Range<X>: An X that can be used by a range-for (§9.5.1), that is, X must provide members, x.begin() and x.end(), or nonmember equivalents, begin(x) and end(x), with the required semantics.

Obviously, these definitions are informal. In most cases, these concepts are based on standard-library type predicates (§35.4.1), and the ISO C++ standard provides formal definitions (e.g., §iso.17.6.3).

24.4.5. Template Definition Checking

A constraints-check template ensures that a type provides the properties required by the concept. If the implementation of a template in fact uses more properties than its concepts guarantee, we may get type errors. For example, the standard-library find() requires a pair of input iterators as arguments, but we might (incautiously) have defined it like this:

template<typename Iter, typename Val>
Iter find(Iter b, Iter e, Val x)
{
static_assert(Input_iterator<Iter>(),"find(): Iter is not a Forward iterator");
static_assert(Equality_comparable<Value_type<Iter>,Val>),
"find(): value type doesn't match iterator");

while (b!=e) {
if (*b==x) return b;
b = b+1; // note: not ++b
}
return b;
}

Now, b+1 is an error unless b is a random-access iterator (and not just a forward iterator as ensured by the constraints check). However, the constraints check does not help us detect that problem. For example:

void f(list<int>& lst, vector<string>& vs)
{
auto p = find(lst.begin(),lst.end(),1209); // error: list does not provide +
auto q = find(vs.begin(),vs.end(),"Cambridge"); // OK: vector provides +
// ...
}

The call of find() for the list will fail (because + is not defined for the forward iterator provided by list) and the call for the vector will succeed (because b+1 is fine for vector<string>::iterator).

Constraints checks primarily provide a service to the user of a template: the actual template arguments are checked against the template’s requirements. On the other hand, constraints checks do not help a template writer who would like to be sure that the implementation doesn’t use any properties beyond those specified in the concepts. Ideally, the type system would ensure that, but that requires language features that are still in the future. So, how do we test the implementation of a parameterized class or a generic algorithm?

Concepts provide a strong guideline: the implementation should use no property of an argument that isn’t specified by the concepts, so we should test the implementation with arguments that provide the properties specified by the implementation’s concepts, and only those. Such a type is sometimes called an archetype.

So, for the find() example, we look at Forward_iterator and Equality_comparable or at the standard’s definition of the forward-iterator and equal-comparable concepts (§iso.17.6.3.1, §iso.24.2.5). Then, we decide that we need an Iterator type that provides at least:

• A default constructor

• A copy constructor and a copy assignment

• Operators == and !=

• A prefix operator ++

• A type Value_type<Iterator>

• A prefix operator *

• The ability to assign the result of * to a Value_type<Iterator>

• The ability to assign a Value_type<Iterator> to the result of *

This is slightly simplified from the standard-library forward iterator, but sufficient for find(). Constructing that list by looking at the concepts is easy.

Given this list, we need to find or define a type that provides only the desired features. For a forward iterator, as needed by find(), the standard-library forward_list fits the bill perfectly. This is because “forward iterator” was defined to express the idea of something that allows us to iterate through a singly-linked list. It is not uncommon that a popular type is an archetype for a popular concept. If we decide to use an existing type, we have to be careful, though, not to pick a type that is more flexible than required. For example, the typical mistake when testing algorithms, such as find(), is to use a vector. However, the very generality and flexibility that make vector so popular make it unusable as an archetype for many simple algorithms.

If we can’t find an existing type that fits our needs, we must define one ourselves. That is done by going through the list of requirements and defining suitable members:

template<typename Val>
struct Forward { // for checking find()
Forward();
Forward(const Forward&);
Forward operator=(const Forward&);
bool operator==(const Forward&);
bool operator!=(const Forward&);
void operator++();
Val& operator*(); // simplified: does not handle a proxy for Val
};

template<typename Val>
using Value_type<Forward<Val>> = Val; // simplified; see §28.2.4

void f()
{
Forward<int> p = find(Forward<int>{},Forward<int>{},7);
}

At this level of testing, we need not check that these operations actually implement the right semantics. We just check that the template implementation does not rely on properties that it should not.

Here, I have simplified the testing by not introducing an archetype for the Val argument. Instead, I simply used int. Testing nontrivial conversions between an archetype for Val and an archetype for Iter would be significantly more work and most likely not particularly useful.

Writing a test harness that checks the implementation of find() against std::forward_list or X is not trivial, but it is not among the most difficult tasks facing a designer of generic algorithms. Using a relatively small and well-specified set of concepts makes the task manageable. The tests can and should be completely compile-time.

Note that this simple specification and checking strategy leads to find() requiring its iterator argument to have a Value_type type function (§28.2). That allows pointers to be used as iterators. For many template parameters it is important that built-in types can be used as well as user-defined types (§1.2.2, §25.2.1).

24.5. Advice

[1] A template can pass argument types without loss of information; §24.1.

[2] Templates provide a general mechanism for compile-time programming; §24.1.

[3] Templates provide compile-time “duck typing”; §24.1.

[4] Design generic algorithms by “lifting” from concrete examples; §24.2.

[5] Generalize algorithms by specifying template argument requirements in terms of concepts; §24.3.

[6] Do not give unconventional meaning to conventional notation; §24.3.

[7] Use concepts as a design tool; §24.3.

[8] Aim for “plug compatibility” among algorithms and argument type by using common and regular template argument requirements; §24.3.

[9] Discover a concept by minimizing an algorithm’s requirements on its template arguments and then generalizing for wider use; §24.3.1.

[10] A concept is not just a description of the needs of a particular implementation of an algorithm; §24.3.1.

[11] If possible, choose a concept from a list of well-known concepts; §24.3.1, §24.4.4.

[12] The default concept for a template argument is Regular; §24.3.1.

[13] Not all template argument types are Regular; §24.3.1.

[14] A concept requires a semantic aspect; it is not primarily a syntactic notion; §24.3.1, §24.3.2, §24.4.1.

[15] Make concepts concrete in code; §24.4.

[16] Express concepts as compile-time predicates (constexpr functions) and test them using static_assert() or enable_if<>; §24.4.

[17] Use axioms as a design tool; §24.4.1.

[18] Use axioms as a guide for testing; §24.4.1.

[19] Some concepts involve two or more template arguments; §24.4.2.

[20] Concepts are not just types of types; §24.4.2.

[21] Concepts can involve numeric values; §24.4.3.

[22] Use concepts as a guide for testing template definitions; §24.4.5.