Partie I – Classe & Fonction Générique

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.

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);
        }
    }
}

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;
    }
}

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]);
            }
        }
    }
}

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.

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)
      {
          ... 
      }
      ...
  }

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]);
            }
        }
    }
}

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'.