Quelqu'un peut-il recommander un conteneur de remplacement C++ std :: map?

Question

Les cartes sont géniales pour faciliter les choses, mais ce sont des porcs mémoire qui souffrent de problèmes de mise en cache. Et quand vous avez une carte dans une boucle critique qui peut être mauvaise. Donc, je me demandais si quelqu'un peut recommander un autre conteneur qui a la même API mais utilise laisse dire une implémentation de vecteur ou de hachage à la place d'une implémentation en arbre. Mon but ici est d'échanger les conteneurs et de ne pas avoir à réécrire tout le code utilisateur qui repose sur la carte.

Mise à jour: performances sage la meilleure solution serait une façade de carte testée sur un std :: vector

Answer 1

Voir Loki::AssocVector et/ou hash_map (la plupart des implémentations STL ont celui-ci).

Answer 2

Si votre clé est un type simple qui peut être comparé très rapidement et que vous n'avez pas plus de quelques milliers d'entrées, vous pourriez avoir de meilleures performances en mettant simplement vos paires dans un std::vector et en itérant pour trouver votre valeur.

Answer 3

Vous pouvez utiliser std :: tr1 :: unordered_map, qui est déjà présent dans la plupart des implémentations STL et fait partie de la norme C++ 0x.

Voici c'est la signature actuelle:

template <class Key, 
      class T, 
      class Hash = std::tr1::hash<Key>, 
      class Pred = std::equal_to<Key>, 
      class Alloc = std::allocator<std::pair<const Key, T> > > 
class unordered_map; 

Answer 4

Peut-être Google SparseHash pourrait vous aider?