Cours

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

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

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

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

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

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

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

=== Question n°2.3 ===

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

User Tools

Site Tools

Page Tools
