namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


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: Stapel. 
 +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, modular, objektbasiert, objektorientiert, typunabhängig) 
 +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" (Quelltexten) erreichbar:
 +
 +> Wir brauchen Intelligenz, Erfahrung und die am wenigsten messbare Eigenschaft qualifizierter Arbeit: Geschmack. [9] 
 +
 +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 ? =====
 +
 +<file>
 +Stapel
 +
 +- ist voll ->   .....  Obergrenze
 +                .   .
 +                .       +---+
 +                .    <- |   | Kiste draufsetzen
 +- waechst       . ^ .     +---+
 +                . | .
 +- schrumpft     . v .     +---+
 +                .    -> |     Kiste herunternehmen
 +                .       +---+
 +                +---+
 +                | 3 |   -> oberste Kiste (aufmachen)
 +                +---+
 +                | 2 |
 +                +---+
 +                | 1 |
 +- ist leer ->   +---+  Untergrenze
 +</file>
 +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 "unmögliche" Dinge zu tun: 
 +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, nicht kontrollierbares Programmverhalten, 
 +Datenverlust und daraus folgende Schäden, Verletzung von Schutzmechanismen etc.
 +
 +Die "sichere" Implementierung einer allgemeinen Idee 
 +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, z.B. durch Definitionen wie
 +
 +<code cpp>
 +#define C 3                     /* aller guten Dinge sind drei   */
 +#define Kiste int               /* wir reden nur noch von Kisten */
 +Kiste   kiste[] = { 1,2,3,4 };  // das soll reichen              
 +</code>
 +
 +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];          // max. C Kisten 
 +int   anzahl = 0;               // zu Beginn ist Stapel leer
 +</code>
 +
 +Nun wird mit den Daten munter gearbeitet:
 +
 +<code cpp>
 +#include <iostream>
 +
 +void stapel_demo_1()
 +{
 +  std::cout << "\nAlle Kisten auf den Stapel   :    ";
 +
 +  int i = 0;
 +  while (i < C && anzahl < maximum)        // Stapel nicht voll
 +  {
 +    stapel[anzahl++] = kiste[i++];
 +    std::cout << stapel[anzahl-1] << ' ';  // oberste Kiste
 +  }
 +  if (anzahl > 0)                          // Stapel nicht leer
 +  {
 +    std::cout << "\nInhalt der obersten Kiste aendern von " << stapel[anzahl-1];
 +    stapel[anzahl-1] = kiste[C];           // auf Stapel legen
 +    std::cout << " nach " << stapel[anzahl-1];
 +  }
 +  std::cout << "\nAlle Kisten vom Stapel nehmen:    ";
 +
 +  while (anzahl > 0)                       // Stapel nicht leer 
 +    std::cout << stapel[--anzahl] << ' ';  // vom Stapel nehmen
 +  std::cout << '\n';
 +}
 +</code>
 +
 +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 ''anzahl++'' zum Erhöhen des Zählers das Doppelplus hinten steht, 
 +beim Herunterzählen in ''%%--anzahl%%'' jedoch vorn. 
 +((C-Programmierer kennen den Unterschied.)) 
 +Und wehe, ein Programmierer vergisst einmal, 
 +dass das letzte belegte Element im Stapel das mit dem Index ''anzahl-1'' 
 +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:((Werte vom Typ int werden in der Sprache C 
 +als Wahrheitswerte verwendet - Null als falsch, alle anderen als wahr. 
 +C-Programmierer können vielfältig "ja" sagen, 
 +aber nur auf eine Weise "nein". In Standard C++ kann dafür der Typ ''bool'' 
 +mit den Werten true und false genutzt werden.))
 +
 +<code cpp>
 +int    voll();                  /* noch Kisten ablegbar?   */
 +int    leer();                  /* noch Kisten entnehmbar? */
 +void   drauf(Kiste neu);
 +Kiste  runter();
 +Kiste* oben();                  /* nachschauen, evtl. neuen Wert zuweisen */
 +</code>
 +
 +Alle Aktionen greifen auf einen, denselben, Stapel von Kisten zu. 
 +Sind sie einmal durch
 +
 +<code cpp>
 +int    voll()           { return anzahl == maximum; }
 +int    leer()           { return anzahl == 0;       }
 +void   drauf(Kiste neu) { stapel[anzahl++] = neu;   }
 +Kiste  runter()         { return stapel[--anzahl];  }
 +Kiste* oben()           { return &stapel[anzahl-1]; }
 +</code>
 +
 +definiert (unter Nutzung der globalen Variablen aus dem 
 +[[#strukturierte_programmierung|strukturierten Programm]]), 
 +ist ihre Verwendung einleuchtend:
 +
 +<code cpp>
 +void stapel_demo_2()
 +{
 +  std::cout << "\nAlle Kisten auf den Stapel   :    ";
 +
 +  int i = 0;
 +  while (i < C && !voll())
 +  {
 +    drauf( kiste[i++] );
 +    std::cout << *oben() << ' ';
 +  }
 +  if (!leer())
 +  {
 +    std::cout << "\nInhalt der obersten Kiste aendern von " << *oben();
 +    *oben() = kiste[C];
 +    std::cout << " nach " << *oben();
 +  }
 +  cout << "\nAlle Kisten vom Stapel nehmen:    ";
 +
 +  while (!leer())
 +    std::cout << runter() << ' ';
 +
 +  std::cout << '\n';
 +}
 +</code>
 +
 +Der Ausdruck ''*oben() = kiste[C]'' zeigt, dass auch zusammengesetzte, 
 +komplizierte Ausdrücke auf der linken Seite einer Zuweisung 
 +(anstelle einer Variable) stehen dürfen, 
 +sofern ihr Wert eine Speicheradresse (Linkswert, "lvalue"
 +bildet.((Hier wird die Adresse mittels eines von der Funktion ''oben()'' 
 +gelieferten Zeigers ermittelt, aber dies ist ein Implementierungsdetail.))
 +
 +Einschränkungen:
 +
 +  *  Der Funktionsaufruf und die Wertübergabe kosten Zeit, so dass Programmierer, für deren Programmieraufgabe der Zeitfaktor entscheidend ist, versuchen werden, an den Stapelfunktionen vorbei direkt auf das Stapelfeld zuzugreifen, womit sich Fehler von außen einschleichen können (und werden). Dies ist möglich, da die Implementierung des Stapels offenliegt.
 +  *  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 "stapel.h":
 +#ifndef __STAPEL__
 +#define __STAPEL__
 +int    voll();                  /* noch Kisten ablegbar?   */
 +int    leer();                  /* noch Kisten entnehmbar? */
 +void   drauf(Kiste neu);
 +Kiste  runter();
 +Kiste* oben();                  /* nachschauen, evtl. neuen Wert zuweisen */
 +#endif // __STAPEL__
 +
 +// Datei "stapel.c":
 +#include "stapel.h"
 +
 +int const maximum = C;
 +static Kiste stapel[maximum];
 +static int   anzahl = 0;
 +
 +int    voll()           { return anzahl == maximum; }
 +int    leer()           { return anzahl == 0;       }
 +void   drauf(Kiste neu) { stapel[anzahl++] = neu;   }
 +Kiste  runter()         { return stapel[--anzahl];  }
 +Kiste* oben()           { return &stapel[anzahl-1]; }
 +</code>
 +
 +Die ''static''-Deklaration der Stapel-Variablen 
 +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 ''"stapel.h"'' 
 +kann auf den Stapel von jedem beliebigen Teilprogramm zugegriffen werden. 
 +Die nutzbare deklarierte Schnittstelle bleibt unverändert.
 +
 +<code cpp>
 +// andere Datei :
 +#include "stapel.h"
 +
 +void stapel_demo_3()    // ohne Ausgabe, sonst wie stapel_demo_1
 +{
 +  int i = 0;
 +  while (i<3 && !voll())
 +    drauf( kiste[i++] );
 +  if (!leer())
 +    *oben() = kiste[3];
 +  while (!leer())
 +    runter();
 +}
 +</code>
 +
 +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   drauf(Stapel& s, Kiste neu);
 +Kiste  runter(Stapel& s);
 +Kiste& oben(Stapel& s);         /* nachschauen, evtl. neuen Wert zuweisen */
 +void   neu(Stapel& s);
 +</code>
 +
 +Hinzu muss eine neue Funktion kommen, die sicherstellt, dass die Kistenanzahl 
 +(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   drauf(Stapel& s, Kiste neu) { s.stapel[s.anzahl++] = neu;  }
 +Kiste  runter(Stapel& s)           { return s.stapel[--s.anzahl]; }
 +Kiste& oben(Stapel& s)             { return s.stapel[s.anzahl-1]; }
 +void   neu(Stapel& s)              { s.anzahl = 0; }
 +
 +// Nutzung :
 +void stapel_demo_4()
 +{
 +  std::cout << "Mehrere Stapel arbeiten gleichzeitig: ";
 +
 +  Stapel stapel1, stapel2;
 +  neu(stapel1);
 +  neu(stapel2);
 +
 +  int i = 0;
 +  while (i<3 && !voll(stapel1))
 +    drauf(stapel1, kiste[i++]);
 +  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 << '\n';
 +}
 +</code>
 +
 +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 [[#prozedurale_programmierung|prozedurales Programm]] zur Umgehung der Stapelfunktionen ein. 
 +
 +===== 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;                  // Definition folgt (irgendwann)
 +// ... Deklaration nutzbarer Funktionen
 +
 +// Implementierung :
 +struct Stapel 
 +{
 +  int anzahl;
 +  Kiste stapel[maximum];
 +};
 +
 +int     voll(Stapel const* s)       { return s->anzahl == maximum;   }
 +int     leer(Stapel const* s)       { return s->anzahl == 0;         }
 +void    drauf(Stapel* s, Kiste neu) { s->stapel[s->anzahl++] = neu;  }
 +Kiste   runter(Stapel* s)           { return s->stapel[--s->anzahl]; }
 +Kiste&  oben(Stapel* s)             { return s->stapel[s->anzahl-1]; }
 +
 +Stapel* erzeugen() 
 +{            
 +  Stapel *s = new Stapel; s->anzahl = 0;
 +  return s;
 +}
 +
 +void beenden(Stapel* alt) { delete alt; }
 +</code>
 +
 +Eine Struktur kann im Ganzen kopiert und zugewiesen werden, 
 +wie im nächsten Beispiel:
 +
 +<code cpp>
 +void stapel_demo_5()
 +{
 +  std::cout << "Stapel als opaker Typ: ";
 +  Stapel* stapel1 = erzeugen(); // dynamischen Speicher anfordern
 +  Stapel* stapel2 = erzeugen();
 +  int i = 0;
 +  while (i<3 && !voll(stapel1))
 +    drauf(stapel1, kiste[i++]);
 +  *stapel2 = *stapel1;          // Kopie des gesamten Stapels merken!
 +  while (!leer(stapel1)) runter(stapel1);
 +
 +  std::cout << "\nKopie des alten Stapels: ";
 +  while (!leer(stapel2))
 +    std::cout << runter(stapel2) << ' ';
 +  std::cout << '\n';
 +  beenden(stapel1);             // dynamischen Speicher freigeben
 +  beenden(stapel2);
 +  stapel1 = stapel2 = 0;        // Zeiger als leer markieren (?)
 +}
 +</code>
 +
 +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, Resourcenbereitstellung und -freigabe 
 +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();                     // Konstruktor
 +  ~Stapel();                    // Destruktor
 +  int anzahl;
 +  Kiste stapel[maximum];
 +};
 +
 +// Implementierung :
 +
 +Stapel::Stapel() : anzahl(0) { /* Ressourcen belegen    */ }
 +Stapel::~Stapel()            { /* Ressourcen bereinigen */ }
 +
 +</code>
 +
 +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 "Gegenteil"
 +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   drauf(Stapel& s, Kiste neu) { s.stapel[s.anzahl++] = neu;  }
 +Kiste  runter(Stapel& s)           { return s.stapel[--s.anzahl]; }
 +Kiste& oben(Stapel& s)             { return s.stapel[s.anzahl-1]; }
 +
 +// Nutzung:
 +
 +void stapel_demo_6()
 +{
 +  std::cout << "Stapel mit Konstruktor: ";
 +  Stapel stapel1, stapel2;      // Konstruktoren werden hier aufgerufen
 +
 +  int i = 0;
 +  while (i<3 && !voll(stapel1))
 +    drauf(stapel1, kiste[i++]);
 +
 +  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 << '\n';
 +}                               // Destruktoraufruf beim Verlassen des Blocks
 +</code>
 +
 +===== 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   drauf(Kiste neu);
 +  Kiste  runter();
 +  Kiste& oben();
 +
 +  int anzahl;
 +  Kiste stapel[maximum];
 +};
 +
 +// Implementierung :
 +
 +Stapel::Stapel() : anzahl(0) { }
 +
 +int    Stapel::voll()           { return anzahl == maximum; }
 +int    Stapel::leer()           { return anzahl == 0;       }
 +void   Stapel::drauf(Kiste neu) { stapel[anzahl++] = neu;   }
 +Kiste  Stapel::runter()         { return stapel[--anzahl];  }
 +Kiste& Stapel::oben()           { return stapel[anzahl-1];  }
 +</code>
 +
 +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, an sich selbst Aktionen auszuführen. 
 +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 als Objekt mit Methoden: ";
 +
 +  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 << '\n';
 +}
 +</code>
 +
 +===== Rumpfersetzung (Inlining) =====
 +
 +Die Effizienz der Ausführung war ein wichtiges Entwurfskriterium 
 +bei der Entwicklung von C zu C++ [5]. 
 +Die "Strafe" für die Anwendung des Objektkonzeptes sollte möglichst gering sein 
 +---- 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 ''inline'' deklariert werden. 
 +Die Definition von ''inline''-Funktionsrümpfen muss in der Header-Datei erfolgen. 
 +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 ''inline''.
 +
 +<code cpp>
 +struct Stapel 
 +{
 +  Stapel();
 +
 +  int    voll()           { return anzahl == maximum; }
 +  int    leer()           { return anzahl == 0;       }
 +  void   drauf(Kiste neu) { stapel[anzahl++] = neu;   }
 +  Kiste  runter()         { return stapel[--anzahl];  }
 +  Kiste& oben()           { return stapel[anzahl-1];  }
 +
 +  int anzahl;
 +  Kiste stapel[maximum];
 +};
 +
 +inline Stapel::Stapel() : anzahl(0) { } // eine mal so
 +</code>
 +
 +''inline''-Funktionen sind mehr als ein Ersatz für C-Präprozessor-Makros. 
 +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;
 +  //...
 +}
 +</code>
 +
 +===== 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 (''class'') ist eine Struktur 
 +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 ''const'' deklariert werden (Lesemethoden). 
 +Lesemethoden dürfen dann keine Bestandteile der Struktur ändern. 
 +Manche Methoden wie ''oben()'' müssen dann 
 +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         drauf(Kiste neu) { stapel[anzahl++] = neu;   }
 +  Kiste        runter()         { return stapel[--anzahl];  }
 +  Kiste const& oben() const     { return stapel[anzahl-1];  } // lesen
 +  Kiste&       oben()           { return stapel[anzahl-1];  } // schreiben
 +private:
 +  int anzahl;
 +  Kiste stapel[maximum];
 +};
 +</code>
 +
 +Die Nutzung bleibt gleich:
 +
 +<code cpp>
 +void stapel_demo_9() // wie stapel_demo_7
 +{
 +  Stapel stapel;
 +  // ...
 +}
 +</code>
 +
 +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 ''const'' gekennzeichneten Objekten 
 +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), aktuell(new Kiste[maximum]), unten(aktuell) {}
 +  ~Stapel() { delete[] unten; }
 +  Stapel(Stapel const& rechtswert);             // Kopie
 +  Stapel& operator=(Stapel const& rechtswert);  // Zuweisung
 +  int          voll() const     { return aktuell == unten+maximum; }
 +  int          leer() const     { return aktuell == unten; }
 +  void         drauf(Kiste neu) { *aktuell++ = neu;      }
 +  Kiste        runter()         { return *--aktuell;     }
 +  Kiste const& oben() const     { return *(aktuell-1);   }
 +  Kiste&       oben()           { return *(aktuell-1);   }
 +private:
 +  int maximum;
 +  Kiste *aktuell;
 +  Kiste *unten;
 +};
 +</code>
 +
 +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::Stapel(Stapel const& x)
 +  : maximum(x.maximum), aktuell(new Kiste[maximum]), unten(aktuell)
 +{
 +  Kiste *quelle = x.unten;
 +  while (quelle != x.aktuell)    // kopiere alle gespeicherten Elemente
 +    *aktuell++ = *quelle++;
 +}
 +
 +Stapel& Stapel::operator=(Stapel const& x)
 +{
 +  if (this != &x)                // verhindert Selbstzuweisung
 +  {
 +    Stapel kopie(x);              
 +    std::swap(maximum, x.maximum);
 +    std::swap(unten, x.unten);
 +    std::swap(aktuell, x.aktuell);
 +  }
 +  return *this;
 +}
 +
 +// Nutzung :
 +void stapel_demo_10()
 +{
 +  Stapel stapel, stapel2(10);
 +  //...
 +  stapel = stapel2;      // Zuweisung
 +  stapel = Stapel(1000); // Zuweisung von zeitweiligem Objekt
 +  //...
 +}
 +</code>
 +
 +===== 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 };
 +</code>
 +
 +Dazu wird der Stapel als Schablone (engl. template) definiert, 
 +die für jeden Typ ''T'' von stapelbaren Objekten verwendet werden kann.
 +
 +<code cpp>
 +template <class T>
 +class Stapel 
 +{
 +public:
 +  Stapel(int anz = 3)
 +  : maximum(anz), aktuell(new T[maximum]), unten(aktuell) {}
 +  ~Stapel() { delete[] unten; }
 +  Stapel(Stapel const<T>& x);
 +  Stapel& operator=(Stapel const<T>& x);
 +  int      voll() const        { return aktuell == unten + maximum; }
 +  int      leer() const        { return aktuell == unten; }
 +  void     drauf(T const& neu) { *aktuell++ = neu; }
 +  T        runter()            { return *--aktuell; }
 +  T const& oben() const        { return *(aktuell-1); }
 +  T&       oben()              { return *(aktuell-1); }
 +private:
 +  int maximum;
 +  T *aktuell;
 +  T *unten;
 +};
 +</code>
 +
 +Alle Funktionen müssen bei Schablonen im Header stehen, 
 +damit ihr Code für beliebige Stapelobjekte generiert werden kann, 
 +auch die nicht ''inline'' implementierten:
 +
 +<code cpp>
 +template <class T>
 +Stapel<T>::Stapel(Stapel const<T>& x)
 +  : maximum(x.maximum), aktuell(new T[maximum]), unten(aktuell)
 +{
 +  T *quelle = x.unten;
 +  while (quelle != x.aktuell)   // kopiere alle gespeicherten Elemente
 +    *aktuell++ = *quelle++;
 +}
 +
 +template <class T>
 +Stapel<T>& Stapel<T>::operator=(Stapel const<T>& x)
 +{
 +  if (this != &x)               // verhindert Selbstzuweisung
 +  { 
 +    Stapel kopie(x);              
 +    std::swap(maximum, x.maximum);
 +    std::swap(unten, x.unten);
 +    std::swap(aktuell, x.aktuell);
 +  }
 +  return *this;
 +}
 +</code>
 +
 +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<Kiste> stapel;
 +  Stapel<Fass>  stapel2(10);
 +  //...
 +}
 +</code>
 +
 +===== 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 << '\n'; }
 +  Kasten(Kasten const& k) : nr(k.nr)
 +            { std::cout << "> Kopie von Kasten " << nr << '\n'; }
 +  ~Kasten() { std::cout << "< Kasten " << nr << '\n'; }
 +  friend std::ostream& operator<< (std::ostream& os, Kasten const& k);
 +  friend int operator== (Kasten const& x,  Kasten const& y);
 +  friend int operator<  (Kasten const& x,  Kasten const& y);
 +private:
 +  int nr;
 +};
 +
 +// Dateiausgabe
 +std::ostream& operator<< (std::ostream& os, Kasten const& k) 
 +{
 +  return os << k.nr; 
 +}
 +
 +// Vergleiche
 +int operator== (Kasten const& x, Kasten const& y) { return x.nr==y.nr; }
 +int operator<  (Kasten const& x, Kasten const& y) { return x.nr< y.nr; }
 +</code>
 +
 +Freunde (engl. ''friend'') einer Klasse haben Zugriff auf private Elemente.
 +
 +Objekte lassen sich mit der Plazierungssyntax des ''new''-Operators 
 +an beliebiger Stelle im Speicher erzeugen und vernichten:
 +
 +<code cpp>
 +#include<memory> // wegen void* operator new(size_t, void* p) { return p; }
 +
 +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->~T();      // expliziter Aufruf des Destruktors ohne Speicherfreigabe
 +}
 +</code>
 +
 +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 "hochoptimierter Code" benötigt:
 +
 +<code cpp>
 +inline void vernichte(int* )    { /* tue nichts */ }
 +inline void vernichte(double* ) { /* tue nichts */ }
 +</code>
 +
 +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<T>& x);
 +  Stapel& operator=(Stapel const<T>& x);
 +  ~Stapel() { leeren(); }
 +  int      voll() const        { return aktuell == unten+maximum; }
 +  int      leer() const        { return aktuell == unten; }
 +  void     drauf(T const& neu) { erschaffe(aktuell, neu); ++aktuell; }
 +  void     runter()            { --aktuell; vernichte(aktuell); }
 +  T const& oben() const        { return *(aktuell-1); }
 +  T&       oben()              { return *(aktuell-1); }
 +private:
 +  void leeren();
 +  void kopieren(T* beginn, T* ende);
 +  int maximum;
 +  T* aktuell;
 +  T* unten;
 +};
 +</code>
 +
 +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 ''oben()'' erfolgen. 
 +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-/Destruktoroperationen wäre das Laufzeitverhalten schlicht untragbar.
 +
 +Wiederkehrende Teile bei Kopie, Zuweisung und Abbau wurden hier in private, 
 +nicht von außen nutzbare Prozeduren ausgelagert.
 +
 +<code cpp>
 +template <class T>
 +Stapel<T>::Stapel(int anz)
 +  : maximum(anz),
 +    aktuell( (T*) ::operator new( sizeof(T)*maximum ) ),
 +    unten(aktuell)
 +{
 +}
 +
 +template <class T>
 +Stapel<T>::Stapel(Stapel const<T>& x)
 +  : maximum(x.maximum),
 +    aktuell( (T*) :: operator new( sizeof(T)*maximum) ),
 +    unten(aktuell)
 +{
 +  kopieren( x.unten, x.aktuell );
 +}
 +
 +template <class T>
 +Stapel<T>& Stapel<T>::operator=(Stapel const<T>& x)
 +{
 +  if (this != &x)              // verhindert Selbstzuweisung
 +  { 
 +    Stapel kopie(x);              
 +    std::swap(maximum, x.maximum);
 +    std::swap(unten, x.unten);
 +    std::swap(aktuell, x.aktuell);
 +  }
 +  return *this;
 +}
 +
 +template <class T>
 +void Stapel<T>::kopieren(T* beginn, T* ende)
 +{
 +  while (beginn != ende) // kopiere alle gespeicherten Elemente
 +  {
 +    erschaffe( aktuell, *beginn );
 +    aktuell++; beginn++;
 +  }
 +}
 +
 +template <class T>
 +void Stapel<T>::leeren()
 +{
 +   while (!leer())
 +     runter();
 +   delete( (char*) unten );
 +}
 +
 +// Nutzung:
 +
 +void stapel_demo_12()
 +{
 +  Stapel<Kiste> stapel;
 +
 +  cout << "Kasten neu erschaffen:\n";
 +  Kasten kasten1(1), kasten2(2);
 +  {
 +    Stapel<Kasten> stapel2(10);
 +
 +    std::cout << "Stapel fuellen mit Kopien von zwischenzeitlichen Kasten:\n";
 +
 +    stapel2.drauf(kasten1);
 +    stapel2.drauf(kasten2);
 +
 +    if (!stapel2.leer())
 +      std::cout << "Obendrauf ist Kasten " << stapel2.oben() << '\n';
 +  }
 +  std::cout << "Stapel leer.\n";
 +}
 +</code>
 +
 +===== Wiederverwendung =====
 +
 +Der größte Teil des Stapel-Quelltextes aus dem 
 +[[#erschaffen_und_vernichten|vorigen Abschnitt]] 
 +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, verwenden wir eine Containerklasse, 
 +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>
 +#include<vector>
 +
 +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     drauf(T const& neu) 
 +  {
 +    std::vector<T>::size_type size=stapel.size();
 +    // bei Bedarf wachsen
 +    if (size == stapel.capacity())
 +      stapel.reserve( size<1000? 2*size : size+1000 );
 +    stapel.push_back(neu);
 +  }
 +  void     runter()            { stapel.pop_back();  }
 +  T const& oben() const        { return stapel.back();  }
 +  T&       oben()              { return stapel.back();  }
 +private:
 +  std::vector<T> stapel;
 +};
 +
 +// Nutzung:
 +
 +void stapel_demo_13()
 +{
 +  Stapel<Kiste> stapel;
 +  Stapel<Fass>  Christos_Wand(13000);
 +  // ...
 +}
 +</code>
 +
 +===== Vererbung =====
 +
 +Leider fordert ''std::vector<T>'' einen parameterlosen (Default-)Konstruktor 
 +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 ist ein Kasten
 +{
 +  Kasten2(int i = 0) : Kasten(i) {}     // mit besonderen Eigenschaften
 +};
 +
 +void stapel_demo_14()
 +{
 +  Stapel<Kasten2> stapel;
 +  // ...
 +}
 +</code>
 +
 +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, unabhängig voneinander 
 +oder auch gleichzeitig einsetzbare Möglichkeiten, 
 +durch Vielgestaltigkeit (Polymorphie) 
 +die Komplexität der Programmieraufgaben zu bewältigen.
 +
 +===== Facettierung =====
 +
 +Die Nutzung von ''std::vector<T>'' ist nicht die einzige Möglichkeit, 
 +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, hier benutzte Schnittstelle aufweist und
 +  *  Elemente vom Typ ''T'' speichert.
 +
 +<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()            { stapel.pop_back();     }
 +  T&       oben()          { return stapel.back();  }
 +  T const& oben() const    { return stapel.back();  }
 +protected:
 +  Container stapel;
 +};
 +
 +// Nutzung:
 +
 +#include<vector>
 +#include<deque>
 +#include<list>
 +
 +void stapel_demo_15()
 +{
 +  Stapel<Kiste,   vector<Kiste> > stapel1;
 +  Stapel<Fass,    deque<Fass>   > stapel2;
 +  Stapel<Kasten2, list<Kasten2> > stapel3;
 +  // ...
 +}
 +</code>
 +
 +===== 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, ihn daran zu hindern. 
 +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 "unsicheren" Stapel auszuschließen. 
 +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 <stdexcept>                    // wegen logic_error
 +
 +template <class T, class Container>
 +class Sicherer_Stapel : private Stapel<T, Container> 
 +{
 +  typedef Stapel<T, Container> Vorfahr; // weniger Schreibarbeit
 +public:
 +
 +  // Fehlerarten, hierarisch geordnet:
 +
 +    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("Schreiben auf leeren Stapel") {}
 +    };
 +    struct Unerlaubtes_Lesen : public Unterlauf, public logic_error 
 +    {
 +      Unerlaubtes_Lesen() : logic_error("Lesen vom leeren Stapel") {}
 +    };
 +  ////////////////////////////////////
 +
 +  void drauf(T const& neu)
 +  { 
 +    if (voll()) throw Ueberlauf;  // So geht's nicht weiter!
 +    Vorfahr::drauf(neu);
 +  }
 +
 +  void runter()
 +  {
 +    if (leer()) throw Unterlauf;  // C++ beschliesst Ausnahmezustand
 +    Vorfahr::runter();
 +  }
 +
 +  T& oben()
 +  {
 +    if (leer()) throw Unerlaubtes_Schreiben; // Programmteil wird verlassen
 +    return Vorfahr::oben();
 +  }
 +
 +  T const& oben() const
 +  {
 +    if (leer()) throw Unerlaubtes_Lesen;
 +    return Vorfahr::oben();       // nachfolgende Aktionen werden ignoriert
 +  }
 +
 +  // Methodenzugriff von aussen wieder erlauben (andernfalls privat):
 +  Vorfahr::leer;
 +  Vorfahr::voll;
 +};
 +</code>
 +
 +Mit einem solchen Stapel könnte tief in irgendeinem Programmteil versteckt
 +Folgendes angestellt werden:
 +
 +<code cpp>
 +template<class Sichere_Stapel>
 +void unsichere_Aktion(Sichere_Stapel& s)
 +{
 +  s.oben() = kiste[1];          // Sorglos!
 +  s.runter();                   // Nicht getestet! Quellen nicht gelesen?
 +}
 +</code>
 +
 +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. ''try'') gesichert werden. 
 +Geht dann etwas schief, lassen sich vorhersehbare Ausnahmen abfangen 
 +(engl. ''catch''). Bei Fehlern schnappt die erste Falle zu, 
 +die auf den erzeugten Fehler passt. 
 +Die passende Falle kann auch eine Basisklasse der Vererbungshierarchie sein. 
 +Dort besteht die Möglichkeit, auf den Fehler angemessen zu reagieren oder 
 +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<Kiste, std::vector<Kiste> > Mein_Stapel;
 +  Mein_Stapel sicherer_stapel; // (denkste!)
 +
 +  try 
 +  {
 +    unsichere_Aktion(sicherer_stapel);
 +    //... weitere Anweisungen
 +  }
 +  catch(Mein_Stapel::Unerlaubtes_Schreiben) 
 +  {
 +    cerr << "Unerlaubter Schreibzugriff auf Stapel" << endl;
 +  }
 +  catch(logic_error& e) 
 +  {
 +    cerr << "Das passiert in ordentlichen Programmen nie:" << e.what << endl;
 +  }
 +  catch(Mein_Stapel::Fehler) 
 +  {
 +    cerr << "Mit dem Stapel wurde Schindluder getrieben." << endl;
 +  }
 +  // Jetzt gehts ordentlich weiter ...
 +}
 +</code>
 +
 +====== 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;
 +}
 +</code>
 +
 +===== Quellen =====
 +  - Die Kunst des Hochstapelns, Unicum Hochschulmagazin 17 (1999) 6, S. 43.
 +  - 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 =====
 +{{ :lernen:stapeln.jpg|Abb.2: umwerfend}} 
 +Entwurf für internes Lehrmaterial zum Sonderkurs 
 +"Programmieren mit Standard C++" 
 +- Aufbaukurs 1999/2000 am Schülerrechenzentrum (SRZ) Dresden.
 +
 +Hinweise und Kritik sind willkommen. 
 +Alle Rechte (auch die auf Fehler) vorbehalten:  R. Richter, Juli 1999.
 +<code cpp>
 +Stapel<Bauklotz> turm; 
 +// ... aufbauen ... 1997-10-23
 +while (!turm.empty())
 +  turm.pop();
 +</code>
 +
  

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki