M2103-TP9-EXO-5

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe User, comme elle est décrite sur le schéma UML. Le constructeur initialise les attribut, si nécessaire, aux valeurs des paramètres correspondants. Il ne faut surtout pas que les adresses des messages que génère l’User puissent changer. Il est donc absolument nécessaire de réserver assez de place pour ranger tous les messages (reserve (1000) devrait suffire.
Un utilisateur ne doit pas pouvoir modifier les messages qu’il a reçus, ils sont la propriété de leur émetteur.
La fonction sendMessage() est proposée aux amis de l’User, elle ajoute donc un message à la liste des messages reçus.
La fonction addMessage() sert à ajouter un message dans la liste des messages envoyés, de façon à pouvoir l’envoyer à un ami, par la suite, mais pas forcément maintenant.
Ajouter l’accesseur à l’attribut myName
Ajouter la méthodesgetSentMessage(), pour accéder au ième message envoyé. Attention ! On doit renvoyer le ième message, pas une copie de celui-ci. Attention encore, il est hors de question de pouvoir modifier ce message. C’est une référence sur un objet constant qu’il faut donc retourner.
Ajouter la méthodesgetRecievedMessage(), pour accéder au ième message reçu. Attention à nouveau ! Il est hors de question de pouvoir modifier ce message.

Ajouter les méthodes GetNbSentMessages(), GetNbFriends() et GetNbRecievedMessages().

Tester avec la fonction testUser() suivante :

    void testUser (void)
    {
        System oneSystem;
        User alfred    ("Alfred", NULL);
        User alain     ("Alain", NULL);
        User sophie    ("Sophie", NULL);
        User emmanuel  ("Emmanuel", NULL);
        User christian ("Christian", NULL);
        User petru     ("Petru", NULL);
        User marc      ("Marc", NULL);
        PrivateMessage message ("salut", & alfred);
        message.displayContent ();
        cout << endl;

        alain.addFriend (&sophie);
        alain.addFriend (&emmanuel);
        alain.addFriend (&christian);
        alain.addFriend (&petru);
        alain.addFriend (&marc);

        cout << "Alain a " << alain.getNbFriends () << " amis" << endl;
        cout << "Le troisième ami d'Alain est : " << (alain.getFriend (2))->getName () << endl;

        alfred.addMessage (message);
        alain.sendMessage (&message);
        cout << "Nombre de message envoyés par Alfred : " << alfred.getNbSentMessages ()   << endl;
        cout << "Nombre de message reçus par Alfred : " << alfred.getNbRecievedMessages () << endl;
        cout << "Nombre de message envoyés par Alain : " << alain.getNbSentMessages ()   << endl;
        cout << "Nombre de message reçus par Alain : " << alain.getNbRecievedMessages () << endl;
        alain.getRecievedMessage (0)->displayContent ();
        cout << endl;
        alfred.getSentMessage (0).displayContent ();
        cout << endl;

    } // testUser()

M2103-TP9-EXO-5-Corrigé

    class System;

    class User
    {
        string   myName;
        System * mySystem;
        vector <PrivateMessage>    mySentMessages;
        vector <PrivateMessager *> myRecievedMessages;
        vector <User *>            myFriends;

      public :
        User (const string & name, System * system = NULL) : myName (name), mySystem (system)
        {
            mySentMessages.reserve (20);
        }
        void addFriend (User * aFriend)
        {
           myFriends.push_back (aFriend);

        } // addFriend()

        const string & getName (void) const { return myName; }

        User * getFriend (unsigned i) const { return myFriends [i]; }

        const PrivateMessage & getSentMessage (unsigned i) const { return mySentMessages [i]; }

        const PrivateMessage * getRecievedMessage (unsigned i) const { return myRecievedMessages [i]; }

        System * getSystem (void) const { return mySystem; }

        unsigned getNbFriends        (void) const { return myFriends.size (); }

        unsigned getNbSentMessages   (void) const { return mySentMessages.size (); }

        unsigned getNbRecievedMessages (void) const { return myRecievedMessages.size ();  }

        void sendMessage (const PrivateMessage * message)
        {
            myRecievedMessages.push_back (message);

        } // sendMessage()

        void addMessage (const PrivateMessage & message)
        {
            mySentMessages.push_back (message);
        }

    }; // User

M2103-TP9-EXO-6

Dans l’espace de noms anonyme du fichier main.cpp déclarer la classe System, comme elle est décrite sur le schéma UML. Le constructeur sera utilisé, comme dans le TD3 (TP4) pour tester le programme.
La fonction getUser() renvoie le ième User (pas une copie).
Idem pour getPublicMessage().
Voici le constructeur :

        System (void) : myNbUsers (0), myNbMessages (0)
        {
            myUsers.reserve (1000);
            myPublicMessages.reserve (1000);
            // création des Users
            addUser ("Alfred");
            addUser ("Alain");
            addUser ("Sophie");
            addUser ("Emmanuel");
            addUser ("Christian");
            addUser ("Petru");
            addUser ("Marc");
            /* verification des Users */
            cout << myUsers.size () << endl;
            for (const User & user : myUsers)
            {
                cout << user.getName () << endl;
            }


            /* création de leurs amis * /
            for (unsigned i (0); i < myUsers.size (); ++i)
                for (unsigned j (0); j < myUsers.size () / 2; ++j)
                    myUsers [i].addFriend (&myUsers [(i + ((j * 2) + 1)) % myUsers.size ()]);

            /*  verification des amis  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a " << user.getNbFriends() << " amis : " << endl;
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                    cout << (user.getFriend (j))->getName () << endl;
            }
            /*  création et envoi des messages privés  * /
            for (User & user : myUsers)
            {
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                {
                    string content (string ("salut") + ' ' + (user.getFriend (j))->getName ());
                    PrivateMessage message (content, & user);
                    user.addMessage (message);
                    (user.getFriend (j))->sendMessage (&(user.getSentMessage (user.getNbSentMessages () - 1)));
                }
            }
            /*  vérifications des messages envoyés  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a envoyé " << user.getNbSentMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbSentMessages (); ++j)
                {
                    (user.getSentMessage (j)).displayContent();
                    cout << endl;
                }

            }
            /*  vérifications des messages reçus  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a reçu " << user.getNbRecievedMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbRecievedMessages (); ++j)
                {
                    cout << "de " << (user.getRecievedMessage (j))->getSender ()->getName () << " : ";
                    (user.getRecievedMessage (j))->displayContent();
                    cout << endl;
                }

            }
            /* création et envoie des messages publiques  * /
            string oneMessage ("a");
            for (const User & user : myUsers)
                for (unsigned i (0); i < 5; ++i)
                {
                    oneMessage += 'a';
                    (user.getSystem ())->addPublicMessage (oneMessage);
                }
            /* test de la création des messages * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << endl;
            }
            /*  création des like  * /
            for (User & user : myUsers)
                for (unsigned i (0); i < myNbMessages; ++i)
                    (user.getSystem ())->getPublicMessage (i).add ();

            /*  test des likes * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << " a " << message.getNbLikers () << " likers" << endl;
            }
/*    */

         } // System()

Dans la fonction main() il suffit de déclarer un objet System pour effectuer les tests.
Au fur et à mesure de vos mises au point, déplacer l'espace entre * et / d'un commentaire à l'autre.

M2103-TP9-EXO-6-Corrigé

    class System
    {
        unsigned                 myNbUsers;
        vector             myUsers;
        unsigned                 myNbMessages;
        vector    myPublicMessages;
      public :
        User  & getUser    (unsigned i) { return myUsers [i]; }
        PublicMessage & getPublicMessage (unsigned i) { return myPublicMessages [i]; }

        void addUser (const string & name)
        {
            myUsers.push_back (User (name, this));
            ++myNbUsers;

        } // addUsers()

        void addPublicMessage (const string & message)
        {
            myPublicMessages.push_back (message);
            ++myNbMessages;

        } // addPublicMessage())

        System (void) : myNbUsers (0), myNbMessages (0)
        {
            myUsers.reserve (1000);
            myPublicMessages.reserve (1000);
            // création des Users
            addUser ("Alfred");
            addUser ("Alain");
            addUser ("Sophie");
            addUser ("Emmanuel");
            addUser ("Christian");
            addUser ("Petru");
            addUser ("Marc");
            /* verification des Users */
            cout << myUsers.size () << endl;
            for (const User & user : myUsers)
            {
                cout << user.getName () << endl;
            }


            /* création de leurs amis * /
            for (unsigned i (0); i < myUsers.size (); ++i)
                for (unsigned j (0); j < myUsers.size () / 2; ++j)
                    myUsers [i].addFriend (&myUsers [(i + ((j * 2) + 1)) % myUsers.size ()]);

            /*  verification des amis  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a " << user.getNbFriends() << " amis : " << endl;
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                    cout << (user.getFriend (j))->getName () << endl;
            }
            /*  création et envoi des messages privés  * /
            for (User & user : myUsers)
            {
                for (unsigned j (0); j < user.getNbFriends (); ++j)
                {
                    string content (string ("salut") + ' ' + (user.getFriend (j))->getName ());
                    PrivateMessage message (content, & user);
                    user.addMessage (message);
                    (user.getFriend (j))->sendMessage (&(user.getSentMessage (user.getNbSentMessages () - 1)));
                }
            }
            /*  vérifications des messages envoyés  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a envoyé " << user.getNbSentMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbSentMessages (); ++j)
                {
                    (user.getSentMessage (j)).displayContent();
                    cout << endl;
                }

            }
            /*  vérifications des messages reçus  * /
            for (unsigned i (0); i < myUsers.size (); ++i)
            {
                User user = myUsers [i];
                cout << user.getName () << " a reçu " << user.getNbRecievedMessages() << " messages : " << endl;
                for (unsigned j (0); j < user.getNbRecievedMessages (); ++j)
                {
                    cout << "de " << (user.getRecievedMessage (j))->getSender ()->getName () << " : ";
                    (user.getRecievedMessage (j))->displayContent();
                    cout << endl;
                }

            }
            /* création et envoie des messages publiques  * /
            string oneMessage ("a");
            for (const User & user : myUsers)
                for (unsigned i (0); i < 5; ++i)
                {
                    oneMessage += 'a';
                    (user.getSystem ())->addPublicMessage (oneMessage);
                }
            /* test de la création des messages * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << endl;
            }
            /*  création des like  * /
            for (User & user : myUsers)
                for (unsigned i (0); i < myNbMessages; ++i)
                    (user.getSystem ())->getPublicMessage (i).add ();

            /*  test des likes * /
            for (const PublicMessage & message : myPublicMessages)
            {
                message.displayContent ();
                cout << " a " << message.getNbLikers () << " likers" << endl;
            }
/*    */

         } // System()
     }; // System

M2103-TP8-Exo-1

L’algorithme du quick-sort sera étudié dans le TP de structures de données consacré aux arbres binaires et à la récursivité.

Nous présentons ici un algorithme légèrement différent de la fonction Partitionnement() (l’intervalle est ici fermé) :

template <typename T>
fonction partitionnement (tab   : in_out tableau de T, 
                          first : in     entier_naturel, 
                          last  : in     entier_naturel) renvoie entier_naturel

debut
    Declarer isUp : booleen;
    isUp <- vrai;
    Declarer pivot   : entier_naturel;
    Declarer courant : entier_naturel;
    Declarer incr    : entier;
    pivot   <- first;
    courant <- last;
    incr    <- -1;
    tant_que (pivot ne_vaut_pas courant)
    faire
        si (NON isUp ET_ALORS tab [pivot] < tab [courant]
                OU_SINON
            isUp ET_ALORS tab [courant] < tab [pivot])

            permuter (tab [pivot], tab [courant]);
            permuter (pivot, courant);
            isUp <- NON isUp;
            incr <- -incr;
        fsi
        courant <- courant + incr;
    ffaire
    renvoie pivot;

fin

Rappelons l’algorithme du quick-sort (intervalle semi-ouvert) :

template <typename T>
procedure quickSort (tab   : in_out tableau de T, 
                     beg   : in     entier_naturel, 
                     end   : in     entier_naturel)
debut
    si (beg < end)
        Déclarer pos : entier_naturel;
        pos <- partitionnement (tab, beg, end - 1);

        quickSort (tab, beg,     pos);
        quickSort (tab, pos + 1, end);
    fsi
fin

Travail à effectuer

Créer le projet QuickSort.

Dans l’espace de noms anonyme du fichier QuickSort.cpp, traduire en C++ les deux algorithmes ci-dessus.

Dans ce même espace de noms anonyme, ajouter la classe générique suivante :

    template <typename T>
    class ILessThanGen
    {
      public :
        virtual ~ILessThanGen (void) {}
        virtual bool operator () (const T &, const T &) const = 0;

    }; // ILessThanGen

Ajouter les classes TriParAgeAsc et TriParNomDesc, dérivées de la classe ILessThanGen, qui permet de comparer des Pers respectivement dans l’ordre d’ages croissants et de noms décroissants.

    class Pers
    {
        string   myNom;
        unsigned myAge;
 
      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}
 
        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }
 
    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();
 
        } // display()
 
      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);
 
        }
 
    }; // Pers

