Generic Programming in C++: Techniques

Table of Contents

Introduction

C++ has can support Generic Programming very well through its template system, but to fully express the ideas of Generic Programming in C++ one must use a variety of template techniques. This document describes many of these techniques, which are used by nearly all generic libraries written in C++.

Concepts

Concepts have no direct representation in C++, so they are represented only within the documentation for a generic library. The documentation for the SGI Standard Template Library established the de facto standard for documenting concepts, which we briefly describe here. Concepts are documented as a set of requirements consisting of valid expressions, associated types, invariants, and complexity guarantees.

• Valid Expressions are C++ expressions which must compile successfully for the objects involved in the expression to be considered models of the concept.
• Associated Types are types that are related to the modeling type in that they participate in one or more of the valid expressions. Typically associated types can be accessed either through typedefs nested within a class definition for the modeling type, or they are accessed through a traits class.
• Invariants are run-time characteristics of the objects that must always be true, that is, the functions involving the objects must preserve these characteristics. The invariants often take the form of pre-conditions and post-conditions.
• Complexity Guarantees are maximum limits on how long the execution of one of the valid expressions will take, or how much of various resources its computation will use.

There is a wealth of concept documentation available online. Links to many concepts, most of them written in the style of the SGI STL documentation, are provided in a separate document of concept examples.

Algorithms

Generic algorithms in C++ are written using C++ templates. Although C++ templates do not provide much type checking at the point of definition, they are type-safe at the point of instantiation and offer uncompromising performance. As a convention, templates document their concept requirements by naming template parameters after the concepts they model. For instance, an implementation of the STL accumulate() algorithm follows:

template
T accumulate(InputIterator first, InputIterator last, T init) {
  for (first != last; ++first)
    init = init + *first;
  return init;
}

Traits

A traits class provides a way of associating information with a compile-time entity (a type, integral constant, or address). For example, the class template std::iterator_traits looks something like this:

template 
struct iterator_traits {
  typedef ... iterator_category;
  typedef ... value_type;
  typedef ... difference_type;
  typedef ... pointer;
  typedef ... reference;
};

The traits' value_type gives generic code the type which the iterator is "pointing at", while the iterator_category can be used to select more efficient algorithms depending on the iterator's capabilities.

A key feature of traits templates is that they're non-intrusive: they allow us to associate information with arbitrary types, including built-in types and types defined in third-party libraries, thereby enabling retroactive modeling. Normally, traits are specified for a particular type by (partially) specializing the traits template.

For an in-depth description of std::iterator_traits, see this page provided by SGI. Another very different expression of the traits idiom in the standard is std::numeric_limits which provides constants describing the range and capabilities of numeric types.

Tag Dispatching

Tag dispatching is a way of using function overloading to effect concept-based overloading, and is often used hand-in-hand with traits classes. A good example of this synergy is the implementation of the std::advance() function in the C++ Standard Library, which increments an iterator n times. Depending on the kind of iterator, there are different optimizations that can be applied in the implementation. If the iterator is random access (can jump forward and backward arbitrary distances), then the advance() function can simply be implemented with i += n, and is very efficient: constant time. Other iterators must be advanced in steps, making the operation linear in n. If the iterator is bidirectional, then it makes sense for n to be negative, so we must decide whether to increment or decrement the iterator.

The relation between tag dispatching and traits classes is that the property used for dispatching (in this case the iterator_category) is often accessed through a traits class. The main advance() function uses the iterator_traits class to get the iterator_category. It then makes a call the the overloaded advance_dispatch() function. The appropriate advance_dispatch() is selected by the compiler based on whatever type the iterator_category resolves to, either input_iterator_tag, bidirectional_iterator_tag, or random_access_iterator_tag. A tag is simply a class whose only purpose is to convey some property for use in tag dispatching and similar techniques. Inheritance of tags is used to encode the refinement hierarchy of concepts, so that overloading can pick the most specific algorithm based on the tag hierarchy. Refer to this page for a more detailed description of iterator tags.

