C++ Standardbibliothek

Geschrieben von Johannes Kapfhammer.

Von allen erlaubten Sprachen an der SOI empfehlen wir sehr stark, C++ zu benutzen. Einerseits weil andere Sprachen langsamer sein können (z.B. Python), andererseits sind schon viele nützliche Algorithmen und Datenstrukturen in der Standardbibliothek enthalten (z.B. im Gegensatz zu C).

Dieses Skript setzt voraus, dass du die Grundlagen von C++ kennst, also Variablen, Kontrollblöcke (if, else, for, while) und wie man Funktionen definiert. Ziel, dieses Skriptes ist es, dir eine Einführung in die Standardbibliothek zu geben und wie sie dir hilft, allgemein SOI-Aufgaben schnell und mit effizientem Code zu lösen.

C++-Version und Compiler-Flags

Es gibt verschiedene Sprachversionen von C++, inoffiziell benannt nach Erscheinungsjahr (C++98, C++03, C++11, C++14 und C++17). An der SOI wird C++17 unterstützt.

Dieses Tutorial setzt C++11 voraus. Falls neuere Features benutzt werden, ist dies explizit vermerkt.

In den meisten modernen IDEs (Visual Studio 2017) oder mit einem neuen Compiler (GCC 6.1) sollte es keine Probleme geben.

Manche Compiler oder IDEs verwenden standardmässig aber noch ältere Versionen wie C++98 (z.B. CodeBlocks 2016, Clang). Am besten schaust du im Internet nach, wie man C++17 in deiner Entwicklungsumgebung aktiviert.

Bei g++ oder clang++ geht dies, in dem du das Flag -std=c++17 angibst. Falls du eine alte Compiler-Version hast, kannst du auch -std=c++11 probieren.

Ebenfalls empfehlen wir dir stark, Warnungen zu aktivieren und Debug-Flags zu setzen. Warnungen sind Hinweise vom Compiler, dass dein Code sehr verdächtig aussieht und vermutlich einen Bug enthält.

Die Flags für g++ und clang++ heissen: -std=c++17 -Wall -Wextra -g3 -ggdb3 -D_GLIBCXX_DEBUG

In den meisten IDEs gibt es irgendwo Compiler Settings, wo man entsprechende Flags setzen kann. Dazu mehr im Abschnitt “Debugging”.

Eingabe und Ausgabe

Wir nehmen an, dass du bereits mit der Ein- und Ausgabe in C++ vertraut bist. Lese diesen Abschnitt trotzdem durch um sicherzustellen, dass dir alle wichtigen Aspekte bekannt sind.

Das unten abgebildete Programm liest zwei Zahlen von der Standardeingabe und gibt die Summe dieser Zahlen aus.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int result = a + b;
    cout << result << '\n';
}

Falls du bisher printf/scanf benutzt hast, empfehlen wir dir, auf cin/cout umzusteigen, da das typsicher ist und heutzutage auch nicht langsamer.

Anstatt nur mit int funktioniert dieses Programm auch mit anderen Zahlentypen (int, long long, double), und sogar mit Zeichenketten (string). Alle Leerräume (also Leerzeichen, Tabulatoren und Zeilenumbrüche) vor dem eingelesenen Objekt werden ignoriert. Bei SOI-Aufgaben kannst du davon ausgehen, dass das Einlesen immer erfolgreich war, deshalb sind keine weiteren Checks nötig.

Ein Zeilenumbruch wird durch '\n' oder "\n" (ersteres ist ein einzelnes Zeichen, letzteres eine Zeichenkette der Länge 1) dargestellt. Manche Bücher oder Tutorials verwenden endl – das ist aber Zeilenumbruch zusammen mit flush, was zwar dazu führt, dass die Ausgabe sofort erscheint. Das verhindert aber das sogenannte “Buffering” und kann dazu führen, dass das Programm sehr viel langsamer abläuft. Falls das gewünscht ist, erzielt man den gleichen Effekt mit cout << '\n' << flush, was aber klarer ausdrückt, was passiert.