Coder les fonctions génériques partitionnement() et quickSort().

Remarques

  1. En C++, le passage du tableau est inutile si la tranche du tableau à traiter est décrite par des itérateurs.
  2. Le type iterator nécessite d’être instancié pour être utilisé. Il ne le sera que lors de l’appel à quickSort(). On ne peut donc déclarer un paramètre de ce type sans que ce type soit un nouveau paramètre de généricité.
  3. La fonction de comparaison utilisée dans la procédure partitionnement() doit être passée sous la forme d’un functor.
  4. Veiller à limiter les variables locales.En particulier, lorsque c’est possible, préférer passer les itérateurs par valeur (par recopie) plutôt que d’en déclarer des instances locales.
  5. Pour des raisons purement algorithmiques, les intervalles sont semi-ouverts lorsqu’ils sont passés à la fonction quickSort() et fermés lorsqu’ils sont passés à la fonction partitionnement().

Test de la fonction quickSort().

La fonction suivante est mise à votre disposition pour tester votre programme :

    void functorSort (void)
    {
        cout << "FunctorSort : \n";
 
        typedef vector <Pers> CVPers;
 
        CVPers vPers;
 
        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));
 
        cout << "\nTri par age croissant\n\n";
 
        quickSort (vPers.begin (), vPers.end (), TriParAgeAsc ());
 
        for (const Pers & personne : vPers)
            cout << personne << '\n';
 
        cout << "\nTri par nom decroissant\n\n";
 
        quickSort (vPers.begin (), vPers.end (), TriParNomDesc ());
 
        for (const Pers & personne : vPers)
            cout << personne << '\n';
 
    } // functorSort()

