Generische Programmierung (Templates)

Willemers Informatik-Ecke

Es gibt Abläufe, die sich auch bei verschiedenen Datentypen gleichen. So funktioniert die Bestimmung des Minimums zweier Werte völlig unabhängig vom verwendeten Datentyp immer gleich, sofern eine Kleiner-Relation für den Datentyp existiert. Auch ein Sortierverfahren lässt sich fast unverändert auf jeden Datentyp anwenden. Schließlich ist es auch einem Stack völlig gleichgültig, was für Daten dort verwaltet werden. In den bisher gezeigten Programmen ist der Typ aber mit dem Algorithmus sehr verwoben. Entsprechend müsste das gleiche Verfahren für einen anderen Typ wieder vollständig neu geschrieben werden.

Schablone

Mit dem Template (engl. Schablone) bietet C++ ein Werkzeug, um einen Algorithmus allgemein zu beschreiben, ohne sich auf einen Datentyp festzulegen. Templates werden verwendet, wenn gleiche Aktionen auf unterschiedliche Datentypen angewandt werden sollen. Diese Form der vom Typ unabhängigen Algorithmenbeschreibung bezeichnet man als >>generische Programmierung<<. Ein Template bildet die Schablone für einen Algorithmus. C++ kennt Template-Funktionen, bei denen der Programmierer die Typen von Parametern offen lässt, und Template-Klassen. Letztere beschreiben beispielsweise Datenstrukturen, die beliebige Typen aufnehmen können.

Template-Funktionen

Die einfache Form von Templates sind Template-Funktionen. Sie beschreiben einen Algorithmus und lassen den zu verwendenden Datentyp offen. Es sind Funktionen mit einer Funktionalität, die auf verschiedenen Datentypen gleich ist.

Beispiel

Ein klassisches Beispiel für eine generische Funktion ist min(). Die Funktion ermittelt aus zwei Parametern den kleineren. Der Vorgang ist bei allen Typen identisch, sofern für den Typ das Kleiner-Zeichen implementiert ist. Bevor die Definition eines Templates gezeigt wird, betrachten wir zunächst eine gewöhnliche Funktion min(), die mit long-Variablen als Parametern arbeitet.

[Funktion min() für den Typ long]

long min(long a, long b)
{
    return (a < b) ? a : b;
}

Daraus lässt sich die folgende Template-Funktion erstellen:

[Template-Funktion min()]

template <class T>
T min(T a, T b) 
{
    return (a < b) ? a : b;
}

Funktionsdefinition

Eine Template-Funktion beginnt mit dem Schlüsselwort template. In spitzen Klammern folgt der Template-Parameter. Er besteht aus dem Schlüsselwort class oder typename, gefolgt von einem Namen. Dieser Name wird im folgenden Template als Repräsentant für den offen gelassenen Typ verwendet. Traditionell wird dazu gern ein großes T verwendet. Aber der Name ist natürlich frei wählbar. Danach folgt eine übliche Funktionsdefinition. Immer da, wo bei der Anwendung der Benutzertyp verwendet werden soll, wird im Template der im Template-Parameter angegebene Name verwendet. Die Funktion min() benutzt den offen gelassenen Typ gleich dreimal. Beide Parameter und der Rückgabewert sind vom Typ T.

typename

Die Verwendung von typename oder class ist völlig gleichwertig. Das Schlüsselwort typename wurde eingeführt, um anzuzeigen, dass hier auch Typen verwendet werden können, die nicht als Klasse definiert sind. Allerdings kann es Ihnen passieren, dass einige Compiler das Schlüsselwort typename noch nicht kennen. Abbildung (graftemplatefunktion) zeigt den Syntaxgraph einer Template-Funktion. Der Syntaxgraph für die Funktionsdefinition, in der Abbildung als Fkt-Def abgekürzt, finden Sie in Abbildung (graffunction).

Hier steht im Buch die Abbildung "Syntaxgraph für Template-Funktionen" (graftemplatefunktion)

Aufruf

