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...???

[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.

[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.

[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 ?

[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...

[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.

[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?

[doudoustephane]

De quoi, les templates?

non, les map

[Matthieu Brucher]

A pleisn de choses.Je m'en sers pour classer les meilleurs paramètres pour un fonction par ex.

[doudoustephane]

A pleisn de choses.Je m'en sers pour classer les meilleurs paramètres pour un fonction par ex.

oui, je me demandais aussi comment??? un exemple de code quoi, pour pouvoir les utiliser par moi-meme ensuite...

[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).

[Matthieu Brucher]

Je calcule le coût d'un jeu de paramètres parameters puis je le stocke :

Code :

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

1
2
3
 
sts::map<double, vecteur> parametersMap;
parametersMap[calculCout(parameters)] = parameters;

Par exemple, c'est super pratique pour classer automatiquement les meilleurs poids dans l'algorithme du Simplexe/Downhill Simplex/Polytope

[NicolasG]

oui, je me demandais aussi comment??? un exemple de code quoi, pour pouvoir les utiliser par moi-meme ensuite...

On utilise les map pour relier des objets entre eux.
Par exemple, on peut utiliser comme clé un pseudo(string) et comme donnée le nombre de messages(int).

Cela permet de retrouver très facilement le nombre de messages en connaissant le pseudo.

Toute les fonctions de stockage et de recherche sont proposées par la classe map.

[doudoustephane]

ok, a tous...