Le type le plus rapide pour la clé std :: map?

Question

Je voudrais utiliser les partitions d'un graphique comme la clé d'un std :: carte

Je pourrais représenter cela comme un vecteur std de noeuds. Ou je pourrais le convertir en un format binaire "custom" plus compact (bitset?), Ou une représentation de chaîne. Pour simplifier, on peut dire qu'il n'y a pas d'ordre inhérent aux partitions d'un graphe.

Ce qui sera le plus rapide en termes d'insertions et des références externes (notez la taille de cette carte sera dans l'ordre d'un milliard de noeuds)

Answer 1

Si vous avez beaucoup d'entrées et que les performances sont critiques, je vous suggère d'utiliser définitivement unordered_map.

Si vous utilisez C++ 1x, il se trouve dans la bibliothèque standard; Sinon, vous pouvez l'obtenir auprès de boost.

Si la performance est vraiment vous pouvez aller encore plus loin et utiliser boost::intrusive. Il contient des versions "intrusives" des conteneurs de bibliothèque standard: ils copient les pointeurs des valeurs que vous insérez au lieu des valeurs elles-mêmes. Si les valeurs sont grandes, vous obtiendrez un grand avantage de performance.

Answer 2

La seule façon de répondre de façon fiable à cette question est la seule façon de répondre à question d'optimisation: Essayez-le et voyez. Cela dit, je doute qu'il y ait beaucoup de différence entre les deux, tant qu'il y a un opérateur de comparaison efficace que vous pouvez utiliser.

Answer 3

Conservez votre type de clé, mais utilisez la fonction unordered_map de boost et écrivez votre propre fonction hash() pour votre partition de graphique. Par exemple, si l'ordre n'a pas d'importance, vous pouvez hacher chaque nœud d'une manière qui est invariante à l'ordre. Si vous publiez comment vous l'écrivez maintenant, nous pouvons vous aider davantage.