Eines der leistungsfähigsten neuen Konzepte von C++ sind die »parametrisierten Typen« oder Templates (Schablonen, Vorlagen). Templates sind so nützlich, daß die Standard Template Library (STL) in die Spezifikation der Sprache C++ aufgenommen wurde. Heute lernen Sie,
Zum Ende der zweiten Woche haben Sie gesehen, wie man ein PartsList
-Objekt erzeugt
und zur Erstellung eines PartCatalogs
nutzt. Wenn Sie ein PartList
-Objekt zum
Aufbau einer Liste von Katzen (CAT
-Objekten) einrichten wollen, haben Sie ein Problem:
PartList
kennt sich nur mit Part
-Objekten aus.
Zur Lösung des Problems könnte man eine Basisklasse List
erstellen und davon die
Klassen PartsList
und CatsList
ableiten. Dann kopiert man soviel wie möglich aus
der Klasse PartsList
in die neue CatsList
-Deklaration. Sobald es Ihnen aber in den
Sinn kommt, eine Liste mit Car
-Objekten zu erstellen, müssen Sie wieder eine neue
Klasse anlegen und wieder mit Ausschneiden und Einfügen arbeiten.
Daß dies keine zufriedenstellende Lösung ist, versteht sich von selbst. Mit der Zeit werden
unter Umständen noch Anpassungen und Erweiterungen der List
-Klasse und ihrer
abgeleiteten Klassen erforderlich. Dann wird es zum Alptraum, alle Änderungen in
allen verwandten Klassen auf den gleichen Stand zu bringen.
Templates bieten eine Lösung für dieses Problem, und durch die Aufnahme in den ANSI-Standard sind sie nun ein integraler Bestandteil der Sprache. Wie alles in C++ sind sie typensicher und sehr flexibel.
Statt typenspezifische Listen zu erzeugen, teilt man dem Compiler mit Templates einfach
mit, wie eine Liste für einen beliebigen Typ zu erzeugen ist. Eine PartsList
ist
eine Liste mit Bauteilen, eine CatsList
eine Liste mit Katzen. Diese Listen unterscheiden
sich einzig und allein durch die Typen der Objekte, die in der Liste verwaltet werden.
Bei Templates wird der Typ des Objekts zu einem Parameter in der Definition
der Klasse.
Nahezu jede C++-Bibliothek definiert in irgendeiner Form eine Array-Klasse. Wie Sie
oben am Beispiel der Klasse Lists
gesehen haben, ist es mühsam und ineffizient,
wenn man für Integer, Fließkommazahlen und Animal
-Objekte jeweils eigene Array-
Klassen implementieren muß. Dank des Templates-Konzepts können Sie eine parametrisierte
Array-Klasse aufsetzen und danach spezifizieren, welchen Typ von Objekten
die einzelnen Instanzen des Array aufnehmen sollen. Im übrigen ist in der Standard
Template Library ein Satz von standardisierten Container-Klassen enthalten, die
Implementierungen von Arrays, Listen u.a. einschließen. Wir werden im folgenden
der Frage nachgehen, was zu beachten ist, wenn man eigene Container schreiben
will, so daß sie bis ins Detail verstehen lernen, wie Templates funktionieren. In der
täglichen Praxis werden Sie es allerdings meist vorziehen, die STL-Klassen zu verwenden,
statt eigene Implementierungen aufzusetzen.
Das Erzeugen eines spezifischen Typs aus einem Template nennt man Instantiierung ; die einzelnen Klassen heißen Instanzen des Templates.
Parametrisierte Templates bieten die Möglichkeit, allgemeine Klasse zu definieren. Durch die Übergabe von Typen als Parameter an diese Klasse lassen sich spezifische Instanzen erstellen.
Ein parametrisiertes Array
-Objekt (ein Template für ein Array) erzeugt man wie folgt:
1: template <class T> // die Template und den Parameter deklarieren
2: class Array // die zu parametrisierende Klasse
3: {
4: public:
5: Array();
6: // hier steht die vollstaendige Klassendeklaration
7: };
Jede Deklaration und Definition einer Templateklasse wird mit dem Schlüsselwort
template
eingeleitet. Die Parameter des Templates stehen nach diesem Schlüsselwort.
Die Parameter sind die Elemente, die sich für jede Instanz ändern. Im obigen Codefragment
ändert sich zum Beispiel der Typ der Objekte, die in dem Array gespeichert
werden. Eine Instanz speichert vielleicht ein Feld von Integer-Werten, während eine
andere ein Feld von Animal
-Objekten aufnimmt.
Im Beispiel ist für den Parameter das Schlüsselwort class
mit einem nachfolgenden T
angegeben. Das Schlüsselwort class
kennzeichnet den Parameter als Typ. Der Bezeichner
T
wird im restlichen Teil der Template-Definition als Platzhalter für den parametrisierten
Typ verwendet. Eine Instanz der Klasse ersetzt T
jeweils durch int
, während
eine andere Instanz den Platzhalter T
durch ein Cat
-Objekt ersetzt.
Um eine int
- und eine Cat
-Instanz der parametrisierten Array
-Klasse zu erzeugen,
schreibt man zum Beispiel:
Array<int> einIntArray;
Array<Cat> einCatArray;
Das Objekt einIntArray
ist vom Typ »Array von Integern«, das Objekt einCatArray
vom Typ »Array von Cat
-Objekten«. Den Typ Array<int>
können Sie jetzt überall dort
verwenden, wo normalerweise eine Typangabe steht - beispielsweise beim Rückgabewert
einer Funktion, als Parameter an eine Funktion und so weiter. Listing 19.1 zeigt
die vollständige Deklaration des rudimentären Array
-Templates.
Listing 19.1: Template für eine Array-Klasse
1: // Listing 19.1 Template fuer eine Array-Klasse
2: #include <iostream.h>
3: const int DefaultSize = 10;
4:
5: template <class T> // das Template und die Parameter deklarieren
6: class Array // die parametrisierte Klasse
7: {
8: public:
9: // Konstruktoren
10: Array(int itsSize = DefaultSize);
11: Array(const Array &rhs);
12: ~Array() { delete [] pType; }
13:
14: // Operatoren
15: Array& operator=(const Array&);
16: T& operator[](int offSet) { return pType[offSet]; }
17:
18: // Zugriff
19: int getSize() { return itsSize; }
20:
21: private:
22: T *pType;
23: int itsSize;
24: };
Es gibt keine Ausgabe; dies ist ein unvollständiges Programm.
Die Definition des Templates beginnt in Zeile 5 mit dem Schlüsselwort template
und
dem nachfolgenden Parameter. In diesem Fall wird der Parameter durch das Schlüsselwort
class
als Typangabe identifiziert und der Bezeichner T
repräsentiert den parametrisierten
Typ.
Von Zeile 6 bis zum Ende des Templates in Zeile 24 gleicht die Deklaration jeder anderen
Klassendeklaration. Der einzige Unterschied ist, daß überall wo üblicherweise
der Typ des Objekts stehen würde, der Bezeichner T
verwendet wird. Nehmen Sie
zum Beispiel den Operator []
, der eine Referenz auf ein Objekt im Array zurückliefern
sollte: Er deklariert als Rückgabetyp eine Referenz auf T
.
Wird eine Instanz für ein Integer-Array deklariert, wird der Operator = für dieses Array
eine Referenz auf einen Integer zurückliefern. Wird eine Instanz für ein Array von Animal
-Objekten deklariert, wird der Operator = für dieses Array eine Referenz auf ein
Animal
-Objekt zurückliefern.
Innerhalb der Klassendeklaration kann der Bezeichner Array
ohne weitere Qualifizierung
verwendet werden. Außerhalb der Klassendeklaration bezieht man sich auf die
Klasse durch den Ausdruck Array<T>
. Wenn Sie zum Beispiel den Konstruktor außerhalb
der Klassendeklaration aufsetzen, müssen Sie schreiben:
template <class T>
Array<T>::Array(int size):
itsSize = size
{
pType = new T[size];
for (int i = 0; i<size; i++)
pType[i] = 0;
}
Die Deklaration in der ersten Zeile des obigen Codefragments ist nötig, um den Typ
(hier class T
) zu identifizieren. Der Template-Name ist Array<T>,
und die Funktion
heißt Array(int size)
.
Der Rest der Funktion sieht genauso aus wie für jede andere Funktion, die nicht Teil eines Templates ist. Viele Programmierer gehen deshalb so vor, daß sie die betreffenden Klassen und Funktionen zuerst als normale Deklarationen aufsetzen und testen, bevor sie sie in Templates verwandeln.
Zur vollständigen Implementierung des Array-Templates müssen noch verschiedene Funktionen wie der Kopierkonstruktor, der =-Operator etc. aufgesetzt werden. Listing 19.2 enthält ein einfaches Testprogramm für die Template-Klasse.
Einige ältere Compiler unterstützen keine Templates. Templates sind jedoch Teil des ANSI-C++-Standards, und alle führenden Compiler-Hersteller unterstützen Templates in ihren aktuellen Versionen. Wenn Sie einen sehr alten Compiler verwenden, werden Sie die Übungen in diesem Kapitel weder kompilieren noch ausführen können. Sie sollten das Kapitel aber trotzdem zu Ende lesen. Die Übungen können Sie dann später durchgehen, wenn Sie sich eine aktuellere Compiler-Version beschafft haben.
Listing 19.2: Implementierung des Array-Templates
1: #include <iostream.h>
2:
3: const int DefaultSize = 10;
4:
5: // Deklaration einer einfachen Animal-Klasse, um spaeter
6: // ein Feld von Animals anlegen zu koennen
7:
8: class Animal
9: {
10: public:
11: Animal(int);
12: Animal();
13: ~Animal() {}
14: int GetWeight() const { return itsWeight; }
15: void Display() const { cout << itsWeight; }
16: private:
17: int itsWeight;
18: };
19:
20: Animal::Animal(int weight):
21: itsWeight(weight)
22: {}
23:
24: Animal::Animal():
25: itsWeight(0)
26: {}
27:
28:
29: template <class T> // Das Template und den Parameter deklarieren
30: class Array // die parametrisierte Klasse
31: {
32: public:
33: // Konstruktoren
34: Array(int itsSize = DefaultSize);
35: Array(const Array &rhs);
36: ~Array() { delete [] pType; }
37:
38: // Operatoren
39: Array& operator=(const Array&);
40: T& operator[](int offSet) { return pType[offSet]; }
41: const T& operator[](int offSet) const
42: { return pType[offSet]; }
43: // Zugriffsfunktionen
44: int GetSize() const { return itsSize; }
45:
46: private:
47: T *pType;
48: int itsSize;
49: };
50:
51: // Implementierungen
52:
53: // Konstruktor
54: template <class T>
55: Array<T>::Array(int size):
56: itsSize(size)
57: {
58: pType = new T[size];
59: for (int i = 0; i<size; i++)
60: pType[i] = 0;
61: }
62:
63: // Kopierkonstruktor
64: template <class T>
65: Array<T>::Array(const Array &rhs)
66: {
67: itsSize = rhs.GetSize();
68: pType = new T[itsSize];
69: for (int i = 0; i<itsSize; i++)
70: pType[i] = rhs[i];
71: }
72:
73: // =-Operator
74: template <class T>
75: Array<T>& Array<T>::operator=(const Array &rhs)
76: {
77: if (this == &rhs)
78: return *this;
79: delete [] pType;
80: itsSize = rhs.GetSize();
81: pType = new T[itsSize];
82: for (int i = 0; i<itsSize; i++)
83: pType[i] = rhs[i];
84: return *this;
85: }
86:
87: // Testprogramm
88: int main()
89: {
90: Array<int> theArray; // Array von Integern
91: Array<Animal> theZoo; // Array von Animals
92: Animal *pAnimal;
93:
94: // Array fuellen
95: for (int i = 0; i < theArray.GetSize(); i++)
96: {
97: theArray[i] = i*2;
98: pAnimal = new Animal(i*3);
99: theZoo[i] = *pAnimal;
100: delete pAnimal;
101: }
102: // Inhalt des Array ausgeben
103: for (int j = 0; j < theArray.GetSize(); j++)
104: {
105: cout << "dasArray[" << j << "]:\t";
106: cout << theArray[j] << "\t\t";
107: cout << "derZoo[" << j << "]:\t";
108: theZoo[j].Display();
109: cout << endl;
110: }
111:
112: return 0;
113: }
dasArray[0]: 0 derZoo[0]: 0
dasArray[1]: 2 derZoo[1]: 3
dasArray[2]: 4 derZoo[2]: 6
dasArray[3]: 6 derZoo[3]: 9
dasArray[4]: 8 derZoo[4]: 12
dasArray[5]: 10 derZoo[5]: 15
dasArray[6]: 12 derZoo[6]: 18
dasArray[7]: 14 derZoo[7]: 21
dasArray[8]: 16 derZoo[8]: 24
dasArray[9]: 18 derZoo[9]: 27
In den Zeilen 8 bis 26 ist eine rudimentäre Klasse Animal
deklariert, die es uns ermöglicht,
Objekte eines benutzerdefinierten Typs zu erzeugen und in das Array aufzunehmen.
Zeile 29 zeigt an, daß es sich bei der nachfolgenden Deklaration um ein Template
handelt und daß es sich bei dem Parameter des Templates um einen Typ namens T
handelt. Wie man sehen kann, definiert die Klasse Array
zwei Konstruktoren, von denen
der erste eine Größenangabe als Argument übernimmt und als Vorgabeargument
die Integer-Konstante DefaultSize
verwendet.
An Operatoren sind der Zuweisungs- und der Offset-Operator deklariert, wobei für
den letzteren sowohl eine const
- als auch eine nicht-const
-Variante definiert ist. Die
einzige vorgesehene Zugriffsfunktion ist GetSize()
, die die Größe des Arrays zurückliefert.
Man könnte sich zweifelsohne eine umfangreichere Schnittstelle vorstellen, und - machen wir uns nichts vor - für jedes ernsthafte Array-Programm wäre die obige Implementierung unzureichend. Operatoren zum Löschen von Elementen, Optionen zum Erweitern oder Komprimieren des Array und anderes mehr wären das Minimum für eine realistische Implementierung. All diese Funktionen werden aber von den STL- Container-Klassen zur Verfügung gestellt, die wir uns gegen Ende dieses Kapitels näher anschauen werden.
Zu den privaten Daten gehören die Größe des Arrays und ein Zeiger auf die im Speicher abgelegten Objekte.
Wenn Sie ein Array-Objekt an eine Funktion weiterreichen wollen, müssen Sie eine
spezielle Instanz des Array, und nicht das Template, übergeben. Wenn Sie also beispielsweise
eine Funktion EineFunktion()
haben, die ein Integer-Array als Parameter
erwartet, schreiben Sie:
void EineFunktion(Array<int>&); // ok
Nicht korrekt wäre dagegen die Deklaration
void EineFunktion(Array<T>&); // Fehler!
da nicht klar ist, was ein T& ist. Ebenfalls falsch, ist die folgende Schreibweise
void EineFunktion(Array &); // Fehler!
denn es gibt keine Klasse Array
- nur das Template und die Instanzen.
Für eine allgemeiner gehaltene Lösung muß man eine Template-Funktion deklarieren
template <class T>
void MeineTemplateFunktion(Array<T>&); // ok
Hier wird die Funktion MeineTemplateFunktion()
durch die erste Zeile als Templatefunktion
ausgezeichnet. Templatefunktionen können im übrigen beliebige Namen haben,
eben ganz wie die normalen Funktionen auch.
Templatefunktionen haben den Vorteil, daß man ihnen neben den Template-Instanzen auch die parametrisierte Form übergeben kann, beispielsweise:
template <class T>
void MeineAndereFunktion(Array<T>&, Array<int>&); // ok
Beachten Sie, daß diese Funktion zwei Arrays übernimmt: ein parametrisiertes Array und ein Integer-Array. Das erste Array kann ein Array für einen beliebigen Objekttyp sein, das zweite ist immer ein Integer-Array.
Template-Klassen können drei Arten von Friends deklarieren:
Sie können in Ihrer Template-Klasse jede beliebige Klasse oder Funktion als Friend deklarieren.
Die einzelnen Instanzen der Templateklasse übernehmen die friend
-Deklaration,
so als wäre die Deklaration in der speziellen Instanz erfolgt. Listing 19.3 erweitert
die Template-Definition der Array
-Klasse um eine einfache friend
-Funktion namens
Intrude()
. Im Testprogramm wird die Funktion aufgerufen. Da Intrude()
eine friend
-
Funktion ist, kann sie auf die privaten Daten der Array
-Klasse zugreifen, da sie aber
selbst keine Template-Funktion ist, kann sie nur für Integer-Arrays aufgerufen werden.
Listing 19.3: friend-Funktion, die kein Template ist
1: // Listing 19.3 - Typenspezfische friend-Funktion in Template
2:
3: #include <iostream.h>
4:
5: const int DefaultSize = 10;
6:
7: // Deklaration einer einfachen Animal-Klasse, um spaeter
8: // ein Feld von Animals anlegen zu koennen
9:
10: class Animal
11: {
12: public:
13: Animal(int);
14: Animal();
15: ~Animal() {}
16: int GetWeight() const { return itsWeight; }
17: void Display() const { cout << itsWeight; }
18: private:
19: int itsWeight;
20: };
21:
22: Animal::Animal(int weight):
23: itsWeight(weight)
24: {}
25:
26: Animal::Animal():
27: itsWeight(0)
28: {}
29:
30: template <class T> // Template und Parameter deklarieren
31: class Array // die parametrisierte Klasse
32: {
33: public:
34: // Konstruktoren
35: Array(int itsSize = DefaultSize);
36: Array(const Array &rhs);
37: ~Array() { delete [] pType; }
38:
39: // Operatoren
40: Array& operator=(const Array&);
41: T& operator[](int offSet) { return pType[offSet]; }
42: const T& operator[](int offSet) const
43: { return pType[offSet]; }
44: // Zugriffsfunktionen
45: int GetSize() const { return itsSize; }
46:
47: // friend-Funktion
48: friend void Intrude(Array<int>);
49:
50: private:
51: T *pType;
52: int itsSize;
53: };
54:
55: // friend-Funktion. Kein Template, kann nur fuer Integer-Arrays
56: // aufgerufen werden! Greift auf private Daten zu.
57: void Intrude(Array<int> theArray)
58: {
59: cout << "\n*** Zugriff auf private Daten ***\n";
60: for (int i = 0; i < theArray.itsSize; i++)
61: cout << "i: " << theArray.pType[i] << endl;
62: cout << "\n";
63: }
64:
65: // Implementierungen...
66:
67: // Konstruktor
68: template <class T>
69: Array<T>::Array(int size):
70: itsSize(size)
71: {
72: pType = new T[size];
73: for (int i = 0; i<size; i++)
74: pType[i] = 0;
75: }
76:
77: // Kopierkonstruktor
78: template <class T>
79: Array<T>::Array(const Array &rhs)
80: {
81: itsSize = rhs.GetSize();
82: pType = new T[itsSize];
83: for (int i = 0; i<itsSize; i++)
84: pType[i] = rhs[i];
85: }
86:
87: // =-Operator
88: template <class T>
89: Array<T>& Array<T>::operator=(const Array &rhs)
90: {
91: if (this == &rhs)
92: return *this;
93: delete [] pType;
94: itsSize = rhs.GetSize();
95: pType = new T[itsSize];
96: for (int i = 0; i<itsSize; i++)
97: pType[i] = rhs[i];
98: return *this;
99: }
100:
101: // Testprogramm
102: int main()
103: {
104: Array<int> theArray; // Array von Integern
105: Array<Animal> theZoo; // Array von Animals
106: Animal *pAnimal;
107:
108: // Array fuellen
109: for (int i = 0; i < theArray.GetSize(); i++)
110: {
111: theArray[i] = i*2;
112: pAnimal = new Animal(i*3);
113: theZoo[i] = *pAnimal;
114: }
115:
116: int j;
117: for (j = 0; j < theArray.GetSize(); j++)
118: {
119: cout << "derZoo[" << j << "]:\t";
120: theZoo[j].Display();
121: cout << endl;
122: }
123: cout << "Jetzt die friend-Funktion aufrufen, um ";
124: cout << "die Elemente von Array<int> auszugeben";
125: Intrude(theArray);
126:
127: cout << "\n\nFertig.\n";
128: return 0;
129: }
derZoo[0]: 0
derZoo[1]: 3
derZoo[2]: 6
derZoo[3]: 9
derZoo[4]: 12
derZoo[5]: 15
derZoo[6]: 18
derZoo[7]: 21
derZoo[8]: 24
derZoo[9]: 27
Jetzt die friend-Funktion aufrufen, um die Elemente von Array<int> auszugeben
*** Zugriff auf private Daten ***
i: 0
i: 2
i: 4
i: 6
i: 8
i: 10
i: 12
i: 14
i: 16
i: 18
Fertig.
Die Deklaration des Array-Templates wurde um die Aufnahme der friend
-Funktion
Intrude()
erweitert. Durch deren Deklaration wird festgelegt, daß jede Instanz des
Array
-Templates für int
-Werte die Funktion Intrude()
als friend
-Funktion zu betrachten
hat, so daß die Funktion auf die privaten Datenelemente und Funktionen der
Array-Instanz zugreifen kann.
In Zeile 60 greift die Funktion Intrude()
direkt auf itsSize
und in Zeile 61 auf pType
zu, um die Elemente im Array auszugeben. An sich hätten wir dazu keine friend
-
Funktion benötigt, denn die Array-Klasse stellt zu diesem Zweck eigene Funktionen
zur Verfügung, aber es ist ein anschauliches Beispiel dafür, wie friend
-Funktionen in
Templates deklariert werden können.
Für den Einsatz der Array
-Klasse wäre es ganz nützlich, wenn wir einen Ausgabeoperator
für Array
definieren würden. Nun könnte man hingehen, und zu diesem Zweck
für jeden möglichen Typ von Array einen eigenen Ausgabe-Operator deklarieren,
doch widerspräche dies völlig den Überlegungen, die uns überhaupt zur Implementierung
als Template geführt haben.
Was wir wirklich benötigen, ist ein Ausgabe-Operator, der jeden möglichen Typ von
Array
verarbeiten kann.
ostream& operator<< (ostream&, Array<T>&);
Um dies zu erreichen, müssen wir den Operator <<
als Funktionstemplate deklarieren.
template <class T> ostream& operator<< (ostream&, Array<T>&)
Nachdem der Operator <<
als Template deklariert ist, muß nur noch eine passende
Implementierung aufgesetzt werden. Listing 19.4 erweitert das Array
-Template um
die Deklaration und Implementierung des <<
-Operators.
Listing 19.4: Einsatz des ostream-Operators
1: #include <iostream.h>
2:
3: const int DefaultSize = 10;
4:
5: class Animal
6: {
7: public:
8: Animal(int);
9: Animal();
10: ~Animal() {}
11: int GetWeight() const { return itsWeight; }
12: void Display() const { cout << itsWeight; }
13: private:
14: int itsWeight;
15: };
16:
17: Animal::Animal(int weight):
18: itsWeight(weight)
19: {}
20:
21: Animal::Animal():
22: itsWeight(0)
23: {}
24:
25: template <class T> // Template und Parameter deklarieren
26: class Array // die parametrisierte Klasse
27: {
28: public:
29: // Konstruktoren
30: Array(int itsSize = DefaultSize);
31: Array(const Array &rhs);
32: ~Array() { delete [] pType; }
33:
34: // Operatoren
35: Array& operator=(const Array&);
36: T& operator[](int offSet) { return pType[offSet]; }
37: const T& operator[](int offSet) const
38: { return pType[offSet]; }
39: // Zugriffsfunktionen
40: int GetSize() const { return itsSize; }
41:
42: friend ostream& operator<< (ostream&, Array<T>&);
43:
44: private:
45: T *pType;
46: int itsSize;
47: };
48:
49: template <class T>
50: ostream& operator<< (ostream& output, Array<T>& theArray)
51: {
52: for (int i = 0; i<theArray.GetSize(); i++)
53: output << "[" << i << "] " << theArray[i] <<endl; return output;
54: }
55:
56: // Implementierungen...
57:
58: // Konstruktor
59: template <class T>
60: Array<T>::Array(int size):
61: itsSize(size)
62: {
63: pType = new T[size];
64: for (int i = 0; i<size; i++)
65: pType[i] = 0;
66: }
67:
68: // Kopierkonstruktor
69: template <class T>
70: Array<T>::Array(const Array &rhs)
71: {
72: itsSize = rhs.GetSize();
73: pType = new T[itsSize];
74: for (int i = 0; i<itsSize; i++)
75: pType[i] = rhs[i];
76: }
77:
78: // =-Operator
79: template <class T>
80: Array<T>& Array<T>::operator=(const Array &rhs)
81: {
82: if (this == &rhs)
83: return *this;
84: delete [] pType;
85: itsSize = rhs.GetSize();
86: pType = new T[itsSize];
87: for (int i = 0; i<itsSize; i++)
88: pType[i] = rhs[i];
89: return *this;
90: }
91:
92: int main()
93: {
94: bool Stop = false; // Flag fuer die Schleife
95: int offset, value;
96: Array<int> theArray;
97:
98: while (!Stop)
99: {
100: cout << "Offset (0-9) ";
101: cout << "und Wert (-1 fuer Abbruch) eingeben: " ;
102: cin >> offset >> value;
103:
104: if (offset < 0)
105: break;
106:
107: if (offset > 9)
108: {
109: cout << "***Bitte Werte zwischen 0 und 9.***\n";
110: continue;
111: }
112:
113: theArray[offset] = value;
114: }
115:
116: cout << "\nHier das vollstaendige Array:\n";
117: cout << theArray << endl;
118: return 0;
119: }
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 1 10
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 2 20
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 3 30
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 4 40
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 5 50
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 6 60
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 7 70
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 8 80
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 9 90
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 10 10
***Bitte Werte zwischen 0 und 9.***
Offset (0-9) und Wert (-1 für Abbruch) eingeben: -1 -1
Hier das vollständige Array:
[0] 0
[1] 10
[2] 20
[3] 30
[4] 40
[5] 50
[6] 60
[7] 70
[8] 80
[9] 90
In Zeile 42 wird das Funktions-Template operator<<()
als Friend des Klassen-Templates
Array
deklariert. Da operator<<()
als Template-Funktion implementiert ist, verfügt
automatisch jede Instanz des parametrisierten Array
-Typs über einen eigenen <<-
Operator. Die Implementierung des Operators beginnt in Zeile 49 und geht die Elemente
des Arrays einzeln durch. Damit dies funktioniert, muß der Operator für jeden
möglichen Typ von Objekt, das im Array gespeichert ist, definiert sein.
Template-Elemente kann man genauso wie jeden anderen Typ behandeln. Sie lassen sich als Parameter und Rückgabewerte von Funktionen sowohl als Referenz als auch als Wert übergeben. Listing 19.5 zeigt die Übergabe von Template-Objekten.
Listing 19.5: Template-Objekte an Funktionen übergeben und zurückliefern
1: #include <iostream.h>
2:
3: const int DefaultSize = 10;
4:
5: // Ein einfache Klasse zum Fuellen des Array
6: class Animal
7: {
8: public:
9: // Konstruktoren
10: Animal(int);
11: Animal();
12: ~Animal();
13:
14: // Zugriffsfunktionen
15: int GetWeight() const { return itsWeight; }
16: void SetWeight(int theWeight) { itsWeight = theWeight; }
17:
18: // friend-Operator
19: friend ostream& operator<< (ostream&, const Animal&);
20:
21: private:
22: int itsWeight;
23: };
24:
25: // Ausgabeoperator fuer Animals
26: ostream& operator<<
27: (ostream& theStream, const Animal& theAnimal)
28 {
29: theStream << theAnimal.GetWeight();
30: return theStream;
31: }
32:
33: Animal::Animal(int weight):
34: itsWeight(weight)
35: {
36: // cout << "Animal(int)\n";
37: }
38:
39: Animal::Animal():
40: itsWeight(0)
41: {
42: // cout << "Animal()\n";
43: }
44:
45: Animal::~Animal()
46: {
47: // cout << "Loest Animal auf...\n";
48: }
49:
50: template <class T> // Template und Parameter deklarieren
51: class Array // die parametrisierte Klasse
52: {
53: public:
54: Array(int itsSize = DefaultSize);
55: Array(const Array &rhs);
56: ~Array() { delete [] pType; }
57:
58: Array& operator=(const Array&);
59: T& operator[](int offSet) { return pType[offSet]; }
60: const T& operator[](int offSet) const
61: { return pType[offSet]; }
62: int GetSize() const { return itsSize; }
63
64: // friend-Funktion
65: friend ostream& operator<< (ostream&, const Array<T>&);
66:
67: private:
68: T *pType;
69: int itsSize;
70: };
71:
70: template <class T>
72: ostream& operator<< (ostream& output, const Array<T>& theArray)
73: {
74: for (int i = 0; i<theArray.GetSize(); i++)
75: output << "[" << i << "] " << theArray[i] << endl;
76: return output;
77: }
78:
79: // Implementierungen...
80:
81: // Konstruktor
82: template <class T>
83: Array<T>::Array(int size):
84: itsSize(size)
85: {
86: pType = new T[size];
87: for (int i = 0; i<size; i++)
88: pType[i] = 0;
89: }
90:
91: // Kopierkonstruktor
92: template <class T>
93: Array<T>::Array(const Array &rhs)
94: {
95: itsSize = rhs.GetSize();
96: pType = new T[itsSize];
97: for (int i = 0; i<itsSize; i++)
98: pType[i] = rhs[i];
99: }
100:
101: void IntFillFunction(Array<int>& theArray);
102: void AnimalFillFunction(Array<Animal>& theArray);
103:
104: int main()
105: {
106: Array<int> intArray;
107: Array<Animal> animalArray;
108: IntFillFunction(intArray);
109: AnimalFillFunction(animalArray);
110: cout << "intArray...\n" << intArray;
111: cout << "\nanimalArray...\n" << animalArray << endl;
112: return 0;
113: }
114:
115: void IntFillFunction(Array<int>& theArray)
116: {
117: bool Stop = false;
118: int offset, value;
119: while (!Stop)
120: {
121: cout << "Offset (0-9) ";
122: cout << "und Wert (-1 fuer Abbruch) eingeben: " ;
123: cin >> offset >> value;
124: if (offset < 0)
125: break;
126: if (offset > 9)
127: {
128: cout << "***Bitte Werte zwischen 0 und 9.***\n";
129: continue;
130: }
131: theArray[offset] = value;
132: }
133: }
134:
135:
136: void AnimalFillFunction(Array<Animal>& theArray)
137: {
138: Animal * pAnimal;
139: for (int i = 0; i<theArray.GetSize(); i++)
140: {
141: pAnimal = new Animal;
142: pAnimal->SetWeight(i*100);
143: theArray[i] = *pAnimal;
144: delete pAnimal; // in Array steht Kopie
145: }
146: }
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 1 10
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 2 20
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 3 30
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 4 40
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 5 50
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 6 60
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 7 70
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 8 80
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 9 90
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 10 10
***Bitte Werte zwischen 0 und 9.***
Offset (0-9) und Wert (-1 für Abbruch) eingeben: -1 -1
intArray:...
[0] 0
[1] 10
[2] 20
[3] 30
[4] 40
[5] 50
[6] 60
[7] 70
[8] 80
[9] 90
animalArray:...
[0] 0
[1] 100
[2] 200
[3] 300
[4] 400
[5] 500
[6] 600
[7] 700
[8] 800
[9] 900
Die Besprechung der Array
-Klasse lasse ich zum größten Teil aus, um Platz zu sparen.
Die Animal
-Klasse ist in den Zeilen 6 bis 23 deklariert. Obwohl es sich dabei nur um
eine rudimentäre und vereinfachte Klasse handelt, definiert sie doch ihren eigenen
Ausgabe-Operator (<<), zum Ausgeben der Animal
-Objekte. Ausgegeben wird dabei
einfach das Gewicht der Tiere.
Beachten Sie, daß die Klasse Animal
einen Standardkonstruktor besitzt. Dies muß so
sein, denn beim Einfügen eines Objektes in ein Array wird der Standardkonstruktor
des Objekts verwendet, um das Objekt zu erzeugen. Welche Komplikationen dies bereitet,
werden Sie noch sehen.
In Zeile 101 ist die Funktion IntFillFunction()
deklariert. Am Prototyp der Funktion
kann man ablesen, daß diese Funktion ein Integer-Array
als Argument übernimmt.
IntFillFunction()
ist kein Funktions-Template, sie erwartet daher einen ganz bestimmten
Typ von Array - ein Integer-Array
. In gleicher Weise ist in Zeile 102 die
Funktion AnimalFillFunction()
für Animal
-Arrays deklariert.
Die Implementierungen der beiden Funktionen sind nicht identisch, da das Füllen eines
Array mit Integer-Werten eine andere Vorgehensweise erfordert, als das Füllen eines
Array mit Animal
-Objekten.
Wenn Sie in Listing 19.5 die Auskommentierung der Ausgabeanweisungen in den
Konstruktoren und dem Destruktor der Klasse Animal
aufheben, werden unerwartete
Konstruktionen und Auflösungen von Animal
-Objekten sichtbar.
Wenn ein Objekt in ein Array eingefügt wird, wird der Standardkonstruktor des Objekts aufgerufen. Danach weist der Array-Konstruktor noch jedem Objekt im Array den Wert 0 zu (vergleiche Zeilen 59 und 60 aus Listing 19.2).
Wenn Sie einAnimal = (Animal) 0;
schreiben, rufen Sie den Standardzuweisungsoperator
=
für Animal
auf. Dieser erzeugt ein temporäres Animal
-Objekt, wozu er sich des
Konstruktor bedient, der ein int
-Argument akzeptiert. Das temporäre Objekt wird auf
der rechten Seite des =
-Operators verwendet und dann aufgelöst.
Dies ist allerdings unnötige Zeitverschwendung, denn das Animal
-Objekt wurde ja bereits
korrekt initialisiert. Sie können aber auch nicht einfach diese Zeile löschen, da Integer-Werte
nicht automatisch mit dem Wert 0 initialisiert werden. Die Lösung besteht
darin, dem Template mitzuteilen, daß es für Animal
-Objekte einen speziellen Konstruktor
verwenden soll.
Listing 19.6 zeigt, wie Sie eine spezielle Implementierung für die Animal
-Klasse vorgeben
können.
Listing 19.6: Template-Implementierungen spezialisieren
1: #include <iostream.h>
2:
3: const int DefaultSize = 3;
4:
5: // Einfache Klasse zum Fuellen des Array
6: class Animal
7: {
8: public:
9: // Konstruktoren
10: Animal(int);
11: Animal();
12: ~Animal();
13:
14: // Zugriffsfunktionen
15: int GetWeight() const { return itsWeight; }
16: void SetWeight(int theWeight) { itsWeight = theWeight; }
17:
18: // friend-Operatoren
19: friend ostream& operator<< (ostream&, const Animal&);
20:
21: private:
22: int itsWeight;
23: };
24:
25: // Operator zum Ausgeben von Animal-Objekten
26: ostream& operator<<
27: (ostream& theStream, const Animal& theAnimal)
28: {
29: theStream << theAnimal.GetWeight();
30: return theStream;
31: }
32:
33: Animal::Animal(int weight):
34: itsWeight(weight)
35: {
36: cout << "animal(int) ";
37: }
38:
39: Animal::Animal():
40: itsWeight(0)
41: {
42: cout << "animal() ";
43: }
44:
45: Animal::~Animal()
46: {
47: cout << "animal wird aufgeloest...";
48: }
49:
50: template <class T> // Template und Parameter deklarieren
51: class Array // die parametrisierte Klasse
52: {
53: public:
54: Array(int itsSize = DefaultSize);
55: Array(const Array &rhs);
56: ~Array() { delete [] pType; }
57:
58: // Operatoren
59: Array& operator=(const Array&);
60: T& operator[](int offSet) { return pType[offSet]; }
61: const T& operator[](int offSet) const
62: { return pType[offSet]; }
62:
63: // Zugriffsfunktionen
64: int GetSize() const { return itsSize; }
65:
66: // friend-Funktion
67: friend ostream& operator<< (ostream&, const Array<T>&);
68:
69: private:
70: T *pType;
71: int itsSize;
72: };
73:
74: template <class T>
75: Array<T>::Array(int size = DefaultSize):
76: itsSize(size)
77: {
78: pType = new T[size];
79: for (int i = 0; i<size; i++)
80: pType[i] = (T)0;
81: }
82:
83: template <class T>
84: Array<T>& Array<T>::operator=(const Array &rhs)
85: {
86: if (this == &rhs)
87: return *this;
88: delete [] pType;
89: itsSize = rhs.GetSize();
90: pType = new T[itsSize];
91: for (int i = 0; i<itsSize; i++)
92: pType[i] = rhs[i];
93: return *this;
94: }
95: template <class T>
96: Array<T>::Array(const Array &rhs)
97: {
98: itsSize = rhs.GetSize();
99: pType = new T[itsSize];
100: for (int i = 0; i<itsSize; i++)
101: pType[i] = rhs[i];
102: }
103:
104:
105: template <class T>
106: ostream& operator<< (ostream& output, const Array<T>& theArray)
107: {
108: for (int i = 0; i<theArray.GetSize(); i++)
109: output << "[" << i << "] " << theArray[i] << endl;
110: return output;
111: }
112:
113:
114: Array<Animal>::Array(int AnimalArraySize):
115: itsSize(AnimalArraySize)
116: {
117: pType = new Animal[AnimalArraySize];
118: }
119:
120:
121: void IntFillFunction(Array<int>& theArray);
122: void AnimalFillFunction(Array<Animal>& theArray);
123:
124: int main()
125: {
126: Array<int> intArray;
127: Array<Animal> animalArray;
128: IntFillFunction(intArray);
129: AnimalFillFunction(animalArray);
130: cout << "intArray...\n" << intArray;
131: cout << "\nanimalArray...\n" << animalArray << endl;
132: return 0;
133: }
134:
135: void IntFillFunction(Array<int>& theArray)
136: {
137: bool Stop = false;
138: int offset, value;
139: while (!Stop)
140: {
141: cout << "Offset (0-9) ";
142: cout << "und Wert (-1 fuer Abbruch) eingeben: " ;
143: cin >> offset >> value;
144: if (offset < 0)
145: break;
146: if (offset > 9)
147: {
148: cout << "***Bitte Werte zwischen 0 und 9.***\n";
149: continue;
150: }
151: theArray[offset] = value;
152: }
153: }
154:
155:
156: void AnimalFillFunction(Array<Animal>& theArray)
157: {
158: Animal * pAnimal;
159: for (int i = 0; i<theArray.GetSize(); i++)
160: {
161: pAnimal = new Animal(i*10);
162: theArray[i] = *pAnimal;
163: delete pAnimal;
164: }
165: }
Die Zeilennumerierung der Ausgabe wurde nachträglich hinzugefügt, damit Sie der Analyse besser folgen können. Wenn Sie das Programm ausführen, erfolgt die Ausgabe ohne Zeilennummern.
1: animal() animal() animal()
Offset (0-9) und Wert (-1 für Abbruch) eingeben: 0 0
2: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 1 1
3: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 2 2
4: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 3 3
5: Offset (0-9) und Wert (-1 für Abbruch) eingeben: -1 -1
6: animal(int) animal wird aufgeloest...animal(int) animal wird aufgeloest...animal(int) animal wird aufgeloest...initArray...
7: [0] 0
8: [1] 1
9: [2] 2
10:
11: animal array...
12: [0] 0
13: [1] 10
14: [2] 20
15:
16: animal wird aufgeloest... animal wird aufgeloest... animal wird aufgeloest...
17: <<< Zweiter Durchgang >>>
18: animal(int) animal wird aufgeloest...
19: animal(int) animal wird aufgeloest...
20: animal(int) animal wird aufgeloest...
21: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 0 0
22: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 1 1
23: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 2 2
24: Offset (0-9) und Wert (-1 für Abbruch) eingeben: 3 3
25: animal(int)
26: animal wird aufgeloest...
27: animal(int)
28: animal wird aufgeloest...
29: animal(int)
30: animal wird aufgeloest...
31: initArray...
32: [0] 0
33: [1] 1
34: [2] 2
35:
36: animal array...
37: [0] 0
38: [1] 10
39: [2] 20
40:
41: animal wird aufgeloest...
42: animal wird aufgeloest...
43: animal wird aufgeloest...
In Listing 19.6 sind beide Klassen ungekürzt, mit allen Kontrollausgaben, abgedruckt,
so daß Sie nachvollziehen können, wie temporäre Animal
-Objekte erzeugt und wieder
aufgelöst werden. Der Wert der Konstante DefaultSize
wurde auf 3 zurückgesetzt, um
die Ausgabe übersichtlicher zu halten.
Die Konstruktoren und Destruktoren der Klasse Animal, Zeilen 33 bis 48, geben jeweils eine entsprechende Mitteilung aus, wenn sie aufgerufen werden.
In den Zeilen 74 bis 81 ist ein Template-Konstruktor für Array
deklariert. Diesem zur
Seite gestellt ist der spezialisierte Konstruktor für Animal
-Arrays (Zeilen 114 bis 118).
Beachten Sie, daß in diesem spezialisierten Konstruktor allein der Standardkonstruktor
für die Initialisierung der einzelnen Animal
-Objekte verwendet wird - eine zusätzliche
Zuweisung erfolgt nicht mehr.
Beim Ausführen des Programms erzeugt dieses die oben abgedruckte Ausgabe. In Zeile 1 der Ausgabe sehen Sie die drei Standardkonstruktorenaufrufe beim Anlegen des Arrays. Der Anwender gibt vier Zahlen ein, und diese werden in das Integer-Array eingefügt.
Dann springt die Programmausführung zur Funktion AnimalFillFunction()
. In der
Funktion wird auf dem Heap ein temporäres Animal
-Objekt erzeugt (Zeile 161) und
dazu benutzt, eines der Animal
-Objekte im Array zu modifizieren (Zeile 162). In Zeile
163 wird das temporäre Objekt wieder aufgelöst. Das Ganze wird für alle Elemente im
Array wiederholt und spiegelt sich in Zeile 6 der Ausgabe wider.
Bei Beendigung des Programms werden die Arrays aufgelöst, und wenn die Destruktoren der Arrays aufgerufen werden, werden auch die Objekte in den Arrays aufgelöst (siehe Zeile 16 der Ausgabe).
Für den zweiten Teil der Ausgabe (Zeilen 18 bis 43) wurde die spezialisierte Implementierung
des Array-Konstruktors aus den Zeilen 114 bis 118 des Programms auskommentiert.
Wird das Programm danach ausgeführt, wird der Template-Konstruktor
(Zeilen 74 bis 81) beim Anlegen des Animal
-Array aufgerufen.
Dies führt dazu, daß in den Zeilen 79 und 80 des Programms für jedes Element des
Array ein temporäres Animal
-Objekt angelegt wird - was sich in der Ausgabe in den
18 bis 20 zeigt.
Ansonsten ist die Ausgabe für beide Läufe des Programms, wie zu erwarten, identisch.
Templates können auch statische Elemente deklarieren. Jede Instantiierung des Templates
verfügt dann über seinen eigenen Satz von statischen Daten, sprich ein Satz
pro Klassentyp. Wenn Sie also die Array
-Klasse um ein statisches Datenelement erweitern
(beispielsweise einen Zähler, in dem festgehalten wird, wie viele Arrays angelegt
wurden), erhalten Sie für jeden Typ ein eigenes Datenelement: eines für alle Animal
-Arrays, ein weiteres für alle Integer-Arrays. In Listings 19.7 wurde die Array
-
Klasse um ein statisches Datenelement und eine statische Funktion erweitert.
Listing 19.7: Statische Datenelemente und Funktionen in Templates
1: #include <iostream.h>
2:
3: const int DefaultSize = 3;
4:
5: // Einfache Klasse zum Fuellen des Arrays
6: class Animal
7: {
8: public:
9: // Konstruktoren
10: Animal(int);
11: Animal();
12: ~Animal();
13:
14: // Zugriffsfunktionen
15: int GetWeight() const { return itsWeight; }
16: void SetWeight(int theWeight) { itsWeight = theWeight; }
17:
18: // friend-Operatoren
19: friend ostream& operator<< (ostream&, const Animal&);
20:
21: private:
22: int itsWeight;
23: };
24:
25: // Ausgabeoperator
26: ostream& operator<<
27: (ostream& theStream, const Animal& theAnimal)
28: {
29: theStream << theAnimal.GetWeight();
30: return theStream;
31: }
32:
33: Animal::Animal(int weight):
34: itsWeight(weight)
35: {
36: //cout << "animal(int) ";
37: }
38:
39: Animal::Animal():
40: itsWeight(0)
41: {
42: //cout << "animal() ";
43: }
44:
45: Animal::~Animal()
46: {
47: //cout << "animal aufloesen...";
48: }
49:
50: template <class T> // Template und Parameter deklarieren
51: class Array // die parametrisierte Klasse
52: {
53: public:
54: // Konstruktoren
55: Array(int itsSize = DefaultSize);
56: Array(const Array &rhs);
57: ~Array() { delete [] pType; itsNumberArrays-; }
58:
59: // Operatoren
60: Array& operator=(const Array&);
61: T& operator[](int offSet) { return pType[offSet]; }
62: const T& operator[](int offSet) const
63: { return pType[offSet]; }
64: // Zugriffsfunktionen
65: int GetSize() const { return itsSize; }
66: static int GetNumberArrays() { return itsNumberArrays; }
67:
68: // friend-Funktion
69: friend ostream& operator<< (ostream&, const Array<T>&);
70:
71: private:
72: T *pType;
73: int itsSize;
74: static int itsNumberArrays;
75: };
76:
77: template <class T>
78: int Array<T>::itsNumberArrays = 0;
79:
80: template <class T>
81: Array<T>::Array(int size = DefaultSize):
82: itsSize(size)
83: {
84: pType = new T[size];
85: for (int i = 0; i<size; i++)
86: pType[i] = (T)0;
87: itsNumberArrays++;
88: }
89:
90: template <class T>
91: Array<T>& Array<T>::operator=(const Array &rhs)
92: {
93: if (this == &rhs)
94: return *this;
95: delete [] pType;
96: itsSize = rhs.GetSize();
97: pType = new T[itsSize];
98: for (int i = 0; i<itsSize; i++)
99: pType[i] = rhs[i];
100: }
101:
102: template <class T>
103: Array<T>::Array(const Array &rhs)
104: {
105: itsSize = rhs.GetSize();
106: pType = new T[itsSize];
107: for (int i = 0; i<itsSize; i++)
108: pType[i] = rhs[i];
109: itsNumberArrays++;
110: }
111:
112:
113: template <class T>
114: ostream& operator<< (ostream& output, const Array<T>& theArray)
115: {
116: for (int i = 0; i<theArray.GetSize(); i++)
117: output << "[" << i << "] " << theArray[i] << endl;
118: return output;
119: }
120:
121:
122:
123: int main()
124: {
125:
126: cout << Array<int>::GetNumberArrays() << " Integer-Arrays\n";
127: cout << Array<Animal>::GetNumberArrays();
128: cout << " Animal-Arrays\n\n";
129: Array<int> intArray;
130: Array<Animal> animalArray;
131:
132: cout << intArray.GetNumberArrays() << " Integer-Arrays\n";
133: cout << animalArray.GetNumberArrays();
134: cout << " Animal-Arrays\n\n";
135:
136: Array<int> *pIntArray = new Array<int>;
137:
138: cout << Array<int>::GetNumberArrays() << " Integer-Arrays\n";
139: cout << Array<Animal>::GetNumberArrays();
140: cout << " Animal-Arrays\n\n";
141:
142: delete pIntArray;
143:
144: cout << Array<int>::GetNumberArrays() << " Integer-Arrays\n";
145: cout << Array<Animal>::GetNumberArrays();
146: cout << " Animal-Arrays\n\n";
147: return 0;
148: }
0 Integer-Arrays
0 Animal-Arrays
1 Integer-Arrays
1 Animal-Arrays
2 Integer-Arrays
1 Animal-Arrays
1 Integer-Arrays
1 Animal-Arrays
Die Besprechung der Animal
-Klasse lasse ich aus, um Platz zu sparen. Die Array
-Klasse
wurde um die Deklaration der statischen Variable itsNumberArrays
erweitert (Zeile
74), und weil diese private
ist, kommt in Zeile 66 noch eine statische public
-Zugruffsfunktion
GetNumberArrays()
hinzu.
Für die Initialisierung der statischen Daten muß man über den vollständigen Template-
Qualifizierer auf das Element zugreifen, so geschehen in den Zeilen 77 und 78. Die
Konstruktoren und der Destruktor der Klasse Array
wurden angepaßt, so daß in der
statischen Variable festgehalten wird, wie viele Arrays gerade existieren.
Der Zugriff auf die statischen Elemente läuft genauso ab wie der Zugriff auf die statischen Elemente jeder normalen Klasse auch: entweder über ein existierendes Objekt (siehe Zeilen 132 und 133) oder durch Angabe des vollen Klassenspezifizierers (siehe Zeilen 126 und 127). Beachten Sie aber, daß Sie für den Zugriff auf die statischen Daten einen spezifischen Array-Typ verwenden müssen, da es ja für jeden Typ eine eigene Variable gibt.
Zu den Neuerungen in C++ gehört die Aufnahme der Standard Template Library (STL) in den Standard. Alle bedeutenden Compiler-Hersteller bieten die STL an. Bei der STL handelt sich um eine Bibliothek aus Template-basierten Container-Klassen, einschließlich Vektoren, Listen, Warteschlangen und Stacks. Darüber hinaus enthält die STL auch eine Reihe allgemeiner Algorithmen, beispielsweise Routinen zum Sortieren und Suchen.
Die STL bietet Ihnen fertige Lösungen für viele typische Programmieraufgaben, so daß Sie nicht unbedingt jedes Mal das Rad neu zu erfinden brauchen. Die Bibliothek ist ausgetestet und fehlerbereinigt, bietet eine hohe Leistung und ist kostenlos! Der wichtigste Punkt ist die Wiederverwendbarkeit. Wenn man einmal den Umgang mit einem STL-Container beherrscht, kann man ihn in allen Programmen verwenden, ohne ihn neu erfinden zu müssen.
Ein Container ist ein Objekt, in dem andere Objekte verwahrt werden können. Die
Standard-C++-Bibliothek stellt eine ganze Reihe von Containern zur Verfügung, die
für C++-Programmierer eine wertvolle Hilfe bei der Lösung vieler allgemeiner Programmieraufgaben
sein können. Es gibt zwei Kategorien von Container-Klassen in der
Standard Template Library (STL): sequentielle und assoziative. Sequentielle Container
sind dafür konzipiert, daß man auf ihre Elemente sukzessive oder direkt durch Angabe
einer Position zugreift. Assoziative Container sind für den Zugriff über Schlüssel
optimiert. Wie auch die anderen Bestandteile der Standard-C++-Bibliothek ist die STL
zwischen den verschiedenen Betriebssystemen portierbar. Alle STL-Containerklassen
sind in dem Namensbereich std
definiert.
Die sequentiellen Container der Standard Template Library erlauben den schnellen
sukzessiven oder direkten Zugriff auf eine Liste von Objekten. Die Standard-C++-Bibliothek
kennt drei verschiedene sequentielle Container: vector
, list
und deque
.
Häufig verwendet man Arrays, um eine bestimmte Zahl von Elementen zu speichern und bei Bedarf auf die Elemente zuzugreifen. Alle Elemente in einem Array gehören einem gemeinsamen Typ an. Der Zugriff auf die Elemente erfolgt über einen Index. Die STL stellt uns eine Container-Klasse zur Verfügung, die sich wie ein Array verhält, dabei aber leistungsfähiger und sicherer einzusetzen ist.
Ein vector ist ein Container, der dafür optimiert ist, einzelne Elemente schnell über einen
Index anzusprechen. Die Container-Klasse vector
ist in der Header-Datei <vector>
im Namensbereich std
definiert (siehe Kapitel 17, »Namensbereiche«, für mehr
Informationen zur Programmierung mit Namensbereichen). Ein vector
wächst mit seinem
Inhalt mit. Nehmen wir an, Sie haben einen vector
für zehn Elemente erzeugt.
Nachdem Sie in dem vector
zehn Objekte abgelegt haben, ist dieser voll. Fügen Sie
danach ein weiteres Objekt in den vector
ein, erhöht dieser automatisch seine Aufnahmekapazität,
so daß er das elfte Objekt entgegennehmen kann. Die Definition der
vector
-Klasse sieht wie folgt aus:
template <class T, class A = allocator<T>> class vector
{
// Klassenelemente
};
Das erste Argument (class T
) bezeichnet den Typ der Elemente, die im vector
verwahrt
werden. Das zweite Argument (class A
) ist eine Allokator-Klasse. Allokatoren
sind Speichermanager, die für die Reservierung und Freigabe des Speichers für die
Elemente im Container verantwortlich sind. Wie man mit Allokatoren arbeitet und wie
man sie implementiert, sind fortgeschrittene Themen, die nicht im Rahmen dieses Buches
behandelt werden können.
Per Voreinstellung werden die Elemente mit Hilfe des Operators new()
erzeugt und
von dem Operator delete()
freigegeben. Dies bedeutet, daß zur Erzeugung neuer Elemente
der Standardkonstruktor der Klasse T
aufgerufen wird. Wir hätten damit ein
weiteres Argument, das dafür spricht, in den eigenen Klassen einen Standardkonstruktor
zu definieren. Wenn Sie dies nicht tun, können Sie den vector
-Container
nicht zur Verwahrung von Instanzen Ihrer Klasse nutzen.
Wie man vector
-Container für die Abspeicherung von Integer-Werten und Fließkommazahlen
definiert, zeigen die folgenden Zeilen:
vector<int> vInts; // vector fuer Integer-Elemente
vector<float> vFloats; // vector fuer Fließkommazahlen
Meist hat man eine vage Vorstellung davon, wie viele Elemente ein Container aufnehmen
soll. Nehmen wir an, in Ihrer Schule gibt es maximal 50 Schüler pro Klasse. Um
alle Schüler einer Klasse in einer Datenstruktur zu verwalten, würden Sie einen vector
definieren, der groß genug ist, um 50 Elemente aufzunehmen. Die vector
-Klasse stellt
hierfür einen Konstruktor zur Verfügung, der die Anzahl der Elemente als Parameter
übernimmt, so daß man einen vector
von 50 Schülern wie folgt definieren kann:
vector<Student> MathClass(50);
Ein Compiler wird für diese Definition Speicher für 50 Student-Objekte reservieren;
die einzelnen Elemente werden mit Hilfe des Standardkonstruktors Student::Student()
erzeugt.
Die Anzahl der Elemente im Container kann mit Hilfe der Elementfunktion size()
abgefragt
werden. In unserem Beispiel würde vStudent.size()
den Wert 50 zurückliefern.
Eine andere Elementfunktion, capacity()
, teilt uns mit, wie viele Elemente der Container
noch aufnehmen kann, bevor seine Kapazität ausgedehnt werden muß. Mehr
hierzu später.
Leer ist ein vector
genau dann, wenn er keine Elemente enthält, das heißt, wenn seine
Größe (size()
) gleich Null ist. Die vector
-Klasse stellt eine eigene Elementfunktion namens
empty()
zur Verfügung, mit der man schnell testen kann, ob ein Container leer ist
oder nicht. Ist der Container leer, liefert die Elementfunktion den Wert true
zurück.
Um ein Student
-Objekt Harry
in den MathClass
-Container aufzunehmen, verwenden
wir den Indexoperator []
:
MathClass[5] = Harry;
Die Indexierung beginnt mit dem Index 0. Die obige Zeile weist Harry
dem sechsten
Element im Container zu, wobei die Zuweisung - wie Ihnen vielleicht aufgefallen ist -
durch den Zuweisungsoperator der Student
-Klasse erfolgt. In gleicher Weise kann
man auf das Element im Container zugreifen, um Harrys Alter herauszufinden:
MathClass[5].GetAge();
Wie ich schon erwähnt habe, wird der Speicherraum von vector
-Containern automatisch
angepaßt, wenn Sie mehr Elemente in einen Container einfügen, als dieser aufnehmen
kann. Nehmen wir an, ein Kurs an Ihrer Schule wäre so populär geworden,
daß die Anzahl der eingeschriebenen Schüler 50 übersteigt. Nun, für unsere Mathematikklasse
ist dies wohl eher unwahrscheinlich, doch wer weiß, manchmal geschehen
merkwürdige Dinge. Wenn der einundfünfzigste Schüler, Sally
, in MathClass
eingetragen
wird, erweitert der Compiler den Container, so daß Sally aufgenommen
werden kann.
Es gibt verschiedene Wege, um Elemente in einen vector
aufzunehmen; einer führt
über die Elementfunktion push_back()
:
MathClass.push_back(Sally);
Diese Elementfunktion hängt das Student
-Objekt Sally
an das Ende des Vektors MathClass
an. Jetzt haben wir 51 Elemente in MathClass,
und Sally
befindet sich an der
Position MathClass[50]
.
Damit die Elementfunktion push_back()
verwendet werden kann, muß unsere Student
-Klasse einen Kopierkonstruktor definieren. Ansonsten kann die Funktion keine
Kopie des Objekts Sally
anlegen.
Die STL gibt nicht an, wie viele Elemente maximal in einem vector
abgelegt werden
können. Den Compiler-Hersteller fällt es leichter, diesen Wert festzulegen. Die vector
-Klasse definiert zu diesem Zweck eine eigene Elementfunktion, die Ihnen angibt,
wie groß dieser magische Wert für Ihren Compiler ist: max_size()
.
Listing 19.8 zeigt Ihnen, wie man die Elemente der Klasse vector
, die wir bis hierher
besprochen haben, eingesetzt werden. Um das Programm nicht unnötig durch aufwendige
Stringmanipulationen komplizieren zu müssen, habe ich dabei auf die Klasse
string
zurückgegriffen. Wenn Sie sich näher über die Klasse string
informieren wollen,
schauen Sie im Handbuch Ihres Compilers nach.
Listing 19.8: Einrichtung eines vector-Containers und Zugriff auf die Elemente
1: #include <iostream>
2: #include <string>
3: #include <vector>
4: using namespace std;
5:
6: class Student
7: {
8: public:
9: Student();
10: Student(const string& name, const int age);
11: Student(const Student& rhs);
12: ~Student();
13:
14: void SetName(const string& name);
15: string GetName() const;
16: void SetAge(const int age);
17: int GetAge() const;
18:
19: Student& operator=(const Student& rhs);
20:
21: private:
22: string itsName;
23: int itsAge;
24: };
25:
26: Student::Student()
27: : itsName("Neuer Schueler"), itsAge(16)
28: {}
29:
30: Student::Student(const string& name, const int age)
31: : itsName(name), itsAge(age)
32: {}
33:
34: Student::Student(const Student& rhs)
35: : itsName(rhs.GetName()), itsAge(rhs.GetAge())
36: {}
37:
38: Student::~Student()
39: {}
40:
41: void Student::SetName(const string& name)
42: {
43: itsName = name;
44: }
45:
46: string Student::GetName() const
47: {
48: return itsName;
49: }
50:
51: void Student::SetAge(const int age)
52: {
53: itsAge = age;
54: }
55:
56: int Student::GetAge() const
57: {
58: return itsAge;
59: }
60:
61: Student& Student::operator=(const Student& rhs)
62: {
63: itsName = rhs.GetName();
64: itsAge = rhs.GetAge();
65: return *this;
66: }
67:
68: ostream& operator<<(ostream& os, const Student& rhs)
69: {
70: os << rhs.GetName() << " ist " << rhs.GetAge() << " Jahre alt";
71: return os;
72: }
73:
74: template<class T>
75: void ShowVector(const vector<T>& v); //vector-Eigenschaften anzeigen
76:
77: typedef vector<Student> SchoolClass;
78:
79: int main()
80: {
81: Student Harry;
82: Student Sally("Sally", 15);
83: Student Bill("Bill", 17);
84: Student Peter("Peter", 16);
85:
86: SchoolClass EmptyClass;
87: cout << "Leere Klasse:\n";
88: ShowVector(EmptyClass);
89:
90: SchoolClass GrowingClass(3);
91: cout << "WachsendeKlasse(3):\n";
92: ShowVector(GrowingClass);
93:
94: GrowingClass[0] = Harry;
95: GrowingClass[1] = Sally;
96: GrowingClass[2] = Bill;
97: cout << "WachsendeKlasse(3) nach Zuweisung von Schuelern:\n";
98: ShowVector(GrowingClass);
99:
100: GrowingClass.push_back(Peter);
101: cout <<"WachsendeKlasse() nach Zuweisung des 4.Schuelers:\n";
102: ShowVector(GrowingClass);
103:
104: GrowingClass[0].SetName("Harry");
105: GrowingClass[0].SetAge(18);
106: cout << "WachsendeKlasse() nach Eintragung des Namens\n:";
107: ShowVector(GrowingClass);
108:
109: return 0;
110: }
111:
112: //
113: // vector-Eigenschaften anzeigen
114: //
115: template<class T>
116: void ShowVector(const vector<T>& v)
117: {
118: cout << "max_size() = " << v.max_size();
119: cout << "\tsize() = " << v.size();
120: cout << "\tcapacity() = " << v.capacity();
121: cout << "\t" << (v.empty()? "leer": "nicht leer");
122: cout << "\n";
123:
124: for (int i = 0; i < v.size(); ++i)
125: cout << v[i] << "\n";
126:
127: cout << endl;
128: }
129:
Leere Klasse:
max_size() = 214748364 size() = 0 capacity() = 0 leer
WachsendeKlasse(3):
max_size() = 214748364 size() = 3 capacity() = 3 nicht leer
Neuer Student ist 16 Jahre alt
Neuer Student ist 16 Jahre alt
Neuer Student ist 16 Jahre alt
WachsendeKlasse(3) nach Zuweisung von Schuelern:
max_size() = 214748364 size() = 3 capacity() = 3 nicht leer
Neuer Student ist 16 Jahre alt
Sally ist 15 Jahre alt
Bill ist 17 Jahre alt
WachsendeKlasse() nach Zuweisung des 4.Schuelers:
max_size() = 214748364 size() = 4 capacity() = 6 nicht leer
Neuer Student ist 16 Jahre alt
Sally ist 15 Jahre alt
Bill ist 17 Jahre alt
Peter ist 16 Jahre alt
WachsendeKlasse() nach Eintragung des Namens:
max_size() = 214748364 size() = 4 capacity() = 6 nicht leer
Harry ist 18 Jahre alt
Sally ist 15 Jahre alt
Bill ist 17 Jahre alt
Peter ist 16 Jahre alt
Unsere Student
-Klasse ist in den Zeilen 6 bis 24 definiert, die Implementierung der zugehörigen
Elementfunktionen steht in den Zeilen 26 is 66. Die Klasse ist einfach gestrickt
und an die Verwendung in Zusammenhang mit vector
-Containern angepaßt.
Aus den weiter oben besprochenen Gründen haben wir einen Standardkonstruktor,
einen Kopierkonstruktor und einen überladenen Zuweisungsoperator definiert. Beachten
Sie auch, daß die Elementvariable itsName
als eine Instanz der C++-Klasse string
definiert ist. Wie man dem Listing entnehmen kann, ist die Programmierung mit C++-
Strings wesentlich einfacher als mit C-Strings vom Typ char*
.
Die Template-Funktion ShowVector()
ist in den Zeilen 74 und 75 deklariert und in den
Zeilen 115 bis 128 definiert. Sie demonstriert den Einsatz eine Reihe von Elementfunktionen
des vector
-Containers: max_size(), size(), capacity()
und empty()
. Wie
Sie der Ausgabe des Programms entnehmen können, beträgt die maximale Anzahl an
Student
-Objekten, die ein vector
aufnehmen kann, für den Visual C++-Compiler
214.748.364. Für andere Elementtypen können sich andere Werte ergeben. So kann
ein vector
-Container für Integer-Werte beispielsweise 1.073.741.823 Elemente aufnehmen.
Wenn Sie andere Compiler verwenden, werden diese unter Umständen andere
Maximalwerte liefern.
In den Zeilen 124 und 125 gehen wir die einzelnen Element im vector
-Container
durch und geben die Werte mit Hilfe des Ausgabeoperators <<
aus, der in den Zeilen
68 bis 72 überladen ist.
In den Zeilen 81 bis 84 werden vier Student
-Objekte erzeugt. In Zeile 86 wird ein leerer
Vektor mit dem treffenden Namen EmptyClass
erzeugt und vom Standardkonstruktor
der vector
-Klasse eingerichtet. Wird ein vector
-Container auf diese Weise angelegt,
reserviert der Compiler keinen Speicher für den Container. Wie man der
Ausgabe der Funktion ShowVector(EmptyClass)
entnehmen kann, sind Größe und Kapazität
beide gleich Null.
In Zeile 90 wird ein vector
für drei Student
-Objekte definiert. Größe und Kapazität
dieses Containers sind danach, wie erwartet, gleich 3. In den Zeilen 94 bis 96 werden
den Elementen in GrowingClass
mit Hilfe des Indexoperators []
Student
-Objekte zugewiesen.
Der vierte Schüler, Peter
, wird dem vector
-Container in Zeile 100 hinzugefügt. Die
Größe des vector
-Containers beträgt danach 4. Interessanterweise wurde die Kapazität
gleichzeitig auf 6 heraufgesetzt. Dies bedeutet, daß der Compiler für den Container
genügend Speicher reserviert hat, um sechs Student
-Objekte darin abzulegen. Da
der Speicher für vector
-Container als ein zusammengehörender Block reserviert werden
muß, sind mit der Erweiterung des Speichers für einen Container eine ganze Reihe
von Operationen erforderlich. Zuerst muß ein neuer Speicherblock reserviert werden,
der groß genug ist, alle vier Student
-Objekte aufzunehmen. Zweitens müssen die
drei Elemente in den neu reservierten Speicherbereich kopiert und das vierte Elemente
hinter dem dritten Element eingefügt werden. Schließlich muß der ursprüngliche
Speicherblock freigegeben werden. Für eine große Anzahl von Elementen in einem
Container können diese fortwährenden Reservierungs- und Freigabeoperationen sehr
zeitraubend sein. Aus diesem Grund wendet der Compiler eine andere Strategie an,
die den Bedarf an Speicherreservierungen reduziert. Für unser Beispiel bedeutet dies,
daß wir noch ein oder zwei weitere Objekte in den vector
-Container aufnehmen können,
ohne daß dieser neuen Speicher allokieren muß.
In den Zeilen 104 und 105 wird wiederum der Indexoperator []
verwendet, um die
Elementvariablen des ersten Objekts im GrowingClass
-Container zu ändern.
Die vector
-Containerklasse enthält noch weitere Elementfunktionen. Die Funktion
front()
liefert eine Referenz auf das erste Elemente in einer Liste zurück. Die Funktion
back()
liefert eine Referenz auf das letzte Elemente zurück. Die Funktion at()
wird
wie der Indexoperator []
eingesetzt, ist aber sicherer, da sie überprüft, ob der Index
gültig ist, also auf ein Element im Container verweist. Ist der Index außerhalb des gültigen
Bereichs, löst die Funktion eine out_of_range
-Exception aus (Exceptions werden
wir am morgigen Tag besprechen).
Die insert()
-Funktion fügt einen oder mehrere Knoten an einer gegebenen Position
in den vector
ein. Die pop_back()
-Funktion entfernt das letzte Element aus einem
vector
. Schließlich wäre da noch die Funktion remove()
, die eines oder mehrere Element
aus einem vector
entfernt.
Ein list
-Container ist ein Container, der für häufiges Einfügen und Löschen von Elementen
optimiert ist.
Die STL-Containerklasse list
ist in der Header-Datei <list>
im Namensbereich std
definiert. Die list
-Klasse ist als eine doppelt verkettete Liste implementiert, in der jeder
Knoten mit dem vorangehenden und dem nachfolgenden Knoten verknüpft ist.
Die list
-Klasse verfügt über alle Elementfunktionen, die auch von der vector
-Klasse
zur Verfügung gestellt werden. Wie Sie in der Rückschau auf die zweite Woche gesehen
haben, können Sie eine Liste durchgehen, indem Sie den Links der einzelnen
Knoten folgen. Die Links werden dabei üblicherweise mit Hilfe von Zeigern realisiert.
Die STL-Containerklasse list
verwendet zu dem gleichen Zweck das Konzept der Iteratoren.
Ein Iterator ist die Abstraktion eines Zeigers. Iteratoren können wie Zeiger dereferenziert werden, um auf den Knoten zuzugreifen, auf den der Iterator verweist. Listing 19.9 demonstriert, wie man mit Hilfe von Iteratoren auf die Knoten in einer Liste zugreifen kann.
Listing 19.9: Einen list-Container mit Hilfe von Iteratoren durchwandern
1: #include <iostream>
2: #include <list>
3: using namespace std;
4:
5: typedef list<int> IntegerList;
6:
7: int main()
8: {
9: IntegerList intList;
10:
11: for (int i = 1; i <= 10; ++i)
12: intList.push_back(i * 2);
13:
14: for (IntegerList::const_iterator ci = intList.begin();
15: ci != intList.end(); ++ci)
16: cout << *ci << " ";
17:
18: return 0;
19: }
2 4 6 8 10 12 14 16 18 20
In Zeile 9 wird intList
als ein list
-Container für Integer-Werte definiert. Darunter
werden in den Zeilen 11 und 12 die ersten zehn geraden Zahlen mit Hilfe der Funktion
push_back()
in die Liste eingetragen.
In den Zeilen 14 bis 16 greifen wir mit Hilfe eines const-Iterators auf die einzelnen Knoten in der Liste zu. Den const-Iterator verwenden wir, weil wir nicht beabsichtigen, die Knoten beim Zugriff über den Iterator zu verändern. Wollten wir den Knoten, auf den unser Iterator verweist, ändern, müßten wir einen nicht-const-Iterator verwenden:
intList::iterator
Die Elementfunktion begin()
liefert einen Iterator zurück, der auf den ersten Knoten
in der Liste verweist. Wie dem Listing zu entnehmen ist, kann man den ++-Operator
verwenden, um einen Iterator auf den nächsten Knoten zu richten. Die Elementfunktion
end()
ist ein wenig merkwürdig - sie liefert einen Iterator, der hinter den letzten
Knoten in der Liste verweist. Wir müssen daher darauf achten, unseren Iterator nicht
bis end()
laufen zu lassen.
Um den Knoten zurückliefern zu lassen, auf den der Iterator verweist, dereferenziert man den Iterator wie einen normaler Zeiger, zu sehen in Zeile 16.
Wir haben die Iteratoren zwar erst hier in Zusammenhang mit dem list
-Container
vorgestellt, doch werden Iteratoren auch von der vector
-Klasse zur Verfügung gestellt.
Zusätzlich zu den Funktionen, die die list
-Klasse mit der vector
-Klasse teilt, verfügt
list
noch über zwei weitere Funktionen: push_front()
und pop_front()
. Beide arbeiten
ganz wie die Funktionen push_back()
und pop_back()
, nur daß sie Elemente nicht
am Ende, sondern am Anfang der Liste einfügen oder löschen.
Ein deque
-Container ist ein doppelköpfiger vector
-Container. Er erbt von der vector
-
Containerklasse die effizienten, sequentiellen Schreib- und Leseoperationen, stellt
aber darüber hinaus optimierte Operationen für die beiden Enden des Containers zur
Verfügung. Implementiert sind diese Operationen ähnlich wie für list
-Container, wo
Speicherreservierungen nur für neue Elemente erforderlich werden. Dieser Eigenschaft
der deque
-Klasse ist es zu verdanken, daß deque
-Container nicht wie vector
-
Container reallokiert und an neue Speicherbereiche kopiert zu werden brauchen. Insgesamt
gesehen sind deque
-Container damit bestens geeignet für Anwendungen, in
denen Einfüge- und Löschoperationen vornehmlich an den beiden Enden des Containers
stattfinden und für die das sequentielle Durchgehen der Elemente wichtig ist. Ein
Beispiel für eine solche Anwendung wäre etwa ein Simulationsprogramm für die Zusammenstellung
von Zügen, bei dem die Waggons an beide Enden der Züge angehängt
werden können.
Eine der bei der Programmierung mit am häufigsten benötigten Datenstrukturen ist
der Stack (zu deutsch: Stapel oder Keller). Allerdings ist der Stack in der STL nicht als
eigene Container-Klasse implementiert, sondern vielmehr als eine Hüllklasse um einen
anderen Container. Die Template-Klasse stack
ist in der Header-Datei <stack>
im Namensbereich std
definiert.
Ein Stack oder Keller ist ein zusammenhängender Speicherblock, der am rückwärtigen
Ende wachsen oder schrumpfen kann. Nur das jeweils letzte Elemente im Stack
kann gelesen oder gelöscht werden. Ähnliche Charakteristika kennen Sie bereits von
den sequentiellen Container, speziell von vector
und deque
. Tatsächlich kann jeder sequentielle
Container, der die Operationen back()
, push_back()
und pop_back()
unterstützt,
als zugrundeliegender Container zur Implementierung eines Stack verwendet
werden. Der größte Teil der restlichen Container-Methoden wird für die Realisierung
eines Stack nicht benötigt und wird daher von der Stack-Klasse nicht zur Verfügung
gestellt.
Die STL-Template-Klasse stack
ist dafür konzipiert, Objekte jeden beliebigen Typs
aufzunehmen. Die einzige Bedingung ist, daß alle Objekte vom gleichen Typ sind.
Ein Stack ist eine LIFO-Struktur (LIFO steht für »last in, first out«). Eine solche Struktur ist wie ein überfüllter Aufzug: Die erste Person, die den Aufzug betritt, wird gegen die Wand gedrückt, während die letzte Person direkt an der Tür steht. Wenn der Aufzug das gewünschte Stockwerk erreicht, verläßt die letzte Person den Aufzug zuerst. Möchte jemand den Aufzug schon ein Stockwerk früher verlassen, müssen alle anderen zwischen der Person und der Tür Platz machen - das heißt, den Aufzug kurz verlassen, um ihn danach gleich wieder zu betreten.
Das offene Ende des Stack wird per Konvention als »top« und die Operationen auf
dem Stack-Ende als »push« und »pop« bezeichnet. Die stack
-Klasse übernimmt diese
Namenskonventionen.
Die STL-Klasse
stack
ist nicht identisch mit der Datenstruktur, die Compiler und Betriebssystem verwenden und in der Elemente verschiedenen Typs abgelegt werden können. Die zugrundeliegende Funktionsweise ist allerdings die gleiche.
Die Queue oder Warteschlange ist ebenfalls eine in der Programmierung sehr gebräuchliche Datenstruktur. Die Elemente werden am einen Ende der Queue eingefügt und am anderen Ende herausgenommen.
Es gibt eine fast schon klassische Analogie zur Erklärung der Datenstrukturen Stack und Queue: Ein Stack ist wie ein Stapel von Tellern an einer Salatbar. Sie erweitern den Stack, indem Sie weitere Teller auf den Stapel legen (wobei der Stack niedergedrückt wird, auf englisch: push). Sie verkleinern den Stack, indem Sie den zuletzt auf den Stapel abgelegten Teller herunternehmen (auf englisch: pop).
Eine Queue ist dagegen wie eine Warteschlange im Theater. Sie treten am hinteren Ende in die Schlange ein und verlassen Sie, wenn Sie ganz vorne angelangt sind. Man bezeichnet dies auch als FIFO-Struktur (FIFO steht für first in, first out), im Gegensatz zum Stack, der eine LIFO-Struktur (last in, first out) darstellt. Manchmal geschieht es natürlich auch, daß Sie der Vorletzte in einer langen Schlange an einer Supermarktkasse sind, wenn plötzlich eine Verkäuferin kommt, eine neue Kasse aufmacht und den letzten in der Schlange zu sich winkt. In diesem Fall verwandelt die Verkäuferin die FIFO-Queue in einen LIFO-Stack und läßt Sie frustriert und mit knirschenden Zähnen zurück.
Ebenso wie stack
ist auch queue
als Hüllklasse für Container implementiert. Die zugrundeliegenden
Container müssen folgende Operationen unterstützen: front(),
back(), push_back()
und pop_front()
.
Während die sequentiellen Container für den sequentiellen und direkten Zugriff über
Indizes oder Iteratoren konzipiert sind, ermöglichen die assoziativen Container den
schnellen direkten Zugriff über Schlüssel. Die Standard-C++-Bibliothek kennt vier verschiedene
assoziative Container: map
, multimap
, set
und multiset
.
Wie Sie gesehen haben, ist ein vector
eine fortgeschrittene Variante eines Array. Er
verfügt über alle Charakteristika eines Array und noch über einige andere nützliche
Merkmale. Unglücklicherweise krankt der vector
-Container aber an einer bedeutenden
Schwäche, die allen Arrays gemeinsam ist: Es gibt keine Möglichkeit, andere
Schlüsselwerte außer Indizes oder Iteratoren für den direkten Zugriff auf die Elemente
einzusetzen. Genau dies ermöglichen aber die assoziativen Container.
Die Standard-C++-Bibliothek kennt vier verschiedene assoziative Container: map
, multimap
, set
und multiset
. In Listing 19.10 sehen Sie noch einmal das Schulklassenbeispiel
aus Listing 19.8, diesmal mit Hilfe eines map
-Containers realisiert.
Listing 19.10: Ein map-Container
1: #include <iostream>
2: #include <string>
3: #include <map>
4: using namespace std;
5:
6: class Student
7: {
8: public:
9: Student();
10: Student(const string& name, const int age);
11: Student(const Student& rhs);
12: ~Student();
13:
14: void SetName(const string& name);
15: string GetName() const;
16: void SetAge(const int age);
17: int GetAge() const;
18:
19: Student& operator=(const Student& rhs);
20:
21: private:
22: string itsName;
23: int itsAge;
24: };
25:
26: Student::Student()
27: : itsName("Neuer Student"), itsAge(16)
28: {}
29:
30: Student::Student(const string& name, const int age)
31: : itsName(name), itsAge(age)
32: {}
33:
34: Student::Student(const Student& rhs)
35: : itsName(rhs.GetName()), itsAge(rhs.GetAge())
36: {}
37:
38: Student::~Student()
39: {}
40:
41: void Student::SetName(const string& name)
42: {
43: itsName = name;
44: }
45:
46: string Student::GetName() const
47: {
48: return itsName;
49: }
50:
51: void Student::SetAge(const int age)
52: {
53: itsAge = age;
54: }
55:
56: int Student::GetAge() const
57: {
58: return itsAge;
59: }
60:
61: Student& Student::operator=(const Student& rhs)
62: {
63: itsName = rhs.GetName();
64: itsAge = rhs.GetAge();
65: return *this;
66: }
67:
68: ostream& operator<<(ostream& os, const Student& rhs)
69: {
70: os << rhs.GetName() << " ist " << rhs.GetAge()
<< " Jahre alt";
71: return os;
72: }
73:
74: template<class T, class A>
75: void ShowMap(const map<T, A>& v); // map-Eigenschaften anzeigen
76:
77: typedef map<string, Student> SchoolClass;
78:
79: int main()
80: {
81: Student Harry("Harry", 18);
82: Student Sally("Sally", 15);
83: Student Bill("Bill", 17);
84: Student Peter("Peter", 16);
85:
86: SchoolClass MathClass;
87: MathClass[Harry.GetName()] = Harry;
88: MathClass[Sally.GetName()] = Sally;
89: MathClass[Bill.GetName()] = Bill;
90: MathClass[Peter.GetName()] = Peter;
91:
92: cout << "Mathe-Klasse:\n";
93: ShowMap(MathClass);
94:
95: cout << "Wir wissen:" << MathClass["Bill"].GetName()
96: << " ist " << MathClass["Bill"].GetAge()
<< "Jahre alt\n";
97:
98: return 0;
99: }
100:
101: //
102: // map-Eigenschaften anzeigen
103: //
104: template<class T, class A>
105: void ShowMap(const map<T, A>& v)
106: {
107: for (map<T, A>::const_iterator ci = v.begin();
108: ci != v.end(); ++ci)
109: cout << ci->first << ": " << ci->second << "\n";
110:
111: cout << endl;
112: }
Mathe-Klasse:
Bill: Bill ist 17 Jahre alt
Harry: Harry ist 18 Jahre alt
Peter: Peter ist 16 Jahre alt
Sally: Sally ist 15 Jahre alt
Wir wissen: Bill ist 17 Jahre alt
In Zeile 3 nehmen wir die Header-Datei <map>
auf, da wir ja die Container-Klasse map
verwenden wollen. Konsequenterweise definieren wir zu dem Container die Templatefunktion
ShowMap()
, um die Elemente in einem map
-Container ausgeben zu können. In
Zeile 77 wird SchoolClass
als ein map
-Container definiert, dessen Elemente aus
(Schlüssel, Wert)-Paaren bestehen. Der erste Teil jedes Paares ist der Schlüssel. In unserer
SchoolClass
verwenden wir die Namen der Schüler als Schlüssel, der Typ der
Schlüssel ist daher string
. Die Schlüssel in einem map
-Container müssen eindeutig
sein, das heißt, keine zwei Elemente in dem Container dürfen den gleichen Schlüssel
haben. Der zweite Teil des Paares ist das eigentliche Objekt, in unserem Beispiel also
ein Student
-Objekt. Für die Paare gibt es in der STL einen eigenen Datentyp pair
, der
als Struktur mit zwei Elementen definiert ist: first
und second
. Wir können diese
Strukturelemente nutzen, um auf den Schlüssel und den Wert eines Knotens zuzugreifen.
Überspringen wir die main()
-Funktion und schauen wir uns zuerst die Funktion
ShowMap()
an. Sie verwendet einen const-Iterator, um auf die map
-Objekte zuzugreifen.
In Zeile 109 weist ci->first
auf den Schlüssel (den Namen des Schülers) und ci->second
auf das Student
-Objekt.
Weiter oben in den Zeilen 81 bis 84 werden vier Student
-Objekte erzeugt. In Zeile 86
wird MathClass
als eine Instanz von SchoolClass
definiert. In den Zeilen 87 bis 90
nehmen wir unter Verwendung der folgenden Syntax
map_object[key_value] = object_value;
vier Studenten in die Mathe-Klasse auf.
Alternativ könnte man auch die Funktionen push_back()
oder insert()
verwenden,
um (Schlüssel, Wert)-Paare in den map
-Container einzufügen; mehr Informationen
über die Verwendung dieser Funktionen finden Sie in der Dokumentation Ihres Compilers.
Nachdem alle Student
-Objekte in den map
-Container eingefügt wurden, können wir
auf die Elemente über ihre Schlüssel zugreifen. In den Zeilen 95 und 96 verwenden
wir die Syntax MathClass["Bill"]
, um auf Bills Daten zuzugreifen.
Die Container-Klasse multimap
ist eine map
-Klasse, die nicht auf die Verwendung eindeutiger
Schlüssel beschränkt ist. In einem multimap
-Container können also mehrere
Elemente den gleichen Schlüssel haben.
Die Container-Klasse set
gleicht der map
-Klasse. Der einzige Unterschied ist, daß die
Elemente in einem set
-Container keine (Schlüssel, Wert)-Paare sind, sondern nur aus
dem Schlüssel bestehen.
Schließlich gibt es noch die Container-Klasse multiset
, die nicht-eindeutige Schlüssel
erlaubt.
Container stellen einen praktischen Aufbewahrungsort für eine Folge von Elementen dar. Alle Standard-Container verfügen darüber hinaus über Operationen, mit denen der Container und seine Elemente bearbeitet werden können. All diese Operationen für eigene Container zu implementieren, wäre allerdings ein recht mühsames und fehleranfälliges Unterfangen. Andererseits sind es zum großen Teil immer die gleichen Operationen, die auf die Elemente angewendet werden, so daß ein Satz von allgemeinen Algorithmen Ihnen die Mühe sparen kann, für jeden neuen Container eigene Operationen zu implementieren. In der Standardbibliothek sind ungefähr 60 Standardalgorithmen vorgesehen, die alle wichtigen Operationen auf Containern abdecken.
Die Standardalgorithmen sind in der Header-Datei <algorithm>
im Namensbereich
std
definiert.
Um zu verstehen, wie die Standardalgorithmen arbeiten, muß man sich zuerst mit dem Konzept der Funktionsobjekte auseinandersetzen. Ein Funktionsobjekt ist eine Instanz einer Klasse, die den ()-Operator überlädt und daher wie eine Funktion aufgerufen werden kann. Listing 19.11 demonstriert den Einsatz eines Funktionsobjekts.
Listing 19.11: Ein Funktionsobjekt
1: #include <iostream>
2: using namespace std;
3:
4: template<class T>
5: class Print {
6: public:
7: void operator()(const T& t)
8: {
9: cout << t << " ";
10: }
11: };
12:
13: int main()
14: {
15: Print<int> DoPrint;
16: for (int i = 0; i < 5; ++i)
17: DoPrint(i);
18: return 0;
19: }
0 1 2 3 4
In den Zeilen 4 bis 11 ist die Klasse Print
definiert. Der überladene ()
-Operator aus
den Zeilen 7 bis 11 übernimmt ein Objekt und schreibt es in die Standardausgabe. In
Zeile 15 ist DoPrint
als Instanz der Klasse Print
definiert. Danach kann DoPrint
, wie
eine Funktion, zum Ausgeben von Integer-Werten verwendet werden, siehe Zeile 17.
Nicht verändernde, sequentielle Algorithmen führen Operationen aus, die die Elemente,
auf denen sie operieren, nicht verändern. Hierzu gehören Operationen wie
for_each(), find(), search(), count()
und so weiter. In Listing 19.12 sehen Sie,
wie man mit Hilfe eines Funktionsobjekts und dem for_each
-Algorithmus die Elemente
eines vector
-Containers ausgeben kann.
Listing 19.12: Einsatz des for_each()-Algorithmus
1: #include <iostream>
2: #include <vector>
3: #include <algorithm>
4: using namespace std;
5:
6: template<class T>
7: class Print
8: {
9: public:
10: void operator()(const T& t)
11: {
12: cout << t << " ";
13: }
14: };
15:
16: int main()
17: {
18: Print<int> DoPrint;
19: vector<int> vInt(5);
20:
21: for (int i = 0; i < 5; ++i)
22: vInt[i] = i * 3;
23:
24: cout << "for_each()\n";
25: for_each(vInt.begin(), vInt.end(), DoPrint);
26: cout << "\n";
27:
28: return 0;
29: }
for_each()
0 3 6 9 12
Da alle C++-Standardalgorithmen in <algorithm>
definiert sind, dürfen wir nicht vergessen,
diese Header-Datei einzubinden. Ansonsten birgt das Programm keinerlei besondere
Schwierigkeiten. In Zeile 25 wird die Funktion for_each()
aufgerufen, um die
Elemente im vector
-Container vInt
durchzugehen. Für jedes Element ruft die Funktion
das Funktionsobjekt DoPrint
auf und übergibt das Element an DoPrint.operator()
- mit dem Ergebnis, daß das Element auf dem Bildschirm ausgegeben wird.
Verändernde, sequentielle Algorithmen führen Operationen aus, die die Elemente, auf
denen sie operieren, verändern. Hierzu gehören Operationen zum Füllen oder Sortieren.
Listing 19.13 demonstriert den Einsatz des fill()
-Algorithmus.
Listing 19.13: Ein verändernder, sequentieller Algorithmus
1: #include <iostream>
2: #include <vector>
3: #include <algorithm>
4: using namespace std;
5:
6: template<class T>
7: class Print
8: {
9: public:
10: void operator()(const T& t)
11: {
12: cout << t << " ";
13: }
14: };
15:
16: int main()
17: {
18: Print<int> DoPrint;
19: vector<int> vInt(10);
20:
21: fill(vInt.begin(), vInt.begin() + 5, 1);
22: fill(vInt.begin() + 5, vInt.end(), 2);
23:
24: for_each(vInt.begin(), vInt.end(), DoPrint);
25: cout << "\n\n";
26:
27: return 0;
28: }
1 1 1 1 1 2 2 2 2 2
Neu an Listing 19.13 sind nur die Zeilen 21 und 22, in denen der fill()
-Algorithmus
aufgerufen wird. Dieser Algorithmus weist den Elementen einen gegebenen Wert zu.
In Zeile 21 wird den ersten fünf Elemente aus vInt
der Wert 1 zugewiesen. Den letzten
fünf Elementen aus vInt
wird der Wert 2 zugewiesen (Zeile 22).
Heute haben Sie gelernt, wie man Templates erzeugt und verwendet. Templates sind in die Sprache C++ integriert. Mit ihrer Hilfe lassen sich parametrisierte Typen erzeugen. Diese Typen ändern ihr Verhalten entsprechend der bei der Erzeugung übergebenen Parameter. Templates erlauben die sichere und effektive Wiederverwendung von einem Code.
Die Definition des Templates bestimmt den parametrisierten Typ. Jede Instanz des Templates ist ein echtes Objekt, das sich wie jedes andere Objekt verwenden läßt - als Parameter an eine Funktion, als Rückgabewert usw.
Template-Klassen können drei Arten von friend
-Funktionen deklarieren: Nicht-Template-Funktionen,
Template-Funktionen und typspezifische Template-Funktionen.
Templates können statische Datenelemente deklarieren, in welchem Fall jede Instanz
des Templates seinen eigenen Satz von statischen Daten erhält.
Möchte man für einen bestimmten Datentyp das Verhalten einer Template-Funktion ändern, kann man die Template-Funktion für den speziellen Datentyp überschreiben. Gleiches funktioniert auch für Elementfunktionen.
Frage:
Warum verwendet man Templates, wenn man auch mit Makros auskommen
könnte?
Antwort:
Templates sind typensicher und integraler Bestandteil der Sprache.
Frage:
Worin liegt der Unterschied zwischen dem parametrisierten Typ einer
Template-Funktion und den Parametern einer normalen Funktion?
Antwort:
Eine normale Funktion (keine Template) übernimmt Parameter, mit denen sie
direkt arbeitet. Bei einer Template-Funktion läßt sich der Typ eines bestimmten
Parameters der Funktion parametrisieren. Das heißt, man kann beispielsweise
ein Array
von Typ
an eine Funktion übergeben und dann den Typ
durch
die Template-Instanz bestimmen lassen.
Frage:
Wann verwendet man Templates und wann Vererbung?
Antwort:
Verwenden Sie Templates, wenn das gesamte - oder nahezu das gesamte -
Verhalten gleich bleibt und sich nur der Typ des Elements, mit dem die Klasse
arbeitet, verändert. Wenn man laufend Klassen kopiert und lediglich den Typ
von Elementen der Klasse ändert, sollte man den Einsatz eines Templates in
Betracht ziehen.
Frage:
Wann verwendet man Templateklassen als Friends?
Antwort:
Wenn jede Instanz, unabhängig vom Typ, ein Freund der Klasse oder Funktion
sein soll.
Frage:
Wann verwendet man typspezifische Template-Klassen oder -Funktionen
als Friends?
Antwort:
Wenn man eine 1:1-Beziehung zwischen zwei Klassen herstellen möchte. Beispielsweise,
wenn array<int>
mit iterator<int>,
aber nicht mit iterator<Animal>
zusammenarbeiten soll.
Frage:
Welche zwei Kategorien von Standard-Containern gibt es?
Antwort:
Sequentielle und assoziative Container. Sequentielle Container bieten den optimierten
sukzessiven und direkten Zugriff auf ihre Elemente. Assoziative
Container bieten optimalen Zugriff auf die Elemente über Schlüssel.
Frage:
Welche Attribute muß eine Klasse haben, um zusammen mit einem
Standard-Container verwendet werden zu können?
Antwort:
Die Klasse muß einen Standardkonstruktor, einen Kopierkonstruktor und einen
überladenen Zuweisungsoperator definieren.
Der Workshop enthält Quizfragen, die Ihnen helfen sollen, Ihr Wissen zu festigen, und Übungen, die Sie anregen sollen, das eben Gelernte umzusetzen und eigene Erfahrungen zu sammeln. Versuchen Sie, das Quiz und die Übungen zu beantworten und zu verstehen, bevor Sie die Lösungen in Anhang D lesen und zur Lektion des nächsten Tages übergehen.
List
-Klasse basiert:
class List
{
private:
public:
List():head(0),tail(0),theCount(0) {}
virtual ~List();
void insert( int value );
void append( int value );
int is_present( int value ) const;
int is_empty() const { return head == 0; }
int count() const { return theCount; }
private:
class ListCell
{
public:
ListCell(int value, ListCell *cell = 0)
:val(value),next(cell){}
int val;
ListCell *next;
};
ListCell *head;
ListCell *tail;
int theCount;
};
List
auf.
List
-Objekte: eine Liste von Strings, eine Liste von Cats
und eine Liste von Integern.
List
-Template definiert ist und mit Cat
die Klasse aus den vorhergehenden Kapiteln des Buches gemeint ist.)
List<Cat> Cat_List;
Cat Felix;
CatList.append( Felix );
cout << "Felix ist " <<
( Cat_List.is_present( Felix ) ) ? "" : "nicht " << "da\n";
friend
-Operator ==
für List
.
friend
-Operator ==
für List
.
==
die gleichen Probleme wie in Übung 5?
swap()
, die zwei Variablen austauscht.
SchoolClass
aus Listing 19.8 als list
-Container. Verwenden Sie die push_back()
-Funktion, um vier Studenten in den list
-Container aufzunehmen. Gehen Sie dann den Container durch, und setzen Sie das Alter der Schüler um jeweils ein Jahr herauf.
© Markt&Technik Verlag, ein Imprint der Pearson Education Deutschland GmbH