Dieses Kapitel behandelt die folgenden Themen:
Entstehung und Konzept
Bezug zur C++-Standardbibliothek
Wie wirken Container, Iteratoren und Algorithmen zusammen?
Einer der Erfolge von C++ beruht darauf, dass es zahlreiche Bibliotheken am Markt gibt, die die Entwicklung von Programmen erheblich erleichtern, weil sie verlässliche und erprobte Komponenten anbieten. Eine besonders sorgfältig konstruierte Bibliothek ist die Standard Template Library, die bei Hewlett-Packard von Alexander Stepanov, Meng Lee und ihren Kollegen entwickelt wurde. Sie ist wegen ihrer überzeugenden Konzeption des Zusammenwirkens von Behälterklassen (englisch Container) und Algorithmen vom ISO-Komitee als Teil des C++-Standards akzeptiert worden. Durch das Aufgehen in der C++-Standardbibliothek hat die STL die Rolle als eigenständige Bibliothek verloren.
Der große Vorteil von Templates liegt auf der Hand. Die Auswertung der Templates geschieht zur Compilierzeit, es gibt keine Laufzeiteinbußen – etwa durch polymorphe Funktionszugriffe, falls die Generizität mit Vererbung realisiert wird. Der Vorteil der Standardisierung ist noch größer einzuschätzen. Programme, die eine standardisierte Bibliothek benutzen, sind leichter portierbar, weil sich jeder Compiler-Hersteller am Standard orientiert. Darüber hinaus sind sie leichter wartbar, weil das entsprechende Know-how sehr viel verbreiteter ist als das Wissen über eine spezielle Bibliothek.
Der Schwerpunkt liegt auf Algorithmen, die mit Containern und Iteratoren zusammenarbeiten. Durch den Template-Mechanismus von C++ sind die Container für Objekte verschiedenster Klassen geeignet. Ein Iterator ist ein Objekt, das wie ein Zeiger auf einem Container bewegt werden kann, um auf das eine oder andere Objekt zu verweisen. Algorithmen arbeiten mit Containern, indem sie auf zugehörige Iteratoren zugreifen. Diese Konzepte werden weiter unten detailliert dargestellt.
Reduktion der Bibliothekskomponenten durch Templates
Die C++-Standardbibliothek bietet Container und Algorithmen für viele, auch benutzerdefinierte Datentypen, sofern sie einigen wenigen Voraussetzungen genügen. Die C++-Templates bieten die Grundlage dafür. Der Schwerpunkt liegt also nicht auf der Objektorientierung, sondern auf der generischen Programmierung. Damit ist der große Vorteil verbunden, dass die Anzahl der notwendigen verschiedenen Container- und Algorithmentypen drastisch reduziert wird. Ein weiterer Vorteil ist die Typsicherheit, weil Templates bereits zur Compilationszeit aufgelöst werden.
Nehmen wir zunächst an, dass es keine Templates gäbe und dass wir ein Element eines Datentyps int in einem Container vom Typ vector finden wollen. Dazu brauchen wir einen Algorithmus find(), der den Container durchsucht. Falls wir n verschiedene Container (Liste, Menge, ...) haben, brauchen wir für jeden Container einen eigenen Algorithmus, also n find()-Algorithmen. Nun könnte es ja sein, dass wir nicht nur ein int-Objekt, sondern ein Objekt eines beliebigen von m möglichen Datentypen suchen wollen. Damit würde die Anzahl der find()-Algorithmen auf n·m steigen. Diese Betrachtung soll für k verschiedene Algorithmen gelten, sodass insgesamt k · n ·m Algorithmen zu schreiben sind. Die Benutzung von Templates erlaubt es, die Anzahl m auf 1 zu reduzieren. Algorithmen der C++-Standardbibliothek arbeiten jedoch nicht direkt mit Containern, sondern nur mit Schnittstellenobjekten, den Iteratoren, die auf Container zugreifen. Iteratoren sind zeigerähnliche Objekte, die unten genau erklärt werden. Dadurch reduziert sich der notwendige programmiertechnische Aufwand (z.B. für eine Bibliothek) von n · k auf n + k (k Algorithmen + n Container-Schnittstellen), eine erhebliche Ersparnis.
| 10.1 | Container, Iteratoren, Algorithmen |
Zunächst werden die wichtigsten Elemente skizziert, ehe auf ihr Zusammenwirken eingegangen wird.
Container
Die C++-Standardbibliothek stellt verschiedene Arten von Containern zur Verfügung, die als Template-Klassen formuliert sind. Sie werden detailliert in Kapitel 27 beschrieben. Container sind Objekte, die zur Verwaltung anderer Objekte dienen, wobei es den Benutzern überlassen bleibt, ob sie die Objekte per Wert oder per Referenz ablegen. Die Ablage per Wert meint, dass jedes Element des Containers ein Objekt eines kopierbaren Typs ist (Wertsemantik). Die Ablage per Referenz heißt, dass die Elemente des Containers Zeiger auf Objekte von möglicherweise heterogenem Typ sind. In C++ müssen die verschiedenen Typen von einer Basisklasse abgeleitet und die Zeiger vom Typ »Zeiger auf Basisklasse« sein.
Ein Mittel, verschiedene Algorithmen mit verschiedenen Containern zusammenarbeiten zu lassen, besteht darin, dass die Namen, die zur Compilierzeit ausgewertet werden, für gleichartige Operationen gleich gewählt sind. Zum Beispiel gibt die Methode size() die Anzahl der Elemente eines Containers zurück, sei er nun vom Typ vector, list oder map.
Iteratoren
Iteratoren arbeiten wie Zeiger. Je nach Anwendungsfall können sie selbst gewöhnliche Zeiger oder Objekte mit zeigerähnlichen Eigenschaften sein. Der Zugriff auf ein Container-Element ist über einen Iterator möglich. Iteratoren können sich von einem Element zum nächsten bewegen, wobei die Art der Bewegung nach außen hin verborgen ist. Beispielsweise bedeutet in einem Vektor die Operation ++ das einfache Weiterschalten zur nächsten Position im Speicher, während dieselbe Operation in einem binären Suchbaum mit dem Entlangwandern im Baum verbunden ist. Die Methode begin() eines Containers gibt einen Iterator auf das erste Element zurück. *begin() ist eine Referenz auf dieses Element. Es muss bei einem Zugriff mit *begin() natürlich existieren, d.h., der Container darf nicht leer sein. Die Methode end() hingegen gibt einen Iterator auf die Position nach dem letzten Element zurück. Ein Zugriff mit *end() ist daher immer ein Fehler!
Hinweis
Die folgende Konvention der C++-Standardbibliothek muss beachtet werden: Wenn zwei Iteratoren begin() und end() einen Bereich definieren, zeigt der erste Iterator auf die Position des ersten Elements und der zweite auf die Position nach dem letzten Element. Der von end() zurückgegebene Iterator ist nicht dereferenzierbar. Ein leerer Container wird durch Gleichheit von begin() und end() gekennzeichnet.
Algorithmen
Die Template-Algorithmen arbeiten mit Iteratoren, die auf Container zugreifen. Da nicht nur benutzerdefinierte Datentypen unterstützt werden, sondern auch die in C++ ohnehin vorhandenen Datentypen wie int, char usw., wurden die Algorithmen so entworfen, dass sie ebenso gut mit normalen Zeigern arbeiten.
Zusammenwirken
Container stellen Iteratoren zur Verfügung, Algorithmen benutzen sie:
Container ⇐⇒ Iteratoren ⇐⇒ Algorithmen
Dadurch gibt es eine Entkopplung, die ein außergewöhnlich klares Design erlaubt. Im Folgenden soll ein Programm in verschiedenen Varianten zeigen, dass Algorithmen mit C-Arrays genauso gut funktionieren wie mit Template-Klassen der C++-Standardbibliothek.
In diesem Beispiel soll ein per Dialog einzugebender int-Wert in einem Array gefunden werden, wozu eine Funktion find() benutzt wird, die auch als Algorithmus der C++-Standardbibliothek vorliegt. Parallel wird find() auf verschiedene Arten formuliert, um die Abläufe sichtbar zu machen. Um sich schrittweise der angestrebten Formulierung zu nähern, wird zunächst eine Variante ohne Benutzung der C++-Standardbibliothek dargestellt. Der Container ist hier ein schlichtes C-Array. Um auszudrücken, dass ein Zeiger als Iterator wirkt, wird der Typname IteratorType mit using eingeführt.
Listing 10.1: Variante noch ohne Nutzung der STL (cppbuch/k10/einf/ohneSTL.cpp)
#include <iostream> using IteratorType = const int*; // neuer Typname für Zeiger auf const int // Prototyp des Algorithmus [[nodiscard]] IteratorType find(IteratorType begin, IteratorType end, int wert); int main() { constexpr int anzahl{100}; int einContainer[anzahl]; // Container definieren IteratorType begin{einContainer}; // Zeiger auf den Anfang IteratorType end{einContainer + anzahl}; // Position nach dem letzten Element // Container mit beliebigen Werten füllen (hier: gerade Zahlen) for (int i = 0; i < anzahl; ++i) { einContainer[i] = 2 * i; } int zahl{0}; while (zahl != -1) { std::cout << "˽gesuchte˽Zahl˽eingeben˽(-1˽=˽Ende):"; std::cin >> zahl; if (zahl != -1) { // weitermachen? IteratorType position = find(begin, end, zahl); if (position != end) { std::cout << "gefunden˽an˽Position˽" << (position - begin) << ’\n’; } else { std::cout << zahl << "˽nicht˽gefunden!\n"; } } } } // Implementation IteratorType find(IteratorType begin, IteratorType end, int wert) { while (begin != end // Zeigervergleich && *begin != wert) { // Dereferenzierung und Objektvergleich ++begin; // nächste Stelle } return begin; }
Im Fall eines leeren Containers haben beide Iteratoren denselben Wert. Man sieht, dass der Algorithmus find() selbst nichts über den Container wissen muss. Er benutzt nur Zeiger (Iteratoren), die einige wenige Fähigkeiten benötigen:
Der Operator ++ dient zum Weiterschalten auf die nächste Position.
Der Operator * dient zur Dereferenzierung. Angewendet auf einen Zeiger (Iterator) gibt er eine Referenz auf das dahinterstehende Objekt zurück.
Die Zeiger müssen mit dem Operator != vergleichbar sein.
Die Objekte im Container werden hier mit dem Operator != verglichen. Im nächsten Schritt wird die Implementierung der Funktion find() gestrichen. Der Prototyp wird durch ein Template ersetzt:
Listing 10.2: Variante 2: Algorithmus als Template (Auszug aus cppbuch/k10/einf/ohneSTLmitTemplate.cpp)
template<class Iterator, typename T> [[nodiscard]] Iterator find(Iterator begin, Iterator end, const T& wert) { while (begin != end // Zeigervergleich && *begin != wert) { // Dereferenzierung und Objektvergleich ++begin; // nächste Stelle } return begin; }
Der Rest des Programms bleibt unverändert. Der Platzhalter IteratorType für den Datentyp des Iterators kann einen beliebigen Namen haben. Im dritten Schritt wird ein Container der STL benutzt. Die Iteratoren begin und end werden im main()-Programm durch die Methoden der Klasse vector<T> ersetzt, die einen entsprechenden Iterator zurückgeben.
Listing 10.3: Variante 3: mit Template-Container vector (cppbuch/k10/einf/mitVector.cpp)
#include <iostream> #include <vector> // Der Prototyp des Algorithmus wird durch ein Template ersetzt: template <class Iterator, typename T> [[nodiscard]] Iterator find(Iterator begin, Iterator end, const T& wert) { while (begin != end // Zeigervergleich && *begin != wert) { // Dereferenzierung und Objektvergleich ++begin; // nächste Stelle } return begin; } int main() { std::vector<int> einContainer(100); // Container definieren // Container mit beliebigen Werten füllen (hier: gerade Zahlen) for (int i = 0; i < einContainer.size(); ++i) { einContainer[i] = 2 * i; } int zahl{0}; while (zahl != -1) { std::cout << "˽gesuchte˽Zahl˽eingeben˽(-1˽=˽Ende):"; std::cin >> zahl; if (zahl != -1) { // weitermachen? // globales find() von oben benutzen: auto position = // auto = vector<int>::const_iterator ::find(einContainer.begin(), // Container-Methoden einContainer.end(), zahl); if (position != einContainer.end()) { std::cout << "gefunden˽an˽Position˽" << (position - einContainer.begin()) << ’\n’; } else { std::cout << zahl << "˽nicht˽gefunden!\n"; } } } }
Alternativ sind die von Seite 226 bekannten freien Funktionen std::begin(arg) und std::end(arg) auch möglich. arg kann ein beliebiger Standardcontainer sein. Man sieht, wie der Standardcontainer mit unserem Algorithmus zusammenarbeitet und wie Arithmetik mit Iteratoren möglich ist (Differenzbildung). Im letzten Schritt wird der in der C++-Standardbibliothek vorhandenen find()-Algorithmus verwendet. Das gesamte Template wird durch eine weitere #include-Anweisung ersetzt:
Listing 10.4: Variante 4: Algorithmus find() der C++-Standardbibliothek (cppbuch/k10/einf/mitSTL.cpp)
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { vector<int> einContainer(100); // Container definieren // Container mit beliebigen Werten füllen (hier: gerade Zahlen) for (auto i {0z}; i < ssize(einContainer); ++i) { einContainer[i] = 2 * i; } int zahl{0}; while (zahl != -1) { cout << "˽gesuchte˽Zahl˽eingeben˽(-1˽=˽Ende):"; cin >> zahl; if (zahl != -1) { // weitermachen? // Der Aufruf ::find() wird durch find() ersetzt (d.h. Namespace std). auto position = find(einContainer.begin(), einContainer.end(), zahl); if (position != einContainer.end()) { cout << "gefunden˽an˽Position˽" << (position - einContainer.begin()) << ’\n’; } else { cout << zahl << "˽nicht˽gefunden!\n"; } } } }
Darüber hinaus ist es nicht erforderlich, mit using einen Iteratortyp zu definieren, weil jeder Container der STL einen entsprechenden Typ liefert. Anstatt IteratorType position kann im obigen Programm vector<int>::iterator position geschrieben werden – oder noch einfacher: auto position. Der Algorithmus kann mit jeder Klasse von Iteratoren zusammenarbeiten, die die Operationen != zum Vergleich, * zur Dereferenzierung und ++ zur Weiterschaltung auf das nächste Element zur Verfügung stellen. Dies zeigt die Mächtigkeit des Konzepts und ist ein Grund dafür, dass jeder Algorithmus nur in einer Form vorliegen muss. Damit werden Verwaltungsprobleme minimiert und Inkonsistenzen ausgeschlossen. Dem Ideal, dass man nur noch verschiedene Softwarekomponenten zusammenstecken muss, die dann miteinander funktionieren, kommen die Algorithmen und Container der C++-Standardbibliothek recht nahe. Durch Verwendung der vorhandenen Algorithmen und Container werden Programme nicht nur kürzer, sondern auch zuverlässiger, weil Programmierfehler vermieden werden. Die Produktivität der Softwareentwicklung steigt damit.
| 10.2 | Iteratoren im Detail |
Die sequenzielle Bearbeitung einer Datenstruktur, die keine Liste sein muss, durch eine Methode, die nach außen hin die innere Struktur der Daten verbirgt, heißt Kontrollabstraktion. Das »Durchwandern« der Datenstruktur in einer bestimmten Reihenfolge kann sinnvoll sein, um auf jedes Element eine bestimmte Operation anzuwenden, zum Beispiel das Ausdrucken des Inhalts. Der Benutzer soll auf die Elemente der Reihe nach zugreifen können, ohne Kenntnis über die verborgene Implementierung haben zu müssen. Ein Prinzip zur Kontrollabstraktion dieser Art wird Iterator genannt.
Ein Iterator ist ein Konzept, das auf eine Menge von Klassen und Typen zutrifft, die bestimmten Anforderungen entsprechen. Ein Iterator kann auf verschiedene Weise mit Grunddatentypen oder Klassenobjekten realisiert werden. Weil ein Iterator dazu dient, auf Elemente eines Containers zuzugreifen, ist er eine Art verallgemeinerter Zeiger. Wesentlich für alle Iteratoren sind die bereits genannten Fähigkeiten des Weiterschaltens (++), der Dereferenzierung (*) und der Vergleichsmöglichkeit (!= bzw. ==). Falls der Iterator nicht ein gewöhnlicher Zeiger, sondern ein Objekt einer Iterator-Klasse ist, werden diese Eigenschaften durch die entsprechenden Operatorfunktionen realisiert:
Listing 10.5: Schema eines einfachen Iterators
template<typename T> class Iteratortyp { public: // Konstruktoren, Destruktor weggelassen bool operator==(const Iteratortyp<T>&) const; // impliziert != Iteratortyp<T>& operator++(); // präfix Iteratortyp<T> operator++(int); // postfix T& operator*() const; T* operator->() const; private: // Verbindung zum Container ... };
Der Operator -> erlaubt es, einen Iterator wie einen Zeiger zu verwenden. Die wesentlichen Eigenschaften eines Iterators sind also:
1. Ein Iterator kann wie ein Zeiger benutzt werden.
2. Wie das Vorangehen mit dem ++-Operator intern funktioniert, ist dem Benutzer verborgen. So wird ein Iterator iter nur mit dem Befehl ++iter um eine Position weitergeschaltet. Die möglicherweise damit verbundene komplexe Operation, zum Beispiel den nächsten Eintrag in einem binären Suchbaum zu finden, ist für den Benutzer nicht sichtbar.
Der Iterator könnte je nach Art des Containers auch weitere Methoden haben, etwa operator--(), operator+=() und operator+():
Die Operation ++ ist für eine einfach verkettete Liste, wie sie im nächsten Abschnitt 10.3 beschrieben wird, sinnvoll. Eine doppelt verkettete Liste muss jedoch in beiden Richtungen durchlaufen werden können. Ein Iterator für eine doppelt verkettete Liste braucht damit auch einen ---Operator.
Bei einem Vektor ist ein ---Operator ebenfalls sinnvoll. Ein Vektor erlaubt einen wahlfreien (englisch random access) Zugriff, also direkt durch Angabe der Adresse. Das geht wie bekannt mit dem []-Operator und auch mit einem passenden Iterator. Bei einem Vektor v zeigt v.begin() auf das Element 0, es gilt also *(v.begin()) == v[0]. Dementsprechend gilt *(v.begin() + n) == v[n], sofern n ≥ 0 und n < v.size() ist. Auf einen Iterator, der wahlfreien Zugriff erlaubt, kann also eine Zahl n addiert werden. Subtraktion ist auch möglich. Das Ergebnis ist ein Iterator, der auf eine Stelle zeigt, die n Positionen weiter liegt. Bei einer verketteten Liste gibt es keinen wahlfreien Zugriff.
Zustände
Iteratoren erlauben es, mit verschiedenen Containern auf gleichartige Weise zu arbeiten. Ein Iterator kann verschiedene Zustände haben.
Ein Iterator kann erzeugt werden, auch ohne dass er mit einem Container verbunden ist. Die Verbindung zu einem Container wird dann erst nachträglich hergestellt. Ein solcher Iterator ist nicht dereferenzierbar. Ein vergleichbarer C++-Zeiger könnte zum Beispiel den Wert nullptr haben.
Ein Iterator kann während der Erzeugung oder danach mit einem Container verbunden werden. Typischerweise – aber nicht zwingend – zeigt er nach der Initialisierung auf den Anfang des Containers. Die Methode begin() eines Containers liefert die Anfangsposition. Wenn der Container nicht leer ist, ist der Iterator in diesem Fall dereferenzierbar. Man kann also über ihn auf ein Element des Containers zugreifen. Der Iterator ist mit Ausnahme der end()-Position (siehe nächster Punkt) für alle Werte dereferenzierbar, die mit der Operation ++ erreicht werden können.
In C++ ist der Wert eines Zeigers, der auf die Position direkt nach dem letzten Element eines C-Arrays zeigt, stets definiert. In Analogie dazu gibt die Methode end() eines Containers einen Iterator mit eben dieser Bedeutung zurück, auch wenn der Container kein Array, sondern zum Beispiel eine Liste ist. Damit können Iteratoren und Zeiger auf C++-Grunddatentypen gleichartig behandelt werden. Der Vergleich eines laufenden Iterators mit diesem Nach-dem-Ende-Wert signalisiert, ob das Ende eines Containers erreicht wurde. Ein Iterator, der auf die Position nach dem Ende eines Containers verweist, ist natürlich nicht dereferenzierbar.
Auf weitere Eigenschaften von Iteratoren wird in Kapitel 28 eingegangen. Im nächsten Abschnitt folgt ein Beispiel mit einem Iterator, der mehr können muss als ein Zeiger auf ein int-Array zu sein.
| 10.3 | Beispiel verkettete Liste |
Wie funktioniert das Zusammenwirken von Containern, Iteratoren und Algorithmen genau? Um dies im Einzelnen zu zeigen, verwende ich das main-Programm zu Listing 10.4 in leicht variierter Form. Damit ein Iterator dieser Klasse nicht einfach einem Zeiger gleichgesetzt werden kann, wird die Komplexität des Beispiels geringfügig erhöht: Eine einfach verkettete Liste tritt an die Stelle des Vektors. Die Klasse werde Liste genannt. Eine einfach verkettete Liste ist wohl die bekannteste dynamische Datenstruktur. Sie besteht aus Elementen, die miteinander über Zeiger verbunden sind (siehe Abbildung 10.1).
Ein Element einer einfach verketteten Liste besteht aus Daten, zum Beispiel einer Adresse, und einem Verweis auf das nächste Element. Der Nachteil der einfach verketteten Liste besteht darin, dass man sie nur in Vorwärtsrichtung bearbeiten kann, weil die Information über das Vorgängerelement in den Elementen der Liste nicht vorhanden ist. Es gibt verschiedene Möglichkeiten, auf eine Liste zuzugreifen:
a) Einfügen eines Elements am Anfang
b) Einfügen eines Elements am Ende
c) Einfügen eines Elements dazwischen
d) Lesen und Entfernen eines Elements am Anfang
e) Lesen und Entfernen eines Elements am Ende
und andere mehr. Eine Liste, bei der nur die Operationen a) und e) zugelassen sind, heißt Warteschlange (englisch queue) und arbeitet nach dem fifo-Prinzip (fifo = first in, first out). Falls nur die Operationen a) und d) (beziehungsweise b) und e)) erlaubt sind, heißt die Liste Stapel oder Kellerspeicher (englisch stack). Auf einen Stapel kann man nur von oben etwas legen oder wegnehmen, er arbeitet nach dem lifo-Prinzip (last in, first out). In eine (allgemeine) Liste kann auch mittendrin eingefügt oder entnommen werden. Im folgenden Beispiel beschränke ich mich auf a). Es gibt keinen Indexoperator und somit keinen wahlfreien Zugriff auf die Elemente. Ferner wird nur mit einfachen Zeigern gearbeitet und keinerlei Rücksicht auf das Laufzeitverhalten genommen, um die Klasse so einfach wie möglich zu gestalten. Der vorhandene Algorithmus std::find() wird verwendet, um zu zeigen, dass sich die selbstgeschriebene Klasse wirklich genau wie eine Klasse der C++-Standardbibliothek verhält, wenigstens bezüglich des main-Programms unten.
Hinweis
Die Klasse für eine einfache Liste ist nicht vollständig und daher nicht sicher benutzbar! Sie stellt nur das zur Verfügung, was im Beispiel benötigt wird. Konsequenz: Nachdem Ihnen die Wirkungsweise klar ist, benutzen Sie für weitere Zwecke bitte die Klasse list der C++-Standardbibliothek (siehe Seite 864).
Die Liste besteht aus Elementen, deren Typ innerhalb der Klasse als innere oder geschachtelte public-Klasse (struct) definiert ist. Sie liegt innerhalb der private-Sektion der Klasse Liste, sodass ein direkter Zugriff von außen nicht möglich ist. Jedes Listenelement trägt die Daten (zum Beispiel eine Zahl) mit sich sowie einen Zeiger auf das nächste Listenelement. Die Klasse Liste stellt einen öffentlichen Iteratortyp Iterator zur Verfügung. Ein Iterator-Objekt verweist auf die aktuelle Position in der Liste (Attribut aktuellesElement der Klasse Liste::iterator) und ist geeignet, darüber auf die in der Liste abgelegten Daten zuzugreifen, wie das Beispiel unten zeigt. Die Iteratormethoden erfüllen die auf Seite 461 beschriebenen Anforderungen.
Listing 10.6: Klasse für eine Liste (unvollständig) (cppbuch/k10/liste/Liste.h)
#ifndef LISTE_H #define LISTE_H #include <cstddef> #include <iterator> // Unvollständig! (nur für das Beispiel notwendige Funktionen sind implementiert). // Siehe auch Übungsaufgaben. template <typename T> class Liste { public: // Kopierkonstruktor, Destruktor und Zuweisungsoperator fehlen! (Aufgaben) // push_front() erzeugt ein neues Listenelement und fügt es am Anfang der Liste ein: void push_front(const T& wert) { anfang = new ListElement(wert, anfang); } private: struct ListElement { T daten; ListElement* naechstes; ListElement(const T& wert, ListElement* p) : daten{wert}, naechstes{p} {} }; ListElement* anfang{nullptr}; public: class Iterator { public: // von find() geforderte Schnittstelle: using iterator_category = std::forward_iterator_tag; using value_type = T; using pointer = T*; using reference = T&; using difference_type = std::ptrdiff_t; Iterator(ListElement* init = nullptr) : aktuellesElement{init} {} [[nodiscard]] const T& operator*() const // Dereferenzierung { return aktuellesElement->daten; } Iterator& operator++() // Präfix { aktuellesElement = aktuellesElement->naechstes; return *this; } [[nodiscard]] Iterator operator++(int) // Postfix { Iterator temp{*this}; ++*this; return temp; } [[nodiscard]] bool operator==(const Iterator& x) const { return aktuellesElement == x.aktuellesElement; } // operator!=() wird automatisch generiert. private: ListElement* aktuellesElement; // Verweis auf aktuelles Element }; // Iterator // Einige Methoden der Klasse Liste benutzen die Klasse Iterator: [[nodiscard]] Iterator begin() { return Iterator(anfang); } [[nodiscard]] Iterator end() { return Iterator(); } }; #endif
Das zugehörige main-Programm verwendet die Listenklasse. Eine gefundene Zahl wird nicht mit der Variablen zahl angezeigt, was auch möglich wäre, sondern mit dem dereferenzierten Iterator.
Listing 10.7: Anwendung der Liste (cppbuch/k10/liste/main.cpp)
#include "Liste.h" #include <algorithm> #include <iostream> int main() { Liste<int> einContainer; // Container definieren // Container mit beliebigen Werten füllen (hier: gerade Zahlen) for (int i = 0; i < 100; ++i) { einContainer.push_front(2 * i); } int zahl{0}; while (zahl != -1) { std::cout << "˽gesuchte˽Zahl˽eingeben˽(-1˽=˽Ende):"; std::cin >> zahl; if (zahl != -1) { // weitermachen? // std::find() benutzen auto position = std::find(einContainer.begin(), einContainer.end(), zahl); if (position == einContainer.end()) { std::cout << "˽nicht˽gefunden!\n"; } else { std::cout << *position // Dereferenzierung des Iterators << "˽gefunden!\n"; } } } std::cout << "Liste˽ausgeben:\n"; for (auto wert : einContainer) { std::cout << wert << ’\n’; } }
In diesem Programm kommt wieder das Schlüsselwort auto zur Geltung, um nicht Liste <int>::Iterator schreiben zu müssen. Diese Einführung zeigt die Funktionsweise der STL. Mehr Informationen zu den Containern, Iteratoren und Algorithmen der C++-Standardbibliothek finden Sie in weiteren Kapiteln:
Container: Kapitel 27
Iteratoren: Kapitel 28
Algorithmen: Kapitel 23 und 29
Übung
10.1 Ergänzen Sie die Klasse Liste wie folgt und versuchen Sie, Lösungen der Teilaufgaben wiederzuverwenden. Achten Sie darauf, dass kein Memory Leak entsteht.
Methode bool empty(), die anzeigt, ob die Liste leer ist
Methode int size(), die die Anzahl der Elemente zurückgibt. Führen Sie dazu kein Attribut anzahl ein, sondern gehen Sie durch die Liste (d.h. schlechte Performance übungshalber in Kauf nehmen).
Kopierkonstruktor
Zuweisungsoperator
Destruktor
Methode Iterator erase(Iterator p), die das Element, auf das der Iterator p zeigt, aus der Liste entfernt. Der zurückgegebene Iterator soll auf das nach p folgende Element zeigen, sofern es existiert. Andernfalls soll end() zurückgegeben werden. Ergänzen Sie vorher die Klasse Iterator um friend class Liste;, damit erase() auf das zu löschende Element zugreifen darf.
Methode void pop_front(), die das erste Element löscht
Methode void clear(), die die ganze Liste löscht
| 10.4 | Ranges und Views |
Einen Range1 (dt. Bereich) kann man sich ungefähr als Paar [i, s) vorstellen, wobei i ein Iterator auf den Anfang ist und s (für sentinel, dt. etwa Wächter) als Endekriterium für das Durchlaufen des Bereichs dient. s kann von einem anderen Typ als i sein, aber auch ein Iterator wie end(). Die ranges-Bibliothek bietet sehr viele Möglichkeiten. Die wichtigsten Konzepte werden in diesem Abschnitt skizziert.
Unterschied zwischen View und Range
Die Klassen string_view und vector<int> sind beide Ranges, weil sie Iteratoren kapseln. Diese werden zum Beispiel von den Funktionen begin() und end() zurückgegeben. Ein Vektor besitzt seine Elemente. Eine Ansicht bzw. View zeichnet sich aber dadurch aus, dass sie die Elemente nicht besitzt und nicht ändern kann. Ein Beispiel ist die Klasse string_view – im Gegensatz zum vector. Sowohl View als auch Range sind letztlich etwas, über das man iterieren kann. Eine View unterliegt nur mehr Einschränkungen. Weil ein View-Objekt im Wesentlichen nur zwei Iteratoren kapselt, kann es in konstanter Zeit kopiert oder zugewiesen werden. Aus einem Range kann eine View erzeugt werden.
Iteratoren
Die klassischen Iteratoren wie begin(), end() usw. und Funktionen wie size() gibt es auch in der ranges-Bibliothek. Eine Anwendung:
Listing 10.8: Ranges-Anwendung
const std::vector<int> vec { 10, 1, 6, 1, 7, 2, 12, 3}; for (auto iter = std::ranges::begin(vec); iter != std::ranges::end(vec); ++iter) { std::cout << *iter << ’\n’; } std::cout << "Anzahl˽˽˽˽:˽" << std::ranges::size(vec) << ’\n’; std::cout << "1.˽Element:˽" << *std::ranges::data(vec) << ’\n’;
Algorithmen
Das Konzept der Iteratoren erlaubt klare und einfache Schnittstellen. Aber die Syntax, bei Algorithmen jeweils begin() und end() angeben zu müssen, ist schreibaufwendig. Die ranges-Bibliothek ermöglicht eine kompaktere Schreibweise. Ein Beispiel:
Die neue Schreibweise ist deutlich bequemer. Trotzdem wird die alte Schreibweise nicht überflüssig: Es könnte ja sein, dass nicht der ganze Vektor, sondern nur ein durch zwei Iteratoren definierter Teilbereich sortiert werden soll. Der Namespace ranges wird im Header <algorithm> berücksichtigt. Im Kapitel 23 (Algorithmen für verschiedene Aufgaben) werden Ranges beachtet, sodass hier nicht weiter darauf eingegangen wird.
Views und Filter
In der Unix-Welt hatte man früh bemerkt, dass die Ausgabe eines Programms in einer Konsole (Standardausgabe, C++: cout) oft als Eingabe eines anderen Programms dient (Standardeingabe, C++: cin). Für die Arbeit mit Kommandozeilen wurde der Operator | (senkrechter Strich) entwickelt, der die Verkettung von Programmen erlaubt. Eine Reihe von verketteten Programmen heißt in der Unix-Welt Pipeline oder kurz Pipe. Im folgenden Beispiel zur Ermittlung der Anzahl der Bilddateien im JPG-Format listet der Befehl ls alle Dateien des Verzeichnisses Bilder und der zugehörigen Unterverzeichnissen auf. Die Ausgabe geht an das Programm grep, das alle Dateinamen mit den Endungen jpg und JPG herausfiltert. Die Option -i sorgt dafür, dass Groß- und Kleinschreibung ignoriert wird. Die Zusatzoption c bewirkt, dass nicht die Dateien, sondern ihre Anzahl ausgegeben wird.
Pipes ermöglichen komplexe Programme mit wenigen Befehlen. Die ranges-Bibliothek bildet diese Funktionalität nach, sodass sie in C++-Programmen nutzbar ist. Das Listing 10.10 zeigt, wie es geht. Dabei ist std::views eine im Header <ranges> definierte Abkürzung für std::range::views.
Listing 10.10: View und Filter (cppbuch/k10/filter.cpp)
#include <ranges> #include <iostream> #include <vector> #include <showContainer.h> [[nodiscard]] bool ungerade(int i) { return i % 2 != 0; } [[nodiscard]] int quadrat(int i) { return i*i; } int main() { const std::vector<int> vec { 10, 1, 6, 1, 7, 7, 2, 9, 12, 3}; std::cout << "Ausgangsvektor:˽"; showContainer(vec); auto view1 = vec | std::views::filter(ungerade); std::cout << "Ungerade˽Zahlen:˽"; showContainer(view1); auto view2 = view1 | std::views::transform(quadrat); std::cout << "Deren˽Quadrate:˽˽"; showContainer(view2); std::cout << "Beide˽Filter˽in˽der˽for-Schleife:˽"; for (int i : vec | std::views::filter(ungerade) | std::views::transform(quadrat)) { std::cout << i << ’˽’; } std::cout << "\nUmgekehrte˽Reihenfolge:˽"; auto view3 = view2 | std::views::reverse; showContainer(view3); std::cout << "Die˽ersten˽drei˽fallen˽lassen:˽"; auto view4 = view3 | std::views::drop(3); showContainer(view4); std::cout << "Mit˽Iterator˽ausgeben:˽"; for(auto iter = view4.begin(); iter != view4.end(); ++iter) { std::cout << *iter << ’˽’; } std::cout << ’\n’; }
Das Ergebnis des Programms ist:
In Listing 10.10 ist view1 eine Sicht auf den Vektor vec, die nur seine ungerade Zahlen enthält. Sie werden mit der Funktion filter() der ranges-Bibliothek und der Funktion ungerade() (oben im Listing) herausgefiltert. Auf view1 wird anschließend eine Transformation angewendet, sodass view2 die Quadrate der ungeraden Zahlen enthält. Wie die for-Schleife zeigt, können beide Operationen nacheinander geschrieben werden, verbunden durch den |-Operator. Danach wird die Reihenfolge umgedreht und vom Ergebnis werden die ersten drei Elemente entfernt. Zum Schluss wird die Anwendung von Iteratoren gezeigt. Bei diesen Operationen wird der Vektor vec nicht verändert.
Subranges
Sie können von einem Container Unterbereiche anlegen. Der größte Unterbereich umfasst den Container selbst:
Im Folgenden wird ein Teilbereich des Vektors definiert, dessen Werte mit 10 multipliziert werden. Zur Kontrolle wird der veränderte Vektor ausgegeben:
Sie kennen nun die Grundlagen der C++-Ranges. Sie werden in weiteren Kapiteln dieses Buchs verwendet, soweit passend. Eine ausführliche Darstellung der vielen Möglichkeiten kann hier aus Platzgründen nicht geleistet werden, aber es gibt gute (englischsprachige) weiterführende Quellen, insbesondere die vom Erfinder Eric Niebler [Nieb].
1 Mit diesem Begriff werden hier Bereiche im Sinn der ranges-Bibliothek bezeichnet. Die Bedeutung im Text ist damit weniger allgemein, verglichen mit der wörtlichen Übersetzung »Bereich«.