Remplir une map [Résolu]

Signaler
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
-
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
-
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é)

10 réponses

Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Statut
Membre
Dernière intervention
11 août 2006
4
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
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Statut
Membre
Dernière intervention
11 août 2006
4
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).
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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...)
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Statut
Membre
Dernière intervention
11 août 2006
4
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)
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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?
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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?
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Statut
Membre
Dernière intervention
11 août 2006
4
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.
Messages postés
371
Date d'inscription
dimanche 4 janvier 2004
Statut
Membre
Dernière intervention
23 septembre 2009

Tu as regardé le code de la STL ?... (bon courage)

Cordialement,
Xterminhate.
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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)?
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
8
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