Les tables associatives.

Les tables associatives.

map

Voir version :

Pas de dépendances

Télécharger :

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    map<string,int> m;
    m["janvier"] = 31;
    m["fevrier"] = 28;
    m["mars"] = 31;
    m["avril"] = 30;
    m["mai"] = 31;
    m["juin"] = 30;
    m["juillet"] = 31;
    m["aout"] = 31;
    m["septembre"] = 30;
    m["octobre"] = 31;
    m["novembre"] = 30;
    m["decembre"] = 31;
    int a = m.count("decembre");
    cout << "il y a " << m["mars"] << " jours en mars" << endl;
    return 0;
}



Commentaires


  Voici le conteneur associatif "map"

  Pensez a un dictionnaire :
  Vous associez une clé a une définition.
  Dans un dictionnaire, la clé est un mot : vous associez un mot a une définition.

  Dans l'exemple, j'associe chaque mois a son nombre de jours.


  je définis 
  map<string,int>

  c'est a dire que ma "clé" sera une string et ma "définition" sera un int.
  (regardez la définition de la classe string dans le tuto sur la chaine de caractere en C++)

  Le concept est simple et puissant :
  je dis :

  Retiens que "janvier" est associé à "31" : en gros, si je te redemande "janvier", tu me diras "31"

  De la, vous pouvez enfermer autant d'éléments que souhaités.
  L'écriture et la lecture d'une map se fait directement avec l'opérateur []

Question : et si on interroge la map sur un élément qui n'existe pas ?
**********************************************************************

  Par exemple si je demande :

  m["plouf"]
  que se passe t il ? 
  --> ça me donne la "définition" par défaut :
  pour un int, ça me donne un int par défaut : donc 0...
  Essayez de demande la map de "plouf" ...

Question : Je peux tres bien mettre 0 dans "paf", et ne pas définir "plouf", si j'interroge les 2, ils me diront tout deux 0,
comment savoir alors si un élément a été rempli ou non ?
********************************************************

  Regardez la valeur de :

  int n = m.count("decembre");

  pour "decembre", ça rendra 1 (car on l'a défini)
  pour "plouf", ça rendra 0 (car on ne l'a pas défini)


Question : Peut on mettre plusieurs valeurs sur une meme clé ?
**************************************************************

  Par exemple, si je fais :

  m["paf"] = 5;
  m["paf"] = 7;

  Qu'est ce que ça me donne si je demande m["paf"] ?

  --> ça me donne 7. 
  On ne peut mettre qu'un seul élément pour une seule clé avec map.

  Pour remédier a cela :
  --> utliser multimap (on verra plus tard comment ça marche)
  --> astuce : définir que chaque élément est une liste :
  map<string,list<int> >



Autre utilisation de map : des numéros de sécurité sociale
***********************************************************

  Imaginons que vous vouliez stocker des personnes par numéro de sécu :

  struct Personne
  {
  int taille;
  string nom;
  string prenom;
  ....
  };

  map<int,struct Personne>

  map est idéal, car les numéro de sécu sont longs. Si vous faites un tableau fixe de plusieurs milliards d'éléments : perte de mémoire considérable


Principe interne : contrainte
*****************************

  Pour donner les éléments en interne tres tres vite (si vous stockez 1000000 d'éléments dans map, celui ci est quand meme capapble
  de vous rendre le résultat tres rapidement)
  map est organisé. (il utilise une table de hashage. -> si vous ne savez pas ce que c'est, pas grave)
  Tout ce qu'il y a à retenir, c'est que les clés doivent etre TRIABLES.

  C'est a dire que l'opérateur < doit etre surchargé pour la clé.
  Dans l'exemple de la sécurité sociale ci dessus, je mets int comme clé : donc pas de soucis.
  Au dessus, dans l'exemple des mois, j'ai mis une "string" et volontairement pas un char*
  En effet, les string sont classables, alors que les char* ne le sont pas (si on essaie de les classer, ça va les classer en fonction
  de l'adresse du pointeur, ce qui ne sera pas bon : 
  (pour les pros : meme si vous avez rempli "décembre", si vous redemandez "décembre", il vous dira qu'il ne l'a pas car a l'appel, la chaine statique créée
  n'aura pas la meme adresse que l'autre appel, donc ça ne marchera pas)

  Donc si vous voulez faire appel a des char*, utilisez un foncteur.
  Pour cela, suivez le tres bel exemple suivant, copié collé, depuis ce site :
http://www.sgi.com/tech/stl/Map.html
(page principale :

  http://www.sgi.com

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  map<const char*, int, ltstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "june -> " << months["june"] << endl;

....
}
  

 * oui, j'ai copié cet exemple, car l'exemple des mois est, selon moi, la meilleure méthode pour illustrer map :)
mais je ne copie jamais quelque chose sans en mettre le lien :)