mapa - ¿Cuál es la mejor manera de usar un HashMap en C++?

string map c++

Question

Sé que STL tiene una API de HashMap, pero no puedo encontrar ninguna documentación buena y exhaustiva con buenos ejemplos al respecto.

Cualquier buen ejemplo será apreciado.

Answer 1

Aquí hay un ejemplo más completo y flexible que no omite las inclusiones necesarias para generar errores de compilación:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Todavía no es particularmente útil para las claves, a menos que estén predefinidas como punteros, ¡porque un valor coincidente no funcionará! (Sin embargo, dado que normalmente uso cadenas para las claves, sustituir "cadena" por "const void *" en la declaración de la clave debería resolver este problema).

Answer 2

Un hash_map es una versión anterior no estandarizada de lo que para propósitos de estandarización se llama unordered_map (actualmente disponible como parte de TR1, y se incluirá en C ++ 0x). Como su nombre lo indica, es diferente de std::map principalmente al estar desordenado: si, por ejemplo, itera a través de un mapa desde begin() hasta end() , obtiene los elementos en orden por la clave ¹ , pero si itera a través de un unordered_map desde el begin() hasta el end() , obtienes elementos en un orden más o menos arbitrario.

Normalmente, se espera que un unordered_map tenga una complejidad constante. Es decir, una inserción, búsqueda, etc., toma esencialmente una cantidad fija de tiempo, independientemente de cuántos elementos hay en la tabla. Un std::map tiene una complejidad que es logarítmica en la cantidad de elementos que se almacenan, lo que significa que el tiempo para insertar o recuperar un elemento crece, pero muy lentamente , a medida que el mapa crece. Por ejemplo, si se necesita 1 microsegundo para buscar uno de 1 millón de elementos, entonces puede esperar que tome alrededor de 2 microsegundos para buscar uno de los 2 millones de elementos, 3 microsegundos para uno de 4 millones de elementos, 4 microsegundos para uno de 8 millones artículos, etc.

Desde un punto de vista práctico, sin embargo, esa no es toda la historia. Por naturaleza, una tabla de hash simple tiene un tamaño fijo. Adaptarlo a los requisitos de tamaño variable para un contenedor de propósito general es algo no trivial. Como resultado, las operaciones que (potencialmente) crecen o reducen la tabla (por ejemplo, inserción y eliminación) a menudo son relativamente lentas. Las búsquedas, que no pueden cambiar el tamaño de la tabla, generalmente son mucho más rápidas. Como resultado, la mayoría de las tablas basadas en hash tienden a estar en su mejor momento cuando haces muchas búsquedas y relativamente pocas inserciones y eliminaciones. Para las situaciones en las que inserta una gran cantidad de datos, luego itera una vez para obtener resultados (p. Ej., Contar el número de palabras únicas en un archivo), es probable que un std::map sea ​​igual de rápido, y muy posiblemente incluso Más rápido.

¹ Donde el orden está definido por el tercer parámetro de plantilla cuando crea el mapa, std::less<T> de forma predeterminada.

Answer 3

Cómo usar una clase personalizada y una función hash con unordered_map

Esta respuesta lo clava: C ++ unordered_map usando un tipo de clase personalizado como la clave

Extracto: igualdad:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Función hash:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Answer 4

El STL incluye los contenedores del mapa ordenado y desordenado ( std::map y std::unordered_map ). En un mapa ordenado, los elementos se ordenan por la clave, insert y el acceso está en O (log n)). Por lo general, el STL usa internamente árboles negros rojos para mapas ordenados. Pero esto es solo un detalle de implementación. En un mapa desordenado, el inserto y el acceso están en O (1). Es solo otro nombre para una tabla hash.

Un ejemplo con (pedido) std::map :

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!/n";
  // retrieve
  std::cout << m["hello"] << ''/n'';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << ''/n'';
  return 0;
}

Salida:

23 Key: hello Value: 23

Si necesita ordenar en su contenedor y está bien con el tiempo de ejecución O (log n), simplemente use std::map .

De lo contrario, si realmente necesita una tabla hash (O (1) inserción / acceso), consulte std::unordered_map , que tiene una API similar a std::map (por ejemplo, en el ejemplo anterior solo tiene que buscar y reemplazar map con unordered_map ).

El contenedor unordered_map se introdujo con la revisión estándar de C ++ 11 . Por lo tanto, dependiendo de su compilador, debe habilitar las características de C ++ 11 (por ejemplo, al usar GCC 4.8, debe agregar -std=c++11 a CXXFLAGS).

Incluso antes de la liberación de C ++ 11, GCC soportaba unordered_map - en el espacio de nombres std::tr1 . Por lo tanto, para los viejos compiladores GCC puede intentar usarlo así:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

También es parte del impulso, es decir, puede usar el boost-header correspondiente para una mejor portabilidad.