David
Abrahams
and Douglas Gregor
Table of Contents
   Introduction
   Concepts
   Algorithms
   Traits
   Tag Dispatching
   Arbitrary Overloading
   Adaptors
   Concept Checking
   Archetypes
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 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.
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;
}
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 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.
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.
|