Containertypen

In einem vorangegangenen Beispiel in Kapitel 3.9 tauchte in der Klasse Werkstueck ein Array mit Objekten vom Typ Rechteck auf, das 100 Elemente enthielt. Diese Festlegung beim Erstellen des Programms ist unglücklich. In vielen Fällen ist diese Grenze von 100 Elementen viel zu hoch, manchmal kann sie auch zu niedrig sein. Besser wäre es, wenn die Anzahl der gespeicherten Elemente erst zur Laufzeit des Programms nach Bedarf eingestellt wird. Eine Möglichkeit besteht darin, mit dem new-Operator bei jedem Hinzukommen eines Elements neuen Speicher dafür zu allokieren und die Alten Elemente plus das eine neue in diesen hineinzukopieren. Das ist aber sehr Zeit aufwändig, da der alte Speicherbereich verworfen wird und ein komplett neuer angelegt wird.

Günstiger ist es so genannte Containertypen zu verwenden. Das sind Objekte, die eine bestimmte Menge anderer Objekte eines bestimmten Types enthalten und verwalten können und die vor allem Mechanismen enthalten um einzelne Elemente hinzuzufügen, oder zu löschen.

Der erste hier behandelte Containertyp ist die Liste. Bei ihr haben die in dem Containerobjekt abgelegten Objekte eine besondere Eigenschaft: Eines dieser Objekte beinhaltet ein weiteres, dieses wiederum noch ein weiteres etc. Ähnlich wie russische Puppen sind sie ineinander gelegt. Man spricht auch von einfacher Verkettung der Objekte, da ein Objekt immer auf das nächste verweist. Das Containerobjekt stellt dann Methoden zur verfügung, um die miteinander verketteten Objekte zu verwalten, z.B.:

Beim Anhängen eines neuen Elements, wird dieses zunächst erzeugt. Dann wird es beim letzten Objekt der Liste registriert.

Der Zugriff auf ein Listenelement kann niemals direkt erfolgen, sondern man muss immer beim ersten Element beginnen und sich von einem zum nächsten hangeln, bis man bei dem gesuchten ankommt. Ferner ist der Speicherbereich, der für die Listenelemente reserviert ist in der Regel nicht zusammenhängend. Es liegt beim Erzeugen eines neuen Elements nicht fest, wo im Speicher es abgelegt ist. Deshalb kann die Lage eines bestimmten Elementes im Speicher bei Bekanntheit der Lage des ersten Elementes auch nicht aus seinem Index berechnet werden, sondern es müssen bei der einfach-verketteten Liste alle Elemente bis zum i-ten durchgegangen werden.

Der Vorteil von Listen ist, dass das Hinzufügen und Entfernen von Elementen schnell und einfach geht.

Wir wollen in diesem Abschnitt eine Containerklasse mit Listenelementen selber implementieren, um das Prinzip von Containerklassen zu verstehen.

C++ bietet jedoch eine Vielzahl an Containerklassen in der standard template library (STL) an. Eine von ihnen ist die Klasse vector. Diese werden wir nicht selber implementieren, aber wir werden hier ihre Benutzung erlernen. Insbesondere die Klasse vector wird uns die ganze Vorlesung in vielen Beispielen immer wieder begegnen.

Als zweiten Containertyp wollen wir Vektoren behandeln. Sie haben den Vorteil, dass dafür gesorgt wird, dass die in ihnen verwalteten Objekte in einem zusammenhängenden Speicherbereich liegen. Der Zugriff über den Index eines Elements ist dadurch möglich. Dafür ist das Hinzufügen und Entfernen von Objekten aufwändiger, da immer wieder dafür gesorgt werden muss, dass der Speicherbereich für die inneren Objekte zusammenhängend bleibt. Die Standard-Implementation von vector in C++ allokiert bei Hinzufügen eines neuen Elements aus Effizienzgründen nicht nur Speicher für dieses eine Element, sondern noch etwas Reserve für weitere, damit die zeitaufwendigen Speicherplatz-Verwaltungsoperationen nicht bei jedem Hinzufügen ausgeführt werden müssen. Das schöne an der Sache ist, dass wir diese Speicherverwaltungsstrategien nutzen können, ohne sie genauer zu verstehen.