lernen:stapeln
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | lernen:stapeln [2020-07-27 09:05] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | |||
+ | ====== C++ Arten, Kisten zu stapeln ====== | ||
+ | |||
+ | > Unsere Sprache bestimmt unsere Denkweise | ||
+ | > und die Gestalt der Dinge, welche wir denken können. | ||
+ | >> --- Benjamin Lee Whorf | ||
+ | |||
+ | Die Variation und Flexibilität von Programmiertechniken | ||
+ | in der Programmiersprache C++ | ||
+ | wird am Beispiel eines allgemeinen Konzeptes vorgeführt: | ||
+ | Die Darstellung bietet einen Einblick in den Umfang | ||
+ | und die Möglichkeiten moderner Programmiersprachen | ||
+ | und will Interesse an der weiteren Beschäftigung | ||
+ | mit diesen Konzepten im Allgemeinen und der Programmiersprache C++ | ||
+ | im Besonderen wecken. | ||
+ | |||
+ | ====== Einleitung ====== | ||
+ | ===== Die Rolle der Sprache ===== | ||
+ | |||
+ | Der Umgang mit Computern erfordert zumeist die Beschreibung der Algorithmen | ||
+ | zur Lösung gestellter Aufgaben in einer Textform (Sprache), | ||
+ | die sowohl der Maschine als auch dem Menschen zugänglich ist. | ||
+ | Lesbarkeit, Schreibbarkeit und Wartbarkeit (Programmier-Effizienz) | ||
+ | sind neben der Laufzeit-Effizienz | ||
+ | wichtige Kriterien für den Einsatz einer bestimmten Programmiersprache. | ||
+ | |||
+ | Unterschiedliche Anforderungen des Problembereichs erfordern | ||
+ | zudem unterschiedliches Herangehen und unterschiedlich komplizierte Lösungen. | ||
+ | |||
+ | Die Programmiersprache C++ [4, 5, 6, 7] | ||
+ | unterstützt eine Vielzahl verschiedener Programmier- und Denkweisen | ||
+ | (prozedural, | ||
+ | in gleicher Weise, ohne einen Stil durchgängig aufzuzwingen. | ||
+ | Die Sprache C++ entwickelte sich etappenweise aus C [8]. | ||
+ | Das Erlernen der Programmiersprache ist ebenfalls ein inkrementeller, | ||
+ | stufenweiser Prozess, der durch die gegenseitige Unabhängigkeit | ||
+ | (Orthogonalität) der Sprachkonzepte von C++ gefördert wird: | ||
+ | |||
+ | > C++ ist eine Sprache, mit der man wachsen kann. [4] | ||
+ | |||
+ | Allerdings ist C++ nicht im Vorbeigehen erlernbar. | ||
+ | Tiefes Verständnis und sicherer Umgang sind nur bei intensiver, | ||
+ | oft mehrjähriger Beschäftigung mit den informationstechnischen Konzepten, | ||
+ | mit Lehrtexten und "guten Beispielen" | ||
+ | |||
+ | > Wir brauchen Intelligenz, | ||
+ | |||
+ | Warum sollte jemand diesen steinigen Pfad betreten? Einige Argumente dafür, | ||
+ | die Variation und Flexibilität verschiedener Techniken in C++ | ||
+ | werden an einer allgemeinen programmiertechnischen Idee vorgeführt: | ||
+ | dem Stapel (engl. stack). Idee und Vorgehen entstammen abgewandelt aus [2]. | ||
+ | |||
+ | ===== (Hoch-)Stapeleien ===== | ||
+ | |||
+ | Der Einsatz von Stapeln ergibt sich aus der Notwendigkeit | ||
+ | flächensparender Lagerung. | ||
+ | Diese allgemeine Aufgabe [1, 2, 3] kann leicht ausarten, | ||
+ | wie das Art-Projekt "The Wall" von Christo und Jeanne-Claude [1] zeigt, | ||
+ | bei dem im Sommer 1999 (bis zum 3. Oktober 1999) 13000 buntbemalte Ölfässer | ||
+ | im alten Oberhausener Gasometer aufgeschichtet wurden. | ||
+ | Auch das Stapeln von Katzen [2] ist nicht trivial, | ||
+ | falls Katzen (und/oder Tierschützer) sich wehren, | ||
+ | ergibt im Englischen aber ein lustiges Wortspiel. | ||
+ | Das Umschichten großer Stapel kann, bei eingeschränkten Stapelmöglichkeiten, | ||
+ | sogar jede dem Menschen zugängliche Zeitspanne überschreiten: | ||
+ | $2^C$ Arbeitsschritte sind nötig beim Turm von Hanoi [3] | ||
+ | aus $C$ Kupferscheiben mit nach oben abnehmendem Durchmesser. | ||
+ | (Die Anzahl $C$ ist eine relativ kleine Konstante. | ||
+ | Wären es nur 50 Scheiben, | ||
+ | und würde das Bewegen einer Scheibe nur eine Sekunde dauern, | ||
+ | ergäben sich $2^{50}$ Sekunden = ca. 35 Millionen Jahre!) | ||
+ | |||
+ | ===== Was ist ein Stapel ? ===== | ||
+ | |||
+ | < | ||
+ | Stapel | ||
+ | |||
+ | - ist voll -> | ||
+ | . . | ||
+ | . | ||
+ | . | ||
+ | - waechst | ||
+ | . | . | ||
+ | - schrumpft | ||
+ | . | ||
+ | . | ||
+ | +---+ | ||
+ | | 3 | -> oberste Kiste (aufmachen) | ||
+ | +---+ | ||
+ | | 2 | | ||
+ | +---+ | ||
+ | | 1 | | ||
+ | - ist leer -> | ||
+ | </ | ||
+ | Abb. 1: Ein Stapel von Kisten | ||
+ | |||
+ | Als Material zum Stapeln nehmen wir der Anschaulichkeit halber Kisten (Abb. 1). | ||
+ | Ein Stapel ist eine (als vertikal aufgestellt vorstellbare) Folge von Kisten, | ||
+ | bei der | ||
+ | |||
+ | * immer nur auf die oberste zugegriffen werden kann (um hineinzuschauen), | ||
+ | * die oberste vom Stapel entfernt werden kann (falls sich noch eine Kiste auf dem Stapel befindet), | ||
+ | * eine weitere Kiste oben drauf gesetzt werden kann (falls nicht die maximale Stapelhöhe erreicht ist). | ||
+ | |||
+ | Die Stapelhöhe kann begrenzt sein durch z.B. die Körperhöhe des Hochstaplers, | ||
+ | die Höhe (des Gasometers), | ||
+ | die Belastbarkeit des Untergrunds oder der darunterliegenden Kisten. | ||
+ | |||
+ | Es ist nicht möglich oder nicht erlaubt bzw. | ||
+ | verboten bei Strafe des Erschlagenwerdens durch den umfallenden Stapel, | ||
+ | auf einem vollen Stapel eine weitere Kiste abzusetzen, | ||
+ | ebenso wie es unmöglich ist, von einem leeren Platz eine Kiste wegzunehmen. | ||
+ | (Mancher Durstige würde das sich gleichwohl wünschen, | ||
+ | und ein Mathematiker könnte sich das sogar vorstellen.) | ||
+ | |||
+ | ===== Was haben Stapel mit Programmierung zu tun? ===== | ||
+ | |||
+ | Stapel sind eine wesentliche Grundlage für die Implementierung prozeduraler | ||
+ | (imperativer) Programmiersprachen, | ||
+ | die Wertparameter und rekursive Funktionsaufrufe erlauben, z.B. die Sprache C. | ||
+ | |||
+ | Im programmiertechnischen Sinne gibt es Obergrenzen für die Stapelgröße $C$ | ||
+ | durch die Endlichkeit des Computerspeichers | ||
+ | |||
+ | C < Speicherplatz / Platz_einer_Kiste | ||
+ | |||
+ | oder den für den Stapel vorgesehenen Speicherplatz, | ||
+ | da im Speicher neben dem Stapel weitere Daten und Programmanweisungen | ||
+ | Platz finden müssen. | ||
+ | |||
+ | Wegen des linearen Speicheraufbaus im Computer ist es beim Programmieren | ||
+ | möglich, auch normalerweise " | ||
+ | So lässt sich ein Stapelüberlauf (bei zu vielen Kisten) oder | ||
+ | Stapelunterlauf (bei zu wenig Kisten) provozieren. | ||
+ | Dann wird auf anderweitig genutzten Speicher und darin enthaltene Daten | ||
+ | lesend und schreibend zugegriffen. | ||
+ | Allerdings geschieht dies nicht ungestraft --- | ||
+ | auch wenn es wie im richtigen Leben nicht immer den Verursacher, | ||
+ | also den Schuldigen, trifft. | ||
+ | |||
+ | Werden keine Vorkehrungen gegen versehentliche (oder absichtliche) | ||
+ | Verletzungen des Konzeptes getroffen, sind Folgen unvermeidlich: | ||
+ | unvorhersagbares, | ||
+ | Datenverlust und daraus folgende Schäden, Verletzung von Schutzmechanismen etc. | ||
+ | |||
+ | Die " | ||
+ | ist eine nicht-triviale Herausforderung. | ||
+ | Die Beherrschung hochentwickelter programmiertechnischer Konzepte kann | ||
+ | (muss leider nicht) zur einfacheren und sichereren Handhabung | ||
+ | von Programmquellen beitragen. Sehen wir uns an, | ||
+ | ob und wie einzelne Techniken in C++ | ||
+ | zu verständlichen Programmen mit geringer Fehlerquote führen. | ||
+ | |||
+ | ====== Stapel-Techniken ====== | ||
+ | ===== Strukturierte Programmierung ===== | ||
+ | |||
+ | Häufig ist man geneigt, | ||
+ | sofort einzelnen Werten Datentypen der benutzten Sprache zuordnen. | ||
+ | Für die Lesbarkeit von Programmen ist jedoch wichtig, | ||
+ | die Beschreibung des Problembereichs | ||
+ | von programmiertechnischen Details abzutrennen, | ||
+ | |||
+ | <code cpp> | ||
+ | #define C 3 /* aller guten Dinge sind drei */ | ||
+ | #define Kiste int /* wir reden nur noch von Kisten */ | ||
+ | Kiste | ||
+ | </ | ||
+ | |||
+ | Wenn sich Art oder Inhalt der Kisten ändern sollte | ||
+ | (durch äußere Zwänge oder Entscheidungen beim Programmentwurf), | ||
+ | bleiben Eingriffe in getestete Programmteile begrenzt | ||
+ | und verringern den notwendigen Aufwand für nachfolgende Tests. | ||
+ | Da es (auf niedrigster Programmierebene) keine unmittelbare Möglichkeit gibt, | ||
+ | die Anzahl im Programm vorhandener Kisten (oder Variablen) zu zählen, | ||
+ | ist über deren Anzahl auf dem Stapel Buch zu führen. | ||
+ | |||
+ | <code cpp> | ||
+ | int const maximum = C; | ||
+ | Kiste stapel[maximum]; | ||
+ | int | ||
+ | </ | ||
+ | |||
+ | Nun wird mit den Daten munter gearbeitet: | ||
+ | |||
+ | <code cpp> | ||
+ | #include < | ||
+ | |||
+ | void stapel_demo_1() | ||
+ | { | ||
+ | std::cout << " | ||
+ | |||
+ | int i = 0; | ||
+ | while (i < C && anzahl < maximum) | ||
+ | { | ||
+ | stapel[anzahl++] = kiste[i++]; | ||
+ | std::cout << stapel[anzahl-1] << ' '; | ||
+ | } | ||
+ | if (anzahl > 0) // Stapel nicht leer | ||
+ | { | ||
+ | std::cout << " | ||
+ | stapel[anzahl-1] = kiste[C]; | ||
+ | std::cout << " nach " << stapel[anzahl-1]; | ||
+ | } | ||
+ | std::cout << " | ||
+ | |||
+ | while (anzahl > 0) // Stapel nicht leer | ||
+ | std::cout << stapel[--anzahl] << ' '; | ||
+ | std::cout << ' | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Die auf den Stapel gelegten Kisten werden in umgekehrter Folge | ||
+ | (last in - first out) wieder entnommen. | ||
+ | Vor dem Auflegen und Entnehmen von Kisten muss immer (!) geprüft werden, | ||
+ | ob die Aktion gefahrlos durchgeführt werden kann. | ||
+ | |||
+ | Allerdings - wo ist der Stapel? | ||
+ | Er existiert nur als Vorstellung im Kopf des Programmierers! | ||
+ | Jeder andere, der diesen Quelltext zum ersten mal sieht, | ||
+ | muss sich erst in dessen Denkweise hinein versetzen und z.B. begreifen, | ||
+ | warum einmal bei '' | ||
+ | beim Herunterzählen in '' | ||
+ | ((C-Programmierer kennen den Unterschied.)) | ||
+ | Und wehe, ein Programmierer vergisst einmal, | ||
+ | dass das letzte belegte Element im Stapel das mit dem Index '' | ||
+ | ist.((Ich weiß, ich weiß: C-Programmierer vergessen das nicht. | ||
+ | Nie. Wirklich! ... Höchstens manchmal.)) | ||
+ | |||
+ | ===== Prozedurale Programmierung ===== | ||
+ | |||
+ | Jede Aktion mit dem Stapel lässt sich in einer Funktion | ||
+ | unterbringen: | ||
+ | als Wahrheitswerte verwendet - Null als falsch, alle anderen als wahr. | ||
+ | C-Programmierer können vielfältig " | ||
+ | aber nur auf eine Weise " | ||
+ | mit den Werten true und false genutzt werden.)) | ||
+ | |||
+ | <code cpp> | ||
+ | int voll(); | ||
+ | int leer(); | ||
+ | void | ||
+ | Kiste runter(); | ||
+ | Kiste* oben(); | ||
+ | </ | ||
+ | |||
+ | Alle Aktionen greifen auf einen, denselben, Stapel von Kisten zu. | ||
+ | Sind sie einmal durch | ||
+ | |||
+ | <code cpp> | ||
+ | int voll() | ||
+ | int leer() | ||
+ | void | ||
+ | Kiste runter() | ||
+ | Kiste* oben() | ||
+ | </ | ||
+ | |||
+ | definiert (unter Nutzung der globalen Variablen aus dem | ||
+ | [[# | ||
+ | ist ihre Verwendung einleuchtend: | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_2() | ||
+ | { | ||
+ | std::cout << " | ||
+ | |||
+ | int i = 0; | ||
+ | while (i < C && !voll()) | ||
+ | { | ||
+ | drauf( kiste[i++] ); | ||
+ | std::cout << *oben() << ' '; | ||
+ | } | ||
+ | if (!leer()) | ||
+ | { | ||
+ | std::cout << " | ||
+ | *oben() = kiste[C]; | ||
+ | std::cout << " nach " << *oben(); | ||
+ | } | ||
+ | cout << " | ||
+ | |||
+ | while (!leer()) | ||
+ | std::cout << runter() << ' '; | ||
+ | |||
+ | std::cout << ' | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Der Ausdruck '' | ||
+ | komplizierte Ausdrücke auf der linken Seite einer Zuweisung | ||
+ | (anstelle einer Variable) stehen dürfen, | ||
+ | sofern ihr Wert eine Speicheradresse (Linkswert, " | ||
+ | bildet.((Hier wird die Adresse mittels eines von der Funktion '' | ||
+ | gelieferten Zeigers ermittelt, aber dies ist ein Implementierungsdetail.)) | ||
+ | |||
+ | Einschränkungen: | ||
+ | |||
+ | * Der Funktionsaufruf und die Wertübergabe kosten Zeit, so dass Programmierer, | ||
+ | * Bis jetzt kann nur ein einziger Stapel im Programm betrieben werden. | ||
+ | |||
+ | Versuchen wir, diese Nachteile durch andere Techniken zu überwinden. | ||
+ | |||
+ | ===== Modularisierung ===== | ||
+ | |||
+ | Nichttriviale Programme bestehen aus mehreren, | ||
+ | unabhängig voneinander übersetzten Programmquelltexten. | ||
+ | Darin enthaltene Funktionen können von anderen Teilen aus aufgerufen werden, | ||
+ | sofern die Art der Parameterübergabe und der Ergebnistyp bekannt sind | ||
+ | (und die Funktion nicht unzugänglich gemacht wurde). | ||
+ | Will man den Stapel in mehreren Programmteilen verwenden, | ||
+ | sind Funktionsdeklaration (die Angabe von Parameter- und Rückgabetypen) | ||
+ | und Funktionsdefinition (die Angabe des Funktionsrumpfes) | ||
+ | voneinander zu trennen und in verschiedenen Dateien unterzubringen. | ||
+ | |||
+ | <code cpp> | ||
+ | // Datei " | ||
+ | #ifndef __STAPEL__ | ||
+ | #define __STAPEL__ | ||
+ | int voll(); | ||
+ | int leer(); | ||
+ | void | ||
+ | Kiste runter(); | ||
+ | Kiste* oben(); | ||
+ | #endif // __STAPEL__ | ||
+ | |||
+ | // Datei " | ||
+ | #include " | ||
+ | |||
+ | int const maximum = C; | ||
+ | static Kiste stapel[maximum]; | ||
+ | static int | ||
+ | |||
+ | int voll() | ||
+ | int leer() | ||
+ | void | ||
+ | Kiste runter() | ||
+ | Kiste* oben() | ||
+ | </ | ||
+ | |||
+ | Die '' | ||
+ | verhindert den unerwünschten äußeren Zugriff, | ||
+ | so dass der Stapel bei ordnungsgemäßem Gebrauch auch nicht aus Versehen | ||
+ | in einen unkontrollierten Zustand geraten kann. | ||
+ | |||
+ | Nach Einbinden der Header-Datei ''" | ||
+ | kann auf den Stapel von jedem beliebigen Teilprogramm zugegriffen werden. | ||
+ | Die nutzbare deklarierte Schnittstelle bleibt unverändert. | ||
+ | |||
+ | <code cpp> | ||
+ | // andere Datei : | ||
+ | #include " | ||
+ | |||
+ | void stapel_demo_3() | ||
+ | { | ||
+ | int i = 0; | ||
+ | while (i<3 && !voll()) | ||
+ | drauf( kiste[i++] ); | ||
+ | if (!leer()) | ||
+ | *oben() = kiste[3]; | ||
+ | while (!leer()) | ||
+ | runter(); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Einschränkungen: | ||
+ | |||
+ | * Bis jetzt ist wenig gewonnen, denn noch immer ist nur ein einziger Stapel verfügbar. | ||
+ | * Nutzer sind gezwungen, eine langsame Schnittstelle zu nutzen. | ||
+ | |||
+ | ===== Mehrere Stapel ===== | ||
+ | |||
+ | Bei mehreren gleichzeitig aktiven Stapeln müssen Referenzen | ||
+ | (oder Zeiger) auf den jeweils zu nutzenden Stapel übergeben werden. | ||
+ | Dafür müssen sich die Funktionsprototypen ändern. | ||
+ | |||
+ | <code cpp> | ||
+ | // Header-Datei: | ||
+ | struct Stapel | ||
+ | { | ||
+ | int anzahl; | ||
+ | Kiste stapel[maximum]; | ||
+ | }; | ||
+ | |||
+ | int voll(Stapel const& s); /* noch Kisten ablegbar? | ||
+ | int leer(Stapel const& s); /* noch Kisten entnehmbar? */ | ||
+ | void | ||
+ | Kiste runter(Stapel& | ||
+ | Kiste& oben(Stapel& | ||
+ | void | ||
+ | </ | ||
+ | |||
+ | Hinzu muss eine neue Funktion kommen, die sicherstellt, | ||
+ | (der Zähler) des Stapels am Anfang wirklich auf Null steht. | ||
+ | |||
+ | <code cpp> | ||
+ | // Implementierung : | ||
+ | int voll(Stapel const& s) { return s.anzahl == maximum; | ||
+ | int leer(Stapel const& s) { return s.anzahl == 0; } | ||
+ | void | ||
+ | Kiste runter(Stapel& | ||
+ | Kiste& oben(Stapel& | ||
+ | void | ||
+ | |||
+ | // Nutzung : | ||
+ | void stapel_demo_4() | ||
+ | { | ||
+ | std::cout << " | ||
+ | |||
+ | Stapel stapel1, stapel2; | ||
+ | neu(stapel1); | ||
+ | neu(stapel2); | ||
+ | |||
+ | int i = 0; | ||
+ | while (i<3 && !voll(stapel1)) | ||
+ | drauf(stapel1, | ||
+ | if (!leer(stapel1)) | ||
+ | oben(stapel1) = kiste[3]; | ||
+ | while (!leer(stapel1) && !voll(stapel2)) | ||
+ | drauf( stapel2, runter(stapel1) ); // mal eben alles umstapeln | ||
+ | while (!leer(stapel2)) | ||
+ | std::cout << runter(stapel2) << ' '; | ||
+ | std::cout << ' | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Einschränkungen: | ||
+ | |||
+ | * Die explizit anzugebende Initialisierung ist fehleranfällig. | ||
+ | * Zwar können mehrere Stapel genutzt werden, aber die Datenstruktur ist offen und lädt (wieder) wie im Abschnitt [[# | ||
+ | |||
+ | ===== Datenabstraktion ===== | ||
+ | |||
+ | Das Innere der Stapel-Implementierung braucht nicht offengelegt zu werden. | ||
+ | Der Stapel wird damit zu einem undurchsichtigen (opaken) Typ. | ||
+ | Diese Technik wird in der C-Erweiterung Objective C genutzt. | ||
+ | Ohne Kenntnis der inneren Struktur wird der Direkt-Zugriff auf Kisten | ||
+ | im Stapel zumindest riskant. Die Struktur kann leicht geändert werden, | ||
+ | ohne dass aufsetzende Programme geändert werden müssen. | ||
+ | Allerdings hat diese Technik auch ihren Preis: | ||
+ | Es dürfen nur Zeiger auf Stapel angesprochen werden --- | ||
+ | Stapel müssen dynamisch angelegt werden. | ||
+ | |||
+ | <code cpp> | ||
+ | // Header-Datei : | ||
+ | struct Stapel; | ||
+ | // ... Deklaration nutzbarer Funktionen | ||
+ | |||
+ | // Implementierung : | ||
+ | struct Stapel | ||
+ | { | ||
+ | int anzahl; | ||
+ | Kiste stapel[maximum]; | ||
+ | }; | ||
+ | |||
+ | int | ||
+ | int | ||
+ | void drauf(Stapel* s, Kiste neu) { s-> | ||
+ | Kiste | ||
+ | Kiste& | ||
+ | |||
+ | Stapel* erzeugen() | ||
+ | { | ||
+ | Stapel *s = new Stapel; s-> | ||
+ | return s; | ||
+ | } | ||
+ | |||
+ | void beenden(Stapel* alt) { delete alt; } | ||
+ | </ | ||
+ | |||
+ | Eine Struktur kann im Ganzen kopiert und zugewiesen werden, | ||
+ | wie im nächsten Beispiel: | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_5() | ||
+ | { | ||
+ | std::cout << " | ||
+ | Stapel* stapel1 = erzeugen(); // dynamischen Speicher anfordern | ||
+ | Stapel* stapel2 = erzeugen(); | ||
+ | int i = 0; | ||
+ | while (i<3 && !voll(stapel1)) | ||
+ | drauf(stapel1, | ||
+ | *stapel2 = *stapel1; | ||
+ | while (!leer(stapel1)) runter(stapel1); | ||
+ | |||
+ | std::cout << " | ||
+ | while (!leer(stapel2)) | ||
+ | std::cout << runter(stapel2) << ' '; | ||
+ | std::cout << ' | ||
+ | beenden(stapel1); | ||
+ | beenden(stapel2); | ||
+ | stapel1 = stapel2 = 0; // Zeiger als leer markieren (?) | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Bis jetzt haben wir uns mit jeder Neuerung eigentlich stets verschlechtert: | ||
+ | Die ausdrückliche Initialisierung der Stapel | ||
+ | und die erforderliche Speicherfreigabe sind fehleranfällig, | ||
+ | da sie leicht vergessen werden können. | ||
+ | Der Umgang mit nichtinitialisierten oder ungültigen Zeigern | ||
+ | eröffnet weitere Fehlerquellen. | ||
+ | Die stets notwendige Zeiger-Dereferenzierung kostet zusätzlich Laufzeit. | ||
+ | Offenbar ist dies der falsche Weg. Versuchen wir es anders. | ||
+ | |||
+ | ===== Automatisierung ===== | ||
+ | |||
+ | Abstraktion soll von nervtötender und fehleranfälliger Routine entlasten | ||
+ | und den Rücken (die Hände, den Kopf...) | ||
+ | für die wesentlichen Aufgaben freihalten. | ||
+ | "C++ ist der Weg, sich eine eigene Sprache zu schaffen", | ||
+ | die möglichst dem bearbeiteten Problembereich nahe kommen soll. | ||
+ | |||
+ | Initialisierungen, | ||
+ | lassen sich automatisieren und belasten dann den Nutzer des Stapels nicht mehr. | ||
+ | |||
+ | Konstruktoren und Destruktoren sind innerhalb der Struktur | ||
+ | deklarierte gleichnamige Funktionen (Methoden, member functions), | ||
+ | die beim Anlegen einer Variable bzw. | ||
+ | an ihrem Lebensende automatisch ausgeführt werden. | ||
+ | |||
+ | <code cpp> | ||
+ | struct Stapel | ||
+ | { | ||
+ | Stapel(); | ||
+ | ~Stapel(); | ||
+ | int anzahl; | ||
+ | Kiste stapel[maximum]; | ||
+ | }; | ||
+ | |||
+ | // Implementierung : | ||
+ | |||
+ | Stapel:: | ||
+ | Stapel:: | ||
+ | |||
+ | </ | ||
+ | |||
+ | Initialisierungen der Stapel-Komponenten können beim Anlegen erfolgen. | ||
+ | Ein Konstruktor ruft zuerst die Konstruktoren aller Komponenten (member) auf. | ||
+ | Hinter der Konstruktor-Funktionsklammer (nach einem Doppelpunkt) | ||
+ | lassen sich Startwerte an die Basiskonstruktoren übergeben. | ||
+ | Dann können im Rumpf des Konstruktors Aktionen mit den Komponenten erfolgen. | ||
+ | Der Destruktor (der Operator ~ liefert das bitweise " | ||
+ | ist nur notwendig, falls Aufräumarbeiten zu erledigen sind. | ||
+ | |||
+ | <code cpp> | ||
+ | int voll(Stapel const& s) { return s.anzahl == maximum; | ||
+ | int leer(Stapel const& s) { return s.anzahl == 0; } | ||
+ | void | ||
+ | Kiste runter(Stapel& | ||
+ | Kiste& oben(Stapel& | ||
+ | |||
+ | // Nutzung: | ||
+ | |||
+ | void stapel_demo_6() | ||
+ | { | ||
+ | std::cout << " | ||
+ | Stapel stapel1, stapel2; | ||
+ | |||
+ | int i = 0; | ||
+ | while (i<3 && !voll(stapel1)) | ||
+ | drauf(stapel1, | ||
+ | |||
+ | if (!leer(stapel1)) | ||
+ | oben(stapel1) = kiste[3]; | ||
+ | |||
+ | while (!leer(stapel1) && !voll(stapel2)) | ||
+ | drauf(stapel2, | ||
+ | |||
+ | while (!leer(stapel2)) | ||
+ | std::cout << runter(stapel2) << ' '; | ||
+ | std::cout << ' | ||
+ | } // Destruktoraufruf beim Verlassen des Blocks | ||
+ | </ | ||
+ | |||
+ | ===== Objektbasierte Programmierung ===== | ||
+ | |||
+ | Wenn es schon Start- und Aufräumroutinen gibt, | ||
+ | können auch andere Funktionen als Methoden (member functions) | ||
+ | in den Stapel integriert werden.((Genaugenommen | ||
+ | verlief die Entwicklung von C++ anders herum.)) | ||
+ | |||
+ | <code cpp> | ||
+ | // Schnittstelle : | ||
+ | |||
+ | struct Stapel | ||
+ | { | ||
+ | Stapel(); | ||
+ | |||
+ | int voll(); | ||
+ | int leer(); | ||
+ | void | ||
+ | Kiste runter(); | ||
+ | Kiste& oben(); | ||
+ | |||
+ | int anzahl; | ||
+ | Kiste stapel[maximum]; | ||
+ | }; | ||
+ | |||
+ | // Implementierung : | ||
+ | |||
+ | Stapel:: | ||
+ | |||
+ | int Stapel:: | ||
+ | int Stapel:: | ||
+ | void | ||
+ | Kiste Stapel:: | ||
+ | Kiste& Stapel:: | ||
+ | </ | ||
+ | |||
+ | Die Methoden haben direkten Zugriff auf die Komponenten der Stapel-Struktur. | ||
+ | |||
+ | Hier ändert sich die Sichtweise: | ||
+ | Bisher wurden Stapel als Datenblöcke an Funktionen übergeben, | ||
+ | die dann etwas mit den Stapeln anstellten. | ||
+ | Jetzt wird der Stapel aufgefordert, | ||
+ | Bisher passive Datenstrukturen werden zu aktiven Objekten, zu Agenten. | ||
+ | Dies ist der Kern der objektbasierten (objektorientierten) Denkweise. | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_7() | ||
+ | { | ||
+ | std::cout << " | ||
+ | |||
+ | Stapel stapel; | ||
+ | |||
+ | int i = 0; | ||
+ | while (i<3 && !stapel.voll()) | ||
+ | stapel.drauf(kiste[i++]); | ||
+ | |||
+ | if (!stapel.leer()) | ||
+ | stapel.oben() = kiste[3]; | ||
+ | |||
+ | while (!stapel.leer()) | ||
+ | std::cout << stapel.runter() << ' '; | ||
+ | std::cout << ' | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Rumpfersetzung (Inlining) ===== | ||
+ | |||
+ | Die Effizienz der Ausführung war ein wichtiges Entwurfskriterium | ||
+ | bei der Entwicklung von C zu C++ [5]. | ||
+ | Die " | ||
+ | ---- das Objektkonzept führt jedoch zur Atomisierung der Aktionen. | ||
+ | |||
+ | Viele hier auszuführende Aktionen sind elementar, | ||
+ | enthalten nur wenige Anweisungen. | ||
+ | Hier kann der Geschwindigkeitsverlust besonders schmerzhaft werden | ||
+ | (bis zum Faktor 10). | ||
+ | |||
+ | Solche kleinen Funktionen können mit dem Vorsatz '' | ||
+ | Die Definition von '' | ||
+ | Dadurch können die Anweisungen ihres Rumpfes an die aufrufende Stelle | ||
+ | gesetzt werden, ohne einen Funktionsaufruf zu generieren. | ||
+ | Die Methodenrümpfe können auch in der Strukturdefinition definiert werden | ||
+ | und sind dann automatisch '' | ||
+ | |||
+ | <code cpp> | ||
+ | struct Stapel | ||
+ | { | ||
+ | Stapel(); | ||
+ | |||
+ | int voll() | ||
+ | int leer() | ||
+ | void | ||
+ | Kiste runter() | ||
+ | Kiste& oben() | ||
+ | |||
+ | int anzahl; | ||
+ | Kiste stapel[maximum]; | ||
+ | }; | ||
+ | |||
+ | inline Stapel:: | ||
+ | </ | ||
+ | |||
+ | '' | ||
+ | Sie unterliegen der strengen Typprüfung durch den Compiler | ||
+ | und können auch keine unerwünschten Seiteneffekte erzeugen. | ||
+ | Gleichwohl ist inline nur eine Empfehlung für den Compiler. | ||
+ | Inlining sollte sich auch auf kleine Funktionen | ||
+ | (mit weniger als 3 Anweisungen) beschränken, | ||
+ | um das ausführbare Programm kürzer und nicht länger zu machen. | ||
+ | An der Nutzung ändert sich nichts: | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_8() // wie stapel_demo_7 | ||
+ | { | ||
+ | Stapel stapel; | ||
+ | //... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Schutzmechanismen ===== | ||
+ | |||
+ | Die Komponenten einer Struktur sind solange öffentlich, | ||
+ | wie nichts anderes angegeben wird. Dies kann ihre Datenintegrität gefährden | ||
+ | (Manipulation an den Methoden vorbei!) | ||
+ | und in der Folge Fehlverhalten hervorrufen. | ||
+ | |||
+ | Der Zugriff auf Teile einer Struktur lässt sich | ||
+ | durch die Kennzeichnung privater und öffentlicher Abschnitte eingeschränken | ||
+ | (Kapselung). Eine Klasse ('' | ||
+ | mit als privat voreingestellten Komponenten. Um nützlich zu sein, | ||
+ | müssen zumindest einige Methoden als öffentlich eingestuft werden. | ||
+ | |||
+ | Zusätzlich können Methoden als '' | ||
+ | Lesemethoden dürfen dann keine Bestandteile der Struktur ändern. | ||
+ | Manche Methoden wie '' | ||
+ | in einer Lese- und einer Schreibvariante angeboten werden. | ||
+ | Die konstante Methode wird gerufen, | ||
+ | wenn ein (Rechts-)Wert in einem Ausdruck benötigt wird, | ||
+ | die nicht-konstante Methode für einen Linkswert (wie bei Zuweisungen). | ||
+ | |||
+ | <code cpp> | ||
+ | class Stapel | ||
+ | { | ||
+ | public: | ||
+ | Stapel() : anzahl(0) {} | ||
+ | |||
+ | int voll() const { return anzahl == maximum; } | ||
+ | int leer() const { return anzahl == 0; } | ||
+ | void | ||
+ | Kiste runter() | ||
+ | Kiste const& oben() const { return stapel[anzahl-1]; | ||
+ | Kiste& | ||
+ | private: | ||
+ | int anzahl; | ||
+ | Kiste stapel[maximum]; | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | Die Nutzung bleibt gleich: | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_9() // wie stapel_demo_7 | ||
+ | { | ||
+ | Stapel stapel; | ||
+ | // ... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Der Compiler setzt sowohl die Zugriffskontrolle | ||
+ | als auch die Prüfung auf Konstantheit so streng wie möglich durch. | ||
+ | Der Aufruf nicht-öffentlicher Funktionen von außerhalb der Klasse | ||
+ | wird vom Compiler verweigert. | ||
+ | Ebenso dürfen bei als '' | ||
+ | nur Lesemethoden aufgerufen werden. Beide Maßnahmen sind nicht dazu da, | ||
+ | den Programmierer zu gängeln, | ||
+ | sondern schützen vor leicht zu begehenden (Denk-)Fehlern, | ||
+ | die sonst nicht oder erst nach langer Suche gefunden würden. | ||
+ | |||
+ | ===== Ressourcenverwaltung ===== | ||
+ | |||
+ | Verschiedene Stapel (unter einer Dachschräge) dürfen unterschiedlich hoch sein. | ||
+ | Der Speicher kann vorher in passender Größe vorgesehen werden | ||
+ | und wird am Ende wieder freigegeben. | ||
+ | |||
+ | <code cpp> | ||
+ | class Stapel { | ||
+ | public: | ||
+ | Stapel(int anz = 3) | ||
+ | : maximum(anz), | ||
+ | ~Stapel() { delete[] unten; } | ||
+ | Stapel(Stapel const& rechtswert); | ||
+ | Stapel& operator=(Stapel const& rechtswert); | ||
+ | int voll() const { return aktuell == unten+maximum; | ||
+ | int leer() const { return aktuell == unten; } | ||
+ | void | ||
+ | Kiste runter() | ||
+ | Kiste const& oben() const { return *(aktuell-1); | ||
+ | Kiste& | ||
+ | private: | ||
+ | int maximum; | ||
+ | Kiste *aktuell; | ||
+ | Kiste *unten; | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | Die Implementierung wird hier wegen der Zeigerarbeit wieder komplizierter. | ||
+ | Zuweisungen von Strukturen erfolgen standardmäßig Byte für Byte. | ||
+ | Sobald Zeiger in einer Struktur enthalten sind, | ||
+ | müssen Kopie und Zuweisung neu definiert oder verboten werden. | ||
+ | Methoden mit umfangreichen Anweisungen gehören in die Implementierungsdatei: | ||
+ | |||
+ | <code cpp> | ||
+ | Stapel:: | ||
+ | : maximum(x.maximum), | ||
+ | { | ||
+ | Kiste *quelle = x.unten; | ||
+ | while (quelle != x.aktuell) | ||
+ | *aktuell++ = *quelle++; | ||
+ | } | ||
+ | |||
+ | Stapel& Stapel:: | ||
+ | { | ||
+ | if (this != & | ||
+ | { | ||
+ | Stapel kopie(x); | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | } | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | // Nutzung : | ||
+ | void stapel_demo_10() | ||
+ | { | ||
+ | Stapel stapel, stapel2(10); | ||
+ | //... | ||
+ | stapel = stapel2; | ||
+ | stapel = Stapel(1000); | ||
+ | //... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Typunabhängige (generische) Programmierung ===== | ||
+ | |||
+ | Der bis jetzt getriebene Aufwand lohnt sich erst richtig, | ||
+ | wenn Stapel nicht nur aus Kisten gebaut werden können. | ||
+ | Ein Stapel aus Fässern wäre auch denkbar (wegen Christo): | ||
+ | |||
+ | <code cpp> | ||
+ | #define Fass float | ||
+ | Fass fass[] = { 1, 2, 3, 4 }; | ||
+ | </ | ||
+ | |||
+ | Dazu wird der Stapel als Schablone (engl. template) definiert, | ||
+ | die für jeden Typ '' | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T> | ||
+ | class Stapel | ||
+ | { | ||
+ | public: | ||
+ | Stapel(int anz = 3) | ||
+ | : maximum(anz), | ||
+ | ~Stapel() { delete[] unten; } | ||
+ | Stapel(Stapel const< | ||
+ | Stapel& operator=(Stapel const< | ||
+ | int voll() const { return aktuell == unten + maximum; } | ||
+ | int leer() const { return aktuell == unten; } | ||
+ | void | ||
+ | T runter() | ||
+ | T const& oben() const { return *(aktuell-1); | ||
+ | T& | ||
+ | private: | ||
+ | int maximum; | ||
+ | T *aktuell; | ||
+ | T *unten; | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | Alle Funktionen müssen bei Schablonen im Header stehen, | ||
+ | damit ihr Code für beliebige Stapelobjekte generiert werden kann, | ||
+ | auch die nicht '' | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T> | ||
+ | Stapel< | ||
+ | : maximum(x.maximum), | ||
+ | { | ||
+ | T *quelle = x.unten; | ||
+ | while (quelle != x.aktuell) | ||
+ | *aktuell++ = *quelle++; | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | Stapel< | ||
+ | { | ||
+ | if (this != & | ||
+ | { | ||
+ | Stapel kopie(x); | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | } | ||
+ | return *this; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Um die Schablone zu nutzen, | ||
+ | muss die Stapeldefinition in spitzen Klammern | ||
+ | den Typ der Stapelobjekte festlegen. Mehr ändert sich aber nicht: | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_11() | ||
+ | { | ||
+ | Stapel< | ||
+ | Stapel< | ||
+ | //... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Erschaffen und Vernichten ===== | ||
+ | |||
+ | Bisher wurde immer ein ganzes Feld von Kisten und Fässern bereitgestellt, | ||
+ | um Werte abzulegen. Das kann aber teuer oder unerwünscht sein, | ||
+ | wenn der Konstruktor der zu stapelnden Objekte umfangreiche Aktionen erledigt | ||
+ | oder bestimmte Angaben braucht (Typen ohne Default-Konstruktor) wie | ||
+ | |||
+ | <code cpp> | ||
+ | struct Kasten | ||
+ | { | ||
+ | Kasten(int i) : nr(i) { std::cout << "> Kasten " << nr << ' | ||
+ | Kasten(Kasten const& k) : nr(k.nr) | ||
+ | { std::cout << "> Kopie von Kasten " << nr << ' | ||
+ | ~Kasten() { std::cout << "< Kasten " << nr << ' | ||
+ | friend std:: | ||
+ | friend int operator== (Kasten const& x, Kasten const& y); | ||
+ | friend int operator< | ||
+ | private: | ||
+ | int nr; | ||
+ | }; | ||
+ | |||
+ | // Dateiausgabe | ||
+ | std:: | ||
+ | { | ||
+ | return os << k.nr; | ||
+ | } | ||
+ | |||
+ | // Vergleiche | ||
+ | int operator== (Kasten const& x, Kasten const& y) { return x.nr==y.nr; } | ||
+ | int operator< | ||
+ | </ | ||
+ | |||
+ | Freunde (engl. '' | ||
+ | |||
+ | Objekte lassen sich mit der Plazierungssyntax des '' | ||
+ | an beliebiger Stelle im Speicher erzeugen und vernichten: | ||
+ | |||
+ | <code cpp> | ||
+ | # | ||
+ | |||
+ | template <class T1, class T2> | ||
+ | inline void erschaffe(T1 *p, T const2& x) | ||
+ | { | ||
+ | new(p) T1(x); | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | inline void vernichte(T* p) | ||
+ | { | ||
+ | p-> | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Für bestimmte Typen ist es nötig, abweichende Definitionen zu verwenden. | ||
+ | So haben grundlegende Datentypen (char, int, float, double) | ||
+ | keine Destruktormethode (wozu auch? | ||
+ | Dann wird " | ||
+ | |||
+ | <code cpp> | ||
+ | inline void vernichte(int* ) { /* tue nichts */ } | ||
+ | inline void vernichte(double* ) { /* tue nichts */ } | ||
+ | </ | ||
+ | |||
+ | Nun lässt sich ein Stapel so bauen, | ||
+ | dass nur dann ein Konstruktoraufruf auf der Stapelspitze erfolgt, | ||
+ | wenn ein Objekt auf den Stapel gelegt wird. | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T> | ||
+ | class Stapel | ||
+ | { | ||
+ | public: | ||
+ | Stapel(int anz=3); | ||
+ | Stapel(Stapel const< | ||
+ | Stapel& operator=(Stapel const< | ||
+ | ~Stapel() { leeren(); } | ||
+ | int voll() const { return aktuell == unten+maximum; | ||
+ | int leer() const { return aktuell == unten; } | ||
+ | void | ||
+ | void | ||
+ | T const& oben() const { return *(aktuell-1); | ||
+ | T& | ||
+ | private: | ||
+ | void leeren(); | ||
+ | void kopieren(T* beginn, T* ende); | ||
+ | int maximum; | ||
+ | T* aktuell; | ||
+ | T* unten; | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | Ab dieser Stapel-Version wird die oberste Kiste | ||
+ | beim Herunternehmen nur noch vernichtet, nicht mehr zurückgeliefert. | ||
+ | Das Nachschauen und Entnehmen von Werten muss vorher durch Aufruf | ||
+ | von '' | ||
+ | Diese Änderung am Verhalten des Stapels | ||
+ | wäre für existierenden Quelltext schlichtweg eine Katastrophe! | ||
+ | Die Änderung ist notwendig, | ||
+ | weil das oberste Objekt beim Herunternehmen sonst zweimal kopiert werden muss: | ||
+ | |||
+ | * Retten in ein temporäres Objekt vor der Vernichtung unabhängig davon, ob es gebraucht wird oder nicht, | ||
+ | * Herauskopieren aus diesem temporären Objekt bei Zuweisung nach außerhalb. | ||
+ | |||
+ | Für Stapel mit großen Objekten und langsamen Kopier- und | ||
+ | Konstruktor-/ | ||
+ | |||
+ | Wiederkehrende Teile bei Kopie, Zuweisung und Abbau wurden hier in private, | ||
+ | nicht von außen nutzbare Prozeduren ausgelagert. | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T> | ||
+ | Stapel< | ||
+ | : maximum(anz), | ||
+ | aktuell( (T*) ::operator new( sizeof(T)*maximum ) ), | ||
+ | unten(aktuell) | ||
+ | { | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | Stapel< | ||
+ | : maximum(x.maximum), | ||
+ | aktuell( (T*) :: operator new( sizeof(T)*maximum) ), | ||
+ | unten(aktuell) | ||
+ | { | ||
+ | kopieren( x.unten, x.aktuell ); | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | Stapel< | ||
+ | { | ||
+ | if (this != & | ||
+ | { | ||
+ | Stapel kopie(x); | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | } | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | void Stapel< | ||
+ | { | ||
+ | while (beginn != ende) // kopiere alle gespeicherten Elemente | ||
+ | { | ||
+ | erschaffe( aktuell, *beginn ); | ||
+ | aktuell++; beginn++; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | void Stapel< | ||
+ | { | ||
+ | while (!leer()) | ||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | // Nutzung: | ||
+ | |||
+ | void stapel_demo_12() | ||
+ | { | ||
+ | Stapel< | ||
+ | |||
+ | cout << " | ||
+ | Kasten kasten1(1), kasten2(2); | ||
+ | { | ||
+ | Stapel< | ||
+ | |||
+ | std::cout << " | ||
+ | |||
+ | stapel2.drauf(kasten1); | ||
+ | stapel2.drauf(kasten2); | ||
+ | |||
+ | if (!stapel2.leer()) | ||
+ | std::cout << " | ||
+ | } | ||
+ | std::cout << " | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Wiederverwendung ===== | ||
+ | |||
+ | Der größte Teil des Stapel-Quelltextes aus dem | ||
+ | [[# | ||
+ | ist zur Speicherverwaltung notwendig. Einem Stapel sollte auch möglich sein, | ||
+ | bei Bedarf über die Anfangsgröße hinaus zu wachsen. | ||
+ | Statt dies auch noch zu implementieren, | ||
+ | die für die Haltung von Datenfeldern variabler Größer entworfen wurde | ||
+ | und zudem schon stapelähnliche Methoden (jedoch mit anderen Namen) besitzt. | ||
+ | |||
+ | Die Wiederverwendung macht den Stapel drastisch übersichtlich. | ||
+ | <code cpp> | ||
+ | # | ||
+ | |||
+ | template <class T> | ||
+ | class Stapel | ||
+ | { | ||
+ | public: | ||
+ | Stapel(int anz = 8) { stapel.reserve( anz>0 ? anz : 2 ); } | ||
+ | |||
+ | int voll() const { return stapel.size() == stapel.max_size(); | ||
+ | int leer() const { return stapel.size() == 0; } | ||
+ | void | ||
+ | { | ||
+ | std:: | ||
+ | // bei Bedarf wachsen | ||
+ | if (size == stapel.capacity()) | ||
+ | stapel.reserve( size< | ||
+ | stapel.push_back(neu); | ||
+ | } | ||
+ | void | ||
+ | T const& oben() const { return stapel.back(); | ||
+ | T& | ||
+ | private: | ||
+ | std:: | ||
+ | }; | ||
+ | |||
+ | // Nutzung: | ||
+ | |||
+ | void stapel_demo_13() | ||
+ | { | ||
+ | Stapel< | ||
+ | Stapel< | ||
+ | // ... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Vererbung ===== | ||
+ | |||
+ | Leider fordert '' | ||
+ | für seine Elemente. Kasten-Objekte lassen sich damit also nicht stapeln, | ||
+ | da deren Konstruktor die Angabe der Kastennummer erfordert. | ||
+ | |||
+ | Die Funktionalität von Objekten lässt sich durch Vererbung (Ableitung) | ||
+ | aus Basisklassen erweitern und modifizieren, | ||
+ | indem neue Funktionen hinzugefügt oder vorhandene Funktionen geändert werden. | ||
+ | Eine neue Kastenversion erhält einen Konstruktor, | ||
+ | der auf den (voreingestellten) Parameter verzichten kann. | ||
+ | |||
+ | <code cpp> | ||
+ | struct Kasten2 : public Kasten | ||
+ | { | ||
+ | Kasten2(int i = 0) : Kasten(i) {} // mit besonderen Eigenschaften | ||
+ | }; | ||
+ | |||
+ | void stapel_demo_14() | ||
+ | { | ||
+ | Stapel< | ||
+ | // ... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Die Vererbungstechnik ermöglicht objektorientierte Programmierung (OOP), | ||
+ | den Aufbau und die Gruppierung ganzer Hierarchien | ||
+ | gleichartig ansprechbarer Objektklassen (Oberbegriffe und Unterbegriffe). | ||
+ | Die OOP-Philosophie (Verallgemeinerung und Spezialisierung, | ||
+ | Ausdrücken von Gemeinsamkeiten) geht weit über das hier Zeigbare hinaus. | ||
+ | |||
+ | Objektorientierte Programmierung und generische Programmierung | ||
+ | (die Parametrisierung von Datentypen in Schablonen) | ||
+ | bieten zwei orthogonale, | ||
+ | oder auch gleichzeitig einsetzbare Möglichkeiten, | ||
+ | durch Vielgestaltigkeit (Polymorphie) | ||
+ | die Komplexität der Programmieraufgaben zu bewältigen. | ||
+ | |||
+ | ===== Facettierung ===== | ||
+ | |||
+ | Die Nutzung von '' | ||
+ | ein Container zur Datenhaltung einzusetzen. | ||
+ | Die Wahl des Containers kann dem Nutzer des Stapels überlassen werden. | ||
+ | Auch bei Definition des Stapels noch nicht gebaute, | ||
+ | nicht bekannte oder noch nicht einmal denkbare Klassen | ||
+ | können zur Implementation eingesetzt werden. | ||
+ | So könnte ein Container seine Elemente stets so sortiert halten, | ||
+ | dass Kisten mit leicht verderblicher Ware stets hinten und | ||
+ | damit oben auf dem Stapel liegen. | ||
+ | (Das entspräche statt dem Konzept eines Stapels | ||
+ | eher einer Prioritäts-Warteschlange, | ||
+ | zeigt aber die Flexibilität im Umgang mit solchen Abstraktionen.) | ||
+ | |||
+ | Das implementierte Verhalten des Containers wird zur | ||
+ | austauschbaren Facette des Stapels. Bedingung ist nur, dass dieser Container | ||
+ | |||
+ | * die entsprechende, | ||
+ | * Elemente vom Typ '' | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T, class Container> | ||
+ | class Stapel | ||
+ | { | ||
+ | public: | ||
+ | int leer() const { return stapel.empty(); | ||
+ | int voll() const { return stapel.size() == stapel.max_size(); | ||
+ | void drauf(T const& neu) { stapel.push_back(neu); | ||
+ | void runter() | ||
+ | T& | ||
+ | T const& oben() const { return stapel.back(); | ||
+ | protected: | ||
+ | Container stapel; | ||
+ | }; | ||
+ | |||
+ | // Nutzung: | ||
+ | |||
+ | # | ||
+ | # | ||
+ | # | ||
+ | |||
+ | void stapel_demo_15() | ||
+ | { | ||
+ | Stapel< | ||
+ | Stapel< | ||
+ | Stapel< | ||
+ | // ... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Fehlerbehandlung ===== | ||
+ | |||
+ | Der Nutzer des Stapel ist dafür verantwortlich, | ||
+ | keine verbotenen Aktionen mit dem Stapel anzustellen. | ||
+ | Sollte er (un)absichtlich doch | ||
+ | |||
+ | * einem leeren Stapel Elemente entnehmen oder | ||
+ | * die nicht vorhandene oberste Kiste lesen oder | ||
+ | * einen vollen Stapel zum Überlaufen bringen wollen, | ||
+ | |||
+ | gab es bisher keine Möglichkeit, | ||
+ | Der nächste Stapel wird sicherer. | ||
+ | |||
+ | C++ ist in der Lage, | ||
+ | "bei erkennbarer oder vorhersehbarer Gefahr für Leben und | ||
+ | Sicherheit des Programms oder des Rechnersystems | ||
+ | den Ausnahmezustand zu verhängen" | ||
+ | (eine Ausnahme zu werfen, engl. throw exception). | ||
+ | |||
+ | Die Implementierung des Stapels wird heimlich (privat) vererbt, | ||
+ | um Verwechslungen mit einem " | ||
+ | Die möglichen Fehler bei der Stapelei werden | ||
+ | durch öffentliche Vererbung kategorisiert. | ||
+ | Klassen(-deklarationen) werden dabei ineinander verschachtelt. | ||
+ | Ein Fehler kann gleichzeitig mehreren Kategorien angehören. | ||
+ | Dann kommt Mehrfachvererbung zum Einsatz. | ||
+ | |||
+ | <code cpp> | ||
+ | #include < | ||
+ | |||
+ | template <class T, class Container> | ||
+ | class Sicherer_Stapel : private Stapel< | ||
+ | { | ||
+ | typedef Stapel< | ||
+ | public: | ||
+ | |||
+ | // Fehlerarten, | ||
+ | |||
+ | struct Fehler {}; | ||
+ | struct Unterlauf : public Fehler {}; | ||
+ | struct Ueberlauf : public Fehler {}; | ||
+ | |||
+ | // sowohl Unterlauf als auch Denkfehler: | ||
+ | struct Unerlaubtes_Schreiben : public Unterlauf, public logic_error | ||
+ | { | ||
+ | Unerlaubtes_Schreiben() : logic_error(" | ||
+ | }; | ||
+ | struct Unerlaubtes_Lesen : public Unterlauf, public logic_error | ||
+ | { | ||
+ | Unerlaubtes_Lesen() : logic_error(" | ||
+ | }; | ||
+ | //////////////////////////////////// | ||
+ | |||
+ | void drauf(T const& neu) | ||
+ | { | ||
+ | if (voll()) throw Ueberlauf; | ||
+ | Vorfahr:: | ||
+ | } | ||
+ | |||
+ | void runter() | ||
+ | { | ||
+ | if (leer()) throw Unterlauf; | ||
+ | Vorfahr:: | ||
+ | } | ||
+ | |||
+ | T& oben() | ||
+ | { | ||
+ | if (leer()) throw Unerlaubtes_Schreiben; | ||
+ | return Vorfahr:: | ||
+ | } | ||
+ | |||
+ | T const& oben() const | ||
+ | { | ||
+ | if (leer()) throw Unerlaubtes_Lesen; | ||
+ | return Vorfahr:: | ||
+ | } | ||
+ | |||
+ | // Methodenzugriff von aussen wieder erlauben (andernfalls privat): | ||
+ | Vorfahr:: | ||
+ | Vorfahr:: | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | Mit einem solchen Stapel könnte tief in irgendeinem Programmteil versteckt | ||
+ | Folgendes angestellt werden: | ||
+ | |||
+ | <code cpp> | ||
+ | template< | ||
+ | void unsichere_Aktion(Sichere_Stapel& | ||
+ | { | ||
+ | s.oben() = kiste[1]; | ||
+ | s.runter(); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Falls der Stapel an dieser Stelle leer ist, | ||
+ | wird der normale Programmlauf übersprungen und | ||
+ | bisher genutzte Ressourcen bis zu einer Stelle abgebaut, | ||
+ | an der ein folgender Nutzer in der Lage ist, | ||
+ | den Ausnahmezustand wieder aufzuheben (engl. catch exception). | ||
+ | Unsichere Passagen müssen vor dem Versuch (engl. '' | ||
+ | Geht dann etwas schief, lassen sich vorhersehbare Ausnahmen abfangen | ||
+ | (engl. '' | ||
+ | die auf den erzeugten Fehler passt. | ||
+ | Die passende Falle kann auch eine Basisklasse der Vererbungshierarchie sein. | ||
+ | Dort besteht die Möglichkeit, | ||
+ | ihn durch erneutes Werfen einer Ausnahme weiter zu delegieren. | ||
+ | Wird der Fehler nicht behandelt, bricht das Programm mit einer Fehlermeldung ab. | ||
+ | |||
+ | <code cpp> | ||
+ | void stapel_demo_16() | ||
+ | { | ||
+ | typedef Sicherer_Stapel< | ||
+ | Mein_Stapel sicherer_stapel; | ||
+ | |||
+ | try | ||
+ | { | ||
+ | unsichere_Aktion(sicherer_stapel); | ||
+ | //... weitere Anweisungen | ||
+ | } | ||
+ | catch(Mein_Stapel:: | ||
+ | { | ||
+ | cerr << " | ||
+ | } | ||
+ | catch(logic_error& | ||
+ | { | ||
+ | cerr << "Das passiert in ordentlichen Programmen nie:" << e.what << endl; | ||
+ | } | ||
+ | catch(Mein_Stapel:: | ||
+ | { | ||
+ | cerr << "Mit dem Stapel wurde Schindluder getrieben." | ||
+ | } | ||
+ | // Jetzt gehts ordentlich weiter ... | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====== Anhang ====== | ||
+ | ===== Treiber-Demoprogramm ===== | ||
+ | |||
+ | Damit die beschriebenen Quellen getestet werden können, | ||
+ | folgt noch ein Hauptprogramm: | ||
+ | |||
+ | <code cpp> | ||
+ | int main() | ||
+ | { | ||
+ | stapel_demo_1(); | ||
+ | stapel_demo_2(); | ||
+ | stapel_demo_3(); | ||
+ | stapel_demo_4(); | ||
+ | stapel_demo_5(); | ||
+ | stapel_demo_6(); | ||
+ | stapel_demo_7(); | ||
+ | stapel_demo_8(); | ||
+ | stapel_demo_9(); | ||
+ | stapel_demo_10(); | ||
+ | stapel_demo_11(); | ||
+ | stapel_demo_12(); | ||
+ | stapel_demo_13(); | ||
+ | stapel_demo_14(); | ||
+ | stapel_demo_15(); | ||
+ | stapel_demo_16(); | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Quellen ===== | ||
+ | - Die Kunst des Hochstapelns, | ||
+ | - Bjarne Stroustrup: 16 ways to stack a cat. C++ Report, Oktober 1990. | ||
+ | - Wie funktioniert das? Der Computer. Meyers, Mannheim (1990), S. 146. | ||
+ | - Bjarne Stroustrup: Die C++ Programmiersprache. 3. Aufl., Addison-Wesley (1998). | ||
+ | - Bjarne Stroustrup: Design und Entwicklung von C++, Addison-Wesley (1994). | ||
+ | - Nicolai Josuttis: C++ Standard Bibliothek, Addison-Wesley (1996). | ||
+ | - Information Technology Standard -- Programming Language C++. ANSI/ISO 14882. Information Technology Council (NSITC), Washington, DC (1998). | ||
+ | - Brian W. Kernighan, Dennis M. Ritchie: Programming in C. 2nd edn, Prentice-Hall (1988). | ||
+ | - Bjarne Stroustrup: Der produktive Weg zu C++. 1st European Software Festival 1990, CHIP Spezial (1990), S. 38 | ||
+ | |||
+ | |||
+ | ===== Impressum ===== | ||
+ | {{ : | ||
+ | Entwurf für internes Lehrmaterial zum Sonderkurs | ||
+ | " | ||
+ | - Aufbaukurs 1999/2000 am Schülerrechenzentrum (SRZ) Dresden. | ||
+ | |||
+ | Hinweise und Kritik sind willkommen. | ||
+ | Alle Rechte (auch die auf Fehler) vorbehalten: | ||
+ | <code cpp> | ||
+ | Stapel< | ||
+ | // ... aufbauen ... 1997-10-23 | ||
+ | while (!turm.empty()) | ||
+ | turm.pop(); | ||
+ | </ | ||
+ | |||