namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


lernen:stapeln

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

lernen:stapeln [2016-12-28 14:02] (aktuell)
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>
 +const int 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"​
 +
 +const int 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(const Stapel& s);   /* noch Kisten ablegbar? ​  */
 +int    leer(const Stapel& 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(const Stapel& s)       { return s.anzahl == maximum; ​ }
 +int    leer(const Stapel& 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(const Stapel* s)       { return s->​anzahl == maximum; ​  }
 +int     ​leer(const Stapel* 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(const Stapel& s)       { return s.anzahl == maximum; ​ }
 +int    leer(const Stapel& 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]; ​ }
 +  const Kiste& 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(const Stapel& rechtswert); ​            // Kopie
 +  Stapel& operator=(const Stapel& 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; ​    }
 +  const Kiste& 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(const Stapel& 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=(const Stapel& 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(const Stapel<​T>&​ x);
 +  Stapel& operator=(const Stapel<​T>&​ x);
 +  int      voll() const        { return aktuell == unten + maximum; }
 +  int      leer() const        { return aktuell == unten; }
 +  void     ​drauf(const T& neu) { *aktuell++ = neu; }
 +  T        runter() ​           { return *--aktuell; }
 +  const T& 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(const Stapel<​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=(const Stapel<​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(const Kasten& k) : nr(k.nr)
 +            { std::cout << "> Kopie von Kasten " << nr << '​\n';​ }
 +  ~Kasten() { std::cout << "< Kasten " << nr << '​\n';​ }
 +  friend std::​ostream&​ operator<<​ (std::​ostream&​ os, const Kasten& k);
 +  friend int operator== (const Kasten& x,  const Kasten& y);
 +  friend int operator< ​ (const Kasten& x,  const Kasten& y);
 +private:
 +  int nr;
 +};
 +
 +// Dateiausgabe
 +std::​ostream&​ operator<<​ (std::​ostream&​ os, const Kasten& k) 
 +{
 +  return os << k.nr; 
 +}
 +
 +// Vergleiche
 +int operator== (const Kasten& x, const Kasten& y) { return x.nr==y.nr; }
 +int operator< ​ (const Kasten& x, const Kasten& 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, const T2& 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(const Stapel<​T>&​ x);
 +  Stapel& operator=(const Stapel<​T>&​ x);
 +  ~Stapel() { leeren(); }
 +  int      voll() const        { return aktuell == unten+maximum;​ }
 +  int      leer() const        { return aktuell == unten; }
 +  void     ​drauf(const T& neu) { erschaffe(aktuell,​ neu); ++aktuell; }
 +  void     ​runter() ​           { --aktuell; vernichte(aktuell);​ }
 +  const T& 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(const Stapel<​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=(const Stapel<​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(const T& 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(); ​ }
 +  const T& 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(const T& neu) { stapel.push_back(neu);​ }
 +  void runter() ​           { stapel.pop_back(); ​    }
 +  T& ​      ​oben() ​         { return stapel.back(); ​ }
 +  const T& 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(const T& 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();​
 +  }
 +
 +  const T& 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>​
 +
  
lernen/stapeln.txt · Zuletzt geändert: 2016-12-28 14:02 (Externe Bearbeitung)