Dans le standard C++ 0x, il y aura unordered_map, comment cela se compare-t-il à boosts unordered_map?

Question

Lequel est le plus efficace? Y a-t-il de bons repères?

Answer 1

La spécification std :: unordered_map de C++ 11 est similaire à boost :: unordered_map qui est basé sur tr1 :: unordered_map. Cela étant dit, il y a quelques petites différences. L'ajout de références rvalue dans C++ 11 entraîne l'ajout des fonctions emplace et emplace_hint qui peuvent être utiles pour les performances.

C++ 11 est maintenant largement implémenté et vous devriez donc pouvoir utiliser std :: unordered_map dès sa sortie de la boîte. C++ 14 ne le modifie pas de manière significative et C++ 17 ajoutera (probablement) les fonctions membres insert_or_assign et try_emplace.

Answer 2

Dans le dernier brouillon standard n3225 de C++ 0x, il existe un modèle de classe section 23.6.1 unordered_map.

Donc, il est déjà là.

C++ 0x unordered_map est proposé basé sur un boost. La bibliothèque Boost elle-même possède également un espace de nommage tr1 :: unordered_map, qui partage l'implémentation de son propre boost: unordered_map. Si vous voulez comparer (bien sûr, vous n'avez pas besoin de comparer boost avec boost), je pense que plusieurs autres compilateurs, y compris Microsoft Visual Studio 2010, et gcc, ont leur propre implémentation unordered_map. Vous pouvez les utiliser en supposant qu'ils sont sous l'espace de noms tr1.

#include <unordered_map> 
... 
std::tr1::unordered_map<...> 

Je ne savais pas encore de référence, mais je pense à ce moment-tôt, une analyse comparative n'a pas de sens parce que le compilateur implémenteur optimiser définitivement leurs propres implémentations lorsque la norme réelle est finalisée et plus de gens va utiliser la bibliothèque.

Answer 3

Cela dépend de l'implémentation et de l'ensemble de données en question. Quand je jouais avec unordered_map pour un blog post j'ai trouvé que VS123 std::unordered_map perfromed bien pire que boost::unordered_mappour l'entrée j'ai utilisé (je n'ai pas construit un benchmark approfondi). En théorie, il ne devrait pas y avoir de différence.

Answer 4

Un point mineur non encore mentionné, la fonction std::hash est uniquement requise pour pouvoir calculer des hachages de types et de chaînes intégrés (et quelques autres types). La fonction boost::hash peut calculer des hachages d'objets plus complexes tels que pair et tuple. Boost a également une fonction hash_combine pour aider à créer des hachages pour les types définis par l'utilisateur.

Cela signifie que std::unordered_set< pair<int, int> > ne compilera pas, mais boost::unordered_set< pair<int, int> > sera.

Vous pouvez utiliser boost::hash avec std::unordered_* si nécessaire.

(Référence:. Article 6.18 the Library Extension Technical Report Issues List)