INF3105 — Structures de données et algorithmes
Été 2024
UQAM
Département d'informatique

Laboratoire 4 : Classes génériques Pile<T> et File<T>

Lectures préalables

Objectifs

Tâches

Téléchargement des fichiers du lab4

wget http://cria2.uqam.ca/INF3105/lab4/lab4.zip
unzip lab4.zip

Temps suggéré : 5 minutes.

Analyse sur papier

Temps suggéré : 15 minutes.

Expérimentation

Temps suggéré : 15 minutes.

Débogueur GDB

Débogueurs dans les environnements de développement intégré


Corrections

Temps suggéré : 20 minutes.

Tests unitaires pour Pile<T>

Temps suggéré : 25 minutes.

Tests unitaire pour File<T>

Temps suggéré : 30 minutes.

Exercices complémentaires

Vérification de la libération de la mémoire

Les tests unitaires proposés ne valident pas la libération correcte de la mémoire. Comment pourriez-vous vérifier si la mémoire est correctement libérée? Il y a plusieurs stratégies possibles. La méthode la plus simple est une méthode empirique consistant à faire un grand nombre d'opérations et vérifier la consommation de mémoire. Si jamais une fuite de mémoire (memory leak) était présente, la quantité de mémoire utilisée par le processus augmenterait continuellement.

Voici un programme permettant une telle vérification. 

int main() {
    int n = 0;
    while(true) {
        cout << n++ << " ";
        Pile<int> pile1;
        for(int i = 0; i < 100000; i++)
            pile1.empiler(i);
        Pile<int> pile2 = pile1;
        pile1.vider();

        Pile<int> pile3;
        pile3.empiler(10);
        pile3 = pile2;
        pile3 = pile1;
   }
}

Procédure :

  1. Dans un premier terminal, compilez le programme ci-haut.
  2. Optionnel : tapez dans le premier terminal la commande « ulimit -v 32768 » afin de fixer la limite de mémoire à 32 Mo.
  3. Lancez le programme ci-haut dans le premier terminal.
  4. Dans un deuxième terminal, lancez la commande « top » ou « htop » afin de voir les processus en cours d'exécution.
  5. Repérez votre programme en cours d'exécution.
  6. Vérifiez si la mémoire consommée (colonne SIZE) est constante. Si la taille augmente constamment, il y a peut-être un problème.
  7. Pour vous assurez que cette procédure permet de détecter des fuites de mémoires, essayez d'enlever les appels à «delete» dans pile.h, et refaites les tests.

La méthode ci-haut est empirique. Si la fuite de mémoire est petite, cela prendra beaucoup de temps avant de la détecter. De plus, cela ne teste pas tous les cas possibles.

À noter qu'il existe des outils permettant de détecter les fuites de mémoire. L'un d'eux est Valgrind.

Intégration avec Tableau<>

Il est possible de combiner les structures de données vues jusqu'à présent. Par exemple, on peut faire une tableau de piles! Essayez le programme suivant.

#include "tableau.h"
#include "pile.h"

int main() {
    Tableau<Pile<int>> tab1;
    for(int i = 0; i < 100; i++) {
        Pile pile<int>;
        pile.empiler(-1);
        tab1.ajouter(pile);
        for(int j = 0; j < i; j++)
            tab1[i].empiler(j);
    }
    Tableau<Pile<int>> tab2;
    tab2 = tab1;
    for(int i = 0; i < 100; i++)
        tab1[i] = Pile<int>();
}

Opérateur = efficace

Pile& Pile::operator = (const Pile& autre) {
    if(this == &autre) return *this; // cas spécial lorsqu'on affecte un objet à lui-même

    vider(); // ou: while(sommet != nullptr){ Cellule* t = sommet->suivante; delete sommet; sommet = t; }
    if(autre.sommet != nullptr) {
        sommet = new Cellule(autre.sommet->element);
        Cellule* cp = autre.sommet;
        Cellule* c = sommet;
        while(cp->suivante != nullptr) {
            c->suivante = new Cellule(cp->suivante->element);
            c = c->suivante;
            cp = cp->suivante;
        }
    }
    return p;
}