======= Partie I – Classe & Fonction Générique =====

[[in204:tds:sujets:td3|TD3]]

La classe de la bibliothèque C++ standard dite STL (Standard Template Library) std::vector est définie comme suit :
<code cpp>
template <class T, class Alloc=allocator<T>> class vector;
</code>

vous trouverez en plus des éléments décrivant la classe dans l’annexe du TD plus d’informations [[http://www.cplusplus.com/reference/vector/vector/|à 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 :

<code cpp>

#include<vector>

</code>

===== 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 :

<code cpp>
#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

</code>


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

<code cpp>

#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)
{…}

}

</code>

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

<code cpp>

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

</code>

<hidden Instructions pour tirer une valeur aléatoire>

__Fonctions C__

La fonction [[http://www.cplusplus.com/reference/cstdlib/rand/|''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é : 

<code cpp>

#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
</code>
 
__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 [[https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution|''std::uniform_int_distribution'']] qui génère des séquences de valeurs pseudo-aléatoires selon une loi de distribution dite uniforme.

<code cpp>
#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.
</code>

</hidden>

<hidden 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 [[http://www.cplusplus.com/reference/vector/vector/|le lien]] pour plus d'informations relativement aux méthodes de la classe [[http://www.cplusplus.com/reference/vector/vector/|''std::vector'']].

<code cpp>

#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));
        }
    }
}
</code>

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é ''[]''.

<code cpp>

#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));
        }
    }
}
</code>


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.

<code cpp>
#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));
        }
    }
}
</code>

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.


<code cpp>
#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));
        }
    }
}
</code>

Si vous utilisez en lieu et place des classes [[https://en.cppreference.com/w/cpp/numeric/random/random_device|std::random_device]], [[https://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine|std::minstd_rand]] et [[https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution|std::uniform_int_distribution<>]] les appels aux fonctions [[https://en.cppreference.com/w/cpp/numeric/random/srand|std::srand]] et [[https://en.cppreference.com/w/cpp/numeric/random/rand|std::rand]], nous obtenons le code suivant :


<code>

#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);
        }
    }
}
</code>

</hidden>


==== 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 :

<code cpp>
void print_vector(const std::vector<int>& anArray)
{…}
</code>

<hidden Correction>


Votre fonction ressemblera à la fonction suivante :

<code cpp>
#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;
    }
}

</code>

</hidden>

=== Question n°1.3 ===

Ajoutez la fonction de tri sur le tableau.

<code cpp>
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;
			}
		}
	}
}
</code>

<hidden 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 [[https://en.cppreference.com/w/cpp/algorithm/swap|''std::swap'']] qui est définie dans la STL dans le fichier d'entête [[https://en.cppreference.com/w/cpp/algorithm|''algorithm'']]. Dans ce cas, le code se simplifie en :

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

</code>

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

<code cpp>
#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]);
            }
        }
    }
}
</code>

</hidden>

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

<hidden Correction>



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

<code cpp>
#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);
    }
</code>

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


</hidden>


===== 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 :

<code cpp>
#ifndef generic_sortHPP
#define generic_sortHPP

#include<vector>

namespace generic
{
	// Version générique des fonctions 
	populate_with_randoms
	print_vector;
	simple_sort
}

#endif
</code>

==== Question n°2.1 ===

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

<hidden 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'',\\ <code cpp>
#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)
    {
        ... 
    }
    ...
}
</code>

  * 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''.\\ <code cpp>
#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)
    {
        ... 
    }
    ...
}
</code>


</hidden>

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

<hidden 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 :

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

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

<code cpp>
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));
    }
}
</code>

qui en fait serait totalement inadaptée. \\
En effet, pour le type ''T=double'', nous nous retrouverons avec la signature :
<code cpp>
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));
        }
}
</code>

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 [[https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution|std::uniform_int_distribution]].

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

<code cpp>
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));
        }
    }
}
</code>

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.

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

</hidden>

==== Question n°2.3 ===

Tester vos fonctions génériques pour différents types.
 
<hidden 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''.

<code cpp>
#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;
}
</code>

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


</hidden>