Implementación simple de hashmap en C ++

Question

Soy relativamente nuevo en C ++. En Java, es fácil para mí crear instancias y usar un hashmap. Me gustaría saber cómo hacerlo de manera simple 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 , formará parte de la biblioteca estándar como std :: unordered_map . La Página STL en ella es bastante estándar. Si usa Visual Studio, Microsoft tiene una página en ella.

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

Suponiendo que su clase se llama MyClass y ya ha definido:

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

Deberá definir dos functores para ajustar esos métodos en 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 cree una instancia de 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 espera después de eso.

Answer 2

¡Usar hashmaps en C ++ es fácil! Es como usar un mapa estándar de C ++. Puede usar la implementación de su compilador / biblioteca de unordered_map o usar la proporcionada por boost , o algún otro proveedor. Aquí hay una muestra rápida. Encontrará más si sigue los enlaces que se le 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 3

Eche un vistazo a boost.unordered , y su estructura de datos .

Answer 4

Pruebe las clases no ordenadas de boost. p>

Answer 5

Echa un vistazo a Implementación de mapa hash simple (tabla hash) en C ++ para obtener una tabla hash básica con clave de tipo genérico pares de valores y estrategia de encadenamiento separada.