6. TP de C++ n°6 Les conteneurs associatifs

6.1.Rappels sur les conteneurs associatifs

Les conteneurs associatifs reposent sur la notion de clef.

Il y a 2 grands types de conteneurs associatifs. Les ensembles (set) et les maps (map). Dans le premier, la valeur contenue et la clef sont identiques, dans le second, on stocke des paires, la premiere valeur (first) étant la clef, la seconde (second) la valeur réellement utilisée.

6.2 Utilisation des ensembles

6.2.1 Description

Au cours de la première partie de ce TP, nous allons manipuler les ensembles simples (c'est à dire, les ensembles où l'on n'admet pas plus d'une copie de chaque élément) et, en particulier, les opérations ensemblistes.

En effet, la STL fournit des primitives permettant de réaliser les opérations ensemblistes les plus courantes (union, intersection etc.) ; leur nom est du type set_operation.

Ces opérations nécessitent 5 itérateurs (attention à l'erreur dans le poly !) :

6.2.2 Travail à réaliser

  1. Créer deux ensembles se recouvrant :
  2. Utilisez la primitive d'union en :
  3. Réalisez la même opérations avec l'intersection et profitez en pour essayer la primitive de test d'inclusion (attention à l'ordre des paramètres dans
  4. Essayez les deux opérations de différence et de différence symmétrique sur ce même exemple.

6.2.3 Solution

#include "Fibonnacci.hxx"
#include <set>
#include <deque>
#include <iostream>
#include <algorithm>
 
class GenerateurImpairs
{
  private:
    int courant;
  public:
    explicit GenerateurImpairs(int lePremier=1) : 
      courant(lePremier-2)
    {
    }
    int operator()(void)
    {
      courant+=2;
      return courant;
    }
};
 
typedef set<int>   EnsInt;
typedef deque<int> DeqInt;
 
ostream& operator<<(ostream &a, const EnsInt &collec)
{
  copy(collec.begin(),collec.end(),ostream_iterator<int>(a," "));
  a << endl;
  return a;
}
 
int main(int,char **)
{
  DeqInt dq(10);
 
  generate(dq.begin(),dq.end(),GenerateurImpairs());
 
  // Construction d'un ensemble a partir d'une sequence preexistente 
  EnsInt ensImpairs(dq.begin(),dq.end());
 
  cout << ensImpairs;
  
  dq.resize(0);
 
  // Construction d'un ensemble a l'aide de la methode insert
  EnsInt     ensFibo;
  Fibonnacci fibo;
  
  for (int i=0;i<10;i++)
    ensFibo.insert(fibo());
 
  cout << ensFibo;
 
  cout << "Operation d'union : " << endl;
 
  // L'iterateur de sortie fonctionne en iterateur output
  set_union(ensImpairs.begin(),
            ensImpairs.end(),
            ensFibo.begin(),
            ensFibo.end(),
            ostream_iterator<int>(cout," "));
  cout << endl;
 
  // Creation d'un nouvel ensemble
  EnsInt ensResultat;
  set_union(ensImpairs.begin(),
            ensImpairs.end(),
            ensFibo.begin(),
            ensFibo.end(),
            inserter(ensResultat,ensResultat.begin()));
 
  cout << ensResultat;
 
  // Extraction du resultat dans une deque
  set_union(ensImpairs.begin(),
            ensImpairs.end(),
            ensFibo.begin(),
            ensFibo.end(),
            inserter(dq,dq.begin()));
 
  copy(dq.begin(),dq.end(),ostream_iterator<int<(cout," "));
  cout << endl;
 
  // Les 3 resultats sont identiques !
 
  ensResultat.erase(ensResultat.begin(),ensResultat.end());
 
  if (includes(ensImpairs.begin(),
               ensImpairs.end(),
               ensFibo.begin(),
               ensFibo.end()))
    cout << "Bleme :)" << endl;
 
  cout << "Intersection : " << endl;
 
  set_intersection(ensImpairs.begin(),
                   ensImpairs.end(),
                   ensFibo.begin(),
                   ensFibo.end(),
                   inserter(ensResultat,ensResultat.begin()));
 
  cout << ensResultat;
 
  if (!includes(ensFibo.begin(),
                ensFibo.end(),
                ensResultat.begin(),
                ensResultat.end()))
    cout << "Bleme numero 2" << endl;
 
 
  cout << "Difference impairs  - fibo " << endl;
 
  set_difference(ensImpairs.begin(),
                 ensImpairs.end(),
                 ensFibo.begin(),
                 ensFibo.end(),
                 ostream_iterator<int>(cout," "));
 
  cout << endl << "Difference fibo  - impairs " << endl;
 
  set_difference(ensFibo.begin(),
                 ensFibo.end(),
                 ensImpairs.begin(),
                 ensImpairs.end(),
                 ostream_iterator<int>(cout," "));
 
  cout << endl << "Difference symmetrique " << endl;
 
  set_symmetric_difference(ensImpairs.begin(),
                           ensImpairs.end(),
                           ensFibo.begin(),
                           ensFibo.end(),
                           ostream_iterator<int>(cout," "));
  cout << endl;
  
  EnsInt ens;
 
 
 
  generate_n(inserter(ens,ens.begin()),10,GenerateurImpairs());
 
  cout << ens << endl;
 
  return 0;
}
 
// Resultat a l'ecran
//
// 1 3 5 7 9 11 13 15 17 19
// 0 1 2 3 5 8 13 21 34
// Operation d'union :
// 0 1 2 3 5 7 8 9 11 13 15 17 19 21 34
// 0 1 2 3 5 7 8 9 11 13 15 17 19 21 34
// 0 1 2 3 5 7 8 9 11 13 15 17 19 21 34
// Intersection :
// 1 3 5 13
// Difference impairs  - fibo
// 7 9 11 15 17 19
// Difference fibo  - impairs
// 0 2 8 21 34
// Difference symmetrique
// 0 2 7 8 9 11 15 17 19 21 34
 
 

6.3 Utilisation des maps

6.3.1 Description

Les maps travaillent sur des paires (clef,valeur). Dans le cas d'une map simple, il ne peut y avoir au plus qu'une valeur associée à chaque clef, la valeur est alors accessible via un opérateur crochet portant sur la clef. Dans le cas d'une map multiple, il sera possible d'utiliser equal_range pour obtenir une paire d'itérateurs encadrant les éléments associés à une clef.

6.3.2 Travail à réaliser

Une compagnie de téléphone souhaite réaliser l'indexation de ses abonnés en fonction du préfixe de zone. Un abonné est caractérisé par son nom et son numéro complet.

Comment pouvez vous réaliser les opérations suivantes :

Dans un second temps, considérant que le système est par trop incomplet, la compagnie souhaire une indexation double :

Comment pouvez vous l'y aider ?