namespace std {
  struct input_iterator_tag { };
  struct bidirectional_iterator_tag : input_iterator_tag { };
  struct random_access_iterator_tag : bidirectional_iterator_tag { };
  namespace detail {
    template 
    void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag) {
      while (n--) ++i;
    }
    template 
    void advance_dispatch(BidirectionalIterator& i, Distance n, 
       bidirectional_iterator_tag) {
      if (n >= 0)
        while (n--) ++i;
      else
        while (n++) --i;
    }
    template 
    void advance_dispatch(RandomAccessIterator& i, Distance n, 
       random_access_iterator_tag) {
      i += n;
    }
  }
  template 
  void advance(InputIterator& i, Distance n) {
    typename iterator_traits::iterator_category category;
    detail::advance_dispatch(i, n, category);
  }
}

Arbitrary Overloading

Tag dispatching provides support for concept-based overloadingof C++ templates, but is limited to decisions based on tags. However, one can use completely arbitrary template metaprograms to make overloading decisions using Substitution Failure Is Not An Error (SFINAE). SFINAE is most useful when encoded into a template such as enable_if, defined in its entirety below:

template 
  struct enable_if {};
template
  struct enable_if {
    typedef T type;
  };

Essentially, enable_if::type is T when V is true, but does not exist when T is false. Why does this matter? SFINAE means that when the compiler substitutes types into the declaration of a template, and that substitution fails for certain reasons (including not finding a member type), that template is silently eliminated from the set of function templates to be considered. For instance, say we want to write a function sqrt that works only for integral types. We could do so like this:

template
  typename enable_if::value, T>::type
  sqrt(T x);

Since enable_if can be used with arbitrary template metafunctions, one can encode any kind of decision procedure to enable or disable certain templates, so long as the set of overloaded templates was coordinated so that only a single template is active for a given set of template arguments. For more information about enable_if and SFINAE, see the Boost enable_if library or read the following article:

J. Järvi, J. Willcock, H. Hinnant, and A. Lumsdaine. Function Overloading Based on Arbitrary Properties of Types. C/C++ Users Journal, 21(6):25--32, June 2003.

Adaptors

An adaptor is a class template which builds on another type or types to provide a new interface or behavioral variant. Adaptors are used when a type or set of types needs to model a concept whose interface is incompatible with the type(s). Examples of standard adaptors are std::reverse_iterator, which adapts an iterator type by reversing its motion upon increment/decrement, and std::stack, which adapts a container to provide a simple stack interface.

A more comprehensive review of the adaptors in the standard can be found here.

Concept Checking

Concept checking is a way to detect errors in the use of templates early in their instantiation process, in the attempt of producing more readable error messages for users. To use concept checking, function and class templates are annotated with code that forces the instantiation of concept-checking classes. These classes exercise all of the syntactic properties of a concept, e.g., valid expressions and associated types. If the types used to instantiate the generic function do not meet the requirements of the concept, the compiler will report an error within these concept-checking classes first. Thus, concept checking plays the role of verifying that a particular type or set of types model a concept properly (in the syntactic sense).

More information about concept checking is available in the Boost Concept Check Library and the following papers:

Jeremy G. Siek and Andrew Lumsdaine. C++ Concept Checking. Dr. Dobb's Journal, June 2001.

Jeremy Siek and Andrew Lumsdaine. Concept checking: Binding parametric polymorphism in C++. In Proceedings of the First Workshop on C++ Template Programming, Erfurt, Germany, 2000.

Archetypes

Archetypes provide improved type-checking for function and class templates in C++. While concept checking helps users by detecting when the template arguments do not model the concepts they should, archetypes help library designers by checking that the definition of a template only relies upon its types to provide behavior listed in its concept requirements. For instance, the following find() implementation is incorrect:

template
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
  while (first < last && !(*first == value))
    ++first;
  return first;
}

The error will not be detected until find() is instantiated with an iterator type that does not support the < operator. Archetypes, then, are special types that provide only the behavior required by a particular concept or set of concepts, and nothing more. By instantiating templates on archetypes, we can determine if the templates try to use features not listed as part of concepts. If the instantiation on the archetypes succeeds, the template is very likely to be syntactically correct.

More information about archetypes is available in the Boost Concept Check Library and the following papers:

Jeremy G. Siek and Andrew Lumsdaine. C++ Concept Checking. Dr. Dobb's Journal, June 2001.

Jeremy Siek and Andrew Lumsdaine. Concept checking: Binding parametric polymorphism in C++. In Proceedings of the First Workshop on C++ Template Programming, Erfurt, Germany, 2000.

© Copyright David Abrahams 2001. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.