[c++] Map

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.

Si tu fais par exemple:

Code:

---

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:

---

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

---

Citation:

---

Envoyé par vdumont

Code:

---

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

---

---

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

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.

Citation:

---

Envoyé par doudouallemand

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.

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 ?

Citation:

---

Envoyé par seriousme

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

Citation:

---

Envoyé par 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 ?

---

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

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

Citation:

---

Envoyé par doudouallemand

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?

Citation:

---

Envoyé par seriousme

De quoi, les templates?

---

non, les map

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

Citation:

---

Envoyé par Miles

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

Citation:

---

Envoyé par 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 ?

---

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

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

Code:

---

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

Citation:

---

Envoyé par doudouallemand

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.

ok, :merci: a tous...