Author:
Table of contents:
Introduction
This tutorial illustrates how the addition of concepts into C++
makes writing and using templates easier, by improving
type-checking and error messages for templates. We follow the
methodology of
Generic Programming,
which focuses on starting with a concrete (non-templated) algorithm
and then slowly introducing template parameters to make it more
generic. If you would like to follow this tutorial with the aid of a ConceptC++ compiler, we suggest that you download the most recent version of
ConceptGCC.
This tutorial is an introduction to concepts. The Google Tech
Talk Concepts:
Extending the C++ Template System for Generic Programming provides
a different introduction to Generic Programming and the concepts
language features. To really dig into concepts, refer to the complete
concepts
proposal, N2081:
Concepts (Revision 1).
Data type abstraction
In this tutorial, we will begin with a simple function
sum that adds an array of numbers:
double sum(double array[], int n)
{
double result = 0;
for (int i = 0; i < n; ++i)
result = result + array[i];
return result;
}
The first step in the Generic Programming process is to abstract
away the data types used in the algorithm. In this case, we have
unnecessarily restricted ourselves by permitting only
double values to be added. Thus, our first step is to
create a template parameter T and use it in place of
double.
template<typename T>
T sum(T array[], int n)
{
T result = 0;
for (int i = 0; i < n; ++i)
result = result + array[i];
return result;
}
This first version of a generic sum algorithm appears at first
glance to be sufficient, especially when sanity checking the
template argument T with a builtin type such as double. However,
all is not well under the surface: there are implicit assumptions
that result in errors when compiling user-defined types, as
illustrated in the example below.
struct pod
{
int i;
};
int main()
{
pod values[3] = { {1}, {2}, {3} };
sum(values, 3);
return 0;
}
dgregor@zarquon> conceptg++ array1-1.C
array1-1.cc: In function 'T sum(T*, int) [with T = pod]':
array1-1.cc:19: instantiated from here
array1-1.cc:5: error: conversion from 'int' to non-scalar type 'pod' requested
array1-1.cc:7: error: no match for 'operator+' in 'result + *((+(((unsigned int)i) * 4u)) + array)'
At this point, there are a couple of notable observations.
- The first attempt at a generic sum function has some
problems, however these problems are only found by chance, when
using a type that was unexpected, and requiring the sum function to
be instantiated, not merely compiled. Wouldn't it be nicer to know,
in advance and without instantiation, that problems existed?
- It is not immediately apparent how to fix this error, or how
to best make the proposed sum function correct.
In order to solve these issues, we want to place concept
requirements on the template parameter T. To do so,
we include a new header <concepts>,
and state that T must be CopyConstructible, i.e., it must have a copy constructor. The
resulting sum function looks like this:
#include <concepts>
template<std::CopyConstructible T>
T sum(T array[], int n)
{
T result = 0;
for (int i = 0; i < n; ++i)
result = result + array[i];
return result;
}
By replacing typename T with std::CopyConstructible
T, we have done two things. First, we have changed our
"normal" C++ template into a constrained ConceptC++
template, which means that the compiler will fully type-check its
definition. Second, we have stated that the type T meets
the requirements of the CopyConstructible concept. Let's compile this example to see what
happens:
dgregor@zarquon> conceptg++ array2.C
array2.cpp: In function 'T sum(T*, int)':
array2.cpp:5: error: conversion from 'int' to non-scalar type 'T' requested
array2.cpp:7: error: no match for 'operator+' in 'result + array[i]'
First off, note that the compiler is now informing us of errors in
the sum function during compilation, even without instantiating the
sum function with a specific type. In addition, it is
informing us that we have attempted to use the template
parameter T in ways that it might not work. For
instance, T might not have a constructor that takes
an int or have an operator +. To remedy these
problems, we need to introduce requirements, which state in what ways
objects of type T can be manipulated, just like we introduced
the CopyConstructible requirement earlier.
Requirements are written as part of concepts: one can think
of concepts as, simply, a bunch of requirements stuck together under a
single name. In this case, we want to create a requirement that states
that two T values can be added with +. So, we write
an Addable concept like this:
auto concept Addable<typename T> {
T operator+(T x, T y);
};
Concepts are a little bit like class templates. They have some type
parameters, for which they express requirements. They also
have signatures, which are essentially declarations that state
what functions the data types must support. In this case, the only
signature is for
operator+, which takes two T
parameters and returns a T. The auto preceding
concept means that this is an implicit concept;
we'll revisit implicit concepts later. For now, we want to
actually say that the T in our sum function meets
the requirements of the Addable concept, so we put
Addable<T> into a new clause called the
the requirements clause:
template<std::CopyConstructible T>
requires Addable<T>
T sum(T array[], int n)
{
T result = 0;
for (int i = 0; i < n; ++i)
result = result + array[i];
return result;
}
Like std::CopyConstructible T, the contents of
the requirements clause say something about the things that we can
do with a T. By writing Addable<T> in
the requirements clause, we say that T must meet the
requirements of the Addable concept, i.e,, it must have a
suitable operator+. Now, we try to compile this new function:
array3.cpp: In function 'T sum(T*, int)':
array3.cpp:10: error: conversion from 'int' to non-scalar type 'T' requested
array3.cpp:12: error: no match for 'operator=' in 'result = Addable<T>::operator+(result, array[i])'
The error message about the missing operator+ is gone!
However, another error message has replaced it: the type T
might not have an assignment operator. So, we write another concept
Assignable that contains a signature for the assignment
operator:
auto concept Assignable<typename T> {
T& operator=(T& x, T y);
};
Next, we introduce an Assignable requirement into the
requirements clause. Note that the requirements clause can have
multiple requirements, separated by commas, because both the
requirements of the Addable concept and
the Assignable concept are important:
template<std::CopyConstructible T>
requires Addable<T>, Assignable<T>
T sum(T array[], int n)
{
T result = 0;
for (int i = 0; i < n; ++i)
result = result + array[i];
return result;
}
We're down to a single error message, now:
array4.cpp: In function 'T sum(T*, int)':
array4.cpp:14: error: conversion from 'int' to non-scalar type 'T' requested
This error comes from the initialization of result to
0. We have several options at this point. First, we could introduce
another concept that captures the syntax "can be initialized by an
integer", e.g.
auto concept IntConstructible<typename T> {
T::T(int);
};
Or, we could create a signature for an
identity_element function in a concept (say,
a Monoid concept, for the mathematically inclined), and call
that function instead of using 0. However, we're going to use
the same methodology employed by the C++ Standard Library's
accumulate function, and pass the initial value as a
parameter:
template<std::CopyConstructible T>
requires Addable<T>, Assignable<T>
T sum(T array[], int n, T result)
{
for (int i = 0; i < n; ++i)
result = result + array[i];
return result;
}
Finally, the entire routine type-checks! We have completely
removed any dependence on the data type double. Now, for
any type T that meets the requirements of the
Addable and Assignable concepts, the sum
function is guaranteed to work. In Generic Programming parlance,
when a type meets the requirements of a concept it is said to
model that concept. Similary, a model of a concept is
a set of data types that meets the requirements of the concept.
Let's review what we did. First, we replaced concrete data types
with template parameters, and added in an initial concept
constraint, CopyConstructible, to enable
type-checking. Then, we added concept requirements to
the requirements clause, creating concepts as needed, until our
function template type-checks properly. For this small routine, we
required two concepts, Addable and Assignable however, these concepts will be reused in
many other generic functions. You can follow the links from the
concept names to see the actual definitions of these concepts used in
the ConceptC++ standard library.
Abstracting iteration
The sum function only allows summation over an entire
array. In this section, we abstract our sum function
further, to allow arbitrary sequences of data to be added together.
We start by replacing our array with a set of pointers, e.g.,
template<std::CopyConstructible T>
requires Addable<T>, Assignable<T>
T sum(T* first, T* last, T result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}
This algorithm type-checks without any problems, so we move on to
generalize from pointers to iterators. An iterator is an
abstract representation of a position into some kind of sequence,
regardless of how that sequence is stored. We'll create a
simple ForwardIterator concept that is similar to the one in
the C++ standard library.
The major operations an iterator must be able to perform are (1)
increment, (2) dereference, and (3) compare against the end of the
sequence. We will place all of these requirements in a new concept
ForwardIterator, which looks like this:
concept ForwardIterator<typename Iter> {
typename value_type;
Iter& operator++(Iter& x);
value_type& operator*(Iter);
bool operator==(Iter, Iter);
bool operator!=(Iter, Iter);
};
This concept introduces the notion of
associated types.
Associated types are types that are part of a concept, but are not
necessarily parameters to the concept. In this case, the
value_type of the iterator is the type of data that is
pointed to by the iterator. The rest of the concept uses
signatures to describe iterator increment, dereference, and
comparison; note that we use value_type as needed, e.g.,
for the dereference operation. For users familiar with the idea of
traits, iterator_traits in particular, concepts
subsume the role of traits, providing concept types and operations for
models. Our new ForwardIterator concept can be used to make
our sum() function more generic:
template<ForwardIterator Iter>
requires Addable<Iter::value_type>, Assignable<Iter::value_type>
Iter::value_type sum(Iter first, Iter last, Iter::value_type result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}
We used the new ForwardIterator concept instead of
pointers, replacing each occurence of T* with a
new, ForwardIterator Iter. Since we no longer
have T as a template parameter, we instead
use Iter::value_type. The name Iter::value_type
refers to the value type of the type Iter when it is acting
as a ForwardIterator. If we wanted to be very explicit
about which value_type we're interested in, we could
equivalently write ForwardIterator<Iter>::value_type.
This new sum function still type-checks properly, but a
call to it with two double pointers will fail, because there
is no way that the compiler could know that pointers are iterators, or
determine what the value_type for a pointer is. So, we
introduce a concept map, which illustrates how a set of types
will model a particular concept. We therefore define a concept map for
of ForwardIterator that makes every double pointer into a ForwardIterator:
concept_map ForwardIterator<double*> {
typedef double value_type;
};
Concept maps state how a particular type (or set of types) meet the
requirements of a concept. Every concept map must meet all of the
requirements of its corresponding concept. In the case
of ForwardIterator, this means that we need a definition for
the associated type value_type (which we satisfy explicitly
with the value_type typedef in the concept map) and
for the operators ++, *, ==,
and != (which are satisfied implicitly, using the built-in
operators for pointers).
With the Addable and Assignable concepts, we
never had to write a model declaration, because they were declared
as auto concepts. The ForwardIterator concept,
however, was not declared with the auto specifier, so the
user must write concept maps. For instance, what if the user now wants
to use int pointers with our sum algorithm? They
could write a concept map ForwardIterator<int*>, but
there is a better way: concept map templates.
template<typename T>
concept_map ForwardIterator<T*> {
typedef T value_type;
};
Like many other constructs in C++, one can create a concept map
template. This particular concept map template states that
for any type T, T* is
a ForwardIterator with value_type T. Thus,
there will not be any need to define concept maps for any other type
of pointer.
When should one use auto concepts and when should
model declarations be required? Our simple rule is this: if the
requirements of a concept are purely syntactic, for instance
because we're only saying that we can add two types, then it should
be an auto concept. However, if the operations have
semantics associated with them, for instance the movement of
iterators, concept maps should be required. This is
particularly important when concept refinement is used: for
instance, one may have an InputIterator and
MultiPassInputIterator concepts that have identical
syntax, but the latter implies that one can make multiple passes
through the same sequence. If syntactic matching alone is used, a
type that is semantically an InputIterator could be
assumed to be a MultiPassInputIterator, causing run-time
failues.
Mapping concept syntax with concept maps
Concept maps are permitted to adapt the syntax of data
types involved in the concept map to the syntax of the concept. For
instance, say we want to use sum to mix a bunch of colors
together. Colors are represented by the Color class, which
does not support operator+:
class Color {
public:
Color();
Color mix(const Color& other) const;
// ...
};
When we call sum, we don't want to add colors together,
we want to mix them. We could just add an
operator+ that calls mix, but then we would bloat
the interface of Color just to use a generic algorithm.
Instead, we define a concept_map Addable<Color> that shows
how Color meets the requirements of the Addable concept.
concept_map Addable<Color> {
Color operator+(const Color& x, const Color& y) { return x.mix(y); }
};
This concept map states that Color meets the requirements
of the
Addable concept, but provides an alternate implementation
of the concept's operator+. Thus, when sum is
instantiated with T=Color,
Addable<Color>::operator+ is used, so sum
will mix colors properly. It may be interesting to step
through the program in a debugger, to see how the operators and
functions used in the template become calls into the concept map.
Concept maps are truly maps that state how the syntax of existing
data types can be mapped to the syntax expected by
concepts, without changing the existing data types. This
feature, called retroactive modeling is one of the
most important features of ConceptC++.
Abstracting operations
Our sum function is already very generic and reusable. It
can apply to many different data types (integers, floating-point
values, strings, etc.) and different representations of data (arrays,
vectors, lists, sets). However, we can lift the algorithm further by allowing the type of result to
differ from the type of Iter::value_type, so that we can, for
instance, add characters to a string or add elements to a set, so long
as the
+ operation is defined well.
The first step we'll take is to create a new template parameter
type T for result. We know this type needs to be
Assignable, so let's take a first stab at the new
sum function:
template<ForwardIterator Iter, Assignable T>
requires Addable<T>
T sum(Iter first, Iter last, T result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}
Trying to compile this with ConceptGCC results in the following
error message:
op1.cpp: In function 'T sum(Iter, Iter, T)':
op1.cpp:26: error: no match for 'operator+' in 'result + * first'
op1.cpp:3: note: candidates are: T Addable<T>::operator+(const T&, const T&)
The compiler informs us that it knows how to add T
objects, but our code is attempting to add a Iter::value_type to
a T. To remedy this, we'll make Addable a
two-parameter concept. Concepts can take one or more parameters,
and like templates those parameters can have defaults. So, our new
Addable can work like the old one, if a single parameter
is provided, but also allows us to express the requirement we need:
adding a value_type to a T and getting a
T back:
auto concept Addable<typename T, typename U = T> {
T operator+(T x, U y);
};
Finally, we change the Addable requirement in
sum to use the new parameter:
template<ForwardIterator Iter, Assignable T>
requires Addable<T, value_type>
T sum(Iter first, Iter last, T result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}
That's it! Our new generic function can do everything that it
could do before, but now the type of result can be
different from Iter::value_type. The interested reader may try
to lift sum one step further, by replacing the use of
+ with a call to a function object. You'll probably need
to create a new concept for function objects and add some
requirements to the new sum. If you get stuck, check out the
ConceptC++ Concept Web for ideas.
Conclusion and review
This tutorial has introduced the basic ideas of Generic Programming
with with ConceptC++. The Generic Programming process starts always
with concrete, non-generic algorithms. We then lift away requirements, introducing template parameters to
replace concrete types and making the algorithm more reusable in the
process. Then we write down the requirements that we place on these
template parameters, in the form of concepts. Using a ConceptC++ compiler such as ConceptGCC, we can check
at each step that our lifting was correct, and that we've captured all
of the real requirements.
Generic Programming also focuses on the reuse of concepts. If we
were to write a different algorithm, e.g., one that counts the
elements in a sequence, we should reuse as many concepts as we can.
The concepts in the C++ Standard Library are a great example: there
are only twenty or so concepts in the C++ standard library, that can
be used with many algorithms and containers.
There is much more to explore in Generic Programming, Concepts for
C++, and ConceptGCC. Please see the our publications, the
ConceptC++
specification, or the ConceptC++
Concept Web for more details. If you have any questions or
comments on this tutorial, ConceptC++, or ConceptGCC, please send them
to Douglas Gregor at .
Thanks to Kyle Ross and Benjamin Kosnik for their helpful
comments on this tutorial.
|