Kompf.de > C/C++ > Artikel

STL Container

Martin Kompf

Container sind ein grundlegendes Element der STL. Welche gibt es und wie werden sie verwendet?

Container sind die Bestandteile der Standard Template Library (STL), welche zur Aufnahme anderer Objekte dienen. Die STL beinhaltet die sequentiellen Container vector, deque und list sowie die assoziativen Container set, multiset, map und multimap. Jeder dieser Container ist als Template realisiert, dass heisst er kann Objekte eines beliebigen Typs speichern. Die Datentypen string und wstring sind dagegen nicht als Template realisiert, jedoch handelt es sich bei ihnen genaugenommen auch um Container, die zur Aufnahme von Elementen des Typs char beziehungsweise wchar_t dienen. Deswegen werden sie im folgenden auch mit vorgestellt.

Sequentielle Container

vector

vector ähnelt am meisten dem Array Datentyp aus C, das heisst er bietet wahlfreien Zugriff auf alle seine Elemente. Er erweitert die C-Arrays allerdings um ein automatisches Speichermanagement sowie um die Möglichkeit, dass die Anzahl seiner Elemente dynamisch veränderbar ist. Die Vektorelemente werden linear im Arbeitsspeicher abgelegt. Damit ist vector auch der einzige Container, der den direkten Zugriff auf seine Elemente als ein zusammenhängendes C-Array erlaubt.

Allerdings kostet das Einfügen und Löschen von Elementen am Anfang und in der Mitte des Vectors relativ viel Zeit, da dafür unter Umständen große Teile des Vektors im Speicher verschoben werden müssen. Insbesondere ist diese Zeit nicht konstant, sondern wächst linear mit der Anzahl der Elemente im Vektor. Das Anhängen von neuen Elementen an das Ende des Vektors ist allerdings in konstanter Zeit möglich.

#include <vector>

using namespace std;

vector<int> v; // ein leerer Vector zur Aufnahme von int

// Anhängen von 3 Elementen
v.push_back(1); v.push_back(2); v.push_back(3);

cout << v[1] << endl; // gibt 2 aus

v[1] = 1000; // Ersetzen 2. Element

// Ausgabe kompletter Vector
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
// gibt 1 1000 3 aus
cout << endl;

// Benutzung als C - Array
memset(&v[0], 0, v.size() * sizeof(int));

string und wstring

string und wstring dienen ebenso wie vector zur sequentiellen Speicherung von Elementen. Sie sind allerdings optimiert zur Speicherung von Zeichenketten. string verwendet als Elementtyp char und kann damit als Ersatz der C-Strings vom Typ char * dienen. wstring dient zur Aufnahme von wide Characters des Typs wchar_t und findet seinen Einsatz bei der Verarbeitung Texte, die auf einem Zeichensatz mit mehr als 255 unterschiedlichen Zeichen beruhen (wie Japanisch oder Chinesisch).

string und wstring erlauben im Gegensatz zu char * eine weitaus komfortablere Behandlung von Zeichenketten. Insbesondere ist durch das integrierte Speichermanagement eine problemlose Veränderung der Länge der Zeichenkette jederzeit möglich.

#include <string>

string s("abcdef"); // erzeugt String aus char*
string t(80, ' '); // erzeugt String aus 80 Leerzeichen

s += t; // Hängt t an s an

char c = s[5]; // Das 6. Zeichen von s
        // unbestimmtes Resultat, wenn s kürzer als 6 Zeichen ist!
char d = s.at(5); // besser 

string::size_type n = s.size(); // Länge des Strings
const char *c = s.c_str(); // Konvertierung nach char* 

cout << "s = " << s << endl; // Ausgabe

deque

deque steht für »double-ended queue«. Dieser Container verhält sich fast genauso wie ein vector, er bietet wahlfreien Elementzugriff und verhält sich beim Einfügen oder Löschen von Elementen in der Mitte und am Ende genauso wie vector. Allerdings ist deque auch auf das Einfügen oder Löschen von Elementen am Anfang optimiert, so dass diese Operationen ebenfalls in konstanter Zeit möglich sind. Damit eignet sich deque sehr gut für die Implementierung von FIFO (first-in-first-out) und LIFO (last-in-first-out) Containern.

#include <deque>

using namespace std;

deque<string> q; // eine leere Queue zur Aufnahme von string

// Einfügen von drei Elementen am Anfang
q.push_front("eins"); q.push_front("zwei"); q.push_front("drei");

// Entfernen eines Elements am Ende
q.pop_back();

