- Wieso Speicherverwaltung?
- Wiederholung: Was sind Stack und Heap?
- Dynamische Arrays
- Ausblick
1. Wieso Speicherverwaltung?
Das ist eine häufig gestellte Frage in C++-Kreisen, besonders von denen, die von einer "bequemen" Sprache wie PHP umsteigen. In PHP kann man z.B. in einem Array beliebig viele Elemente hinzufügen, die Größe spielt keine Rolle und ist selbst dynamisch:
PHP-Code:
<?php
$array = array(); // initialisiere ein Array
for($i = 0; $i < 29; $i++) { // beliebig viel mit Elementen füllen
$array[$i] = $i * $i;
}
?>
Wir möchten in einem Array Integer-Werte speichern. Dabei soll der Nutzer des Programmes zunächst die Größe eingeben und dann soll das Array in einer Schleife gefüllt werden.
Problem erkannt? Nein? Dann ist da wohl jemandem das C++-Konzept von Arrays aus der Erinnerung geraten... 
2. Wiederholung: Was sind Stack und Heap?
Für gewöhnlich wurden Arrays immer auf dem normalen Arbeitsspeicher angelegt, ein Array ist prinzipiell nichts anderes als ein Wrapper um benachbarte Variablen. Benachbart bedeutet, dass in C++ jede Variable eine Adresse auf dem Arbeitsspeicher hat, jede Adresse beschreibt ein Segment des RAMs, in dem die Information der Variable gespeichert ist, wie bei uns Integer-Werte. Mithilfe des Operators '&' kann man die Adresse einer C++-Variable ermitteln:
Code cpp:
1 2 | int a = 10;
std::cout << "Inhalt von a: " << a << " Adresse von a: " << &a << endl; |
Arrays sind im Grunde einfach nur mehrere Variablen, deren die Adressen der Speichersegmente direkt nebeneinander liegen, d.h. z.B., dass auf einem 32-Bit-System eine Integer-Variable 4 Bytes groß ist. Ein Int-Array sähe im Hauptspeicher also so aus:
Code :
1 2 3 4 5 6 7 8 9 | STACK (Stapel):
+------------------------------+
| 0x000004 -----> 4 = array[0] |
| 0x000008 -----> 8 = array[1] |
| 0x000012 -----> 2 = array[2] |
| 0x000016 -----> 6 = array[3] |
| ... |
| 0xnnnnnn -----> n = array[n] |
+------------------------------+ |
Ein Array legt mat in C++ bekanntlich so an:
Code cpp:
1 | int array[10]; |
Dabei wird nun für 10 Integervariablen auf dem Arbeitsspeicher Platz angefordert. Die Zahl 10 ist für den Compiler ein Numeral, d.h. 10 ist in C++ eine Konstante Größe. Alternativ könnte man auch schreiben:
Code cpp:
1 2 | const unsigned groesse = 10; // const ist wichtig!
int array[groesse]; |
Das const vor dem Integer-Wert groesse ist verbindlich, man kann groesse nach der Definition nicht mehr verändern. Das Array braucht eine konstante Größe, da die Größe des Arrays, 10 Integers, zur Kompilierzeit festgelegt werden muss. Das heißt, wenn wir das Programm kompilieren, wird der Compiler sich 10 Adressen für Int heraussuchen. Diese sind dann für das Programm für immer die selben. Die Größe und Adresse des Arrays wird somit zur Kompilierzeit festgelegt, der Arbeitsspeicher für diese Information nennt sich "Stack", Stapel (der Adressen) zu deutsch, er wird auch als "statischer Speicher" bezeichnet. Wenn man das const weglässt, wird dies einen Fehler geben. Wenn man im Array den Index 11 verwendet, dann gibt es einen Stack-Overflow, also undefiniertes Verhalten, denn da wird auf eine Adresse zugegriffen, die nicht mehr zum Array gehört. Kurz und knapp: Es gibt keine Möglichkeit mehr, die Größe dieses Arrays zu verändern.
Das trifft sich aber schlecht, unser Array sollte doch so groß sein, wie der Benutzer es eingibt.
Die Eingabe erfolgt aber leider nicht zur Kompilier-Zeit, sondern in der Laufzeit (= Runtime).Daher funktioniert folgender Code nicht:
Code cpp:
1 2 3 4 5 6 7 8 9 | int eingabe;
std::cin >> eingabe;
int array[eingabe]; // Zack!
// genauso geht nicht
const int eingabe;
cin >> eingabe; // Zack!
int array[eingabe]; |
Was tun? Wir brauchen etwas neues, ja, das ist es, wir verweden den "dynamischen Speicher", oder auch "Heap", wie er oft genannt wird. Der Heap alloziiert den Speicher erst, wenn er zur Laufzeit irgendwo gebraucht wird. Der Unterschied zum Stack ist, dass die Adressen der Variablen fest im Binärcode der Executable steht und somit zur Kompilierzeit bekannt ist. Heap-Speicher ist ebenfalls RAM (oder auch unter Win die Auslagerungsdatei bzw. unter Linux die Swap-Partition), aber dieser Speicherplatz ist erst bestimmt, wenn das Programm läuft, somit variieren auch die Adressen. Nachteil: er ist etwas langsamer und Fehler bzgl. des Heaps bringen Runtime-Errors. Man alloziierte den Speicher in C standartmäßig mit der Funktion malloc(), in C++ gibt es dafür new [Datentyp]:
Code cpp:
1 2 3 4 5 6 7 8 9 10 11 | #include <iostream>
int main() {
int *s; // Zeiger deklarieren
s = new int; // new liefert die Adresse eines Segmentes für 1 Int
*s = 5; // derefferenzieren und 5 zuweisen
std::cin >> *s; // Eingabe im derefferenzierten s speichern
std::cout << s << ' ' << *s;
delete s; // Speicher freigeben
std::cin.get();
} |
new gibt immer eine Adresse des neuen Speichers zurück, ähnlich wie malloc(), nur, dass man nicht mehr casten muss. Adressen speichert man dann natürlich in Zeigern ab, man kann die Adresse eines integers, was auf dem Stack liegt, nicht ändern. Wir haben jetzt nur noch die Adresse des int-Wertes, den tatsächlichen Zugriff zum Wert erhalten wir nur noch durch Derefferenzieren.
Beim mehrmaligen Ausführen kann es vorkommen, dass sich die Adresse ändert, das entscheidet aber das Betriebssystem. Am Ende muss man sich selber um die Freigabe des Speichers kümmern, das geht unter C mit free(), in C++ mit delete [Adresse]. Fällt das aus, gibt es Speicherlecks, d.h., der Arbeitsspeicher ist, solange der Computer gerade an ist, verloren. (Aber die meisten Compiler sind in der Lage, solche kleinen Sachen weg zu optimieren, bei Klassen wird das dann aber schwieriger.)
Eine Regel sollte man nie vergessen, wozu man aber auch oft in C++ durch das einfache new neigen kann: Alloziierung != Initialisierung. Was das bedeuten soll? Ganz einfach: wenn wir dynamischen Speicher anfordern, weist das Betriebssystem ein Stückchen RAM unserem Programm zu. Würden wir vorher darauf zugreifen, gibt's meistens 'nen Segfault mit Programmabsturz. So weit, so klar. Nehmen wir an, wir haben eine Klasse Widget, die hat logischerweise auch einen Konstruktor zum initialisieren irgendwelcher Resourcen, Handles usw. Wenn Speicher angefordert wird, wird nicht der Konstruktor des Objektes aufgerufen, wir haben lediglich den Speicher sicher! Und was gibt es für eine Möglichkeit, Speicher zu alloziieren, ohne ihn zu initialisieren? malloc.
Code cpp:
1 | Widget *w = static_cast<Widget*>(malloc(sizeof(Widget))); // Alloziiere Speicher in Größe von Widget und caste in Widget-Pointer |
Was jetzt? Sollten wir etwa sowas machen wie "w->Widget()", den Konstruktor also explizit aufrufen? Schlechte Idee, dafür hat C++ eine Lösung namens "Placement new", also Plazierungs-new, womit wir ein Objekt in einem bestimmten Speicher gezielt platzieren und initialisieren können. Der nachfolgende Code sähe so aus:
Code cpp:
1 2 | Widget *ptr = new(w) Widget;
ptr->DoSomeStuff(); |
Natürlich muss das Objekt dann auch wieder (bestenfalls von einem Placement-delete) freigegeben werden.
So, jetzt ist das auf jeden Fall wieder aufgefrischt, kommen wir nun zum eigentlichen Thema!
3. Dynamische Arrays
So, die oben genannte Aufgabenstellung ist noch fällig. Mithilfe des Heaps können wird das problemlos bewerkstelligen:
Code cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <iostream>
int main() {
int *array; // Zeiger auf Array deklarieren
unsigned size, tmp, i; // Ein paar Hilfsvariablen
std::cin >> size; // Größe des Arrays eingeben
array = new int[size]; // Mit new ein Array alloziieren, in den Klammern steht die Größe
for(i = 0; i < size; i++) {
std::cin >> tmp; // int-Wert eingeben
array[i] = tmp; // und im Array speichern
}
for(i = 0; i < size; i++) {
std::cout << array[i] << std::endl; // ausgeben
}
delete [] array; // Array zerstören
std::cin.get();
} |
Mit new[size] kann man die dynamische Größe dann alloziieren, new gibt dann die Adresse des ersten Elementes im Array zurück, alle anderen kommen dann hintereinander weg. Auch hier muss der Speicher wieder freigegben werden. Mit delete geht das nicht, würden wir "delete array" schreiben, wäre das gleichbedeutend mit "delete &array[0]", also lösche Adresse des erstesn Heap-Ints. Da es dann aber noch array[1 - 9] gäbe, wäre das ein Speicherleck. Mit einer Schleife kann man alle Elemente löschen, oder man verwendet die delete [] Notation, die automatisch das komplette Array löscht.
So, jetzt können wir mal ein wenig in die Vollen gehen und Anwendungsmöglichkeiten zeigen.
Wir werden das Array in einer Klasse kapseln. Mithilfe von Methoden und Operatorüberladungen sind wir somit in der Lage, Arrays zu erschaffen wie in PHP.
Also, here we go, aber Achtung: Jetzt sollte man schon etwas mehr Ahnung von C++ haben:
Code cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include <iostream>
using namespace std;
template <typename T>
class MyArray {
private:
struct Rep { // Repräsentationsschnittstelle
T *array; // das Array
unsigned len; // aktuelle Größe des Arrays
} val;
public:
MyArray() { // Standartkonstruktor
val.len = 0;
}
MyArray(int size) {
val.len = size; // Länge speichern
val.array = new T[size]; // Array initialisieren
for(int i = 0; i < size; i++)
val.array[i] = 0;
}
MyArray(const MyArray &cpy) {
for(int i = 0; i < Length(); i++)
cpy.Insert(i, val.array[i]); // Achtung: Der '='-Operator muss definiert sein!
}
~MyArray() { // Im Destruktor das Array löschen
delete [] val.array;
}
const unsigned& Length() const { // gibt die Länge des Arrays zurück
return val.len;
}
void Resize(unsigned neueGroesse) { // vergrößert/kleinert unser dynamisches Array
if(neueGroesse + 1 == 0) {// Größe ist 0? Dann löschen wir einfach nur
delete [] val.array;
val.len = 0;
return;
}
int i;
T *buf = new T[val.len]; // Puffer erstellen, für Wert-Tausch
for(i = 0; i < val.len; i++)
buf[i] = val.array[i]; // Array temporär kopieren
delete [] val.array; // Altes Array löschen
val.array = new T[neueGroesse + 1]; // neues Array erstellen
for(i = 0; i < neueGroesse; i++) {
val.array[i] = buf[i]; // und zurücktauschen
if(i >= val.len) // wenn i größer wird als die alte Länge, sind bis zur neuen Länge uninitialiserte Werte
val.array[i] = '\0'; // also einfach die uninitialisierten Werte auf 0 setzen
}
val.len = neueGroesse + 1; // neue Länge abspeichern
delete [] buf; // Wichtig! Temporären Puffer löschen
}
void Insert(unsigned key, T value) {
if(key >= val.len || val.len == 0) // Ist der Key größer? Dann müssen wir Überlauf verhindern!
Resize(key); // Platz für key erstellen
val.array[key] = value; // Wert zuweisen, Zuweisungsoperator muss definiert sein!
}
void Read() const {
for(int i = 0; i < val.len; i++)
cout << "array[" << i << "] = " << val.array[i] << endl;
}
T& operator [](unsigned index) {
if(index > val.len) // Wenn der Index zu groß ist ---> Array vergrößern
Resize(index);
return val.array[index]; // Wert zurückgeben
}
MyArray<T> operator =(MyArray<T> a1) {
for(int i = 0; i < Length(); i++) {
a1.Insert(i, val.array[i]); // Achtung: Der '='-Operator muss definiert sein!
}
return a1;
}
void Delete(unsigned index) {
if(index > val.len)
return;
delete &val.array[index]; // Einzelnen Wert löschen
val.len--;
}
};
int main() {
MyArray<int> arr(2);
arr.Insert(0, 1);
arr.Insert(1, 5);
arr.Insert(2, 45);
arr[3] = 8;
arr.Delete(3);
arr.Insert(5, 3);
arr.Delete(5);
MyArray<int> arr2;
arr.Read();
cout << "Das Array hat " << arr.Length() << " Elemente." << endl;
cout << "Bitte einen Index eingeben: ";
unsigned index;
cin >> index;
cout << "Der Wert fuer " << index << ": " << arr[index] << endl;
MyArray<char*> namen;
namen.Insert(0, "Hans");
namen.Read();
cout.flush();
cin.get();
} |
Was für ein Anblick.
Keine Angst, ich gehe das jetzt Stück für Stück durch.
Wir machen eine Template-Klasse, unser Array kann Werte enthalten wie es will, integer, char*, was auch immer.Im private-Teil erstelle ich eine struct, um die Information etwas zu kapseln und mache gleichzeitig ein Objekt dieser Struktur mit dem Namen val. Im public-Teil sind erst mal 3 Konstruktoren vorhanden: Ein Standartkonstruktor, welcher die Länge auf 0 setzt, ein Konstruktor, der eine Länge entgegennimmt und das Array initialisert (alloziiert und mit 0 füllt) und als letztes noch ein kleiner Copy-Konstruktor, mit dem wir unser Array kopieren können.
Der Destruktor wird automatisch aufgerufen, wenn das gesamte Objekt gelöscht wird. Wenn das Objekt auf dem Stack liegt, wird der Dtor implizit aufgerufen und löscht das Heap-Array. Die Methode Length() gibt, oh Wunder, die Anzahl der Elemente im Array aus. Resize() ist eine der wichtigsten Methoden, in ihr kann man viel falsch machen, was zu Speicherlecks, Overflows und falsche Zeigerzugriffe führen kann, hier muss man sehr sehr (habe ich schon sehr gesagt?
) gut aufpassen, sonst stürzt das Programm ab.Wir prüfen erst einmal, ob die neue Größe + 1 größer als 0 ist, + 1, weil ein Array[0] ja schon ein Element hat, Länge = größter Index + 1, denn bei der Länge fangen wir an bei 1 zu zählen, beim Index bei 0.
Wenn dies der Fall ist, dann löschen wir das Array einfach, man kann auch eine Fehlermeldung ausgeben lassen. So, jetzt wird's spannend: wir erstellen eine kleine Zählvariable und ein neues, temporäres Array vom Template-Typ T mit der selben Größe wie unser aktuelles Array. Dann kopieren wir das Array. Jetzt können wir das lokale Array leeren (delete []) und machen es neu, mit der Größe, die als Parameter übergeben wurde und kreieren das neue Array mit new[] und der Länge + 1. Jetzt kopieren wir die Arrays wieder zurück. Aufpassen: unser Array wird größer, aber die Werte sind noch nicht da. Wir prüfen also, ob i gerade größer als die alte Größe ist, wenn ja, initialisieren wir die Werte vor mit 0. Jetzt weisen wir noch die neue Länge zu und überschreiben die alte. Und jetzt gut aufpassen, wir müssen natürlich das buf-Array löschen (delete []), sonst Speicherleck!
Puh! Das war die wohl wichtigste Methode der ganzen Geschichte. Die Methode Insert() fügt an der Position key den value ein. Wir prüfen, ob der key größer ist als die Länge. Wenn das der Fall sein sollte, müssen wir mit Resize() das Array vergrößern. Jetzt können wir in einer Schleife die Werte zuweisen, aber Achtung: die Werte, die im Array gespeichert werden, bei uns Template-T, müssen den Zuweisungsoperator definiert haben, int hat ihn natürlich schon, aber z.B. char* nicht, also vorsicht!
Mit Read() geben wir schön formatiert alle Werte des Arrays aus. Am Ende noch Operatorüberladungen: Der Index-Operator wird überladen, damit wir auf das Objekt so zugreifen können wie auf ein Array. Auch hier müssen wir auf Überlauf prüfen, und ggf. vergrößern, dann ist die Rückgabe logischerweise auch 0. Man kann natürlich auch eine Exception werfen, wie man will.
Dann noch eine Überladung von =, das muss ich jetzt nicht weiter erklären. Die allerletzte Methode löscht ein einzelnes Element, wenn es vorhanden ist, aus dem Array und verringert die Länge.
Uff! Mannomann, ätzend, nicht wahr?
Aber das wird jetzt belohnt, man schaue sich die main()-Funktion an. Soviel Komfort, man kann das Objekt fast wie ein Array behandeln, Keys verwenden, wie man will, es gibt keinen Überlauf mehr, der Speicher wird automatisch bereinigt, das Array kann char*, int, string, ja was auch immer speichern, und die index-Reihen bleiben erhalten, wenn man einen Wert in der Mitte löscht, wird er 0, löscht man ihn am Ende, wird das Array kürzer. Jetzt kann speichertechnisch nichts mehr passieren. 
Lasst euch das Ergebnis einfach mal ausgeben.
Und gleichzeitig sieht man schon, wofür dieses Gedöhns gut sein könnte: wenn wir statt dem Template-T ein char-Array hätten, dann wäre das prinzipiell schon eine kleine String-Klasse, á la std::string. Und man sieht, dieses Thema spielt in C++ eine große Rolle.
4. Ausblick
Das war jetzt aber nur die Spitze des Eisbergs.
Die dynamische Speicherverwaltung ist ein sehr komplexes Thema, denn neben Arrays besteht immer noch die Möglichkeit, ganze Listen, sogenannte "Verkettete Listen", zu kreieren, das sind dann statt Arrays ganze Objekte, die miteinander per Zeiger verknüpft werden, und das ist noch etwas komplizierter. Und Übrigens: das ist auch ein sehr beliebtes Prüfungsthema für Info-Studenten.
C++ selbst hat Vorgaben für solche Listen, gesammelt in der Standartbibliothek, genauer in der STL (Standart Template Libary). Aber darauf jetzt einzugehen, würde nur den Rahmen sprengen, denn das ist ein sehr komplexes Thema in C++.
___
Ich hoffe, dir hat mein *erstes* Tutorial gut gefallen und du konntest einige Verwirrungen, die C++ hinterlassen hat, aus dem Weg räumen. Ich glaube aber, mit meinem letzten Beispiel habe ich noch mehr Verwirrung verursacht.
Je nach Bewertung bin ich selbstverständlich bereit, das Thema noch etwas auszubauen, besonders das Thema "Verkettete Listen", dann stelle ich das Thema mal vor mit all seinen Scheußlichkeiten und allem, was C++ zu bieten hat (Polymorphie z.B., mit der ich mich hier noch zurückgehalten habe .Noch viel Spaß weiterhin mit C++, denn es wird nicht leichter! Aber wir sind doch alle Masochisten, oder?
Kommentar schreiben
Login
Bereiche
Kategorien
Forum - Programming
Shop @ tutorials.de
Artikel bewerten