Conteneurs associatifs - map
Conteneurs associatifs
Alors que les conteneurs de séquence sont conçus pour des accès séquentiels et aléatoires à leurs éléments via l’index ou un itérateur, les conteneurs associatifs sont conçus pour un accès aléatoire rapide aux éléments à l’aide de clés. La bibliothèque C++ standard fournit quatre conteneurs associatifs : map, multimap, set et multiset.La bibliothèque standard distingue deux types de conteneurs associatifs : les conteneurs qui différencient la valeur de la clef de la valeur de l’objet lui-même et les conteneurs qui considèrent que les objets sont leur propre clef. Pour certains conteneurs, que l’on qualifie de conteneurs à clef unique, chaque élément contenu doit avoir une clef qui lui est propre. Il est donc impossible d’insérer plusieurs éléments distincts avec la même clef dans ces conteneurs (map, set). En revanche, les conteneurs associatifs dits à clefs multiples permettent l’utilisation d’une même valeur de clef pour plusieurs objets distincts. L’opération de recherche d’un objet à partir de sa clef peut donc, dans ce cas, renvoyer plus de un objet (multimap, multiset).
map
Le conteneur map permet de stocker « des choses » comme un tableau, mais à la grande différence de ce dernier, sa taille évolue dynamiquement ! Vous ne serez limité que par la mémoire de votre ordinateur.Une autre grande différence des map sur les tableaux est la façon dont ils sont indexés. L’index peut être de type int, char, string, ou n’importe quelle autre classe que vous aurez définie, du moment qu’il existe un moyen de comparer les objets.
À savoir
La façon particulière dont les map sont indexés entraîne une surcharge de traitement lors des opérations d’insertion et de tri. Si les performances du programme sont essentielles, vous devrez envisager d’écrire votre propre code pour ces fonctions.Pour utiliser un conteneur map, vous devez inclure le fichier en-tête <map> au début du programme et travailler dans l’espace de noms std.
Chaque élément d’un map est une paire struct définie dans l’espace de noms std comme suit :
template<class First, class Second> struct pair
{
// Autres membres de structure
First first;
Second second;
};
Comme les conteneurs de séquence, la classe map fournit les trois fonctions membres size(), max_size() empty() liées à la taille. Elle fournit aussi les itérateurs begin() (pointe sur le premier élément), end() (pointe vers l’élément après le dernier), rbegin() (pointe sur le premier élément de la séquence inverse), et rend() (pointe vers l’élément après le dernier de la séquence inverse).
La classe map fournit aussi l’opérateur index [] pour accéder directement aux éléments et la fonction find() pour retrouver un élément à partir de sa clé. Celle-ci renvoie map::end() si la clé n’existe pas.
Notre exemple de code illustre les principales opérations réalisables sur un conteneur.
Code 8.13 : utilisation d’un map
#include <iostream>
#include <string>
#include <map>
using namespace std;
class MaClasse
{
public:
//constructeurs
MaClasse():v1("Objet nouveau"), v2(0) {}
MaClasse(string valeur1, int valeur2 = 0):
v1(valeur1), v2(valeur2) {}
//Fonctions d’accès
void DefinirValeur(string valeur1) { v1 = valeur1; }
void DefinirValeur(int valeur2) { v2 = valeur2; }
string LireValeur() const { return v1; }
int LireValeur2() const { return v2; }
//opérateur << surchargé
friend ostream& operator<<(ostream& sortie, const MaClasse& p)
{
sortie << "Chaîne: " << p.v1
<< "\tValeur: " << p.v2;
return sortie;
}
private:
string v1;
int v2;
};
// Fonction modèle d’affichage des éléments d’un map
template<class T, class A>
void AfficherMap(const map<T, A>& m);
int main()
{
//On crée 3 objets
MaClasse objet1("Objet 1", 10);
MaClasse objet2("Objet 2", 20);
MaClasse objet3("Objet 3", 30);
//On crée le map
map<string, MaClasse> MonMap;
//On initialise les éléments
MonMap[objet1.LireValeur()] = objet1;
MonMap[objet2.LireValeur()] = objet2;
MonMap[objet3.LireValeur()] = objet3;
AfficherMap(MonMap);
//On affiche la valeur de objet1
cout << "Voici les valeurs de objet1: " << MonMap["Objet 1"].LireValeur();
cout << "\t" << MonMap["Objet 1"].LireValeur2() << endl;
//On modifie les 2 valeurs de objet2
MonMap["Objet 2"].DefinirValeur("Objet 2 bis");
MonMap["Objet 2"].DefinirValeur(22);
cout << "Voici les nouvelles valeurs de objet2: ";
cout << MonMap["Objet 2"].LireValeur() << "\t";
cout << MonMap["Objet 2"].LireValeur2() << "\n";
cout << "On ajoute au map : Chaîne: Objet 1 Valeur: 40\n";
MaClasse objet4("Objet 1", 40);
MonMap[objet4.LireValeur()] = objet4;
AfficherMap(MonMap);
// Les diverses fonctions d’accès relatives à l’objet 1
cout << "\nVoici le nombre d’objets 1 : ";
cout << MonMap.count("Objet 1") << "\n";
//On cherche le premier objet de clé "Objet 1"
map<string, MaClasse>::iterator ci=MonMap.lower_bound("Objet 1");
cout << "Le premier Objet 1: " << ci->second << "\n";
//on pointe sur l’élément suivant
ci = MonMap.upper_bound("Objet 1");
cout << "Elément qui suit Objet 1: " << ci->second;
// On tente d’accéder à un élément qui n’existe pas
cout << "\nOn cherche un Objet 10 : ";
cout << MonMap["Objet 10"] << endl;
cout << "On efface Objet 3\n";
MonMap.erase("Objet 3");
AfficherMap(MonMap);
cout << "On efface tout\n";
MonMap.clear();
AfficherMap(MonMap);
}
//Définition de la fonction d’affichage du map
template<class T, class A>
void AfficherMap(const map<T, A>& m)
{
cout << "Voici les éléments du map :\n";
for (typename map<T, A>::const_iterator ci = m.begin(); ci != m.end(); ++ci)
cout << ci->first << "\t" << ci->second << "\n";
cout << "\n\n";
}
En exécutant ce programme, vous obtenez le résultat suivant :
Voici les éléments du map : Objet 1 Chaîne: Objet 1 Valeur: 10 Objet 2 Chaîne: Objet 2 Valeur: 20 Objet 3 Chaîne: Objet 3 Valeur: 30 Voici les valeurs de objet1: Objet 1 10 Voici les nouvelles valeurs de objet2: Objet 2 bis 22 On ajoute au map : Chaîne: Objet 1 Valeur: 40 Voici les éléments du map : Objet 1 Chaîne: Objet 1 Valeur: 40 Objet 2 Chaîne: Objet 2 bis Valeur: 22 Objet 3 Chaîne: Objet 3 Valeur: 30 Voici le nombre d’objets 1 : 1 Le premier Objet 1: Chaîne: Objet 1 Valeur: 40 Elément qui suit Objet 1: Chaîne: Objet 2 bis Valeur: 22 On cherche un Objet 10 : Chaîne: Objet nouveau Valeur: 0 On efface Objet 3 Voici les éléments du map : Objet 1 Chaîne: Objet 1 Valeur: 40 Objet 10 Chaîne: Objet nouveau Valeur: 0 Objet 2 Chaîne: Objet 2 bis Valeur: 22 On efface tout Voici les éléments du map :
Les éléments d’un tel conteneur étant des paires, nous utilisons first et second pour renvoyer leur paire clé/valeur. Vous constatez qu’après l’ajout d’un second objet de clé Objet 1, celui-ci remplace le premier puisqu’un map ne peut contenir de doublons sur la clé.
Notez aussi que nous avons fait en sorte que la recherche d’un élément inexistant entraîne la création d’un nouvel élément par l’appel du constructeur par défaut de la classe.
Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)