C++ Concepts (Advanced)

Conceptual Template Parameters

Concepts are template parameters that do not define types that are used by the class, but control the behaviour of the class through defining which abstract data type it implements.

One of the primary responsibilities of a generic library is to define the interfaces that allow algorithms to be written independently of any particular data structure. Note that by interface we do not merely mean a set of function prototypes. Instead, we mean a set of syntactic requirements—things like function names and numbers of arguments—as well as semantic requirements (executing the function must have certain effects) and time and space complexity guarantees.

Using the terminology from the book Generic Programming and the STL, we use the word concept to refer to this richer notion of an interface. The STL defines a collection of iterator concepts that provide a generic mechanism for traversing and accessing sequences of objects.

Here is an example of a class defined solely to be used as a template parameter for checking purposes:

class integer_class {};
template <typename I, class IS_INTEGER> class integer {};

Next, a partial specialization is added for the case when the second template parameter is class integer_class. This becomes the only implementation of the class, whereas the general class is made unusable through having its constructors deleted or some other means.

template <typename I> class integer<I,integer_class> {/* code */};

Sets of Requirements

The requirements for a concept consist of a set of valid expressions, associated types, invariants, and complexity guarantees. A type that meets the set of requirements is said to model the concept. A concept can extend the requirements of another concept, which is called refinement.

• Valid Expressions are C++ expressions that must compile successfully for the types involved in the expression to be considered models of the concept.
• Associated Types are auxiliary types that have some relation to the type T modeling the concept. The requirements in a concept typically make statements about associated types. For example, iterator requirements typically include an associated type called the value_type and the requirement that objects returned by the iterator's dereference operator must be of the value_type. In C++ it is common to use a traits class to map from the type T to the associated types of the concept.
• Invariants are run-time characteristics of types that must always be true. The invariants often take the form of preconditions and postconditions. When a precondition is not fulfilled, the behavior of the operation is, in general, undefined and can lead to a segmentation fault. This is the case for the Boost Graph Library. Some libraries provide debugging versions that use assertions or throw exceptions when a precondition is violated.
• Complexity Guarantees are maximum limits on how long the execution of one of the valid expressions will take, or how much of the various resources its computation will use.

Example: InputIterator

In this section, we take a closer look at InputIterator as an example of a concept. First, the InputIterator concept is a refinement of TrivialIterator which, in turn, is a refinement of Assignable and EqualityComparable . Thus, the InputIterator meets all the requirements of a TrivialIterator (which meets all of the requirements of Assignable and EqualityComparable) The result is that a type that models InputIterator will have a dereference operator, it can be copied and assigned, and it can be compared with other iterator objects using == and != .

The InputIterator concept adds the requirement for pre-increment and post-increment operators. These requirements are denoted by the following valid expressions. Objects i and j are instances of a type T that models InputIterator.

i = j   // assignment (from Assignable)
T i(j)  // copy (from Assignable)
i == j  // equality test (from EqualityComparable)
i != j  // inequality test (from EqualityComparable)
*i      // dereference (from TrivialIterator)
++i     // pre-increment operator
i++     // post-increment operator

The std::iterator_traits class provides access to the associated types of an iterator type. The type of an object that is pointed to by an iterator type (call it X) can be determined via the value_type of the traits class. The other associated types are reference, pointer, difference_type, and iterator_category.

In the following template function we show the use of the iterator_traits class to obtain the value_type of the iterator and dereference the iterator.

template <typename Iterator>
void dereference example(Iterator i) {
  typename iterator traits<Iterator>::value_type t;
  t = *i;
}

As for complexity guarantees, all of the InputIterator operations are required to be constant time. Some types that model InputIterator are std::list<int>::iterator, double*, and std::istream iterator<char>.

The purpose of defining concepts becomes clear when considering the implementation of generic algorithms. The implementation of the std::for_each() function follows. Inside the function precisely four operations are applied to the iterator objects first or last : comparison using operator!=(), increment with operator++(), dereference with operator*(), and copy construction. For this function to compile and operate properly the iterator arguments must support at least these four operations. The concept InputIterator includes these operations (and not many more), so it is a reasonable choice for succinctly describing the requirements of for_each().

template <typename InputIterator, typename Function>
Function for_each(InputIterator first, InputIterator last, Function f ) {
  for ( ; first != last; ++first)
    f(*first);
  return f ;
}