2.3.2. Listen und das Item-Container-Konzept

Lernziele

Das Item-Container-Konzept
Item-basierte strukturierte Typen
Abhängige und unabhängige Item-Typen
Zugriff auf Inhalte von Containern über Items
Iterieren über Strukturen mit forall_items und forall_rev_items
LEDA-Regel 13

Wie können wir auf ein Element an einer beliebigen Stelle einer Liste zugreifen? Wie können wir ein Element an einer beliebigen Stelle in eine Liste einfügen oder von dort herauslöschen? Warum sind Einfügen und Löschen von Elementen Operationen, die von LEDA immer mit konstant vielen Schritten durchgeführt werden können? (Im Gegensatz zu einem Array, wo wir bei einer Einfüge- bzw. Löschoperation Elemente nach rechts bzw. nach links verschieben müssen, um Platz zu schaffen bzw. ein entstandenes „Loch“ zu füllen.) Um diese Fragen zu beantworten, müssen wir uns ein wenig mit dem internen Aufbau von LEDA-Listen beschäftigen.

Betrachten wir dazu kurz Abbildung 2.12. Sie zeigt noch einmal die Liste, die das letzte Programm aufgebaut hat.

Abbildung 2.12. Eine Liste mit 5 Integer

Eine Liste mit 5 Integer

LEDA-Listen sind mit Hilfe von Containern aufgebaut. Diese Container speichern die eigentlichen Informationen, die der Datentyp vorhalten soll; in diesem Beispiel sind das einzelne ganze Zahlen. Darüber hinaus findet durch und in den Containern auch die Strukturierung des Datentyps statt; in einer linearen Liste ist das die Verlinkung der einzelnen Container zu einer linearen Abfolge.

Wir können aber nicht direkt auf diese Container zugreifen. Vielmehr können wir nur indirekt auf den Inhalt eines Containers über ein so genanntes Item zugreifen. Ein Item ist die Adresse eines Containers und daher mit einem gewöhnlichen Zeiger von C++ vergleichbar.

Haben wir ein Item, so können wir dadurch auf die Informationen innerhalb des zum Item gehörigen Containers zugreifen. Diese werden auch als Attribute des Items bezeichnet. Die Attribute sind also das, was klassischerweise als Listenelement bezeichnet wird. Wir können nur auf die Attribute zugreifen, nicht aber auf die strukturelle Information, die zusätzlich in den Containern steckt, um die Funktionalität des Datentyps herzustellen. Daher ermöglichen Items die Effizienz von Zeigern, schließen aber deren Möglichkeiten zum Missbrauch aus. Anders gesagt kann ein Zugriff über Items niemals den internen Aufbau der Datenstruktur durcheinander bringen.[14]

Viele Datenstrukturen von LEDA sind nach diesem Item-Container-Konzept aufgebaut. Wörterbücher (Klasse dictionary) und Prioritätswarteschlangen (Klasse p_queue) etwa sind weitere Beispiele. Diese werden in der Kategorisierung der LEDA-Typen als item-basierte strukturierte Typen bezeichnet.

Die zu den jeweiligen Datentypen gehörigen Items bilden ebenfalls einen eigenständigen LEDA-Typ. Items von linearen Listen etwa bilden den Typ list_item. In der Kategorisierung der LEDA-Typen werden solche Objekte als Item-Typ bezeichnet. Hier wird zwischen abhängigen und unabhängigen Item-Typen unterschieden: Abhängige Item-Typen gehören zu Containern, die nur in einer größeren Struktur vorkommen können, wie z. B. Listen-Items, deren zugehörige Container nur innerhalb einer Liste leben können. Unabhängige Item-Typen dagegen verweisen auf Container, die für sich alleine, außerhalb einer umfassenden Struktur, lebensfähig sind. Beispiele hierfür sind beliebig große ganze Zahlen (Klasse integer) und Brüche (Klasse rational), zu denen wir erst später kommen werden.