Falls die Eingaben und Ausgaben sehr gross sind, kann cin und cout wie folgt schneller gemacht werden:

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // code
}

Container

Der für die SOI mit Abstand nützlichste Teil der Standardbibliothek sind die Container und Funktionen dafür in <algorithm> (und <numeric>). Und der mit Abstand wichtigste Container ist der vector<>.

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.

Array Visualization

Array Visualization

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 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 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 zu einem vector. Er besitzt ebenfalls die oben besprochenen Funktionen. Zusätzlich besitzt er aber auch die Funktionen + (um zwei string’s aneinanderzuhängen) und substr (für einen Teilstring):

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.

Dictionary Visualization

Dictionary Visualization

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: code=c++   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: code=c++   occurrences.erase("stofl"); Löscht den Eintrag von "stofl".
  • Nächstgrösseres Element finden (kleinstes Element, welches \(\ge\) Wert) code=c++   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 genennt 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 alle Funktionen, die sie benötigen (wie z.B. lower_bound), dann kannst du auch unordered_map benutzen. Dafür ist unoredered_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 nicht wichtig, einen Wert für einzelne Elemente zu haben, sondern nur zu wissen, ob er 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”:

Visualisierung der Operationen push und pop

Visualisierung der 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 zu einem Stack eine sehr eingschränkte Datenstruktur. Sie unterstützt nur die Operationen “rein” (Fachbegriff: “enqueue”) und “raus” (Fachbegriff: “dequeu”).

Queue Operationen

Queue Operationen

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 eine 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, in dem 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.

Iteratoren

Alle Container haben eine Gemeinsamkeit: Sie speichern verschiedene Elemente ab. Mit diesen Elementen will man nun diverse Operationen ausführen, z.B. sie sortieren.

Der Vector hat aber keine Sortierfunktion. Es wäre auch unnötig, wenn jeder Container seine eigene Sortierfunktion hätte, denn es kommt nicht so drauf an, ob es ein vector oder eine deque ist. Sortieren geht immer ähnlich.

Stattdessen gibt es eine Funktion std::sort(), welche ein Paar von Iteratoren annimmt. Bevor die Algorithmen vorgestellt werden können, müssen wir uns also zuerst Iteratoren anschauen.

Iteratoren sind die Verallgemeinerung von einem Index oder einem Zeiger. Sie zeigen auf ein Element von einem Container und können dessen Wert abfragen. Und sie wissen, wie man auf das nächste/vorhergehende Element kommt.

Iteratoren erhält man über die Memberfunktionen begin() und end().

vector<int> v{5,2,3};
auto it = v.begin(); // it ist ein Iterator auf das erste Element
cout << *it << '\n'; // gibt 5 aus
++it; // Verschiebt den Iterator um eins nach hinten
cout << *it << '\n'; // gibt 2 aus
++it; // Verschiebt den Iterator nochmal um eins nach hinten
cout << *it << '\n'; // gibt 3 aus
--it; // Verschiebt den Iterator wieder nach vorne
cout << *it << '\n'; // gibt 2 aus

Achtung: end() ist eins hinter dem letzten Element! Das ist unter anderem so gemacht, damit man einen leeren Bereich angeben kann (also begin()==end()).

Iterator Visualization

Iterator Visualization

Iteratoren kann man unter anderem dazu benutzen, durch einen Vector durchzuiterieren:

for (auto it=v.begin(); it!=v.end(); ++it)
    cout << *it << ' ';

Genau der gleiche Code würde auch mit einem std::set<> funktionieren.

Im Abschnitt über den vector wurde die range-based for-Loop vorgestellt. Hinter den Kulissen benutzt sie Iteratoren:

for (auto& x : v)
    cout << x << ' ';

Manche Iteratoren lassen sich auch subtrahieren. So gibt it-v.begin() den Index des Iterators zurück und v.end()-v.begin() ist die Anzahl Elemente in einem Container. Umgekehrt ist v.begin()+i ein Iterator auf das \(i\)-te Element (bei der Addition muss aber einer der Operatoren eine Zahl sein).

