User Tools

Site Tools


in204:tds:sujets:td3:part1

Partie I – Classe & Fonction Générique

TD3

La classe de la bibliothèque C++ standard dite STL (Standard Template Library) std::vector est définie comme suit :

template <class T, class Alloc=allocator<T>> class vector;

vous trouverez en plus des éléments décrivant la classe dans l’annexe du TD plus d’informations à ce lien.

Pour l’instant, nous ignorons le paramètre Alloc.

Pour pouvoir utiliser cette classe, il est impératif de charger le fichier qui contient la définition de la classe :

#include<vector>

Question n°1

Nous nous intéressons pour trier des éléments dans un tableau dynamique de type std::vector<int>. L’ensemble des fonctions sera créé dans un nom d’espace appelé monomorphic.

Le fichier d’entête simple_sort.hpp expose trois fonctions :

  • populate_with_randoms initialise le vecteur theVector avec theNumberOfValues valeurs entières

tirées au hasard entre theMinValue et theMaxValue,

  • print_vector affiche l'ensemble des valeurs entières contenues dans un vecteur d'entiers,
  • simple_sort tire les valeurs d'un vecteur d'entiers de la plus petite à la plus grande.

Le fichier simple_sort.hpp ressemblera au fichier suivant :

#ifndef simple_sortHPP
#define simple_sortHPP
 
#include<vector>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue);
 
    void print_vector(const std::vector<int>& anArray);
 
    void simple_sort(std::vector<int>& theValues);
}
 
#endif

Le fichier de code simple_sort.cpp ressemblera au fichier suivant :

#include"simple_sort.hpp"
#include<iostream>
#include<stdlib.h>
 
namespace monomorphic
{
 
void populate_with_randoms(std::vector<int>& theVector,
    int theNumberOfValues, int theMinValue, int theMaxValue)
    {}
 
void print_vector(const std::vector<int>& anArray)
{}
 
void simple_sort(std::vector<int>& theValues)
{}
 
}

Question n°1.1

Écrivez une fonction qui prend un objet de type std::vector<int> et qui ajoute à cet objet un certains nombres de valeurs aléatoires theNumberOfValues comprises entre theMinValue et theMaxValue.

void populate_with_randoms(std::vector<int>& theVector,
    int theNumberOfValues, int theMinValue, int theMaxValue)
{}

Instructions pour tirer une valeur aléatoire

Instructions pour tirer une valeur aléatoire

Fonctions C

La fonction ''rand()'' retourne une valeur alérateoire entre 0 et RAND_MAX.

Pour calculer une valeur aléatoire comprise entre theMinValue et theMaxValue, le code suivant peut-être utilisé :

#include<cstdlib>
 
std::srand(std::time(nullptr));
    // Initialise la racine du générateur de 
    // nombre aléatoire avec la valeur temporelle 
    // actuelle.
int width = theMaxValue - theMinValue;
int randomValue = theMinValue + (std::rand() % width);
    // Retourne une valeur entre theMaxValue et theMinValue

Approche C++

A partir de C++, la bibliothèque STL propose des classes implantant différents générateurs de nombres aléatoires et proposant différentes distributions. Pour les besoins de la question, nous nous intéressons à la classe ''std::uniform_int_distribution'' qui génère des séquences de valeurs pseudo-aléatoires selon une loi de distribution dite uniforme.

#include <random>
#include <iostream>
 
std::random_device rd;  
    // Générateur de nombres alératoire qui est utilisé 
    // comme racine d'une séquence de nombres aléatoires.
std::minstd_rand gen(rd()); 
    // Générateur générant des nombres aléatoires initialisées 
    // par une valeur tirée au hasard par le générateur rd. 
std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
    // Crée une distribution qui prend une valeur générée par un
    // générateur aléatoire et retournant une valeur uniformément 
    // distribuée entre theMinValue et theMaxValue.
 
int randomValue = distribution(generator);
    // Une valeur générée entre theMinValue et theMaxValue de 
    // manière équiprobable.

Correction

Correction

