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>

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

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

#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

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

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

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

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.

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

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

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.

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