// Ausgabe komplette queue
copy(q.begin(), q.end(), ostream_iterator<string>(cout, ","));
// gibt drei,zwei, aus
cout << endl;

list

Bei der STL Implementierung handelt es sich um eine doppelt verlinkte Liste. Diese erlaubt die Traversierung der Liste in beide Richtungen. list ist optimiert für das Einfügen von Elementen an beliebiger Stelle. Damit sind im Gegensatz zu vector und deque Operationen wie das Sortieren der Liste sehr effektiv in konstanter Zeit möglich. Allerdings ist ein wahlfreier Zugriff auf die Elemente nicht möglich, sondern durch die Liste kann nur von Anfang bis Ende (oder umgekehrt) schrittweise mittels eines Iterators durchlaufen werden.

#include <algorithm>
#include <list>

using namespace std;

list<int> l; // eine leere Liste

// füge 10 zufällige Werte ein
insert_iterator<list<int> > ins(l, l.begin());
generate_n(ins, 10, rand);

l.sort(); // sortiere die Liste 

// Ausgabe komplette Liste
copy(l.begin(), l.end(), ostream_iterator<int>(cout, ","));
cout << endl;

Assoziative Container

set und multiset

set ist ein sortierter assoziativer Container. Die Elemente eines Sets sind alle vom Typ Key. Die Sortierung des Sets wird beim Einfügen neuer Elemente immer aufrecht erhalten. set eignet sich besonders für Mengenoperationen, wie includes (Teilmenge), set_union (Vereinigungsmenge) set_intersection (Schnittmenge), set_difference (Differenzmenge) und so weiter. set ist ein unique Container, das heisst jedes Element darf nur einmal enthalten sein. multiset hingegegen erlaubt das mehrfache Auftreten eines Elements.

#include <string>
#include <iostream>

#include <set>

using namespace std;

int main()
{
  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic",
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};

  set<string> A(a, a + N);
  set<string> B(b, b + N);
  set<string> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<string>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<string>(cout, " "));
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<string>(cout, " "));
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<string>(cout, " "));
  cout << endl;

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()));
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<string>(cout, " "));
  cout << endl;
}

Die Ausgabe dieses Programmes ist:

Set A: artichoke ephemeral isomer nugatory prosaic serif
Set B: artichoke flat frigate isomer prosaic this
Union: artichoke ephemeral flat frigate isomer nugatory prosaic serif this
Intersection: artichoke isomer prosaic
Set C (difference of A and B): ephemeral nugatory serif

map und multimap

map ist genauso wie set ein sortierter assoziativer Container. Im Unterschied zum Set sind die enthaltenen Elemente Wertepaare, die aus Key und Value bestehen. Das Verhalten (zum Beispiel die Sortierung) der Elemente wird dabei allein durch den Key bestimmt. Während map analog zu set fordert, dass jeder Key nur einmal enthalten sein darf, lässt multimap das mehrfache Auftreten gleicher Key-Werte zu.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
  map<string, int> phonebook; // eine Map
  // die Keys sind vom Typ string, die values vom Typ int

  // Füge drei Wertepaare hinzu
  phonebook["Karl"] = 4456388;
  phonebook["Klaus"] = 334566;
  phonebook["Heinz"] = 1244572;

  cin.tie(&cout);
  cout << "Name? ";

  string name;
  cin >> name;

  // suche nach name
  map<string, int>::iterator it;
  it = phonebook.find(name);

  if (it != phonebook.end()) {
    // Ausgabe von key (first) und value (second)
    cout << "Die Nummer von " << it->first << " ist " << it->second << endl;
  }
  else {
    cout << "Keine Nummer gefunden für " << name << endl;
  }
}

Nichtstandardisierte Assoziative Hash Container

Die standardmäßig in der STL enthaltenen assoziativen Container verwenden B-Trees, um ihre Elemente in sortierter Reihenfolge zu halten. Dieses Verfahren hat Performancenachteile beim Einfügen oder Löschen. Werden diese Operationen häufig ausgeführt und ist die Anzahl in einem Container gespeicherten Elemente sehr hoch, dann ist die Verwendung von Hash-Algorithmen zur Sortierung die bessere Wahl. Dazu gibt es in einigen STL-Implementierungen die Container hash_set, hash_multiset, hash_map und hash_multimap. Sie sind allerdings noch nicht durch das Standardisierungskomittee in die Standard C++ Library Spezifikation aufgenommen worden.

Die Effektivität von Hash Containern steigt und fällt mit der Wahl einer guten Hashfunktion. Diese muss in der Regel vom Anwender selbst bereitgestellt werden, was zusätzlichen Entwicklungsaufwand bedeutet.