Synthèse et défis : données composées

L’acquis de l’unité

L’unité s’était proposé d’enseigner à représenter des collections de données et à les traiter avec les algorithmes de base, en estimant ce qu’ils coûtent. Elle y est parvenue en s’appuyant uniquement sur ce que l’introduction a déclaré tenir pour acquis : les boucles avec invariant, les fonctions et leurs modes de passage, l’arithmétique des entiers. Le programme des scores, qui avec cinq variables taisait les données en trop, s’écrit maintenant avec un vecteur ; et la question des ex aequo, qui avec toutes les paires exigeait des minutes pour un million de données, se résout en triant et en comparant les voisins.

Tableaux de taille fixe

La leçon Tableaux de taille fixe a présenté std::array, la séquence de taille fixe, dont les indices comptent à partir de zéro parce que ce sont des décalages. Elle a établi que l’indice $i$ est valide si et seulement si $0 \leq i < n$, que chaque accès avec [] exige de le démontrer par l’invariant de la boucle, et que l’accès hors limites est un comportement indéfini, que .at() transforme en un arrêt défini ; elle a introduit std::size_t et appris à lire les tableaux C.

Vecteurs

La leçon Vecteurs a présenté la séquence qui grandit avec push_back et a établi quand il faut conserver une série : si une décision sur une donnée dépend de données ultérieures. Elle a établi les parcours canoniques (accumuler, filtrer, transformer) avec leurs invariants et leurs abréviations dans la bibliothèque (std::ranges::count, std::ranges::max, std::ranges::fold_left), la règle du passage d’un vecteur, et la différence entre taille et capacité, d’où découlent le coût constant en moyenne de push_back et l’invalidation des références quand le vecteur déménage.

Le coût d’un algorithme

La leçon Le coût d’un algorithme a ajouté la seconde question : compter l’opération dominante dans le pire cas, classer par ordre de croissance, prédire l’effet du doublement de $n$ et mesurer avec std::chrono::steady_clock, avec optimisation, sans détecteurs, en répétant et en prenant la médiane.

Rechercher et trier

La leçon Rechercher et trier a justifié la recherche dichotomique par son invariant et sa mesure ; elle a écrit le tri par sélection et le tri par insertion, en comptant leurs comparaisons ; elle a présenté les algorithmes de ranges avec la précondition de l’ordre, que personne ne vérifie ; et elle a calculé quand il convient de trier avant de rechercher.

Tableaux à deux dimensions

La leçon Tableaux à deux dimensions a parcouru les tableaux par lignes et par colonnes, calculé la transposée et le produit de matrices, avec son coût cubique, compté des voisins sans sortir des bords et rangé un tableau dans un vecteur plat avec l’indice $i \cdot \mathit{columns} + j$.

Enregistrements

La leçon Enregistrements a remplacé les vecteurs parallèles par le struct, avec une valeur initiale dans chaque champ ; elle a appris à passer et à renvoyer des enregistrements, à les trier et à les rechercher selon un champ avec une projection, à trier selon plusieurs critères avec std::ranges::stable_sort et à modéliser un problème avec des enregistrements qui contiennent des enregistrements et des vecteurs.