Le point sur unordered_map

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 .

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

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

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.

Citation:

---

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

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

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

Citation:

---

Envoyé par 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

---

D'ailleurs j'ai une question à ce propos :
Si l'on connais approximativement le nombre max d'élément que l'on va mettre dans sa hash table, est-ce qu'il n'y a pas moyen de faire l'équivalent d'un reserve() en jouant avec les fonction max_load_factor() et rehash() ?

la derniere fois que j'ai regardé sur l'implementation microsoft (c'etait il y a 4 ans quand meme) cette methode n'existait pas d'ou la lenteur. On a obtenu un speedup d'environ 90% en remplacant un hash map par un map simplement a cause de ca (le hash map passait son temps a grandir).

Merci à tout le monde pour vos avis.....
Donc apparement vous me conseillez d'utiliser une map à la place....
Juste une dernière chose : j'ai cru lire sur le site de microsoft que toutes les opérations seraient en O(1) si l'on connaissait la taille maxi à l'avance..
Dans ce cas on pourrait déclarer ainsi std::unordered_map MY_MAP(SIZE_MAX);
Est-ce que je pourrais avoir votre confirmation là-dessus sachant que j'ai un petit doute (SIZE_MAX représente t-elle la taille des éléments ou des buckets ??)
Sans oublier que la fonction hash que j'utilise provient de sa majesté boost...;)
Merci

oui dans ce cas ca marche :) size_max représente le nombre d'éléments que tu vas insérer dans le hash_map (si je comprends bien)

L'idéal est de faire des benchs entre map et unordered_map dans le cas d'utilisation souhaité (ce qui est d'autant plus simple que les interfaces sont quasiment identiques). J'ai eu plusieurs témoignages indiquant que malgré une complexité meilleure en moyenne, en pratique map avait tendance à être plus efficace que unordered_map tant que le nombre de données n'était pas très grand.

Ok Je fais un bench et je vous tiens au courant....s'il y en a qui veulent en faire aussi... ce sera cool....

Bon Le verdict est tombé....
J'ai fait 3 benchs :
- INSERT ---> UNORDERED_MAP :1733 us | MAP :909 us
- INSERT + FIND ---> UNORDERED_MAP :2456 us | MAP :1571 us
- INSERT + FIND + ERASE ---> UNORDERED_MAP :4482 us | MAP :2906 us
Info Bench : us = microsecond

Voici le code du 3ème Bench :
Pour la map :

Citation:

---

PerfChrono chrono;
std::map<std::pair<GLint,GLint>, GLfloat> TEMP_MAP;
std::cout<<"Frequence de l'horloge : "<<chrono.GetFreq()<<" Hz."<<std::endl;
GLint ind1 =0;
GLint ind2 =1;
GLfloat val = 2.5f;
chrono.Start();

for(GLint i=0; i<100; i++){
TEMP_MAP.insert(std::make_pair(std::make_pair(++ind1,++ind2),++val));
TEMP_MAP.find(std::make_pair(i+2,i+3));
TEMP_MAP.erase(std::make_pair(i*2,i*3));
}

std::cout<<"Time elapsed = "<<chrono.GetDiffUs()<<std::endl;

---

Et celui de l'unordered_map :

Citation:

---

std::unordered_map<std::pair<GLint,GLint>, GLfloat, boost::hash<std::pair<GLint,GLint> > > TEMP_MAP(100);
std::cout<<"Frequence de l'horloge : "<<chrono.GetFreq()<<" Hz."<<std::endl;
GLint ind1 =0;
GLint ind2 =1;
GLfloat val = 2.5f;
chrono.Start();

for(GLint i=0; i<100; i++){
TEMP_MAP.insert(std::make_pair(std::make_pair(++ind1,++ind2),++val));
TEMP_MAP.find(std::make_pair(i+2,i+3));
TEMP_MAP.erase(std::make_pair(i*2,i*3));
}

std::cout<<"Time elapsed = "<<chrono.GetDiffUs()<<std::endl;

---

Comme vous pouvez le constater la std::map l'emporte haut la main(près du double des perfs)...J'avoue, je suis assez surpris sachant que j'utilise une fonction hash de boost...bizarre non??
Sinon à quoi ça servirait cette structure ??

100 ca n'est pas beaucoup, la complexité entre a peine en jeu.
Le problème c'est que le map a une complexité en O(log(n)) tandis que le unordered_map a une complexité en O(1), donc lorsque n est petit les deux sont similaires mais lorsque n grandit la complexité de map tend vers l'infini (mais t`res très doucement)
je pense que le unordered_map n'est vraiment utile qu'au dela de 50000 objets
meme so a partir de 100, avec une bonne implémentation, il devrait deja etre assez performant -_-
il y a aussi peut etre trop de collisions
enfin, si je suis bien, ton erase et ton find ne trouve jamais rien?

Je ne parlais pas d'un bench dans un exemple décorrélé de tout, mais d'un bench dans le cadre de ton application, avec des vraies données en entrée, pour savoir en fonction du nombre, mais aussi du conditionnement de tes données, laquelle de ces deux structures est plus intéressante.