Zum Inhalt springen
Topos Uranos
Deutsch

Datensätze

Zusammenfassung

Bisher speicherte jede Sammlung des Kurses Daten eines einzigen Typs: Noten, Körpergrößen, Zellen einer Tabelle. Die Entitäten eines Problems haben dagegen mehrere Merkmale verschiedener Typen: Studierende haben einen Namen und eine Note; ein Buch hat einen Titel, einen Autor und ein Jahr. Diese Lektion stellt den Datensatz vor, den zusammengesetzten Typ, den man als Programmierer mit struct selbst definiert, um diese Merkmale unter einem einzigen Namen zusammenzufassen. Sie beginnt mit dem Grund, warum es Datensätze gibt, der Zerbrechlichkeit paralleler Vektoren; sie fährt fort mit der Definition eines struct, seinen Feldern mit Anfangswert und dem Erzeugen von Datensätzen mit geschweiften Klammern und mit designierten Initialisierern; danach folgen Datensätze als Parameter und als Ergebnisse von Funktionen sowie Vektoren von Datensätzen, die man mit strukturierten Bindungen durchläuft und nach einem Feld sortiert und durchsucht, samt der Frage des stabilen Sortierens; und sie schließt mit der Kunst, ein Problem mit Typen zu modellieren, die seinen Gegenstandsbereich widerspiegeln.

Lernziele

  1. Ein struct mit Feldern und Anfangswerten definieren und Datensätze durch Initialisierung mit geschweiften Klammern erzeugen, auch mit designierten Initialisierern.
  2. Funktionen schreiben, die Datensätze empfangen und zurückgeben, und dabei die Art der Übergabe wählen.
  3. Einen Vektor von Datensätzen nach einem Feld sortieren und durchsuchen, mit std::ranges::sort, std::ranges::stable_sort und std::ranges::find samt einer Projektion, und ein stabiles Sortieren von einem nicht stabilen unterscheiden.
  4. Die Daten eines Problems mit Datensätzen modellieren und begründen, welche Felder und Typen man wählt.

Daten zusammenfassen

Parallele Vektoren

Angenommen, ein Programm soll für alle Studierenden einer Gruppe den Namen, die Note und das Alter speichern. Mit dem, was bis zur Lektion Tabellen behandelt wurde, liegt die Lösung auf der Hand: drei Vektoren, einer pro Merkmal, mit der Vereinbarung, dass der Index ii in allen dreien dieselbe Person bezeichnet: names[i], grades[i] und ages[i]. Man nennt sie parallele Vektoren. Eine Tabelle taugt nicht, weil ihre Zellen alle denselben Typ haben müssen, und ein Name ist keine Zahl.

C++-Programm
#include <algorithm>#include <cstddef>#include <print>#include <string>#include <vector>​int main(){    const std::vector<std::string> names{"Ana", "Luis", "Eva"};    std::vector<int> grades{6, 4, 7};    const std::vector<int> ages{19, 22, 20};    std::ranges::sort(grades);    for (std::size_t i{0}; i < names.size(); ++i) {        std::println("{}: Note {}, {} Jahre", names[i], grades[i], ages[i]);    }}
Ausgabe
Ana: Note 4, 19 JahreLuis: Note 6, 22 JahreEva: Note 7, 20 Jahre

Das Programm wollte die Studierenden nach Note sortieren und hat nur die Noten sortiert. Es kompiliert ohne Warnungen, und weder der Sanitizer für Speicherfehler, AddressSanitizer, noch der für undefiniertes Verhalten, UndefinedBehaviorSanitizer, hat etwas zu melden; trotzdem ist seine Ausgabe falsch: Ana hatte eine 6 und steht mit einer 4 da. Die Vereinbarung, die die drei Vektoren verband, steht nirgends, wo der Compiler sie lesen könnte, sodass nichts verhindert, sie zu brechen. Daraus folgt die Zerbrechlichkeit paralleler Vektoren: Jede Operation, die ein Element verschiebt, hinzufügt oder entfernt, muss in allen Vektoren wiederholt werden, gleich und in derselben Reihenfolge; und es genügt, einen zu vergessen, um die Daten stillschweigend zu verderben.

BeispielZeilen, die verrutschen, und Karteikarten, die sich als Ganzes bewegen

Drei parallele Vektoren gegenüber einem Vektor von Karteikarten, deren jede die drei Daten einer Person enthält.

Beweis

  1. Die Spalte 0 beschreibt eine Person: names[0], grades[0] und ages[0] sind Name, Note und Alter von Ana. Die Verbindung ist nur der Index.

  2. std::ranges::sort(grades) ordnet eine einzige Zeile neu. Die beiden anderen merken nichts davon: Die Spalte 0 vereint jetzt den Namen von Ana, die Note von Luis und das Alter von Ana, die niemandem gehören.

  3. Die Alternative: ein einziger Vektor, dessen Elemente Karteikarten sind. Jede Karte enthält die drei Daten einer Person, und die Verbindung zwischen ihnen ist keine Vereinbarung über Indizes mehr, sondern die Karte selbst.

  4. Nach Note zu sortieren bewegt ganze Karten: Die Karte von Luis rückt mit dem Namen und dem Alter, die darauf stehen, an die erste Stelle. Kein Datum kann sich von den anderen lösen, weil die Operation sie nicht getrennt sieht.

Wenn dem so ist, verlangt das Problem einen Typ, dessen Werte Karten sind: einen Wert, der einen Namen, eine Note und ein Alter enthält und der als Ganzes kopiert, einer Funktion übergeben, in einem Vektor gespeichert und sortiert wird. C++ liefert ihn nicht fertig, weil die Karten jedes Problems verschieden sind; aber es erlaubt, ihn selbst zu definieren. Dieser Typ ist der Datensatz.