Associated Types and Traits Classes

(Unsatisfied) Associated Types Needed in a Function Template

A traits class is basically a way of determining information about a type that you would otherwise know nothing about. For example, consider a generic sum() function:

template <typename Array>
X sum(const Array& v, int n) {
  X total = 0;
  for (int i = 0; i < n; ++i)
    total += v[i];
  return total;
}

From the point of view of this function template, not much is known about the template type Array. For instance, the type of the elements that are inside the array is not given. However, this information is necessary in order to declare the local variable total, which should be the same type as the elements of Array. The X that is there now is just a placeholder that needs to be replaced by something else to produce a correct sum() function.

Typedefs Nested in Classes

One way to access information out of a type is to use the scope operator :: to access typedef's that are nested inside the class. For example, an array class might looks like the following:

class my array {
public:
  typedef double value_type; // the type for elements in the array
  double& operator[](int i) { m_data[i];};
private:
  double* m_data;
};

The type of the elements in the array can now be accessed via my array::value_type. The generic sum() function can be realized using this technique as follows (note that the X placeholders have been replaced with typename Array::value_type):

template <typename Array>
typename Array::value_type sum(const Array& v, int n) {
  typename Array::value_type total = 0;
  for (int i = 0; i < n; ++i)
    total += v[i];
  return total;
}

In the sum() function above, the technique of using a nested typedef works as long as Array is a class type that has such a nested typedef. However, there are important cases for which having a nested typedef is neither practical nor possible. For instance, one might want to use the generic sum() function with a class from a third party that did not provide the required typedef. Or, one might want to use the sum() function with a built-in type such as double *.

int n = 100;
double* x = new double[n];
sum(x, n);

In both of these cases, it is quite likely that the functional requirements of our desired use are met; that is, the operator[]() works with double* and with our imaginary third-party array. The limitation to reuse is in how to communicate the type information from the classes we want to use to the sum() function.

Definition of a Traits Class

The solution to this is a traits class, which is a class template whose sole purpose is to provide a mapping from a type to other types, functions, or constants. The language mechanism that allows a class template to create a mapping is template specialization. The mapping is accomplished by creating different versions of the traits class to handle specific type parameters. We will show how this works by creating an array traits class that can be used in the sum() function.

The array_traits class will be templated on the Array type and will allow us to determine the value_type (the type of the element) of the array. The default (fully templated) case will assume that the array is a class with a nested typedef such as my_array:

template <typename Array>
struct array traits {
  typedef typename Array::value_type value_type;
};

We can then create a specialization of the array traits template to handle when the Array template argument is a built-in type like double*:

template <> struct array_traits<double*> {
  typedef double value_type;
};

The sum() function, written with array_traits class, is shown below. To access the type for the total variable we extract the value type from array_traits:

template <typename Array>
typename array_traits<Array>::value_type sum(const Array& v, int n) {
  typename array_traits<Array>::value_type total = 0;
  for (int i = 0; i < n; ++i)
    total += v[i];
  return total;
}

But writing a traits_class for every pointer type is not practical or desirable. The following shows how to use partial specialization to provide array traits for all pointer types. The C++ compiler will attempt a pattern match between the template argument provided at the instantiation of the traits class and all the specializations defined, picking the specialization that is the best match. The partial specialization for T* will match whenever the type is a pointer. The previous complete specializations for double* would still match first for that particular pointer type.

template <typename T>
  struct array_traits<T*> {
  typedef T value_type;
};

The most well-known use of a traits class is the iterator_traits class used in the STL. The BGL also uses traits classes such as graph_traits and the property_traits classes. Typically, a traits class is used with a particular concept or family of concepts. The iterator_traits class is used with the family of iterator concepts. The graph_traits class is used with the family of BGL graph concepts.

Tag Dispatching

A technique that often goes hand in hand with traits classes is tag dispatching, which is a way of using function overloading to dispatch based on properties of a type. A good example of this is the implementation of the std::advance() function in the STL, which, in the default case, 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, then the advance() function can simply be implemented with i += n and is very efficient; that is, it is in constant time. If the iterator is bidirectional, then it may be the case that n is negative, so we can decrement the iterator n times. The relation between external polymorphism and traits classes is that the property to be exploited for dispatch (in this case, the iterator_category) is accessed through a traits class.

In the following example, the advance() function uses the iterator_traits class to determine the iterator_category. It then makes a call to the overloaded advance_dispatch() function. The appropriate advance_dispatch() is selected by the compiler based on whatever type the iterator_category resolves to (one of the tag classes in the following code).

A tag is simply a class whose only purpose is to convey some property for use in tag dispatching. By convention, the name of a tag class ends in _tag. We do not define a function overload for the forward iterator_tag because that case is handled by the function overloaded for input_iterator_tag.

struct input iterator tag {};
struct output iterator tag {};
struct forward iterator tag : public input iterator tag {};
struct bidirectional iterator tag : public forward iterator tag {};
struct random access iterator tag : public bidirectional iterator tag {};

template <typename InputIterator, typename Distance>
void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag) {
  while (n−−)
    ++i;
};
template <typename BidirectionalIterator, typename Distance>
void advance dispatch(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
  if (n >= 0)
    while (n−−) ++i;
  else
    while (n++) −−i;
}
template <typename RandomAccessIterator, typename Distance>
void advance_dispatch(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
  i += n;
};
template <typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n) {
  typedef typename iterator_traits<InputIterator>::iterator_category Cat;
  advance dispatch(i, n, Cat());
};