Remplir une map [Résolu]

vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 13 août 2005 à 13:36 - Dernière réponse : vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention
- 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
steve_clamage 475 Messages postés dimanche 3 octobre 2004Date d'inscription 11 août 2006 Dernière intervention - 14 août 2005 à 10:56
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

Merci steve_clamage 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 93 internautes ce mois-ci

Commenter la réponse de steve_clamage
steve_clamage 475 Messages postés dimanche 3 octobre 2004Date d'inscription 11 août 2006 Dernière intervention - 13 août 2005 à 17:29
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
vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 13 août 2005 à 18:50
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
steve_clamage 475 Messages postés dimanche 3 octobre 2004Date d'inscription 11 août 2006 Dernière intervention - 13 août 2005 à 19:20
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
vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 13 août 2005 à 20:55
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
vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 13 août 2005 à 20:58
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
steve_clamage 475 Messages postés dimanche 3 octobre 2004Date d'inscription 11 août 2006 Dernière intervention - 13 août 2005 à 21:56
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
xterminhate 371 Messages postés dimanche 4 janvier 2004Date d'inscription 23 septembre 2009 Dernière intervention - 14 août 2005 à 09:25
0
Merci
Tu as regardé le code de la STL ?... (bon courage)

Cordialement,
Xterminhate.
Commenter la réponse de xterminhate
vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 14 août 2005 à 10:00
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
vecchio56 6539 Messages postés lundi 16 décembre 2002Date d'inscription 22 août 2010 Dernière intervention - 14 août 2005 à 11:34
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.