Sorbonne Université
Master 1 de mathématiques et applications Unité d’enseignement MU4MA056
Programmation en C++ pour mathématiciens: notes de cours
Damien Simon
Laboratoire de Probabilités, Statistique et Modélisation (LPSM)
Année universitaire 2019–2020
ii
Les notes de cours qui suivent sont en cours de rédaction et ne contiennent pas tous les détails et commentaires vus en cours. Ce document sera régulièrement mis à jour et un polycopié sera fourni lorsque ces notes seront complétées : faites un geste pour l’environnement, ne l’imprimez pas avant !
Introduction et organisation du cours vii
1 Notions générales 1
1.1 Qu’est-ce que la programmation? . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Une première approche intuitive . . . . . . . . . . . . . . . . . . . . 1
1.1.2 L’ordinateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.3 L’algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4 La compilation ou l’interprétation . . . . . . . . . . . . . . . . . . . 3
1.1.5 Les différents langages et le choix de C++ . . . . . . . . . . . . . . . 4
1.2 Pourquoi programmer pour un mathématicien? . . . . . . . . . . . . . . . . 4
1.2.1 Traiter efficacement des données numériques . . . . . . . . . . . . . 5
1.2.2 Étudier un modèle à travers des simulations . . . . . . . . . . . . . . 5
1.2.3 Ce que ne fait pas la programmation . . . . . . . . . . . . . . . . . . 5
1.3 Programmer efficacement : quelques conseils . . . . . . . . . . . . . . . . . . 6
1.3.1 Aborder sereinement un projet de programmation . . . . . . . . . . 6
1.3.2 Bonnes pratiques de codage lors d’un travail en équipe . . . . . . . 7
1.4 La notion de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Structure et compilation d’un programme 9
2.1 Histoire du C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Quelques références indispensables . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Exemples de programmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Premier exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 Un deuxième exemple avec une fonction auxiliaire . . . . . . . . . . 11
2.3.3 Un troisième exemple issu des mathématiques . . . . . . . . . . . . . 12
2.4 Compilation de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 Cas d’un fichier unique . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Cas de plusieurs fichiers séparés . . . . . . . . . . . . . . . . . . . . . 14
2.4.3 Les directives de précompilation . . . . . . . . . . . . . . . . . . . . 17
2.4.4 Durée d’exécution d’un programme . . . . . . . . . . . . . . . . . . . 17
2.4.5 [hors programme] Compilation pour utilisation par d’autres langages
de programmation : l’exemple de swig . . . . . . . . . . . . . . . . 18
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 La syntaxe du C++ 23
3.1 Les types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Les types simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.3 Les tableaux statiques . . . . . . . . . . . . . . . . . . . . . . . . . . 29
iii
iv TABLE DES MATIÈRES
3.1.4 Les structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.5 Les références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Les tests et les boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Le test if ( ) { } else { } . . . . . . . . . . . . . . . . . 33
3.2.2 Le test switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Les fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 Description générale . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Les λ-fonctions à partir du standard C++11. . . . . . . . . . . . . . 41
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 La bibliothèque standard (STL) 47
4.1 Présentation de la bibliothèque standard . . . . . . . . . . . . . . . . . . . . 47
4.2 Les entrées-sorties vers le terminal et les fichiers . . . . . . . . . . . . . . . . 49
4.2.1 Lecture et écriture de données . . . . . . . . . . . . . . . . . . . . . 49
4.2.2 Écriture dans le terminal. . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.3 Lecture dans le terminal. . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.4 Lecture et écriture dans un fichier. . . . . . . . . . . . . . . . . . . . 51
4.3 Les chaînes de caractères string . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Les conteneurs ordonnés std::vector et std::list . . . . . . . . . . . . 53
4.4.1 Les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 Les conteneurs non ordonnés std::map et std::set . . . . . . . . . . . . 59
4.5.1 Les ensembles, std::set et std::unordered_set . . . . . . . . . 59
4.5.2 Les fonctions à domaine de définition fini et le conteneur map . . . . 60
4.6 Itérateurs et algorithmes sur les conteneurs . . . . . . . . . . . . . . . . . . 61
4.6.1 Un exemple simple et basique : dénombrer des éléments selon un
critère. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6.2 Les itérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.6.3 Les algorithmes de <algorithm> et <numeric> . . . . . . . . . . . 64
4.6.4 Des extensions des itérateurs bien utiles en pratique . . . . . . . . . 66
4.7 L’aléatoire en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.7.1 L’aléatoire et la programmation . . . . . . . . . . . . . . . . . . . . . 69
4.7.2 Les générateurs de nombres aléatoires en C++ . . . . . . . . . . . . 71
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5 Programmation orientée objet et classes 81
5.1 Généralités sur les classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.1.1 Étude d’un exemple préliminaire . . . . . . . . . . . . . . . . . . . . 82
5.1.2 Vocabulaire et définition d’une classe : champs et méthodes . . . . . 85
5.2.1 Accesseurs et mutateurs . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.2 Constructeurs et destructeurs . . . . . . . . . . . . . . . . . . . . . . 91
5.2.3 Incrémentation et décrémentation . . . . . . . . . . . . . . . . . . . 93
5.2.4 Méthodes de conversion . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3 Surcharge d’opérateurs, de fonctions et amitié . . . . . . . . . . . . . . . . . 95
5.4 Héritage public entre classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4.1 Définition et syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4.2 Méthodes virtuelles et polymorphisme . . . . . . . . . . . . . . . . . 100
TABLE DES MATIÈRES v
5.4.3 Méthodes virtuelles pures . . . . . . . . . . . . . . . . . . . . . . . . 101 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6 Programmation générique et templates 109
6.1 Introduction à la programmation générique . . . . . . . . . . . . . . . . . . 109
6.1.1 Présentation de quelques exemples . . . . . . . . . . . . . . . . . . . 109
6.1.2 Vocabulaire et syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.1.3 Structure du code et compilation . . . . . . . . . . . . . . . . . . . . 112
6.1.4 Particularités pour les modèles de classe . . . . . . . . . . . . . . . . 113 6.1.5 Redéfinition d’une instanciation particulière . . . . . . . . . . . . . . 114
6.2.1 La bibliothèque standard et la STL . . . . . . . . . . . . . . . . . . . 115
6.2.2 Objets mathématiques standards . . . . . . . . . . . . . . . . . . . . 115
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7 Gestion de la mémoire 121
7.1 Notions sur les pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.1.1 L’un des atouts du C et du C++ . . . . . . . . . . . . . . . . . . . . 121
7.1.2 Les adresses en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2 Gestion dynamique de la mémoire . . . . . . . . . . . . . . . . . . . . . . . 125
7.2.1 Arithmétique des pointeurs. . . . . . . . . . . . . . . . . . . . . . . . 125
7.3 Gestion de la mémoire dans les classes . . . . . . . . . . . . . . . . . . . . . 128
7.3.2 Opérateur d’affectation . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.4 Les structures de données usuelles . . . . . . . . . . . . . . . . . . . . . . . 131
7.4.1 La problématique de la complexité . . . . . . . . . . . . . . . . . . . 131
7.4.2 Listes et itérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.4.3 Listes simplement chaînées, piles, arbres, « skip lists », arbres . . . . 135 7.4.4 Les itérateurs des conteneurs de la STL . . . . . . . . . . . . . . . . 136
7.5 [Hors programme] Une rapide revue des pointeurs intelligents en C++11 . . 137
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Conclusion 141
Introduction à Makefile 143
Bibliographie 144
vi TABLE DES MATIÈRES
Introduction et organisation du cours
Ce cours a pour but de vous donner une base solide de programmation en C++ orientée vers les mathématiques appliquées, avec un fort accent mis sur le calcul intensif.
Étant donné le volume horaire restreint, de nombreuses bibliothèques ne seront pas présentées et nous ne pourrons pas aborder en détail le calcul parallèle; en revanche, la structure du cours vise à donner suffisamment de bases sur ces questions pour que l’étudiant intéressé puisse s’y mettre par lui-même à la suite du cours, en M2 ou en stage.
Le côté pratique étant essentiel pour un cours de programmation, le nombre d’étudiants inscrits est limité à 100 étudiants. Il y a 4 groupes de TP et une répartition uniforme des étudiants sur ces 4 groupes est indispensable pour le bon fonctionnement des TP. L’effectif d’un groupe de TP est plafonné à 25. L’inscription dans l’un des 4 groupes est obligatoire et nécessaire pour valider ce module.
lundi, mardi, mercredi et vendredi de 13h45 à 16h45 en salle 16.26.401
et sont assurés par C. Boutillier, D. Giorgi et D. Simon. La salle étant dans un couloir de laboratoire, vous êtes priés d’arriver et d’attendre en silence devant la porte.
Calendrier prévisionnel pour l’année 2019–2020
— premier et deuxième cours : lundi 13 janvier 2019
— premier TP : la semaine du 20 janvier 2019
— premier TP noté : la semaine du 24 février 2019
— deuxième TP noté : la semaine du 20 avril 2019 (juste après les vacances de printemps)
Évaluation. Les séances de TP sur machine sont obligatoires. Elles donnent lieu à deux notes (à travers 2 séances de TP notés en séances 6 et 12 des TP) sur 25. L’examen et le rattrapage sont sur papier et donnent lieu à une note pour 75. Le calcul de la note finale procède selon la formule :
(︂note TP1 sur 25 + note TP2 sur 25)︂
note finale sur 100 = + note examen sur 75
2
L’évaluation en TP se fait par binôme ou individuellement (si le nombre de machines le permet) : la composition d’un binôme ne peut pas varier d’un TP noté au suivant.
vii
viii TABLE DES MATIÈRES
Structure de l’ouvrage. Le chapitre 1 ne traite pas du C++ mais de l’informatique en général. Il vise à donner une culture générale sur les ordinateurs et l’algorithmique et fournit des conseils pour aborder sereinement un projet de programmation.
Le chapitre 3 présente la syntaxe du C++, i.e. les mots-clefs et symboles à maîtriser pour écrire des programmes élémentaires. La plupart des notions sont classiques en programmation et se retrouvent dans de nombreux autres langages avec des syntaxes légèrement différentes.
Le chapitre 4 présentela bibliothèque standard du C++, qui permett de gérer en pratique de nombreux outils classiques tels les conteneurs, les algorithmes et les nombres pseudoaléatoires.
Le chapitre 5 explique comment créer de nouveaux types en C++ à l’aide de classes et comment exploiter la programmation orientée objet.
Le chapitre 6 décrit la programmation générique en C++ qui permet d’écrire des morceaux de code réutilisables sur des objets de types très différents à l’aide de « templates » (modèles en français) de fonctions et de classes.
Le chapitre 7 décrit une spécificité majeure du C et du C++ : la possibilité de gérer soi-même la mémoire à l’aide des pointeurs pour une plus grande efficacité du code.
Remerciements. Je tiens ici à remercier toutes les personnes qui ont participé à l’élaboration de ce polycopié. En premier lieu, je voudrais remercier Vincent Lemaire qui est à l’origine de ce cours et me l’a transmis et avec qui j’ai enseigné cette matière de nombreuses fois. Mes collègues de TP, Cédric Boutillier, Raphaël Roux, Nicolas Gilliers, Thibaut Lemoine et Daphné Giorgi ont été, au fil du temps et des évolutions de ce cours, d’une aide précieuse pour la relecture et la conception des sujets. Enfin, je voudrais remercier mes autres relecteurs qui ont corrigé de très nombreuses coquilles et mauvaises formulations : il doit malheureusement en rester encore
Chapitre 1
Notions générales d’algorithmique et de programmation
1.1 Qu’est-ce que la programmation?
1.1.1 Une première approche intuitive
L’avantage de ce dernier est sa capacité d’effectuer extrêmement rapidement les calculs logiques et arithmétiques; son inconvénient — si cela en est un — est de suivre aveuglément les instructions qui lui ont été fournies et de ne pas mesurer la pertinence du résultat.
Les instructions doivent être écrites dans un langage que comprend l’ordinateur. Comme pour les langues humaines, il existe plusieurs langages mais ils décrivent tous les mêmes calculs mathématiques et logiques. Pour nous, ce langage sera le C++.
1.1.2 L’ordinateur
Pour bien comprendre les langages informatiques, il est nécessaire d’avoir une idée du fonctionnement d’un ordinateur. Nous n’entrerons pas dans les détails qui peuvent atteindre une très grande complexité et dont les informaticiens sont les spécialistes.
Un ordinateur est essentiellement composé :
— de mémoire vive (la RAM) : c’est là que sont écrites les données manipulées par le processeur. Y accéder pour lire ou écrire des données est très rapide. Lorsqu’un programme termine, toutes les données présentes dans la RAM qui dépendent de ce programme sont effacées et perdues. C’est une mémoire rapide mais temporaire.
— de mémoire morte (disque dur, CD, DVD, disquette, clef USB, etc.) : c’est là que sont écrites les données de manière durable, i.e. au-delà de la fin d’un programme. Y accéder est beaucoup plus lent que pour la RAM. Le processeur ne se permet d’y écrire que sur instruction explicite du programmeur.
— de processeurs : ce sont eux qui effectuent les calculs. Ils chargent quelques données, opèrent des opérations logiques et arithmétiques très élémentaires sur celles-ci et donnent le résultat.
— de périphériques, en particulier l’affichage : tout ce qui permet de faire l’interface
1
Un langage de programmation comporte donc les types d’instructions suivants :
— des instructions de calcul qui permettent d’ordonner aux processeurs les opérations logiques et arithmétiques à effectuer et d’indiquer sur quelles données les effectuer,
— des instructions d’affectation qui permettent d’indiquer où stocker le résultat dans la RAM pour un usage futur,
— des instructions de lecture et écriture qui permettent d’aller lire des données ou d’écrire des résultats dans la mémoire morte ou de les afficher dans des périphériques, tels l’écran.
L’un des buts de ce cours est de maîtriser ces trois types de commandes dans le langage C++.
Toute mémoire, vive ou morte, est organisée de la manière suivante : c’est une suite ordonnée de valeurs 0 ou 1, appelées bits. Cette organisation unidimensionnelle a deux conséquences majeures.
D’une part, toute donnée un peu plus évoluée que 0 ou 1 doit être codée en termes d’une succession de 0 et 1. Par exemple, un nombre entier sera écrit en base deux; les lettres de l’alphabet seront numérotées et leur numéro sera écrit en base deux. Dans les instructions de lecture et écriture, il faut donc faire attention à dire à l’ordinateur ce qu’il doit lire! Par exemple la suite de bits 01101 peut coder aussi bien un tableau (0,1,1,0,1) de cinq valeurs dans {0,1}, l’entier 0 × 1 + 1 × 2 + 1 × 4 + 0 × 8 + 1 × 16 = 22, ou l’entier 1×1+0×2+1×4+1×8+0×16 = 13 écrit dans l’autre sens. Le codage de l’information a donc une grande importance : c’est à la base de la notion de type que nous étudierons en C++.
1.1.3 L’algorithmique
L’algorithmique est une discipline qui se focalise sur le découpage d’une méthode de traitement d’une tâche donnée en étapes élémentaires préalablement fixées et dont le but est de minimiser le nombre d’étapes élémentaires à utiliser. Cela permet d’avoir un programme qui s’exécute en un temps minimal avec le moins d’opérations possibles.
En particulier, l’algorithmique ne dépend que très peu du langage utilisé; c’est la programmation des étapes élémentaires qui dépend du langage, non le choix du découpage en étapes élémentaires. Pour les questions mathématiques qui vont nous intéresser, la plupart des langages usuels offrent le même panel d’opérations élémentaires.
Il s’agit donc de bien réfléchir à la méthode de résolution d’un problème avant de commencer à écrire des lignes de programmation!
Un exemple extrêmement élémentaire de deux algorithmes qui réalisent la même tâche en des temps très différents est celui du calcul d’une puissance.
Exemple : calcul dea517. Soit a un élément d’un anneau; quel est le nombre minimal de multiplications à utiliser pour calculer a517 ?
Une première réponse naïve consiste à dire 516 : on commence par calculer a2 (une multiplication), puis a3 = a2× a (une autre multiplication), puis a4 = a3× a, etc., puis a517 = a516 × a.
1.1. QU’EST-CE QUE LA PROGRAMMATION?
1.1.4 La compilation ou l’interprétation
Le code d’un programme est la suite de lignes de programmation écrites dans un langage donné (C++ dans ce cours) pour effectuer une tâche donnée. C’est la transcription dans ce langage C++ des algorithmes expliqués dans la section précédente.
À ce stade, nous sommes encore loin de ce qui se passe réellement dans le cœur de l’ordinateur, où les opérations élémentaires « physiques » consistent à transformer des 0 en 1 aux bons endroits. Pour passer de l’un à l’autre, il faut convertir nos lignes de programmation en « instructions machine » : c’est l’étape de compilation ou interprétation du programme (voir en fin de section pour la différence entre les deux notions). C’est un autre programme qui est chargé de cela : le compilateur1 ou l’interpréteur.
Un langage de programmation est ainsi inutile sans compilateur/interpréteurs associé. Pour un même langage, il peut exister différents compilateurs. Selon les processeurs utilisés et le système d’exploitation, les instructions machine peuvent varier : le travail du compilateur est de gérer tout cela. Nous n’entrerons pas dans les détails du fonctionnement du compilateur et des instructions machines dans ce cours.
Le compilateur produit un fichier exécutable qui contient les instructions machine. Il ne reste alors qu’à exécuter ce fichier pour que l’ordinateur effectue réellement les opérations que nous avions prévues dans notre algorithme de départ.
Il est possible que le compilateur détecte des erreurs de syntaxe (parenthèses non fermées, instruction inconnue, tentative d’addition de vecteurs de dimensions différentes, etc.). Dans un tel cas, le compilateur indique la ligne du programme qu’il ne comprend pas et qu’il faut corriger. Il est important de garder en mémoire les deux choses suivantes :
— le compilateur ne sait pas détecter une erreur de raisonnement : il produira toujours un programme exécutable si la syntaxe est correcte, même si ce programme effectue une toute autre opération que ce vous auriez souhaité. Il est de la responsabilité du programmeur de vérifier que son programme effectue bien la tâche imposée : personne ne peut le faire à part lui.
En résumé, pour un langage compilé – ce qui est le cas de C++ —, les quatre étapes successives de programmation à respecter sont les suivantes : conception de l’algorithme (pas de langage à apprendre, uniquement des mathématiques), écriture du code, compilation du code pour produire le programme exécutable, exécution de ce programme.
Un langage interprété mélange les deux dernières étapes : au lieu de compiler une fois pour toute un code et de l’exécuter ensuite autant de fois que nécessaire, on lance directement l’interpréteur sur le code non-compilé et ce dernier transforme chaque ligne en instruction machine immédiatement exécutée.
1.1.5 Les différents langages et le choix de C++
Il existe une multitude de langages de programmation. L’immense majorité d’entre eux partage les mêmes fonctionnalités élémentaires. Ce qui les différencie est d’une part leur syntaxe, qui peut rendre la même opération agréable ou détestable à écrire, et d’autre part la présence de fonctionnalités spécifiques supplémentaires. Il est important de prendre conscience qu’a priori toute tâche est réalisable par tous les langages usuels. Le choix d’un langage est donc arbitraire.
Parmi les langages usuels, on peut citer Fortran, Pascal (anciens), Java, C, C++, Python (calcul), Perl, Ruby (traitement des chaînes de caractères), Haskell, C# , Caml, etc.
Les critères de choix usuels sont les suivants :
— intégration de fonctionnalités à des programmes préexistants ou travail en équipe : en général, on s’adapte à ce qui était déjà là quand on vient d’intégrer l’équipe de développement d’un projet;
— choix d’une syntaxe adaptée aux outils que l’on souhaite utiliser : une même tâche peut prendre une seule ligne dans certains langages contre plusieurs dizaines de lignes dans un autre;
— gestion de la mémoire et choix entre compilation et interprétation : pour de petits programmes, ce critère n’est pas important; pour un gros programme de calcul intensif, l’utilisation d’un langage compilé, qui permet de gérer la mémoire soi-même, rend possible des optimisations à plus grande échelle lors de la transformation des lignes de code en instructions machine.
— ouverture du code et choix d’un langage connu : si le code du programme est public, plus le langage est largement connu, plus les chances augmentent que quelqu’un puisse vous aider.
— existence de bibliothèques qui réalisent déjà ce que l’on souhaite faire.
Le langage C++ est un langage maintenant très classique et figure parmi les plus utilisés, en particulier en finance et en calcul intensif. D’une part, sa syntaxe est assez naturelle et, d’autre part, sa gestion directe de la mémoire permet une bonne vitesse d’exécution.
Le C++ est réputé pour avoir une certaine lourdeur syntaxique, comparativement à Python par exemple : cette lourdeur se révèle être un avantage pour les gros programmes car la rigueur qu’elle impose évite l’accumulation de petites erreurs ou incompatibilités entre programmeurs. De plus, une fois qu’on maîtrise le C++, il est facile de passer à d’autres langages moins lourds et moins rigides : « Qui peut le plus peut le moins »
1.2 Pourquoi programmer pour un mathématicien?
Ce cours n’a pas pour but non plus de traiter le problème mathématique du contrôle des erreurs commises lors de discrétisation ou d’approximations : nous renvoyons pour cela à des cours de mathématiques.
1.2. POURQUOI PROGRAMMER POUR UN MATHÉMATICIEN?
L’emphase est mise sur l’implémentation de calculs mathématiques en C++, en particulier liés aux probabilités et aux statistiques en lien avec différentes applications.
1.2.1 Traiter efficacement des données numériques
Savoir résoudre formellement un problème est au cœur des mathématiques; malheureusement, appliquer la formule de la solution dans un cas pratique peut parfois être long et pénible. Par exemple, le pivot de Gauss permet de résoudre formellement un système linéaire mais il est très fastidieux de résoudre « à la main » un système de 10 équations à 10 inconnues. Or, dans de nombreux cas pratiques, ce sont des systèmes de taille supérieure à 10000 qu’il faut résoudre. Il devient alors inévitable d’écrire un code qui réalise la méthode du pivot de Gauss.
De nombreux TP ce semestre ont pour but d’écrire les algorithmes et les lignes de code qui permettent de programmer des méthodes mathématiques que vous avez étudiées pendant vos années d’université : méthode de Monte-Carlo pour des estimations d’intégrales, algèbre linéaire, polynômes, chaînes de Markov, etc.
Avec le récent développement du « Big Data », les volumes statistiques à traiter sont énormes et requièrent de gros moyens de calcul programmés efficacement (calcul parallèle, etc) : le langage C++ se révèle bien adapté pour cela.
1.2.2 Étudier un modèle à travers des simulations
1.2.3 Ce que ne fait pas la programmation
Pour un mathématicien néophyte en programmation, certaines impossibilités peuvent parfois dérouter. Tout d’abord, sauf cas très particulier très récents (cf. le langage Coq par exemple), un programme ne prouve pas qu’un algorithme marche : il se contente de l’exécuter quelle que soit la pertinence du résultat. Si l’algorithme de départ est faux, le programme peut être syntaxiquement correct (i.e. le compilateur ne donne aucun message d’erreur) et le résultat faux. Autrement dit, l’écriture d’un programme vient après la formulation mathématique d’un problème et d’une méthode formelle de résolution.
Dans un tout autre registre, une autre impossibilité est déroutante : l’absence des nombres réels et de tout infini ! En effet, mathématiquement, un nombre réel requiert la connaissance de tous les chiffres de son développement binaire ou décimal. Il faudrait une mémoire infinie pour stocker ne serait-ce qu’un réel; sur une machine réelle, on travaille avec des troncatures des nombres réels à une précision donnée. Cela a pour conséquence majeure l’accumulation des erreurs d’arrondis qui peuvent mener à des résultats aberrants.
Exemple : calcul de la série harmonique. Nous souhaitons calculer les valeurs de Hn /k. Nous savons que cette série diverge comme logn quand n → ∞.
Néanmoins, calculons Hn selon deux méthodes différentes avec des variables de type float (réels avec une précision basse, cf. le chapitre suivant) :
— du grand vers le petit : on commence par 1, puis on ajoute 1/2, puis 1/3, etc, jusqu’à 1/n;
— du petit vers le grand : on commence par 1/n, puis on ajoute 1/(n−1), puis 1/(n−2), etc, jusqu’à 1/2 puis 1;
Nous refaisons le même calcul avec des double (réels avec une plus grande précision) à la place des float . Nous obtenons alors les résultats suivants :
| n | 107 | 108 | 109 | |
| Du grand vers le petit ( float ) | 14.3574 | 15.4037 | 15.4037 | 15.4037 |
| Du petit vers le grand ( float ) | 14.3927 | 16.686 | 18.8079 | 18.8079 |
| Du grand vers le petit ( double ) | 14.3927 | 16.6953 | 18.9979 | 21.3005 |
| Du petit vers le grand ( double ) | 14.3927 | 16.6953 | 18.9979 | 21.3005 |
| Valeur attendue pour Hn | ≃ 14.3927 | ≃ 16,7 | ≃ 19,0 | ≃ 21,3 |
L’analyse de ces résultats est la suivante. Tout d’abord, le passage de float à double augmente la précision des résultats : c’est normal puisque plus de bits sont utilisés pour stocker chaque nombre; l’inconvénient est alors que le calcul prend plus de temps en double qu’en float . Même si cela n’apparaît pas ici, le type double a également ses limitations.
Au niveau des différentes méthodes, le deuxième est meilleure que la première car, dans la deuxième, chaque addition ne fait intervenir que des nombres d’ordres de grandeur comparables et cela limite les erreurs d’approximation. Dans la première, vers la fin du calcul, on ajoute des nombres très petits (O(1/n)) à des nombres très grands (O(logn)) et les petits se retrouvent arrondis à zéro. À titre d’exemple, pour n = 109, la différence entre les deux méthodes est de 2,4 × 10−1.
1.3 Programmer efficacement : quelques conseils
Le cerveau ayant des capacités limitées, il est complètement utopique — surtout pour des débutants — d’espérer être capable de penser simultanément aux mathématiques, à l’algorithmique, à tous les détails de syntaxe et à l’optimisation d’un code. De plus, il est assez difficile de corriger des lignes de code tapées rapidement et truffées d’erreur. Le travail doit donc être divisé comme suit :
2. implémentation des algorithmes en lignes de code : on traduit les algorithmes en C++ en écrivant précautionneusement chaque ligne pour laisser le moins possible d’erreurs de syntaxe.
3. compilation et correction des erreurs de syntaxe : les messages du compilateur ne sont pas des punitions et ils vous indiquent les lignes qu’il ne comprend pas. Ne corrigez qu’une erreur à la fois en commençant par la première puis recompilez2.
1.4. LA NOTION DE COMPLEXITÉ
4. test du programme sur des données pour lesquelles vous connaissez déjà les résultats attendus : ce n’est pas parce que la syntaxe est correcte que votre programme fait ce qu’il était prévu qu’il fasse! Il suffit pour cela d’une mauvaise initialisation de récurrence par exemple.
5. utilisation du programme pour tout ce que vous voulez!
Selon que l’on travaille pour soi-même sur un petit programme ou dans une équipe de développeurs sur un grand logiciel, les habitudes de travail peuvent être différentes.
Lire du code est difficile; lire le code d’autrui (ou son propre code quelques années plus tard) l’est encore plus. Il est important de commenter son code en expliquant avec des vraies phrases ce que fait chaque fonction et chaque morceau de code, i.e. de rédiger un documentation de son code (cf. par exemple le logiciel doxygen ).
Il est fréquent de corriger ou améliorer du code, par exemple lorsqu’une erreur est découverte ou lorsqu’on souhaite utiliser une nouvelle méthode de calcul. Il ne faut pourtant pas tout réécrire à chaque fois. Pour éviter cela, il est important de morceler le plus possible le code et de respecter l’adage « une tâche, une fonction ». La maintenance du code se fait ensuite en modifiant seulement quelques lignes faciles à repérer.
1.4 La notion de complexité
La complexité d’un programme peut être définie approximativement comme la quantité de ressources utilisées pour effectuer une tâche donnée. Les ressources peuvent être du temps ou de l’espace mémoire ou le nombre d’appels à une fonction donnée. À notre niveau, nous nous intéresserons au coût en temps, qui peut se ramener en général au nombre d’opérations élémentaires utilisées : en effet, une opération donnée prend en général toujours le même temps quelle que soit les valeurs génériques utilisées. Il faut néanmoins faire attention que certaines fonctions prennent plus de temps que d’autres : les calculs de fonctions analytiques
√
cos, sin, log, exp, ·, etc prennent plus de temps qu’une multiplication qui prend elle-même plus de temps qu’une addition (pour vous faire une idée, demandez vous comment vous feriez à la main : plus vous mettrez de temps, plus l’ordinateur mettra de temps lui aussi!).
Il n’est pas nécessaire de connaître le temps pris par chaque opération (cela dépend du processeur, du pourcentage d’occupation du CPU, etc) mais plutôt de savoir l’ordre de grandeur du nombre de fois où elles sont utilisées. En effet, c’est essentiellement le
répétition un grand nombre de fois des opérations qui allonge le temps d’exécution.
Ce qui contribue à la complexité, ce sont généralement le nombre de boucles imbriquées et la taille des boucles utilisées. Prenons plusieurs exemples.
Puissances. Pour le calcul de la puissance, on a vu que seulement 11 multiplications étaient nécessaires pour calculer a517. De manière générale, le calcul de aN est de complexité O(logN) (il s’agit de trouver le plus grand chiffre en base 2 de N).
Trouver le minimum d’un tableau de tailleN. Pour cela, il faut parcourir tout le tableau une seule fois en comparant chaque élément au minimum des éléments précédents. La complexité est donc O(N) (on a compté ici le nombre de comparaisons à effectuer).
Trier un tableau de tailleN. Le résultat précédent donne une première piste : on cherche le minimum du tableau puis on le met en première position, on recommence alors avec les N − 1 éléments restants. Il faut donc environ comparaisons.
Vous verrez en TP que cet algorithme n’est pas le meilleur et cela peut être amélioré en O(N logN).
Une autre manière d’aborder la complexité est de regarder par combien de temps est multipliée la durée d’un programme lorsque la taille des données double. Par exemple, si N est remplacé par 2N, le temps pour trouver le minimum d’un tableau est doublé et le temps de tri par la méthode naïve est multiplié par 4. Cette notion est donc extrêmement utile pour estimer le temps de calcul pour des problèmes de grande taille. En particulier, on peut ainsi deviner s’il faut attendre une réponse dans la seconde/heure/journée/année/siècle.
Chapitre 2
Structure et compilation d’un programme
2.1 Histoire du C++
Thompson. Face à l’ampleur de la tâche, Kenneth Thompson et Dennis Ritchie décident de créer un langage de programmation plus approprié afin de rendre l’écriture plus aisée.
Après plusieurs essais, le langage C apparaît en 1972.
De cette histoire initiale liée à UNIX, le C hérite une particularité remarquable : il est très axé sur la manipulation directe de la mémoire vive avec un système efficace et omniprésent de pointeurs (cf. le chapitre 7). Cette possibilité de gestion directe de la mémoire par le programmeur permet ainsi au langage C d’être un langage bien adapté au calcul intensif, comme le Fortran et le Pascal à la même époque, et lui assure un important succès. L’idéologie dans ces langages est de casser tout objet évolué en briques élémentaires de mémoire et en nombreuses procédures qui manipulent ces briques de mémoire. Il ne reste alors de l’objet évolué qu’un long manuel d’utilisation qui décrit comment assembler soi-même des procédures qui se ressemblent toutes au niveau de la syntaxe.
Au début des années 1980, la programmation orientée objet (POO) commence à se répandre. L’idée est au contraire de manipuler un objet évolué par ses propriétés intrinsèques sans devoir se référer constamment aux briques élémentaires qui le constituent. Il faut donc une bibliothèque qui fait le lien entre ces propriétés intrinsèques et les briques de mémoire et les procédures élémentaires mais qu’on préfère ne pas avoir à lire. La personne qui manipule ensuite un tel objet évolué n’a plus à connaître le travail fait en amont et il lui est donc plus facile d’écrire ce qu’elle veut.
Pour un mathématicien, la programmation orientée objet apparaît comme une démarche naturelle : en effet, toute définition d’une structure mathématique abstraite commence par
9
le postulat de règles de manipulations d’objets. En pratique, les exemples de structures évoluées sont construits en combinant des structures plus élémentaires. C’est la même chose en C++ : définir une classe (cf. le chapitre 5), c’est donner la liste des opérations qu’on peut faire sur les objets de cette classe; coder une classe concrète, c’est décrire comment ces constructions peuvent être réalisées à partir d’objets concrets préexistants.
2.2 Quelques références indispensables
Il est hors de question, dans le cadre de ce cours, de maîtriser par cœur l’ensemble du C++ et de sa bibliothèque standard. En revanche, les quatre points suivants sont importants :
1. maîtriser toute la syntaxe de base du langage (sans la bibliothèque standard),
2. maîtriser les conteneurs élémentaires tels que std::vector et les entrées-sorties de std::iostream ,
3. avoir une bonne idée des outils présents dans la bibliothèque standard pour savoir aller les chercher le jour où vous en aurez besoin,
4. savoir lire la documentation de la bibliothèque standard pour s’adapter rapidement à de nouveaux outils.
Pour cela, il y a quelques références indispensables : — les deux sites internet :
et
Le premier est très complet et décrit en particulier en détail les nouveaux standards du langage C++14, C++17 et C++20; le second est moins à jour sur les standards au-delà de C++17 mais les exemples de la bibliothèque standard sont souvent plus abordables. — le site internet de la norme officielle du langage C++
— les livres classiques que sont[1, 5, 6] sur les bases de langage mais qui ne sont pas nécessairement les plus à jour sur les dernières évolutions.
2.3 Exemples de programmes
Considérons notre premier programme :
| #include<iostream>int main() { std::cout << "Bienvenue en 4M056 !"; /* Ceci est un commentaire sur plusieurs lignes */ std::cout << std::endl; //ceci est un commentaire en fin de lignereturn 0; } |
2
4
6
8
2.3. EXEMPLES DE PROGRAMMES
Lors de l’exécution de ce programme dans un terminal de commande (cf. la section suivante pour comprendre comment le faire), ce programme affichera dans ce même terminal la phrase « Bienvenue en 4M056! », reviendra à la ligne puis s’arrêtera avec succès.
Commentons-le ligne à ligne :
— ligne 1 : ce programme doit réaliser de l’affichage d’informations sur un écran par un terminal de commande : cette opération élaborée est préprogrammée dans une bibliothèque appelée iostream et cette ligne est là pour indiquer au programme d’aller chercher cette bibliothèque.
— ligne 2 : c’est le prototype qui débute le code de la fonction main(void) ; cette fonction principale (« main » en anglais) est la fonction lancée à l’exécution du programme.
— ligne 3 : nous sommes à présent à l’intérieur (délimité par les accolades { } ) du code la fonction main() . Cette ligne se termine par un point-virgule : c’est une instruction. L’objet std::cout est l’objet défini dans la bibliothèque <iostream> qui permet d’afficher dans le terminal de commande. L’opérateur << dit à std::cout d’afficher le message voulu, placé entre guillemets.
— ligne 6 : l’opérateur std::endl ordonne de passer à la ligne suivante (« endl » est l’abréviation de "end line"), là encore dans le terminal via std::cout . La fin de la ligne après // est un autre commentaire ignoré par le compilateur.
— ligne 7 : on indique à la fonction main() de terminer proprement en produisant la valeur nulle. L’accolade finale termine le code de la fonction main() .
Un programme en C++ est ainsi constitué d’une suite d’instructions terminées par des points-virgules et rassemblées dans des fonctions.
Considérons à présent un second exemple qui affiche l’aire d’un cercle dont le rayon est demandé à l’utilisateur du programme :
| #include<iostream>#include<cmath> double circle_area(double r) { return M_PI*r*r; } int main() { std::cout << "Entrez le rayon du cercle:" << std::endl; double x; std::cin >> x; std::cout << "L'aire du cercle est "; std::cout << circle_area(x); std::cout << std::endl; return 0; } |
2
4
6
8
10
12
Nous retrouvons comme précédemment des instructions d’affichage de messages par l’intermédiaire de std::cout et std::endl . Les nouveautés sont les suivantes :
— les lignes 3, 4 et 5 définissent une fonction auxiliaire qui calcule l’aire d’un cercle de rayon r par la formule πr2. Pour cela, il faut le symbole de multiplication * ainsi que le nombre π avec une grande précision. Pour cela, nous invoquons à la ligne 2 la bibliothèque cmath où sont définies de nombreuses constantes et fonctions mathématiques, dont le nombre π renommé ici M_PI .
— enfin, la ligne 11 permet d’afficher dans le terminal le résultat de la fonction circle_area calculée en la valeur x donnée par l’utilisateur en ligne 9.
Considérons un dernier exemple mathématique qui utilise une bibliothèque d’algèbre linéaire très efficace, appelée Eigen , pour calculer et afficher l’inverse de la matrice A de taille 4 donnée par :
⎛ ⎞
1 2 3 4
⎜1 −1 2 −2⎟
A = ⎜ ⎟
⎜9 8 7 6 ⎟
⎝ ⎠
Le programme s’écrit :
| #include<iostream>#include<Eigen/Dense>int main() { Eigen::Matrix<double,4,4> A; A << 1, 2 , 3, 4 , 1,-1,1,-1,4,3,2,1,1,-1,0,0 ; std::cout << "La matrice A est: " << std::endl; std::cout << A << std::endl; std::cout << "Son determinant est: " << A. determinant() << std::endl; std::cout << "Son inverse est:" << std::endl ; std::cout << A.inverse() << std::endl; } |
2
4
6
8
10
12
Comme précédemment, la ligne 2 indique l’usage de la partie Dense de la bibliothèque
Eigen que nous avons préalablement installée sur notre ordinateur. Elle donne ainsi accès à plusieurs opérations :
— à la ligne 5, un objet A qui décrit une matrice 4 par 4 contenant des nombres réels en double précision.
— à la ligne 6, un opérateur << qui permet de remplir A à partir de la liste ordonnée de ses coefficients.
— à la ligne 9, une méthode determinant() qui calcule le déterminant de la matrice
— à la ligne 10, une méthode inverse() qui calcule l’inverse de la matrice.
Le résultat du programme tel qu’il s’affiche est le suivant :
La matrice A est:
1 2 3 4
1 -1 1 -1
4 3 2 1
1 -1 0 0
Son determinant est: 40 Son inverse est:
-0.075 -0.125 0.175 0.5
-0.075 -0.125 0.175 -0.5 0.175 0.625 -0.075 -0.5
0.175 -0.375 -0.075 0.5
Ce dernier programme semble magique puisqu’il calcule en une seule ligne l’inverse d’une matrice 4 par 4. Il est donc très utile pour celui qui ne veut pas connaître la formule pour inverser une telle matrice. En fait, tout le travail a été fait par des mathématiciens comme vous au sein de la bibliothèque Eigen . Nous souhaitons insister sur le double but de ce cours de programmation en C++ :
— le second but de ce cours est de vous apprendre à concevoir de nouvelles bibliothèques pour définir de nouveaux objets qui deviendront ensuite utilisables par vous-mêmes ou par d’autres.
2.4 Compilation de fichiers
Supposons que nous ayons pour l’instant dans notre répertoire de travail un unique fichier que nous venons de créer avec un éditeur spécifique. Supposons également que ce fichier ne fasse appel à aucune bibliothèque spécifique. La compilation doit alors être faite dans le terminal par la commande g++ -o
Le nom g++ est le nom du compilateur utilisé, -o est l’abbréviation de output et permet de donner au compilateur le nom du fichier exécutable que l’on souhaite choisir (ici ). Après validation de cette ligne de commande, deux choses peuvent alors se passer :
— soit un message potentiellement très long apparaît pour décrire les erreurs de syntaxe que le compilateur a détecté. Le compilateur est bavard et essaie de vous aider : en général il donne la ligne à laquelle il pense avoir trouvé l’erreuret la nature de l’erreur. Le message, en anglais avec un vocabulaire parfois abscons, peut paraître déroutant au début mais ce sont toujours les mêmes erreurs qui reviennent et auxquelles on s’habitue. Il serait dommage de se priver de l’aide précieuse du compilateur pour trouver ses erreurs!
— soit aucun message n’apparaît et le terminal vous redonne une invite de commande : cela signifie que la compilation a réussi et un nouveau fichier, nommé s’est matérialisé dans votre répertoire de travail. Vous pouvez alors exécuter le programme par l’instruction
À chaque modification du fichier source , il faudra bien évidemment compiler à nouveau le programme par la même commande et l’exécuter de nouveau.
Par exemple, pour compiler le deuxième programme de la section précédente (calcul de l’aire du cercle) écrit dans un fichier , il faudra taper g++ -o -lm
où -lm indique au compilateur d’aller chercher à l’endroit idoine le lien vers les fonctions mathématiques de <cmath> . Pour le troisième programme précédent (calcul de l’inverse d’une matrice) nommé , il faut tout d’abord installer sur l’ordinateur la bibliothèque Eigen (facile sur un système Linux : il suffit d’installer le paquet libeigen3-dev ), repérer où elle a été installée (ou se référer à la documentation) et enfin entrer dans le terminal la commande g++ -I /usr/include/eigen3 -o
De nombreuses autres options de compilations existent et leur invocation commence toujours par un tiret -. La figure 2.1 indique les options les plus fréquentes. Il suffit de taper man g++ dans le terminal ou de se référer à la documentation complète de g++ pour obtenir la liste exhaustive de toutes les options possibles.
Lorsque la longueur d’un programme augmente nettement ou lorsque l’on souhaite réutiliser des morceaux de code pour différents programmes, il est indispensable de découper un programme en différents modules ou bibliothèques. Dans ce cas, un seul morceau du programme final contient la fonction main() et les autres morceaux contiennent des définitions de fonctions auxiliaires.
Étudions un exemple simple. Imaginons que nous ayons un programme en trois morceaux structurés de la manière suivante :
— le fichier contient le code de fonctions int f1(void) , int f2(int) et void f3(void) et utilise les bibliothèques <iostream> et <cmath> ,
— le fichier contient le code de deux fonctions double g(int) et double h(double) , utilise la bibliothèque <fstream> et la fonction h() fait
appel à la fonction f3() du morceau précédent,
| Option | Argument | Usage |
| -std= | c++98, c++11, | Utilisation d’une version particulière du standard du langage C++ (98, 03, 11, 14 et bientôt 17). |
| -O1, -O2, -O3, -Os | Optimisation du code par le compilateur selon différents niveaux. | |
| -Wall | Affiche tous les avertissements sur des pratiques considérées comme douteuses. | |
| -pedantic | Vérifie que le code est compatible avec toutes les normes ISO et est syntaxiquement parfait. | |
| -ggdb | Produit des informations de débogage pour le programme GDB (non utilisé dans ce cours). | |
| -gp | Produit des informations de profilage pour le programme gprof qui permet d’estimer le temps de calcul passé dans chaque fonction. | |
| -pthread | Permet de paralléliser un programme en utilisant plusieurs cœurs d’un processeur et une bibliothèque idoine. |
Figure 2.1 – Options de compilation de g++ les plus fréquentes.
Il faut utiliser alors cinq fichiers, les trois précédents et deux fichiers d’en-tête. Les fichiers d’en-têtes sont des fichiers avec un suffixe en .hpp et contiennent toutes les définitions nécessaires pour assurer les compilations séparées des morceaux. Nous pouvons à présent entrer dans le contenu des différents fichiers :
— le fichier d’en-tête contient :
| #include<iostream>#include<cmath> #ifndef MORCEAU1 #define MORCEAU1int f1(void); int f2(int); int f3(void); #endif |
2
4
6
8
Il y a la liste des bibliothèques nécessaires pour la compilation de et l’annonce des fonctions de ce même fichier, afin que celles-ci soient connues d’autres fichiers qui pourraient les utiliser.
— le fichier contient une première ligne #include""
pour connaître les bibliothèques requises puis le code des trois fonctions f1() ,
f2() et f3() .
— le fichier contient
| #include<fstream> #include"" #ifndef MORCEAU2 #define MORCEAU2double g(int); double h(double); #endif 4 6 8 et sa deuxième ligne permet à de savoir que la fonction f3() existe quelque part dans un autre morceau. — le fichier contient #include"" puis le code des fonctions g() et h() . — le fichier contient
2 4 6 car la fonction main() a besoin de connaître les prototypes de toutes les fonctions des morceaux qu’elle peut utiliser, ainsi que les bibliothèques nécessaires. La compilation se fait ensuite en trois étapes distinctes, morceau par morceau : g++ -c -lm g++ -c g++ morceau1.o morceau2.o -o L’option -c des deux premières lignes indique que le compilateur ne doit pas attendre de fonction main() , ni produire un fichier exécutable mais seulement produire des fichiers compilés : chacune de ces deux lignes produit un fichier morceau1.o ou morceau2.o . La dernière ligne compile le fichier et l’assemble avec les autres fichiers objets .o pour produire l’exécutable final. Le lancement de l’exécutable final se fait alors par la commande Si l’on modifie l’un des morceaux, il faut recompiler ce dernier ainsi que le fichier final. Cette procédure est assez lourde mais devient inévitable lorsque plusieurs personnes travaillent chacune sur un morceau d’un programme. Il nous reste à présent à expliquer les lignes qui commencent par des croisillons # : c’est le but de la section suivante. Remarque : on ne compile jamais un fichier d’en-tête, d’extension .hpp! Si vous le faites, cela peut produit des fichiers avec extension qui ont potentiellement une taille énorme et nuiront à vos compilations suivantes. 2.4.3 Les directives de précompilationAvant la compilation proprement dite qui transforme nos instructions en tâches réalisables par le processeur, g++ a besoin de préparer le code et le programmeur peut influencer sur cette préparation par des directives de précompilation qui commencent systématiquement par un croisillon # . La plus fréquente est la directive d’inclusion #include qui indique au compilateur quelle bibliothèque utiliser pour comprendre notre code. Les bibliothèques externes installées sur la machine doivent être appelées par leur nom entre chevrons <nom_de_la_bibli> . Pour des bibliothèques faites par l’utilisateur, leur chemin d’accès doit être spécifié entre guillemets "" avec mention de l’extension .hpp . Les directives de précompilation peuvent elles-mêmes contenir des tests logiques qui ont leur syntaxe propre. C’est en particulier utile pour des programmes réalisés en plusieurs morceaux qui ont chacun besoin d’une même bibliothèque. Reprenons l’exemple de la section précédente. Les fichiers et ont tous deux besoins de la bibliothèque et a elle-même besoin de la bibliothèque : le fichier a donc besoin deux fois de , une fois directement et une fois à travers . Ce n’est pas évident a priori mais cela pose un problème au compilateur! En effet, il voit les mêmes fonctions déclarées plusieurs fois et, afin d’éviter toute collision malencontreuse, préfère afficher un message d’erreur. Il existe une solution simple pour éviter ce désagrément : insérer un test lors de la précompilation comme cela a été fait dans les fichiers et de l’exemple précédent : — donner un nom à la partie du code concernée (ici la déclaration des fonctions de chaque fichier .cpp ), — vérifier si le morceau est déjà défini par #ifndef LE_NOM (IF Not DEFined), 2.4.4 Durée d’exécution d’un programmeAfin de tester l’efficacité d’un programme, il est facile de mesurer le temps d’exécution d’un programme sous Linux en utilisant la commande time lors de l’exécution du programme : time ./NOM_DE_L_EXECUTABLE Plusieurs informations s’affichent alors : seul le premier temps, exprimé en secondes, nous intéresse : il correspond au temps mesuré par le système d’exploitation entre le début et l’arrêt du programme. Cet outil est utile pour mieux comprendre la notion de complexité : dans les différents exercices de TP, nous vous conseillons de mesurer la variation du temps d’exécution lorsque la taille des données à traiter varie. Une complexité en O(Nα) correspond à un temps d’exécution multiplié par environ 2α lorsque la taille des données est multiplié par deux. 2.4.5 [hors programme] Compilation pour utilisation par d’autres lan- gages de programmation : l’exemple de swigComme vous l’avez probablement découvert les années précédentes, il existe d’autres langages de programmation comme Python dont la syntaxe est bien plus légère, qui permet de faire l’affichage facilement mais que l’usage non-optimisé de la mémoire rend peu efficace pour des calculs numériques lourds. Il est donc souvent très intéressant de combiner la puissance des différents langages mais cela requiert d’écrire des interfaces pour passer de l’un à l’autre. En pratique, cela signifie qu’il y a besoin des briques suivantes : — un programme et son en-tête en C++ à convertir en une bibliothèque Python — des fichiers de description qui indiquent quelles options de compilation utiliser, quelles bibliothèques charger, etc. — un logiciel qui fasse les bonnes compilations, produise une bibliothèque Python et écrive un programme qui permette la conversion systématique des objets d’un langage vers l’autre.
2 4 6 8 10 12 14 et il y a un fichier qui contient les codes des différentes méthodes. Nous souhaitons à présent l’utiliser en Python. Pour cela, nous devons créer les fichiers suivants : — un fichier RW.i , destiné à swig , qui explique à ce dernier qu’on utilise l’instanciation std::vector<int> de la STL (en effet, Python n’a ni template, ni STL mais swig sait transformer certains vecteurs de la STL du C++ en objet Python via sa propre bibliothèque std_vector.i ) :
1 2 3 4 5 6 7 8 9 — un fichier qui explique à swig les caractéristiques de la compilation (utilisation de C++11 , d’un éventuel parallélisme, etc) et de la bibliothèque Python à bâtir :
1 2 3 4 5 6 7 8 9 Ensuite, la magie de swig opère avec l’exécution successive dans le terminal des commandes suivantes :
1 2 La première ligne produit un nouveau fichier en C++ qui contient le code nécessaire pour la conversion des différents objets entre Python et C++.
1 2 3 4 5 6 et produit la sortie :
1 2 3 que nous allons à présent commenter. La première ligne du programme charge la nouvelle bibliothèque. La déclaration d’un objet a de la classe RW en ligne 2 utilise le constructeur de la classe RW . L’affichage de a montre qu’en fait c’est un raccourci vers un objet swig sur un certain emplacement mémoire. L’utilisation des méthodes de la classe se fait en Python comme en C++ en lignes 4 et 5. Le résultat de la ligne 5 est intéressante : elle utilise la méthode trajectory du C++ qui produit en C++ un vecteur de la STL; la surcouche introduite par permet une conversion automatique vers le vecteur u en Python. Il est très facile de généraliser l’exemple précédent à des bibliothèques beaucoup plus évoluées, tant que swig sait convertir les objets nécessaires de la STL vers d’autres langages. Remarque : coût de la conversion. La solution présentée ici peut sembler magique et naturelle. Il faut néanmoins se méfier des coûts de calcul cachés dans la conversion. La conversion entre vecteur de la STL du C++ et vecteur Python de la ligne 5 du programme précédent exige de parcourir le vecteur en entier (complexité en O(N)) : si les tailles sont grandes et que de trop nombreuses conversions sont utilisés, le programme peut passer plus de temps à réaliser l’interface entre langages qu’à calculer des résultats mathématiques! Exercices Exercice 2.1. Soient les fichiers suivants : — fichier a.hpp
2 4 6 — fichier a.cpp
2 — fichier b.hpp
2 4 6 8 — fichier b.cpp
2 4 — fichier c.hpp
2 4 — fichier c.cpp
2 — fichier d.cpp
2 4 6 8 10 12 Compléter les en-têtes des fichiers puis écrire toutes les commandes de compilation pour obtenir un fichier de sortie intitulé et l’exécuter plusieurs fois. Essayer de comprendre l’affichage du programme. Chapitre 3 La syntaxe du C++ 3.1 Les types 3.1.1 GénéralitésDéfinition d’une variable. L’objet élémentaire de la programmation est la variable qui permet de stocker dans la mémoire un objet mathématique. La notion de variable en informatique est plus évoluée que la notion mathématique de variable. En effet, dans un langage dit « fortement typé » comme le C++, une variable est définie comme un espace réservé en mémoire décrit par quatre qualités : 1. son nom qui permet de l’identifier et la manipuler dans un programme, 2. son type qui est la convention de codage choisie pour la stocker dans la mémoire, 4. sa valeur qui est la séquence de bits écrite à son adresse dans la mémoire. Le nom est choisi par le programmeur et n’a aucune incidence sur l’exécution du programme : il est donc important de choisir des noms les plus explicites possible afin d’être capable de lire efficacement des lignes de code. La valeur est remplie directement par le programmeur par une affectation soit d’une valeur choisie au préalable, soit du résultat d’une fonction. L’adresse est le plus souvent choisie directement lors de l’exécution du programme par le système d’exploitation qui cherche un espace disponible dans la mémoire et le réserve temporairement pour notre programme. Le type est choisi par le programmeur lorsqu’il donne pour la première fois le nom d’une variable. Il est important de prendre conscience que la notion de type dépasse la description mathématique d’un objet et reste intimement liée à la gestion de la mémoire. Prenons l’exemple d’un entier n = 19 = 16 + 2 + 1 = 24 + 21 + 1 = 100112 en base 2 : la mémoire de l’ordinateur est faite de bits prenant les valeurs 0 et 1 et le codage en base 2 est le plus naturel. Encore faut-il choisir une convention pour savoir si l’on écrit les chiffres de gauche à droite ou à l’envers, une autre convention pour savoir où on écrit le signe de l’entier, etc. La même question se pose pour les réels afin de distinguer des écritures du type 10413 = 10,413 × 103 = 1,0413 × 104. Il est important de noter que le seul codage ne suffit pas pour avoir un type facilement manipulable : il faut également décrire les opérations élémentaires nécessaires (par exemple l’addition et le produit pour les entiers). Il y a ainsi trois aspects à maîtriser : 23 — apprendre à utiliser la plupart des types usuels du C++ pour un usage mathématique élémentaire (cette section a pour but de les présenter), — apprendre à créer des nouveaux types à partir des types élémentaires (c’est le but des chapitres 5 et 6). Nous vous conseillons de bien travailler les deux premiers aspects avant de passer vous-même à la création de nouveaux objets. Utilisation d’une variable. Avant toute utilisation, une variable doit être déclarée de la manière suivante :
2 en écrivant son type (ici deux entiers puis un caractère) puis le nom de la variable puis un point-virgule qui marque en C++ la fin d’une instruction. L’affectation d’une valeur à une variable se fait par l’intermédiaire du signe = :
2 4 Contrairement à l’usage mathématique, le signe = n’est pas un test d’égalité et n’est pas symétrique mais permet seulement de recopier la valeur du membre de droite dans la variable du membre de gauche. Ainsi, 19=z; conduit à une erreur de compilation. D’autre part, il est important qu’à gauche et à droite d’un signe = , les deux objets aient le même type. Il est possible de déclarer et initialiser une variable simultanément en écrivant : int z=19;Durée de vie et effacement. Une variable a une durée de vie et n’est définie que dans le bloc d’instruction où elle est déclarée, un bloc d’instructions étant délimité par des accolades { } . Après la fin de ce bloc, l’espace mémoire où elle était stockée est effacé et son nom oublié : il est donc important de déclarer les variables aux bons endroits afin de ne pas perdre leur contenu en terminant un bloc d’instructions. La question de la durée de vie est la source de nombreuses erreurs de programmation. — short int : codé sur 2 octets (16 bits, un pour le signe et ensuite 15 bits pour le codage du nombre en base deux : on peut donc atteindre 215 = 32768, c’est peu), — int : codé sur 4 octets (32 bits, un pour le signe et ensuite 31 bits pour le codage du nombre en base deux, valeur maximale 2147483648) — long int : codé sur 4 ou 8 octets — long long int : codé sur 8 octets depuis la norme de 1998. Plus le stockage est gros, plus les opérations seront lentes : c’est le prix à payer pour atteindre de grandes tailles. Pour affecter des valeurs à ces variables, on peut les entrer directement : — soit en base 10 : int n=534; — soit en base 8 en faisant précéder les chiffres par un zéro 0 muet : int n=01026; — soit en base 16 en faisant précéder les chiffres par un 0x muet : int n=0x216;Si l’on souhaite n’utiliser que des entiers positifs, il est possible de récupérer le bit de signe pour multiplier par deux les valeurs maximales en déclarant les entiers par le type unsigned :
2 Enfin, il existe une dernière manière de préciser la longueur du codage en utilisant int_Nt (ou uint_Nt pour la version sans signe) avec le symbole N remplacé par 8, 16, 32 ou 64 selon le nombre de bits utilisés. Les opérations arithmétiques élémentaires disponibles sur les entiers sont les suivantes : — l’addition et la soustraction par les symboles + et -
2 — le passage à l’opposé par le signe - :
2 — la multiplication par le symbole * (qui doit impérativement être écrit)
2 — le reste modulo m par le symbole % et le quotient euclidien par m par le symbole /
2 Dans les exemples précédents, nous avons rempli la valeur d’une troisième variable par opération sur deux autres variables. Très souvent, on souhaite seulement actualiser la valeur d’une variable en la combinant avec une autre. Il y a alors deux solutions et les deux codes suivants sont équivalents :
2
2 Il n’y a (presque) aucune différence d’efficacité entre ces deux syntaxes et l’on peut choisir ce que l’on préfère. Il faut néanmoins être capable de comprendre les deux pour les circonstances où l’on doit lire le code d’autrui. Ces opérateurs existent bien évidemment également pour la soustraction, le reste euclidien et le quotient euclidien avec -= , /= et %= . Enfin, lors du parcours d’une boucle, il est très fréquent de devoir incrémenter un compteur de 1; il existe quatre manières équivalentes de le faire :
2 4 et, bien évidemment, la même syntaxe marche avec le signe - en lieu et place du signe + . Il existe une subtilité entre les deux derniers opérateurs et, pour éviter les pièges, nous déconseillons leur utilisation autrement qu’isolément. Les « flottants »Les problèmes de taille de stockage rencontrés pour les entiers se révèlent encore plus problématiques pour les nombres réels. De manière générale, il est raisonnable de considérer — du point de vue du programmeur — qu’il n’existe pas de nombres réels en informatique. La notion la plus proche est celle de « flottants » qui correspond à l’écriture d’un nombre réel sous la forme 254,36 = 2,5436 × 10 = 11111110,010111 = 1.111111100101112× 27 = 1.111111100101112× 21112 Les différents types de « flottants » sont ainsi caractérisés par le nombre de bits alloués à l’exposant et à la mantisse (tous deux écrits en base 2) : — float : codé sur 4 octets, i.e. 32 bits (1 bit de signe, 8 bits pour l’exposant, 23 bits pour la mantisse), cela permet de couvrir des réels tronqués au sixième chiffre après la virgule et des exposants variant de −38 à 38. — double : codé sur 8 octets, i.e. 64 bits (1 bit de signe, 11 bits d’exposants et 52 bits pour la mantisse), cela permet de couvrir des réels tronqués au quinzième chiffre après la virgule et des exposants variant de −308 à 308. Il existe également un type long double mais nous ne l’utiliserons pas car les erreurs d’arrondi sont le plus souvent causées par des problèmes de calculs qui ne relèvent pas du choix des double . En général, nous choisirons de manière quasi-systématique les double . Les opérations arithmétiques usuelles sont disponibles avec la même syntaxe que pour les entiers. Il est important de remarquer que la division avec l’opérateur / réalise pour, les flottants, la division réelle (multiplication par l’inverse) et non la division euclidienne, celle du cas entier. Un piège fréquent consiste à utiliser l’une à la place de l’autre. Le résultat de 11/3 vaut 3 alors que 11/3.0 vaut 3,66666. Les booléensLes tests logiques n’ont que deux valeurs possibles, comme en mathématique : vrai et faux. Sur ces valeurs, il existe des opérations logiques élémentaires comme « et », « ou », « non », etc. Tout cela est géré en C++ par le type bool . Une variable de type bool ne prend que deux valeurs possibles, true (écrit aussi 1 ) et false (écrit aussi 0 ). Le tableau suivant résume les opérations logiques élémentaires :
2 4 6 8 10 12 14 16 18 20 22 24 26 Cette définition doit être écrite dans un en-tête .hpp qui doit être inclus dans tous les fichiers qui utilisent des objets de cette classe. Attention, la déclaration de la classe doit se terminer absolument par un point-virgule! La partiepublic . La définition d’un objet de type NOM_DE_LA_CLASSE se fait comme toutes les déclarations de variables par : NOM_DE_LA_CLASSE nom(argumentsK);où la liste des arguments argumentsK doit correspondre à l’un des constructeurs de la classe. Comme pour les types usuels, à l’issue de cette déclaration, une zone de la mémoire est allouée à la variable nom : cette zone correspond à tous les champs publics et privés champ1 , etc., champA , etc. Si le constructeur numéro K contient des new , de la mémoire supplémentaire est allouée. L’initialisation de toutes ces zones mémoires se fait selon les instructions écrites dans les constructeurs; si rien n’est écrit à ce sujet, les valeurs d’initialisation sont imprévisibles. Une fois cette variable nom déclarée, le programmeur a le droit d’accéder à tous les champs étiquetés public par la syntaxe : nom.champcomme pour les struct . Le programmeur a également le droit d’appeler toutes les méthodes étiquetées public par la syntaxe : Seule la partie public intéresse les utilisateurs de la classe. La partieprivate . Les champs et méthodes étiquetés private ne sont utilisables qu’à l’intérieur du code des méthodes publiques ou privées (ainsi que par les fonctions externes déclarées friend , cf. plus bas) et nulle par ailleurs. Cela permet d’éviter qu’un utilisateur de la classe qui ne connaît pas son fonctionnement interne n’écrive des instructions dangereuses. La partie private n’intéresse donc que les concepteurs de la classe et non les utilisateurs. Description des méthodes de la classe. Seuls les prototypes des méthodes figurent dans la classe. Le code des méthodes est écrit dans un fichier d’extension .cpp qui doit inclure le .hpp de définition de la classe et qui doit être compilé séparément. Dans ce fichier .cpp , il n’y a plus de distinctions entre public et private et l’ordre d’écriture des codes n’importe pas. Normalement, un utilisateur de la classe n’a jamais à ouvrir ce fichier; d’ailleurs, il arrive fréquemment que seule la version compilée soit fournie à l’utilisateur. La définition d’une méthode se fait comme la définition d’une fonction, à ceci près qu’il faut spécifier la classe à laquelle elle appartient avec l’opérateur de résolution :: comme ceci :
2 4 Lors de l’écriture du code d’une méthode, il faut toujours garder à l’esprit qu’elle contient un argument de plus que ceux écrits dans son prototype. En effet, elle est toujours utilisée associée à un objet par var.nom_de_la_methode(args) et il faut considérer l’objet d’appel comme un argument supplémentaire fantôme. On accède à son adresse par le pointeur this ou en faisant mention du champ ou de la méthode sans préfixe. t+= this->coeffs[i*n+i];Qualificatifconst . Lorsqu’une méthode d’une classe ne modifie pas les champs de l’objet sur lequel elle est appelée, il faut l’étiqueter const . Ce mot-clef doit être placé à la fin du prototype à l’intérieur de la classe ainsi que lors de la définition de la méthode. Il n’est appuyé à aucun argument de la liste d’arguments et par convention s’applique à l’objet d’appel pointé par this . Son usage est obligatoire. En effet, une méthode étiquetée const (ou une fonction extérieure à la classe dont un argument est un objet de la classe et est marqué const ) ne peut faire intervenir bien évidemment que des méthodes étiquetées const . Oublier de qualifier une méthode const restreint donc son utilisation. Or, de nombreux opérateurs déjà présents dans des bibliothèques comportent des const , comme par exemple + et << . Oublier tous les const dans une classe empêche donc d’utiliser ces opérateurs! Qualificatifstatic devant un camp privé. Il est possible d’ajouter le mot-clef static devant un champ privé dans la définition d’une classe. Alors, ce champ sera commun à tous les objets de la classe. Cela peut être utile pour éviter de stocker une même information, parfois volumineuse, dans toutes les instances d’une classe ou bien pour étudier des caractéristiques globables d’une classe, par exemple connaître en temps réel le nombre d’objets existants de la classe. Il faut alors faire attention aux constructeurs et destructeurs comme expliqué ci-dessous. L’initialisation d’une telle variable doit se faire une seule fois dans le code à travers la syntaxe TYPE NOM_CLASSE::NOM_VARIABLE = VALEUR;De plus, cette variable n’étant plus liée nécessairement à un objet de la classe, elle peut être utilisée librement avec la syntaxe NOM_CLASSE::NOM_VARIABLE , indépendamment de toute déclaration d’objets de la classe. 5.2.1 Accesseurs et mutateursPlusieurs méthodes sont très simples et consistent à donner l’accès à certains champs privés, en lecture ou en écriture : ces méthodes sont appelées accesseurs (lecture seule) et mutateurs (écriture). Il pourrait sembler a priori stupide de restreindre l’accès à des champs par le mot-clef private pour ensuite le rétablir avec des accesseurs et mutateurs. Néanmoins, cela ne l’est pas pour plusieurs raisons. Tout d’abord le mot-clef private ne distingue pas lecture et écriture. D’autre part, cela simplifie grandement la structure du code à écrire lorsqu’il y a de l’héritage de classe (cf. la section 5.4). Enfin, nous verrons dans le chapitre 6 qu’il est pratique d’avoir des méthodes qui portent les mêmes noms dans différentes classes, même si, en arrière-plan, la structure interne des champs privés des objets est très différente. Sauf exception, la règle d’or à adopter est de mettre tous les champs dans la partie private et de rétablir les accès en lecture et écriture par des accesseurs et des mutateurs au cas par cas. Un accesseur et un mutateur doivent avoir en général le même nom (puisqu’ils concernent le même champ!) et ne diffèrent que par leur prototype. Un accesseur donne l’accès en lecture donc doit être étiqueté const et produit une valeur qui sera stockée ou utilisée ailleurs. Un mutateur donne l’accès en écriture donc ne doit pas être étiqueté const et produit une référence vers l’objet à modifier. Dans les deux cas, leur code tient en une seule ligne et consiste à renvoyer le champ souhaité : pour que le compilateur puisse optimiser le programme, il est préférable d’écrire ce code directement dans la définition de la classe. Un exemple fondamental. Prenons un exemple abstrait mais minimal :
2 4 6 8 Considérons les lignes de code suivantes, trions celles qui sont acceptables ou non et essayons de comprendre si c’est le mutateur ou l’accesseur qui est utilisé :
2 4 6 8 10 Dans les deux dernières lignes, il faut se référer aux prototypes de reset et << qui contiennent un const sur l’argument et donc seule une méthode const peut être utilisé sur a : cela exclut donc le mutateur. Dans l’exemple de la figure 5.2 sur les matrices, l’opérateur () qui renvoie un double & est un mutateur de la case (i,j) de la matrice, alors que le même opérateur, du même nom, mais avec un const et sans référence est un accesseur. De même la méthode taille() est un accesseur à la taille de la matrice. Un exemple plus élaboré (hors programme mais instructif) qui illustre le rôle des copies et références. Le but de cet exemple est de montrer que, dans certaines circonstances, le prototype des accesseurs peut être amélioré pour maintenir une bonne efficacité de calcul. Considérons ainsi la classe suivante :
4 6 8 10 12 14 16 18 20 (a) Devinez le résultat du code suivant puis vérifiez en l’exécutant :
2 4 6 8 10 12 14 16 18 20 22 (b) Devinez le résultat du code suivant puis vérifiez en l’exécutant :
2 4 6 8 10 12 14 16 18 20 22 24 Exercice 5.3. (accesseurs et mutateurs) Soit la classe définie dans le fichier par :
2 4 6 8 10 12 14 16 Deviner et comprendre l’affichage du code suivant :
2 4 6 8 10 12 14 16 18 108 CHAPITRE 5. PROGRAMMATION ORIENTÉE OBJET ET CLASSES Chapitre 6 ne diffèrent que par leur prototype :
2 Il faudrait également que toute personne qui concevrait une nouvelle classe pour laquelle le symbole < aurait un sens écrive également sa propre fonction min en recopiant une fois de plus ces instructions. C’est long, fastidieux et source d’erreurs de copie s’il faut le faire pour de nombreuses fonctions et que le code de chacune ne tient pas en une ligne Pour simplifier, cela le C++ offre la syntaxe suivante :
2 Cela s’appelle un modèle de fonction (ou « template » en anglais) et cela décrit un algorithme de calcul du minimum sans se soucier de la nature exacte des objets. Nous voyons également que le type d’objet devient lui-même un paramètre, appelée ici T , qui doit donner le nom d’un type et donc qualifié par typename . L’utilisation d’un tel modèle se fait alors simplement par des appels du style :
2 109 De la géométrie dans Rn. Imaginons que nous souhaitions manipuler des points dans un espace de dimension n fixée sur R ou sur C, par exemple pour faire de la géométrie dans le plan ou dans l’espace. La dimension de l’espace est fixée a priori ainsi que le corps de base. Pour un décrire un point dans Kn, on peut ainsi construire un modèle de classe tel que celui décrit dans la figure 6.1. On déclare alors un point de R3 par Point<double,3> P; et un point de C2 par Point<Complexe,2> Q; à condition d’avoir préalablement défini (ou chargé à partir d’une bibliothèque) une classe qui décrive les nombres complexes avec leurs opérations usuelles. Les modèles std::vector et std::list de la STL. Nous avons déjà manipulé des modèles de classe en utilisant les bibliothèques std::vector et std::list . En effet, la majorité des algorithmes ( push_back() ou l’opérateur de [] ) ne dépendent pas de la nature des objets placés dans un tableau ou une liste. Ce sont donc des modèles de classes que la STL définit et cela explique les notations std::vector<double> avec des chevrons. 6.1.2 Vocabulaire et syntaxeLa déclaration d’un modèle (« template ») de fonction ou de classe est toujours défini par la syntaxe :
2 4 6 8 où A1 , A2 , etc sont appelés paramètres du modèle et sont de typesoit class ou typename (i.e. ce sont des noms de types), soit int . Le prototype, le code et les définitions peuvent alors utiliser A1 , A2 , etc., partout où sont attendus soit des noms de type, soit des valeurs d’entiers. L’appel d’un modèle de fonctions sur des arguments se fait par NOM_DE_LA_FONCTION < VALEUR_DE_A1, VALEUR_DE_A2, > ( ARGUMENTS )et la déclaration d’un élément d’une classe par 6.1. INTRODUCTION À LA PROGRAMMATION GÉNÉRIQUE
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 Figure 6.1 – Exemple de modèle de classe pour décrire des points dans Kn où K est un corps quelconque et n un entier plus grand que 1.
Un choix de valeurs de paramètres A1 , A2 , etc pour un modèle s’appelle une instanciation du modèle. 6.1.3 Structure du code et compilationLe traitement des modèles par le compilateur est très spécifique et nécessite d’être bien maîtrisé pour comprendre l’utilisation de template . Virtuellement, toutes valeurs des paramètres de modèle A1 , A2 , peuvent être choisies mais toutes les instanciations possibles ne sont pas compilées bien évidemment. Le compilateur lit l’intégralité du code qui utilise des template et établit la liste des instanciations nécessaires pour l’exécution du code. Ensuite, il reprend le modèle de template en substituant les valeurs de paramètres nécessaires et compile successivement chaque instanciation.
La deuxième conséquence est que le code de modèles de classes ou de fonctions ne peut pas être compilé séparément à l’avance, comme c’est le cas pour des fonctions ou des classes, car on ne connaît pas les valeurs de paramètres qui seront choisies pour les instanciations : en effet, c’est le type précis des objets qui dicte la gestion de la mémoire et donc les instructions machine. L’intégralité du code d’untemplate doit figurer dans le .hpp et ne peut plus être scindé entre déclarations dans le .hpp et le .cpp . C’est une erreur très classique à laquelle il faut faire extrêmement attention. La troisième conséquence est que la compilation en présence d’un template peut être longue puisque le compilateur doit parfois compiler de très nombreuses instanciations différentes d’un même template . Enfin, il y a un avantage majeur à utiliser des template avec des paramètres entiers pour l’optimisation du code par le compilateur. Puisque la valeur d’un paramètre entier d’un template est connu dès la compilation, le compilateur peut faire des choix particuliers qui utilise cette valeur pour simplifier des morceaux de code et supprimer des tests inutiles. L’accélération est notable dans de nombreux cas et a fait le succès de bibliothèques comme boost par exemple. Revenons sur le cas particulier de l’exemple de géométrie précédent. Sans la notion de template , nous aurions écrit (pour des coordonnées réelles) une classe :
2 4 6 8 6.1. INTRODUCTION À LA PROGRAMMATION GÉNÉRIQUE
10 12 for( inti=0; i < n; i++) p[i]++;parce qu’il sait que n vaut 3 (parce que c’est par exemple un paramètre de modèle), il prend si nécessaire la liberté de transformer le code en
2 Cela permet de ne pas avoir à calculer l’incrément i++ ni à faire le test i<n à chaque itération. Ce sont des opérations certes rapides mais malheureusement très nombreuses en calcul intensif par exemple. Pour décider si un paramètre entier doit être passé en template , il faut trouver un compromis entre la liberté de fixer une valeur à l’utilisation (sans template donc) et le gain de temps de calcul (avec template ). Seul l’usage que l’on destine au programme permet de juger. 6.1.4 Particularités pour les modèles de classeLa définition des méthodes d’un modèle de classe ne se fait plus dans le .cpp mais dans le .hpp après la définition de la classe. Il peut donc y avoir une compilation de moins. La définition d’une méthode d’un modèle de classe se fait en écrivant à nouveau template mais la classe doit être instanciée avant l’opérateur de résolution :: comme l’indique l’exemple de la figure 6.1 aux lignes 24, 27 et 30. Comme pour les fonctions et les classes, il est possible de déclarer des liens d’amitié entre modèles de fonction et modèles de classes avec le mot-clef friend . Considérons l’exemple minimal suivant :
2 Il faut interpréter ces modèles comme une collection de classes A<K> pour toutes les valeurs de K et, pour chacune d’elle, on a une fonction qui prend en argument un objet de type
2 4 pour le premier cas (amitiés entre toutes les instanciations de chaque) et
2 4 pour le deuxième cas (amitiés seulement entre des instanciations associées). 6.1.5 Redéfinition d’une instanciation particulièreSupposons que nous ayons un template donné par
2 4 et que nous sachions que, si A est double , nous connaissions une version simplifiée de la structure. Alors, nous pouvons ajouter après le code précédent la nouvelle définition
2 4 Il est aussi possible de spécifier tous les arguments du template avec la syntaxe
2 4 Pour des templates de fonctions, cela fonctionne de la même manière mais il n’est pas possible d’avoir des spécialisations partielles mais seulement des redéfinitions avec tous les arguments de template fixés. Par exemple, nous pouvons écrire
2 4 6 8 Ces spécialisations sont particulièrement utiles lors de définitions récursives de templates sur les entiers pour fixer la valeur initiale de la récurrence. Ce qui diffère d’un template à l’autre est la présence d’un ordre entre les éléments et la navigation dans la mémoire d’un objet de la collection à l’autre. Outre la nature indifférenciée des éléments des conteneurs, on peut également une couche supplémentaire de templates en écrivant des algorithmes qui ne dépendent pas (ou presque pas) de la nature exacte du conteneur : c’est précisément ce qui fait dans la bibliothèque <algorithm> . 6.2.2 Objets mathématiques standardsDifférents objets mathématiques classiques donnent lieu à des modèles de classe à cause de la présence de différentes classes pour décrire les mêmes objets mathématiques avec des précisions variées. Un premier exemple est la bibliothèque <complex> . Les nombres réels sont remplacés par des flottants avec des précisions variées selon que l’on choisit des float , double et long double . Cela se répercute sur les complexes que l’on peut décrire comme des couples de réels : la bibliothèque <complex> permet de définir des nombres complexes avec une précision voulue avec un modèle de classe std::complex<T> où T est l’un des trois types de flottants rappelés ci-dessus. Un deuxième exemple est la bibliothèque <random> en C++ 11 déjà introduite au chapitre 4 : les variables aléatoires classiques sont à valeurs dans Z ou R. En C++, il faut donc décider avec quelle précision les variables aléatoires doivent être générées : les lois à support dans Z sont donc des modèles de classes dont le paramètre du modèle est l’un des types int , long int et les lois des variables à support dans R sont ainsi décrites par des modèles de classe de paramètre float , double ou long double . Les matrices de la bibliothèques Eigen sont présentes sous deux formes différentes :
2 L’avantage du premier est la possibilité pour le compilateur d’optimiser le code s’il l’estime nécessaire (par exemple en déroulant des boucles courtes si N et M sont petits). L’avantage du second est de laisser à l’utilisateur le soin de fixer la taille des matrices B ainsi que de pouvoir modifier la taille des matrices en court d’exécution. Pour les matrices qui contiennent beaucoup de zéros, Eigen contient également un format appelé sparse qui permet de ne stocker en mémoire que les coefficients non nuls des matrices. Pour tirer un profit véritable de cette bibliothèque, il convient de compiler avec les options d’optimisation -O2 et -O3 : nous vous invitons à effectuer les comparaisons de temps d’exécution chez vous selon l’activation ou non de ces options ainsi que selon l’usage de taille N et M ou Eigen::Dynamic . 6.2.4 Les nouveautés des standards récents de C++ et la notion de std : :tupleL’un des domaines où le standard C++ évolue le plus et acquiert de nombreux enrichissements est le domaine de la programmation générique. Ainsi, C++ a vu l’ajout dans le standard de 2011 des templates variadiques qui permettent d’avoir un nombre d’arguments du template indéterminé à la définition et fixé à l’instanciation. En particulier, l’usage des std::tuple introduit dans la bibliothèque <tuple> depuis C++ 11 permet de définir des fonctions avec plusieurs types de retours via un prototype du type std::tuple<int, double, std::string> f(int a);qui renvoie un 3-uplet de trois objets. La déclaration, la construction et l’accès à un élément d’un std::tuple se fait selon : std::cout << std::get<2>(A) << std::endl; int x; char c; std::string S; std::tie(x,c,S) = A; std::cout << x << " " << c << " " << S << std::endl; |
2
4
6
8
10
La fonction std::tie permet de répartir les éléments d’un std::tuple dans différentes références de variables préexistantes.
De manière générale, un template variadique se définit selon :
| template < classT, class T f(const classTypes & .. } | Types> guments) { | |
| . ar | ||
2
4
Nous vous conseillons néanmoins de bien maîtriser les templates présentés dans ce chapitre avant de vous intéresser aux nouvelles fonctionnalités.
Exercice 6.1. Soit le modèle de fonction suivant :
| template < classConteneur > void affichage(std::ostream & o, Conteneur C) { for(auto iterateur= ___ ; ____ ; ____ ){ o << ___; } return; } |
2
4
6
1. Compléter le template suivant pour qu’il puisse afficher le contenu de n’importe quel conteneur possédant des itérateurs et qui possèdent des begin() , end() et * que la STL. Les éléments doivent être séparés par des espaces.
2. Tester le programme sur le conteneur std::vector<double> ainsi que sur le conteneur std::list< std::string > .
3. Quelle condition d’utilisation y a-t-il sur le type des objets du conteneur?
Exercice 6.2. (important!) Écrivez des implémentations personnelles des algorithmes de la STL tels std::any_of , std::count_if , std::copy , std::transform , etc., et testez-les sur des exemples. Comparez-les ensuite au code de la STL pour le compilateur g++ .
Exercice 6.3. (héritage, modèles récursifs et vertige) Comprendre la structure de la classe Boite<10> , en particulier combien de champs a elle contient réellement. Quel est le résultat du programme?
int a;
public:
Boite(): Boite<p-1>(), a(p) {} void write() const ;
}; template <int p> void Boite<p>::affichage() const {
Boite<p-1>::write();
std::cout << "niveau " << p<< ": " << a << std::endl; }
template <> classBoite<0> { protected:
int a;
public:
Boite(): a(0) {}
void write() const { std::cout<< "niveau 0: " << a << std::endl;}
2
4
6
8
10
12
14
16
18
| }; int main() { Boite<10> u; std::cout << "Contenu de u:\n"; u.write(); } |
20
22
24
26
Exercice 6.4. Pour tout type T muni d’un produit * , d’une opération + et d’un opérateur d’affectation = et pour tout conteneur de la STL muni de la méthode size() , écrire un modèle de fonction
| template <classAnneau,classConteneur> Anneau scalaire(const Conteneur<Anneau> & A,const Conteneur<Anneau> & B); |
2
qui calcule ∑︀ni=1aibi où (ai) et (bi) sont les éléments ordonnés du conteneur. Le tester sur différents conteneurs et différents types numériques.
120 CHAPITRE 6. PROGRAMMATION GÉNÉRIQUE ET TEMPLATES
Chapitre 7
Les pointeurs forment un aspect incontournable des langages C et C++. D’autres langages, tel Python, ne les utilisent pas et ils ne sont donc pas incontournables a priori. Leur intérêt vient dès lors qu’on souhaite faire du calcul intensif car les pointeurs permettent de gérer la répartition de la mémoire et les accès à cette dernière de manière particulièrement efficace. C’est cela qui explique l’intérêt du C et du C++ pour des mathématiciens et c’est aussi pourquoi ce chapitre est essentiel dans ce cours.
La mémoire peut être décrite comme une longue suite unidimensionnelle de bits (ou plutôt d’octets, i.e. une suite de 8 bits) juxtaposés et numérotés de 1 jusqu’au dernier. Une variable de type élémentaire (cf. les exemples du chapitre 3) occupe en général une suite contiguë de bits en mémoire et son adresse est tout simplement les coordonnées en mémoire de son premier octet. Pour héberger ces coordonnées, il faut donc de nouvelles variables dont la valeur est l’adresse en mémoire d’un octet donné : ce sont les pointeurs.
Un type de pointeur générique est le type void * . Une variable p déclarée par l’instruction void * p est une variable dont la valeur pourra être l’adresse d’une autre variable. La variable p a sa propre adresse qui n’a rien à voir avec sa valeur et une valeur qui n’a rien à voir avec la valeur de la variable pointée.
Il faut retenir qu’un pointeur est utilisé pour naviguer efficacement entre les variables dans la mémoire sans avoir à se soucier de leur valeurs (cela est d’autant plus utile que les valeurs stockées sont complexes à manipuler). Pour cet aspect, il ressemble partiellement aux références.
121
premier bit une variable z sur 16 bits = 2 octets
Figure 7.1 – Dessin schématique de la mémoire. Nous avons décidé 240 bits=30 octets consécutivement (il faut imaginer que chaque ligne suit immédiatement la précédente). La variable z peut être aussi bien du type short int ou char[2] car elle occupe deux octets.
On remarque également que l’adresse donnée par le pointeur ne donne aucune information sur la taille occupée en mémoire par la variable. Cet inconvénient est partiellement contournée par l’introduction de différents types de pointeurs, correspondant à tous les types déjà introduits. Un pointeur vers un entier a un type int * , un pointeur vers un flottant a un type float * ou double * . Ces types seront utilisés d’ici quelques paragraphes pour translater des adresses selon un mécanisme que nous préciserons mais, formellement, ils sont tous du même type et peuvent être convertis les uns dans les autres indifféremment par conversion implicite.
L’adresse d’une variable préexistante est récupérée par l’opérateur & , dont le symbole est appelé en français esperluette. L’accès à la valeur écrite à une adresse donnée se fait par l’opérateur * . Voici un exemple :
| int n=147, m=78; int * p1; double x=3.1415; double * p2; p1 = &n; // récupération de l'adresse de n std::cout << p1 << std::endl; // affichage de l'adresse de n // la valeur change à chaque exécution // le format n'est pas simple à interpréter m = *p1 ; // stockage dans m de la valeur pointée par p1 |
2
4
6
8
10
7.1. NOTIONS SUR LES POINTEURS
| std::cout << m << std::endl; // affichage de m qui vaut alors 147; p2 = &x; // récupération de l'adresse de x |
12
14
Dans l’exemple précédent, l’accès à la valeur de n peut se faire par deux méthodes différentes : soit par n=5; , soit par *p1=5; puisque p1 pointe vers n . Ainsi, nous avons :
| int n=147; int * p1= &n; // récupération de l'adresse de n *p1 = 5; std::cout << "n vaut maintenant : " << n << std::endl; // c'est bien la valeur 5 qui s'affiche ! |
2
4
Remarque. Il est clair que, pour toute variable x , la commande *&x donne la valeur de x : on récupère l’adresse puis on lit la valeur pointée par l’adresse. En revanche, &*p sur un pointeur p n’a pas de sens! L’étoile permet de récupérer la valeur pointée par p mais une valeur n’a pas d’adresse puisqu’elle peut être écrite n’importe où. Il suffit pour cela de se convaincreque int *p = &3; n’a pas de sens puisque 3 est une valeur, n’a pas d’endroit réservé dans la mémoire et peut être écrit dans toute variable entière.
Comme les références, les pointeurs peuvent être utilisés pour modifier des valeurs de variables en donnant leurs adresses en argument à des fonctions ou pour éviter d’avoir à recopier leurs valeurs dans la mémoire. Là encore, pour ce dernier usage, le mot-clef const permet d’indiquer que la fonction ne modifie pas les valeurs derrière les adresses. C’est donc une alternative aux références de ce point de vue. Par exemple, pour échanger les valeurs de deux variables de type TYPE , on peut écrire la fonction echange suivante :
| void echange( TYPE * p, TYPE * q) { TYPE a= *p; *p = *q; *q = a; return; } |
2
4
6
Il faut faire attention au placement du const dans une déclaration de pointeur. L’écriture constint * p; désigne un pointeur vers un entier dont la valeur ne peut changer mais la
Erreur de segmentation.
À chaque déclaration de variable, c’est le système d’exploitation de l’ordinateur qui attribue les adresses des variables. Il ne faut donc jamais fixer explicitement soi-même la valeur d’un pointeur : avec une probabilité très proche de 1, cette adresse ne correspond pas à une variable déclarée. Ce problème est indétectable à la compilation; le programme s’arrête brutalement à la compilation dès qu’on tente d’accéder à une adresse inexistante et affiche simplement Erreur de segmentation (ou Segmentation fault en anglais).
C’est pourquoi l’opérateur & est inévitable : il est le seul moyen de récupérer l’adresse d’une variable préexistante.
Supposons que nous ayons préalablement défini une structure (resp. classe) S avec des champs champ1 , champ2 , etc. Un pointeur p vers un objet de type struct S (resp. S ) est donc défini par struct S * p (resp. S * p; ). Pour accéder aux champs champ1 ,
champ2 (resp. aux champs ou aux méthodes) de l’objet pointé, il faut a priori écrire :
| (*p).champ1 (*p).champ2 |
2
Les parenthèses sont inévitables et l’écriture peut être parfois lourde. Pour éviter cela, il existe une syntaxe complètement équivalente et plus légère utilisant -> . Les deux lignes précédentes se réécrivent alors :
| p->champ1 p->champ2 |
2
Cette syntaxe marchera également pour l’appel de méthodes de classe définies au chapitre
5.
Nous avons introduit brièvement en section 3.1.5 la notion de référence. Nous avons à présent toutes les notions sur la mémoire pour définir plus rigoureusement la notion de
référence en C++. Cette notion est absente dans le langage C.
Une référence r est un genre particulier de pointeur avec les propriétés suivantes :
2. on ne peut pas récupérer son adresse ( &r renvoie l’adresse de l’objet pointé et non l’adresse de la référence r ),
3. il se déréférence automatiquement (pas besoin d’utiliser * pour accéder à l’objet pointé).
Le type d’une référence est T & où T est un type déjà défini.
Selon le premier point mentionné ci-dessus, une tentative de réaffectation r=a; ne redéfinit pas r comme une référence vers a mais remplace directement le contenu pointé par r par la valeur de a (pour un pointeur p , cela correspondrait à *p=a; ).
Comme tout pointeur, une référence peut être ou non affublée d’un const . Dans un prototype de fonction, l’usage d’une référence peut ainsi se substituer à celle d’un pointeur dans un argument de fonction pour éviter que l’objet pointé ne soit recopié dans la mémoire. L’usage d’une référence rend même le code de la fonction beaucoup plus lisible car cela permet de supprimer tous les * , & et -> nécessaires lors de la manipulation de valeurs désignées par des pointeurs.
7.2 Gestion dynamique de la mémoire
Se déplacer dans la mémoire.
Comme nous l’avons écrit, un pointeur est une adresse mémoire, i.e. un numéro d’octet dans la mémoire, transcrit usuellement en base hexadécimale. Il y a tout d’abord la valeur nulle, donnée par le mot-clef NULL qui pointe vers un soi-disant 0-ème octet de la mémoire qui n’existe donc pas! Tout accès par * à un pointeur de valeur NULL donne une erreur de segmentation.
Considérons l’exemple suivant :
| short int *p=NULL; int *q=NULL; long double *r=NULL; cout << p << " " << q << " " << r << endl; //cela affiche: 0 0 0 p++; q++; r++; cout << p << " " << q << " " << r << endl; //cela affiche: 0x2 0x4 0x10 cout << q+512 ; //cela affiche: 0x804 |
2
4
6
8
10
Essayons de comprendre l’affichage. Comme vu précédemment, le préfixe 0x indique qu’il faut la valeur qui suit en hexadécimal. Un entier de type short int est codé sur deux octets : décaler p de 1 consiste donc à passer du zéro-ème octet au deuxième. Un
long double est codé sur 16 octets, or 16 s’écrit 10 en base 16 : incrémenter r par r
décale l’adresse de 16 octets. Après la ligne 7, q vaut 4. On ajoute alors 512 fois la taille en octets d’un int codé sur 4 octets; q vaut alors 2048+4=2052 qui s’écrit 80416 en base 16.
Pour connaître le nombre d’octets en mémoire occupé par une variable d’un type TYPE , il suffit d’appeler la fonction sizeof(TYPE) . C’est ainsi qu’on connaît l’effet de ++ sur un pointeur TYPE * .
Lien avec les tableaux.
L’usage de l’arithmétique des pointeurs nous permet de mieux comprendre la structure des tableaux. Un tableau double t[50] correspond dans la mémoire à 50 double stockés consécutivement. Techniquement, il suffit donc de connaître l’adresse de la première case et la taille d’une case; la taille sert pour le créer en allouant la bonne quantité de mémoire et pour éviter ensuite les erreurs de segmentation.
Ce mécanisme de gestion des tableaux explique également pourquoi on obtient une erreur de segmentation si l’on écrit t[i] avec un entier i qui n’est pas dans l’ensemble {0,1,2, ,49} puisqu’une telle case n’est pas attribuée au programme dans la mémoire.
Jusqu’à maintenant, nous avons expliqué comment les types simples, les tableaux statiques et les modèles de classe de la STL sont codés en mémoire mais nous n’avons pas géré la mémoire nous-même : cela a été fait automatiquement par le programme et le système d’exploitation lors de la déclaration de la variable. Cela a un inconvénient majeur : il a fallu attribuer un nom à chaque emplacement lors de l’écriture du programme et réserver des plages de mémoire de taille immuable pour les tableaux statiques. En pratique, cela n’est en général pas suffisant car les besoins évoluent selon l’utilisateur et la taille des données à traiter.
Les pointeurs permettent de réserver et de libérer de la mémoire de manière très flexible avec les mots-clefs respectifs new et delete .
Soit p un pointeur de type TYPE * . La commande p=new TYPE; demande au système d’exploitation de réserver en mémoire un emplacement de la taille nécessaire pour stocker un objet de type TYPE , récupère l’adresse de cet emplacement et la stocke dans la variable
p . La valeur stockée à cet emplacement est alors accessible uniquement par *p .
La commande delete p; ordonne au système d’exploitation de libérer l’emplacement réservé précédemment. La variable p existe toujours bien évidemment mais ne pointe plus vers une zone accessible (la commande *p donne alors un résultat indéterminé et le plus souvent une erreur de segmentation).
Il faut faire attention à ne pas mélanger les versions simple et étendue. Si un emplacement étendue est réservé avec new [] , il faut impérativement le libérer avec delete [] sinon
7.2. GESTION DYNAMIQUE DE LA MÉMOIRE
0 0 0 1 1 1 1 1
0 1 0 0 1 0 0 0
0 0 0 1 0 1 0 1
0 0 1 1 1 1 1
1 0 0 1 0 1 1
0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1
0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1
1 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1
0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0
1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1
Figure 7.2 – Structure en mémoire d’un tableau dynamique déclaré par short int *t = newshort int [2]; . Le pointeur t a pour valeur l’adresse 0xB
(11 en hexadécimal, 1011 en base 2) de l’espace mémoire alloué à travers la commande new
(ici délimité par des pointillés). L’adresse de t est en revanche 0x2 puisque la valeur de t est stockée sur le deuxième octet. L’espace alloué occupe 4 octets, i.e. deux fois la taille
d’un short int .
le comportement du programme est indéfini.
Jusqu’ici, il peut sembler que rien ne distingue en apparence l’usage de new / delete sur des pointeurs de la déclaration d’une variable. Il existe une différence majeure néanmoins qui réside dans la possibilité de réutiliser un pointeur pour un usage différent dans un même programme alors qu’une déclaration de variable fige la nature de cette dernière. Prenons l’exemple du programme suivant :
| int main() { double * p; // Premiere utilisation p=newdouble; *p=3.34; std::cout << *p << std::endl; delete p; //Seconde utilisation p=newdouble[57]; for( int i=0; i<57; i++) delete [] p; return 0; } | p[i]=0.5*i*i; |
2
4
6
8
10
12
14
Avec un seul pointeur et un usage astucieux de new et delete , nous avons pu manipuler la mémoire de manière très différente en utilisant une unique variable p tout au long du programme.
C’est cette liberté liée aux pointeurs qui est utilisée dans le modèle de classe vector
(les changements de capacité se font à travers des usages de new et delete ) ainsi que dans les exemples de la section 7.4. Les constructeurs et destructeurs du chapitre 5 seront également basés sur cette gestion de la mémoire par pointeur.
Valeur en cas d’échec. Les mots-clefs new et delete se révèlent également utiles lorsque d’énormes volumes de données sont en jeu. En effet, si la mémoire vive (RAM) de l’ordinateur est déjà très remplie ou tout simplement insuffisante, il se peut qu’une instruction du type T * p=new T[N]; échoue si un objet de type T occupe beaucoup de place et que N est trop grand. Dans ce cas-là, l’espace mémoire nécessaire n’est pas réservé et, au prochain appel de type p[i] , une erreur de segmentation viendra interrompre subitement le programme. Ce n’est pas trop grave pour un programme de petite ampleur sur un ordinateur personnel; c’est très grave pour un programme qui aurait tourné plusieurs semaines ou qui gère des activités critiques (cf. la ligne 14 du métro par exemple!). Il est alors absolument nécessaire de se prémunir de ce type d’erreur.
Pour cela, il existe la convention suivante : si l’allocation de mémoire échoue, alors new renvoie un pointeur de valeur NULL . Après une instruction du type T * p=new T[N]; , il suffit de tester si p !=NULL pour décider de la continuation du programme si le résultat est true ) ou d’une procédure d’arrêt (sauvegarde des données importantes, solutions alternatives, etc) si le résultat est false .
En général, une bonne partie de la gestion de la mémoire est effectuée au niveau des constructeurs : c’est lors de la déclaration d’objets qu’on réserve la mémoire nécessaire. Pour une gestion dynamique de la mémoire, si certains champs sont des pointeurs, les constructeurs contiennent toujours des new pour allouer la mémoire et stocker l’adresse dans les champs pointeurs.
En particulier, il faut ajouter un constructeur par copie. En effet, sans lui, seul l’adresse du pointeur serait copiée et deux objets de la classe pointeraient en interne vers un même tableau : l’effacement de l’un d’entre eux rendrait alors l’autre inutilisable. Ce comportement est parfois souhaitable mais c’est rarement le cas : on souhaite alors créer un nouveau tableau dans le deuxième objet et y copier les valeurs des cases du premier.
Lorsqu’un objet d’une classe est supprimé de la mémoire, les destructeurs correspondants aux types des champs sont appliqués sur chaque champ mais rien n’est prévu pour de la mémoire allouée par new . Le code du destructeur doit donc contenir un delete (ou delete [] pour chaque pointeur soumis à un new dans un constructeur.
Remarque. Il arrive parfois qu’on souhaite ajouter constructeur par copie et destructeur même lorsque la mémoire est gérée automatique par une autre bibliothèque. Cela arrive
7.3. GESTION DE LA MÉMOIRE DANS LES CLASSES
| classMatrice { private: unsigned int n; double * coeffs; public: Matrice(unsigned N=1, double x=0.); // constructeur 1 Matrice(std::vector<double> v); // constructeur 2 Matrice(const Matrice &); //nécessaire ~Matrice() { delete [] coeffs;} // nécessaire // les méthodes: double & operator() (unsigned int,unsigned int); double taille() const { return n;} double trace() const; friend Matrice operator+(const Matrice &, const Matrice &); friend Matrice operator*(const Matrice &, const Matrice &); friend std::ostream & operator<<(std::ostream &,const Matrice &); }; |
2
4
6
8
10
12
14
16
18
Figure 7.3 – Définition de la classe Matrice avec les champs privés et l’ensemble des méthodes disponibles. Les méthodes marquées d’une étoile sont inutiles ici car la mémoire est directement gérée par la classe std::vector : elles deviendraient nécessaire avec l’usage de pointeurs tels que définis dans le chapitre 7.
en présence de variables globables de classes ou de programme qu’on souhaite modifier à chaque création ou destruction d’un objet de la classe. Nous ne nous en préoccuperons pas dans ce cours.
Un exemple avec des matrices. Reprenons l’exemple des figures 5.1 et 5.2. Le nouveau code est à présent décrit dans les figures 7.3.
Le constructeur par défaut est bien présent ligne 6 et construit une matrice nulle de taille 1. Son code est donné par :
| Matrice::Matrice(unsigned N, double x): n(N), coeffs(nullptr) { //Allocation puis initialisation coeffs= newdouble[N*N]; for(unsignedint i=0; i<N*N; i++) coeffs[i]=x; } |
2
4
Il contient un new qui alloue la mémoire suffisante pour n2. Les autres constructeurs doivent donc en faire de même et le destructeur doit effacer cette mémoire. Son code est donc donné ligne 9 de la figure 7.3.
Le constructeur par copie doit dupliquer tout le contenu d’une matrice préexistante dans l’espace alloué pour une nouvelle matrice. Son code est donc donné par :
| Matrice::Matrice(const Matrice & A) { // bien entendu, le this-> est ici optionnel. this->n=A.n; this->coeffs=newdouble[n*n]; //allocation de la mémoirefor(unsignedint i=0; i<n*n;i++) this->coeffs[i]=A.coeffs[i]; //on copie toutes les données contenues dans A } |
2
4
6
Il semble évidemment stupide d’écrire a=a; mais cet usage est parfois caché dans des situations difficiles à examiner. Prenons l’exemple suivant :
| A a; A & r=a; //beaucoup de lignes de code r=a; |
2
4
Quand on lit la dernière ligne, on a l’impression que r et a sont des objets différents alors que r est construit comme référence à a . Il aurait fallu lire l’intégralité du code pour se rendre compte de la collision, ce qui souvent fastidieux en pratique.
Une solution à ce problème consiste à systématiquement tester si les objets à gauche et à droit du signe = désignent ou non les mêmes données en mémoire. Le code du l’opérateur = sera donc toujours du style :
| A & } | A::operator=(const A & c) { if( this == &c) return *this; // NE JAMAIS L'OUBLIER // effaçage de this avec un code similaire au destructeur /* initialisation des champs de this avec un code similaire au constructeur par copie */return *this; |
2
4
6
Le type renvoyé par = permet des instructions du style a1=a2=a3=c; où un objet c est copié dans toutes les variables a1 , a2 et a3 .
Exemple. Dans l’exemple des figures 5.1 et 5.2, le code de l’opérateur d’affectation est tout simplement
| Matrice & Matrice::operator=(const Matrice & B) { if( this == &B) return *this; // NE JAMAIS L'OUBLIERif( B.n != n) { delete [] coeffs; n=B.n; coeffs=newdouble[n*n]; } for(unsignedint i=0; i<n*n ; i++) coeffs[i]=B.coeffs[i]; return *this; } |
2
4
6
8
10
Reprenons le vocabulaire de la section 1.4. Considérons une suite de N objets avec N grand. En choisissant un tableau, accéder à un élément quelconque prend toujours le même nombre fini d’opérations par *(t+i) : la complexité de l’accès est donc O(1). Insérer ou supprimer un élément demande de bouger en moyenne la moitié du tableau : la complexité est donc en O(N). Cela signifie que le doublement de la taille du tableau ne modifie pas le temps d’accès mais multiplie en moyenne par deux le temps d’insertion/suppression d’un élément.
Une première remarque fondamentale est qu’il n’est pas possible de trouver une structure dans laquelle les deux opérations (accès et insertion) soient rapides. Une deuxième remarque est qu’en revanche il existe deux structures aux efficacités inverses : les tableaux et les listes. Le choix entre les deux lors de la programmation demande d’estimer si ce sont les accès ou les insertions/suppressions qui seront les plus utilisés.
Une liste est une suite d’éléments qui ne sont pas nécessairement contigus en mémoire mais dans laquelle chaque élément contient les adresses du précédent et du suivant. Il suffit d’alors de connaître l’adresse du premier pour pouvoir accéder à tous les autres « en suivant les liens ».
C’est une alternative à l’usage de std::vector() : beaucoup de fonctions sont identiques mais ont une complexité différente, il y a également certaines fonctions supplémentaires et d’autres sont manquantes. Le choix réside essentiellement sur une réflexion sur la complexité des algorithmes que l’on souhaite implémenter.
Chaque élément d’une liste d’objets de type TYPE est appelé maillon et peut être décrit par :
| typedef struct maillon{ TYPE valeur; struct maillon * precedent; struct maillon * suivant; } Maillon; |
2
4
Le champ precedent (resp. suivant ) contient l’adresse du maillon précédent (resp. suivant) dans la liste. Pour le premier (resp. dernier) maillon, la valeur de precedent (resp. suivant ) est fixée par convention à NULL . Une liste est alors une structure :
| typedef struct { unsigned int taille; Maillon * premier; Maillon * dernier; } Liste; |
2
4
qui indique les premiers et derniers maillons, et seulement ces deux.
Imaginons qu’on veuille ajouter une valeur x de type TYPE dans une liste L dans un nouveau maillon juste avant un maillon d’adresse a . La fonction ajout peut par exemple s’écrire :
| bool ajout(Liste & L, Maillon * a, TYPE x) { struct Maillon * p=new Maillon; if( p== NULL) return false; //echec de la creation: rien ne change. p->valeur=x; L.taille++;//ne pas oublier de tout mettre à jour ! // Cas où le maillon est le premier de la listeif( L.premier == a ) { p->precedent=NULL; p->suivant= L.premier; L.premier = p; a->precedent=p; return true; } // Cas où le maillon est le dernier de la listeif( L.dernier == a) { |
2
4
6
8
10
12
14
16
| a->suivant=p; p->precedent=a; p->suivant=NULL; L.dernier=p; return true; } // Autres cas p->suivant=a; p->precedent=a->precedent; a->precedent->suivant=p; a->precedent=p; return true; } |
18
20
22
24
26
28
30
Ce code montre ainsi que l’ajout d’un élément ne nécessite de ne bouger aucun autre élément et que le nombre d’opérations ne dépend pas de la taille de la liste. La complexité d’un ajout est donc en O(1) en la longueur de la liste.
| Maillon * acces(const struct Liste & L, unsigned int i) { if( i >= L.taille) return NULL; // element inexistant Maillon * p=L.premier; while( i>0) { p=p->suivant; i--; } return p; } |
2
4
6
8
Cette fois-ci, la boucle while parcourt la liste jusqu’au bon endroit. La complexité moyenne est donc en O(N).
Nous avons ainsi atteint notre but en construisant une structure qui permet l’accès en O(N) et l’insertion en O(1). On vérifie également qu’il est facile d’ajouter et supprimer des éléments en début ou fin de liste puisque les adresses du premier et du dernier élément sont écrites dans la structure de liste.
Le concept d’itérateur. Il existe des opérations qui prennent autant de temps dans un tableau que dans une liste et pour lesquelles les algorithmes se retrouvent être les mêmes, par exemple, calculer la somme des éléments d’une liste ou d’un tableau d’objets de type double . Écrivons les trois codes aussi efficaces les uns que les autres pour les trois structures étudiées jusque là :
| double somme( const Liste & L) { double s=0.; Maillon * p= L.premier; |
2
| } | while( p != NULL) { s += (*p).valeur; p = p-> suivant; } return s; |
4
6
8
| double somme(constdouble * t, unsigned int taille) { double s=0.; unsigned k=0; while( k < taille) { s += t[k]; k++; } return s; } |
2
4
6
8
| double somme(constdouble * t, unsigned int taille) { double s=0.; double * p= t; while( p != t+taille) { s += *p ; p++; } return s; } |
2
4
6
8
— ligne 3 : initialisation sur le premier élément
— ligne 4 : détection de la sortie de la structure
— ligne 5 : accès à la valeur
— ligne 6 passage à l’élément suivant
Cette similarité n’est pas un hasard et est à la base de la notion d’itérateur.
Un itérateur joue le rôle d’un pointeur vers un élément d’une structure et doit être pourvu des opérations suivantes :
— accès à la valeur par l’opérateur *
— passage à l’élément suivant par ++ ;
— récupération à partir d’une liste d’un itérateur vers le premier élément et d’une condition de sortie de la structure.
Le modèle de classe std::list de la STL. La STL contient déjà des listes doublement chaînées avec des fonctionnalités bien plus nombreuses que notre tentative précédente et nous vous encourageons à utiliser directement cette nouvelle solution. En utilisant
l’en-tête
#include<list>
on a accès au modèle de classe std::list<TYPE> pour gérer une liste d’objets de type
TYPE et d’itérateurs std::list<TYPE>::iterator vers des éléments de liste. Les opérations naturelles sur ces objets sont résumées dans le tableau de la figure 7.4 pour des objets déclaré par std::list<TYPE> L; , std::list<TYPE>::iterator i; et TYPE x; . Les
fonctionnalités sont similaires aux fonctions précédentes.
Ainsi, si nous souhaitons construire une liste avec les carrés des 100 premiers nombres entiers puis afficher cette liste dans l’ordre inverse, nous pouvons écrire :
| #include<list>#include<iostream>using namespace std; int main() { list<int> L; for(int i=0 ; i<100; i++) L.push_front(i*i); list<int>::iterator it; for( it=L.begin(); it != L.end() ; it++) cout << *it << endl; return 0; } |
2
4
6
8
10
Listes simplement chaînées et piles. Reprenons notre définition de Maillon dans la section précédente. Il est possible de supprimer le champ precedent dans Maillon : cela permet de gagner de la place en mémoire (un pointeur par maillon) mais il n’est alors plus possible d’utiliser -- sur un itérateur et tout retour sur un maillon précédent demande de recommencer à partir du premier. Le gain de place en mémoire ou en temps a un prix à payer en termes de fonctionnalités. La STL fournit la plupart de ces structures allégées sous les noms de stack (pile), queue , etc.
Toutes ces structures ainsi que les tableaux gardent en commun le fait que les éléments sont ordonnés du premier au dernier. Cet ordre est souvent pertinent (par exemple, quand il s’agit de coordonnées de vecteurs ou d’ordre d’arrivée d’objets) mais il ne l’est pas toujours. L’exemple des listes sera traité en détail en cours.
Structures non ordonnées : ensembles, « skip-lists » et « arbres B ». Lorsque l’on préfère utiliser des ensembles plutôt que des n-uplets, i.e. lorsque l’ordre des éléments n’importent pas dans le problème considéré, il existe d’autres structures plus efficaces. Des
| Méthodes | Effet | Complexité |
| L.push_front(x); | ajoute un élément en tête de liste | O(1) |
| L.push_back(x); | ajoute un élément en fin de liste | O(1) |
| L.pop_front(); | enlève un élément en tête de liste | O(1) |
| L.pop_back(); | enlève un élément en fin de liste | O(1) |
| it=L.begin(); | renvoie un itérateur vers le premier élément | O(1) |
| (); | renvoie un itérateur vers l’élément fantôme après le dernier | O(1) |
| ++it / --it | déplace l’itérateur vers l’élément suivant/précédent | O(1) |
| x=*it; | renvoie la valeur pointée par l’itérateur | O(1) |
| L.insert(it,x); | O(1) | |
| Pas d’accès direct au i-ème élément | virtuellement O(N) |
Figure 7.4 – Méthodes du modèle de classe std::list<TYPE> décrites par un exemple et leurs effets. La complexité est également précisée. La variable x est de type TYPE . La variable it désigne ici un itérateur de type std::list<TYPE>::iterator .
exemples de telles situations sont des collections de fichiers, des ensembles de cas à traiter, des familles de points sur lesquelles on souhaite faire des statistiques, etc.
Dans ce cas, il est utile d’introduire un ordre, naturel ou non, partiel ou total, sur les objets. Pour les entiers ou les réels on peut se baser sur l’ordre naturel; pour les chaînes de caractères on peut se baser sur l’ordre lexicographique. Ce qui est important, c’est de pouvoir comparer rapidement les objets (quelle que soit leur taille). On trouve alors un objet, que ce soit pour y accéder, pour le supprimer ou insérer un objet avant ou après lui, rapidement par dichotomie avec une complexité moyenne en général de l’ordre de O(logN) où N est la taille de la collection d’objets.
L’exemple des « skip-lists » sera traité en détail dans le cadre d’un TP.
Les différents conteneurs ordonnés de la STL comme std::list , std::vector , std::array , std::stack , etc possèdent tous des itérateurs qui sont présents sous deux
types différents :
| std::CONTENEUR<TYPE>::iterator It; std::CONTENEUR<TYPE>::const_iterator Itc; |
2
Dans tous les cas, ces deux types d’itérateurs se comportent comme des pointeurs TYPE * ou const TYPE * vers les contenus des cases des structures. En particulier, ils sont tous munis d’un opérateur ++It qui permet de passer à une case suivante; certains d’entre eux sont aussi munis de -- qui permet de remonter dans la structure. Ils sont tous également
De plus, chaque conteneur possède des méthodes begin() et end() : la première renvoie un itérateur sur le premier élément et la seconde renvoie un itérateur sur un élément « après le dernier ». Ce dernier permet de détecter l’arrivée à la fin d’une structure après usage de ++ .
La plupart des exemples de ce cours ainsi que les exemples vus en TP ont traité d’objets de type std::vector pour lesquels on accède aux case par les crochets [] .
Malheureusement, c’est impossible pour la plupart des autres conteneurs et le seul moyen de parcourir ces conteneurs dans l’ordre est de manipuler des itérateurs.
7.5 [Hors programme] Une rapide revue des pointeurs intelligents en C++11
Tout ce qui est décrit dans cette section a été introduit dans le standard C++11 :
il faut donc compiler les programmes avec l’option -std=c++11 .
Le standard C++11 offre de nouvelles possibilités de gestion de la mémoire pour éviter de nombreux pièges vus précédemment dans les cas les plus simples. Cela repose sur la notion de « pointeurs intelligents » (smart pointers en anglais). Les utiliser requiert l’inclusion suivante en en-tête :
#include<memory>
Il en existe de plusieurs types et choisir le bon demande une réflexion supplémentaire sur les programmes que l’on écrit.
Documentation. De nombreuses informations sont récapitulées dans les réferences suivantes :
et
Les pointeurs à usage unique. C’est le premier type de pointeur intelligent qui permet de définir des pointeurs dont on veut restreindre l’accès au contenu au seul environnement qui a créé le pointeur (typiquement une classe).
L’intéret est alors qu’il n’est plus nécessaire d’écrire les delete correspondants : le pointeur et son contenu pointé sont détruits lorsque l’environnement qui les a créé est lui-même détruit.
| std::unique_ptr<TYPE> p; // construit le pointeur nul std::unique_ptr<TYPE> p(new TYPE); // alloue la mémoire // pour un objet de type TYPE par défaut et écrit l'adresse // dans un pointeur unique pour la protéger. |
2
4
Ensuite, cela s’utilise comme d’habitude avec les syntaxes *p et p-> pour accéder au contenu pointé. En revanche, il n’y a plus de delete à écrire et tout le contenu pointé est détruit lorsque p arrive en fin de vie.
Un exemple typique d’utilisation est la classe Matrice revue dans ce chapitre en figure 7.3 : le pointeur coeff ne doit être utiliser que par la matrice qui le possède car toute copie de matrice passe la création d’un autre tableau pointé et la copie du contenu. Remplacer la ligne 4 par :
aurait les conséquences suivantes :
— le destructeur devient inutile (plus d’erreur d’étourderie!)
— les constructeurs 1 et 2 doivent utiliser la syntaxe de construction de std::unique_ptr précédente (presque rien )
— l’oubli du constructeur par copie donne une erreur de compilation car le champ coeff n’est plus copiable et cela oblige ainsi à se poser la question de la copie (plus d’étourderie possible!)
— l’oubli de la redéfinition de = donne une erreur de compilation pour la même raison et oblige à se poser la question de la copie.
Les pointeurs partagés. Il est des cas où l’on souhaite l’inverse : avoir un pointeur vers un objet unique partagé par plusieurs objets. Imaginons par exemple le cas d’un grand tableau, d’une grande image, d’un long texte auxquels se référeraient plusieurs objets. Dans ce cas, on veut pouvoir copier l’adresse de ce gros objet et que ce dernier ne soit effacé qu’après que le dernier objet qui l’utilise disparaisse. Dans ce cas-là, la bonne notion est celle de pointeur partagé.
La déclaration d’un tel pointeur se fait par :
auto sp2= std::make_shared<TYPE>(arg1, ,argn);// où arg1, ,argn // sont les arguments du constructeur souhaité de TYPE.
2
4
qui fonctionne comme précédemment. La structure interne d’un tel objet est constituée d’un pointeur nu TYPE * ainsi que d’un compteur qui mémorise le nombre de fois que ce pointeur est copié dans la mémoire. Il s’utilise ensuite comme un pointeur normal avec *sp et sp-> . Là encore, il n’y a plus de delete à écrire : la mémoire est automatiquement libérée lorsque la variable sp est effacée et que plus aucun objet n’utilise le pointeur (d’où le compteur interne associé ).
Nous n’entrerons pas dans les détails mais, associé à ce type, il existe la notion de std::weak_ptr<TYPE> qui permettent, sans rien allouer ni effacer, de pointer vers l’élément de mémoire pointé par un std::shared_ptr<T> (en incrémentant d’une unité le compteur de ce dernier).
7.5. [HORS PROGRAMME] UNE RAPIDE REVUE DES POINTEURS INTELLIGENTS EN C++11139
Exercice 7.1. (navigation par pointeur) Soit le programme
| #include<iostream>int main() { double * t = newdouble[20]; for(double * p=t+4; p<t+16; p++) { *p = 1.23456; } _____ delete [] t; } |
2
4
6
8
Que fait-le programme suivant? Compléter le programme pour afficher toutes les cases du tableau pour vérifier votre intuition.
Exercice 7.2. Si vous ne faites pas ce qu’il faut à la fin de la fonction f() , ce code va paralyser votre machine ou bien planter après peu de temps. Soyez vigilants!
| #include<iostream> #include<string>#include<complex>double f() { double *t= newdouble[10000000]; double u=t[0]; // agissez maintenant !return u; } int main() { double x; for (longlong int i = 0; i < 10000000; i++) x=f(); return 0; } |
2
4
6
8
10
12
14
| #include<iostream>int main() { int t[6]= {0,5,4,2,1,3}; int *p = t+5; p -= 1; p = t+ *p; p = p+1; std::cout << *p << std::endl; |
2
4
6
8
| return 0; } |
10
Ces notes de cours ne constituent qu’une introduction à la programmation en C++ pour les mathématiciens, avec une orientation vers l’aléatoire et les structures de données.
Il est temps maintenant de faire un rapide panorama de tout ce que ce cours ne contient pas :
— la gestion des exceptions : lorsqu’un new échoue, qu’une division par zéro s’effectue, qu’un fichier devant être présent ne l’est pas, etc, il ne sert en général à rien de poursuivre l’exécution d’un programme et il vaut mieux prévenir l’utilisateur de la raison de l’arrêt soudain du programme. Pour cela, il faudrait en toute rigueur ajouter des tests pour vérifier qu’aucun de ces scénarii ne se produit et, s’il s’en produit un, prévoir une sortie rapide du programme : c’est tout l’objet du traitement des exceptions, que nous n’avons pas du tout abordé.
— la définition des espaces de noms : nous avons vu fréquemment apparaître des espaces de noms tels std:: et Eigen:: pour préciser l’appartenance de certaines classes et fonctions à des familles plus grandes. Nous avons montré comment définir des classes et, pour être complet, il faudrait également expliquer comment définir de nouveaux espaces de noms.
En revanche, le nouveau standard C++20 va être une révolution au moins aussi grande que celle qu’a été le standard C++11 à sa sortie. Peut-être ce cours en parlera-t-il dans quelques années!
— nous avons insisté à plusieurs reprises sur l’erreur d’arrondi lié aux types de flottants et sur le dépassement de capacité des entiers, ainsi que sur la qualité approximative des générateurs de nombres aléatoires : néanmoins nous n’avons pas proposé de méthodes de contrôle et d’estimation de ces erreurs par manque de temps. Nous vous conseillons de vous référer à un cours d’analyse numérique ou de probabilités numériques pour aborder ce sujet.
— à travers les exemples vus en séances de cours et de TP, nous avons présenté quelques structures algorithmiques parmi les plus fréquentes. Il en existe beaucoup d’autres et nous vous conseillons de développer votre culture générale en vous référant à des livres d’introduction à l’algorithmique.
— au-delà de l’aspect mathématique, l’aspect « programmation orientée objet » du C++ permet aussi de développer aisément des interfaces graphiques (par exemple avec les outils de développement Qt). Les problématiques sont alors complètement différentes : en général on sacrifie l’efficacité numérique (la vitesse est le plus souvent limitée par les utilisateurs) au profit de la facilité de création de nouveaux outils à intégrer aux interfaces ainsi et au profit de la capacité d’évolution de ces dernières.
Nous vous souhaitons une bonne continuation dans la découverte du C++ et de la programmation en général.
Nous avons vu en section 2.4 que les commandes de compilation avec g++ peuvent être longues et nombreuses dès lors que des bibliothèques externes sont utilisées ou que le programme est découpé en de nombreux fichiers .cpp . Lors de la correction des erreurs dans un programme, il peut être fastidieux de relancer manuellement toutes ces commandes de compilation : tout ce processus peut être automatisé grâce à l’usage du programme make et la création d’un fichier Makefile . De plus, l’usage de make permet de varier les paramètres de compilation (changement de compilateur ou d’options de compilation) ainsi de nettoyer les fichiers intermédiaires produits par les compilations partielles.
La marche à suivre est de créer un fichier dont le nom est nécessairement Makefile dans le répertoire de travail. Ce fichier est structuré de la manière suivante :
| CC= g++ CFLAGS= -Wall -pedantic -O3 : fichier1.o fichier2.o principal.o $(CC) -o fichier1.o fichier2.o principal.o fichier1.o: $(CC) -c $(CFLAGS) fichier2.o: $(CC) -c $(CFLAGS) -I/usr/include/eigen3 principal.o: $(CC) -c $(CFLAGS) clean: rm *.o |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Les trois premières lignes définissent trois variables qui contiennent respectivement le nom du compilateur, les options de compilations, les liens vers les librairies pour l’assemblage des fichiers. L’accès à la valeur d’une variable V se fait ensuite par l’opérateur $(V). Une variable peut être laissée vide comme cela a été fait dans la ligne 3 ci-dessus.
APPENDICE : MAKEFILE
Toutes les commandes suivantes doivent suivre la syntaxe suivante :
La cible est par exemple le nom d’un fichier à bâtir. Les dépendances sont tous les fichiers dont dépend l’obtention de la cible. Par exemple, si c’est un fichier .o, toute modification dans les .cpp et .hpp correspondant ainsi que dans les tous les autres .hpp qui apparaissent dans leurs #include" " induit une modification du .o correspondant. Les lignes suivantes doivent nécessairement commencer par une tabulation (la touche à gauche de la première rangée de lettres sur la majorité des claviers) puis contiennent la ligne de commandes nécessaires à l’exécution de la cible.
Une fois le Makefile constitué, on utilise dans le terminal le logiciel de la manière suivante :
— make cible fait le nécessaire pour atteindre la cible en calculant toutes les dépendances à satisfaire
— make fait le nécessaire pour atteindre la première cible.
En général, la première cible est le fichier exécutable final que l’on souhaite construire.
Lors d’un nouvel appel à make cible après modification de quelques fichiers, make cherche l’ensemble minimal de cibles à régénérer qui font intervenir les fichiers modifiés. Dans l’exemple ci-dessus, si on modifie seulement le fichier et qu’on appelle à nouveau make, seules les recompilations (dans l’ordre) de fichier2.o puis sont effectuées et fichier1.o et principal.o restent inchangés. Si, au contraire c’est alors toutes les cibles sont à nouveau traitées par make.
Enfin, une cible peut ne pas être un fichier mais un mot quelconque. C’est utile pour nettoyer un répertoire après de multiples compilations : dans l’exemple ci-dessus, l’appel de make clean traite la dernière cible, qui ne dépend d’aucune autre, et efface tous les fichiers .o dont il n’y a plus besoin après construction de l’exécutable final.
[1] B. Stroustrup, Le langage C++ (3ème édition), CampusPress, 1999. (la référence par l’auteur du langage !)
[2] le site avec une description complète de la bibliothèque standard agrémentée d’exemples faciles à comprendre.
[3] le site avec une description complète de la bibliothèque standard et des derniers standards.
[4] site web avec de nombreux exercices d’entraînement.
[5] D. Ryan Stephens, C. Diggins, J. Turkanis, J. Cogswell, C++ Cookbook : Solutions and Examples for C++ Programmers, O’Reilly Media, 2005.
[6] E. Scheinerman,C++ for Mathematicians. An Introduction for Students and Professionals. CRC Press, 2006.
[7] D. Knuth, The art of computer programming, volumes 1 à 4, Addison Wesley, réédité en 2011. (une excellente introduction à l’algorithmique)
[1] . Mais qui donc a compilé le premier compilateur?
[2] . une fois que le compilateur ne comprend pas une ligne, par exemple une parenthèse non fermée, il est possible qu’il perde ses repères et voit ensuite d’autres problèmes qui en fait n’existent plus une fois la première erreur corrigée.
[3] .
[4] . attention, cette ligne peut être fausse : s’il s’agit par exemple d’une parenthèse non fermée dans une ligne antérieure, le compilateur n’est pas capable de localiser ce que vous souhaitiez faire.
. Pour des questions de rétro-copatibilité avec des programmes écrits en langage C, des entiers déclarés non-constants sont tolérés mais sont déconseillés par la norme du langage. On préférera toujours utiliser les conteneurs std::array<TYPE,TAILLE> de la bibliothèque standard <array> .
[6] . Pour les classes que nous définirons au chapitre 5, le destructeur est appelé.
[8] . Pour conserver la propriété de taille fixe et avoir une implémentation équivalente mais compatible avec la STL, il suffit d’utiliser le modèle std::array du standard C++ 11)
. Autrement dit, il peut s’interrompre brutalement ou tout aussi bien continuer en renvoyant une valeur quelconque
[10] . Cette dernière ne peut bien sûr par être appelée sur un vecteur vide.
. Ici, l’accusation est légère car le programme fait 3 lignes avec un std::cout mais il faut imaginer un programme un peu plus long et un peu moins trivial.
. Cette lourdeur de syntaxe, avec des noms de type très longs et malheureusement absolument nécessaires, a souvent été reprochée au C++ dans les versions antérieures à C++11.
[13] . Nul besoin de savoir le nombre exact!
[14] . Pour un std::set , il est équivalent de mettre E.begin() ou E.end() car le conteneur est ordonné.
En revanche, pour insérer dans une liste à partir d’un endroit donné, le deuxième argument est important.
. Ce n’est rigoureusement exact en fait. La vérité est que tous les types ne sont pas permis ( double par exemple est interdit). Les entiers et les noms de type sont en revanche les plus utilisés.
[16] . Il est important de passer du temps à comprendre cette phrase; pour cela n’hésitez pas à faire un schéma de ce qui se passe dans la mémoire.
[17] . Intéressez-vous au message d’erreur que vous obtenez lors de la compilation.
[18] . Le modèle de classe std::vector , derrière lequel se cache un usage astucieux de new [] et delete [] , permettait de s’affranchir partiellement de cette contrainte avec la notion de capacité.
