Table of Contents

Partie II – Fonction spécialisée

TD3

Question n°1

Nous considérons la fonction suivante que nous ajoutons à l’espace de nom generic. Expliquez ce qu’elle fait et tester là.

#include <stdio.h>
#include <random>
 
....
 
template<>
void populate_with_randoms(std::vector<std::string>& theVector,
    int theNumberOfValues, int theMinValue, int theMaxValue)
{
    // Initialise le générateur de nombres aléatoires
    // et définit la loi de distribution uniforme.
    std::random_device rd; 
    std::mt19937 generator(rd())
    std::uniform_int_distribution<int> 
        distribution(theMinValue, theMaxValue);
 
    char buffer[20];
 
    int width = theMaxValue - theMinValue;
    for(; 
        theNumberOfValues > 0; 
        theNumberOfValues--)
    {
 
        int randValue = distribution(generator);
        std::sprintf(buffer,"%d",randValue);
        std::string stringValue = buffer;
	theVector.push_back(stringValue);
    }
}

Correction

Correction

Supposons d'abord que nous souhaitons appelé la fonction generic::populate_with_randoms en lui passant un tableau de type std::string avec le code suivant :

#include <iostream>
#include"simple_sort.hpp"
#include<string>
 
using namespace std;
 
int main()
{
    {
        using namespace generic;
        std::vector<std::string> stringValues;
 
        populate_with_randoms(stringValues, 10, 'A', 'Z');
        print_vector(stringValues);
        simple_sort(stringValues);
        print_vector(stringValues);
    }
    return 0;

La compilation de ce code génère une erreur à la ligne :

namespace generic
{
    template<typename T, typename genType = int>
    void populate_with_randoms(
        std::vector<T>& theVector,
      	int theNumberOfValues, genType theMinValue, genType theMaxValue)
    {
        ...
        theVector.push_back(
            (T)distribution(gen));
    }
}

Question n°2

Nous souhaitons pouvoir choisir la fonction de comparaison utilisée dans le simple_sort. Pour l’instant, la fonction de comparaison fait toujours appel à l’opérateur >.

Nous souhaitons utiliser une classe traits qui fournira l’opération de comparaison. Par défaut, cette opération de comparaison est >.

Question n°2.1

Ecrire la classe greater_traits en complétant ce qui manque dans la classe suivante:

template<typename T>
struct greater_traits
{
public:
    static bool is_greater(T aValue, T anotherValue) 
    {
     ...
    }
};

Correction

Correction

La classe greater_test teste si aValue > anotherValue et retourne true si la condition est vérifiée et false si cette condition n'est pas vérifiée.

template<typename T>
struct greater_traits
{
public:
    static bool is_greater(T aValue, T anotherValue) 
    {
        return aValue > anotherValue;
    }
};

La méthode is_greater est précédée du mot clé static, ce qui signifie que cette méthode est une méthode statique aussi appellée méthode de classe. A la différence des méthodes habituelles de l'objet, cette méthode ne peut accéder qu'aux champs statique statiques de la classe. En conséquence, cette méthode n'a pas besoin qu'un objet soit créé pour pouvoir être appelé. Elle peut simplement être appellée selon la syntaxe suivante :

int main()
{
    greater_traits<int>::is_greater(3, 2);
}

Question n°2.2

Modifier la fonction simple_sort pour qu’elle prenne un paramètre de type supplémentaire qui est la classe fournissant l’opération de comparaison.

Correction

Correction

Nous ajoutons à la liste des paramètres de types de la fonction, un paramètre supplémentaire sortTraits qui correspond au type d'une classe qui doit exposer une méthode statique permettant de tester si une valeur est plus grande qu'une autre valeur pour des valeurs de types T et ayant pour nom is_greater.

Cependant, ce paramètre de type est facultatif, par défaut, nous considérons que ce paramètre est initialisé à greater_traits<T>.

Maintenant, nous avons un premier souci. Au moins un paramètre de la fonction doit faire référence à un paramètre de types. Cependant, nous n'avons aucun paramètre qui n'a le type sortTraits. Enfin, nous ne créons aucun objet de type sortTraits que nous allons passer en paramètre. Pour contourner ce problème, nous allons ajouter un paramètre supplémentaire à la fonction qui sera un pointeur sur un objet de type sortTraits et qui sera initialisé à NULL.

    void simple_sort(std::vector<T>& theValues, sortTraits* = NULL)

Comme nous n'utilisons jamais ce paramètre, nous ne donnons même pas de nom à ce paramètre ! Il n'est là que pour respecter la règle qui impose que tout paramètre de type doit être référencé directement ou undirectement par au moins un paramètre de la fonction.

Nous modifions ensuite l'opération de comparaison pour désormais faire appel à la méthode statique is_greater de la classe de type sortTraits.

namespace generic
{
    ...
 
    template<typename T, typename sortTraits = greater_traits<T>> 
    void simple_sort(std::vector<T>& theValues, sortTraits* = NULL)
    {
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(sortTraits::is_greater(theValues[i], theValues[j]))
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
    ...
}

Question n°2.3

Proposer une classe lower_traits qui inverse l’ordre de tri.

Correction

Correction

Il suffit de dupliquer la classe greater_traits et de remplacer l'opérateur > par l'opérateur <.

template<typename T>
struct lower_traits
{
public:
    static bool is_greater(T aValue, T anotherValue) 
    {
        return aValue > anotherValue;
    }
};

Question n°2.4

Tester votre code sur l’exemple suivant :

#include"generic_sort.hpp"
#include<iostream>
 
int main()
{
    std::vector<int> array;
    generic::populate_with_randoms(array, 10, 1, 10);
    generic::print_vector(array);
    std::cout << "\n";
    generic::simple_sort(array);
    generic::print_vector(array);
    std::cout << "\n";
    generic::simple_sort<int, generic::lower_traits<int>>(array);
    generic::print_vector(array);
    return 0;
}

Compléments

Compléments

Nous avons vu comment paramètrer la fonction simple_sort par un opérateur de comparaison. Cependant, l'opérateur de comparaison est un opérateur qui expose une méthode statique. Nous ne pouvons pas choisir un opérateur de conversion dynamique, ie. dont nous pouvons au moment de l'exécution décider de l'ordre, si c'est un tri ascendant ou descendant. Nous pourrions imagine une telle classe.

template<typename T>
struct greater_or_lower_traits
{
private:
    bool m_isAscending;
 
public:
    greater_or_lower_traits():
        m_isAscending(false) {}
    explicit greater_or_lower_traits(bool isAscending):
        m_isAscending(isAscending) {}
 
    set(bool isAscending) { m_isAscending = isAscending; }
    get() const { return m_isAscending ; }
 
    bool is_greater(T aValue, T anotherValue) 
    {
        if(!m_isAscending)
            return aValue < anotherValue;
        return aValue > anotherValue;
    }
};

Sauf que dans ce cas, il est nécessaire d'avoir un champ. Donc la méthode is_greater ne peut pas être une méthode de classe.

Pour ce faire, nous modifions le contrat relatif à la classe traits définissant l'ordre sur les valeurs de type traits comme suit :

  • la méthode is_greater n'est plus une méthode de classe.
  • l'objet expose un constructeur par défaut.
  • l'objet supporte la recopie.

Nous devons modifier en conséquence les classes greater_traits et lower_traits pour transformer la méthode statique en méthode standard :

template<T>
struct greater_traits
{
    public bool is_greater(T aValue, T anotherValue) const
    {
        return aValue > anotherValue;
    }
};
template<T>
struct lower_traits
{
    public bool is_lower(T aValue, T anotherValue) const
    {
        return aValue < anotherValue;
    }
};

Avec ces deux conditions, il est possibles de redéfinir la définition de la fonction simple_sort comme suit :

namespace generic
{
    ...
 
    template<typename T, typename sortTraits = greater_traits<T>> 
    void simple_sort(std::vector<T>& theValues,
        sortTraits traits = sortTraits())
    {    
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(traits.is_greater(theValues[i], theValues[j]))
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
    ...
}

Nous ajoutons un paramètre supplémentaire à la fonction simple_sort qui est le paramètre traits. Ce paramètre a pour type sortTraits et correspond normalement à une instance d'une classe traits qui fournit la méthode is_greater tel que définit précédemment. Cependant, il n'est pas nécessaire de passer ce paramètre quand nous utilisons les classes traits greater_traits ou lower_traits. Dans ce cas, nous affectons à ce paramètre l'objet de type sortTraits qui est initialisé par le constructeur par défaut.

    std::vector<int> vector;
    ...
    simple_sort(vector);       

Dans ce cas, quand le compilateur compile le code simple_sort, il peut inférer que :

  • T dénote le type entier int,
  • aucun argument n'est passé pour le paramètre traits, le type n'est pas résolu.

Il reste donc à résoudre le type sortTraits.

  • aucun type n'est passé en paramètre à la fonction simple_sort
  • un type par défaut est spécifié pour le type sortTraits. Dans ce cas, le compilateur affecte à sortTraits le type par défaut, c'est-à-dire greater_traits<T> avec T==int qui se transforme en greater_traits<int>.

Une fois le type sortTraits inféré, il ne reste plus qu'à affecter à traits la valeur par défaut. Cette valeur par défaut est défini comme étant égal une instance d'objet de type sortTraits initialisé par son constructeur par défaut : sortTraits(). Ce qui dans le cas correspond à greater_traits<int>(). Le compilateur génère donc l'appel suivant :

    std::vector<int> vector;
    ...
    simple_sort<int, greater_traits<int>)(vector, greater_traits<int>());       

Considérons désormais l'appel suivant:

    std::vector<int> vector;
    ...
    simple_sort<int, lower_traits<int>>(vector);       

Dans ce cas, quand le compilateur compile le code simple_sort, il peut inférer que :

  • T dénote le type entier int,
  • aucun argument n'est passé pour le paramètre traits, le type n'est pas résolu.

Il reste donc à résoudre le type sortTraits.

  • le type lower_traits<int> est passé en paramètre à la fonction simple_sort. Dans ce cas, le compilateur affecte à sortTraits le type par défaut, c'est-à-dire lower_traits<int>.

Une fois le type sortTraits inféré, il ne reste plus qu'à affecter à traits la valeur par défaut. Cette valeur par défaut est défini comme étant égal une instance d'objet de type sortTraits initialisé par son constructeur par défaut : sortTraits(). Ce qui dans le cas correspond à lower_traits<int>(). Le compilateur génère donc l'appel suivant :

    std::vector<int> vector;
    ...
    simple_sort<int, lower_traits<int>>(vector, lower_traits<int>());       

Enfin, si je souhaite effectuer un appel en passant une instance de l'objet greater_or_lower_traits, il suffit d'écrire le code suivant :

    std::vector<int> vector;
 
    greater_or_lower_traits traits(true);
    simple_sort(vector, traits);
    traits.set(false);       
    simple_sort(vector, traits);

Mais il est tout à fait possible d'écrire aussi :

    std::vector<int> vector;
 
    simple_sort<int, greater_or_lower_traits <int>>(vector);

qui deviendra au moment de la compilation :

    std::vector<int> vector;
 
    simple_sort<int, greater_or_lower_traits <int>>(vector, 
        greater_or_lower_traits<int>());