unordered_set - unordered_map c++ example

Función Hash C++ para cadena en unordered_map

Question

Parece que C ++ no tiene una función hash para cadenas en la biblioteca estándar. ¿Es esto cierto?

¿Cuál es un ejemplo práctico de utilizar una cadena como clave en un mapa desordenado que funcionará con cualquier compilador de c ++?

Answer 1

C ++ STL proporciona specializations de plantillas de std::hash para las diversas clases de cadenas. Solo podría especificar std::string como tipo de clave para std::unordered_map :

#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> map;
    map["string"] = 10;
    return 0;
}

Answer 2

En mi caso, fue realmente una distracción.

Tenía un tipo X para el que implementé el hashing para const & X y lo utilicé en alguna parte con

std::unordered_map<const X, int> m_map;

Luego quería tener otro mapa cuyas claves son del tipo X y lo hicieron:

std::unordered_map<X, int> map_x;

Observe la FALTA de const en el segundo caso.

Answer 3

En realidad, hay std::hash<std::string>

Pero ahí está cómo puedes usar otra función hash:

struct StringHasher {
    size_t operator()(const std::string& t) const {
          //calculate hash here.
    }
}

unordered_map<std::string, ValueType, StringHasher>

Answer 4

Me encontré con esto hoy (en realidad con wstring , no con string , pero es el mismo trato): el uso de wstring como clave en unordered_map genera un error sobre la ausencia de función hash disponible para ese tipo.

La solución para mí fue agregar:

#include <string>

Lo creas o no, sin el include todavía tenía el tipo de wstring disponible pero aparentemente NO las funciones auxiliares como el hash. Simplemente agregando el include de arriba lo solucionó.

Answer 5

Si tiene un CustomType y desea conectarse a la infraestructura de STL, esto es lo que podría hacer.

namespace std
{
//namespace tr1
//{
    // Specializations for unordered containers

    template <>
    struct hash<CustomType> : public unary_function<CustomType, size_t>
    {
        size_t operator()(const CustomType& value) const
        {
            return 0;
        }
    };

//} // namespace tr1

template <>
struct equal_to<CustomType> : public unary_function<CustomType, bool>
{
    bool operator()(const CustomType& x, const CustomType& y) const
    {
        return false;
    }
};

} // namespace std

Si luego quieres crear say a std::unordered_map<CustomType> el STL encontrará las funciones hash e equal_to sin que tengas que hacer nada más con la plantilla. Así es como me gusta escribir mi comparador de igualdad personalizado que admite estructuras de datos desordenadas.