Les zones mémoire
Différentes zones de mémoire sont utilisées pour un processus :
Les zones text et data sont intégrées dans le fichier objet exécutable : elles contiennent des valeurs spécifiées statiquement dans le programme comme des valeurs de variables globales ou champs statiques (entiers, flottants, chaînes de caractères) ainsi que les instructions du programme (dans text). La zone text est en lecture seule afin que l'on ne puisse modifier dynamiquement les instructions exécutées ainsi que certaines chaînes de caractères. Les autres zones sont accessibles en lecture et écriture. Le segment BSS est créé à l'exécution du programme avec une taille fixée nécessaire à la conservation des variables globales qui seront initialisées dynamiquement.
Les systèmes d'exploitations modernes protègent les pages de mémoire de lecture ou écriture par des processus étrangers. Si l'on tente une telle opération, nous sommes confrontés à une erreur de segmentation (signal SIGSEV envoyé au processus qui provoque son arrêt).
Voici un exemple de programme avec l'emplacement des données utilisées (nous n'utilisons pas pour l'instant d'allocation dynamique, le tas n'est donc pas employé) :
#include <iostream>
const char * helloWorldMessage = "Hello world!"; // chaîne conservée dans la zone en lecture seule text
char helloWorldMessage2[] = "Hello world 2!"; // chaîne initialisée statiquement et conservée dans data, peut être modifiée
void printMessage()
{
static char * lastMessage = helloWorldMessage2; // le pointeur lastMessage est conservé dans data et initialisé statiquement avec l'adresse mémoire de helloWorldMessage2
char * currentMessage = NULL; // variable locale conservée dans la pile d'appel
// on alterne entre les deux messages à chaque appel de printMessage
if (lastMessage == helloWorldMessage)
currentMessage = helloWorldMessage2;
else if (lastMessage == helloWorldMessage2)
currentMessage = (char*)helloWorldMessage;
cout << currentMessage << endl;
lastMessage = currentMessage; // pour le prochain appel à printmessage
}
int main()
{
for (int i = 0; i < 10; i++) // i est une variable locale dans la pile
{
printMessage(); // on empile l'appel à printMessage
}
}
La déclaration de variables locales sur la pile
Les variables locales sont stockées sur la pile d'appel. Elles sont déclarées dans le corps d'une fonction. Le compilateur relève toutes les variables locales déclarées et prévoie l'allocation d'un espace mémoire suffisant sur la pile lors de l'entrée dans la fonction. Lorsque l'on sort de la fonction, la variable est détruite par libération de l'espace mémoire réservé dans la pile.
L'utilisation de variables locales est simple et présente l'avantage d'une destruction automatique. Toutefois il n'est pas possible de détruire la variable prématurément avant la fin de la fonction. Ainsi une variable locale déclarée dans la fonction main d'entrée reste vivante durant tout le déroulement du programme.
Les variables locales sont adaptées pour des types primitifs ou des types personnalisés (structures, classes) occupant peu d'espace mémoire, la taille de la pile d'appel étant en général limitée. Il faut faire attention à ne pas conserver de pointeurs ou références vers des variables locales lorsque l'on est sorti de leur portée :
#include <iostream>
using namespace std;
int * factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
cout << "Value of factorial (inside function call): " << result << endl;
return &result;
}
int otherFunction(int * pointer) {
int result = 7;
cout << "Value: " << *pointer << endl;
return result;
}
int main() {
int * pointer = factorial(10);
otherFunction(pointer);
}
Cette fonction calculant la factorielle de n retourne un pointeur vers un entier qui est une variable locale de la fonction. Ainsi lorsque l'on sort de la fonction, result est enlevé de la pile et le pointeur pointe vers une zone inactive. L'appel à otherFunction qui tente de déréférencer le pointeur peut afficher une valeur incohérente (contenu actuel de la zone mémoire) ou provoquer une erreur de segmentation (zone mémoire d'accès interdit).
On notera que le compilateur nous aura prévenu du problème avec un avertissement (qui n'empêche pas la compilation) :
stackMisuse.cpp: In function ‘int* factorial(int)’:
stackMisuse.cpp:6:6: warning: address of local variable ‘result’ returned [-Wreturn-local-addr]
int result = 1;
^~~~~~
L'allocation dynamique
L'allocation dynamique est le mécanisme permettant de créer lors de l'exécution du programme des structures de données dans une zone mémoire appelée le tas (contrairement aux variables locales initialisées dans la pile d'appel). On parle d'allocation dynamique par opposition à l'allocation statique survenant lors de la compilation ; il est impossible par le compilateur (sauf cas triviaux) de deviner quand et comment les allocations dynamiques seront réalisées : ce n'est qu'à l'exécution que l'on peut le savoir.
On utilise l'allocation dynamique lorsque la quantité de données à stocker en mémoire dépend de conditions uniquement connues à l'exécution (données reçues de l'extérieur). Pour chaque allocation réalisée, il est nécessaire de prévoir une libération ultérieure afin d'éviter toute fuite de mémoire. Des fuites de mémoire conduisent un programme à utiliser de plus en plus de mémoire lors de son exécution jusqu'à son éventuel arrêt forcé par le noyau en cas de pénurie de mémoire.
Utilisation de malloc
Les fonctions malloc et calloc sont fournies par la bibliothèque standard C pour allouer dynamiquement de la mémoire. La désallocation se fait avec la méthode free.
Ces fonctions sont utilisables en C++ mais on préferera néanmoins utiliser les opérateurs d'allocation new et de destruction delete.
Voici un exemple écrivant sur la sortie standard des nombres entre 0 et n dans un ordre aléatoire :
/* Création d'un tableau de n int */
int * intTab = (int *)calloc(n , sizeof(int)); /* calloc remplit la zone mémoire avec des octets nuls */
if (intTab == null) {
cerr << "allocation failure" << endl;
abort();
}
/* On remplit le tableau */
for (int i = 0; i < n; i++)
intTab[i] = i;
/* On mélange le tableau */
shuffle(intTab, n);
/* On écrit les nombre mélangés */
for (int i = 0; i < n; i++)
cout << i << endl;
/* On libère l'espace du tableau */
free(intTab);
malloc (ou calloc) recherche une zone mémoire libre pour stocker n int consécutifs : on retourne alors un pointeur vers cette zone. Un registre des zones allouées (avec leur taille) ainsi que des emplacements libres est géré par malloc. On peut ensuite appeler free pour libérer la structure de la mémoire lorsque nous n'avons plus besoin d'elle.
Voici les signatures des méthodes malloc, calloc, realloc et free (définies dans stdlib.h) :
- void *malloc(size_t size);
- void free(void *ptr);
- void *calloc(size_t nmemb, size_t size);
- void *realloc(void *ptr, size_t size);
Le type de retour void* défini un pointeur vers un type indéfini ce qui explique la nécessité de caster le retour. La fonction realloc permet d'agrandir ou réduire un espace déjà alloué (et peut retourner un nouveau pointeur). En cas d'échec d'allocation, un pointeur nul est retourné : une bonne pratique consiste à vérifier systématiquement ceci.
Utilisation des opérateurs new et delete
Les opérateurs new et delete en C++ correspondent aux fonctions calloc et free de la bibliothèque C. En C++, on n'utilisera plus malloc, calloc et free sauf pour des raisons de rétro-compatibilité avec du vieux code en C. new alloue un objet et retourne un pointeur vers celui-ci tandis que delete permet de le détruire.
Ainsi pour allouer un tableau d'entiers de taille n et ensuite pour le détruire, on utiliser le code suivant :
int * intTab = new int[n]; ... delete[] intTab;
L'allocation peut échouer et lever une exception bad_alloc que l'on peut capturer (si l'on ne capture pas l'exception, le programme se termine abruptement). Ainsi le programme suivant essaiera d'allouer le plus gros tableau de char possible (en doublant la taille à chaque fois) et écrira sa taille sur la sortie standard :
#include <exception>
#include <iostream>
using namespace std;
int main() {
size_t size = 1;
while (true) {
try {
char * tab = new char[size];
cout << "Allocation succeeded with size=" << size << endl;
delete[] tab;
} catch (bad_alloc e) {
cout << "Allocation failed with size=" << size << endl;
return 0;
}
size *= 2;
}
}
Les opérateurs new et delete peuvent aussi servir pour l'allocation/libération d'éléments individuels :
int * singleInt = new int(42); ... delete singleInt;
Les opérateurs new et delete permettent aussi de créer et détruire des objets dont les classes sont munies de constructeurs et destructeurs :
#include <iostream>
using namespace std;
const int currentYear = 2018;
class Person {
private:
string name;
int birthYear;
int age;
public:
Person(string name, int birthYear): name(name), birthYear(birthYear) {
cerr << "Allocating person " << name << endl;
age = currentYear - birthYear;
}
string getName() const { return name; }
int getBirthYear() const { return birthYear; }
int getAge() const { return age; }
~Person() {
cerr << "Destroying person " << name << endl;
}
};
int main() {
// Using pointer
Person * p = new Person("foobar", 2000);
cout << p->getName() << " is " << p->getAge() << " old " << endl;
// Can also be used as a reference
Person& p2 = *p;
cout << p2.getName() << " is " << p2.getAge() << " old " << endl;
delete p;
// the following statement should raise a logic_error (null reference)
cout << p2.getName() << " is " << p2.getAge() << " old " << endl;
}
Ainsi l'opérateur new a la responsabilité d'allouer l'espace mémoire sur le tas pour accueillir l'objet (ce qui peut échouer en cas de pénurie de mémoire) et d'appeler le constructeur de l'objet le cas échéant afin de l'initialiser. De manière anologue delete appelle le déstructeur de l'objet s'il existe puis libère l'espace mémoire sur le tas. Ces même remarques s'appliquant pour la version tableau des opérateurs.
⚠ Créer un objet dynamiquement avec l'opérateur new nécessite des précautions :
- Une pénurie de mémoire peut empêcher l'allocation (rare pour des petits objets individuels, plus fréquents pour des grands tableaux)
- Il faut toujours détruire l'objet après son utilisation avec delete pour ne pas créer de fuites mémoires (processus nécessitant de plus en plus de mémoire avec le temps)
- Il ne faut pas déréférencer un pointeur qui n'est pas encore alloué ou alors qui a été libéré (pointeur nul)
Voici quelques exemples de comportements problématiques :
int * i; cout << "Value of i: " << *i << endl; // Déréférencement interdit: le pointeur i ne pointe vers rien i = new int(1); cout << "Value of i: " << *i << endl; // Pas de problème, i pointe vers un entier 1 dans le tas int * j = i; *i = 2; // Affectation possible cout << "Value of j: " << *j << endl; // i et j sont des pointeurs vers le même entier de valeur 2 delete i; // nous libérons l'entier de la mémoire cout << "Value of i: " << *i << endl; // Pas possible car l'entier a été libéré cout << "Value of j: " << *j << endl; // SEGFAULT possible : j pointe toujours vers une adresse mémoire mais qui a été libérée par delete i
Les pointeurs intelligents
Les pointeurs intelligents sont implantés sous forme de classes de la bibliothèques standard et permettent de limiter les risques liés à la manipulation de pointeur (en particulier les fuites mémoires liées à l'oubli d'appel à delete). Ils peuvent être considérés comme des sortes d'enveloppe pour les pointeurs classiques.
Pointeur unique
La classe unique_ptr est utilisable pour représenter un pointeur unique qui est donc le seul à pointer vers un objet donné.
Reprenons comme exemple la classe Person représentant un individu avec son nom et année de naissance et crééons des unique_ptr<Person> :
#include <iostream>
#include <memory>
using namespace std;
void f() {
unique_ptr<Person> p1(new Person("Foo", 1970));
unique_ptr<Person> p2(new Person("Bar", 1980));
cout << "Age difference: " << p1->getAge() - p2->getAge() << endl;
}
Lorsque nous sortons de la fonction f, les pointeurs uniques sont détruits et par conséquent les objets Person vers lesquels ils pointent : il n'est plus nécessaire d'appeler delete. L'inconvénient des pointeurs uniques (mais ce qui est aussi leur caractéristique) est qu'il est impossible de pointer avec plusieurs pointeurs uniques vers le même objet. Ainsi le code suivant ne fonctionne pas (le compilateur proteste) :
unique_ptr<Person> p1(new Person("Foo", 1970));
unique_ptr<Person> p3 = p1; // impossible car deux pointeurs pointeraient vers Person("Foo", 1970)
Toutefois, il est possible de transférer la propriété d'un objet d'un pointeur unique vers un autre pointeur unique. Le code suivant fonctionne :
unique_ptr<Person> p1(new Person("Foo", 1970));
cout << p1.get() << endl;
unique_ptr<Person> p2(move(p1)); // p2 pointe maintenant vers Person("Foo", 1970) tandis que p1 devient un pointeur nul
cout << p1.get() << endl;
cout << p2.get() << endl;
Le problème réside maintenant dans le fait que p1 ne pointe vers rien. Mais on peut toujours revenir à la situation initiale (p1 pointant vers l'objet et p2 vers rien) :
p1 = move(p2);
Pointeur partagé
Les pointeurs uniques ne permettent pas d'avoir plusieurs pointeurs menant vers le même objet. Pour résoudre ce problème, nous utilisons des pointeurs partagés.
Afin de mettre en œuvre un logiciel de généalogie, nous décidons d'étendre la classe Person précédemment réalisée afin d'indiquer son éventuel enfant. Pour simplifier notre modèle, nous considérons qu'une personne a soit un seul enfant, soit pas d'enfant du tout.
class PersonWithChild: public Person {
private:
shared_ptr<Person> child;
public:
PersonWithChild(string name, int birthYear): Person(name, birthYear) {}
void setChild(shared_ptr<Person> child) {
this->child = child;
}
shared_ptr<Person> getChild() {
return child;
}
}
Plusieurs shared_ptr peuvent pointer vers la même personne. Par exemple, nous pouvons créer deux parents et leur enfant unique :
int main() {
shared_ptr<Person> mother(new PersonWithChild("Mother", 1970));
shared_ptr<Person> father(new PersonWithChild("Father", 1971));
shared_ptr<Person> baby(new PersonWithChild("baby", 2005));
cout << mother.use_count() << "," << father.use_count() << "," << baby.use_count() << endl; // 1,1,1
mother.setChild(baby);
father.setChild(baby);
cout << mother.use_count() << "," << father.use_count() << "," << baby.use_count() << endl; // 1,1,3
// maintenant il existe trois shared_ptr pointant vers baby:
// 1: le shared_ptr du main
// 2: le shared_ptr child de la mère
// 3: le shared_ptr child du père
baby = 0; // plus de pointeur dans le main vers baby
// mais il reste les pointeurs child dans mother et father
cout << mother.getChild()->getAge() << endl; // baby est toujours là: on affiche son âge
father = 0; // father est détruit car plus aucun pointeur ne mène à lui
mother = 0; // mother est détruit car plus aucun pointeur
// et également baby car mother détenait le dernier pointeur vers baby
}
Comment s'assurer que les objets pour la mère, le père et le bébé sont bien détruits lorsqu'ils ne sont plus utiles ? Le shared_ptr utilise pour cela un comptage de références : tous les shared_ptr qui pointent vers le même objet partagent un compteur commun qui indique le nombre de pointeurs courants. On peut obtenir la valeur de ce compteur avec use_count(). Lorsque cette valeur redescend à zéro, l'objet pointé est détruit (avec appel automatique à free) puisque plus aucun pointeur ne mène vers lui.
Il n'est pas nécessaire à la sortie d'une méthode d'initialiser à zéro les variables locales shared_ptr : ils sont automatiquement détruits (et l'objet pointé si le compteur de référence devient nul).
☞ Par défaut un pointeur partagé appelle l'opérateur delete pour détruire l'objet pointé lorsque c'est nécessaire. Il est aussi possible de passer comme deuxième paramètre de shared_ptr un destructeur personnalisé :
void customizedDeleter(Person * person) {
cerr << "We destroy " << person->getName() << " using a shared_ptr" << endl;
delete person;
}
int main() {
shared_ptr<Person> mother(new PersonWithChild("Mother", 1970), &customizedDeleter);
mother = 0;
}
Pointeur faible
Lorsque nous utilisons des pointeurs partagés, un objet est détruit lorsque son compteur de référence chute à 0 (plus aucun pointeur lié à l'objet). Dans la majorité des cas, cela est suffisant. Toutefois, il peut arriver que cette stratégie de destruction pose problème.
Réécrivons la classe PersonWithChild en introduisant des nouveaux champs parent1 indiquant les deux parents d'une personne (affectés à l'enfant lors de l'appel à setChild sur ses parents) :
class PersonWithChild: public Person {
private:
shared_ptr<Person> child;
shared_ptr<Person> parent1;
shared_ptr<Person> parent2;
public:
PersonWithChild(string name, int birthYear): Person(name, birthYear) {}
void setChild(shared_ptr<Person> child) {
this->child = child;
if (auto castChild = dynamic_pointer_cast<PersonWithChild>(child)) {
if (! castChild->parent1) castChild->parent1 = shared_ptr<Person>(this);
else if (! castChild->parent2) castChild->parent2 = shared_ptr<Person>(this);
}
}
shared_ptr<Person> getChild() {
return child;
}
shared_ptr<Person> getParent1() {
return parent1;
}
shared_ptr<Person> getParent2() {
return parent2;
}
}
Si l'on réexécute le main précédent, on constate qu'après la construction des parents et du bébé, chacun des parents a un compteur de références de 2 (avec le pointeur du bébé vers eux) et le bébé a un compteur de références de 3. Avec baby = 0 dans le main, le compteur de références du bébé chute à 2, avec mother = 0 le compteur de références de la mère chute à 1 et pas à zéro : en effet le bébé détient toujours un pointeur vers sa mère. Même remarque pour le père. A la fin du main, les compteurs de références sont :
Mother -> 1 Father -> 1 Baby -> 2
Aucun des objets ne peut être détruit ; pourtant il n'existe plus aucun moyen d'y accéder. Il y a donc une fuite de mémoire. Celle-ci est liée à l'existence de références circulaires : en effet la mère pointe vers le bébé qui lui-même pointe vers la mère (idem pour la relation entre le père et le bébé). Un shared_ptr avec comptage de références n'est donc pas adapté à cette situation. On peut y remédier par l'usage d'un weak_ptr (pointeur faible). Un pointeur faible n'impacte pas le compteur de références : on peut ainsi déclarer les parents en weak_ptr :
class PersonWithChild: public Person {
private:
shared_ptr<Person> child;
weak_ptr<Person> parent1;
weak_ptr<Person> parent2;
// ...
Un pointeur faible n'appelle jamais de destructeur sur l'objet ; un objet pointé avec un pointeur faible quelque part doit toujours être pointé avec au moins un shared_ptr autre part. S'il n'y a plus de shared_ptr qui pointent vers l'objet et que le compteur de références chute à zéro, le weak_ptr devient expiré (ptr.expired() retourne true). Il est possible d'obtenir un shared_ptr à partir d'un weak_ptr non expiré avec la méthode lock().
Ainsi si nous crééons un enfant en indiquant ses parents puis détruisons tous les shared_ptr vers les parents, les objets des parents sont détruits et l'enfant a alors des weak_ptr expirés. Avant d'utiliser un weak_ptr, il faut toujours vérifier sa non-expiration. Le plus simple consiste à appeler la méthode lock de conversion en shared_ptr qui retournera un shared_ptr nul si le pointeur faible est expiré.
Implantons par exemple une méthode computeParentAgeSum() retournant la somme des âges des parents :
int PersonWithChild::computeParentAgeSum() {
int sum = 0;
if (auto p1 = parent1.lock())
sum += p1->getAge();
if (auto p2 = parent2.lock())
sum += p2->getAge();
return sum;
}
Exercices
Crible d'Eratosthène
Le crible d'Eratosthène est une méthode mise au point par le mathématicien et philosophe grec à qui elle doit son nom pour trouver des nombres premiers. Nous nous proposons d'implanter une classe qui nous permettra de connaître tous les nombres premiers inférieurs à un entier N fixé.
Voici un exemple d'utilisation de cette classe :
int main() {
EraSieve sieve(1000000); // pour connaître tous les nombres premiers jusqu'à 1 million
sieve.strike();
cout << "2017 prime? " << sieve.isPrime(2017) << endl;
cout << "2 prime? " << sieve.isPrime(2) << endl;
cout << "1024 prime? " << sieve.isPrime(1024) << endl;
cout << "Largest known prime: " << sieve.getLargestKnownPrime() << endl;
cout << "sizeof(sieve)= " << sizeof(sieve) << endl;
}
Le crible nécessite de disposer d'un tableau de N cellules de booléens. On teste chacun des diviseurs et on barre toutes les cellules (passage à true) multiples de ce diviseur (à part le diviseur lui-même) :
- Pour le diviseur 2, on barre les cellules 4, 6, 8, 10...
- Pour le diviseur 3, on barre les cellules 6 (déjà barré), 9, 12 (déjà barré)...
- Pour le diviseur 5, on barre 10, 15, 20...
- Pour le diviseur 7, on barre 14, 21...
- ...
Remarque : on ne teste que les diviseurs premiers ; il est ainsi inutile de tester un diviseur déjà barré (qui n'est pas premier)
- Implantez un constructeur pour la classe EraSieve qui créé un tableau de N cellules (N étant passé en argument au constructeur). Est-il possible de créer un tableau sans allocation dynamique ? Pourquoi ?
- Implantez un destructeur pour EraSieve afin de gérer la libération du tableau
- Ecrivez une méthode void strikeNumbers(int divider) barrant tous les nombres multiples d'un diviseur dans le tableau.
- Implantez une méthode int getUnstrikenNumber(int k) retournant le premier nombre non-barré immédiatement supérieur ou égal au paramètre k.
- Implantez maintenant une méthode void strike() barrant tous les nombres qui ne sont pas premiers. Pour cela on appelera strikeNumbers() pour tous les diviseurs non-barrés jusqu'à la racine carrée de N (condition divider * divider <= N) ; pour les diviseurs plus grands, le premier nombre barré est au-delà de la taille du tableau.
- Implantez la méthode int getLargestKnownPrime() retournant le plus grand nombre premier connu (en fait le dernier nombre non-barré du tableau).
- Testez la méthode main() présentée précédemment. Que se passe-t-il si on oublie d'appeler la méthode strike() ?
- Quelle valeur est retournée par sizeof(sieve) ? Comment peut-on l'expliquer ? Comment connaître la taille totale nécessaire en mémoire pour sieve ?
Liste chaînée
Une liste chaînée est une structure de donnée stockant une collection d'éléments. Chaque élément est conservé dans un nœud (Node), les nœuds étant connectés ensemble par des liens.
Il est possible de placer tout type d'élément dans la liste chaînée ; pour les besoins de l'exercice, nous utiliserons des int.
- Créez un nouveau fichier linkedlist.hpp pour écrire le module de gestion de listes chaînées.
- Mettez en place un namespace CustomCollections dans lequel nous allons implanter les classes nécessaires.
-
Créez une nouvelle classe nommée LinkedListNode représentant un nœud de la liste chaînée. Cette classe dispose des données suivantes :
- L'élément stocké dans le nœud (un int)
- Un pointeur vers le nœud suivant de la liste
- Implantez les champs de la classe en visibilité private et ajoutez des getters et setters pour y accéder et les changer.
- Implantez un constructeur prenant en paramètre l'élément à accueillir dans le nœud. Le pointeur de nœud suivant est initialisé à NULL par défaut.
- Créez une classe LinkedList comprenant un pointeur vers le premier nœud de la liste chaînée.
- Ajoutez une méthode createNode() de visibilité private dans LinkedList permettant d'instancier un nouveau LinkedListNode avec un élément passé en paramètre. On retournera un pointeur simple vers l'élément instantié.
- Ajoutez une méthode void addAtFront(int element) rajoutant l'élément indiqué dans un nouveau nœud au début de la liste. Pour cela, il sera nécessaire d'instancier un nouveau nœud avec l'élément, de changer le pointeur d'élément suivant de cet élément pour qu'il pointe vers la tête de liste, puis ensuite de changer la tête de liste afin de pointer vers le nouveau nœud instancié.
- Implantez une méthode int get(int i) permettant d'obtenir l'élément d'indice i de la liste (les indices démarrent à 0). Pour cela, il faut parcourir les nœuds en utilisant les pointeurs suivants.
- Implantez une méthode void remove(int i) permettant d'enlever l'élément d'indice i de la liste. Il faut repérer le nœud à supprimer ainsi que ses nœuds immédiatement précédent et suivant. On supprime le nœud et on change le pointeur du nœud précédent vers le pointeur du nœud suivant.
- Ajoutez une méthode int getSize() pour obtenir la taille de la liste. Si l'on ne souhaite pas parcourir tous les nœuds avec une boucle, comment peut-on s'y prendre pour obtenir immédiatement la taille ?
- Que se passe-t-il si nous oublions d'implanter un destructeur pour la classe LinkedList ? Implantez une telle méthode ; vous pouvez vous servir des méthodes précédemment écrites.
- Comment pourrait-on implanter intelligemment une méthode void addAtEnd(int element) permettant d'ajouter rapidement un élément à la fin de la liste ?
- Serait-il raisonnable d'avoir une méthode publique LinkedListNode * getFirstNode() retournant un pointeur vers le premier nœud de la liste ? Expliquez pourquoi.
- Afin de fiabiliser l'usage des pointeurs, remplacez les pointeurs simples des nœuds par des shared_ptr<LinkedListNode>. Est-il maintenant nécessaire d'utiliser l'opérateur delete pour supprimer des nœuds ? Le destructeur de LinkedList est-il encore nécessaire ?
Testez toutes vos méthodes avec une méthode main() pour faire des opérations d'ajout, d'accès et de suppression d'éléments.
Liste doublement chaînée
On reprend l'exercice précédent en implantant maintenant une liste doublement chaînée. A la différence d'une liste simplement chaînée, un nœud contient également un pointeur vers le nœud précédent. Réécrivez toutes les méthodes afin de prendre en compte ce second pointeur. On continuera d'utiliser des shared_ptr<LinkedListNode>.
On cherchera en particulier à optimiser le code de certaines méthodes lorsque c'est possible. Ainsi par exemple les méthodes int get(int i) et void remove(int i) peuvent bénéficier d'un parcours depuis la fin de la liste en utilisant le pointeur précédent si i est élevé.