[C++] TP 8

First publication date: 2020/06/05

In this practical work, we will go thru the basic handling of containers from the standard library. In a second part, you will see tricky use of template writing.

Lecture examples

Dynamic array

Here is an example to compile and to run

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

int main (int, char **) {
  std::vector<int> v;  
  int input;
  
  while (std::cin >> input)
    v.push_back (input);  
 
  std::sort(v.begin(), v.end());

  std::copy (v.begin(), v.end(), 
    std::ostream_iterator<int> (std::cout, "\n"));
  
  return 0;
}

The version with ostream_iterator is a little hard. Are you able to display the input in an easier way ?

a vector is a dynamic array whose size is given by size(). Each element can be accessed with operator[]
a vector is a basic container with a begin iterator begin() and a end iterator end()
Since C++2011, an extended version of for is available

for (int& e : v) {
   // to do 
   // you can even forget the int type with a special keyword
   // but it is another story...
}

The stack

int main(int, char **) {
  std::stack<int> is;
  std::stack<double, std::vector<double> > ds;

  for (int i = 0; i < 100; ++i)
    is.push(i);

  while (!is.empty()) {
     std::cout << is.top() << std::endl;
     ds.push((double)is.top()*is.top());
     is.pop();
  }

  return 0;
}

File à priorité

Reprenez le code suivant en ajoutant les opérateurs qui manquent sur la classe ZZ

l'operator<() pour comparer des éléments (ordre)
l'operator<<() pour afficher un élément sur le flux donné

class ZZ {
  string nom, prenom;
  double note;
  // …
};

Pour utiliser la classe priority_queue, il faut le bon espace de nommage mais surtout le bon fichier d'entête !

Votre bible : https://cppreference.com

typedef std::vector<ZZ>  vzz;
// OU en C++ 2011
// using vzz = std::vector<ZZ> ;

vzz zz;

// il faut mettre des elements
// zz.push_back(ZZ(...));

priority_queue<ZZ> tri;

for(vzz::iterator it = zz.begin(); 
    it!=zz.end(); ++it)
 tri.push(*it);

while(!tri.empty()) {
   cout << tri.top() << " ";
   tri.pop();
}

Vecteur et pointeurs

Instancier un vecteur de ZZ * et allouer dynamiquement quelques ZZ à ajouter à ce vecteur
Vérifier ce qu'il se passe avec valgrind
Appeler la méthode clear() du conteneur. Vérifier ce qu'il se passe avec valgrind
Faire ce qu'il faut pour qu'il n'y ait pas de fuite mémoire. Contrôler avec valgrind.

Si vous voulez réutiliser le code précédent pour cet exercice, la file a priorité contient toujours des ZZ et non des pointeurs, ajouter un élément ne se fait plus par *it!
Comparer des pointeurs, c'est toujours possible, c'est une comparaison d'index. On veut comparer des ZZ suivant l'opérateur que vous avez défini

Tableau associatif

Je vous redonne les morceaux de code concernant le tableau associatif : définition, recherche et affichage.

typedef std::map<string, string> mss;
// OU en C++ 2011
// using mss = std::map<string, string> ;  
mss m;

m.insert(pair<string,string>("loic", "405042"));
m.insert(make_pair("pierre", "405033"));
m.insert(make_pair("SOS C++ 24/7", "407662"));
m["secours"]  = "42";

mss::iterator it = m.find("loic");
if (it==m.end()) cout << "et moi ?";

const string& first(const pair<string,string>& p) { return p.first; }

int main(int, char**) {
 map<string, string> liste;

 map<string, string>::const_iterator it 
      = liste.begin();
 while(it!=liste.end()) {  
    cout << it->first  << " " 
         << it->second << endl;
    ++it;
 }

 transform(liste.begin(), liste.end(), 
   ostream_iterator<string>(cout, " "), first);
  
 return 0;
}

Pouvez-vous écrire un petit programme :

