Remplir une map [Résolu]

Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
- - Dernière réponse : vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
- 14 août 2005 à 11:34
Bonjour a tous
Je dois remplir une map<string, int> au debut de mon programme et je voudrais le faire le plus rapidement possible. Je pense que si je le fais de manière anarchique (sans faire attention à l'ordre d'insertion), mon arbre va devoir être rééquilibré plein de fois.
Est-ce qu'il y a une méthode pour créer mon arbre le plus rapidement possible? (j'ai pensé a prendre d'abord l'élément du milieu, puis faire la même chose à gauche et a droite, en travaillant avec un tableau auxiliaire trié selon la clé)
Afficher la suite 

Votre réponse

10 réponses

Meilleure réponse
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Dernière intervention
11 août 2006
2
3
Merci
Il vaut mieux eviter de ce fier à une seul implementation, le
standard spécifie juste l'interface et les complexités des différentes
opérations donc il vaut mieux tenir compte uniquement de ca et ne pas
regarder le code dans cette optique.



Le standard dit à propos de la construction (à partir d'une séquence de
N) que la complexité est linéaire en N si les élement sont deja trié
sinon N log (N).



Il est aussi dit que map (et tout les autres conteneurs associatifs)
sont implémentés avec un "arbre rouge-noir" qui s'auto équilibre (comme
tu le disais) et rend l'insertion d'un élément plus complexe.



L'article sur wikipedia anglophone, l'insertion y est expliquée.

http://en.wikipedia.org/wiki/Red-black_tree

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 117 internautes nous ont dit merci ce mois-ci

Commenter la réponse de steve_clamage
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Dernière intervention
11 août 2006
2
0
Merci
Essayes le constructeur qui prend une séquence en paramètre,
l'insertion des elements est peut etre optimisée (rien vu dans la doc).
Commenter la réponse de steve_clamage
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
16
0
Merci
J'ai fait des tests, l'insertion est plus rapide quand j'insère les éléments dans l'ordre que quand ils sont mélangés (pourtant il me semblait que c'était le pire des cas...)
Commenter la réponse de vecchio56
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Dernière intervention
11 août 2006
2
0
Merci
La construction d'un map ca revient à un tri par insertion, si tu lui
passes à chaque insert une cle plus grande (si deja trier) tu gagne du
temps (la recherche est instantanée), c'est probablement ca.

Avec le constructeur map(begin, end) c'est plus rapide ? (quelque soit l'ordre)
Commenter la réponse de steve_clamage
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
16
0
Merci
Si j'insère de manière triée c'est plus rapide mais l'arbre devient déséquilibré, un peu comme moi :)
J'ai pas trop compris ton histoire de constructeur, tu peux m'expliquer?
Commenter la réponse de vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
16
0
Merci
Par exemple, disons que je veux faire ceci:
map<string, int> m;
m["a"] = 1;
m["b"] = 2;
m["c"] = 3;
m["d"] = 4;
m["e"] = 5;
m["f"] = 6;

Tu as une autre solution pour fabriquer cet arbre?
Commenter la réponse de vecchio56
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Dernière intervention
11 août 2006
2
0
Merci
Oui, je parlais du constructeur qui construit la map à partir d'une sequence (de pair, dans ton cas pair<string, int>).



#include // pair

#include <string>

#include <map>





int main()

{

using namespace std;

typedef pair<string, int> si_pair;

typedef map<string, int> si_map;



const si_pair v[] =

{

si_pair("a", 1),

si_pair("b", 2),

si_pair("c", 3),

si_pair("d", 4),

si_pair("e", 5),

si_pair("f", 6)

};



si_map m(v, v + sizeof v / sizeof v[0]);

}



A toi de voir si c'est plus rapide comme ca et si de cette facon l'ordre à une importance.
Commenter la réponse de steve_clamage
Messages postés
371
Date d'inscription
dimanche 4 janvier 2004
Dernière intervention
23 septembre 2009
0
Merci
Tu as regardé le code de la STL ?... (bon courage)

Cordialement,
Xterminhate.
Commenter la réponse de xterminhate
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
16
0
Merci
steve_clamage, ta méthode semble équivalente
xterminhate j'ai essayé de regardé, ca m'a fait mal au yeux
J'ai fini par tomber sur _Tree::insert(const value_type& _Val) mais ce qui me fait peux c'est que j'ai l'impression qu'il insère la clé (je comprends à peu près le code), mais on ne dirait pas qu'il regarde si l'arbre est équilibré ou non. Vous avez des infos la dessus? Est-ce qu'il est possible qu'un arbre binaire deviennent complètement pourri (un arbre en peigne par ex)?
Commenter la réponse de vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
16
0
Merci
OK, j'avais vu arbre rouge noir sans savoir ce que c'était.
Je vais donc insérer les éléments dans l'ordre
Merci a tous les deux
Commenter la réponse de vecchio56

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.