namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


lernen:stapeln

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 ?

Stapel

- ist voll ->   .....  Obergrenze
                .   .
                .   .     +---+
                .   .  <- |   | Kiste draufsetzen
- waechst       . ^ .     +---+
                . | .
- schrumpft     . v .     +---+
                .   .  -> |   |   Kiste herunternehmen
                .   .     +---+
                +---+
                | 3 |   -> oberste Kiste (aufmachen)
                +---+
                | 2 |
                +---+
                | 1 |
- ist leer ->   +---+  Untergrenze

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

#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              

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.

const int maximum = C;
Kiste stapel[maximum];          // max. C Kisten 
int   anzahl = 0;               // zu Beginn ist Stapel leer

Nun wird mit den Daten munter gearbeitet:

#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';
}

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. 1) Und wehe, ein Programmierer vergisst einmal, dass das letzte belegte Element im Stapel das mit dem Index anzahl-1 ist.2)

Prozedurale Programmierung

Jede Aktion mit dem Stapel lässt sich in einer Funktion unterbringen:3)

int    voll();                  /* noch Kisten ablegbar?   */
int    leer();                  /* noch Kisten entnehmbar? */
void   drauf(Kiste neu);
Kiste  runter();
Kiste* oben();                  /* nachschauen, evtl. neuen Wert zuweisen */

Alle Aktionen greifen auf einen, denselben, Stapel von Kisten zu. Sind sie einmal durch

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]; }

definiert (unter Nutzung der globalen Variablen aus dem strukturierten Programm), ist ihre Verwendung einleuchtend:

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';
}

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.4)

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.

// 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]; }

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.

// 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();
}

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.

// 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);

Hinzu muss eine neue Funktion kommen, die sicherstellt, dass die Kistenanzahl (der Zähler) des Stapels am Anfang wirklich auf Null steht.

// 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';
}

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 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.

// 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; }

Eine Struktur kann im Ganzen kopiert und zugewiesen werden, wie im nächsten Beispiel:

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 (?)
}

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.

struct Stapel 
{
  Stapel();                     // Konstruktor
  ~Stapel();                    // Destruktor
  int anzahl;
  Kiste stapel[maximum];
};
 
// Implementierung :
 
Stapel::Stapel() : anzahl(0) { /* Ressourcen belegen    */ }
Stapel::~Stapel()            { /* Ressourcen bereinigen */ }

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.

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

Objektbasierte Programmierung

Wenn es schon Start- und Aufräumroutinen gibt, können auch andere Funktionen als Methoden (member functions) in den Stapel integriert werden.5)

// 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];  }

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.

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';
}

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.

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

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:

void stapel_demo_8() // wie stapel_demo_7
{
  Stapel stapel;
  //...
}

Schutzmechanismen

Die Komponenten einer Struktur sind solange öffentlich, wie nichts anderes angegeben wird. Dies kann ihre Datenintegrität gefährden (Manipulation an den Methoden vorbei!) und in der Folge Fehlverhalten hervorrufen.

Der Zugriff auf Teile einer Struktur lässt sich durch die Kennzeichnung privater und öffentlicher Abschnitte eingeschränken (Kapselung). Eine Klasse (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).

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];
};

Die Nutzung bleibt gleich:

void stapel_demo_9() // wie stapel_demo_7
{
  Stapel stapel;
  // ...
}

Der Compiler setzt sowohl die Zugriffskontrolle als auch die Prüfung auf Konstantheit so streng wie möglich durch. Der Aufruf nicht-öffentlicher Funktionen von außerhalb der Klasse wird vom Compiler verweigert. Ebenso dürfen bei als 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.

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;
};

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:

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
  //...
}

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):

#define Fass float
Fass fass[] = { 1, 2, 3, 4 };

Dazu wird der Stapel als Schablone (engl. template) definiert, die für jeden Typ T von stapelbaren Objekten verwendet werden kann.

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;
};

Alle Funktionen müssen bei Schablonen im Header stehen, damit ihr Code für beliebige Stapelobjekte generiert werden kann, auch die nicht inline implementierten:

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;
}

Um die Schablone zu nutzen, muss die Stapeldefinition in spitzen Klammern den Typ der Stapelobjekte festlegen. Mehr ändert sich aber nicht:

