Discussion :

[nasboy3d]

Salut Amis développeurs
J'ai découvert il y a pas longtemps l'existence du conteneur std::unordered_map avec msvc 2010.
D'après ce que j'ai lu ce conteneur est plus efficace que la std::map pour tout ce qui est find, insert, erase.....Mais par contre il faut fournir une fonction de hachage qui tient la route..Aussi il y en a qui sont fournies par défaut....
Moi je veux faire ça : std::unordered_map<std::pair<int,int>, float>.....
Donc la question est : est-ce que j'ai une fonction de hachage appropriée pour
les std::pair...ou faut-il la fournir....En gros quel condition doit-remplir un type pour être clé d'une unordered_map....
N.B : Je suis en plein dans un projet donc j'ai pas trop le temps de chercher en profondeur...Merci de me filer un coup de main .

[nasboy3d]

Je me repond moi-meme car j'ai trouvé.....
Pour ceux qui ont le meme probleme sachez que boost fournit dans son header
boost/functional/hash/extensions.hpp des fonctions de hach pour std::pair<> et tous les conteneurs.

Attendez...c'est pas encore fini...J'ai un autre petit problème
Je veux modifier une clé dans mon unordered_map par itérateur mais apparemment c'est protégé car quand j'essaie-->erreur de compilation...

Je ne maitrise pas encore ce conteneur mais je sais que avec map il peut y avoir des soucis car c'est ordonné en permanence...mais là il n'y a pas d'ordre...

Alors Est-ce que quelqu'un sait comme procéder pour modifier les valeurs des clés tout en gardant la meme position...???
Merci

[Invité]

Le nom est trompeur... Les unordered_map sont aussi ordonnées, mais pas selon des critères que tu definis toi-même. Logiquement tu ne peux pas modifier la clé.

[3DArchi]

Salut,
ordonnée ou pas, une map est une association entre une clé et une valeur. Modifier la clé revient à supprimer une ancienne association pour en créer une nouvelle.
L'idée sous jascente des map (ordered) est d'utiliser la relation d'ordre strict pour construire un arbre binaire des éléments et permettre leur recherche en log(n). L'inconvénient est que l'insertion ou la suppression d'un élément est couteuse car cela demande de retravailler sur l'arbre.
L'idée des unordered map est d'utiliser une fonction de hachage pour segmenter l'ensemble des clés en différents sous-ensembles plus réduits (un peu comme les CMap des MFC), l'association dans le sous-ensemble étant gérée plus 'basiquement' (les MFC font une liste chaînée si je me souvient bien). Le principe est d'avoir une fonction de hachage qui minimise les collisions, çad qui minimise le nombre de clés qui ont le même hash. L'insertion et la suppression peuvent être alors plus rapide (comme dans une liste chaînée par expl) mais la recherche est un peu moins performante.

[nasboy3d]

L'insertion et la suppression peuvent être alors plus rapide (comme dans une liste chaînée par expl) mais la recherche est un peu moins performante.

Qu'entends-tu par moins performante ??? car selon ce que j'ai lu les unordered_map sont plus rapides que les map que ce soit pour l'insertion, la suppression mais aussi pour la recherche....

[ymoreau]

Salut, voici les infos sur les conteneurs de Qt : http://qt.developpez.com/doc/latest/...mic-complexity

A savoir que QHash correspond au std::unordered_map et QMap au std::map. Même s'il ne s'agit pas exactement de la même implémentation, les algos sont les mêmes derrière, donc la complexité aussi. Pour résumer l'unordored_map sera plus rapide en moyenne pour n'importe quelle action (insertion, suppression, recherche), par contre le pire (lorsque la fonction de hachage crée beaucoup de collisions) est plus important qu'avec une map (en arbre).

[screetch]

il faut savoir que les unordered_map ont un gros defaut: lorsqu'on depasse une certqine taille (qui double a chaque fois) l'ensemble va etre realloué, toute les clés de hachage vont etre recalculées (ca depend de l'implementation bien sur mais la derniere fois que j'avais essayé sur crosof c'etait comme ca) et donc la performance a l'insertion chute