Table of Contents

Partie III – Algorithmes génériques

Dans la conclusion du cours, nous affirmons qu’un intérêt du polymorphisme, c’est de pouvoir écrire un algorithme « générique », c’est à dire un algorithme qui pourra fonctionner pour des objets représentant des données de plusieurs types.

Nous considérons un algorithme de tri très simple qui fonctionne sur des entiers :

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

Cet algorithme fonctionne uniquement pour des entiers. Nous nous proposons de transformer cette fonction afin qu’elle puisse aussi bien trier des entiers mais aussi des réels ou des complexes.

Question n° 1

Pour ce faire, nous concevons une classe « abstraite » ayant comme nom « Base » qui expose les fonctions nécessaires à l’écriture de l’algorithme de tri.

Nous souhaitons utiliser l’algorithme avec la signature suivante :

void insertion_sort(std::vector<Base*>& anArray)

Quelles sont les méthodes virtuelles que la classe abstraite doit exposer ?

Correction

Correction

La classe doit exposée une méthode permettant de déterminer si un élément est plus grand que l'autre. Il peut s'agit soit d'une méthode testant si un élément est plus grand que l'autre :

class Base
{
public: 
    virtual bool isGreater(const Base&) const = 0; 
        // Retourne true si l'objet courant est plus grand.
    ...
};

Nous pouvons ajouter éventuellement des méthodes complémentaires comme :

    virtual bool isGreaterOrEqual(const Base&) const = 0; 
    virtual bool isLess(const Base&) const = 0; 
    virtual bool isLessOrEqual(const Base&) const = 0; 
    virtual bool isEqual(const Base&) const = 0; 
    virtual bool isNotEqual(const Base&) const = 0; 

Voire éventuellement une fonction compareTo:

    virtual int compareTo(const Base&) const = 0;
       // retourne -1 si l'instance courante est plus petite que l'instance passée en paramètre
       // retourne 0 si elles sont égales
       // retourne 1 si l'instance courante est plus grande que l'instance passée en paramètre.

Question n° 2

Question n° 2.1

Ajouter à la classe de base Base une méthode purement virtuelle print() qui affiche le contenu de la classe sur la console.

Correction

Correction

Il suffit d'ajouter la méthode suivante:

class Base
{
    ...
public:
    ...
    virtual void print() const = 0;
 
}

Question n° 2.2

Créer une fonction print(std::vector<Base*> anArray) qui prend un tableau en paramètre et affiche l’ensemble des éléments contenus dans le tableau sur la console.

Correction

Correction

Il suffit d'énumérer les éléments dans le tableau ou dans le containeur.

Nous pouvons faire une version orientée tableau qui ressemblera à cette version.

void print(std::vector<Base*> anArray) {

  std::cout << "[";
  int lastIndex = anArray.size()-1;
  if(lastIndex >= 0)
  {
      for(int i = 0; i < lastIndex; i++)
      {
          anArray[i]->print(); 
          std::cout << ", ";
      }
      anArray[lastIndex]->print(); 
  }
  std::cout << "]";

}

Si nous souhaitons être un peu plus “C++” dans l'esprit, nous accéderons par des itérateurs.

template<typename iterator>
void print(iterator theStart, iterator theEnd)
{
    std::cout << "[";
    if (theStart != theEnd)
    {
        *theStart->print();
        theStart++;
        while (theStart != theEnd)
        {
            std::cout << ", ";
            *theStart->print();
        }
        std::cout << "]";
    }
}

Question n° 3

Question n° 3.1

Créer une classe Entier qui dérive de la classe « abstraite » Base et qui contient un champ m_value ayant comme type le type int.

Correction

Correction

En plus de contenir le champ entier m_value, la classe doit définir le constructeur par défaut, le constructeur de conversion d'une valeur de type int vers l'objet Entier ainsi que la conversion d'un objet Entier vers une valeur de type int.

class Entier : public Base
{
private:
    int m_value;
public:
    Entier() : m_value(0) {}
    Entier(int aValue): m_value(aValue) {}
    operator int() { return m_value; }
 
    void print() const { std::cout << m_value; }
    bool isGreater(const Base& unEntier) const
    {
        return m_value > dynamic_cast<const Entier&>(unEntier).m_value;
    }
};

En plus, il faut définir les fonctions print et isGreater. La fonction print se contente d'afficher le contenu de l'entier sur la console, la fonction isGreater est plus complexe. En effet, l'argument a comme type un type Base et non pas un type Entier. Il va falloir convertir ce type vers un type Entier qui est un type hérité, c'est pour cela que nous faisons un dynamic_cast<const Entier&>(unEntier) qui va essayer de convertir si le paramètre unEntier hérite bien de Entier ou est un Entier. Sinon, un exception std::bad_cast sera lancé si la conversion n'est pas possible.