void stapel_demo_11()
{
  Stapel<Kiste> stapel;
  Stapel<Fass>  stapel2(10);
  //...
}

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

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; }

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:

#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
}

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:

inline void vernichte(int* )    { /* tue nichts */ }
inline void vernichte(double* ) { /* tue nichts */ }

Nun lässt sich ein Stapel so bauen, dass nur dann ein Konstruktoraufruf auf der Stapelspitze erfolgt, wenn ein Objekt auf den Stapel gelegt wird.

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;
};

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.

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";
}

Wiederverwendung

Der größte Teil des Stapel-Quelltextes aus dem 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.

#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);
  // ...
}

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.

struct Kasten2 : public Kasten          // Kasten2 ist ein Kasten
{
  Kasten2(int i = 0) : Kasten(i) {}     // mit besonderen Eigenschaften
};
 
void stapel_demo_14()
{
  Stapel<Kasten2> stapel;
  // ...
}

Die Vererbungstechnik ermöglicht objektorientierte Programmierung (OOP), den Aufbau und die Gruppierung ganzer Hierarchien gleichartig ansprechbarer Objektklassen (Oberbegriffe und Unterbegriffe). Die OOP-Philosophie (Verallgemeinerung und Spezialisierung, Ausdrücken von Gemeinsamkeiten) geht weit über das hier Zeigbare hinaus.

Objektorientierte Programmierung und generische Programmierung (die Parametrisierung von Datentypen in Schablonen) bieten zwei orthogonale, 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.
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;
  // ...
}

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.

#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;
};

Mit einem solchen Stapel könnte tief in irgendeinem Programmteil versteckt Folgendes angestellt werden:

template<class Sichere_Stapel>
void unsichere_Aktion(Sichere_Stapel& s)
{
  s.oben() = kiste[1];          // Sorglos!
  s.runter();                   // Nicht getestet! Quellen nicht gelesen?
}

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.

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 ...
}

Anhang

Treiber-Demoprogramm

Damit die beschriebenen Quellen getestet werden können, folgt noch ein Hauptprogramm:

int main()
{
  stapel_demo_1();
  stapel_demo_2();
  stapel_demo_3();
  stapel_demo_4();
  stapel_demo_5();
  stapel_demo_6();
  stapel_demo_7();
  stapel_demo_8();
  stapel_demo_9();
  stapel_demo_10();
  stapel_demo_11();
  stapel_demo_12();
  stapel_demo_13();
  stapel_demo_14();
  stapel_demo_15();
  stapel_demo_16();
 
  return 0;
}

Quellen

  1. Die Kunst des Hochstapelns, Unicum Hochschulmagazin 17 (1999) 6, S. 43.
  2. Bjarne Stroustrup: 16 ways to stack a cat. C++ Report, Oktober 1990.
  3. Wie funktioniert das? Der Computer. Meyers, Mannheim (1990), S. 146.
  4. Bjarne Stroustrup: Die C++ Programmiersprache. 3. Aufl., Addison-Wesley (1998).
  5. Bjarne Stroustrup: Design und Entwicklung von C++, Addison-Wesley (1994).
  6. Nicolai Josuttis: C++ Standard Bibliothek, Addison-Wesley (1996).
  7. Information Technology Standard – Programming Language C++. ANSI/ISO 14882. Information Technology Council (NSITC), Washington, DC (1998).
  8. Brian W. Kernighan, Dennis M. Ritchie: Programming in C. 2nd edn, Prentice-Hall (1988).
  9. Bjarne Stroustrup: Der produktive Weg zu C++. 1st European Software Festival 1990, CHIP Spezial (1990), S. 38

Impressum

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.

Stapel<Bauklotz> turm; 
// ... aufbauen ... 1997-10-23
while (!turm.empty())
  turm.pop();
1)
C-Programmierer kennen den Unterschied.
2)
Ich weiß, ich weiß: C-Programmierer vergessen das nicht. Nie. Wirklich! … Höchstens manchmal.
3)
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.
4)
Hier wird die Adresse mittels eines von der Funktion oben() gelieferten Zeigers ermittelt, aber dies ist ein Implementierungsdetail.
5)
Genaugenommen verlief die Entwicklung von C++ anders herum.
lernen/stapeln.txt · Zuletzt geändert: 2016-12-28 14:02 (Externe Bearbeitung)