We need to associate iterators with the corresponding value types of the elements. This type information can be transferred with static mappings and template specialization.

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!