Nun aber genug des akademischen Vorgeplänkels, wir wollen nun endlich Items in Aktion sehen! Füllen wir dazu eine Liste mit denselben Zahlen wie im vorigen Programm und greifen wir dann über Items darauf zu. Wir erhalten ein Item, indem wir die Liste darum bitten. Über ein solches Item können wir dann den Inhalt eines Containers lesen und schreiben. Wir können vor und hinter dem Container einen weiteren Container einfügen. Von dem Item aus gelangen wir über geeignete Methoden der Klasse list zu Items, die auf die benachbarten Container verweisen. Items dienen also auch dazu, über eine Struktur zu iterieren.

Filename: ListItemConcept.C
#include <LEDA/list.h>
#include <iostream>

using leda::list;
using leda::list_item;
using std::cout;
using std::endl;


int main() 
{
  list<int> L;

  list_item it_back,it_front;

  it_front = it_back = L.push(1);
  it_back = L.insert(5, it_back, leda::after); 
  L.insert(2, it_back); // implicit leda::after
  it_front = L.insert(3, it_front, leda::before);
  L.insert(5, it_front, leda::before);


  list_item it;

  forall_items(it,L)
      cout << L[it] << " ";
  cout << endl;

  forall_rev_items(it,L)
      cout << L[it] << " ";
  cout << endl;

  it = L.first();
  L[it] = 7;

  for(it = L.first(); it != nil; it = L.succ(it))
      cout << L.contents(it) << " ";
  cout << endl;
  
  for(it = L.last(); it != nil; it = L.pred(it))
      cout << L.contents(it) << " ";
  cout << endl;
  
  int counter = 0;
  for(it = L.first(); counter < 2 * L.size(); 
      it = L.cyclic_succ(it), counter++)
      cout << L.contents(it) << " ";
  cout << endl;
}

Die Ausgabe des Programms ist

5 3 1 5 2
2 5 1 3 5
7 3 1 5 2
2 5 1 3 7
7 3 1 5 2 7 3 1 5 2

Der Aufbau der Liste geschieht hier über ein explizites Einfügen von Containern an bestimmten Stellen. Das erste push() liefert ein Item it zurück, das auf den gerade eingefügten Container verweist. Von diesem Item aus können wir durch

L.insert(x, it, position);

weitere Container einfügen. Dabei kann durch Angabe von leda::after bzw. leda::before festgelegt werden, ob der neue Container hinter bzw. vor dem zum Item it gehörigen Container in die Liste eingefügt wird. Fehlt die Angabe, so wird hinter dem entsprechenden Container eingefügt.

insert() liefert selbst wieder ein Item zurück, das auf den gerade eingefügten Container verweist. Durch Aufsammeln dieses Items und Verwendung im nächsten Aufruf von insert() kann die Struktur nacheinander aufgebaut werden. In obigem Beispiel verweisen die Variablen it_front bzw. it_back vom Typ list_item während der Aufbauphase immer auf den ersten bzw. letzten Container.

Danach wird hier nur noch über das Listen-Item it auf den Inhalt der Liste zugegriffen. Das Makro

forall_items(it, L) { ... }

lässt it nach und nach auf jeden Container der Liste verweisen. Dadurch kann dann auf den zugehörigen Container zugegriffen werden. forall_items iteriert dabei von vorne nach hinten über die Liste.

Dagegen iteriert das Makro

forall_rev_items(it, L) { ... }

von hinten nach vorne über die Liste.

Haben wir nun ein Item it, so können wir auf das zugehörige Attribut, also den Inhalt des Containers, durch den Operator [] zugreifen und dieses Attribut auch abändern:

L[it] = new_value;

Das ist die Art und Weise, wie der Wert von Listenelementen verändert werden kann. Es gibt darüber hinaus noch die Methode assign(it, val), mit der ebenfalls der Wert neu gesetzt werden kann. Diese liefert im Gegensatz zu [] keine Referenz auf das Attribut zurück, so dass sie nicht in Kette verwendet werden kann.

Auf den Inhalt eines Containers kann auch durch die die Methode

L.contents(it);

zugegriffen werden; sie liefert zu einem Item it eine Kopie des Inhalts des Listencontainers, also eine Kopie der zum Item gehörigen Attribute. Das ist hier die im jeweiligen Container gespeicherte ganze Zahl.

[Tip] Tipp

