Templates (2)
Anhand eines Algorithmus zur Speicherung von beliebigen Objekten in einem Stack wird die Erstellung von Klassentemplates erklärt.
LIFO-Container
Nachdem im ersten Teil dieser Artikelfolge ein Funktionstemplate vorgestellt wurde, soll heute ein Klassentemplate entwickelt werden. Wir erinnern uns: Templates dienen der Entwicklung von Algorithmen unabhängig von konkreten Datentypen. In der Informationstechnologie immer wieder benötigte Algorithmen sind die Speicherung mehrerer Objekte in einem Container. Einfache Container sind Arrays, Listen, Queues und Stacks. Ein Stack muss im wesentlichen zwei Funktionen realisieren: Eine push-Funktion zum Ablegen von Objekten und eine pop-Funktion zum Entfernen von Objekten. Das Besondere dabei ist, dass das zuletzt mittles push() abgelegte Objekt bei einem pop() zuerst wieder auftaucht - ein Stack ist ein Last-In-First-Out (LIFO) Container.
Templates klar im Vorteil
Für die Realisierung eines Stacks bietet sich zunächst die Implementierung als Klasse an: Eine private Membervariable hält die eigentlichen Daten; push() und pop() sind öffentliche Memberfunktionen. Bei näherer Betrachtung des Problems fällt ausserdem auf, dass die Funktionalität des Stacks immer die gleiche bleibt - egal ob in ihm Variablen vom Typ int, double oder MeineEigeneKlasse gespeichert werden. Es bietet sich also an, auch nur diesen typunabhängigen Algorithmus zu implementieren. Das C++ Werkzeug dazu ist das Klassentemplate.
Unser Programmcode beginnt mit der Deklaration von zwei leeren Klassen, die später als Exception zur Ausnahmebehandlung verwendet werden:
class StackFullException {}; class StackEmptyException {};
Dann folgt die Templatedefinition, die zwei Parameter in spitzen Klammern bekommt: Den Typ T des zu speichernden Objektes und die maximale Kapazität des Stacks cap. Diese ist standardmäßig mit 10 vorbelegt.
template < class T, int cap = 10 > class Stack
Die Implementierung des Stack-Algorithmus erfolgt unter Zuhilfenahme eines Arrays zur Speicherung der Objekte. Der Programmcode sollte eigentlich für sich sprechen. Bemerkenswert ist nur, dass die Funktion pop() zwar das oberste Element vom Stack entfernt, dieses aber nicht als Rückgabewert zurückliefert. Der Anwender muss vielmehr die Funktion top() benutzen, um sich das oberste Element auf dem Stack anzusehen. Dieses auf den ersten Blick ungewöhnliche Verfahren hat zwei Vorteile: Zum einen kann top() auf ein Kopieren des Objektes verzichten, die Rückgabe erfolgt per reference. Pop() könnte dies nicht, da es ja das Objekt zuerst vom Stack entfernen muss. Ein zeitaufwendiges Kopieren wäre so nötig. Zum anderen hat der Anwender die Möglichkeit, mittels top() das oberste Element des Stacks zu betrachten, ohne dieses gleich entfernen zu müssen - bei vielen Aufgaben könnte sich dies durchaus als Vorteil erweisen:
{
public:
Stack() : m_a( new T[cap]), m_size (0) {}
~Stack() { delete[] m_a; }
void push( const T& val) {
if (m_size >= cap) throw StackFullException();
m_a[m_size++] = val;
}
void pop() {
if (m_size == 0) throw StackEmptyException();
--m_size;
}
T& top() {
if (m_size == 0) throw StackEmptyException();
return m_a[m_size-1];
}
int size() const { return m_size; }
bool full() const { return m_size == cap; }
bool empty() const { return m_size == 0; }
private:
T* m_a;
int m_size;
};
Wir sehen, dass überall dort, wo wir uns bei einer einfachen Klassendefinition auf den konkreten Typ des zu speichernden Objektes festzulegen hätten, jetzt der Templateparameter T quasi als Platzhalter verwendet werden kann. Auch ist nun ersichtlich, wozu die Exceptions dienen: Wird mit einen leeren Stack pop() oder top() aufgerufen, kommt die StackEmptyException; ein Versuch, mittels push() die Kapazität des Stacks zu überschreiten, führt zur Auslösung der StackFullException.
Der Test
Nun kann unser Template mit einem kleinen Programm getestet werden:
#include <iostream> int main( int argc, char **argv) { Stack < int > s;
Unser Teststack soll Objekte vom Typ int speichern. Der Compiler nimmt sich jetzt also die obige Templatedefinition und ersetzt T mit int und cap mit 10 (da dieser Parameter hier fehlt, wird der Standardwert aus der Templatedefinition genommen) und konstruiert daraus eine neue Klassendefinition für das Objekt s.
Jetzt werden 10 Elemente in den Stack geschrieben und anschließend wieder entfernt. Die Elemente werden ausgegeben, um zu sehen, ob das LIFO Prinzip richtig implementiert wurde. Zum Schluss wird auch noch getestet, ob der Exceptionmechanismus richtig funktioniert, indem auf den leeren Stack mit pop() zugegriffen wird:
try {
std::cout << "+++push: ";
for (int i = 0; i < 10; ++i) {
s.push( i);
std::cout << i << " ";
}
std::cout << std::endl;
std::cout << "---pop: ";
while (! s.empty()) {
std::cout << s.top() << " ";
s.pop();
}
std::cout << std::endl;
// provoke an exception
s.pop();
}
catch (const StackFullException &e) {
std::cerr << "stack overrun\n";
}
catch (const StackEmptyException &e) {
std::cerr << "stack underrun\n";
}
}
Die STL kann schon alles
Nachdem an diesem Beispiel die Erstellung und Benutzung von Klassentemplates demonstriert wurde, darf nicht verschwiegen werden, dass ein Stack-Template auch in der Standard Template Library (STL) enthalten ist, die Bestandteil jedes modernen C++ Compilersystems ist. Unser Testprogramm funktioniert also auch, wenn wir anstelle der Templatedefinition einfach
#include <stack>
schreiben und die Templateinstanzierung durch
std::stack < int > s;
ersetzt wird. Damit wird der Stackalgorithmus aus der STL benutzt (kenntlich am Namespaceprefix std::), welcher keine Limitierung der Stackkapazität besitzt (der Templateparameter cap entfällt also), dafür aber bei Fehlbedienungen wie pop() auf den leeren Stack keine Exceptions wirft, sondern »undefiniertes Verhalten« aufweist.