Dernière remarque

Pour y stocker provisoirement la valeur du pivot, il est nécessaire de déclarer, dans le corps de la fonction, une variable locale du type de l’objet pointé.

Malheureusement, ce type n’est pas connu, il dépend du type de l’itérateur qui a servi à instancier la fonction quickSort().

Il est cependant accessible par la ligne suivante, que vous ajouterez dans la fonction :

typedef typename std::iterator_traits ::value_type Value_t;

iterator_traits est une classe générique standard dont le paramètre de généricité est un type d’itérateur, et qui exporte le type (value_type) de l’objet pointé par un itérateur de type IterType.

Elle est définie dans la bibliothèque iterator.

M2103-TP8-Exo-1-Corrigé

/**
 *
 * @file     FunctorSort.cpp
 *
 * @authors  M. Laporte, D. Mathieu
 *
 * @date     07/12/2011
 *
 * @version  V1.0
 *
 **/
#include <string>
#include <vector>
#include <algorithm>  // sort()
#include <iostream>
#include <utility>    // swap()

using namespace std;

namespace
{
    template <typename T>
    class ILessThanGen
    {
      public :
        virtual ~ILessThanGen (void) {}
        virtual bool operator () (const T &, const T &) const noexcept = 0;

    }; // ILessThanGen

