C++-Programmierung/ Die STL/ Container

Containerklassen

In diesem Kapitel soll das Konzept generischer Container vorgestellt werden. Als Container bezeichnet man einen Datentyp, der Daten gleichen Typs in einer bestimmten Struktur zusammenfasst. Generisch bedeutet natürlich, dass die Container als Klassentemplates realisiert sind und der Typ der gespeicherten Daten so frei gewählt werden kann.

Ein einfacher Container trägt den Namen array, es bekommt zwei Templateparameter. Der Erste ist der Datentyp der Array-Elemente, der Zweite ist die Anzahl der Array-Elemente. Ein std::array ist im Grunde nichts anderes, als ein gewöhnliches C-Array, mit den zusätzlichen Eigenschaften eines STL-Containers. Welche das sind, werden wir gleich klären.

Der wohl wichtigste Container ist std::vector. Er ist im Prinzip ein Array, dessen Größe sich zur Laufzeit anpassen lässt. Er bekommt als Templateparameter also nur den Datentyp, die Anzahl der Elemente ist dynamisch. Im folgenden sollen die STL-Container und ihre Verwendung kurz erläutert werden. Folgende Typen stehen zur Verfügung:

Sequentielle Containerklassen

• array
• vector
• list
• forward_list
• deque

Assoziative Containerklassen

• unordered_map
• unordered_multimap
• unordered_multiset
• unordered_set
• map
• multimap
• multiset
• set

Containeradapterklassen (keine C++ Standardbibliothek-Iteratoren)

• priority_queue
• queue
• stack

Container sind Behälter für Objekte. Dabei wird immer eine Kopie des Objektes in dem Container gespeichert. Das hat den Vorteil, dass sich die Speicherverwaltung vereinfacht, denn das Objekt verliert seine Gültigkeit, wenn das Containerobjekt aufgelöst wird. Der Nachteil liegt auf der Hand - durch das Erstellen einer Kopie geht Zeit und Speicherplatz verloren. Es gibt aber auch Wege, Zeiger in Containern zu speichern, was aber an späterer Stelle erläutert werden soll. Ein weiterer Vorteil bei der Verwendung von Containern ist ihre einheitliche Schnittstelle zu Elementfunktionen. Das vereinfacht den Einsatz von bestimmten Algorithmen, wie sie ebenfalls in der STL zu finden sind.

Containereigenschaften

Ein vector ist im Wesentlichen ein dynamisches Feld, das je nach Bedarf seine Größe dynamisch verändern kann. Allerdings sind dabei einige Dinge zu beachten. Auf ein beliebiges Objekt innerhalb des Feldes kann sehr effizient unter direkter Adressierung zugegriffen werden - man spricht daher auch von konstantem Aufwand, da sich die Zugriffszeit nicht ändert, wenn das Feldobjekt wächst. Ebenso ist das Anhängen und Entfernen von Objekten am Ende effizient, nicht so hingegen am Anfang oder in der Mitte (linearer Aufwand). Der Container deque beherrscht ebenso wie vector das schnelle Einfügen von Objekten am Ende und dazu noch am Anfang des Feldes. Hingegen ist auch hier das Einfügen von Objekten in der Mitte sehr aufwendig. Auch dieser Containertyp unterstützt Random-Access-Operatoren, d.h. der Zugriff auf ein beliebiges Element ist sehr effizient. Der dritte sequenzielle Container ist der list-Container. Dieser Typ unterstützt nur sogenannte Bidirectional-Iteratoren. Dadurch ist ein direkter Indexzugriff wie bei den anderen Containern nicht möglich. Der Vorteil dieses Containers ist allerdings das effiziente Einfügen und Entfernen von Objekten an beliebigen Positionen des Feldes. Durch diese deutlichen Unterschiede sollte sich der Programmierer schon bei der Planung des Programms darüber im Klaren sein, welcher Containertyp am besten zu seinen Anforderungen passt.

Grundlegende Mitgliedsfunktionen der sequentiellen Containerklassen

Sequenzielle Container besitzen Funktionen wie front() oder auch back(). Damit kann auf das erste bzw. letzte Element des Containers zugegriffen werden. Darüber hinaus gibt es Funktionen, die das Anhängen und Entfernen von Elementen am Ende eines Feldes erlauben (push_back(), pop_back()). Das Einfügen/Entfernen von Objekten am Anfang wird nur von den Typen deque und list beherrscht (mittels: push_front() und pop_front()). Das direkte Indizieren beherrschen vector und deque (mittels at() bzw. mit operator[]). Die folgende Tabelle soll dies vergleichend veranschaulichen.

	vector	deque	list
front()	x	x	x
back()	x	x	x
push_back()	x	x	x
pop_back()	x	x	x
push_front()	/	x	x
pop_front()	/	x	x
at()	x	x	/
operator[]	x	x	/

Darüber hinaus sind weitere Funktionen definiert, deren konkrete Implementierung vom jeweiligen Containertyp abhängig sind. Als Beispiel sei hier der vector-Container gewählt.

Funktionsname	Beschreibung
assign	Zuweisen von Elementen zum vector
begin	gibt einen Iterator auf das erste Element zurück
capacity	gibt Anzahl an Elementen zurück die vom vector aufgenommen werden können
clear	löscht alle Elemente
empty	gibt wahr zurück wenn Container leer ist
end	gibt einen Iterator auf das letzte Element zurück
erase	löscht das Element oder eine Reihe von Elementen
insert	fügt Elemente in den Container ein
max_size	gibt die maximal mögliche Zahl von Elementen des Containers an
rbegin	gibt einen reverse Iterator auf den Anfang zurück
rend	gibt einen reverse Iterator auf das Ende zurück
reserve	setzt eine minimale Kapazität des Containers
resize	ändert die Größe des Containers
size	gibt aktuelle Größe des Feldes zurück
swap	tauscht den Inhalt des Containers mit einem anderen

Adaptive Container

Dies sind spezielle Container, die auch Containeradapter genannt werden. Insbesondere lassen sich auf diese Container keine Iteratoren definieren. Der Zugriff erfolgt ausschließlich über die Elementfunktionen dieser Typen. In der STL finden sich folgende Typen:

• stack
• queue
• priority_queue