# Lifap6 — Liste chaînées
Ce TP a pour but de vous rafraîchir la mémoire sur la programmation en `C++` et
la conception de structures de données. Il prépare une séance de TP à venir
sur les Skip-Lists qui sont une évolution des listes chaînées. Votre travail est
donc de réaliser une implémentation des listes chaînées.
## Récupérer le code
Ce TP vous est fourni sous la forme d'un dépôt utilisant un *outil de
versionnement* : git. Les outils de versionnement sont incontournables dans le
monde de la programmation. Ils permettent d'éviter la perte de données, de
suivre l'avancée du travail, de collaborer facilement à plusieurs sur un même
code.
### Forge de l'université
L'université met à votre disposition une [forge](https://forge.univ-lyon1.fr)
sur laquelle vous vous trouvez, via le logiciel [gitlab](https://gitlab.com). La
forge est un outil en ligne pour gérer des dépôts git. Elle vous fournit en plus
la possibilité de consulter le dépôt en ligne, des outils de suivi de bugs, etc.
Sur cet espace, vous avez la possibilité de créer autant de dépôts que vous le
souhaitez, pour vos codes, vos rapports, ou vos projets personnels.
### Duplication du dépôt
Vous pouvez vous contenter de cloner le dépôt, ou de le dupliquer sur la forge
pour avoir votre propre version que vous pourrez faire évoluer et sauvegarder.
Pour dupliquer le projet, utilisez le petit bouton <kbd>Fork</kbd>. Cette action
créera un nouveau dépôt dans votre espace personnel.
Une fois le dépôt dupliqué, le bouton <kbd>Code</kbd> vous donne accès à
différents moyens pour éditer le code. Nous vous conseillons de cloner
localement le dossier via l'url `HTTPS`, mais si vous maîtrisez l'outil libre à
vous de choisir une autre méthode.
Dans votre invite de commande, naviguez là où vous souhaitez travailler, et
utilisez la commande
```bash
git clone <adresse>
```
Un dossier sera créé et vous pouvez commencer à travailler.
### Sauvegarder votre travail
Git est un outil permettant de *versionner* votre travail. À tout moment,
lorsque vous le souhaitez (et de préférence souvent), vous pouvez créer un
instantané de l'état de votre travail. Quoi que vous fassiez par la suite, il
vous sera toujours possible de revenir à cet version. Cet instantané est un
*commit*, et se génère avec la commande du même nom.
Commencez par choisir les fichiers dont vous voulez sauvegarder l'état. Vous
pouvez ajouter un fichier au commit via la commande
```bash
git add <votre fichier>
```
Une fois les fichiers choisis, vous pouvez taper
```bash
git status
```
pour avoir un récapitulatif de ce qui sera sauvegardé au prochain commit. Une
fois tous les fichiers sélectionnés, il vous reste à créer le commit :
```bash
git commit -m "Message du commit"
```
Votre commit est créé, vous pouvez continuer à travailler. Faites en sorte que
le message soit explicite, car il vous permettra d'identifier le commit si vous
avez besoin d'y revenir.
Vos commits sont des sauvegardes *locales*. Les autres personnes ayant accès à
votre dépôt ne peuvent pour l'instant pas les voir. Si votre disque dur crame,
votre travail reste perdu. Pour envoyer vos commits sur la forge, et ainsi les
rendre disponibles aux autres, et les sauvegarder plus solidement, vous pouvez
ensuite réaliser un *push* via :
```bash
git push
```
Cette commande vous demandera éventuellement de répondre à quelques questions la
première fois pour renseigner votre identité, et dans tous les cas vous
demandera vos identifiants universitaires. Une fois votre travail poussé sur la
forge, vous pouvez vérifier sur l'interface que vos fichiers ont bien été mis à
jour.
Si vous ne parvenez pas à pousser, il est fréquent que vous n'ayez pas créé
votre propre dépôt via un fork. Dans ce cas le dépôt distant est le dépôt
général proposant le sujet à tout le monde, et vous n'avez pas le droit de le
modifier.
## Listes chaînées
### Code de base et compilation
Vous trouverez dans le dépôt un dossier `src` avec un code de base. Dans un
premier temps, vous travaillerez sur les fichiers suivants :
* `cellule.hpp/cpp`
* `liste.hpp/cpp`
* `test_liste.cpp`
Les deux premiers sont utilisés pour implémenter la structure de données, et le
troisième fournit un ensemble de tests à activer qui vous permettront de valider
votre travail au fur et à mesure de votre avancée. Un Makefile écrit à la main
vous est proposé pour compiler le code rapidement via la commande `make` lancée
dans le dossier.
### Q1 : structure de base
Une liste chaînée est une structure de données dont le but est de stocker une
séquence de valeurs. La liste est composée d'un ensemble de *cellules*. Chaque
cellule contient une valeur, ainsi que l'adresse de la cellule suivante. Une
liste est généralement représentée par le schéma ci dessous.
L'intérêt de cette structure de données est de pouvoir facilement rajouter des
valeurs en tête de liste.
#### Votre travail
Dans les fichiers `cellule.hpp/cpp` et `liste.hpp/cpp`, complétez les classes
cellule et liste en leur ajoutant des variables membres pour implémenter la
structure de données. Une cellule d'une liste chaînée contient une valeur et
l'adresse de la cellule suivante. Par convention, lorsque la cellule est la
dernière de sa liste, vous utiliserez l'adresse `nullptr` comme adresse de
cellule suivante.
>:warning: Dans ce TP le but est prioritairement d'obtenir un prototype
>fonctionnel et de se concentrer sur les algorithmes. Nous ne vous demandons
>donc pas dans un premier temps de vous focaliser sur des aspects d'organisation
>de code, en particulier via la gestion des champs `public` ou `private` des
>cellules, ou via l'utilisation du mot clé `const` pour restreindre la
>possibilité de modifier des choses. Par défaut, considérez que tout est public
>et modifiable, le debug n'en sera que plus simple. Libre à vous par la suite de
>faire une passe de qualité une fois le code fonctionnel.
##### Cellule
Vous considérerez que la valeur contenue dans la cellule est un entier de type
`int`. Notez également que pour un type `T` donné, l'adresse mémoire d'une
valeur de type `T` est de type `T*`. Vu que nous allons manipuler des adresses
de `Cellule`, ces adresses seront donc de type `Cellule*`.
##### Liste
La classe liste n'est pas forcément nécessaire selon l'implémentation des listes
chaînées. Elle est utile lorsque vous souhaitez conserver des informations
globales sur la liste, comme le nombre d'éléments insérés par exemple. Pour la
suite, il vous sera utile d'avoir une telle classe. La classe liste contiendra
donc pour l'instant l'adresse de la première cellule de la liste. Notez qu'une
liste vide ne contient **aucune** cellule, et l'adresse de la première cellule
d'une liste vide est donc `nullptr`. Complétez le *constructeur par défaut* de
la classe Liste pour vous assurer que toute nouvelle liste respectera cette
convention. Dans le fichier d'entête `liste.hpp` le constructeur par défaut est
déclaré par
```cpp
Liste() ;
```
La définition de cette fonction est à compléter dans le fichier d'implémentation
`liste.cpp` avec le prototype
```cpp
Liste::Liste()
```
Pour rappel le préfixe `Liste::` sert à indiquer que vous définissez une méthode
de la classe `Liste`.
##### Test
Une fois votre implémentation réalisée, vous pouvez éditer le fichier
`test_liste.cpp` pour décommenter la ligne
```cpp
//#define TEST_CONSTRUCTION_VIDE
```
Recompilez ensuite le code et lancez l'exécutable pour lancer le test.
### Q2 : manipulations en tête de liste
Les listes chaînées permettent de réaliser efficacement des manipulations en
tête de liste, car la structure liste gère l'adresse de la cellule en tête de
liste. Il n'est par contre pas immédiat d'accéder aux autres éléments de la
liste car les cellules peuvent être n'importe où, et il est nécessaire de
parcourir les cellules les unes après les autres à partir de la tête pour
accéder à la fin de la liste. Vous allez donc maintenant vous concentrer sur ces
manipulations.
#### Votre travail
Votre but est d'implémenter les méthodes `tete`, `ajouter_en_tete` et
`supprimer_en_tete` de la classe `Liste`, en modifiant le fichier `liste.cpp`
##### Tete
La méthode `tete` renvoie simplement l'adresse de la cellule en tête de liste.
Cette méthode est principalement là pour être indépendant du nom de variable que
vous souhaiterez utiliser pour les variables membres de votre classe.
##### Ajout en tête
Pour ajouter en tête une valeur, il est nécessaire de **créer** une nouvelle
cellule. Pour que la cellule continue à exister lorsque la méthode aura
retourné, il est nécessaire d'allouer cette nouvelle cellule **sur le tas**. Si
vous ne voyez pas ce que sont la pile et le tas, ce sont des notions vues dans
les années précédentes qu'il vous faut rapidement maîtriser. Faites donc appel à
votre chargé de TP pour obtenir de l'aide. Pour fabriquer de nouvelles cellules
sur le tas, il est donc nécessaire de faire appel à `new`.
Une fois la cellule créée, il faut lui donner la bonne valeur, puis la
**chaîner**, c'est à dire ajuster l'adresse de la tête de liste stockée dans la
classe `Liste` et les cellules suivantes de certaines cellules pour s'assurer
que la nouvelle cellule est à sa place et que la liste est bien formée. Ici,
faites vous un dessin au brouillon si ce n'est pas évident.
##### Suppression en tête
Les cellules étant stockées sur le tas, pour éviter les fuites mémoires, il est
nécessaire de faire appel à la fonction `delete` pour libérer la mémoire qui
leur a été allouée. Attention cependant, une fois `delete` appelé, les données
de la cellule supprimée ne sont plus sensées être accessibles. En particulier,
vous perdez l'adresse de la cellule suivante. De même, faites vous un dessin de
l'état de la liste avant et après, et listez les modifications nécessaires si ce
n'est pas évident pour vous.
#### Test
Une fois votre implémentation réalisée, vous pouvez éditer le fichier
`test_liste.cpp` pour décommenter la ligne
```cpp
//#define TEST_AJOUT_SUPPRESSION_EN_TETE
```
Recompilez ensuite le code et lancez l'exécutable pour lancer le test.
### Q3 : taille de la liste
Vous allez maintenant faire en sorte de pouvoir efficacement obtenir la taille
de la liste. Il est actuellement possible de calculer la taille de la liste en
parcourant toute la liste et en comptant les cellules sur le passage. Cette
action est néanmoins linéaire sur la taille de la liste, et donc peu efficace.
Nous vous proposons ici de **stocker** la taille de la liste dans la classe
`Liste`. Il devient néanmoins nécessaire de s'assurer que la taille de la liste
reste cohérente lors des différentes manipulations réalisées sur la liste.
#### Votre travail
Ajoutez une variable membre à la classe `Liste` permettant de stocker la taille
de la liste. Complétez ensuite la méthode `taille` pour renvoyer la valeur de
cette variable membre. Modifiez ensuite les méthodes que vous avez déjà mises en
place pour vous assurer que la taille est correcte à tout instant : lors de la
construction de la liste, des insertions ou des suppressions.
#### Test
Une fois votre implémentation réalisée, vous pouvez éditer le fichier
`test_liste.cpp` pour décommenter la ligne
```cpp
//#define TEST_TAILLE
```
Recompilez ensuite le code et lancez l'exécutable pour lancer le test.
### Q4 : affichage de la liste
Pour visualiser la liste et faciliter le debug, vous allez maintenant
implémenter l'affichage de la liste.
#### Votre travail
Dans le fichier `liste.cpp`, complétez la méthode `afficher` pour qu'elle
permette l'affichage de la liste. Cette méthode va devoir parcourir la liste,
c'est la première méthode de ce TP qui réalise un tel parcours. Parcourir la
liste consiste à partir de la cellule en tête de liste, puis sauter de cellule
en cellule en utilisant les adresse des cellules suivantes, jusqu'à atteindre la
fin de la liste. Plus spécifiquement, pour réaliser ce parcours, vous aurez
besoin d'une notion de **cellule courante**. Si vous dessiniez la liste en cours
de parcours sur votre brouillon, vous auriez envie de dessinez quelque chose
comme ci-dessous :
Les flèches sur ce schéma correspondent à des *pointeurs*, c'est ç dire des
variables contenant des adresses. Les cellules contiennent l'adresse de leur
cellule suivante, et la variable courante est également un pointeur, c'est à
dire qu'elle contient l'adresse de la cellule de l'itération courante. Pour
réaliser le parcours, posez-vous les questions suivantes :
* quelle est la cellule courante au début du parcours ?
* comment évolue la cellule courante lors du parcours à chaque itération ?
* que vaut la cellule courante lorsque le parcours est terminé ?
#### Test
Une fois votre implémentation réalisée, vous pouvez éditer le fichier
`test_liste.cpp` pour décommenter la ligne
```cpp
//#define TEST_AFFICHAGE
```
Recompilez ensuite le code et lancez l'exécutable pour lancer le test.
### Q5 : destruction de la liste
Lorsqu'une liste est détruite, son destructeur est automatiquement appelé. C'est
en particulier vrai lorsque vous créez une liste sur la pile et qu'elle sort de
portée. C'est la raison pour laquelle chaque test dans le fichier
`test_liste.cpp` est encapsulé dans une paire d'accolades `{ }` : ces accolades
définissent une portée, et toute donnée créée sur la pile à l'intérieur de la
portée sera détruite à la sortie de la portée. Pour l'instant, le destructeur ne
fait rien qu'afficher l'adresse de la liste détruite, ce qui pose problème car
les cellules qui constituent la liste sont allouées sur le tas, et si elles ne
sont pas manuellement détruite lors de la destruction de la liste, elle
persisteront, sans pour autant être accessibles : c'est une fuite mémoire.
#### Votre travail
Modifiez le destructeur de la liste pour vous assurer que lorsqu'une liste est
détruite, toutes les cellules qui la constituent le soient également.
#### Test
Il est difficile de vous assurer que votre programme n'a pas de fuite mémoire,
dans la mesure où lorsque votre programme se termine, le système d'exploitation
va de toute façon libérer le segment mémoire alloué au processus, et donc
détruire toute la mémoire occupée restante. Les fuites mémoire sont donc surtout
un problème pour les processus ayant vocation à rester actif longtemps.
Si vous travaillez sous linux, vous pouvez utiliser l'outil `valgrind` pour
détecter les erreurs et fuites mémoire.
### Q6 : manipulations en queue
Nous dépassons désormais le cadre strict de l'implémentation classique d'une
liste chaînée : vu que les manipulations en queue nécessitent de parcourir toute
la liste pour en atteindre la fin, elles sont particulièrement inefficaces sur
une grande liste. Le but de cette partie est d'implémenter tout de même ces
fonctionnalités car elles constituent un bon exercice de parcours d'une liste
chaînée.
#### Votre travail
Implémentez dans vos listes la possibilité d'ajouter ou consulter une valeur en
queue de liste. Prenez soi également de vous assurer que la taille de la liste
reste cohérente.
#### Test
Une fois votre implémentation réalisée, vous pouvez éditer le fichier
`test_liste.cpp` pour décommenter la ligne
```cpp
//#define TEST_AJOUT_EN_QUEUE
```
Recompilez ensuite le code et lancez l'exécutable pour lancer le test.
### Q7 : recherche d'une valeur
Pour continuer sur les fonctions nécessitant de parcourir la liste, vous
implémenterez ensuite une fonction permettant de déterminer si une valeur est
présente ou non dans la liste.
#### Votre travail
Implémentez la fonction de recherche. Cette fonction renvoie l'adresse de la
cellule contenant la valeur fournie si une telle cellule existe, ou `nullptr`
sinon. Si plusieurs cellules contiennent la valeur, renvoyez l'adresse de l'une
d'elles selon ce qui vous semble le plus efficace.
#### Test
Une fois votre implémentation réalisée, vous pouvez éditer le fichier
`test_liste.cpp` pour décommenter la ligne
```cpp
//#define TEST_RECHERCHE
```
Recompilez ensuite le code et lancez l'exécutable pour lancer le test.
### Q8 : recopie d'une liste
En général, s'il est nécessaire d'implémenter un destructeur à votre classe pour
éviter les fuites mémoire, c'est que votre classes est *propriétaire* et
*responsable* de données stockées sur le tas, à l'extérieur de la classe (ce ne
sont pas des données membres). C'est cette responsabilité qui impose le fait de
nettoyer les cellules à la destruction de la liste. En C++, toute classe est
munie par défaut d'un constructeur par copie et d'un opérateur d'affectation.
Lorsque vous ne les spécifiez pas, ils consistent simplement à recopier les
octets qui constituent la classe. Ce comportement n'est généralement pas adapté
lorsqu'une classe est propriétaire de données sur le tas : ces données ne sont
pas recopiées car elles sont extérieures à la classe, et la classe initiale
ainsi que sa copie se retrouvent à *partager* les mêmes données sur le tas.
#### Votre travail
Cette fois, commencez par décommenter le test pour constater le problème du
constructeur par copie par défaut, en décommentant la ligne :
```cpp
//#define TEST_COPIE
```
Étudiez la situation, comprenez le problème, et implémentez le constructeur par
copie pour vous assurer que la liste copiée est bien une copie, et ne partage
pas de cellule avec la liste initiale. Réalisez ensuite l'opérateur
d'affectation sur le même modèle, en pensant bien à supprimer nettoyer les
cellules présentes au préalable dans la liste qui se fait affecter.
## Serpent
Cette partie n'est pas disponible sous windows sans utiliser le sous-système
linux du fait de l'utilisation de la bibliothèque `ncurses`.
Avec les opérations d'ajout en tête et d'ajout en queue, les listes chaînées
sont adaptées pour réaliser un jeu de *serpent*. Une base vous est fournie, à
vous de l'étendre pour ajouter l'apparition de bonus à manger, des niveaux plus
complexes, l'éventuel changement de niveau, le score, ...
Vous pouvez désormais commencer à examiner les autres fichiers. Le fichier
contenant le programme principal du jeu est `jeu_serpent.cpp`. Sa compilation
est réalisée via `make jeu_serpent`.
<a name="rappels"></a>
## Rappels
Cette section comporte quelques rappels de base de programmation en `C++`.
### Commentaires
Les commentaires sont des portions de fichier qui ne sont pas interprétées par
le compilateur. Ils vous permettent de documenter votre code, et de rajouter des
explications pour le rendre plus lisible. Prenez l'habitude d'écrire des
commentaires dans votre code. Une bonne façon de développer consiste par exemple
à commencer par remplir une fonction avec des commentaire indiquant ce qu'il
faut ajouter, puis à rédiger le code sous les commentaires correspondants.
En `C++` les commentaires sont délimités par `/*` et `*/`. Ils peuvent faire
plusieurs lignes, mais il n'est pas possible de
les imbriquer (et donc de placer des `/* ... */` dans un commentaire) :
```cpp
/* commentaire sur une ligne */
/* commentaire
sur deux lignes */
```
Il est aussi possible en plus de rajouter de courts commentaire en utilisant `//`.
Une fois écrit `//`, le reste de la ligne n'est plus interprété.
```cpp
int a ; //un commentaire de fin de ligne
```
Dans la suite de ces rappels, vous saurez donc identifier les commentaires.
### Types primitifs
Le `C++` propose un certain nombre de types primitifs. Durant ce cours, les
types que vous serez le plus couramment ammenés à employer sont :
* `int` des entiers positifs ou négatifs
* `float` des nombres réels (rationnels en réalité) positifs ou négatifs
* `char` des carractères
Notez que tous ces types sont stockés sur un certain nombre d'octets que vous
pouvez consulter via l'instruction `sizeof(type)`. Du fait que le nombre
d'octets est limité, il n'est pas possible de représenter tous les entiers ou
tous les réels avec ces types. Par exemple 3 milliards est trop grand pour être
stocké dans un type `int`. De même les réels ne peuvent pas être d'une précision
infinie, et seuls certains nombres rationnels peuvent être stockés exactement.
Le nombre $\pi$ par exemple n'est pas rationnel et ne pourra pas être stocké
exactement.
D'autres types primitifs existent, vous les trouverez rapidement en consultant
la documentation du `C++`.
### Cases mémoire
Comme mentionné ci dessus, chaque type primitif est stocké sur un certain nombre
d'octets en mémoire. Lorsque vous écrirez :
```cpp
int variable = 12 ;
```
vous pouvez imaginer qu'une zone en mémoire sera réservée de la bonne taille
(souvent 4 octets pour un `int`), et que vous pouvez ensuite considérer que dans
toute la suite de votre programme le mot clé `variable` sera remplacé par le
contenu de ces 4 octets, interprétés comme un entier.
### Tableau
Un tableau est un groupe de plusieurs cases mémoire consécutives contenant le
même type de donnée. Il peut être alloué statiquement via :
```cpp
int tableau[4] ;
```
Nous avons ici un groupe de 4 entiers stockés les uns à côté des autres en
mémoires, auxquels il est possible de faire référence via le nom "tableau".
Notez que le `4` dans l'exemple précédent ne peut généralement pas être
remplacé par un nom de variable, car le compilateur doit être en mesure de
déterminer la taille du tableau lors de la compilation. Pour créer des tableau
de taille inconnue à la compilation, il faudra passer par une [allocation
dynamique](#alloc_dyn_tableau)
Il est possible d'accéder à un tableau en utilisant les crochets `[` et `]`.
```cpp
int tableau[4] ;
tableau[0] = 1 ;
tableau[3] = 2 ;
tableau[2 = tableau[0] ;
```
### Structures de contrôle
Les instructions principales permettant de faire varier le fil d'éxécution d'un
programme en fonction de tests sont les suivantes :
```cpp
if(test) {
/* code execute en cas de test vrai */
} else {
/* code execute en cas de test faux */
}
for(unsigned int i = 0; i < 5; ++i) {
/* code repete 5 fois */
}
while(test) {
/* code repete tant que le test est vrai */
}
do {
/* code repete jusqu'a ce que le test soit faux */
} while(test) ;
```
### Références
Le comportement par défaut en `C++` est la *copie*. Par exemple dans le code :
```cpp
int a = 5 ;
int b = a ;
b = 12 ;
```
la valeur de la variable `b` est initialement fixée à la même valeur que celle
de `a` (c'est une copie), mais les deux variables ne sont pas liées pour autant.
Ainsi lorsqu'ensuite la valeur de `b` est changée pour `12` la valeur de `a`
reste inchangée à `5`.
Pour lier deux variables afin de faire en sortent qu'elles correspondent aux
mêmes octets en mémoire, il est possible d'utiliser des *références*. Une
référence est réalisée en utilisant le symbole `&` ajouté au type d'une
variable. Dans le code précédent, pour faire en sorte que la variable `b` soit
une référence sur la variable `a` et partage les mêmes octets, il aurait ainsi
fallu écrire :
```cpp
int a = 5 ;
int & b = a ;
b = 12 ;
```
la valeur de la variable a est ici changée pour 12 lorsque b est affecté. Si
cette image vous aide, vous pouvez considérer qu'une référence consiste à donner
un pseudonyme à une variable. Dans la suite du programme, le nom initial ou le
pseudonyme peuvent tous les deux être utilisés pour les mêmes octets.
### Passage par valeur
On parle de *passage de paramètres* lorsqu'on appelle une fonction en lui
fournissant des paramètres. Selon les langages de programmation, il existe de
types de passage de paramètre :
Le **passage par valeur** *recopie* la valeur fournie en paramètre à la fonction
ou à la procédure. Ainsi, une fonction modifiant la valeur de ses paramètre ne
modifiera pas la valeur des variables utilisées pour fournir ces paramètres dans
la fonction appelante. C'est cette stratégie qui est appliquée en `C++`.
```cpp
void f(int a) {
a = a+1 ;
}
int b = 0 ;
f(b) ;
/* b vaut toujours 0 */
```
Le nom *passage par valeur* vient du fait qu'on considère que c'est la *valeur*
de la variable qui est fournie à la fonction lors de l'appel.
Pour plus de détails, vous pouvez vous référer à [l'article de wikipedia sur
les stratégies d'évaluation]("https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_reference")
Pour vous la conclusion à retenir est la suivante : **en `C++` le passage de paramètre
est réalisé par valeur.**
Vous pouvez cependant avoir de temps besoin d'avoir le même comportement que le
passage par nom, si vous souhaitez qu'une fonction modifie des données en dehors
de sa portée, ou si vous voulez éviter la copie de données volumineuses passées
en paramètre. Vous pouvez pour cela utiliser les références en paramètre de
fonctions:
```cpp
void f(int & ref) {
ref = ref + 1 ;
}
int a = 1 ;
f(a) ; /* a vaut maintenant 2 */
```
### Adresses
Une autre notion, souvent comparée aux références est la notion d'*adresse*,
souvent mentionnée sous le nom de *pointeur*. Votre mémoire manipule la mémoire,
y lit des valeurs, y inscrit d'autres valeurs. En `C++` chaque octet de cette
mémoire possède une *adresse*. L'adresse d'un objet en `C++` est l'adresse du
premier octet servant à stocker cet objet. Vous pouvez manipuler des adresses en
utilisant le symbole `*`. Per exemple, l'instruction
```cpp
int * a ;
```
crée une variable qui stockera *l'adresse* d'un entier. Étant donné un objet en
`C++`, il est possible d'obtenir son adresse via le symbole `&`. Par exemple :
```cpp
int a = 10 ;
int * pa = &a ;
```
Attention ici `a` et `pa` ne sont pas deux noms pour la même chose : la variable
`a` est le nom d'une case mémoire contenant un entier de valeur 10. La variable
`pa` est le nom d'une case mémoire contenant l'adresse d'une autre case mémoire
contenant un entier.
```cpp
int a = 10 ;
int * pa = &a ;
// pa = 10 ; //erreur : pb n'est pas un entier
```
L'opération consistant à utiliser une adresse pour accéder à la case mémoire
correspondante s'appelle le *déréférencement*. Cette opération est réalisée en
utilisant également le symbole `*`.
```cpp
int a = 10 ;
int * pa = &a ;
int b = *pa ; //b prend la valeur 10
*pa = 15 ; //a vaut 15 b, vaut 10
int & ra = *pa ; //ra est une reference sur la meme case que a
*pa = 20 ; //a et ra valent desormais 20
int * pra = &ra ; //ra est la meme case que a, pa et pra ont la meme valeur
```
Les références et les adresses sont souvent opposées l'une à l'autre, car ce
sont deux moyens de faire en sorte de manipuler les mêmes octets via plusieurs
variables. Ces deux notions sont en réalité complémentaires, et chaque notion
peut être utilisée pour faire quelques chose qu'il est difficile de réaliser
élégament via l'autre notion. Il est donc essentiel que vous sachiez maîtriser
les deux.
### Allocation dynamique
En `C++`, la mémoire vous est souvent présentée comme découpée en plusieurs zones. Vous
utiliserez généralement la *pile* et le *tas*.
#### La pile
C'est la zone mémoire dans laquelle sont allouées les données locales aux
fonctions : en `C++`, toute variable n'est valable qu'à l'intérieur
de sa *portée*, matérialisée par les accolades (`{`, `}`).
Les paramètres d'une fonction sont également limités à la portée de cette
fonction :
```cpp
int f(int a) {
int b = 10 ;
int c = 0 ;
for(int i = 0; i < b, ++i) {
c = c * a ;
} /* i n'est plus definie */
if(c < 0) {
int d = -c ;
c = c * d ;
} /* d n'est plus definie */
{
int d = 2 * c ;
c = c / d ;
} /* d n'est plus definie */
return c ;
} /* a, b et c ne sont plus definies */
```
Toute donnée que vous créez sans utiliser les fonctions `new` ou
`malloc` est stockée sur la pile, et aura donc une durée de vie limitée.
#### Le tas
C'est une zone mémoire pour créer des données *persistantes*. À moins que
vous ne donniez explicitement l'instruction de détruire les données présentes,
elles persisteront tant que le programme fonctionnera. L'outil `valgrind`
vous permettra de détecter de nombreuses erreurs liées à la gestion de la
mémoire, et nous vous encourageons à l'utiliser systématiquement.
En `C` la gestion du tas en se fait avec le couple de fonctions `malloc` et
`free`. La fonction `malloc` prend en paramètre *le nombre d'octets* à réserver.
Le langage `C` fournit la directive `sizeof` qui permet de connaître le nombre
d'octets nécessaire pour un type atomique ou une structure. La valeur de retour
de `malloc` est une adresse *générique* (de type `void *`), qui indexe le
premier octet alloué dans le tas. Il convient ensuite de convertir cette adresse
générique en une adresse typée correctement via un *cast*. Il est
**indispensable** de récupérer la valeur de retour de `malloc`, sans quoi
l'adresse de la zone allouée est perdue, et vous ne pourrez plus accéder à la
zone, ou la libérer pour faire de la place en mémoire. Une allocation typique
d'un objet sur le tas a donc la forme :
```cpp
int * a = (int *) malloc(sizeof(int)) ;
```
Notez le type `int` qui est ici mentionné trois fois : la première pour
définir le type de la variable déclarée (l'adresse d'un entier), la seconde pour
*caster* l'adresse générique renvoyée par `malloc` en l'adresse d'un
entier, et la troisième pour déterminer le nombre d'octets à réserver pour un
entier via la directive `sizeof`.
En `C` et en `C++`, la norme du langage assure qu'un tableau de données est
une zone mémoire *contiguë* (où les données sont rangées les unes à côté
des autres, il n'y a pas d'espace vide entre les données). Il est donc possible
de réserver un tableau dans le tas en allouant simplement le nombre d'octets
nécessaire pour *l'ensemble* des données du tableau :
```cpp
/* allocation d'un tableau de 10 entiers */
int * tab = (int *) malloc(10*sizeof(int)) ;
```
Les données sont ensuite accessibles comme d'habitude en utilisant les crochets
(`[`, `]`) :
```cpp
for(int i = 0; i < 10; ++i) {
tab[i] = 2*i ;
}
```
De la même façon qu'une parenthèse ouverte à un moment donné doit être refermée
plus tard, une donnée allouée avec `malloc` doit être libérée plus tard avec
`free`. Dans le cas contraire, on parle de *fuite de mémoire*. Prenez donc
l'habitude lorsque vous écrivez `malloc` quelque part d'écrire `free` ailleurs
(ou de noter en commentaire où vous comptez le faire). La fonction `free` prend
en paramètre une adresse *qui doit avoir été fournie par `malloc`*. C'est
parce que `malloc` a réalisé l'allocation que vous n'avez pas à préciser le
nombre d'octets à libérer. Quelque part, en sous main, le nombre d'octets
correspondants à l'adresse a été enregistré. Vous pouvez ainsi libérer la
mémoire allouée par les deux instructions précédentes via :
```cpp
free(a) ;
free(tab) ;
```
Si vous utilisez `valgrind`, les octets qui ont été alloués durant l'exécution
du programme et n'ont pas été libérés à la sortie du programme vous seront
signalés.
En `C++` vous pouvez utiliser `malloc` et `free` mais ces fonctions sont
généralement déconseillées car elles ne sont pas compatibles avec le mécanisme
des constructeurs et destructeurs des objets. Il vous est conseillé d'utiliser
les directives `new` et `delete`, qui initialisent et détruisent correctement
les objets, et perturbent moins le système de types. De même que `malloc`, `new`
produit une adresse qu'il faut récupérer. À la différence de `malloc` cette
adresse est correctement typée par rapport au type de l'objet alloué.
```cpp
int * a = new int ;
int * tab = new int[10] ;
```
Notez ici que vous n'avez pas à mentionner le nombre d'octets, le type fourni à
new suffit. Comme précédemment, chaque utilisation de `new` doit être un
jour compensée par l'utilisation de `delete`. La suppression des variables
précédentes se fait via :
```cpp
delete a ;
delete[] tab ;
```
Notez bien l'utilisation de `delete[]` pour faire écho à `new <type>[]`.
### Classes et structures
Les classes et structures sont à la base de l'élaboration de structures de données
complexes. Une classe (à votre niveau) permet d'agglomérer plusieurs types existants pour
former de nouveaux types de données. Vous pourrez ajouter à votre classes des
méthodes pour manipuler votre nouveau type de données.
Les classes et structures se déclarent via
```cpp
class nom_classe {
/* ... */
} ;
struct nom_structure {
/* ... */
} ;
```
Dans la définition d'une classe ou d'une structure, les mots clé `public` et
`private` permettent de définir ce qui sera accessible ou non pour votre classe
```cpp
class nom_classe {
/* ... */ //ici tout est inaccessible
public :
/* ... */ //ici tout est accessible
private :
/* ... */ //ici tout est de nouveau inaccessible
} ;
struct nom_structure {
/* ... */ //ici tout est accessible
private :
/* ... */ //ici tout est inaccessible
public :
/* ... */ //ici tout est de nouveau accessible
} ;
```
Notez que la différence entre les classes et les structures est que par défaut
dans une classe tout est privé, alors que dans une structure tout est public.
Un exemple de déclaration de structure pourrait être :
```cpp
class Fusee {
public :
/* Constructeur automatiquement appele a l'initialisation */
Fusee() ;
/* Destructeur automatiquement appele a la destruction */
~Fusee() ;
/* fonctions membre publiques */
void faire_le_plein(float carburant) ;
float reserves_carburant() const ; //la methode ne modifie pas la classe
void decoller() ;
private :
/* variables membre privees */
float carbutant ;
float position[3] ;
/* fonctions membre privees */
void disco_mode() ;
} ;
```
Le code des méthodes de cette structure devra ensuite être fourni via
```cpp
Fusee::Fusee() {
/* ... */
}
Fusee::~Fusee() {
/* ... */
}
void Fusee::faire_le_plein(float carburant) {
/* ... */
}
float Fusee::reserves_carburant() const {
/* ... */
}
void Fusee::decoller() {
/* ... */
}
void Fusee::disco_mode() {
/* ... */
}
```
Les membres privés peuvent être utilisés dans la portée de ces fonctions car
elles sont membres de la classe.
Le compilateur se chargera de déterminer le nombre d'octets occupés par la
structure, et vous pourrez l'obtenir via `sizeof(Fusee)`. Il est ensuite
possible de déclarer un objet de type structure et d'accéder à ses champs via la
syntaxe :
```cpp
/* allocation sur la pile */
Fusee f ;
/* le . permet d'acceder aux champs et methodes de la structure */
f.faire_le_plein(12.7) ;
/* allocation sur le tas */
Fusee * pf = new Fusee ;
pf->decoller() ; /* a-> est un raccourci pour (*a). */
delete pf ;
```
Notez bien que dans le cas d'une classe munie d'un constructeur ou d'un
destructeur, l'opérateur `new` prendra soin d'appeler le constructeur, et
l'opérateur `delete` le destructeur. Ces fonctions n'auraient pas été appelées
en utilisant `malloc` et `free`.
Une classe peut être définie récursivement, tant qu'elle ne contient que des
*adresses* ou des *références* sur des structures similaires. Sinon, il serait bien impossible
de déterminer le `sizeof` de la structure pour cause de récursion
```cpp
class Personne {
int num_secu ;
Personne * parent1 ;
Personne * parent2 ;
} ;
```