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)