Idee aus: [Ruminations] Andrew Koenig, Barbara Moo: Ruminations on C++. Addison-Wesley, Reading (Mass.) (1997) 175-190

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

Falls etwas schiefgeht, teilen wir das mit einer Ausnahmeklasse mit:

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

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.

  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:

    Item(T const& x, Item* successor)
    : use(1), value(x), next(successor)
    {
      if (successor) successor->use++;
    }
  };

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:

public:
  Sequence() : item(0) {}

Eine Sequenz aus Kopfwert und Restfolge zusammensetzen ist kaum schwieriger:

  Sequence(T const& headvalue, Sequence const& tailseq) 
  : item(new Item(headvalue, tailseq.item)) 
  {}

Da wir Zeiger verwalten, müssen wir den Kopierkonstruktor angeben. Wir müssen nur daran denken, den Referenzzähler des Anfangs zu erhöhen:

  Sequence(Sequence const& original)
  : item(original.item)
  {
    if (item) item->use++;
  }

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:

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

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:

private:
  Sequence(Item* entry)
  : item(entry)
  {
    if (item) item->use++;
  }

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.

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

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:

/*
  for (Seq s2 = s; s2; ++s2)
  {
    cout << *s2 << ' ';  // 1 2 3 4 5
  }
*/

Die Implementierung ist einfach:

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

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?

/*
  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, 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.

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

Wird versucht, einer Sequenz einen einzelnen Wert zuzuweisen, ist das als Beginn einer Initialisiererliste zu werten.

  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.

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

Diese können die Sequenzklasse so umhüllen, dass die Sequenz Lisp-artig funktional genutzt werden kann:

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

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

Der Quelltext der Klasse ist hier: sequence.hpp.