Implementación de hashmap simple en C++

Question

Soy relativamente nuevo en C++. En Java, es fácil para mí crear instancias y utilizar un hashmap. Me gustaría saber cómo hacerlo de una manera sencilla en C++, ya que vi muchas implementaciones diferentes y ninguna de ellas me pareció simple.

Answer 1

La mayoría de los compiladores deberían definir std::hash_map para usted; en el próximo estándar C++0x, será parte de la biblioteca estándar como std::unordered_map. El STL Page en él es bastante estándar. Si usa Visual Studio, Microsoft tiene una página.

Si desea utilizar su clase como el valor, no como la clave, entonces no necesita hacer nada especial. Todos los tipos primitivos (cosas como int, char, bool e incluso char *) deberían "solo funcionar" como claves en un hash_map. Sin embargo, para cualquier otra cosa, tendrá que definir sus propias funciones de hash e igualdad y luego escribir "funtores" que las envuelvan en una clase.

Asumiendo que su clase se llama MyClass y ya se han definido:

size_t MyClass::HashValue() const { /* something */ } 
bool MyClass::Equals(const MyClass& other) const { /* something */ } 

Tendrá que definir dos funtores para envolver esos métodos en los objetos.

struct MyClassHash { 
    size_t operator()(const MyClass& p) const { 
    return p.HashValue(); 
    } 
}; 

struct MyClassEqual { 
    bool operator()(const MyClass& c1, const MyClass& c2) const { 
    return c1.Equals(c2); 
    } 
}; 

Y instancia su hash_map/hash_set como:

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map; 
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set; 

todo debería funcionar como se esperaba después de eso.

Answer 2

Pruebe las clases de unordered de boost.

Answer 3

Eche un vistazo a boost.unordered, y es data structure.

Answer 4

¡Usar hashmaps en C++ es fácil! Es como usar el mapa C++ estándar. Puede usar la implementación del compilador/biblioteca de su unordered_map o usar la proporcionada por boost, o algún otro proveedor. Aquí hay una muestra rápida. Encontrarás más si sigues los enlaces que se te dieron.

#include <unordered_map> 
#include <string> 
#include <iostream> 

int main() 
{ 
    typedef std::tr1::unordered_map< std::string, int > hashmap; 
    hashmap numbers; 

    numbers["one"] = 1; 
    numbers["two"] = 2; 
    numbers["three"] = 3; 

    std::tr1::hash<std::string> hashfunc = numbers.hash_function(); 
    for(hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i) { 
     std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc(i->first) << ")" << std::endl; 
    } 
    return 0; 
} 

Answer 5

Salida Simple Hash Map (Hash Table) Implementation in C++ de una tabla hash básica con pares de valores clave de tipo genérico y la estrategia de encadenamiento separado.