    template <typename iter_t, typename LessThan>
    iter_t partitionnement (const iter_t & first, const iter_t & last,
                            const LessThan  & compar)
    {
        bool isUp (true);
        iter_t pivot   (first);
        iter_t courant (last);
        int incr (-1);
        while (pivot != courant)
        {
            if (((!isUp) && compar (*pivot, *courant)) ||
                (isUp && compar (*courant, *pivot)))
            {
                swap (*pivot, *courant);
                swap (pivot, courant);
                isUp = ! isUp;
                incr = -incr;
            }
            courant = courant + incr;
        }
        return pivot;

    } // partitionnement()

    template <typename iter_t, typename LessThan>
    void quickSort (const iter_t & beg, const iter_t & end,
                    const LessThan & compar)
    {
        if (beg < end)
        {
            iter_t pos = partitionnement (beg, end - 1, compar);
            quickSort (beg,     pos, compar);
            quickSort (pos + 1, end, compar);
        }
    } // quickSort ()

    class Pers
    {
        string   myNom;
        unsigned myAge;

      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}

        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }

    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();

        } // display()

      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);

        }

    }; // Pers

    class TriParAgeAsc : public ILessThanGen <Pers>
    {
      public :
        virtual ~TriParAgeAsc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getAge () < p2.getAge ();

        } // operator ()

    }; // TriParAgeAsc

    class TriParNomDesc : public ILessThanGen <Pers>
    {
      public :
        virtual ~TriParNomDesc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getNom () > p2.getNom ();

        } // operator ()

    }; // TriParNomDesc

    void functorSort (void)
    {
        cout << "FunctorSort : \n";

        typedef vector <Pers> CVPers;

        CVPers vPers;

        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        cout << "\nTri par age croissant\n\n";

        quickSort (vPers.begin (), vPers.end (), TriParAgeAsc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        cout << "\nTri par nom decroissant\n\n";

        quickSort (vPers.begin (), vPers.end (), TriParNomDesc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

    } // functorSort()

} // namespace

int main (void)
{
    functorSort ();

    return 0;

} // main()

M2103-TP8-Exo-2

Il existe une fonction de recherche générique standard très
puissante :

template <class InputIterator, class Predicate>
InputIterator find_if (InputIterator first, InputIterator last,
                       Predicate pred);

Comme son nom l’indique, elle recherche, entre les itérateurs first et last d’un conteneur, la position du premier élément qui satisfait une condition, représentée par le functor pred qui doit être un prédicat.

Cela signifie que la surcharge de l’opérateur () a le
profil suivant :

    bool operator () const (const T &);

Le principe en est le même que précédemment.

Travail à effectuer

Créer le projet FunctorFind.

Copier dans le fichier main.cpp le fichier de test FunctorSort.cpp FunctorSort.cpp, qui est le corrigé de l’exercice FunctorSort Functors et algorithmes de tri” ci-dessus.

/**
 *
 * @file     FunctorSort.cpp
 *
 * @authors  M. Laporte, D. Mathieu
 *
 * @date     07/12/2011
 *
 * @version  V1.0
 *
 **/
#include <string>
#include <vector>
#include <algorithm> // sort()
#include <iostream>

using namespace std;

namespace
{
    template <typename T>
    class ILessThanGen
    {
      public :
        virtual ~ILessThanGen (void) {}
        virtual bool operator () (const T &, const T &) const = 0;

    }; // ILessThanGen

    class Pers
    {
        string   myNom;
        unsigned myAge;

      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}

        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }

    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();

        } // display()

      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);

        }

    }; // Pers

    class TriParAgeAsc : public ILessThanGen <Pers>
    {
      public :
        virtual ~TriParAgeAsc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getAge () < p2.getAge ();

        } // operator ()

    }; // TriParAgeAsc

    class TriParNomDesc : public ILessThanGen <Pers>
    {
      public :
        virtual ~TriParNomDesc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getNom () > p2.getNom ();

        } // operator ()

    }; // TriParNomDesc

    void functorSort (void)
    {
        cout << "FunctorSort : \n";

        typedef vector <Pers> CVPers;

        CVPers vPers;

        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));

        cout << "\nTri par age croissant\n\n";

        sort (vPers.begin (), vPers.end (), TriParAgeAsc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        cout << "\nTri par nom decroissant\n\n";

        sort (vPers.begin (), vPers.end (), TriParNomDesc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

    } // functorSort()

} // namespace

