anwenden:sequence
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | anwenden:sequence [2020-07-26 18:31] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Wertfolgen ====== | ||
+ | Idee aus: | ||
+ | [Ruminations] Andrew Koenig, Barbara Moo: Ruminations on C++. | ||
+ | Addison-Wesley, | ||
+ | ===== Anforderungen an Sequenz ===== | ||
+ | <code cpp> | ||
+ | Sequence(); | ||
+ | Sequence(head, | ||
+ | bool empty() const; | ||
+ | T head() const; | ||
+ | Sequence tail() const; | ||
+ | </ | ||
+ | ===== Implementierung ===== | ||
+ | |||
+ | Falls etwas schiefgeht, teilen wir das mit einer Ausnahmeklasse mit: | ||
+ | |||
+ | <code cpp> | ||
+ | |||
+ | //: sequence.h : Sequenz-Klasse - R.Richter 2002-10-14 | ||
+ | ////////////////////////////////////////////////////// | ||
+ | #ifndef SEQUENCE_H | ||
+ | #define SEQUENCE_H | ||
+ | |||
+ | class SequenceError | ||
+ | { | ||
+ | public: | ||
+ | SequenceError(char const* message) : msg(message) {} | ||
+ | virtual char const* what() const { return msg; } | ||
+ | private: | ||
+ | char const* msg; | ||
+ | }; | ||
+ | |||
+ | </ | ||
+ | Beginnen wir mit Klassendefinition als Schablone. | ||
+ | Eine Folge enthält stets Elemente des gleichen Typs, | ||
+ | von Folge zu Folge kann der Typ jedoch anders sein. | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T> | ||
+ | class Sequence | ||
+ | { | ||
+ | private: | ||
+ | struct Item; | ||
+ | Item* item; | ||
+ | |||
+ | </ | ||
+ | Einträge (Items) werden als private Struktur gehalten. | ||
+ | Für den Anfang geben wir uns mit einer Forward-Deklaration zufrieden. | ||
+ | Nur der erste Eintrag der Folge wird über einen Zeiger verwaltet. | ||
+ | Der Eintrag enthält einen Wert und einen Zeiger auf nächsten Eintrag. | ||
+ | |||
+ | <code cpp> | ||
+ | struct Item | ||
+ | { | ||
+ | int use; // reference count | ||
+ | T const value; | ||
+ | Item* next; | ||
+ | |||
+ | </ | ||
+ | Die Werte der Folge sind nicht änderbar (const). | ||
+ | Wir können das Kopieren von ganzen oder Teilfolgen vermeiden | ||
+ | durch die gemeinsame Nutzung der darunterliegenden Sequenz. | ||
+ | Das erfordert Referenzzähler. | ||
+ | |||
+ | Der einzige trickreiche Teil der Implementierung betrifft | ||
+ | das Bauen einer neuen Sequenz aus einem neuen Wert x und einer existierenden Sequenz | ||
+ | Danach müssen beide Sequenzen mit einer gemeinsamen Restfolge auskommen: | ||
+ | |||
+ | <code cpp> | ||
+ | Item(T const& x, Item* successor) | ||
+ | : use(1), value(x), next(successor) | ||
+ | { | ||
+ | if (successor) successor-> | ||
+ | } | ||
+ | }; | ||
+ | |||
+ | </ | ||
+ | Wichtig ist, die Referenzzählerei richtig zu verstehen. | ||
+ | Der Nachfolger wird dann einmal mehr benutzt, | ||
+ | der erste ist neu, also nur einmal gezählt. | ||
+ | Beachte: Der Zähler beim ersten kann niedriger sein als beim zweiten. | ||
+ | Das wird beim weiteren Bau der Sequenzklasse wichtig sein. | ||
+ | |||
+ | Der Standardkonstruktor definiert eine leere Folge. | ||
+ | Wir setzen den item Zeiger auf Null: | ||
+ | |||
+ | <code cpp> | ||
+ | public: | ||
+ | Sequence() : item(0) {} | ||
+ | |||
+ | </ | ||
+ | Eine Sequenz aus Kopfwert und Restfolge zusammensetzen ist kaum schwieriger: | ||
+ | |||
+ | <code cpp> | ||
+ | Sequence(T const& headvalue, Sequence const& tailseq) | ||
+ | : item(new Item(headvalue, | ||
+ | {} | ||
+ | |||
+ | </ | ||
+ | Da wir Zeiger verwalten, müssen wir den Kopierkonstruktor angeben. | ||
+ | Wir müssen nur daran denken, den Referenzzähler des Anfangs zu erhöhen: | ||
+ | |||
+ | <code cpp> | ||
+ | Sequence(Sequence const& original) | ||
+ | : item(original.item) | ||
+ | { | ||
+ | if (item) item-> | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Destruktor und Zuweisungsoperator müssen möglicherweise eine ganze Folge freigeben. | ||
+ | Wir kommen später darauf zurück, wenn die einfachen Dinge fertig sind. | ||
+ | Wann die Sequenz leer ist, ist offensichtlich: | ||
+ | |||
+ | <code cpp> | ||
+ | bool empty() const { return item == 0; } | ||
+ | |||
+ | T head() const | ||
+ | { | ||
+ | if (!item) throw SequenceError(" | ||
+ | return item-> | ||
+ | } | ||
+ | |||
+ | Sequence tail() const | ||
+ | { | ||
+ | if (!item) throw SequenceError(" | ||
+ | return Sequence(item-> | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Kopf und Rest der Folge lassen sich nur bilden, wenn die Folge mindestens einen Wert enthält. | ||
+ | Falls nicht, müssen wir eine Ausnahme werfen. | ||
+ | Der Rest der Liste muss aus item-> | ||
+ | aber dies ist ein Item, wir brauchen jedoch eine neue Sequence. | ||
+ | Dafür brauchen wir noch einen (privaten) Konstruktor: | ||
+ | |||
+ | <code cpp> | ||
+ | private: | ||
+ | Sequence(Item* entry) | ||
+ | : item(entry) | ||
+ | { | ||
+ | if (item) item-> | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Wir wenden uns wieder der Zuweisung und dem Destruktor zu. | ||
+ | Den komplizierten Teil des Abbauens einer Folge verstecken wir in einer (privaten) Hilfsmethode, | ||
+ | deren Implementation im Anschluss an die Klasse erfolgt. | ||
+ | |||
+ | <code cpp> | ||
+ | static void destroy(Item* item); | ||
+ | |||
+ | public: | ||
+ | ~Sequence() { destroy(item); | ||
+ | |||
+ | Sequence& | ||
+ | { | ||
+ | if (original.item) original.item-> | ||
+ | destroy(item); | ||
+ | item = original.item; | ||
+ | return *this; | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Der Zuweisungsoperator muss sich gegen Selbstzuweisung schützen. | ||
+ | Wir erhöhen deshalb den Zähler der rechten Seite, bevor die linke Seite abgebaut wird. | ||
+ | |||
+ | Für C- und C++-Programmierer ist eine zeigerartige Schreibweise vertraut, | ||
+ | auch wenn es sich bei den Sequenzen genaugenommen nicht um Zeiger handelt: | ||
+ | |||
+ | <code cpp> | ||
+ | /* | ||
+ | for (Seq s2 = s; s2; ++s2) | ||
+ | { | ||
+ | cout << *s2 << ' '; | ||
+ | } | ||
+ | */ | ||
+ | |||
+ | </ | ||
+ | Die Implementierung ist einfach: | ||
+ | |||
+ | <code cpp> | ||
+ | // pointer-like metapher - overloading operators (member) | ||
+ | |||
+ | operator bool() const { return item != 0; } | ||
+ | T operator*() | ||
+ | Sequence& | ||
+ | Sequence operator++(int) { Sequence tmp = *this; ++(*this); return tmp; } | ||
+ | |||
+ | </ | ||
+ | Der Postfix-Operator (erkennbar am nicht benutzten int-Parameter) | ||
+ | muss das gewohnte Verhalten der Postfix-Operatoren nachbilden | ||
+ | und die alte Sequenz zurückgeben. | ||
+ | |||
+ | Lässt sich einer Sequenz eine durch Komma getrennte Liste von Werten zuweisen? | ||
+ | |||
+ | |||
+ | <code cpp> | ||
+ | /* | ||
+ | Sequence s; | ||
+ | s = 1, 2, 3, 4, 5; | ||
+ | */ | ||
+ | </ | ||
+ | Aus der Numerik-Bibliothek Blitz++ für mehrdimensionale Arrays | ||
+ | ist zu erkennen, dass und wie es geht. | ||
+ | |||
+ | Dazu wird eine neue Hilfsklasse, | ||
+ | Der Initialisierer kann davon ausgehen, | ||
+ | immer auf dem letzten Knoten einer neuen Sequenz zu arbeiten. | ||
+ | Mit dem Initialisierer wird an der Liste entlanggehangelt. | ||
+ | Dazu wird (sehr ungewöhnlich!) der Kommaoperator überladen. | ||
+ | |||
+ | <code cpp> | ||
+ | // list initializer | ||
+ | class Init | ||
+ | { | ||
+ | public: | ||
+ | Init(Item* lastnode) : item(lastnode) {} | ||
+ | Init operator,(T const& x) | ||
+ | { | ||
+ | item-> | ||
+ | return Init(item-> | ||
+ | } | ||
+ | private: | ||
+ | Item* item; | ||
+ | }; | ||
+ | |||
+ | </ | ||
+ | Wird versucht, einer Sequenz einen einzelnen Wert zuzuweisen, | ||
+ | ist das als Beginn einer Initialisiererliste zu werten. | ||
+ | |||
+ | <code cpp> | ||
+ | Init operator=(T const& x) | ||
+ | { | ||
+ | destroy(item); | ||
+ | item = new Item(x, 0); | ||
+ | return Init(item); | ||
+ | } | ||
+ | }; | ||
+ | |||
+ | </ | ||
+ | Damit ist Klassendefinition abgeschlossen. | ||
+ | Zugegeben, das Überladen des Kommaoperators ist eine sehr gefährliche Sache. | ||
+ | Unabsichtliche Zuweisungen löschen die enthaltene Folge. | ||
+ | Darüber hinaus ist es nicht möglich, die Liste beim Konstruktor anzugeben, | ||
+ | da ein Konstruktor keinen Wert zurückgegeben kann. | ||
+ | |||
+ | Es bleibt die aufgeschobene destroy()-Methode zu implementieren. | ||
+ | Die Aufräumarbeiten müssen sorgfältig erledigt werden. | ||
+ | Die Folge darf nur überhaupt und nur soweit abgeräumt werden, | ||
+ | wie dieses Objekt der einzige Besitzer ist. | ||
+ | |||
+ | <code cpp> | ||
+ | template <class T> | ||
+ | void Sequence< | ||
+ | { | ||
+ | while (item && --item-> | ||
+ | { | ||
+ | Item* next = item-> | ||
+ | delete item; | ||
+ | item = next; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | #endif // SEQUENCE_H | ||
+ | </ | ||
+ | ===== Globale Funktionen | ||
+ | Diese können die Sequenzklasse so umhüllen, | ||
+ | dass die Sequenz Lisp-artig funktional genutzt werden kann: | ||
+ | |||
+ | <code cpp> | ||
+ | // Lisp like global functions: | ||
+ | template <class T> | ||
+ | inline | ||
+ | bool empty(Sequence const< | ||
+ | { | ||
+ | return s.empty(); | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | inline | ||
+ | T head(Sequence const< | ||
+ | { | ||
+ | return s.head(); | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | inline | ||
+ | Sequence< | ||
+ | { | ||
+ | return s.tail(); | ||
+ | } | ||
+ | |||
+ | template <class T> | ||
+ | inline | ||
+ | Sequence< | ||
+ | concat(T const& x, Sequence const< | ||
+ | { | ||
+ | return Sequence< | ||
+ | } | ||
+ | |||
+ | template <class T> // Lisp: | ||
+ | Sequence< | ||
+ | concat(Sequence< | ||
+ | { // | ||
+ | if (empty(s)) | ||
+ | { // | ||
+ | return concat(x, Sequence< | ||
+ | } // | ||
+ | return concat(s.head(), | ||
+ | concat(s.tail(), | ||
+ | | ||
+ | } // ) | ||
+ | </ | ||
+ | ===== Testprogramm ===== | ||
+ | <code cpp> | ||
+ | #include < | ||
+ | #include " | ||
+ | |||
+ | int main() | ||
+ | { | ||
+ | typedef Sequence< | ||
+ | int i; | ||
+ | Seq s; | ||
+ | |||
+ | for (i = 1; i <= 5; ++i) | ||
+ | { | ||
+ | s = concat(i, s); | ||
+ | } | ||
+ | |||
+ | // object-oriented metapher | ||
+ | Seq s1 = s; | ||
+ | std::cout << " | ||
+ | |||
+ | while (!s1.empty()) | ||
+ | { | ||
+ | std::cout << s1.head() << ' '; // 5 4 3 2 1 | ||
+ | s1 = s1.tail(); | ||
+ | } | ||
+ | std::cout << ' | ||
+ | |||
+ | // Sequence is initialized from list | ||
+ | s = 1, 2, 3, 4, 5; | ||
+ | |||
+ | // pointer-like metapher | ||
+ | std::cout << " | ||
+ | |||
+ | for (Seq s2 = s; s2; ++s2) | ||
+ | { | ||
+ | std::cout << *s2 << ' '; | ||
+ | } | ||
+ | std::cout << ' | ||
+ | | ||
+ | // Lisp-like metapher: | ||
+ | Seq s3 = s; | ||
+ | for (i = 1; i <= 5; ++i) | ||
+ | { | ||
+ | s3 = concat(s3, i); | ||
+ | } | ||
+ | |||
+ | std::cout << "Lisp Style : ( "; | ||
+ | while (!empty(s3)) | ||
+ | { | ||
+ | std::cout << head(s3) << ' '; | ||
+ | s3 = tail(s3); | ||
+ | } | ||
+ | std::cout << " | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
+ | Der Quelltext der Klasse ist hier: {{sequence.hpp}}. |
anwenden/sequence.txt · Zuletzt geändert: 2020-07-26 18:31 von 127.0.0.1