Les tableaux

Une liste Python sait combien elle contient d'éléments, refuse un indice trop grand, et grandit quand on lui ajoute quelque chose. Un tableau C ne fait aucune des trois. C'est une suite de cases de même taille, posées les unes après les autres en mémoire, et son nom ne désigne rien d'autre que l'adresse de la première.

Il n'y a donc ni longueur enregistrée, ni vérification d'indice, ni agrandissement. Ce qui reste est très rapide et très exposé : lire la case numéro huit d'un tableau qui en compte cinq est une opération parfaitement légale pour la machine, qui lit ce qui se trouve là. Ce chapitre installe les tableaux, et montre ce que coûte l'absence de garde-fou.

Déclarer et parcourir

int notes[5] réserve cinq cases contiguës de quatre octets, soit vingt octets d'un seul tenant. Les cases sont numérotées de 0 à 4, et il n'y a pas de case numéro 5.

Une liste d'initialisation évite de remplir case par case :

La recherche du maximum commence à la case 1, la case 0 servant de valeur de départ. Partir de zéro comme maximum donnerait un résultat faux dès qu'un tableau ne contient que des valeurs négatives, ce qui est la faute classique de cette boucle.

Un tableau non initialisé contient ce qui traîne

Dans ces pages, un tableau déclaré sans valeurs est rempli de zéros, pour que les programmes du cours soient reproductibles.
Un vrai programme C n'offre pas cette courtoisie : les cases contiennent les octets laissés par ce qui occupait cet endroit de la pile auparavant. Le programme semble alors marcher lorsqu'on le teste, et rend autre chose ailleurs. Une case se remplit avant d'être lue, sans exception.

Ce que le nom du tableau désigne

Le nom d'un tableau, employé comme valeur, vaut l'adresse de sa première case. C'est la règle qui surprend le plus, et elle explique tout le reste.

L'écart entre deux cases voisines vaut la taille d'un élément, donc quatre octets pour un int. C'est ce qui permet à la machine de trouver la case i sans rien chercher : son adresse est l'adresse du tableau plus i fois la taille d'un élément, une multiplication et une addition.

L'accès à une case coûte toujours la même chose

Atteindre t[0] et atteindre t[9999] demandent exactement le même travail : un calcul d'adresse. Aucun parcours, aucune recherche.
C'est la propriété qui distingue un tableau d'une liste chaînée, et elle vient directement du fait que les cases sont contiguës et de taille identique.

Le dépassement, et ce qu'il fait

L'interpréteur de ces pages nomme l'indice fautif et la taille du tableau. Un vrai programme C ne dit rien : il lit les quatre octets qui suivent la dernière case, les affiche comme un entier, et continue. Ces octets appartiennent à autre chose, souvent à une autre variable locale de la même fonction.

En écriture, c'est pire. notes[5] = 0 écrase quatre octets qui appartiennent à quelqu'un d'autre, et le programme se met à mal fonctionner ailleurs, dans une partie du code qui n'a rien à se reprocher. C'est le mécanisme du débordement de tampon, et c'est encore aujourd'hui l'une des premières causes de failles de sécurité dans les logiciels écrits en C.

À manipuler

Dans le bloc ci-dessus, essayer notes[-1] : l'interpréteur le refuse aussi, alors qu'un indice négatif est une adresse parfaitement calculable, quatre octets avant le début du tableau.
Remplacer ensuite la boucle des blocs précédents par for (int i = 0; i <= 5; i++) et l'exécuter : le seul signe extérieur est une case de trop, et c'est ainsi que se produisent presque tous les dépassements réels.

Passer un tableau à une fonction

Puisque le nom d'un tableau vaut une adresse, c'est cette adresse que la fonction reçoit. Elle ne reçoit pas une copie des cases, et elle ne reçoit pas la taille.

Deux conséquences, et elles vont dans des sens opposés.

double_tout modifie le tableau de l'appelant, alors que le chapitre précédent affirmait qu'une fonction ne peut pas modifier ce qu'on lui passe. Il n'y a pas de contradiction : ce qui a été recopié est l'adresse, et les deux fonctions travaillent donc sur les mêmes cases.

somme a besoin qu'on lui dise n, parce que rien dans t ne porte cette information. Écrire int t[] ou int *t dans l'en-tête revient exactement au même, et les crochets vides ne sont qu'une politesse envers le lecteur.

La taille voyage toujours à côté du tableau

Un tableau passé à une fonction a perdu sa taille en chemin. Il n'existe aucun moyen de la retrouver depuis l'intérieur de la fonction : ni un compte enregistré, ni une marque de fin, ni un sizeof qui répondrait juste.
D'où la signature que toute la bibliothèque standard emploie : le tableau, puis son nombre d'éléments. Les oublier fait de la fonction appelée le lieu du dépassement, alors que la faute est dans l'appel.

