Warum nur arrays?

Wir können jetzt also arrays beliebigen Typs in unser sum1 stecken. Was aber, wenn unsere Daten in einer std::list<int> stecken? Oder gar in einer Datei? Oder wir die Spaltensummen von Matrix-Elementen berechnen wollen?

Um eine Summe zu bilden, müssen wir ja eigentlich nur auf alle Summanden einmal zugreifen können. Das ist bei den Beispielen Matrix-Spalte und Liste sicher erfüllt, nur sieht der Zugriff und das Weitergehen auf das jeweils nächste Element etwas anders aus.

Um klarer zu machen, was eigentlich passiert und wie wir sum1 verallgemeinern können, formulieren wir den Code zunächst etwas um. Denn was wir mit einer Liste sicher nicht abbilden können, ist der wahlfreie Zugriff wie a[i] bei einem Array. Den brauchen wir für eine Summe aber auch gar nicht!

template<typename T>
T sum1b(T* a, T* a_end)
{
  T res = 0;
  for(; a != a_end; ++a)
    res += *a;
  return res;
}

Statt einem Zeiger auf den Array-Anfang (das erste Element) und der Anzahl Elemente übergeben wir jetzt Zeiger auf Anfang und hinter das letzte Element. (Warum nicht auf das letzte? Dazu werde ich bei Gelegenheit an anderer Stelle mehr sagen. Jetzt nur soviel, dass man damit auch leere Bereiche gut darstellen kann.) Ausserdem wird im Code jetzt nicht mehr der wahlfreie Zugriff mit operator[] benutzt (also a[i]), sondern nur der Dereferenzierungs-Operator operator* (also *a). Der Aufruf ändert sich dadurch etwas:

float a[10];
// ...
float sa = sum1b(a, a+10);

Was haben wir damit gewonnen? Wir brauchen nun nur noch die folgenden Operationen für das Argument a vom Typ T*:

1. Inkrementieren eines Zeigers: ++a
2. Vergleich zweier Zeiger: a != a_end
3. Dereferenzieren: *a

Das sieht zwar immer noch ziemlich speziell auf Zeiger zugeschnitten aus, in Wirklichkeit aber sind das recht einfache Operationen, die prinzipiell auch für Listen und erst recht Matrix-Spalten bereitgestellt werden können.

Zeiger und ihre Verallgemeinerung: Iteratoren

Bisher haben wir immer nur unsere Implementierung von sum verändert, um die Implementierung generischer zu machen. An dieser Stelle müssen wir aber auch etwas zu den Argument-Typen hinzufügen, um die notwendige Funktionalität bereitzustellen bzw. in die Sprache der generischen Routine sum zu übersetzen, denn wir gehen ja von der Grundannahme aus, dass die Funktionalität im Prinzip im Argumenttyp schon vorhanden ist. In Wirklichkeit müssen wir auch bei sum1 nochmal etwas genauer hinschauen. Nehmen wir also eine ganz einfache Listen-Definition her:

struct mylist {
  int      data;
  mylist  *next;
};

Dazu möchten wir jetzt einen Hilfstyp definieren, der sich in bezug auf die oben aufgelisteten Funktionen wie ein Zeiger verhält, also die Operationen ++p, *p und p != q unterstützt. Ein solcher Type erlaubt die Iteration über die Listenelemente und wird daher auch als Iterator-Typ bezeichnet. Da Iteratoren allgegenwärtig sind, hat man sie in der Standardbibliothek formalisiert (siehe link oben). In unserem folgenden Beispiel implementieren wir nur eine Ausschnitt der Gesamt-Funktionalität.

struct mylist_iter {
  // ...
  mylist  *curr;
  mylist_iter& operator++() { 
    if(curr) 
      curr = curr->next;
    return *this; 
  }
  // precondition: curr != 0 
  int&         operator* () { return curr->data; } 
};

bool operator!=(mylist_iter const& p, mylist_iter const& q)
{ return p.curr != q.curr; }

Solchermaßen ausgerüstet, können wir jetzt unsere Definition von sum so erweitern, dass wir nicht nur Zeigertypen akzeptieren, sondern beliebige Iteratoren mit dem entsprechenden Interface:

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

Aber jetzt haben wir uns ganz offensichtlich ein Problem eingehandelt. Was soll denn der Rückgabetyp von sum2 sein? Vorher konnten wir diesen Typ T direkt aus dem Argumenttyp T* ableiten. Woher nehmen wir ihn jetzt?

• <<<Vorherige Seite
• Nächste Seite >>>