qui essaie l'algorithme copy() sur la map ?
qui utilise une fonction paire() sur le modèle de first() pour afficher le contenu de la map ?
qui lit les entrées de l'annuaire à partir d'un fichier texte (flux) dont le nom sera codé en dur dans le programme
qui affiche la liste des entrées sur la sortie standard s'il n'y a aucun paramètre donné en ligne de commande
qui affiche l'entrée trouvée ou un message "non trouvé" si l'utilisateur donne un argument en ligne de commande
Est-ce que vous pouvez créer l'annuaire inversé ?

Fil rouge ...

Vous pouvez maintenant utiliser un conteneur de la bibliothèque standard pour la classe Groupe

Exercice : un dictionnaire

Nous voulons coder un programme permettant de gérer un dictionnaire : une liste de lettres avec la liste de mots commençant par cette lettre. Nous vous proposons le diagramme UML suivant :

Manipulation d'une liste chaînée

Nous voulons fournir une classe ListeMotsTries qui contient des listes de mots (std::string) triés. C'est une simple encapsulation de std::list<std::string>. Les méthodes seront donc très rapides à écrire et on essaiera d'utiliser le plus possible la bibliothèque standard.

Écrire la déclaration de la classe avec son attribut.
Ajouter une méthode ajouterMot(const string&) qui ajoute un mot à cette liste. La liste sera triée après chaque ajout.
Ajouter une méthode getNbMots() qui retourne le nombre de mots de la liste. Vérifier que l'ajout de mots incrémente bien cette valeur.
Écrire une méthode afficher(ostream & = cout) qui permet d'afficher sur le flux spécifié le contenu de la liste. Vous pouvez :

Parcourir cette liste avec un itérateur et afficher dans le flux
Utiliser l'algorithme copy() et ostream_iterator

Surcharger l'opérateur de redirection <<
Ajouter une méthode debut() qui retournera un itérateur constant sur le premier élément de la liste. Le type const_iterator sera défini comme un typedef ou un using du type correspondant de la chaîne de caractères et dans la classe ListeMotsTries.
Ajouter une méthode fin() qui retournera un itérateur constant de fin de liste
Ajouter une méthode inserer() qui permet d'insérer une liste de mots triés dans une autre liste de mots triés en prenant des itérateurs constants sur la liste à insérer.

Voici un extrait de fichier de tests :

Catch

TEST_CASE ( "ListeMT1" ) {
  ListeMotsTries liste;

  REQUIRE( 0 == liste.getNbMots() );
  liste.ajouterMot("inserer");
  REQUIRE( 1 == liste.getNbMots() );
  liste.ajouterMot("effacer");
  REQUIRE( 2 == liste.getNbMots() );
  liste.ajouterMot("ajout");
  REQUIRE( 3 == liste.getNbMots() );


  ListeMotsTries::const_iterator it = liste.debut();

  REQUIRE( *it == "ajout" ); 
  ++it;
  REQUIRE( *it == "effacer" );
  ++it;
  REQUIRE( *it ==  "inserer" );
  ++it;
  REQUIRE( it == liste.fin() );

  liste.enleverMot("effacer");
  REQUIRE( 2 == liste.getNbMots() );
  liste.enleverMot("inserer");
  REQUIRE( 1 == liste.getNbMots() );
  liste.enleverMot("ajout");
  REQUIRE( 0 == liste.getNbMots() );

  REQUIRE( liste.debut() == liste.fin() );
}

TEST_CASE ( "ListeMT2" ) {
  ListeMotsTries liste1, liste2;

  liste1.ajouterMot("essai 1 a");
  liste1.ajouterMot("essai 1 b");
  liste2.inserer(liste1.debut(), liste1.fin());

  ListeMotsTries liste3;
  liste3.ajouterMot("essai 1 b");
  liste3.ajouterMot("essai 2 a");
  liste3.ajouterMot("essai 2 c");
  liste2.inserer(liste3.debut(), liste3.fin());
}

Google Test

