Je dois faire un outil qui parse des fichiers de log assez conséquent 1G0.
 
je me servais, jusqu'à présent de std::map pour stocker les lignes et pouvoir les identifier par la suite grâce à un ID.
 
J'essaye maintenant d'optimiser le temps d'éxécution et je me demandais si une unordered_map ne serait pas plus rapide..
 
et si oui en C++, existe t-il des choses en standard ?
 
Merci

La principale différence entre map et unordered_map c'est que unordered_map rajoute le calcule du hash de la clé afin de la stocker dans un entier.
 
Donc en résumant si ta clef n'est pas un entier, unordered_map sera souvent plus rapide car le hash de cette clé sera plus rapide à manipuler qu'un gros objet.
Sinon si ta clé est déjà un entier, unordered_map sera plus lent car calcule du hash en plus.

pas mal merci, effectivement ma clef est une string

ok http://en.wikipedia.org/wiki/Hash_map_(C%2B%2B_class)

visual 2005 semble pas connaitre hash_map par contre

c'est normal ?

Je n'ai pas visual 2005 mais tu as bien ?

c'ets pas std::tr1::hash_map ?

http://msdn.microsoft.com/en-us/li [...] S.71).aspx

 
Sinon il y a :

VisualStudioG

stdext, hum ok je mettais std

Ben je vois pas pourquoi, c'est plus clair de différencier ce qui est standard (std::map) de ce qui est une extension (stdext::hash_map) de ce qui est du technical report (std::tr1::unordered_map).

oui, entre développer sous visual ou sous linux avec emacs... le choix est vite vu

Je me permet de rebondir en prolongeant la question : a priori, pour moi si une clef dans une map c'est un pointeur vers un objet, j'ai toujours pensé que la clef était considérée comme un entier, l'adresse mémoire... avec bien sur l'opérateur de la classe utilisé pour le tri.
 
Donc je pensais que dans le cas d'une clef de type pointeur, utiliser un map était aussi rapide qu'un unordered_map : mais est-ce le cas ?

houla-là...
 
- Si la clé est un pointeur, c'est hashé/comparé comme un entier, puisqu'un pointeur est, en interne, un nombre entier. La comparaison se fait par défaut avec la comparaison des pointeurs, qui est la même que les entiers. 0x0052647B < 0x0052678D par exemple, quoi qu'il soit pointé. On peut surcharger l'opérateur de comparaison.
 
- La compléxité d'un accès en table de hashage est O(1) en général, O(n) dans le pire des cas, + compléxité de la fonction de hashage.
 
- La compléxité d'un accès en map est O(c * log2(n)) où n est le nombre d'éléments et c la compléxité de la fonction de comparaison.
 
- Donc que les éléments soient des entiers ou pas, l'accès en table de hashage est plus rapide, sauf (rare) pire des cas. En gros, hash_table de donne en vitesse ce que tu perds en information, puisque tu perds l'ordre.

je suis perdu moi,dans  une std::map les éléments sont ordonnées ??

oui.
dans hash_map/unordered_map, non, d'où son nom.

ça permet  quoi d'avoir les éléments ordonnées au juste ? y a bien un avantage...y a un truc qui m'échappe

Il y a des applications ou c'est utile.
 
Mais on peut aussi voir le fait que les map soient triee comme un detail d'implementation dont on a finit par dependre et qui fait partie maintenant de la spec.
 
(Les map sont contraintes de sorte qu'un arbre binaire equilibre soit l'implementation naturelle pour respecter l'interface -- qui demande une fonction de comparaison et non une fonction de hachage -- et la complexite -- operations garanties en log N alors qu'avec une table de hachage on peut degenerer en N).

ah oui je vois , très intéressant , merci bien

svp j ai besoin a des info sur la fanction hachage j ai un projet

C'est un peu court, jeune homme