Les structures

Un point a deux coordonnées, un étudiant a un nom et une note, un paquet réseau a une adresse et une charge utile. Jusqu'ici, ces valeurs auraient voyagé séparément : deux tableaux parallèles, trois paramètres à chaque appel, et la certitude qu'un jour l'indice 7 de l'un correspondra à l'indice 8 de l'autre.

Une structure rassemble ces valeurs sous un seul nom, et leur donne une place contiguë en mémoire. C'est la dernière construction dont le langage a besoin pour bâtir tout le reste : les listes, les arbres, les tables, les fichiers. Ce chapitre installe les structures, et montre les deux choses qui les distinguent des tableaux : elles se copient entièrement, et leur taille n'est pas la somme de leurs champs.

Rassembler ce qui va ensemble

La déclaration struct Point { ... }; ne crée aucune variable : elle décrit un type, c'est-à-dire une disposition en mémoire. Le point-virgule après l'accolade fermante fait partie de la déclaration, et c'est l'oubli le plus fréquent du chapitre.

struct Point origine; crée ensuite une variable de ce type, et origine.x désigne son premier champ.

Pourquoi pas deux tableaux parallèles

Un tableau des abscisses et un tableau des ordonnées font le même travail tant que personne ne se trompe. Le jour où une insertion décale l'un et pas l'autre, chaque point devient faux, et rien ne le signale.
Une structure rend cette faute impossible à commettre : les deux coordonnées sont un seul objet, qui se copie, se passe et se range d'un seul geste.

Une structure se copie entièrement

C'est la différence la plus importante avec un tableau, et elle se voit en trois lignes.

b = a recopie tous les octets. Les deux structures sont ensuite indépendantes, et modifier l'une ne touche pas l'autre. Un tableau, lui, ne se copie pas ainsi : t2 = t1 est même refusé par le compilateur, parce que le nom d'un tableau est une adresse et non une valeur.

À manipuler

Ajouter struct Point *c = &a; puis c->x = 77; avant l'affichage, et relancer : cette fois a change, parce que c ne contient pas une copie mais l'adresse de a.
Les deux lignes qui précèdent résument tout le chapitre : la structure se copie, le pointeur vers la structure ne copie rien.

Le point et la flèche

La règle tient en une ligne : le point sur une structure, la flèche sur un pointeur vers une structure. p->x est d'ailleurs une abréviation exacte de (*p).x, et les parenthèses y sont obligatoires, ce qui explique l'existence de la flèche.

Une fonction qui reçoit une structure reçoit une copie

deplace_copie ne modifie rien, et le compilateur n'y trouve rien à redire : la fonction travaille sur sa copie, exactement comme pour un entier.
C'est l'inverse d'un tableau, dont le nom se réduit à une adresse et dont la fonction appelée modifie bel et bien les cases. Deux constructions voisines, deux comportements opposés, et aucun message pour les distinguer.

La taille n'est pas la somme des champs

struct Mixte contient un octet et quatre octets, et en occupe huit. Trois octets ont été ajoutés entre les deux champs, et ils ne contiennent rien.

La raison est matérielle : un processeur lit un entier de quatre octets à une adresse multiple de quatre. Le compilateur place donc chaque champ à une adresse alignée sur sa taille, quitte à laisser des trous, et complète la fin de la structure pour que la suivante, dans un tableau, tombe elle aussi juste.

À manipuler

Dans struct Large, inverser les deux champs pour obtenir double d; char c; et relancer : la taille ne change pas, seize octets dans les deux cas, parce que la fin est complétée jusqu'au multiple de huit.
Essayer ensuite struct Trois { char a; int n; char b; }; et comparer avec struct Trois { char a; char b; int n; }; : la seconde occupe quatre octets de moins, pour exactement les mêmes champs. Ranger les champs du plus grand au plus petit est la règle qui évite ces trous.

Un tableau de structures

Un tableau de structures reste un tableau : les fiches se suivent en mémoire, et passer de l'une à l'autre revient à avancer de sizeof(struct Etudiant) octets. C'est ce qui rend le parcours aussi rapide que celui d'un tableau d'entiers.

Une structure sur le tas

Cette fonction est le contraire de celle du chapitre sur les pointeurs, qui rendait l'adresse d'une variable locale et produisait un pointeur pendant. Ici la structure vit sur le tas, elle survit donc au retour, et c'est l'appelant qui doit la libérer.

sizeof(struct Point) est la seule écriture juste de la taille à demander : compter huit octets à la main serait faux dès qu'un champ serait ajouté.

À calculer soi-même

Une structure se dimensionne avant d'être écrite.

