kramann.info
© Guido Kramann

Login: Passwort:










Informatik3
1 Vom_struct_zur_Klasse
..1.1 Vom_struct_zur_Klasse
..1.2 struct_Programm
..1.3 Klassen_Programm
..1.4 Offene_Fragen
..1.5 Historie
..1.6 Objektabstraktion
..1.7 OO_Kundenverwaltung
..1.8 Objektfaehigkeiten
..1.9 Formatierung
..1.10 Motivation
..1.11 Uebung1
..1.12 Uebung2
2 UML
..2.1 Volumenberechnung
..2.2 UML_Klassendiagramm
..2.3 Konstruktor
..2.4 Statische_Variable
3 Strings
..3.1 Klassenbibliotheken
..3.2 stringUML
..3.3 Uebung3
4 Initialisierungen
4 bluej
5 Zeiger_und_Arrays
..5.1 Zeiger
..5.2 Zeiger_und_Funktion
..5.3 Uebung4
6 Vererbung
..6.1 MesswerteUML
..6.2 MesswerteProgramm
..6.3 VererbungsProgramm
..6.4 Vector
..6.5 Uebung
7 Modifikatoren
..7.1 public_Vererbung
..7.2 protected_Vererbung
8 Listen_und_Templates
..8.1 Containertypen
....8.1.1 ListeUML
....8.1.2 ListeProgramm
..8.2 Templates
....8.2.1 Listentemplate
....8.2.2 STLvectorTemplate
..8.3 Uebung5
..8.4 Uebung6
..8.5 Uebung7
9 Java
..9.1 Uebung
..9.2 GettingStarted
..9.3 Animation
..9.4 Hybrid
..9.5 Threads
10 Delegation
11 LayoutProjekt
12 Fenster
13 Uebung
14 Zwischenprojekt
..14.1 Befehle
..14.2 Planung
..14.3 JNI
..14.4 JNIumsetzen
..14.5 Anwendungsklasse
..14.6 GUI01
..14.7 GUI02
15 Rasterlayout
..15.1 Bilder_Packages
..15.2 interfaces
..15.3 ArrayList
..15.4 clone
..15.5 Uebung
16 Nuetzliches
..16.1 Threads
..16.2 Animation
..16.3 RungeKutta
..16.4 Loesungsansatz
..16.5 Internetprogrammierung
....16.5.1 Codegenerierung
....16.5.2 PHP_Programmierung
....16.5.3 PHP_OOP
....16.5.4 Java
17 Algorithmen
..17.1 RungeKutta
..17.2 Loesungsansatz
..17.3 Evoopt
..17.4 Uebung12
..17.5 Uebung8_2014
..17.6 Ausdruecke
18 Uebung10
19 UML_ALT
..19.1 Flaechenberechnung
..19.2 UML_Flaechenberechnung
..19.3 Implementierung
..19.4 ListeUML
..19.5 ListenImplementierung
..19.6 Anwendung

8.1 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.

Listen

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

  • Anhängen eines neuen Elements
  • Einfügen eines neuen Elements nach dem i-ten Element
  • Entfernen des i-ten Elements
  • Löschen aller Elemente
Liste als russische Puppen vorgestellt

Bild 8.1-1: Stellen Sie sich Listenobjekte als ineinander geschachtelte russische Puppen vor.

Container-Objekt für eine Liste

Bild 8.1-2: Container-Objekt für eine Liste: Stellen Sie sich das Container-Objekt als Haus vor, in dem die Listenobjekte wohnen. Ein Listen-Objekt kennt immer nur seinen linken Nachbarn. Wird das Container-Objekt veranlasst, das Objekt mit Index 2 herauszugeben, so muss es immer bei Idex 0 beginnen und sich "durchfragen".

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.

Vektoren

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.