Nous proposons plusieurs solutions au problème. Première approche, nous supprimons l'ensemble des valeurs dans le vecteur theVector en effectuant un appel à la fonction clear de l'object std::vector et nous ajoutons à la fin du vecteur, un par un les valeurs aléatoires que nous tirons en appelant la fonction push_back. Suivez le lien pour plus d'informations relativement aux méthodes de la classe ''std::vector''.

#include "../include/simple_sort.hpp"
#include<random>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.clear();
        for(;
            theNumberOfValues > 0;
            theNumberOfValues --)
        {
            theVector.push_back(
                distribution(gen));
        }
    }
}

Une autre solution équivalente consiste à redimensionner le tableau dynamique std::vector à la taille spécifiée par le paramètre theNumberOfValues, l'appel à la méthode resize de std::vector va initialiser exactement theNumberOfValues avec la valeur par défaut. Il est possible ensuite d'affecter à chaque entrée du tableau une valeur aléatoire avec l'opérateur d'accès indexé [].

#include "../include/simple_sort.hpp"
#include<random>
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.resize(theNumberOfValues);
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                distribution(gen));
        }
    }
}

Cependant, nous pouvons constater que nous procédons systématiquement à l'initialisation du générateur de nombre pseudo-aléatoire lorsque nous appelons la fonction std::populate_with_randoms, ce qui n'est pas souhaitable en terme d'efficacité ou au contraire de qualité de la génération des séquence de nombres.

Pour ce faire, nous avons deux approches, soit nous déclarons le générateur comme une variable globale.

#include<random>
 
std::random_device rd;
std::minstd_rand gen(rd());
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.resize(theNumberOfValues);
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                distribution(gen));
        }
    }
}

soit au contraire, nous définissons le générateur de nombre pseudo-aléatoire comme étant une variable statique de fonction, ceci signifie que la variable est partagée entre tous les appels de la fonction, il s'agit d'une variable globale qui n'est visible que par la fonction et qui est initialisée lors du premier appel à la fonction.

#include "simple_sort.hpp"
#include<random>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        static std::random_device rd;        // Variables statiques, initialisées uniquement
        static std::minstd_rand gen(rd());   // lors du premier appel de la fonction et persistant
                                             // entre deux appels de fonctions.
 
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.resize(theNumberOfValues);
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                distribution(gen));
        }
    }
}

Si vous utilisez en lieu et place des classes std::random_device, std::minstd_rand et std::uniform_int_distribution<> les appels aux fonctions std::srand et std::rand, nous obtenons le code suivant :

#include "simple_sort.hpp"
#include<cstdlib>
#include<ctime>

namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::srand(std::time(nullptr)); 
            // Initialisation de la racine, du générateur de nombre aléatoir, 
            // peut-être déplacé au début 
            // du programme comme étant la première instruction 
            // dans la fonction ''main''
        theVector.resize(theNumberOfValues);
        int width = theMaxValue - theMinValue;
        for(int index = theNumberOfValues;
            index  < theNumberOfValues;
            index ++)
        {
            theVector[index] =
                theMinValue + (std::rand() % width);
        }
    }
}

Question n°1.2

Ecrivez the une fonction qui affiche un objet de type std::vector<int> vers la console qui aura l’entête suivante :

void print_vector(const std::vector<int>& anArray)
{}

Correction

Correction

Votre fonction ressemblera à la fonction suivante :

#include "simple_sort.hpp"
#include<iostream>
 
namespace monomorphic
{
    void print_vector(const std::vector<int>& anArray)
    {
        int length = anArray.size();
        std::cout << "[";
        for(int index = 0; index < length - 1; index ++)
            std::cout << anArray[index] << ", ";
        std::cout << anArray[length - 1] << "]" << std::endl;
    }
}

Question n°1.3

Ajoutez la fonction de tri sur le tableau.

void simple_sort(std::vector<int>& theValues)
{
	for (int i = 0; i<theValues.size(); i++)
	{
		for (int j = i + 1; j< theValues.size(); j++)
		{
			// Compare si les deux elements sont dans le bon ordre.
			if (theValues[i] > theValues[j])
			{
				// Procede a la permutation des deux elements
				int Temp = theValues[i];
				theValues[i] = theValues[j];
				theValues[j] = Temp;
			}
		}
	}
}

