Wir müssen Iteratoren einen Wertetyp zuordnen. Solche Typ-Informationen können mit statischen Abbildungen und spezialisierten Templates transportiert werden.

Gib mir den Typ!

Wir müssen uns also überlegen, wie wir unserem Iterator-Typ einen Werte-Typ value_type zuordnen, analog zu der Zuordnung T* zu T. Eine Lösung wäre, direkt in mylist_iter einen typedef int value_type einzufügen, aber diese Lösung würde für den Iterator-Typ T* nicht funktionieren (und auch nicht für Iteratorklassen, auf deren Quellcode wir keinen Zugriff haben).

Im Prinzip ist das aber die richtige Spur. Wir brauchen eine Art Typ-Funktion, die Iterator-Typen auf Werte-Typen abbildet. Das kann man prinzipiell ganz einfach mit typedefs erreichen:

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

Damit wird durch die "Typ-Funktion" type_function der Typ arg auf den Typ result abgebildet, some_type muss dazu natürlich geeignet gewählt werden. Um etwa einem Typ T den zugehörigen Zeiger-Typ T* zuzuordnen, schreiben wir

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

Allgemeine Typabbildungen mittels Template-Spezialisierung

So weit, so gut. Wir brauchen hier die umgekehrte Richtung, und müssen den Resultatstyp von I::operator* extrahieren. Leider gibt es in C++2003 keine allgemeine Methode dafür (zu C++11 s.u.), und wir müssen unsere Funktion (nennen wir sie analog zu pointer_type einfach value_type) für die Einzelfälle ad hoc definieren, sozusagen per Fall-Unterscheidung:

  • value_type(T*) = T
  • value_type(mylist_iter) = int
  • value_type(I) bleibt undefiniert für andere Typen I (oder wird auf I::value_type gesetzt, in der Hoffnung dass es einen solchen gibt.)

Um das zu realisieren, müssen wir die C++ Template-Maschinerie anwerfen und Spezialisierung von Templates benutzen. Zunächst müssen wir ein allgemeines Template (primary template) für einen beliebigen Iterator-Typ I definieren. Da wir nichts über I wissen, könnten wir dieses allgemeine Template leer lassen. Für Zeiger-Typen und unser mylist_iter kennen wir aber den Werte-Typ und geben ihn in einer partiellen oder vollständigen Spezialisierung an:

// Das "primary template" ... Alternative siehe unten
template<typename Iterator> struct value_type {};

// Partielle Spezialisierung auf T*
template<typename T> struct value_type<T*> 
{ typedef T result; };

// Vollstaendige Spezialisierung fuer mylist_iter
template<> struct value_type<mylist_iter>
{ typedef int result; };

Wenn wir einen konkreten Typ einsetzen, sucht sich der Compiler automatisch die am meisten spezialisierte Variante heraus. Diese Technik (Template-Definition per Spezialisierung, d.h. Fallunterscheidung) läßt sich verallgemeinern und ist auch als template meta-programming bekannt (weil die Template-Definitionen für sich genommen ein kleines Programm darstellen, dass vom Compiler ausgeführt wird.)

Allerdings bedeutet unsere Lösung für allgemeine Typen im primary template, dass wir für jeden selbstdefinierten Iterator-Typ auch value_type spezialisieren müssen, analog zu value_type<mylist_iter>. Wenn wir uns auf die Konvention einigen, dass wir solchen Iterator-Typen einen inneren Typ I::value_t mitgeben, kann dies die Spezialisierungen überflüssig machen:

// Das "primary template" alternative using nested type of arg
template<typename Iterator> struct value_type
{ typedef typename  Iterator::value_t result; };

Wenn wir also direkt in mylist_iter einen Typ value_t definieren, können wir uns die Spezialisierung des Templates für mylist_iter ersparen. Ein template-technischer Hinweis: Im obigen Code muss man dem Compiler mit dem Schlüsselwort typename mitteilen, dass man mit dem Scope-Operator :: aus dem Template-Argument Iterator einen Typ und nicht eine statische Funktion oder Variable benötigt. Das ist etwas lästig, macht dem Compiler aber das Parsen einfacher.

C++11 macht alles einfacher

In C++11 hingegen können wir den neuen decltype Operator benutzen, um direkt auf den Rückgabetype von I::operator* zuzugreifen:

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

Richtiger wäre es, einen eventuell vorhandenen Referenz-Qualifier vom Rückgabe-Typ abzustreifen.

Summen-Funktion mit Iteratoren und Typabbildung

Wie auch immer wir das jetzt machen, mit value_type können wir endlich unsere Summe sum2 implementieren:

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;
}

Ein schneller Test ...

Damit sind alle Problem gelöst, die Sonne scheint, das Bier steht kalt ... Wir benutzen noch schnell unser sum2, um alle Strings aus einer langen Liste aneinanderzuhängen (das geht ja auch mit + ...):

vector<string> strings;
// ...
string all = sum2(strings.begin(),strings.end()); // was passiert?

Tja ... die Grillparty muss wohl noch verschoben werden.