int main (void)
{
    functorSort ();

    return 0;

} // main()

Remplacez la classe ILessThanGen par IPredicatGen et supprimez tout ce qui concerne les tris.

Dérivez publiquement cette classe en SelParTrancheAge, qui possède :

  • les deux données-membres myAgeMin et myAgeMax,
  • un constructeur qui permet de les initialiser,
  • un destructeur virtuel,
  • la surcharge de l’opérateur (), qui renvoie true lorsque l’âge de l’élément qui lui est passé en paramètre est dans l’intervalle [myAgeMin, myAgeMax].

Testez en utilisant et en complétant la fonction suivante :

    void functorFind (void)
    {
        cout << "FunctorFind : \n";

        typedef vector <Pers> CVPers;
        CVPers vPers;

        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        CVPers::const_iterator pos;

        cout << "\nRecherche sur  43 <= age <= 75 : ";

        pos = find_if (vPers.begin (), vPers.end (), // a completer
        if (vPers.end () ==pos)
            cout << "Aucun element ne correspond a ce critere\n";
        else
            cout << *pos << '\n';

        cout << "\nRecherche sur  43 <= age <= 45 : ";

        pos = find_if (vPers.begin (), vPers.end (), // a completer
        if (vPers.end () == pos)
            cout << "Aucun element ne correspond a ce critere\n";
        else
            cout << *pos << '\n';

        cout << '\n';

    } // functorFind()

Lorsque vous obtenez des résultats conformes à l’affichage attendu ci-dessous,

FunctorFind : 
21 - Charlotte
12 - Alfred
42 - Jean
11 - Noemie
99 - Berthe
29 - Agathe
42 - Sylvain
75 - Pierre

Recherche sur  43 <= age <= 75 : 75 - Pierre

Recherche sur  43 <= age <= 45 : Aucun element ne correspond a ce critere
  • dérivez publiquement la classe IPredicatGen en SelParNomMin, qui possède :
    • la donnée-membre myNomMin,
    • un constructeur qui permet de l’initialiser,
    • un destructeur virtuel,
    • la surcharge de l’opérateur (), qui renvoie true lorsque le nom de l’élément qui lui est passé
      en paramètre est supérieur à celui de myNomMin.
  • ajoutez à la fonction functorFind() la séquence suivante :
            cout << "\nRecherche sur nom > Noemie : ";
    
            pos = find_if (vPers.begin (),  vPers.end (), // a completer
    
            if (vPers.end () == pos)
                cout  << "Aucun element ne correspond a ce critere\n";
            else
                cout << *pos << '\n';
    
            cout  << "\nRecherche sur nom > alfred : ";
    
            pos = find_if (vPers.begin (),  vPers.end (), // a completer
    
            if (vPers.end () == pos)
                cout  << "Aucun element ne correspond a ce critere\n";
            else
                cout << *pos << '\n';
    

Vous devez obtenir des résultats conformes à la deuxième partie de l’affichage attendu ci-dessous.

Lorsque les affichages sont corrects, une dernière modification est proposée : on remarque que la classe IPredicatGen manque encore de généralité, car le résultat est toujours un booléen (c’est pour cela que c’est un prédicat).

En réalité, dans certaines applications, on peut supposer avoir besoin de functors à un seul paramètre qui renvoient des types différents du type booléen.

Il suffit d’ajouter en second paramètre de généricité le type de retour : cela s’appelle une fonction-objet unaire ou unary function.

Ajoutez la classe IUnaryFunction, copie de IPredicatGen, à laquelle est ajouté le second paramètre de généricité TRes représentant le type de retour de la fonction.

Modifiez les deux classes SelParTrancheAge et SelParNomMin, en en faisant des UnaryFunction‘s et tester à nouveau.

résultats supplémentaires attendus :

Recherche sur nom > Noemie : 42 - Sylvain

Recherche sur nom > alfred : Aucun element ne correspond a ce critere

M2103-TP8-Exo-2-Corrigé

/**
 *
 * @file     FunctorFind.cpp
 *
 * @authors  M. Laporte, D. Mathieu
 *
 * @date     07/12/2011
 *
 * @version  V1.0
 *
 **/
#include <string>
#include <vector>
#include <algorithm>  // sort()
#include <iostream>

using namespace std;

namespace
{
    template <typename T>
    class IPredicatGen
    {
      public :
        virtual ~IPredicatGen (void) {}
        virtual bool operator () (const T &) const = 0;

    }; // IPredicatGen

    template <typename T, typename TRes>
    class IUnaryFunction
    {
      public :
        virtual ~IUnaryFunction (void) {}
        virtual TRes operator () (const T &) const = 0;

    }; // IUnaryFunction

    class Pers
    {
        string   myNom;
        unsigned myAge;

      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}

        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }

    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();

        } // display()

      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);

        }

    }; // Pers

    class SelParTrancheAge : public IPredicatGen <Pers>