Correction

Correction

Il s'agit d'un tri par insertion. Nous pouvons envisager d'implanter d'autre tri, comme un tri par bulles par exemple.

Nous avons dans le code précédent explicité l'opération d'échange entre la case i et la case j du tableau. Nous pouvons aussi utiliser la fonction ''std::swap'' qui est définie dans la STL dans le fichier d'entête ''algorithm''. Dans ce cas, le code se simplifie en :

void simple_sort(std::vector<int>& theValues)
{
    for (int i = 0; i<theValues.size(); i++)
    {
        for (int j = i + 1; j< theValues.size(); j++)
        {
            std::swap(theValues[i], theValues[j]);
        }
    }
}

Après cet ajout, votre fichier simple_sort.cpp devrait ressembler au fichier suivant :

#include "simple_sort.hpp"
 
#include<algorithm>
#include<random>
#include<iostream>
 
namespace monomorphic
{
    void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<> distribution(theMinValue, theMaxValue);
        theVector.clear();
        for(;
            theNumberOfValues > 0;
            theNumberOfValues --)
        {
            theVector.push_back(
                distribution(gen));
        }
    }
    void print_vector(const std::vector<int>& anArray)
    {
        int length = anArray.size();
        std::cout << "[";
        for(int index = 0; index < length - 1; index ++)
            std::cout << anArray[index] << ", ";
        std::cout << anArray[length - 1] << "]" << std::endl;
    }
 
    void simple_sort(std::vector<int>& theValues)
    {
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(theValues[i] > theValues[j])
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
}

Question n°1.4

Tester le code que vous avez créé sur un exemple simple, par exemple en créant un tableau de 10 valeurs aléatoires en 1 et 10, l’affichant ensuite, le triant et l’affichant de nouveau.

Correction

Correction

Il suffit d'écrire dans votre fnction main le code suivant :

#include <iostream>
#include"include/simple_sort.hpp"
#include<string>
 
using namespace std;
 
