3.7 Iteration über Containerelemente

Der Anwender eines Containers wird mit einer gewissen Wahrscheinlichkeit früher oder später eine Möglichkeit brauchen, alle eingefügten Elemente wieder zu erhalten (beispielsweise um alle Elemente in einer Datei zu speichern, oder Summen, Durchschnittswerte und ähnliches über alle Elemente bilden zu können).

Wenn ein Container nur die Mindestoperationen Einfügen, Suchen anhand eines Schlüsselwertes und Löschen anhand eines Schlüsselwertes anbietet, ist es nicht möglich, zu einem späteren Zeitpunkt alle Elemente anfassen zu können, ohne alle Schlüssel zu kennen.

Um mit allen Elementen eines Containers arbeiten zu können (Iteration über die Elemente, Enumeration der Elemente), ist also eine erweiterte Schnittstelle nötig.

Wenn sich aus der Art des Containers nicht natürlicherweise eine solche Möglichkeit ergibt (wie bei einem Array oder Vektor durch den Zugriff über den Index), hat man dafür im Wesentlichen folgende Möglichkeiten:

1. Cursor: Der Container speichert intern einen Verweis auf ein aktuelles Element, auch Cursor genannt, und bietet in seiner Schnittstelle zum Anwender über Methoden die folgenden Möglichkeiten:
   • den Cursor an den Anfang zu setzen (auf ein Element, das als erstes erscheinen soll, beispielsweise bei einer Liste der Listenanfang)
   • den Cursor von einem Element zum nachfolgenden zu bewegen (in einer Liste also zum Nachfolger wechseln)
   • Zugriff auf die Nutzdaten des Elements, auf das der Cursor gerade verweist
   • eventuell eine Abfragemöglichkeit, ob nach dem aktuellen noch weitere Elemente existieren (man kann auf diese Abfrage auch verzichten, indem beim Weiterbewegen auf das nächste Element durch einen Rückgabewert oder eine Ausnahme das Ende der Iteration signalisiert wird, oder indem der Zugriff auf die Nutzdaten einfach fehlschlägt, wenn man sich bereits über das letzte Element hinausbewegt hat).

   Mit diesen Methoden kann sich der Anwender eine Schleife über alle Elemente konstruieren in der Art (Schreibweise angelehnt an Java):

   Liste  l;
   l.insert( ... ); // Container füllen
   l.insert( ... );
   ...
   Nutzdatentyp aktuell; // Verweis auf jeweils ein Containerelement
   l.resetCursor();      // Cursor auf erstes Element richten
   while( (aktuell=l.getCursorDaten())!=null ) // Daten holen
   {
       // verarbeite das Objekt aktuell...
   
       l.nextCursor(); // ein Element weitergehen
   }
   

2. Enumerationsobjekt: Der Container bietet einen eigenen Datentyp zur Enumeration an, von dem sich der Anwender ein Objekt beschafft (beispielsweise mit einer Methode im Container wie etwa getNewEnumerator()).

   Dieses Objekt bietet eine Schnittstelle an, wie oben beim Cursor beschrieben.

   Die Verwendung könnte dann so aussehen:

   Liste  l;
   l.insert( ... ); // Container füllen
   l.insert( ... );
   ...
   ListenEnumerator aktuell = l.getNewEnumerator(); // Enumerationsobjekt
   aktuell.resetCursor();         // Cursor auf erstes Element richten
   while( (aktuell.getDaten())!=null ) // Daten holen
   {
       // verarbeite das Objekt aktuell.getDaten()...
   
       aktuell.next(); // ein Element weitergehen
   }
   

3. call back-Funktion: Der Container bietet eine Methode an (beispielsweise iterator()), die über alle Element iteriert, und der Anwender ruft diese Methode auf, anstatt eine eigene Schleife zu bauen. Die Schleife über alle Elemente liegt also nicht im Code des Anwenders, sondern des Containers.

   Weil der Ersteller des Containers aber natürlich nicht wissen kann, was mit den einzelnen Elementen zu geschehen hat, muß der Anwender dies mitteilen. Dazu schreibt er sich eine Funktion beziehungsweise eine Methode, die bei jedem Aufruf ein Nutzdatenelement des Containers erhält, und wie gewünscht verarbeitet. Diese Funktion wird von der iterator()- Methode des Containers für jedes Element des Containers aufgerufen, und heißt oft call back-Funktion (weil über diese Funktion aus dem Code des Containers beim Anwender sozusagen zurückgerufen wird).

   Der Anwendercode für eine Iteration sieht damit etwa so aus:

   // call back-Funktion:
   void tuwasmitmeinenNutzdaten( Nutzdatentyp aktuell )
   {
       // verarbeite das Objekt aktuell.getDaten()...
   }
   
   ...
   Liste  l;
   l.insert( ... ); // Container füllen
   l.insert( ... );
   ...
   l.iteriere( tuwasmitmeinenNutzdaten );
   

   Die bei den bisherigen Möglichkeiten zur Iteration (Cursor, Enumerationsobjekt) im Anwendercode vorhandene Schleife über die Elemente ist hierbei in den Container verlagert, und muß gar nicht zwangsweise eine explizite Schleife sein, sondern kann auch durch rekursive Funktionsaufrufe ausgeführt werden.