//  class SelParTrancheAge : public IUnaryFunction <Pers, bool>
    {
        unsigned myAgeMin;
        unsigned myAgeMax;
      public :
        SelParTrancheAge (unsigned ageMin, unsigned ageMax) : myAgeMin (ageMin), myAgeMax (ageMax) {}
        virtual ~SelParTrancheAge (void) noexcept {}

        virtual bool operator () (const Pers & p) const
        {
            return myAgeMin <= p.getAge () && p.getAge () <= myAgeMax;

        } // operator ()

    }; // SelParTrancheAge

    class SelParNomMin : public IPredicatGen <Pers>
//  class SelParNomMin : public IUnaryFunction <Pers, bool> 
    {
        string myNomMin;
      public :
        SelParNomMin (const string & nomMin) : myNomMin (nomMin) {}
        virtual ~SelParNomMin (void) noexcept {}

        virtual bool operator () (const Pers & p) const
        {
            return myNomMin < p.getNom ();

        } // operator ()

    }; // SelParNomMin

    void functorFind (void)
    {
        cout << "FunctorFind : \n";

        typedef vector <Pers> CVPers;
        CVPers vPers;

        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        CVPers::const_iterator pos;

        cout << "\nRecherche sur  43 <= age <= 75 : ";

        pos = find_if (vPers.begin (), vPers.end (), SelParTrancheAge (43, 75));// a completer
        if (vPers.end () == pos)
            cout << "Aucun element ne correspond a ce critere\n";
        else
            cout << *pos << '\n';

        cout << "\nRecherche sur  43 <= age <= 45 : ";

        pos = find_if (vPers.begin (), vPers.end (), SelParTrancheAge (43, 45)); // a completer
        if (vPers.end () == pos)
            cout << "Aucun element ne correspond a ce critere\n";
        else
            cout << *pos << '\n';

        cout << '\n';

        cout << "\nRecherche sur nom > Noemie : ";

        pos = find_if (vPers.begin (),  vPers.end (), SelParNomMin ("Noemie"));// a completer

        if (vPers.end () == pos)
            cout  << "Aucun element ne correspond a ce critere\n";
        else
            cout << *pos << '\n';

        cout  << "\nRecherche sur nom > alfred : ";

        pos = find_if (vPers.begin (),  vPers.end (), SelParNomMin ("alfred"));// a completer

        if (vPers.end () == pos)
            cout  << "Aucun element ne correspond a ce critere\n";
        else
            cout << *pos << '\n';


    } // functorFind()

} // namespace

int main (void)
{
    functorFind ();

    return 0;

} // main()

M2103-TP8-Exo-3

