ConceptC++ Tutorial

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.

  1. 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?
  2. 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 
templateCopyConstructible 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 into a new clause called the the requirements clause:

templateCopyConstructible T>
  requires Addable
  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 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::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:

templateCopyConstructible T>
  requires Addable, Assignable
  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:

templateCopyConstructible T>
  requires Addable, Assignable
  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.,

templateCopyConstructible T>
  requires Addable, Assignable
  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, Assignable
  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::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, but there is a better way: concept map templates.

template<typename T>
concept_map ForwardIterator {
  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 that shows how Color meets the requirements of the Addable concept.

concept_map Addable {
  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::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 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::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 
requires Addable
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.