¿Alguien puede recomendar un contenedor de reemplazo C++ std :: map?

Los mapas son geniales para hacer las cosas con facilidad, pero son recuerdos y sufren problemas de almacenamiento en caché. Y cuando tienes un mapa en un bucle crítico, puede ser malo.¿Alguien puede recomendar un contenedor de reemplazo C++ std :: map?

Así que me preguntaba si alguien puede recomendar otro contenedor que tenga la misma API pero use una implementación de vector o hash en lugar de una implementación de árbol. Mi objetivo aquí es intercambiar los contenedores y no tener que volver a escribir todo el código de usuario que se basa en el mapa.

Actualización: se refiere a rendimiento la mejor solución sería una fachada mapa probado en un std :: vector

Fuente

2008-09-24 Robert Gould

Ver Loki::AssocVector y/o hash_map (la mayoría de las implementaciones STL tienen éste).

Fuente

2008-09-24 07:49:26 yrp

Esto es básicamente una ordenada std :: vector > con interfaz tipo mapa. La licencia es lo suficientemente permisiva como para arrancarla y aferrarse a su proyecto en alguna parte. –

Lo siento, no había regresado para comprobar la respuesta hasta ahora, ¡pero esto es exactamente lo que necesitaba! Gracias un drop-in perfecto (teniendo en cuenta los casos de uso que tengo) –

Si su clave es un tipo simple que se puede comparar muy rápidamente y tiene no más de unos pocos miles de entradas, puede tener un mejor rendimiento simplemente colocando sus pares en un std::vector e iterando para encontrar su valor.

Fuente

2008-09-24 07:59:30

Idealmente, esa sería la mejor solución, pero no quiero escribir (y eliminar errores) la interfaz/envoltorio del vector para que sea compatible con Map. ¿Conoces alguna implementación de esta técnica? –

Desafortunadamente no. –

El conjunto de conceptos 'boost :: property_map' y especialmente' boost :: vector_property_map' es lo que estás buscando ... –

Puede usar std :: tr1 :: unordered_map, que ya está presente en la mayoría de las implementaciones de STL, y es parte del estándar C++ 0x.

Aquí es que es la firma actual:

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;

Fuente

2008-09-24 08:00:40

No he usado std :: tr1 :: unordered_map, pero si es algo como hash_map de STLport , No me sorprendería si una implementación típica es una memoria aún más grande que std :: map y tiene una localidad espacial igualmente mala. – bk1e

Ahora es C++ 11 :). – Kos

Tal Google SparseHash podría ayudarle?

Fuente

2008-09-24 08:25:47

¿Alguien puede recomendar un contenedor de reemplazo C++ std :: map?

Respuesta

Cuestiones relacionadas