Remarque préliminaire : cet exercice ne peut être fait qu’après les exercices précédents sur les functors.

Outre les fonctions-objets unaires, la bibliothèque standard C++ utilise des fonctions-objets binaires, ou binary functors, qui possèdent un paramètre supplémentaire, dont le type est lui aussi générique.

En revanche, elle n’utilise aucune fonction-objet à plus de deux paramètres.

C’est ce que nous aurions pu utiliser dans l’exercice Functor-comparateur abstrait générique qui n’est pas autre chose qu’un prédicat à deux paramètres de même type.

Nous allons donc le généraliser dans cet exercice.

D’autre part, nous avons montré que, selon les fonctions standard utilisées, il est nécessaire de développer pour une même classe et pour un même critère de comparaison à la fois un functor unaire et un functor binaire.

Par exemple, pour la relation d’ordre “age croissant” de la classe Pers, un functor binaire TriParAgeAsc est nécessaire à la fonction standard générique sort(), et un functor unaire SelParTrancheAge est nécessaire à la fonction standard générique find_if().

Nous allons montrer comment un functor binaire peut être simplement transformé en functor unaire sans réécriture.

Travail à effectuer

Créez le projet Adaptor.

Tri

Dans votr main.cpp copier le fichier de test :

/**
 *
 * @file     FunctorSort.cpp
 *
 * @authors  M. Laporte, D. Mathieu
 *
 * @date     07/12/2011
 *
 * @version  V1.0
 *
 **/
#include <string>
#include <vector>
#include <algorithm>  // sort()
#include <iostream>

using namespace std;

namespace
{
    template <typename T>
    class ILessThanGen
    {
      public :
        virtual ~ILessThanGen (void) {}
        virtual bool operator () (const T &, const T &) const = 0;

    }; // ILessThanGen

    class Pers
    {
        string   myNom;
        unsigned myAge;

      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}

        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }

    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();

        } // display()

      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);

        }

    }; // Pers

    class TriParAgeAsc : public ILessThanGen <Pers>
    {
      public :
        virtual ~TriParAgeAsc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getAge () < p2.getAge ();

        } // operator ()

    }; // TriParAgeAsc

    class TriParNomDesc : public ILessThanGen <Pers>
    {
      public :
        virtual ~TriParNomDesc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getNom () > p2.getNom ();

        } // operator ()

    }; // TriParNomDesc

    void functorSort (void)
    {
        cout << "FunctorSort : \n";

        typedef vector <Pers> CVPers;

        CVPers vPers;

        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));

        cout << "\nTri par age croissant\n\n";

        sort (vPers.begin (), vPers.end (), TriParAgeAsc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        cout << "\nTri par nom decroissant\n\n";

        sort (vPers.begin (), vPers.end (), TriParNomDesc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

    } // functorSort()

} // namespace

int main (void)
{
    functorSort ();

    return 0;

} // main()

, qui est le corrigé de l’exercice Functors et algorithmes de tri.