Algorithmen

Zwei Iteratorenfirst und last definieren einen Bereich, der aus den Werten first,first+1,…,last-1 besteht.

Auf diese Werte kann man verschiedene Algorithmen anwenden.

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 eine Iterator auf das minimal respektive 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 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 solche 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.

Statische Hilfstypen

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 bestimmtem 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 benuzten. 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 …

Debugging

C++ hat die unangenehme Eigenschaft, dass normalerweise nicht überprüft wird, ob ein Element schon existiert.

vector<int> v{3,1,4};
v[10] = 5; // ???

Dieser Code kann machen, was er will. Manchmal stürzt er ab. Manchmal hängt er sich in einer Endlosschleife auf. Manchmal produziert er falsche Resultate. Und manchmal macht er das richtige. Nur eines ist sicher: Er hat einen Fehler drin.

Da die Performance darunter leidet, werden standardmässig keine Range-Checks ausgeführt.

Es ist aber möglich, diese zu aktivieren. Dann stürzt das Programm bei einem falschen Speicherzugriff ab und du kannst dir im Debugger anschauen, wo der Fehler passiert ist.

Dem g++ kann man das Flag -D_GLIBCXX_DEBUG übergeben.

Unter OS X wird normalerweise clang++ mit der libc++ verwendet. Dort kann mit dem Argument -D_LIBCPP_DEBUG=0 das Debugging aktiviert werden.

In Visual Studio muss _SECURE_SCL auf 1 definiert werden.

Wir empfehlen dir, diese wenn immer zu aktivieren!

assert

Extrem praktisch und häufig unterbenutzt ist assert(condition). Das ist eine Funktion, die einen bool (true/false) entgegennimmt und abstürzt, wenn es false war. Das ist praktisch, da du damit dokumentieren kannst, was dein Programm so voraussetzt.

Mal ein Beispiel: Gegen ein verbundener Graph, berechne die Distanz von start zu target. Hier sind mögliche asserts:

int main() {
  ...
  assert(1 <= n && n <= 1000);  // limits
  assert(1 <= m && m <= 10000); // limits
  for (...) {
     ... //  a und b sind die Endpunkte einer eingelesenen Kante
     assert(a != b);
     assert(0 <= a && a < n); // limits
     assert(0 <= b && b < n); // limits
     assert(a != b);  // Garantie: a!=b
  }
  bfs(start);
  assert(dist[target] != -1);  // target wurde gefunden
  assert(dist[target] < n); // distanz kann höchstens n-1 sein
  cout << dist[target] << '\n';
}

Vorteil ist nun, dass das Programm bei einer ungültigen Eingabe abstürzt (das verhinert z.B., dass du ein ungültiges Sample testest) oder du mögliche Programmierfehler sofort bemerkst (z.B. dass BFS nicht den ganzen Graph traversiert).

Das “wichtigste” assert in dem Beispiel ist assert(dist[target] != -1);. Ja, beim Testen würdest du das vielleicht bei der Ausgabe bemerken, aber wenn dein Program komplizierter ist und der BFS nur ein kleiner Teil davon ist, dann siehst du sofort, wo der Fehler ist.

STL

Manchmal wird die Standardbibliothek oder die Container/Algorithmen der Standardbibliothek mit “STL” (Standard Template Library) bezeichnet. Beide Benutzungen sind zwar gebräuchlich, aber falsch. Die STL war ursprünglich eine eigenständige Bibliothek, die dann in die C++-Standardbibliothek eingebunden wurde.

Mehr Informationen

Dieses Skript hat nicht als Ziel, eine vollständige Auflistung aller Features der Standardbibliothek zu sein. Es wurden auch nicht alle Funktionen vorgestellt. So besitzt vector auch die Funktionen clear() oder assign(), welche in gewissen Situationen praktisch sind.

Wir empfehlen folgenden Link, um sich mit der Standardbibliothek besser vertraut zu machen: http://en.cppreference.com/w/.