TD 12 C++: template<>

Rappels


Exercice 1: Fonction générique

  1. Implémentez dans un fichier 1.1.h une fonction générique void Print(x) qui prend un argument x et l'imprime (avec cout << x). L'argument x pourra avoir n'importe quel type.
    Notez bien que je demande un .h et pas de .cc! C'est dû à l'utilisation de template: dans un projet C++ classique, on implémente les fonctions génériques dans les .h, pour qu'elle soient utilisables par les autres fichiers (explication au tableau si vous voulez).

    Testez votre code:
    rm 1.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td12/1.tar.gz
    tar xf 1.tar.gz
    make 1.1
    RENDU: 1.1.h

  2. Copiez 1.1.h dans 1.2.h et spécialisez la fonction Print pour qu'elle ait un comportement particulier quand x est un int: elle devra alors afficher "int(x)" (sans les guillemets, et en remplaçant le "x" par sa valeur).
    Vous utiliserez les template, et pas la surcharge!

    Test: make 1.2
    RENDU: 1.2.h

  3. Dans une copie 1.3.h, continuez à spécialiser Print() pour que:
    Test: make 1.3
    RENDU: 1.3.h


Exercice 2: Classe générique

  1. En suivant le modèle suivant, qui serait valide étant donné une classe donnée SomeClass, implémentez dans un fichier 2.1.h une classe générique Track qui encapsulera une classe quelquonque*.
    Gardez le même texte affiché dans cerr: les auto-tests s'en servent pour détécter que tout marche bien.
    class Track : public SomeClass {
     public:
      Track() : SomeClass() {
        cerr << "Default-Constructing @" << this << "\n";
      }
    
      Track(const SomeClass& obj) : SomeClass(obj) {
        cerr << "Copy-Constructing @" << this << "\n";
      }
    
      ~Track() {
        cerr << "Destructing @" << this << "\n";
      }
    };
    Testez votre code:
    rm 2.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td12/2.tar.gz
    tar xf 2.tar.gz
    make 2.1
    RENDU: 2.1.h

  2. Copiez votre fichier dans 2.2.h et ajoutez deux fonctions "accesseurs":
    Test: make 2.2
    RENDU: 2.2.h


Exercice 3: Triplet<>

  1. Dans un fichier 3.1.h, implémentez une classe générique Triplet qui implémente un triplet d'objet quelquonques*.
    Le code qui l'utilisera pourra ressembler à ça:
    const double x = 3.0;
    SomeClass my_class;
    Triplet<int, SomeClass, double> t(42, my_class, x);
    cout << "Triplet: " << t.first << "; " << t.second << "; " << t.third << "\n";
    t.third /= 2.0;
    cout << t.third << "\n";
    Cahier des charges:
    Test:
    rm 3.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td12/3.tar.gz
    tar xf 3.tar.gz
    make 3.1
    RENDU: 3.1.h

  2. Dans une copie 3.2.h, ajoutez un constructeur par défaut (qui construira par défaut chaque objet du triplet).

    Test: make 3.2
    RENDU: 3.2.h

  3. Dans une copie 3.3.h, ajoutez un operateur < qui fera la comparaison stricte dans l'ordre lexicographique:
    Test: make 3.3
    RENDU: 3.3.h

  4. Idem dans un 3.4.h mais faites en sorte que votre code n'utilise que l'opérateur < sur les classes sous-jacentes.
    Test: make 3.4
    RENDU: 3.4.h


Exercice 4: Cardinality Counter

  1. Complétez le fichier 4.1.h, en l'implémentant!
    // Generic cardinality counter for hashable objects.
    // It counts how many times a given object was inserted, all
    // in constant time.
    template<class T>
    class CardinalityCounter {
     public:
      // Adds an object once, i.e. increments its cardinality count.
      void Add(const T& t) {
        // TODO
      }
    
      // Returns the current cardinality cound of object t, i.e. the number of
      // times Add(t) was called. Can be 0 if t was never added.
      int NumOccurences(const T& t) const {
        // TODO
      }
    
     private:
      // TODO
    };
    Testez votre code:
    rm 4.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td12/4.tar.gz
    tar xf 4.tar.gz
    make 4.1
    RENDU: 4.1.h

  2. Dans une copie 4.2.h, ajoutez une fonction int Size() qui renvoie le nombre d'élément distincts insérés jusque-là.

    Test: make 4.2
    RENDU: 4.2.h

  3. Dans une copie 4.3.h, ajoutez une fonction const T& MostFrequent() qui presupposera que Size() > 0 et qui renverra l'élément dont la cardinalité est la plus grande (si plusieurs éléments sont ex aequo, retournez n'importe lequel).
    Débrouillez-vous pour que ça marche en temps constant O(1), les autres opérations devant également rester en temps constant.

    Test: make 4.3
    RENDU: 4.3.h

  4. (*) Dans une copie 4.4.h, ajoutez une fonction Remove() qui enlève une occurence d'un objet donné en argument. Si l'objet n'était pas présent, elle ne fait rien.
    Attention:
    Test: make 4.4
    RENDU: 4.4.h

  5. (**) : Modifiez la structure de données pour garantir une complexité O(log(N)) voire O(1) pour toutes les operations, dans le pire cas, même Remove().
    Pour garantir le max de points, obtenez la complexité pire cas en O(1).
    Indice: dans un conteneur de type set, unordered_set, map ou unordered_map, les références (donc également les pointeurs) vers des éléments du set ou du map (clé et/ou valeur) restent valides tant qu'on n'enlève pas l'élément! En d'autres termes, une fois inséré, les clés (et/ou leur valeur associée) gardent une adresse mémoire constante tant qu'il ne sont pas retirés. Le code suivant marche bien, par exemple:
    std::map my_map;
    my_map[5] = 4.567;
    double* value_of_5 = &(my_map[5]);
    int* key_of_5 = &(my_map.find(5)->first);
    my_map[4] = 3;
    my_map[2] = 8;
    my_map.erase(4);
    cout << *key_of_5;  // Prints "5".
    cout << *value_of_5;  // Prints "4.567".
    my_map[5] = 9.8;
    cout << *key_of_5;  // Prints "5".
    cout << *value_of_5;  // Prints "9.8".
    
    Test: make 4.5
    RENDU: 4.5.h


*: presque quelquonque: l'objet en question devra avoir un constructeur par copie et par défaut.