remplir une mapRésolu

Question

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

steve_clamage · Accepted Answer

Il vaut mieux eviter de ce fier &#224; une seul implementation, le
standard sp&#233;cifie juste l'interface et les complexit&#233;s des diff&#233;rentes
op&#233;rations donc il vaut mieux tenir compte uniquement de ca et ne pas
regarder le code dans cette optique.



Le standard dit &#224; propos de la construction (&#224; partir d'une s&#233;quence de
N) que la complexit&#233; est lin&#233;aire en N si les &#233;lement sont deja tri&#233;
sinon N log (N).



Il est aussi dit que map (et tout les autres conteneurs associatifs)
sont impl&#233;ment&#233;s avec un "arbre rouge-noir" qui s'auto &#233;quilibre (comme
tu le disais) et rend l'insertion d'un &#233;l&#233;ment plus complexe.



L'article sur wikipedia anglophone, l'insertion y est expliqu&#233;e.

http://en.wikipedia.org/wiki/Red-black_tree

steve_clamage · Answer

Essayes le constructeur qui prend une s&#233;quence en param&#232;tre,
l'insertion des elements est peut etre optimis&#233;e (rien vu dans la doc).

vecchio56 · Answer

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

steve_clamage · Answer

La construction d'un map ca revient &#224; un tri par insertion, si tu lui
passes &#224; chaque insert une cle plus grande (si deja trier) tu gagne du
temps (la recherche est instantan&#233;e), c'est probablement ca.

Avec le constructeur map(begin, end) c'est plus rapide ? (quelque soit l'ordre)

vecchio56 · Answer

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?

vecchio56 · Answer

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?

steve_clamage · Answer

Oui, je parlais du constructeur qui construit la map à partir d'une sequence (de pair, dans ton cas pair). #include // pair #include #include int main() { using namespace std; typedef pair si_pair; typedef map 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.

xterminhate · Answer

Tu as regard&#233; le code de la STL ?... (bon courage)

Cordialement,
   Xterminhate.

vecchio56 · Answer

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

vecchio56 · Answer

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

Remplir une map

10 réponses

Votre réponse