Discussion :

[Castagnems]

Bonjour à tous,

j'aurais aimé savoir comment les map fonctionnent. Plus précisément comment se fait il que les recherches avec find s'effectuent en Log(N) ainsi que ce qu'il se passe lorsqu'on accède à un élément avec map["cle"] ?

D'avance je vous remercie.

[vdumont]

Si tu fais par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
map["cle"] = "allo";

Si la clé "cle" n'existe pas, cela la créera avec la valeur associée "allo".
Si elle existe, cela modifiera la valeur courante.


Pour ce qui concerne le find, tu peux faire par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
std::map<int,std::string> m;
int position = m.find(1) // rechercher la clé 1 et retourne sa position si trouvée

[doudoustephane]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
std::map<int,std::string> m;

oui, mais ce code la (que j'ai laisse), tu peux me l'expliquer STP...???

[Pragmateek]

oui, mais ce code la (que j'ai laisse), tu peux me l'expliquer STP...???

map est une classe template qui prend en paramètre template le type de la clé et le type des données.

[doudoustephane]

map est une classe template qui prend en paramètre template le type de la clé et le type des données.

ok, mais, a quoi cela sert alors concretement car j'ai beau chercher dans les cours... je trouve rien qui me l'explique bien...

[Pragmateek]

ok, mais, a quoi cela sert alors concretement car j'ai beau chercher dans les cours... je trouve rien qui me l'explique bien...

De quoi, les templates?

[Castagnems]

C'est de savori comment s'est implémenté qui m'intéresse.

Ca fonctionne avec des arbres binaires de recherche ? Comment la clé du noeud est-elle calculée ?

[Matthieu Brucher]

C'est de savori comment s'est implémenté qui m'intéresse.

Ca fonctionne avec des arbres binaires de recherche ? Comment la clé du noeud est-elle calculée ?

En général, ce sont des arbres à noeuds rouges et noirs. RBTree.

[Castagnems]

Ok merci merci ... j'vais essayer d'aller voir dans le fichier <map> ... j'y trouverai sans doute toutes les infos que je veux.

[NicolasG]

C'est de savori comment s'est implémenté qui m'intéresse.

Ca fonctionne avec des arbres binaires de recherche ? Comment la clé du noeud est-elle calculée ?

Les maps sont des collections triées par clé.
Elles utilisent une fonction de comparaison des clés (less) pour permettre le tri.

Cette même fonction permet de rechercher simplement une clé par dichotomie (puisqu'elles sont triées).

[Luc Hermitte]

Ben .. c'est implémenté avec des arbres. C'est de l'algorithmique très classique.

Quand à m[clé], cela réalise une recherche, si rien n'est trouvé, un nouvel élément initialisé à sa valeur par défaut est rajouté. Au final, l'élément (nouveau ou non) qui va bien est retourné par référence.