Vektoren und Listen
Die Standard Template Library (STL) enthält nützliche Container-Templates zur sequentiellen Speicherung von Objekten. Diese sind weitaus komfortabler einzusetzen als die aus ANSI-C bekannten (und berüchtigten) Arrays.
Oftmals ist der Softwareentwickler mit der Aufgabe konfrontiert, ein Feld oder eine Liste mehrerer Objekte zu speichern. In der STL gibt es dafür eine Reihe von Container-Templates, von denen hier vector und list vorgestellt werden sollen. So wird mittels
vector<int> a(10);
ein Vektor aus zehn Elementen vom Typ int deklariert, wogegen
list<StockItem> a;
eine leere Liste anlegt, die Objekte des Typs StockItem aufnehmen kann. Generell lassen sich beliebige Objekte in einem solchen STL-Container speichern, vorausgesetzt, dass sie kopierbar sind. Das heißt, sowohl Copy-Konstruktor als auch Assignment-Operator müssen definiert sein. Soll der Container sortierbar sein, so muss außerdem der Vergleichsoperator < für den Elementtyp vorhanden sein. Bereitet die Implementierung dieser Operatoren Schwierigkeiten, so lässt sich als Elementtyp auch ein Pointer auf ein Objekt verwenden, wie in
list<StockItem*> pa;
Die Verwendung von Pointern ist auch die einzige Möglichkeit, wenn polymorphe (voneinander abgeleitete) Objekte in einem Container gespeichert werden sollen.
Sowohl vector als auch list dienen zur Speicherung einer linearen Abfolge von Objekten. Die Unterschiede liegen in der Art der Implementierung. vector speichert seine Elemente ähnlich wie das aus C bekannte Array. Damit ist ein wahlfreier Zugriff auf jedes Element über den Indexoperator [] jederzeit möglich:
for (vector<int>::size_type i = 0; i < a.size(); ++i) { a[i] = i; }
Ein Nachteil von vector ist, dass beim Anhängen (push_back), Einfügen (insert) oder Löschen (erase) eines Elements unter Umständen Teile des Vektors im Speicher verschoben (kopiert) werden müssen. Diese Operationen kosten relativ viel Rechenzeit, insbesondere steigt diese Zeit mit wachsender Größe des Vektors an.
// ein 11. Element anhängen, die Größe wird automatisch erweitert // NICHT a[10] benutzen!!! a.at(10) würde Exception werfen a.push_back( -10); // ein Element vor dem 6. Element einfügen a.insert( a.begin() +5 , 9999);
Diesen Nachteil hat list nicht. Dafür ist bei list kein wahlfreier Zugriff auf einzelne Elemente via operator[] möglich. Listen ist gegenüber Vektoren also immer dann der Vorzug zu geben, wenn sehr oft Elemente verschoben, eingefügt oder gelöscht werden müssen und kein wahlfreier Elementzugriff notwendig ist.
Die Anweisung
list<int> l( a.begin(), a.end());
erzeugt eine list l, die den kompletten Inhalt des vector a enthält. Da das Entfernen und Verschieben von Listenelementen sehr effektiv ist, gibt es eine Reihe spezifischer Funktionen dafür. So wird mittels
l.sort();
die Liste sortiert, alle Elemente mit dem Wert 4 lassen sich durch
l.remove( 4);
entfernen.
Zum sequentiellen Zugriff auf alle Elemente einer Liste oder eines Vektors dienen Iteratoren. Die Memberfunktion begin() liefert einen Iterator auf das erste Element eines Containers zurück, end() zeigt hinter das letzte Element. Ein Iterator lässt sich genauso wie ein Pointer verwenden, die Ausgabe sämtlicher Elemente eines Vektors auf cout könnte also folgendermaßen programmiert werden:
vector<int>::const_iterator i; for (i = a.begin(); i != a.end(); ++i) { cout << *i << " "; }
Eleganter und kürzer ist allerdings die Verwendung des STL Algorithmus copy zusammen mit einem ostream_iterator:
copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
Im Rahmen dieses Beitrags kann nur auf eine kleine Anzahl der für Listen und Vektoren in der STL zur Verfügung stehenden Methoden eingegangen werden. Für eine detaillierte Referenz und weitere Beispiele sei auf den Standard Template Library Programmer's Guide verwiesen.