namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


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, Reading (Mass.) (1997) 175-190
  
 +===== Anforderungen an Sequenz =====
 +<code cpp>
 +Sequence();              // leere Sequenz bauen: Standardkonstruktor;
 +Sequence(head, tailseq); // Sequenz aus neuen Kopfwert und Schwanzfolge
 +bool    empty() const;   // wahr, wenn keine weiteren Werte in Sequenz
 +T        head() const;   // Kopfwert;  Sequenz darf nicht leer sein
 +Sequence tail() const;   // Restfolge; Sequenz darf nicht leer sein
 +</code>
 +===== 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;
 +};
 +
 +</code>
 +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;
 +
 +</code>
 +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;
 +
 +</code>
 +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->use++;
 +    }
 +  };
 +
 +</code>
 +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) {}
 +
 +</code>
 +Eine Sequenz aus Kopfwert und Restfolge zusammensetzen ist kaum schwieriger:
 +
 +<code cpp>
 +  Sequence(T const& headvalue, Sequence const& tailseq) 
 +  : item(new Item(headvalue, tailseq.item)) 
 +  {}
 +
 +</code>
 +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->use++;
 +  }
 +
 +</code>
 +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("no head in empty sequence");
 +    return item->value;  
 +  }  
 +
 +  Sequence tail() const
 +  {
 +    if (!item) throw SequenceError("no tail in empty sequence");
 +    return Sequence(item->next);  
 +  }
 +
 +</code>
 +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->next gebildet werden, 
 +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->use++;
 +  }
 +
 +</code>
 +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& operator=(Sequence const& original) 
 +  {
 +    if (original.item) original.item->use++;
 +    destroy(item);
 +    item = original.item;
 +    return *this;
 +  }
 +
 +</code>
 +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 << ' ';  // 1 2 3 4 5
 +  }
 +*/
 +
 +</code>
 +Die Implementierung ist einfach:
 +
 +<code cpp>
 +// pointer-like metapher - overloading operators (member)
 +   
 +  operator bool() const { return item != 0; }
 +  T operator*()   const { return head(); }
 +  Sequence& operator++()   { return *this = tail(); } 
 +  Sequence operator++(int) { Sequence tmp = *this; ++(*this); return tmp; }
 +
 +</code>
 +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;
 +*/
 +</code>
 +Aus der Numerik-Bibliothek Blitz++ für mehrdimensionale Arrays
 +ist zu erkennen, dass und wie es geht. 
 +
 +Dazu wird eine neue Hilfsklasse, ein Initialisierer benötigt.
 +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->next = new Item(x, 0);
 +      return Init(item->next);
 +    }
 +  private:  
 +    Item* item; 
 +  };
 +
 +</code>
 +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);
 +  }  
 +};
 +
 +</code>
 +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<T>::destroy(Sequence::Item* item)
 +{
 +  while (item && --item->use == 0)
 +  {
 +    Item* next = item->next;
 +    delete item;
 +    item = next;
 +  }
 +}
 +
 +#endif // SEQUENCE_H
 +</code>
 +===== 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<T>& s) // Lisp: null?
 +{
 +  return s.empty();
 +}
 +
 +template <class T>
 +inline
 +T head(Sequence const<T>& s) // Lisp: car
 +{
 +  return s.head();
 +}
 +
 +template <class T>
 +inline
 +Sequence<T> tail(Sequence const<T>& s) // Lisp: cdr
 +{
 +  return s.tail();
 +}
 +
 +template <class T>
 +inline
 +Sequence<T> 
 +concat(T const& x, Sequence const<T>& s) // Lisp: cons
 +{
 +  return Sequence<T>(x, s);
 +}
 +
 +template <class T>                       // Lisp:
 +Sequence<T> 
 +concat(Sequence<T> s, T const& x)       // (define append  
 +{                                       //   (lambda s x)
 +  if (empty(s))                         //   (if (null? s)
 +  {                                     //  
 +    return concat(x, Sequence<T>());    //       (cons x '())
 +  }                                     //       
 +  return concat(s.head(),               //       (cons (car s) 
 +                concat(s.tail(), x)     //             (append (cdr s) x))
 +               );                       //   )
 +}                                       // )  
 +</code>
 +===== Testprogramm =====
 +<code cpp>
 +#include <iostream>
 +#include "sequence.h"
 +
 +int main()
 +{
 +  typedef Sequence<int> Seq;
 +  int i;
 +  Seq s;
 +
 +  for (i = 1; i <= 5; ++i)
 +  {
 +    s = concat(i, s);
 +  }
 +
 +  // object-oriented metapher
 +  Seq s1 = s;
 +  std::cout << "OO-Style:      ";
 +
 +  while (!s1.empty())
 +  {
 +    std::cout << s1.head() << ' '; // 5 4 3 2 1
 +    s1 = s1.tail();
 +  }
 +  std::cout << '\n';
 +
 +  // Sequence is initialized from list
 +  s = 1, 2, 3, 4, 5;
 +
 +  // pointer-like metapher
 +  std::cout << "Pointer Style: "; 
 + 
 +  for (Seq s2 = s; s2; ++s2)
 +  {
 +    std::cout << *s2 << ' ';  // 1 2 3 4 5
 +  }
 +  std::cout << '\n';
 +  
 +  // 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 << ")\n";
 +  return 0;
 +}
 +</code>
 +Der Quelltext der Klasse ist hier: {{sequence.hpp}}.  
anwenden/sequence.txt · Zuletzt geändert: 2020-07-26 18:31 von 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki