C++ Standardbibliothek

std::vector<T>

Ein vector ist ein dynamisches Array, das effizienten Zugriff auf Elemente per Index erlaubt und wessen Grösse während der Ausführung des Programms verändert werden kann. Wenn man von “Array” oder “Liste” spricht, dann meint man meistens einen vector.

Zunächst einmal ein Beispiel.

vector<int> v;
v.push_back(3); // [3]
v.push_back(2); // [3,2]
v.push_back(5); // [3,2,5]

Dieser Code erstellt einen leeren vector und fügt drei Elemente hinten an. Das “dynamische” daran ist, dass du nicht im Voraus angeben musstest, wie viel Speicher du benötigst. Der vector passt seine Grösse automatisch an deine Bedürfnisse an.

Hast du bereits einen vector, kannst du auf seine Elemente mit [index] zugreifen:

cout << v[0] << '\n'; // 3
cout << v[1] << '\n'; // 2
cout << v[2] << '\n'; // 5

Oft möchte man auch über alle Elemente des Vectors durchgehen, oder im Computer-Jargon “darüber iterieren”.

Eine (unpraktische) Variante, dies zu tun, ist eine Schleife, bei der ein Index von 0 bis v.size() hochgezählt wird:

for (size_t i = 0; i < v.size(); ++i) {  // manchmal auch int statt size_t
  cout << v[i] << '\n';
}

Wir empfehlen dir aber, stattdessen eine sogenannte “range-based for-Loop” zu benutzen:

for (auto x : v) {
  cout << x << '\n';
}

Das “auto” bedeutet hier, dass x automatisch den richtigen Typen bekommt. Du hättest hier auch int schreiben können. auto hat aber den Vorteil, dass es immer funktioniert, auch wenn du deinen vector z.B. von vector<int> auf vector<long long> änderst. Generell ist die Richtlinie, immer auto zu benutzen, ausser man ist gezwungen (weil es sonst einen Compiler-Fehler gibt) oder man möchte explizit betonen, welchen Typ die Variable gerade hat. In diesem Fall wissen wir, dass v ein vector<int> ist, deshalb ist das int unnötig.

Falls du die Elemente ändern möchtest, musst du eine Referenz verlangen (dies mit dem Zeichen “&”):

for (auto& x : v) {
  x += 10;
}

Bisher hast du nur die push_back-Funktion gesehen. Es gibt aber auch pop_back(), welches das letzte/hinterste Element löscht, sowie back() welches das letzte Element zurückgibt.

vector<int> v;
v.push_back(5);
v.push_back(2);
cout << v.back() << '\n'; // 2
v.pop_back();
cout << v.back() << '\n'; // 5

Zum Erstellen eines Vectors gibt es mehr Möglichkeiten als nur wiederholt push_back aufzurufen. Der folgende Code erstellt einen vector mit fünf Elementen:

vector<int> v = {2,4,2,5,1};

Eine andere Möglichkeit ist es, die Anzahl Elemente und einen Anfangswert zu übergeben

vector<int> v(10);     // v=[0,0,0,0,0,0,0,0,0,0] (10 Elemente)
vector<int> v(10, 5);  // v=[5,5,5,5,5,5,5,5,5,5] (10 Elemente)

Ein vector kann beliebige Typen enthalten, der gewünschte Typ kann als Template-Parameter angegeben werden: vector<int> für eine Liste aus ints, oder vector<string> für eine Liste von Zeichenketten.

Hier ein Beispiel für eine typische Eingabe einer Aufgabe: Auf der ersten Zeile steht $n$, danach folgen $n$ Zahlen $a_1,a_2,\dots,a_n$. Der Code, der dies einliest, würde wie folgt aussehen:

int n;
cin >> n;
vector<int> v;
for (int i=0; i<n; ++i) {
  int a;
  cin >> a;
  v.push_back(a);
}

Oder, etwas kürzer:

int n;
cin >> n;
vector<int> v(n); // v hat schon n Elemente, die auf 0 initialisiert sind
for (int i=0; i<n; ++i)
  cin >> v[i]; // ohne das (n) existiert v[i] nicht

Solltest du schon mit den Landau-Symbolen aus dem Artikel über Algorithmen vertraut sein: push_back, pop_back und size() sind $\mathcal O(1)$. (Genau genommen sind push_back und pop_back nur amortisiert $\mathcal O(1)$, d.h. nur im Durchschnitt.)

Ein vector ist mit Abstand der häufigste Container an der SOI und in der Regel auch der schnellste. Als Faustregel: Wenn etwas mit vector geht, dann sollst du ihn auch benutzen.

Falls du klassische C-Arrays kennst (int a[100]; oder int *a = new int[n]();), empfehlen wir dir, an der SOI nur vector zu benutzen. Er kann alles, was diese auch können – und mehr:

• Optionale Range-Checks
• Einfache Benützung von <algorithm>
• Unterstüzt Einfügen/Löschen am Ende

In der Praxis ist ein vector dennoch nicht langsamer als C-Arrays.

std::string

Ein string ist ziemlich ähnlich wie ein vector. Er besitzt ebenfalls die oben besprochenen Funktionen. Zusätzlich besitzt er aber auch die Funktionen + (um zwei strings aneinanderzuhängen) und substr (gibt einen Teilstring zurück):

string a = "stofl";
string b = a+a;
cout << b << '\n'; // stoflstofl
b[4] = 'a';
cout << b << "\n"; // stofastofl
string c = b.substr(3, 4);
cout << c << "\n"; // fast

std::map<Key, Value>

Eine mögliche Interpretation von einem vector ist, dass er gewissen Zahlenwerten (den Indices zwischen $0$ und der Länge $n$) einen Wert zuweist. Eine std::map verallgemeinert dieses Konzept und weist einem beliebigen Schlüssel (Key) einen Wert (Value) zu. In anderen Sprachen ist map auch als assoziatives Array, Dictionary oder Hashtable bekannt.

Das funktioniert auch dann, wenn Schlüssel und Wert beide vom Typ int sind. Ein Vector müsste so gross sein wie der grösste Schlüssel, aber eine map speichert nur die relevanten Wertepaare.

map<int, int> m; // m={},           m.size()==0
m[3] = 5;        // m={3: 5},       m.size()==1
m[7] = 2;        // m={3: 5, 7: 2}, m.size()==2
m[3] = 4;        // m={3: 4, 7: 2}, m.size()==2

Eine sehr nützliche Eigenschaft ist, dass eine Map automatisch Werte einfügt, sobald der Schlüssel angefordert wird. Diese sind dann auf dem Default-Wert (0 für ints).

Damit kann man z.B. zählen, wie oft jedes Wort der Eingabe vorkommt:

int n;
cin >> n;
map<string, int> occurrences;
for (int i=0; i < n; ++i) {
  string word;
  cin >> word;  // lese "word" ein
  occurrences[word] += 1; // Erhöhe die Anzahl Wörter "word" um eins.
                          // falls "word" das erste ist, ist die Anzahl 0
}

Über eine map kann man ähnlich wie für einen vector mittels der range-based for-Loop iterieren:

for (auto p : occurrences) {
  // p.first: key
  // p.second: value
  cout << "word " << p.first << " was found " << p.second << " times\n";
}

Wenn du durch eine map iterierst, sind die Elemente immer aufsteigend sortiert.

Die Variable p ist hier vom Typ pair<string, int>.

Mit C++17 geht auch Folgendes (genannt Structured Bindings, falls du es genauer nachlesen möchtest):

for (auto [word, count] : occurrences) {
  cout << "word " << word << " was found " << count << " times\n";
}

Einfügen und Zugriff in einer map sind jeweils $\mathcal O(\log n)$, wobei $n$ die Anzahl Elemente ist.

Einige fortgeschrittene Operationen in einer map sind:

• Testen, ob ein Element vorhanden ist:

  if (occurrences.count("stofl")) {
    // found stofl at least once
  }
  

  In diesem Fall könnte man auch occurrences["stofl"] > 0 schreiben, aber das hat den Nachteil, dass "stofl" eingefügt wird! Falls du dann über alle Wörter iterierst, kommt der Eintrag, dass "stofl" 0 mal vorkommt.

• Einträge löschen:

  occurrences.erase("stofl");
  

  Löscht den Eintrag von "stofl".

• Nächstgrösseres Element finden (kleinstes Element, welches $\ge$ Wert)

  cout << "lexicographically smallest word starting with 's':"
       << occurrences.lower_bound("s")->second << '\n';
  

  Alle diese Operationen sind ebenfalls $\mathcal O(\log n)$.

std::unordered_map<Key, Value>

Es stand oben zwar geschrieben, dass eine map manchmal auch Hashtable genannt wird. Das ist aber genau genommen falsch. Eine Hashtable ist eine mögliche Datenstruktur, welche sich fast wie eine map verhält. Allerdings mit dem Unterschied, dass die Reihenfolge der Elemente nicht aufsteigend sortiert ist.

Benötigst du diese Sortiertheit nicht und auch keine der Funktionen, die sie benötigen (wie z.B. lower_bound), dann kannst du auch unordered_map benutzen. Dafür ist unordered_map ein bisschen schneller: Einfügen und Zugriff sind hier jeweils (im Erwartungswert) $O(1)$ unabhängig von der Anzahl Elemente.

std::set<T>/std::unordered_set<T>

Manchmal ist es nicht wichtig, einen Wert für einzelne Elemente zu haben, sondern nur zu wissen, ob ein Element drin ist. Also eigentlich map<T, empty>. Das macht ein set. Es entspricht dem Konzept einer Menge aus der Mathematik.

set<int> s;
s.insert(2);
cout << s.count(5) << "\n"; // 0
s.insert(5);
cout << s.count(5) << "\n"; // 1
s.insert(5);
cout << s.count(5) << "\n"; // 1

Hier kannst du ebenfalls mit count(x) testen, ob ein Element vorhanden ist.

std::deque<T>

Eine deque kann alles, was ein Vector auch kann, aber zusätzlich noch push_front und pop_front. Man zahlt dafür aber mit einer etwas langsameren Zugriffszeit. Im Normalfall reicht ein vector aus.

std::stack<T>

Zunächst einmal: Was ist ein Stack? Es ist eine Datenstruktur mit den Operationen “push” und “pop”:

Stelle dir einen Bücherstapel vor. Anfangs ist dieser leer. Du kannst folgende Aktionen ausführen:

• push(x): Lege das Buch x auf den Stapel
• pop(): Entferne das oberste Buch
• top(): Schaue dir das oberste Buch an

Diese Datenstruktur scheint zwar sehr simpel zu sein im Vergleich zu den anderen, die wir bisher gesehen haben, aber sie taucht erstaunlich häufig auf.

Nun gibt es zwei Arten, einen Stack zu benutzen.

1. Benutze einen vector und schreibe push_back für push, back anstatt top() sowie pop_back anstatt pop.
2. Verwende std::stack und benutze push/pop/top.

Mit einem stack beschränkst du dich auf die Operationen des Stacks, was manchmal wünschenswert sein kann. Für die SOI empfehle ich aber, direkt einen vector zu benutzen, da es leichter ist, diesen auszugeben (für Debugging) und den Code zu optimieren (Caching, etc.).

std::queue

Eine Queue ist ähnlich wie ein Stack eine sehr eingschränkte Datenstruktur. Sie unterstützt nur die Operationen “rein” (Fachbegriff: “enqueue”) und “raus” (Fachbegriff: “dequeue”).

Du kannst sie dir wie eine Schlange vor der Kasse vorstellen: Es stehen neue Leute hinten an (rein), und es wird der Vorderste bedient und er wird von der Schlange entfernt (raus).

Der Unterschied zum Stack ist hier, dass das Einfügen und das Rausnehmen an unterschiedlichen Enden passieren. Stacks werden manchmal LIFO genannt (last in first out: Das letzte Element, das rein gepusht wurde, kommt bei pop auch wieder zuerst raus). Queues sind im Gegensatz dazu FIFO (first in first out: der Erste, der an der Kasse kam, wird auch als erstes bedient).

In C++ heissen die Funktionen nochmal anders und analog zum Stack:

• push(x): Person x kommt an die Kasse (rein).
• pop(): Bediene die erste Person (raus).
• front(): Die vorderste Person (die, die als erste raus darf)
• back(): Die hinterste Person (die letzte, die rein kam)

Auch hier gibt es zwei Möglichkeiten, das in C++ umzusetzen.

1. Benutze eine deque und schreibe push_back für push und pop_front für pop. front und back bleiben gleich.
2. Verwende std::queue und benutze push/pop/front/back.

Auch hier wäre meine allgemeine Empfehlung, eine deque zu benutzen.

std::priority_queue

std::priority_queue ist ein etwas spezielles Konzept. Sie unterstützt folgende Operationen:

• push(x): Fügt Element x ein.
• top() gibt das grösste Element zurück
• pop() entfernt das grösste Element

Mehr Operationen sind nicht möglich, du kannst z.B. nicht über alle Elemente iterieren.

Stelle dir vor, du hast eine TODO-Liste und jede deiner Aufgaben hat eine Priorität. Du schreibst alle Aufgaben mit ihrer Priorität auf einen eigenen Zettel und wirfst sie in einen magischen Sack. Du kannst schnell neue Aufgaben hinzufügen, indem du diese in den Sack legst. Immer wenn du aus dem magischen Sack einen Zettel herausnimmst, ist das der Zettel der höchsten Priorität. Der magische Sack ist eine priority_queue.

priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << "\n"; // 7
q.pop();
cout << q.top() << "\n"; // 5
q.pop();
q.push(6);
cout << q.top() << "\n"; // 6
q.pop();

Um anstelle vom Minimum ein Maximum zu bekommen, kann man Folgendes machen:

priority_queue<T, vector<T>, greater<T>> q;

Oder konkret, für einen int:

priority_queue<int, vector<int>, greater<int>> q;

Der Trick passiert im dritten Argument. Hier kann man seine eigene Definition des <-Operators angeben. Wir übergeben den >-Operator, die Elemente werden also umgekehrt sortiert.

Noch eine kleine Bemerkung: Priority-Queues kannst du auch mit std::set oder std::map nachbauen, da sie immer sortiert sind. Im Gegensatz zu Stacks und Queues empfehle ich das im allgemeinen Fall nicht, da das in der Praxis um einiges langsamer ist. Es kann aber sein, dass du mehr Funktionalität benötigst (z.B. Testen, ob ein Element schon drin ist). Dann ist es natürlich legitim, auf set/map umzusteigen.

std::sort()

Sehr nützlich ist sort(). Wie der Name nahelegt, sortiert diese Funktion die Werte in aufsteigender Reihenfolge.

vector<int> v{5,2,3};
sort(v.begin(), v.end());
// v=={2,3,5}

sort nimmt noch ein drittes Argument an, die Vergleichsfunktion. Standardmässig ist dies std::less. Gibt man stattdessen std::greater an, wird die Liste absteigend sortiert.

sort(v.begin(), v.end(), greater<int>());
// v=={5,3,2}

Die Laufzeit von sort ist als $\mathcal O(n \log n)$ garantiert.

min_element, max_element

Diese Funktionen geben einen Iterator auf das minimale beziehungsweise maximale Element zurück.

vector<int> v{3,1,4,1,5,9,2,6};
auto it = min_element(v.begin(), v.end());
// it==v.begin()+1, *it==1
it = max_element(v.begin(), v.end());
// it==v.begin()+5, *it==9
sort(v.begin(), v.end(), greater<int>());

reverse

Reverse dreht die Reihenfolge der Elemente um.

vector<int> v{3,1,4,1,5,9,2,6};
reverse(v.begin(), v.end());
// v=={6,2,9,5,1,4,1,3}

unique

Unique verschiebt doppelte Elemente an das Ende. Der Bereich muss vorher sortiert sein. Um die doppelten Elemente zu löschen soll erase benutzt werden.

vector<int> v{3,1,4,1,3,3};
sort(v.begin(), v.end());
// v=={1,1,3,3,3,4}
auto it=unique(v.begin(), v.end());
// v=={1,3,4,1,3,3}, it==v.begin()+3
v.erase(it, v.end());
// v=={1,3,4}

lower_bound, upper_bound

Diese Funktionen führen eine binäre Suche aus. Siehe dazu das Skript über binäre Suche.

Beide Funktionen setzen voraus, dass der Bereich bereits sortiert aufsteigend ist.

lower_bound(first, last, x) gibt das kleinste Element zurück, das $\ge x$ ist (oder last, falls kein solches existiert).

upper_bound(first, last, x) gibt das kleinste Element zurück, das $> x$ ist (oder last, falls kein solches existiert).

Es gibt eine funktion binary_search, diese gibt aber nur zurück ob ein bestimmtes Element existiert. Sie ist deshalb sehr häufig nutzlos.

pair

Beim Iterieren über eine map tauchte zum ersten Mal ein pair auf:

for (auto p : occurrences) {
  // p.first: key
  // p.second: value
  cout << "word " << p.first << " was found " << p.second << " times\n";
}

Ein Pair, deutsch Paar, speichert zwei Werte ab. Ein pair<int, int> speichert zwei Ganzzahlen, ein pair<string, double> eine Zeichenkette und eine Kommazahl. Auf den ersten Wert kann man mit .first zugreifen, auf den zweiten mit .second (beachte dass es keine Funktionen sind, deshalb keine Klammern dahinter).

