Concepts
Douglas Gregor
Concepts
Nested Requirements
Associated Types
Refinement
Concepts bundle together coherent sets of requirements into
a single entity. Concepts describe a family of related abstractions
based on what those abstractions can do. For instance,
an Iterator concept would describe abstractions that
iterate over sequences of values (such as a pointer),
a Socket concept would describe abstractions that
communicate data over a network (such as an IPv6 socket), and
a Polygon concept would describe abstractions that are
closed plane figures (such triangles and octagons).
Concepts are neither designed nor invented. They are discovered
through the process of lifting many algorithms within the same
domain. The result of the lifting process is a generic algorithm and
a set of requirements. The following was the result of lifting
the sum algorithm from the prior section:
// Requirements:
// T must have an additive operator +
// T must have an assignment operator
// T must have a copy constructor
// I must have an inequality operator !=
// I must have a copy constructor
// I must have an assignment operator
// I must have an operation next() that moves to the next value in the sequence
// I must have an operation get() that returns the current value (of type T).
template<typename I, typename T>
T sum(I start, I end, T init) {
for (I current = start; current != end; current = next(current))
init = init + get(current);
return init;
}
There are many ways that these requirements can be packaged into
one or more concepts. At one end of the spectrum, we could create
the Sum concept, which contains the entire list of
requirements. At the other end, each requirement could stay within
its own concept. In general, the correct answer is somewhere in
between: a concept should have enough requirements that it gives
some common identity to the abstractions it describes, but should
not contain so many requirements that the family of abstractions is
unnecessarily restricted.
When we want to package requirements into concepts, we again rely
on the lifting process. However, this time we look at the
requirements across many different algorithms. For instance, the
following example illustrates the result of lifting an
algorithm find that searches for a value in a sequence:
// Requirements:
// T must have an equality operator ==
// T must have a copy constructor
// I must have an inequality operator !=
// I must have a copy constructor
// I must have an assignment operator
// I must have an operation next() that moves to the next value in the sequence
// I must have an operation get() that returns the current value (of type T).
template<typename I, typename T>
I find(I start, I end, T value) {
for (I current = start; current != end; current = next(current))
if (get(current) == value)
return current;
return end;
}
Comparing the requirement sets from find()
and sum(), we see quite a few similarities and some notable
differences. For instance, the requirement for operator+ on
values of type T is only present in sum(), whereas
the requirement for operator== is only present
in find(). However, both sum() and find()
have the requirement for a copy constructor on T, and can
therefore use the same concept to represent that requirement. Moving
to the requirements on I, we see that they are identical in
both algorithms. Therefore, all of the requirements on I
can be encapsulated into a single concept, which we will call
the Iterator concept. The following table groups
requirements into preliminary concepts. We use the
notation ConceptName<T1, T2, ..., TN> to say
that we're placing the requirements associated
with ConceptName on the types T1, T2,
..., TN. When there is only one type T,
we often simply say "T is a ConceptName".
Concept  Requirements 
CopyConstructible<T> 
T must have a copy constructor 
Assignable<T> 
T must have an assignment operator 
Addable<T> 
T must have an operator+ that takes
two T values and returns a T 
EqualityComparable<T> 
T must have an operator== comparing
two Ts and returning a bool.
T must have an operator!= comparing
two Ts and returning a bool. 
Iterator<I, T> 
I must have an operator== comparing
two Is and returning a bool.
I must have an operator!= comparing
two Is and returning a bool.
I must have a copy constructor.
I must have an assignment operator.
I must have an operation next() that moves to the next value in the sequence.
I must have an operation get() that returns the current value (of type T). 
Using the concept descriptions above, we can drastically simplifiy
the specification of the requirements of sum()
and find(), to:
// Requirements: Addable<T>, Assignable<T>, CopyConstructible<T>, Iterator<I, T>
template<typename I, typename T>
T sum(I start, I end, T init);
// Requirements: EqualityComparable<T>, Assignable<T>, CopyConstructible<T>,
// Iterator<I, T>
template<typename I, typename T>
I find(I start, I end, T value);
By bundling related requirements into concepts, we can simplify the
expression of the requirements on algorithms and give some identity to
the abstractions. Type I is an iterator, type T
is Addable, etc. Concepts also illustrate the relationships
between algorithms: both sum() and find() operate on
a single sequence of values to compute a result.
Nested Requirements
Our preliminary table of concepts has some unnecessary redundancy
in it. For instance, the iterator concept has operators ==
and !=, along with a copy constructor, that have already been
specified in other concepts. We can reuse those prior concepts in the
definition of other concepts, by way of nested requirements. A
nested requirement is when a concept references another concept as one
of its own requirements, e.g., the Iterator<I, T>
concept requires EqualityComparable<I>. Using nested
requirements, we can update the Iterator concept as
follows:
Concept  Requirements 
Iterator<I, T> 
EqualityComparable<I>,
CopyConstructible<I>,
Assignable<I>
I must have an operation next() that moves to the next value in the sequence.
I must have an operation get() that returns the current value (of type T). 
Associated Types
Trying to use concepts to aid in the lifting of more algorithms is
the best way to uncover weaknesses in the concept requirements. In
the case of the Iterator concept, it's actually a
completely trivial algorithm that uncovers the first problem:
the distance() function, which computes the length of a
sequence.
// Requirements: Iterator<I, T>
template<typename I, typename T>
int distance(I start, I end) {
int i = 0;
for (; start != end; ++start)
++i;
return i;
}
The problem with distance() is that it is hard to
use. Since there is no reference to T anywhere in the
function signature, users are forced to provide the type T
(i.e., the type returned by get()), even though it is never
used. Providing one extra type is a mere inconvenience, but as
concepts become more involved, with many extra types, this
inconvenience becomes a serious problem.
Associated types address the problem of having too many
parameters to concepts by allowing certain types to be stored inside
the concept definition. These types are always available when needed,
but they aren't used to specify the concept. For instance, the type
returned by an iterator's get() function (which we've been
calling T) can be made into an associated type we'll
call value_type. Generic algorithms can use
the value_type of an iterator, but when they don't need it,
they won't have to specify it. An updated Iterator concept
follows. Note in particular that we have eliminated the
type T from Iterator<I, T>.
Concept  Requirements 
Iterator<I> 
EqualityComparable<I>,
CopyConstructible<I>,
Assignable<I>
I must have an operation next() that moves to the next value in the sequence.
value_type is an associated type, accessible via iterator_traits<I>::value_type
I must have an operation get() that returns the current value (of type value_type). 
Using this new definition of Iterator, we can express
the distance() algorithm more simply:
// Requirements: Iterator<I>
template<typename I>
int distance(I start, I end) {
int i = 0;
for (; start != end; ++start)
++i;
return i;
}
In C++, associated types are stored in class templates
called traits. Traits are auxiliary class templates that can
be specialized to retrieve the associated types for a particular use
of the concept. For instance, the value_type of an iterator
can be accessed via the iterator_traits data structure. The
following implementation of sum(), for instance,
uses iterator_traits to access the value_type.
// Requirements: Iterator<I>, Addable<value_type>, Assignable<value_type>,
CopyConstructible<value_type>
template<typename I>
typename iterator_traits<T>::value_type
sum(I start, I end, typename iterator_traits<T>::value_type init) {
for (I current = start; current != end; current = next(current))
init = init + get(current);
return init;
}
Associated traits for a type can be specified through
C++ specialization. For instance, the following class
template partial specialization states that the value_type
of a pointer T* (which is an iterator) is T:
template<typename T>
struct iterator_traits<T*> {
typedef T value_type;
};
Refinement
Nested requirements allow us to
reuse concepts to describe other concepts. Nested requirements can
express arbitrary concept requirements, but often we need a much
more specific, hierarchical relationship. Concept refinement
describes a hierarchical relationship between two concepts. If a
concept C2 refines a concept C1,
then C2 includes all of the requirements of C1 and
adds its own new requirements. So every C2 is also
a C1, but C2 is more specific, and presumably
enables more and better algorithms.
Consider the Iterator concept that we have devised so
far. It permits forward movement and reading each value. However,
what if we want to change a value or move backwards? If we added
these two operations, set and prev,
to Iterator, we could implement a reverse()
algorithm that reverses the elements in a sequence. However, instead
of making Iterator larger, we will create a new
concept BidirectionalIterator
that refines Iterator but adds these two
operations:
Concept  Requirements 
BidirectionalIterator<I> 
Refines Iterator<I>
I must have an operation prev() that moves to the previous value in the sequence.
I must have an operation set() that sets the current value. 
Using this new concept, we can express the reverse
algorithm:
// Requirements: BidirectionalIterator<BI>, Assignable<value_type>, CopyConstructible<value_type>
template<typename BI>
void reverse(BI start, BI end) {
while (start != end) {
end = prev(end);
if (start == end)
break;
// Swap the values
typename iterator_traits<BI>::value_type tmp = get(start);
set(start, get(end));
set(end, tmpl);
start = next(start);
}
}
Every BidirectionalIterator is an Iterator, but
the inverse is not necessarily true: an Iterator into a
singlylinked list, for instance, can modify values (set()
requirement) but cannot move backwards
(prev()). Similarly, an iterator into a
doublylinked list of constant values can move backwards but cannot
change values.
Careful lifting of many generic algorithms will unveil the correct
packaging of requirements into concepts, and the hierarchical
relationships among concepts as expressed through refinement. The
careful analysis of
the Standard
Template Library resulted in the following iterator concept
relationships, where an arrow C2 > C1
indicates that C2 refines C1. When we have a
number of concepts arranged together in one or more concept
hierarchies, we refer to the result as a concept taxonomy.