Zur Iteration über eine Struktur sind die Makros forall_items und forall_rev_items dem forall-Makro vorzuziehen, weil dabei keine Zuweisung mit Wertkopie an die Laufvariable durchgeführt wird, was je nach Typparameter der Struktur eine zeitaufwändige Operation sein kann! Für den Zugriff im Rumpf des Makros sollte dann der Operator [] verwendet werden, da contents() ebenfalls eine Kopie anlegt und zurückliefert.

Die Methode

L.first();

liefert ein Item, das auf den ersten Container der Liste verweist; entsprechend liefert

L.last();

ein Item, das auf den letzten verweist.

Die Methoden

L.succ(it);
L.pred(it);

liefern zu einem Item it ein Item, das auf den nachfolgenden bzw. vorangehenden Container verweist, s. Abbildung 2.13. Wenn wir dabei schon auf dem letzten bzw. ersten Container stehen, liefern sie den Wert nil. Beim Typ list handelt es sich also um doppelt verkettete Listen, die von vorne nach hinten und umgekehrt durchlaufen werden können.[15]

Abbildung 2.13. Iteration in einer Liste mit Hilfe von Items

Iteration in einer Liste mit Hilfe von Items

Das Item it verweist auf einen Container. Davon ausgehend kann mit den Methoden pred(), succ(), cyclic_pred() und cyclic_succ() in der Liste vorwärts bzw. rückwärts gewandert werden.

Die Listen sind sogar zirkulär und können durch die Methoden

L.cyclic_succ();
L.cyclic_pred()

im Kreis herum vorwärts bzw. rückwärts durchlaufen werden. Diese Methoden arbeiten wie succ() und pred(), nur dass sie beim letzten bzw. ersten Container nicht nil, sondern wieder ein Item auf den ersten bzw. letzten Container liefern. Die letzte Schleife in obigem Programm läuft somit zweimal in der Liste vorwärts im Kreis herum.

Ein genauerer Blick auf die forall-Makros

Die Anweisungen in LEDA, mit denen über Containerstrukturen iteriert werden kann, sind durch Makro-Expansion verwirklicht. Beispielsweise wird das Makro

forall_items(it, L) { ... }

zum Iterieren über eine Liste in eine for-Schleife von C++ expandiert. Der Expansionsprozess führt eine neue Variable loop_it vom Typ list_item ein und initialisiert diese mit einem Item, das auf den ersten Container der Liste verweist; für jede Schleife wird vom Expansions-Prozess eine weitere solche Variable erzeugt. In jeder Iteration der Schleife wird it der Wert von loop_it zugewiesen, loop_it wird weitergeschoben, und der Rumpf der Schleife wird ausgeführt. Die Schleife endet, wenn it den Wert nil hat.

Der Expansionsprozess erzeugt folgenden Code:

for(list_item loop_it = (L).first();
    it = loop_it, loop_it = (L).succ(loop_it); it )
      { ... }

Das zieht eine wichtige Regel nach sich: Ist f() irgendeine Funktion, die eine list zurückliefert, so sollte das Makro nicht in folgender Form benutzt werden:

forall_items(it, f()) { ... }

Das besagt auch LEDA-Regel 13:

[Warning] Warnung

Das Datentypargument in einer Iterationsanweisung darf kein Funktionsaufruf sein, der ein Objekt des Datentyps erzeugt, sondern nur ein Objekt des Datentyps selbst.

Übungen

Übung 12.

Erklären Sie mit Hilfe Ihres Wissens über die Makro-Expansion der forall-Makros LEDA-Regel 11, LEDA-Regel 12 und LEDA-Regel 13.



[14] An dieser Stelle kommen erfahrene Programmierer leicht in Verwirrung, weil bei anderen Bibliotheken, wie z. B. der STL, dieselben Bezeichnungen andere Bedeutung haben. Dort ist der Begriff „Container“ die Bezeichnung für die gesamte Struktur; diese besteht aus „Elementen“, die manchmal auch „Items“ genannt werden. Über diese Elemente kann mit Hilfe von „Iteratoren“ iteriert werden.

[15] Die Abbildung verleitet zu der Annahme, dass die Items verkettet sind. Es sind dies aber die Container. Das sind jedoch Details der Implementierung, die für den Benutzer unerheblich sind.




Imprint-Dataprotection