Vektoren

Die Folge, die wächst

Einen Vektor anlegen und füllen

Die Lektion Arrays hat die indizierte Folge vorgestellt: Elemente desselben Typs, eines nach dem anderen, von null an nummeriert. Ihre moderne Form mit fester Größe, std::array<int, 7>, trägt die Größe im Typ, und der Compiler muss sie kennen. Nun weiß aber, wer ein Programm schreibt, das den Durchschnitt der Noten eines Kurses berechnet, nicht, wie viele Studierende der Kurs haben wird. Daraus folgt der Bedarf an einer Folge, deren Größe ein Datum wie jedes andere ist, das sich während der Ausführung ändert: Das ist der Vektor, std::vector<T>, aus dem Header <vector>, wobei T der Typ der Elemente ist.

#include <print>#include <vector>​int main(){    std::vector<int> squares{};    std::println("Am Anfang: Größe {}, leer: {}", squares.size(), squares.empty());    for (int k{1}; k <= 5; ++k) {        squares.push_back(k * k);    }    std::println("{}", squares);    std::println("Größe {}, erstes {}, letztes {}", squares.size(), squares[0], squares.back());    squares[1] = 0;    squares.pop_back();    std::println("{}", squares);}

Am Anfang: Größe 0, leer: true[1, 4, 9, 16, 25]Größe 5, erstes 1, letztes 25[1, 0, 9, 16]

Zeile 6 legt einen leeren Vektor ganzer Zahlen an: Anders als beim Array muss man nicht ankündigen, wie viele Elemente er haben wird. size() gibt zurück, wie viele er hat, und empty() sagt, ob er keines hat. Die Schleife der Zeilen 8 bis 10 fügt mit push_back fünf Quadrate hinzu; diese Funktion setzt ihr Argument ans Ende und erhöht die Größe um eins. Zeile 11 schreibt den ganzen Vektor mit der Formatierung von Ranges, die die vorige Lektion bei den Arrays benutzt hat. Der Zugriff über den Index ist der gewohnte, und squares.back() kürzt squares[squares.size() - 1] ab. Zeile 13 weist einem vorhandenen Element einen Wert zu, und Zeile 14 entfernt mit pop_back das letzte. Die Operationen dieser Lektion sind, zusammengefasst, die folgenden.

• v.push_back(x) fügt x am Ende hinzu; v.pop_back() entfernt das letzte (beim leeren Vektor ist das undefiniertes Verhalten).
• v.size() ist die Größe, vom Typ std::size_t, der vorzeichenlosen ganzen Zahl für Größen, die die Lektion Arrays vorgestellt hat; v.empty() ist gleichwertig mit v.size() == 0.
• v[i] und v.at(i) liefern das Element mit dem Index i, der i < v.size() erfüllen muss; v.front() und v.back() liefern das erste und das letzte und setzen voraus, dass der Vektor nicht leer ist.
• v.resize(n) lässt den Vektor mit n Elementen zurück: Es entfernt die überzähligen am Ende oder fügt am Ende Elemente hinzu, die wie mit leeren geschweiften Klammern initialisiert sind (Nullen bei Zahlen).

Wie bei den Arrays garantiert v[i] keine Prüfung, v.at(i) dagegen schon: Bei einem Index 7 und fünf Elementen hält es das Programm mit der Meldung vector::_M_range_check: __n (which is 7) >= this->size() (which is 5) an, die den Index und die Größe nennt. Der Mechanismus, der dieses Anhalten bewirkt, eine Ausnahme, wird in Programmieren in C++ II behandelt.

Geschweifte und runde Klammern

Der Kurs initialisiert alles mit geschweiften Klammern, und der Vektor ist der erste Typ des Kurses, bei dem es das Ergebnis ändert, die geschweiften durch runde Klammern zu ersetzen. Mit geschweiften Klammern sind die geschriebenen Werte die Elemente; mit runden Klammern ist die erste Zahl die Anzahl der Elemente und die zweite, falls vorhanden, der Wert jedes einzelnen.

#include <print>#include <vector>​int main(){    const std::vector<int> a{5};    const std::vector<int> b(5);    const std::vector<int> c{3, 7};    const std::vector<int> d(3, 7);    std::println("{} {} {} {}", a, b, c, d);}

[5] [0, 0, 0, 0, 0] [3, 7] [7, 7, 7]

a hat ein Element, die 5; b fünf Nullen; c die 3 und die 7; d drei Siebenen. Die Liste in geschweiften Klammern sagt also „das sind die Elemente“, und die runden Klammern bleiben dafür reserviert, n Kopien desselben Werts anzufordern, etwa einen Vektor von Zählern auf null.

Das letzte Element eines leeren Vektors

Ein leerer Vektor ist ein legitimer Fall (die Eingabe ohne Daten, der Filter, den niemand passiert), und jede Formel mit seiner Größe muss in diesem Fall überprüft werden; die tückischste ist v.size() - 1. Da v.size() eine vorzeichenlose ganze Zahl ist, ergibt das Abziehen von 1, wenn sie 0 ist, nicht $-1$, sondern dreht sich, wie in der Lektion Ganze Zahlen und ihre Darstellung gesehen, bis zum größten Wert von std::size_t herum.

#include <cstddef>#include <print>#include <vector>​int main(){    const std::vector<int> values{};    std::println("values.size() - 1 = {}", values.size() - 1);    // Falsche Schranke: Beim leeren Vektor ist die Bedingung wahr.    for (std::size_t i{0}; i <= values.size() - 1; ++i) {        std::println("{}", values[i]);    }}

values.size() - 1 = 18446744073709551615/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::const_reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

Die erste Zeile der Ausgabe ist $18\,446\,744\,073\,709\,551\,615$, das heißt $2^{64} - 1$, das größte std::size_t dieser Plattform. Daraus folgt, dass die Bedingung der Schleife, 0 <= 18446744073709551615, wahr ist und dass der erste Durchlauf values[0] aus einem Vektor liest, der kein Element 0 hat: undefiniertes Verhalten. Was man beobachtet, hängt wie bei den Arrays von den Optionen ab: Ohne Optimierung kompiliert, prüft die Bibliothek von GCC 15 den Index von operator[] und hält das Programm mit einer Zusicherung an, die __n < this->size() sagt; mit Optimierung verschwindet diese Prüfung, und die Schleife, die nicht rechtzeitig anhält, versucht dort zu lesen, wo es überhaupt kein Element gibt (unter Linux mit -O2 geprüft: Da der leere Vektor keinen Block hat, endet das Programm mit einem Speicherzugriffsfehler, ohne Meldung, die die Ursache erklärt). Die Korrektur besteht darin, die Schranke ohne Subtraktion zu schreiben, i < values.size(), was beim leeren Vektor von Anfang an falsch ist; und wo die Subtraktion nötig scheint, vorher values.empty() abzufragen.