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.
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 !) :
#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
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.
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 ?