Question n° 3.2

Créer une fonction qui crée un tableau de theNumberOfValues entiers de type Entier

std::vector<Base*> create_integer_array(
	size_t theNumberOfValues)

qui crée un tableau de theNumberOfValues valeurs commençant par la valeur 0 et se terminant à la valeur theNumberOfValues-1.

Correction

Correction

std::vector<Base*> create_integer_array(size_t theNumberOfValues)
{
    std::vector<Base*> result;
    result.resize(theNumberOfValues);
    for (int i = 0; i < theNumberOfValues; i++)
        result[i] = new Entier(i);
    return result;
}

Question n° 3.3

Créer une fonction qui crée un tableau de theNumberOfValues entiers de type Entier dont les éléments sont des nombres aléatoires compris entre theMinValue et theMaxValue.

Cette fonction peut s’implanter comme suit.

std::vector<Base*> create_random_integer_array(
	size_t theNumberOfValues, int theMinValue, int theMaxValue)
{
	std::random_device rd;
	std::mt19937 gen(rd());	
	std::uniform_int_distribution<> distr(theMinValue, theMaxValue);
	std::vector<Base*> array(theNumberOfValues);
	for (size_t i = 0; i < theNumberOfValues; i++)
		array[i] = new Entier(distr(gen));
	return array;
}

Correction

Correction

La fonction initialise un générateur de nombre aléatoire ainsi qu'une distribution uniforme pour des entiers entre theMinValue et theMaxValue. Elle utilise ensuite ce générateur couplé à la distribution pour initialiser les theNumberOfValues éléments du tableau.

Question n°4

Modifier la fonction de tri insertion_sort(std::vector<int>& anArray) afin de ne plus travailler sur des entiers mais sur des objets dérivant de la classe « abstraite » Base :

void insertion_sort(std::vector<Base*>& anArray)

Tester la fonction avec le tableau d’entiers que vous avez créé à la question n°3.3.

Correction

Correction

La seule ligne à modifier est relative à la comparaison, au lieu d'utiliser l'opérateur de comparaison >, nous faisons un appel à la méthode isGreater, ce qui donne le code suivant :

void insertion_sort(std::vector<Base*>& anArray)
{
    for (int i = 0; i < anArray.size(); i++)
    {
        for (int j = i + 1; j < anArray.size(); j++)
        {
            if (anArray[i]->isGreater(*anArray[j]))
                std::swap(anArray[i], anArray[j]);
        }
    }
}

Pour tester, nous allons écrire la fonction suivante :

void testTriEntier()
{
	std::vector<Base*> entiers = create_random_integer_array(10, -100, 100);
	print(entiers);
	std::cout << std::endl;
	insertion_sort(entiers);
	print(entiers);
	std::cout << std::endl;
}

Question n° 5

Nous souhaitons étendre le code à une classe de réel.

Question n° 5.1

Ecrire une nouvelles classe Reel qui dérive de Base et qui contient un champ m_value de type double.

Question n° 5.2

Créer une fonction qui crée un tableau de theNumberOfValues objets de type Reel dont les éléments sont des nombres aléatoires compris entre theMinValue et theMaxValue.

Cette fonction peut s’implanter comme suit.

std::vector<Base*> create_random_double_array(
	size_t theNumberOfValues, double theMinValue, double theMaxValue)
{
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_real_distribution<> distr(theMinValue, theMaxValue);
	std::vector<Base*> array(theNumberOfValues);
	for (size_t i = 0; i < theNumberOfValues; i++)
		array[i] = new Reel(distr(gen));
	return array;
}

Vérifier que l’algorithme de tri fonctionne aussi pour cette nouvelle nouvelle classe.

Correction

Correction

Par analogie à la classe Entier, nous créons la classe réel comme suit :

class Reel : public Base
{
private:
    double m_value;
public:
    Reel() : m_value(0) {}
    Reel(double aValue) : m_value(aValue) {}
    operator double() { return m_value; }
 
    void print() const { std::cout << m_value; }
    bool isGreater(const Base& unReel) const
    {
        return m_value > dynamic_cast<const Reel&>(unReel).m_value;
    }
};

Pour tester, nous utiliserons une fonction similaire à la fonction suivante:

void testTriReel()
{
	std::vector<Base*> reels = create_random_double_array(10, -1, 1);
	print(reels);
	std::cout << std::endl;
	insertion_sort(reels);
	print(reels);
	std::cout << std::endl;
}