4. Funktionsobjekt: Da nicht alle Programmiersprachen die Übergabe von Funktionen als Parameter ermöglichen (Fortran, Pascal, Ada, C/C++: ja; Java: nein), muß man eventuell auf ein sogenanntes Funktionsobjekt (functional object, functionoid, functor) ausweichen. Das ist ein Objekt einer Klasse, die eine Methode anbietet, und sonst in der Regel keine oder nur wenige Daten enthält. Sinn dieses Objekts ist nur, als Parameter übergeben werden zu können, und dabei eine aufzurufende Methode über die Parameterliste zu ,,schmuggeln``. Aufrufer und Container müssen sich über den Namen der aufzurufenden Methode einig sein; im folgenden Beispiel wird sie einfach tuwas genannt.

   Ansonsten ist dieser Weg identisch mit der obigen call back-Funktion; es wird lediglich statt eines Funktion ein Objekt mit angehängter Funktion als Parameter übergeben.

   // Schnittstelle eines Funktionsobjekts:
   interface IFunktionObject
   {
       void tuwas( Object o );
   }
   
   // Implementierung des Funktionsobjekts:
   class TuwasMitMeinenNutzdaten implements IFunktionObject
   {
       void tuwas( Object o )
       {
           // verarbeite das Objekt o...
       }
   }
   
   ...
   Liste  l;
   l.insert( ... ); // Container füllen
   l.insert( ... );
   ...
   TuwasMitMeinenNutzdaten funktionsobjekt = new TuwasMitMeinenNutzdaten();
   l.iteriere( funktionsobjekt );
   

   Auch wenn die Vorgehensweise recht ähnlich ist zu einer call back-Funktion, die als Parameter übergeben wird, hat man hier aber zwei Vorteile:

   1. Man kann Funktionsobjekte auch verwenden, wenn Funktionen als Parameter nicht zulässig sind (wie in Java).
   2. Neben der eigentlichen Aufgabe, eine Methode an den Container zu übergeben, kann ein Funktionsobjekt noch mehr Funktionalität bieten.

      Beispielsweise können in der Klasse weitere Attribute definiert werden, die einen internen Status bilden und von Datenelement zu Datenelement manipuliert werden, wie etwa Aufsummieren von Werten, Zählen aller Elemente oder nur solcher mit bestimmten Eigenschaften, und weiteres.

      Hat ein Student beispielsweise eine Intelligenz in Form eines Attributs int iq, dann kann man die durchschnittliche Intelligenz aller Elemente eines Containers folgendermaßen bilden:

      // Implementierung des Funktionsobjekts:
      class Durchschnittsintelligenz implements IFunktionObject
      {
          private int  iq_summe;
          private int  anzahl_aufrufe;
      
          public Durchschnittsintelligenz()
          {
              iq_summe = 0;
              anzahl   = 0;
          }
      
          void tuwas( Object o )
          {
              // Intelligenz summieren, Aufrufe zählen:
              iq_summe += ((Student)o).getIQ();
              anzahl++;
          }
      
          double getDurchschnittsintelligenz()
          {
              return ((double)iq_summe)/anzahl;
          }
      }
      
      ...
      Liste  l;
      l.insert( ... ); // Container füllen
      l.insert( ... );
      ...
      Durchschnittsintelligenz durchschnitt = new Durchschnittsintelligenz();
      l.iteriere( durchschnitt );
      System.out.println( durchschnitt.getDurchschnittsintelligenz() );
      

      Verwendet man call back-Funktionen, kann man solche Konstruktionen nicht elegant schreiben, weil man auf irgendeine Form von statischen oder globalen Variablen und wilde Typkonvertierungen zurückgreifen muß.

      Hinweis für C++: Da hier (fast) alle Operatoren inklusive dem operator() (der wie ein Funktionsaufruf aussieht) überladen werden können, kann man hier auf die Namenskonvention für die aufgerufene Funktion verzichten, und gleich die runden Klammern nehmen. Dann erscheint das Funktionsobjekt tatsächlich wie eine Funktion.

      // Implementierung des Funktionsobjekts:
      class Durchschnittsintelligenz
      {
      private:
          int  iq_summe;
          private int  anzahl_aufrufe;
      
      public:
          public Durchschnittsintelligenz()
            : iq_summe( 0 ), anzahl( 0 )
          {
          }
      
          void operator()( Student o )
          {
              // Intelligenz summieren, Aufrufe zählen:
              iq_summe += ((Student)o).getIQ();
              anzahl++;
          }
      
          double getDurchschnittsintelligenz()
          {
              return ((double)iq_summe)/anzahl;
          }
      }
      
      ...
      Liste<Student>  l;
      l.insert( ... ); // Container füllen
      l.insert( ... );
      ...
      Durchschnittsintelligenz durchschnitt;
      l.iteriere( durchschnitt );
      cout << durchschnitt.getDurchschnittsintelligenz() << endl;
      