Wenn eine Template-Funktion aufgerufen wird, erzeugt der Compiler daraus eine dem Aufruftyp angepasste Funktion. Beim Aufruf wird nicht explizit angegeben, dass beispielsweise eine int-Instanz erzeugt werden soll. Der Compiler bestimmt den Typ der Werte, die als Parameter übergeben werden, und entnimmt daraus, für welchen Typ die Funktion generiert werden muss. Im Beispiel unten wird das T der Template-Definition durch den Standardtyp int ersetzt.

[Anwendung der Template-Funktion min]

int i=15;
int j=7;
cout << min(i,j) << endl;

Beispiel

Als weiteres Beispiel zeigt die Funktion swap(), dass Sie auch lokale Variablen des noch unbekannten Typs verwenden können und dass die Parameter auch per Referenz übergeben werden können.

[Template-Funktion swap]

template <typename T> void swap(T& a, T& b)
{
T hilf;

    hilf = a;
    a = b; 
    b = hilf;
}

Mehrere Typen

Es ist möglich, mehrere verschiedene Typen zu verwenden. Dazu wird in den spitzen Klammern lediglich ein weiterer Typ deklariert:

template <class T1, class T2>
int meineFunktion(T1 t1, T2 &t2)
{
    ...

Spezifizierung

Nicht immer wird aus den Parametern deutlich, für welchen Typ ein Template aufgerufen wird. Das Problem besteht besonders, wenn das Template keine Übergabeparameter besitzt, sondern nur einen Rückgabewert. Um festzulegen, mit welchem Typ das Template verwendet werden soll, wird in solch einem unklaren Fall beim Aufruf der Zieltyp in spitzen Klammern zwischen dem Funktionsnamen und der Parameterklammer angegeben:

int a = Create<int>();

Besitzt das Template mehrere offene Typen, so können diese, durch Kommata getrennt, angegeben werden. Es können aber auch nur die ersten Parameter festgelegt werden. Der folgende Aufruf von meineFunktion() stellt klar, dass der erste Parameter als short zu verstehen ist:

int a = meineFunktion<short>(12, 5.5);

Wenn Sie festlegen wollen, dass der erste Parameter als short und der zweite Parameter als float zu interpretieren ist, dann würde der Aufruf so aussehen:

int a = meineFunktion<short,float>(12, 5.5);

Template-Parameter

Mit den Template-Parametern können nicht nur Typen festgelegt werden, sondern auch Ausdrücke übergeben werden. Im folgenden Beispiel wird der Funktion SuperArray() mitgegeben, wie viele Plätze für das Array angelegt werden sollen.

template <class T, int max>
int SuperArray(T t)
{
T a[max];
...
}

int main()
{
    SuperArray<int, 100>(12);
}

Makro-Ersatz

Templates sind prädestiniert als Ersatz für die gefürchteten C-Makros. Da die Makros auf der Basis reiner Textersetzung funktionieren, sind die Fehlerquellen kaum überschaubar. Vor allem können Makros keine Typsicherheit gewährleisten. Auch wenn Template-Funktionen den Typ offen lassen, garantieren sie, dass alle gleichen Typen auch gleich bleiben. Wenn der Aufrufer beispielsweise den Typ T1 als float verwendet, müssen bei diesem Aufruf auch alle anderen T1 als float bedient werden.

Template-Klassen

Es ist möglich, ganze Klassen als Template zu definieren. Damit lässt sich das Problem lösen, das bei der Beispielklasse tStack schon aufgefallen war. Bei der Erstellung der Klasse muss bereits festgelegt werden, welchen Typ der Stack verwaltet. Bei einer Template-Klasse können Sie den Typ mit Hilfe eines Templates offen lassen.

Beispiel

Die folgende Stack-Implementierung basiert auf einem Array statt auf einer verketteten Liste.

[Template-Klasse Stack]

// Ein Stack für eine beliebige Klasse T
template<class T> class Stack 
{
public:
    // Konstruktor mit Initialisierung der Konstanten maxStack
    Stack() : maxStack(256)
        { s = new T[maxStack]; index=0;}
    ~Stack() {delete[] s;}
    bool pop(T *); // abholen
    bool push(T ); // drauflegen
private:
    const int maxStack; // Konstante für die Stackgröße
    T *s;               // Der Stack selbst
    int index;          // aktuelle Position im Stack-Array
};

// Element vom Stack nehmen und freigeben
template<class T> bool Stack<T>::pop(T *get)
{
    if (index==0 ) return false; // ist Stack leer?
    *get = s[--index]; // Entnehme Element
    return true;
}

// Neues Element auf den Stack schieben
template<class T> bool Stack<T>::push(T set)
{
    if (index>=maxStack) return false; // Ist Stack überfüllt?
    s[index++] = set;  // Element auflegen
    return true;
}

int main() // Testet den Stack
{
   Stack<int> iStack; // Lege einen Stack für ganze Zahlen an

   iStack.push(8); // Testzahlen eintragen
   iStack.push(4);
   iStack.push(2);
   // Stack auslesen und auf dem Bildschirm anzeigen
   for (int i=0; i<3; i++)
   {
       int a;
       if (iStack.pop(&a))
       {
           cout << a << endl;
       }
   }
}

Funktionsdefinition

Die Elementfunktionen push() und pop() werden in der Template-Klasse deklariert und dann separat definiert. Dabei werden sie wie die Klasse selbst durch eine Template-Deklaration eingeleitet. Des Weiteren wird zwischen dem Klassennamen und den beiden Doppelpunkten in spitzen Klammern der Name des Template-Typs genannt.

template<class T> bool Stack<T>::push(T set)

Anlegen einer Instanz

In der main()-Funktion wird ein Stack für int-Variablen angelegt. Dazu wird als Typ zunächst der Klassenname Stack verwendet. Danach wird in spitzen Klammern der Typ genannt, für den der Stack angelegt werden soll. Darauf folgt wie bei jeder Variablendefinition der Variablenname.

Stack<int> iStack;

Im weiteren Verlauf werden ein paar Werte auf den Stack gelegt und wieder heruntergeholt. Dabei ist nicht mehr zu erkennen, dass der Stack ein Template ist.

Template-Klasse mit Parameter

Im Beispiel oben haben wir die Stackgröße mit 256 festgelegt. Zwischen den spitzen Klammern kann ein solcher Wert als Parameter übergeben werden, im folgenden Beispiel als max. Dieser Wert muss bei der Instanziierung als Konstante angegeben werden. Er wird dann mit Hilfe eines Initialisierers am Konstruktor zur Vorbelegung der Klassenkonstante maxStack verwendet.

[Template-Klasse mit Parameter(templstack2.cpp)]

#include <iostream>
using namespace std;

template<class T, int max> class Stack
{
public:
    Stack() : maxStack(max)  // wird bei Definition festgelegt
        { s = new T[maxStack]; index=0;}
    ~Stack() {delete[] s;}
    bool pop(T *); // abholen
    bool push(T ); // drauflegen
private:
    const int maxStack; // Konstante für die Stackgröße
    T *s;               // Der Stack selbst
    int index;          // aktuelle Position im Stack-Array
};

// Element vom Stack nehmen und freigeben
template<class T, int max> bool Stack<T,max>::pop(T *get)
{
    if (index==0 ) return false; // ist Stack leer?
    *get = s[--index]; // Element entnehmen
    return true;
}

// Neues Element auf den Stack schieben
template<class T, int max> bool Stack<T,max>::push(T set)
{
    if (index>=maxStack) return false; // ist Stack überfüllt?
    s[index++] = set; // Element auflegen
    return true;
}

int main() // Testlauf
{
   Stack<int, 2> iStack; // Stack mit zwei Integerelementen
   int a;

   iStack.push(8); // Auffüllen!
   iStack.push(4);
   iStack.push(2); // Hier wird es eng!
   // Ausgabe des Stacks
   for (int i=0; i<3; i++)
   {
       if (iStack.pop(&a))
       {
           cout << a << endl;
       }
   }
}

In der Funktion main() wird ein Stack mit zwei Elementen erzeugt. Zum Test werden drei Werte auf den Stack gelegt. Dann wird geprüft, ob sich die drei Werte herunterziehen lassen.

Übung

Makroprogrammierung mit #define

Präprozessor

Generische Programmierung gibt es nicht erst seit C++. Auch in C können mit Hilfe der Präprozessor-Makros generische Funktionen erstellt werden. Aus Kompatibilitätsgründen steht diese Möglichkeit auch in C++ zur Verfügung, sollte aber für neue Programme nicht benutzt werden. Der Befehl #define ist die Basis für die Makro-Programmierung. Wie alle Befehle, die mit einem # anfangen, wird auch #define vom Präprozessor des Compilers ausgeführt. Der Präprozessor kann lediglich Textersetzungen durchführen, hat aber keine Kenntnis der Sprache C oder C++.

Syntax

Nach dem Befehl #define wird der Name des Makros angegeben. Hat das Makro Parameter, werden an den Namen Klammern angehängt. In die Klammer wird für jeden Parameter je ein Name angegeben. Einen Typ erhalten die Parameter nicht. Da #define vom Präprozessor ausgewertet wird und dieser nur Textersetzungen beherrscht, kann eine Typprüfung gar nicht stattfinden. In der Klammer können mehrere Parameter angegeben werden, die durch Kommata getrennt werden. Nach einem Leerzeichen wird der Ersetzungstext angegeben, den der Präprozessor anstelle des Aufrufs in den Quelltext einfügt. Der Präprozessor liest dazu den kompletten Rest der Zeile. Reicht dieser Platz nicht aus, kann als letztes Zeichen der Zeile ein Backslash (\) gesetzt werden. Dann betrachtet der Präprozessor die nächste Zeile als Fortsetzung der aktuellen Zeile.

Hier steht im Buch die Abbildung "Syntaxgraph für #define" (grafdefine)

Sehr häufig werden Sie die generische Funktion min() als Makro finden. Sie wird so oder ähnlich implementiert sein:

[Beispielmakro min()]

#define min(a,b) a>b?b:a

Textersetzung

Überall, wo im Programm min() auftaucht, wird dieser Aufruf durch die bedingte Anweisung ersetzt. Dabei wird der erste Parameter des Aufrufs als Text überall eingesetzt, wo im Makro a steht. Analog wird mit dem zweiten Parameter verfahren. Da der Präprozessor nur textuelle Ersetzungen vornimmt, werden die Parameter vor der Übergabe nicht ausgewertet. Es kann dadurch leicht passieren, dass sie durch die Ersetzung in einen Kontext geraten, in dem sie anders interpretiert werden, als der Programmierer sich das dachte. Weiter unten sehen Sie dazu ein Beispiel. Das Makro hat aus Sicht des C-Programmierers zwei Vorteile:
  • Er kann Code für mehrere Typen schreiben.
  • Es wird kein Code für den Funktionsaufruf benötigt. Das Makro wird also geringfügig schneller ausgeführt als eine Funktion.
In C++ sind beide Argumente nicht schlagkräftig. Um Code für mehrere Typen zu schreiben, verwendet man
Templates. Wollen Sie den Funktionsüberhang sparen, verwenden Sie inline-Funktionen.

Aus Sicht eines C++-Programmierers haben Makros folgende Nachteile:

  • Da Makros reine Textersetzungen sind, die der Präprozessor vor dem eigentlichen Übersetzungslauf durchführt, kann der Compiler nicht kontrollieren, ob die Aufrufparameter einwandfrei sind.
  • Sobald ein Makro etwas größer wird, werden die Ausdrücke schnell unübersichtlich, da es nicht möglich ist, Zwischenergebnisse in Variablen abzulegen.
  • Es kann leicht zu falschen Prioritäten kommen, da die Parameter beim Aufruf nicht ausgewertet werden. Beispiel:

    [Tückisches Makro]

    #define  mul(a,b) a*b
    int a=-5;
    int c = mul(a+4,2);
    

    Das Ergebnis ist keineswegs -2, sondern 3! Der Grund ist, dass a+4 nicht beim Aufruf zu -1 umgerechnet wird, sondern textuell ersetzt wird:

    c = a+4*2;
    

    Daraus wird dann -5+8.

  • Die Fehlermeldungen des Compilers zeigen meist nicht die Stelle im Makro an, die das Problem verursacht, sondern die Stelle, wo das Makro aufgerufen wird.
  • Durch die Beschränkung auf den Rest der Zeile ist Makro-Code meist sehr gepackt und dadurch oft völlig unlesbar.


Informatik-Ecke Einstieg in C++ (C) Copyright 2005 Arnold Willemer