Zum Inhalt springen
Topos Uranos
Deutsch

Arrays

Zusammenfassung

Bisher hat jedes Datum des Kurses in einer eigenen Variablen gelebt, mit eigenem Namen; aber viele Daten desselben Typs, etwa die Temperaturen einer Woche, lassen sich nicht mit einer Schleife durchlaufen, wenn jedes einen anderen Namen trägt. Diese Lektion stellt die erste Datenstruktur des Kurses vor, die indizierte Folge: Elemente desselben Typs an zusammenhängenden Positionen des Speichers, von null an nummeriert. Im modernen C++ schreibt man sie mit std::array, dessen Größe beim Kompilieren feststeht. Behandelt werden seine Deklaration, der Typ std::size_t der Indizes und die beiden Arten des Durchgangs, mit Index und mit dem bereichsbasierten for. Es wird die Regel aufgestellt, die die ganze Einheit bestimmt: Ein Index ist gültig, wenn er zwischen 0 und der Größe minus eins liegt, und bei jedem Zugriff in einer Schleife wird diese Gültigkeit mit der Invariante begründet. Es wird gezeigt, was geschieht, wenn sie nicht erfüllt ist, nämlich undefiniertes Verhalten, und [] wird mit dem geprüften Zugriff .at() verglichen. Schließlich werden die C-Arrays vorgestellt, damit man fremden Code lesen kann.

Lernziele

  1. Ein std::array deklarieren, initialisieren und mit Indizes und mit dem bereichsbasierten for durchlaufen.
  2. Mithilfe der Schleifeninvariante begründen, dass ein Index bei jedem Zugriff innerhalb der Grenzen liegt.
  3. Den Zugriff mit [], den der Standard nicht prüft, vom Zugriff mit .at(), der stets geprüft wird, unterscheiden und erklären, wann sich welcher eignet.
  4. Code mit C-Arrays lesen und ihre Nachteile gegenüber std::array erklären.

Die indizierte Folge

Viele Daten, ein einziger Name

Um mit dem bisher Gelernten den Durchschnitt der Temperaturen einer Woche zu berechnen, bräuchte man sieben Variablen, monday, tuesday und so fort bis sunday, und eine Summe aus sieben Termen. Mit denen eines Jahres wären es 365, und keine Schleife könnte sie durchlaufen, weil im Rumpf einer Schleife der Name einer Variablen immer derselbe ist. Es fehlt ein Name für das Ganze und eine Nummer für jedes Element, sodass die Nummer eine Variable sein kann, die die Schleife voranschreiten lässt.

Eine indizierte Folge ist genau das: eine Menge von nn Elementen desselben Typs, die hintereinander in zusammenhängenden Speicherzellen abgelegt und durch ihre Position bezeichnet werden, den sogenannten Index. Die Mathematik kennt das Objekt: eine endliche Folge (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}), in der aia_i das Element an der Stelle ii bezeichnet, oder einen Vektor wie die des Kurses Algebra und Geometrie I. In C++ schreibt man a[i], und der Index kann ein beliebiger ganzzahliger Ausdruck sein: 2, i, i + 1.

Warum von null an

In C++ hat, wie in den meisten heutigen Sprachen, das erste Element den Index 0 und das letzte den Index n−1n - 1. Der Grund ist keine launische Konvention, sondern die Art, wie ein Element gefunden wird: Beginnt die Folge an einer bestimmten Speicheradresse und belegt jedes Element ss Bytes, so liegt das Element mit dem Index ii an der Anfangsadresse plus i⋅si \cdot s. Der Index ist also ein Versatz (Offset): die Anzahl der Elemente, die man vom ersten aus überspringen muss. Das erste ist null Sprünge von sich selbst entfernt.

Daraus folgt die Definition, die diese ganze Einheit bestimmt: In einer Folge von nn Elementen ist ein Index ii genau dann gültig, wenn 0≤i<n0 \leq i < n gilt. Die rechte Ungleichung ist streng, und sie ist die Quelle des häufigsten Fehlers bei Folgen, des Off-by-one-Fehlers: i≤ni \leq n zu schreiben, wo i<ni < n hätte stehen müssen, oder bei 1 zu beginnen, wo bei 0 hätte begonnen werden müssen. Ein Index gleich nn bezeichnet nicht das letzte Element, sondern die Zelle, die auf die Folge folgt und nicht zu ihr gehört.