An Introduction to Generic Programming

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
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
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 ConceptNameN> 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".

Using the concept descriptions above, we can drastically simplifiy the specification of the requirements of sum() and find(), to:

// Requirements: Addable, Assignable, CopyConstructible, Iterator
template
T sum(I start, I end, T init);
// Requirements: EqualityComparable, Assignable, CopyConstructible, 
//               Iterator
template
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 concept requires EqualityComparable. Using nested requirements, we can update the Iterator concept as follows:

Concept	Requirements
Iterator	EqualityComparable, CopyConstructible, Assignable 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
template
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.

Concept	Requirements
Iterator	EqualityComparable, CopyConstructible, Assignable 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::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
template
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, Addable, Assignable,
                 CopyConstructible
template
typename iterator_traits::value_type 
sum(I start, I end, typename iterator_traits::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
struct iterator_traits {
  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	Refines Iterator 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, Assignable, CopyConstructible
template
void reverse(BI start, BI end) {
  while (start != end) {  
    end = prev(end);
    if (start == end)
      break;
    // Swap the values
    typename iterator_traits::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 singly-linked list, for instance, can modify values (set() requirement) but cannot move backwards (prev()). Similarly, an iterator into a doubly-linked 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.

Previous: Lifting

Author: Douglas Gregor

Next: Models