int main()
{
    {
        using namespace monomorphic;
 
        std::vector<int> values;
        populate_with_randoms(values, 10, 1, 10);
        print_vector(values);
        simple_sort(values);
        print_vector(values);
    }

Nous avons dans le code précédent défini une portée débutant par { using namespace monomorphic;. Ceci indique que dans cette portée qui se termine avec le } correspondant nous importons l'ensemble des fonctions contenues dans l'espace de nom monomorphic. Cette importation permet de ne pas avoir à écrire le préfix monomorphic:: devant les fonctions populate_with_randoms, print_vector et simple_sort.

Question n°2

Nous souhaitons étendre cet algorithme de tri fonctionnant sur des entiers à des objets qui peuvent manipuler d’autres éléments que des entiers.

L’ensemble des fonctions sera créé dans un nom d’espace appelé generic. Le fichier d’entête generic_sort.hpp ressemblera au fichier suivant :

#ifndef generic_sortHPP
#define generic_sortHPP
 
#include<vector>
 
namespace generic
{
	// Version générique des fonctions 
	populate_with_randoms
	print_vector;
	simple_sort
}
 
#endif

Question n°2.1

Il n’y aura pas de fichier generic_sort.cpp. Expliquer pourquoi ?

Correction

Correction

Pour une fonction (resp. une classe) qui est définie par un patron de fonction (resp. de classe), la génération du code s'effectuant au moment de l'appel de la fonction (resp. de la création d'un objet). Pour que le compilateur soit en mesure d'effectuer cette génération de code, il est nécessaire que le code soit disponible, cela signifie que le code soit présent dans le fichier qui sera inclut.

Habituellement, le code est séparé en deux fichiers :

  • le fichier '.hpp' qui contient les prototypes des fonctions ainsi que la structure des classes,
  • le fichier '.cpp' qui contient le code définit par le corps des fonctions, l'instanciation des variables globales, des champs statiques, etc.

Habituellement, seul le fichier '.hpp' est “inclut” dans le fichier qui va faire appel à la fonction ou qui va céer un objet d'un type qui est définit dans le fichier '.hpp'. Cependant, ce modèle ne fonctionne pas pour les fonctions et classes qui sont définies par des patrons. Il est nécessaire d'inclure le code contenu dans les corps de fonctions dans le fichier qui va faire appel à la fonction. Dans ce cas, cela signifie que l'ensemble du code va être présent dans le fichier '.hpp'.

Plus précisément, nous pouvons constater que pour la définition des librairies présentes dans la STL (la librairie standard de C++), les fichiers n'ont plus d'extension. Ainsi par exemple, l'entête stdlib.h de C est devenu cstdlib sans extension '.h' pour bien montrer que le fichier inclus mélange définition de protoypes, de types et de patrons.

Dans le cas de ce projet, nous pouvons :

  • soit intégrer les patrons incluant le code dans le fichier simple_sort.hpp,
    #ifndef SIMPLE_SORT_HPP
    #define SIMPLE_SORT_HPP
     
    #include<iostream>
    #include<random>
    #include<vector>
    #include<algorithm>
    #include<cstdio>
     
    namespace monomorphic
    {
        void populate_with_randoms(
            std::vector<int>& theVector,
          	int theNumberOfValues, int theMinValue, int theMaxValue);
     
        void print_vector(const std::vector<int>& anArray);
     
        void simple_sort(std::vector<int>& theValues);
    }
    namespace generic
    {
        template<typename T, typename genType = int>
        void populate_with_randoms(
            std::vector<T>& theVector,
          	int theNumberOfValues, genType theMinValue, genType theMaxValue)
        {
            ... 
        }
        ...
    }
  • soit créer un fichier simple_sort qui inluera le fichier simple_sort.hpp pour les définitions des prototypes des fonctions implantées dans simple_sort.cpp et les patrons des fonctions qui sera défini dans simple_sort.
    #ifndef SIMPLE_SORT
    #define SIMPLE_SORT
     
    #include<iostream>
    #include<random>
    #include<vector>
    #include<algorithm>
    #include<cstdio>
     
    #include"simple_sort.hpp"
     
    namespace generic
    {
        template<typename T, typename genType = int>
        void populate_with_randoms(
            std::vector<T>& theVector,
          	int theNumberOfValues, genType theMinValue, genType theMaxValue)
        {
            ... 
        }
        ...
    }

Question n°2.2

Proposer une réécriture des fonctions populate_with_randoms, print_vector et simple_sort pour qu’elles puissent fonctionner avec n’importe quel autre type comme des double, des float, des short, des unsigned.

Correction

Correction

Nous nous restreignons pour l'instant à des types dénotant des valeurs numériques et supportant nativement une conversion soit implicite soit explicite d'un type entier supporté par le générateur de nombre aléatoire et le type des valeurs stockées dans le tableau dynamique.

Lorsque nous nous intéressons au prototype de la fonction populate_with_randoms monomorphes :

void populate_with_randoms(
        std::vector<int>& theVector,
      	int theNumberOfValues, int theMinValue, int theMaxValue);

Il serait tentant de remplacer toutes les instances de int par un paramètre de type T.
Ceci donnerait la signature suivante :

template<typename T>
void populate_with_randoms(
        std::vector<T>& theVector,
      	T theNumberOfValues, T theMinValue, T theMaxValue)
{
    std::random_device rd;
    std::minstd_rand gen(rd());
    std::uniform_int_distribution<T> distribution(theMinValue, theMaxValue);
    theVector.clear();
    for(;
        theNumberOfValues > 0;
        theNumberOfValues --)
    {
        theVector.push_back(
        (T)distribution(gen));
    }
}

qui en fait serait totalement inadaptée.
En effet, pour le type T=double, nous nous retrouverons avec la signature :

void populate_with_randoms<double>(
        std::vector<double>& theVector,
      	double theNumberOfValues, double theMinValue, double theMaxValue)
{
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<double> 
            distribution(theMinValue, theMaxValue);
            // !!!! l'instantiation uniform_int_distribution<double> 
            // n'est pas supportée
        theVector.clear();
        for(;
            theNumberOfValues > 0;
            theNumberOfValues --)
            // Fonctionne mais theNumberOfValues n'est pas 
            // a priori une valeur flottante mais un entier !
        {
            theVector.push_back(
                (double)distribution(gen));
        }
}

Il est donc nécessaire de bien séparer les différents types des paramètres :

  • std::vector<int>& theVector ⇒ nous pouvons étendre le support de la fonction à tous les types T génériques correspondant à des types numériques.
  • int theNumberOfValues ⇒ cet élément reste un nombre entier, éventuellement nous pouvons y substituer le type size_t.
  • int theMinValue, int theMaxValue ⇒ le support de la fonction peut être étendu à tous les types supportés par la classe std::uniform_int_distribution.

Dans ce cas, nous pouvons redéfinir le patron de la fonction comme suit :

namespace generic 
{
    template<typename T, typename genType>
    void populate_with_randoms(
        std::vector<T>& theVector,
      	size_t theNumberOfValues,
        genType theMinValue, genType theMaxValue)
    {
        std::random_device rd;
        std::minstd_rand gen(rd());
        std::uniform_int_distribution<genType> distribution(theMinValue, theMaxValue);
        theVector.clear();
        for(;
            theNumberOfValues > 0;
            theNumberOfValues --)
        {
            theVector.push_back(
                (genType)distribution(gen));
        }
    }
}

Pour les fonctions print_vector et simple_sort, la généralisation est simple, puisqu'il n'y a qu'un paramètre à généraliser qui est le type des valeurs stockées dans le tableau dynamique.

namespace generic
{
    ...
 
    template<typename T>
    void print_vector(const std::vector<T>& anArray)
    {
        int length = anArray.size();
        std::cout << "[";
        for(int index = 0; index < length - 1; index ++)
            std::cout << anArray[index] << ", ";
        std::cout << anArray[length - 1] << "]" << std::endl;
    }
    template<typename T>
    void simple_sort(std::vector<T>& theValues)
    {
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(theValues[i] > theValues[j])
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
}

Question n°2.3

Tester vos fonctions génériques pour différents types.  

Correction

Correction

Vous créez une fonction main pour appeller les fonctions précédentes pour différents types. Dans l'exemple suivant qui est proposé, nous testons les fonctions génériques pour les types int, float, char. Vous pouvez tester avec d'autres types supportant la conversion d'une valeur numérique vers le type T.

#include"simple_sort.hpp"
#include<iostream>
#include<vector>
 
int main()
{
    {
        using namespace generic;
 
        std::vector<int> values;
        populate_with_randoms(values, 10, 20, 40);
        print_vector(values);
        simple_sort(values);
        print_vector(values);
 
        std::vector<float> floatValues;
        populate_with_randoms(floatValues, 10, 20.0, 40.0);
        print_vector(floatValues);
        simple_sort(floatValues);
        print_vector(floatValues);
 
        std::vector<char> charValues;
        populate_with_randoms(charValues, 10, 'A', 'Z');
        print_vector<char>(charValues);
        simple_sort(charValues);
        print_vector(charValues);
    }
    return 0;
}

Pour les types int et float, le comportement est équivalent à celui des fonctions monomorphiques puisque notre implantation du générateur de nombres aléatoires génère des entiers entre les valeurs minimales et maximales. Lors de l'affichage des valeurs dans le vecteur, que le type soit int ou float, les valeurs sont des valeurs entières. Cependant dans le dernier cas, nous manipulons des caractères et plus exactement le code ASCII des caractères. Nous générons les codes aléatoirements entre 'A' et 'Z', quand la fonction print_vector affiche les valeurs, elle affiche le caractère correspondant au code ASCII situé entre la valeur représentant 'A' et la valeur représentant 'Z'. En conséquence de quoi, elle affiche un caractère supérieur ou égal à 'A' et inférieur ou égal à 'Z'.

in204/tds/sujets/td3/part1.txt · Last modified: 2022/11/18 10:49 (external edit)