Synthese und Herausforderungen: zusammengesetzte Daten

Zusammenfassung

Diese Lektion schließt die sechste Einheit des Kurses ab, die den zusammengesetzten Daten gewidmet ist. Sie rekonstruiert die Kette der Begriffe, die von der indizierten Folge zum Datensatz führt, über die wachsende Folge, die Kosten eines Algorithmus, das Suchen und Sortieren und die Tabellen; sie trennt, was davon in jeder Sprache gilt, von dem, was C++ eigen ist; sie fasst das undefinierte Verhalten der Einheit zusammen, mit dem, was die Bibliothek anhält, was der Sanitizer anhält und was niemand meldet; sie wiederholt in ihrem Abschlusstest die Fertigkeiten des Eingangstests; und sie endet mit sechs Herausforderungen, die die ganze Einheit verbinden.

Lernziele

Sammlungen und Entitäten mit dem passenden Typ darstellen (Array, Vektor, Tabelle oder Datensatz) und die Wahl mit der Gestalt der Daten begründen.
Sammlungen mit korrekten Algorithmen verarbeiten, von Hand geschrieben und mit einer Invariante begründet oder aus der Bibliothek übernommen unter Beachtung ihrer Vorbedingungen.
Die Kosten eines Algorithmus durch Zählen seiner dominanten Operationen abschätzen und die Schätzung mit einer Messung überprüfen.
Das undefinierte Verhalten der Einheit erkennen (den Zugriff außerhalb der Grenzen, die ungültig gewordene Referenz, den überlaufenden Mittelpunkt, die verletzte Vorbedingung der Bibliothek) und das Programm ohne es neu schreiben.
Im Gelernten der Einheit zwischen dem unterscheiden, was in jeder Sprache gilt, und dem, was C++ eigen ist.

Was die Einheit erreicht hat

Die Einheit hatte sich vorgenommen zu lehren, wie man Sammlungen von Daten darstellt und mit den grundlegenden Algorithmen verarbeitet und dabei abschätzt, was sie kosten. Das ist gelungen, gestützt nur auf das, was die Einführung als bekannt vorausgesetzt hat: die Schleifen mit Invariante, die Funktionen und ihre Arten der Übergabe, die Arithmetik der ganzen Zahlen. Das Programm der Punktzahlen, das mit fünf Variablen die überzähligen Daten verschwieg, wird jetzt mit einem Vektor geschrieben; und die Frage nach Gleichständen, die mit allen Paaren für eine Million Elemente Minuten verlangte, wird durch Sortieren und Vergleichen benachbarter Elemente beantwortet.

Arrays

Die Lektion Arrays stellte std::array vor, die Folge fester Größe, deren Indizes von null an zählen, weil sie Versätze sind. Sie legte fest, dass der Index $i$ genau dann gültig ist, wenn $0 \leq i < n$ gilt, dass jeder Zugriff mit [] verlangt, dies mit der Schleifeninvariante zu beweisen, und dass der Zugriff außerhalb der Grenzen undefiniertes Verhalten ist, das .at() in einen definierten Abbruch verwandelt; sie führte std::size_t ein und lehrte, C-Arrays zu lesen.

Vektoren

Die Lektion Vektoren stellte die Folge vor, die mit push_back wächst, und legte fest, wann man eine Reihe speichern muss: wenn eine Entscheidung über ein Element von späteren Elementen abhängt. Sie stellte die kanonischen Durchgänge auf (akkumulieren, filtern, transformieren) mit ihren Invarianten und ihren Abkürzungen in der Bibliothek (std::ranges::count, std::ranges::max, std::ranges::fold_left), die Regel für die Übergabe eines Vektors und den Unterschied zwischen Größe und Kapazität, aus dem die im Mittel konstanten Kosten von push_back und das Ungültigwerden der Referenzen folgen, wenn der Vektor umzieht.

Die Kosten eines Algorithmus

Die Lektion Die Kosten eines Algorithmus fügte die zweite Frage hinzu: die dominante Operation im schlechtesten Fall zählen, nach der Wachstumsordnung einordnen, die Wirkung einer Verdopplung von $n$ vorhersagen und mit std::chrono::steady_clock messen, mit Optimierung, ohne Sanitizer, wiederholt und mit dem Median.

Suchen und Sortieren

Die Lektion Suchen und Sortieren begründete die binäre Suche mit ihrer Invariante und ihrem Maß; sie schrieb das Sortieren durch Auswahl und durch Einfügen und zählte ihre Vergleiche; sie stellte die Ranges-Algorithmen mit der Vorbedingung der Ordnung vor, die niemand prüft; und sie berechnete, wann es sich lohnt, vor dem Suchen zu sortieren.

Tabellen

Die Lektion Tabellen durchlief Tabellen zeilen- und spaltenweise, berechnete die Transponierte und das Matrixprodukt mit seinen kubischen Kosten, zählte Nachbarn, ohne die Ränder zu verlassen, und legte eine Tabelle in einem flachen Vektor ab, mit dem Index $i \cdot \mathit{columns} + j$ .

Datensätze

Die Lektion Datensätze ersetzte die parallelen Vektoren durch den struct, mit einem Anfangswert in jedem Feld; sie lehrte, Datensätze zu übergeben und zurückzugeben, sie mit einer Projektion nach einem Feld zu sortieren und zu suchen, mit std::ranges::stable_sort nach mehreren Kriterien zu sortieren und ein Problem mit Datensätzen zu modellieren, die Datensätze und Vektoren enthalten.