À calculer soi-même

Une case se trouve par un calcul d'adresse, et ce calcul se fait à la main une fois pour toutes.

Cases, octets et adresses

1.
Un tableau int t[10] occupe combien d'octets ?
2.
Quel est le numéro de la dernière case de ce tableau ?
3.
Le tableau commence à l'adresse 1000. À quelle adresse se trouve t[3] ?
4.
À quelle adresse se trouve la première case qui n'appartient plus au tableau ?
5.
Un tableau char m[10] commence à l'adresse 1000. À quelle adresse se trouve m[3] ?
6.
Une boucle for (int i = 0; i <= 10; i++) sur un tableau de 10 cases : combien de cases lit-elle en dehors du tableau ?
7.
Un tableau de 1000 int passé à une fonction : combien d'octets sont recopiés à l'appel ?

La dernière réponse est la raison pour laquelle passer un grand tableau à une fonction ne coûte rien en C, alors que passer une grande structure coûte sa taille entière.

Vérification

Vérification rapideon peut se reprendre

1.Que vaut le nom d'un tableau employé comme valeur ?

2.Quel est le numéro de la dernière case d'un tableau de 10 éléments ?

3.Que fait un vrai programme C quand il lit une case hors du tableau ?

4.Pourquoi une fonction qui reçoit un tableau a-t-elle besoin de sa taille ?

5.Une fonction reçoit un tableau et modifie t[0]. Le tableau de l'appelant change-t-il ?

Exercices type

Pourquoi la numérotation commence-t-elle à zéro ?

Parce que l'indice n'est pas un numéro d'ordre, c'est un décalage. L'adresse de la case i vaut l'adresse du tableau plus i fois la taille d'un élément, et la première case est celle qui est décalée de rien du tout.

Une numérotation commençant à un obligerait à retrancher un à chaque accès. Le choix n'est donc pas une convention arbitraire, c'est la conséquence directe du calcul d'adresse.

Comment écrire une fonction qui cherche une valeur dans un tableau et rend sa position ?

int position(int t[], int n, int cherchee) {
    for (int i = 0; i < n; i++) {
        if (t[i] == cherchee) return i;
    }
    return -1;
}

La valeur -1 sert de réponse « absente », parce qu'aucune position valide ne peut valoir -1. C'est la convention la plus répandue, et elle oblige l'appelant à tester le résultat avant de s'en servir comme indice.

Rendre 0 pour signaler l'absence serait une faute : zéro est la position de la première case.

Un programme lit 100 mesures dans un tableau de 100 cases, et fonctionne. Le même programme lit 101 mesures et se met à afficher des dates absurdes. Pourquoi les dates ?

Parce que la mesure surnuméraire a été écrite dans les quatre octets qui suivent le tableau, et que ces octets appartenaient à une autre variable de la même fonction. Si cette variable portait une date, la date a changé.

Le symptôme n'a aucun rapport avec la cause, et c'est ce qui rend ce genre de faute si long à trouver : le code qui affiche la date est parfaitement juste, et c'est le code qui remplit le tableau qui est fautif, cent lignes plus haut.

La parade est de contrôler l'indice avant d'écrire, ou de refuser d'écrire au-delà de la capacité annoncée.

La méthode

Écrire la taille une fois, dans une constante, et s'en servir partout : à la déclaration, dans les boucles, et dans les appels.
Parcourir avec for (int i = 0; i < n; i++), forme qui ne dépasse jamais.
Remplir avant de lire, parce qu'une case non initialisée contient ce qui traînait là.
Passer la taille avec le tableau, systématiquement, sans attendre d'en avoir besoin.
Contrôler l'indice avant d'écrire, dès qu'il vient d'un calcul ou d'une donnée extérieure.

Synthèse

Un tableau est une suite de cases contiguës de même taille. Sa longueur n'est enregistrée nulle part.
Les cases sont numérotées de 0 à n moins 1, parce que l'indice est un décalage.
L'adresse de la case i vaut l'adresse du tableau plus i fois la taille d'un élément, ce qui rend l'accès immédiat quel que soit l'indice.
Le nom du tableau vaut l'adresse de sa première case : une fonction reçoit cette adresse, pas une copie, et modifie donc les cases de l'appelant.
Un dépassement n'est signalé par personne hors de ces pages : il lit ou écrase ce qui se trouve à côté, et le désordre apparaît ailleurs.

Et ensuite

Le nom d'un tableau est une adresse, et une fonction qui reçoit cette adresse modifie l'original. Les pointeurs donnent leur nom à ces adresses, et permettent enfin d'écrire une fonction qui modifie une simple variable.