TEST ( TestListeMT, LMT1 ) {
  ListeMotsTries liste;

  EXPECT_EQ( liste.getNbMots(), 0 );
  liste.ajouterMot("inserer");
  EXPECT_EQ( liste.getNbMots(), 1);
  liste.ajouterMot("effacer");
  EXPECT_EQ( liste.getNbMots(), 2 );
  liste.ajouterMot("ajout");
  EXPECT_EQ( liste.getNbMots(), 3 );


  ListeMotsTries::const_iterator it = liste.debut();

  EXPECT_STREQ(it->c_str(), "ajout");
  ++it;
  EXPECT_STREQ(it->c_str(), "effacer");
  ++it;
  EXPECT_STREQ(it->c_str(), "inserer");
  ++it;
  EXPECT_EQ(it, liste.fin());

  liste.enleverMot("effacer");
  EXPECT_EQ(liste.getNbMots(), 2);
  liste.enleverMot("inserer");
  EXPECT_EQ(liste.getNbMots(), 1);
  liste.enleverMot("ajout");
  EXPECT_EQ(liste.getNbMots(), 0);

  EXPECT_EQ(liste.debut(), liste.fin());
}

TEST ( TestListeMT, LMT2 ) {
  ListeMotsTries liste1, liste2;

  liste1.ajouterMot("essai 1 a");
  liste1.ajouterMot("essai 1 b");
  liste2.inserer(liste1.debut(), liste1.fin());

  ListeMotsTries liste3;
  liste3.ajouterMot("essai 1 b");
  liste3.ajouterMot("essai 2 a");
  liste3.ajouterMot("essai 2 c");
  liste2.inserer(liste3.debut(), liste3.fin());
}

Manipulation d'un tableau associatif

La classe Dictionnaire est composée d’une instance de std::map<char,ListeMotsTries>. Le premier champ est la clé, il s’agit de la première lettre d’un mot. La valeur qui lui est associée est une liste de mots (instance de ListeMotsTries) qui stocke par ordre alphabétique tous les mots commençant par la dite lettre.

Implémentez les méthodes de base telles que ajouterMot ou supprimerMot.
La méthode rechercherMots() renvoie la liste de tous les mots commençant par le motif qu’on lui passe en paramètre. L’une des méthodes compare de la classe std::string vous aidera à fournir cette fonctionnalité.

Vérifiez à présent le bon fonctionnement de votre dictionnaire :

Testez la recherche d’un mot qui n’existe pas.
Vérifiez que vous avez compris la gestion d’une map en proposant les fonctions nécessaires pour utiliser cette surcharge : std::ostream & operator<<( std ::ostream & inO, const Dictionnaire& inD );

Illustrations de problèmes liés l'utilisation des templates et leur solution

Regardez le code ci-dessous, c'est celui qui va nous permettre d'illustrer plusieurs "astuces" à connaître pour utiliser les templates... Cela ne s'invente pas, faut le savoir et "pis c'est tout" !

template<typename T>
class Stats {
   vector<T> data;
   T sum;
   double moy;
   double ecart;

 public:
   Stats():data(10), moy(.0) {}

   void push_back(const T& t) { data.push_back(t);}
   void compute() { 
   }
   void display(ostream& o = cout) const {
   }
};

int main(int, char**) {
  Stats<int> is;
  
  is.push_back(3);
  is.push_back(4);
  is.push_back(2);
  is.compute();
  is.display();

  return 0;
}

typename (!important)

Le code est incomplet ! Est-ce que vous pouvez écrire au moins une des deux méthodes vides en parcourant le conteneur avec un const_iterator?

Pour que le code soit accepté par le compilateur, il faut utiliser typename dans un deuxième usage : préciser au compilateur que ce que vous déclarez existe réellement et est un type (car en l'état, le compilateur n'a aucun moyen de le savoir)

Héritage

Écrire un code qui instancie la classe Fille sur un type simple (ou un type pour lequel il y a surcharge de l'opérateur << et *). Vérifier également que la méthode f() est appelable.

template<class T>
class Mere {
 protected:
  T a;
 public:
  Mere(T t):a(t) {}
  void f() { std::cout << a ; }
};

template<class T>
class Fille : public Mere<T> {
 public:
  Fille(T t): Mere<T>(t) {}
  void m() { 
       a = a*a; 
       f();
     }
};

Que faut-il faire pour que cela compile ?

Cela a été vu en cours !