Tailles, décalages et remplissage

1.
Une structure faite de deux int occupe combien d'octets ?
2.
Une structure faite d'un char puis d'un int occupe combien d'octets ?
3.
Combien d'octets de remplissage cette structure contient-elle ?
4.
Une structure faite d'un char puis d'un double occupe combien d'octets ?
5.
Une structure faite d'un char, d'un int, puis d'un char occupe combien d'octets ?
6.
Les mêmes champs rangés en char, char, int occupent combien d'octets ?
7.
Un tableau de 100 fiches de 20 octets occupe combien d'octets ?
8.
Dans un tableau de fiches de 20 octets commençant à l'adresse 5000, à quelle adresse commence la fiche d'indice 3 ?

Les deux questions sur l'ordre des champs valent la peine d'être retenues : à champs identiques, un rangement du plus grand au plus petit économise un tiers de la place. Sur un million de fiches, cela se voit.

Vérification

Vérification rapideon peut se reprendre

1.Que crée la déclaration struct Point { int x; int y; }; ?

2.Quelle est la différence entre p.x et p->x ?

3.Que fait b = a entre deux structures ?

4.Une fonction reçoit une structure en paramètre et modifie un de ses champs. L'original change-t-il ?

5.Pourquoi struct { char c; int n; } occupe-t-elle 8 octets et non 5 ?

Exercices type

Quand passer une structure, et quand passer son adresse ?

Passer l'adresse dès que la fonction doit modifier la structure, et dès qu'elle est volumineuse : chaque passage par valeur recopie tous ses octets, cadre d'appel compris.

Passer la structure quand elle est petite, deux ou trois champs, et que la fonction n'a qu'à la lire. La copie évite alors toute surprise : l'appelé ne peut rien casser chez l'appelant.

La convention répandue dans les grands projets consiste à passer un pointeur dès que la structure dépasse la taille de deux pointeurs, et à le déclarer const quand la fonction ne modifie rien, ce qui fait vérifier la promesse par le compilateur.

Comment une structure peut-elle contenir une chaîne de caractères ?

De deux façons, et elles ne se valent pas.

Un tableau de caractères dans la structure, char nom[32];. La place est réservée dans la structure elle-même, la fiche est autonome, et la longueur du nom est plafonnée à 31 caractères.

Un pointeur, char *nom;. La structure ne contient alors que quatre ou huit octets, et le texte vit ailleurs. La fiche n'est plus autonome : copier la structure ne copie pas le texte, et les deux copies désignent la même chaîne. Il faut de surcroît décider qui libère ce texte.

La première forme est celle d'un débutant bien inspiré ; la seconde est celle d'une bibliothèque qui assume une règle de propriété écrite quelque part.

Un fichier de 2 millions de fiches contient un char, un int et un char, dans cet ordre. Que gagne-t-on à réordonner les champs ?

Dans cet ordre, la fiche occupe 12 octets : un octet, trois de remplissage, quatre pour l'entier, un octet, puis trois de remplissage final. Rangée en char, char, int, elle en occupe 8.

Sur deux millions de fiches, l'écart est de 8 mégaoctets, soit un tiers. Ce n'est pas seulement de la place : un parcours complet lit un tiers d'octets en moins, et comme la mémoire est le goulot d'étranglement des parcours, le gain de temps suit.

C'est l'optimisation la moins coûteuse qui existe, puisqu'elle ne change pas une ligne de code, et c'est aussi celle qu'on oublie le plus souvent.

La méthode

Terminer la déclaration par un point-virgule, après l'accolade fermante.
Ranger les champs du plus grand au plus petit, pour ne pas payer le remplissage.
Employer sizeof(struct X) pour toute réservation, jamais un nombre d'octets écrit à la main.
Passer l'adresse dès que la fonction modifie la structure, ou dès qu'elle est volumineuse.
Se rappeler que la structure se copie et que le tableau ne se copie pas : c'est la source des surprises entre les deux.

Synthèse

struct Nom { ... }; décrit un type, pas une variable, et le point-virgule final en fait partie.
L'accès se fait par . sur une structure et par -> sur un pointeur vers une structure, p->x étant l'abréviation de (*p).x.
Une affectation entre structures recopie tous les champs, contrairement à un tableau.
Une structure passée à une fonction est copiée : il faut passer son adresse pour la modifier.
La taille d'une structure inclut le remplissage dû à l'alignement, et l'ordre des champs la change.

Et ensuite

Une structure qui contient un pointeur vers une structure du même type ouvre tout un monde. Les listes chaînées construisent une suite qui grandit à la demande, sans jamais recopier ce qui existe déjà.