Pairs erstellt man so:

pair<int, string> p(4, "hi");  // Konstruktor
pair<int, string> p = {3, "hi"};  // Braced initializer
auto p = make_pair<int, string>(3, "hi");  // make_pair
auto p = make_pair(3, 4); // automatische Typ-Inferenz
// (Achtung: make_pair(3, "hi") erstellt <int, const char*>)

Praktisch ist ein pair dann, wenn man nicht zwei Variablen benutzen kann. Zum Beispiel als Wert in einem vector: Gewichtete Graphen werden typischerweise als vector<vector<pair<int, int>>> abgespeichert. Oder in einer Priority-Queue als priority_queue<pair<int, int>> (wenn man z.B. immer das Grösste anschauen möchte, aber eigentlich am Index interessiert ist – dann ist .first die Grösse und .second der Index). Oder eben, wenn wir durch eine map durchiterieren (.first ist der Schlüssel, .second der Wert).

Besonders nützlich ist, dass der <-Operator für pair überladen (definiert) ist. Erste Priorität hat der erste Wert, ist dieser gleich der zweite Wert.

Beim Abschnitt über die map haben wir ebenfalls folgende Syntax (ab C++17) kennen gelernt:

for (auto [word, count] : occurrences) {
  cout << "word " << word << " was found " << count << " times\n";
}

Das geht auch in “normalem” Code:

pair<int, string> mouse(5, "stofl");
auto [age, name] = mouse;

Dann ist age ein int und name ein string.

Erstellen kann man pairs mit den {}-Klammern, aber auch mit der Funktion make_pair.

tuple

Was tun, wenn wir nicht nur zwei Werte, sondern drei Werte speichern wollen? Wir könnten ein Pair von Pairs benutzen!

pair<int, pair<string, double> > mouse{5, {"stofl", 12.5}};
auto [age, name_and_length] = mouse; // C++17
auto [name, length] = name_and_length; // C++17

Für vier Werte könnten wir pair<T1, pair<T2, pair<T3, T4>>> benutzen.

Es gibt aber eine bessere Variante: tuple. Ein Tupel kann beliebig viele Werte zu verschiedenen Typen abspeichern.

tuple<int, string, double> mouse{5, "stofl", 12.5};
auto [age, name, length] = mouse; // C++17

Es ist auch möglich, auf ein Element mit einem bestimmten Index zuzugreifen:

auto name = get<1>(mouse);

Erstellen kann man tuples mit den {}-Klammern, aber auch mit make_tuple.

Ein kleines Wort der Warnung: In echtem Code wird es nicht so gerne gesehen, überall pairs und tuples zu benutzen. Das Phänomen hat sogar einen eigenen Namen erhalten: Primitive Obsession. Für komplexere Objekte kann es sich lohnen, eigene structs zu erstellen. In SOI-Code hingegen haben tuples den Vorteil, schnell geschrieben zu sein.

array

Falls das tuple viele Elemente hat und alle den selben Typ besitzen, kann man stattdessen ein array benutzen. array<int, 10> ist z.B. ein Array von 10 ints. Das Array ist nicht dynamisch, hat also immer die selbe Länge.

Über ein array kann man auch iterieren.

Hier ein Beispiel des Floodfill-Algorithmus (ohne Bounds-Check, d.h. es muss sichergestellt sein, dass es ums Bild rum einen Rahmen hat, welcher nicht target_color ist):

void floodfill(int y, int x, int target_color, int replacement_color) {
  if (pixel[y][x] != target_color)
    return;
  pixel[y][x] = replacement_color;
  array<pair<int, int>, 4> directions { {1,0}, {-1,0}, {0,1}, {0,-1} };
  for (auto [dy,dx] : directions)
    if (pixel[y+dy][x+dx] == target_color)
      floodfill(y+dy, x+dx, target_color, replacement_color)
}

An dieser Stelle war es praktisch, ein array anstelle eines vectors zu benutzen, da es um einiges effizientert ist (kein dynamischer Speicher, alles Konstanten, was dem Compiler viele Optimierungsmöglichkeiten eröffnet, z.B. die Schleife mit 4 if-Statements zu ersetzen – genannt “loop unrolling”).

Anders als C-Arrays, darf man ein array von einer Funktion returnen.

Ebenfalls lässt es sich gut Debuggen …