Nachdem man jetzt vier verschiedene Möglichkeiten hat, eine Iteration über die Elemente eines Containers zu realisieren, stellt sich die Frage nach den Vor- und Nachteilen.

Die Nutzung eines Cursors direkt im Container ist in der Praxis nicht sinnvoll, weil der Cursor für den gesamten Container gilt, und deshalb vom Anwender sichergestellt werden muß, daß auch nur ein Programmteil zu jedem Zeitpunkt iteriert. Weder kann man zwei ineinander geschachtelte Schleifen verwenden, um alle Elemente eines Containers mit allen anderen zu kombinieren (Kreuzprodukt), noch können zwei oder mehr threads eines Prozesses gleichzeitig über alle Elemente iterieren. Der einzige Vorteil dieser Vorgehensweise ist, daß sie mit wenig Quelltext auskommt und daran die prinzipiellen Mechanismen von Containern übersichtlicher dargestellt werden können.

Alle anderen vorgestellten Mechanismen können thread-sicher implementiert werden.

Cursor und Enumerationsobjekte sind nur sinnvoll, wenn innerhalb eines Containers von einem Element zum nächsten navigiert werden kann. Das ist bei einfach verketteten Listen vorwärts möglich, bei doppelt verketteten in beiden Richtungen; bei (offenen) Hashtabellen hängt es von der intern verwendeten Liste ab. Bei Bäumen dagegen bräuchte man für alle gängigen Durchläufe neben den Verweisen von jedem Knoten auf seine Kinder auch Verweise in der anderen Richtung von jedem Kindknoten zu seinem Vaterknoten. Das Durchlaufen einer einfach verketteten Liste in umgekehrter Reihenfolge ist ebenso wenig sinnvoll machbar wie der Durchlauf durch einen Baum, der keine Aufwärtsreferenzen von den Kinder zu den Vätern besitzt.

Bei den Varianten mit call back-Funktion und Funktionsobjekt dagegen muß der Container gar nicht wirklich in einer Schleife durchlaufen werden; oft ist es wesentlich einfacher solche Durchläufe rekursiv zu formulieren (beispielsweise ein in order-Durchlauf durch einen Binärbaum mit der Folge rekursiver Aufruf mit linkem Kind - Verarbeitung des aktuellen Elements - rekursiver Aufruf mit rechtem Kind ).

Bei Enumerationsobjekten leidet die Effektivität darunter, daß sehr viele Methodenaufrufe nötig sind. Mit call back-Funktionen kann man höhere Geschwindigkeiten erreichen. In C++ sind Funktionsobjekte meist noch schneller, weil alle nötigen Methodenaufrufe vom Compiler durch inline-Aufrufe umgesetzt werden können.

Abgesehen vom höheren Schreibaufwand beim Aufrufer sind in den meisten Fällen dann wohl Funktionsobjekte am sinnvollsten; wenn man den Schreibaufwand beim Anwender mit in Betracht zieht, können call back-Funktionen auch interessant sein.

In der Standard template library STL von C++, die ausschließlich auf templates aufbaut, ist es an vielen Stellen möglich, wahlweise Zeiger auf call back-Funktionen als auch Funktionsobjekte zu verwenden.

Mit call back-Funktionen oder Funktionsobjekten lassen sich leicht verschiedene Durchläufe (bei Bäumen beispielsweise in order, präorder, postorder und level order, oder verschiedene Richtungen bei Listen) durch je eine Methoden realisieren, oder eine gemeinsame Methode mit einem zusätzlichen Parameter, der die Art des Durchlaufs bestimmt.