Remplacez la classe ILessThanGen par la classe IBinaryFunction à trois paramètres de généricité (les types des deux paramètres et de la valeur de retour), selon le modèle suivant :

    template <typename T1, typename T2, typename TRes>
    class IBinaryFunction
    {
      public :
        typedef T1   first_argument_type;
        typedef T2   second_argument_type;
        typedef TRes result_type;

        ...

Attention : les identificateurs des types sont imposés par bind2nd(),

Modifiez en conséquence les classes TriParAgeAsc et TriParNomDesc.

Le profil d’une fonction de tri comme par exemple :

    template <typename Iter_t> 
    void selectSort (Iter_t deb, Iter_t fin, const LessThan & IsInf);

devrait être modifié en :

    template <typename Iter_t, typename T>
    void selectSort (Iter_t deb, Iter_t fin,
                    const IBinaryFunction <T, T, bool> & isInf);
</t,>

En revanche, l’utilisation de la fonction sort() ne nécessite aucune modification.

Compilez et testez.

Recherche

Les functors binaires que nous avons écrits devraient pouvoir être utilisés pour faire des recherches.

Par exemple, le prédicat TriParAgeAsc renvoie true lorsque l’âge du premier paramètre est inférieur ou égal à celui du second paramètre.

Nous souhaitons donc l’utiliser pour rechercher le premier élément dont l’âge est <= à un âge donné, par exemple 40, quel que soit le nom de ce dernier.

Il suffit donc de comparer successivement tous les éléments du conteneur à la constante Pers ("", 40).

Malheureusement, la fonction find_if() déjà étudiée précédemment, nécessite un functor unaire.

La bibliothèque fournit la fonction bind2nd (appelée un helper), qui renvoie un functor unaire à partir :

  • de son premier paramètre qui doit être un functor binaire (nous utiliserons ici une instance de la classe TriParAgeAsc),
  • de son second paramètre qui doit être un objet de même type que le second paramètre de l’opérateur () du functor binaire (ici un Pers, second paramètre de l’opérateur () de TriParAgeAsc).

Très peu de modifications sont nécessaires :

  • ajoutez le fichier inclus functional dans lequel est déclaré le helper bind2nd(),
  • ajoutez en fin de la fonction Adaptor() (functorSort ()) le code suivant à compléter :
            cout << "\nRecherche de la premiere personne d'age <= 40 : ";
    
            CVPers::const_iterator pos =
                find_if (vPers.begin (), vPers.end (),  // a completer
    
            if (vPers.end () == pos)
                cout << "Aucun element correspondant\n";
            else
                cout << *pos << '\n';
    
            cout << "\nRecherche de la premiere personne d'age<= 4 : ";
    
            pos = find_if (vPers.begin (), vPers.end (), // a completer
    
            if (vPers.end () == pos)
                cout << "Aucun element correspondant\n";
            else
                cout << *pos << '\n';
    

M2103-TP8-Exo-3-Corrigé

/**
 *
 * @file     Adaptor.cpp
 *
 * @authors  M. Laporte, D. Mathieu
 *
 * @date     07/12/2011
 *
 * @version  V1.0
 *
 **/
#include <string>
#include <vector>
#include <algorithm>  // sort()
#include <iostream>
#include <functional>

using namespace std;

namespace
{
    template <typename T1, typename T2, typename TRes>
    class IBinaryFunction
    {
      public :
        typedef T1   first_argument_type;
        typedef T2   second_argument_type;
        typedef TRes result_type;

        virtual ~IBinaryFunction (void) {}
        virtual TRes operator () (const T1 &, const T2 &) const = 0;

    }; // IBinaryFunction

    class Pers
    {
        string   myNom;
        unsigned myAge;

      public :
        Pers (const string & Nom, unsigned Age)
            : myNom (Nom), myAge (Age) {}

        const string & getNom (void) const noexcept { return myNom; }
        unsigned       getAge (void) const noexcept { return myAge; }

    private :
        ostream & display (ostream & os)  const
        {
            return os << getAge () << " - " << getNom ();

        } // display()

      public :
        friend ostream & operator << (ostream & os, const Pers & p)
        {
            return p.display (os);

        }

    }; // Pers

    class TriParAgeAsc : public IBinaryFunction <Pers, Pers, bool>
    {
      public :
        virtual ~TriParAgeAsc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getAge () < p2.getAge ();

        } // operator ()

    }; // TriParAgeAsc

    class TriParNomDesc : public IBinaryFunction <Pers, Pers, bool>
    {
      public :
        virtual ~TriParNomDesc (void) noexcept {}

        virtual bool operator () (const Pers & p1, const Pers & p2)
                        const noexcept
        {
            return p1.getNom () > p2.getNom ();

        } // operator ()

    }; // TriParNomDesc

    void adaptor (void)
    {
        cout << "FunctorSort : \n";

        typedef vector <Pers> CVPers;

        CVPers vPers;

        vPers.push_back ( Pers ("Charlotte", 21));
        vPers.push_back ( Pers ("Alfred",    12));
        vPers.push_back ( Pers ("Jean",      42));
        vPers.push_back ( Pers ("Noemie",    11));
        vPers.push_back ( Pers ("Berthe",    99));
        vPers.push_back ( Pers ("Agathe",    29));
        vPers.push_back ( Pers ("Sylvain",   42));
        vPers.push_back ( Pers ("Pierre",    75));

        cout << "\nTri par age croissant\n\n";

        sort (vPers.begin (), vPers.end (), TriParAgeAsc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';

        cout << "\nTri par nom decroissant\n\n";

        sort (vPers.begin (), vPers.end (), TriParNomDesc ());

        for (const Pers & personne : vPers)
            cout << personne << '\n';
        cout << "\nRecherche de la premiere personne d'age <= 40 : ";

        CVPers::const_iterator pos = find_if (vPers.begin (), vPers.end (),
                                              bind2nd (TriParAgeAsc (), Pers (" ",40)));// a completer

        if (vPers.end () == pos)
            cout << "Aucun element correspondant\n";
        else
            cout << *pos << '\n';

        cout << "\nRecherche de la premiere personne d'age<= 4 : ";

        pos = find_if (vPers.begin (), vPers.end (),
                       bind2nd (TriParAgeAsc (), Pers (" ", 4)));// a completer

        if (vPers.end () == pos)
            cout << "Aucun element correspondant\n";
        else
            cout << *pos << '\n';
    } // adaptor()

} // namespace

int main (void)
{
    adaptor ();

    return 0;

} // main()