# 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 **int**s, **complex<double>**s, or**Matrix**es. 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;

}

double s {0};

for (int i = 0; i<n; ++i)

s = s + array[i];

return s;

}

Obviously, this computes the sum of the **double**s 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;

}

int s = 0;

while (first!=last) {

s += first–>data;

first = first–>next;

}

return s;

}

This computes the sum of the **int**s in the singly-linked list implemented by the **Node**s.

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, typenameVal 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 **int**s and **double**s. 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] **C**s are copied by copy assignment and copy initialization.

[2] **String** compares **C**s using **==** and **!=**.

[3] **String** makes arrays of **C**s (that implies default construction of **C**s).

[4] **String** takes the address of **C**s.

[5] **C**s are destroyed when a **String** is destroyed.

[6] **String** has **>>** and **<<** operators that somehow must read and write **C**s.

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 as**std::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 **const**s 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 **C**s 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 **String**s 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);

};

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 term*constraints 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>>();

}

&& 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 **vector**s 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; //

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; //

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) //

bool Copy_assign_equality(T x, T& y) //

*semantics of assignment*

**{**

return (y=x, y==x); //

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) //

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);

}

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 of**Equality_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;

}

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;

//

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>: X**s can be copied, default constructed, allocated on the free store, and are free of minor annoying technical restrictions.

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

• **Ordered<X>: X**s 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*** and**Common_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;

}

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*(); //

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; //

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);

}

{

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*.