Gimme the type!

We now have to find a means to associate a value type value_type to our iterator type, analogous to the association of T to T*, which we implicitly used before. One possible solution is to directly insert typedef int value_type into mylist_iter, but this would not work for the iterator type T* (nor for iterator classes for which we cannot change the source).

Basically however we are on the right track. We need a kind of type function, mapping iterator types to value types. In principle, this can be easily achieved using templates with nested typedefs:

template<typename arg> struct type_function { typedef some_type result; };

Here, the "type function" type_function maps the type arg to the type result (assuming an appropriate value for some_type). For mapping a type T to its pointer type T*, we could write

template<typename T> struct pointer_type { typedef T* result; };

General type mappings via template specializations

So far, so good (and useless). What we need, is the inverse direction, and extract the result type of I::operator*. In C++2003, there is no general method for this (for a C++11 example see below). So we must define our function (let's call it value_type) in an ad hoc way by case distinction:

• value_type(T*) = T
• value_type(mylist_iter) = int
• value_type(I) is left undefined for other types I (or is set to I::value_type, hoping there is such a nested type)

To realize this in C++, we must use the template machinery and use specialization of templates. First, we define a general primary template for arbitrary iterator types I. As we don't now anything about this type, the primary template stays empty, and the type function value_type is undefined in general (see below for an alternative). For pointer types and our mylist_iter we know the value type, and we can specify it using a partial or complete specialization:

// The "primary template" ... alternative see below
template<typename Iterator> struct value_type {};

// partial specialization for T*
template<typename T> struct value_type<T*> 
{ typedef T result; };

// complete specialization for mylist_iter
template<> struct value_type<mylist_iter>
{ typedef int result; };

If we instantiate value_type with a concrete type, the compiler automatically chooses the most specialized variant. This technique (template definition by specialization, i.e. case distinction) can be generalized and is known as template meta-programming (because the template definition itself is a little programm executed by the compiler).

However, our solution for general types in the primary template means, that we need a specialization of value_type for each own iterator type, (like mylist_iter). If we introduce the convention that each iterator type I provides a nested type I::value_t, we don't need the specializations any more:

// Das "primary template" Alternative mit Zugriff auf geschachtelten Typ
template<typename Iterator> struct value_type
{ typedef typename  Iterator::value_t result; };

So, if we provide a type value_t directly in mylist_iter, we'll save the extra specialization of the template value_type for mylist_iter. A technical note: With the typename keyword, we have to tell the compiler that we use the scope operator :: to extract a type from the template argument Iterator and not something different (a static function or variable). This is cumbersome, but makes the compiler's job easier.

C++11 makes life easier

In C++11 in contrast we can use the new decltype operator to simply extract the return type of I::operator*:

template<typename Iterator> struct value_type 
{ typedef decltype( *(Iterator()) ) result; };

In practice, we would also strip a possible reference from the type obtained with decltype.

Sum function using iterators and type mapping

Whatever method we choose, using value_type we can finally implement sum2:

template<typename Iterator>
typename value_type<Iterator>::result
sum2(Iterator  a, Iterator a_end)
{
  typename value_type<Iterator>::result res = 0;
  for(; a != a_end; ++a)
    res += *a;
  return res;
}

A quick test ...

Thus, we have solved all problems, the sun is shining, we grab a fresh beer to enjoy the evening ... just quickly use our sum2 to concatenate all strings in a long list (this also uses + ...):

vector<string> strings;
// ...
string all = sum2(strings.begin(),strings.end()); // what the heck ...?

Dang ... we have to postpone our barbecue party!

• <<<Previous page
• Next page >>>