Aller au contenu
Topos Uranos
Français

Tableaux de taille fixe

Résumé

Jusqu’ici, chaque donnée du cours a vécu dans sa propre variable, avec son propre nom ; mais de nombreuses données du même type, comme les températures d’une semaine, ne peuvent pas être parcourues par une boucle si chacune porte un nom différent. Cette leçon présente la première structure de données du cours, la séquence indexée : des éléments du même type, placés à des positions contiguës de la mémoire, numérotées à partir de zéro. En C++ moderne, elle s’écrit avec std::array, dont la taille est fixée à la compilation. On étudie sa déclaration, le type std::size_t des indices et les deux parcours, avec un indice et avec le for basé sur un intervalle. On établit la règle qui gouverne toute l’unité : un indice est valide s’il est compris entre 0 et la taille moins un, et, à chaque accès dans une boucle, cette validité se justifie par l’invariant. On montre ce qui se passe quand elle n’est pas respectée, ce qui est un comportement indéfini, et l’on compare [] à l’accès vérifié .at(). Enfin, on présente les tableaux C, pour lire le code d’autrui.

Objectifs d’apprentissage

  1. Déclarer, initialiser et parcourir un std::array avec des indices et avec le for basé sur un intervalle.
  2. Justifier, au moyen de l’invariant de boucle, qu’un indice est dans les limites à chaque accès.
  3. Distinguer l’accès avec [], que la norme ne vérifie pas, de l’accès avec .at(), qui est toujours vérifié, et expliquer quand chacun convient.
  4. Lire du code avec des tableaux C et expliquer leurs désavantages par rapport à std::array.

La séquence indexée

Beaucoup de données, un seul nom

Pour calculer la moyenne des températures d’une semaine avec ce qui a été enseigné jusqu’ici, il faudrait sept variables, monday, tuesday et ainsi de suite jusqu’à sunday, et une somme de sept termes. Avec celles d’une année, il en faudrait 365, et aucune boucle ne pourrait les parcourir, car dans le corps d’une boucle le nom d’une variable est toujours le même. Ce qui manque, c’est un nom pour l’ensemble et un numéro pour chaque élément, de sorte que le numéro puisse être une variable que la boucle fait avancer.

Une séquence indexée est exactement cela : un ensemble de nn éléments du même type, rangés les uns à la suite des autres dans des cases contiguës de la mémoire, et désignés par leur position, appelée indice. La mathématique connaît l’objet : une suite finie (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}), dans laquelle aia_i désigne l’élément de rang ii, ou un vecteur, comme ceux du cours Algèbre et géométrie I. En C++, on écrit a[i], et l’indice peut être n’importe quelle expression entière : 2, i, i + 1.

Pourquoi à partir de zéro

En C++, comme dans la plupart des langages actuels, le premier élément a l’indice 0, et le dernier, l’indice n−1n - 1. La raison n’est pas une convention capricieuse, mais la manière dont on trouve un élément : si la séquence commence à une certaine adresse mémoire et que chaque élément occupe ss octets, l’élément d’indice ii se trouve à l’adresse initiale plus i⋅si \cdot s. L’indice est donc un décalage : le nombre d’éléments qu’il faut sauter depuis le premier. Le premier est à zéro saut de lui-même.

Il s’ensuit la définition qui gouverne toute cette unité : dans une séquence de nn éléments, un indice ii est valide si et seulement si 0≤i<n0 \leq i < n. L’inégalité de droite est stricte, et elle est la source de l’erreur la plus fréquente avec les séquences, l’erreur de décalage d’une unité : écrire i≤ni \leq n là où il fallait écrire i<ni < n, ou commencer à 1 là où il fallait commencer à 0. Un indice égal à nn ne désigne pas le dernier élément, mais la case qui suit la séquence, et qui ne lui appartient pas.