robin map

Una implementación en C++ de un mapa hash rápido y un conjunto de hash usando hash de Robin Hood

La biblioteca robin-map es una implementación en C++ de un mapa hash rápido y un conjunto de hash que utiliza hash Robin Hood lineal y de direccionamiento abierto con eliminación por desplazamiento hacia atrás para resolver colisiones.

Se proporcionan cuatro clases: tsl::robin_map , tsl::robin_set , tsl::robin_pg_map y tsl::robin_pg_set . Los dos primeros son más rápidos y utilizan una política de crecimiento de poder de dos, los dos últimos utilizan una política de crecimiento principal y son capaces de hacer frente mejor a una función hash deficiente. Utilice la versión principal si existe la posibilidad de que se repitan patrones en los bits inferiores de su hash (por ejemplo, si está almacenando punteros con una función de hash de identidad). Consulte GrowthPolicy para obtener más detalles.

Puede encontrar una referencia de tsl::robin_map frente a otros mapas hash aquí. Esta página también brinda algunos consejos sobre qué estructura de tabla hash debería probar para su caso de uso (útil si está un poco perdido con las múltiples implementaciones de tablas hash en el espacio de nombres tsl ).

Características clave

• Biblioteca de solo encabezado, simplemente agregue el directorio de inclusión a su ruta de inclusión y estará listo para comenzar. Si usa CMake, también puede usar el destino exportado tsl::robin_map desde CMakeLists.txt.

• Tabla hash rápida, consulte el punto de referencia para ver algunos números.

• Soporte para clave/valor construible de solo movimiento y no predeterminado.

• Soporte para búsquedas heterogéneas que permiten el uso de find con un tipo diferente a Key (por ejemplo, si tiene un mapa que usa std::unique_ptr<foo> como clave, puede usar foo* o std::uintptr_t como parámetro clave para find sin construir un std::unique_ptr<foo> , ver ejemplo).

• No es necesario reservar ningún valor centinela de las claves.

• Posibilidad de almacenar el valor hash junto con el valor-clave almacenado para una repetición y búsqueda más rápidas si el hash o las funciones iguales de clave son costosas de calcular. Tenga en cuenta que el hash puede almacenarse incluso si no se pregunta explícitamente cuando la biblioteca puede detectar que no tendrá ningún impacto en el tamaño de la estructura en la memoria debido a la alineación. Consulte el parámetro de plantilla StoreHash para obtener más detalles.

• Si se conoce el hash antes de una búsqueda, es posible pasarlo como parámetro para acelerar la búsqueda (consulte el parámetro precalculated_hash en API).

• Soporte para serialización y deserialización eficientes (consulte el ejemplo y los métodos serialize/deserialize en la API para obtener más detalles).

• La biblioteca se puede usar con las excepciones deshabilitadas (a través de la opción -fno-exceptions en Clang y GCC, sin una opción /EH en MSVC o simplemente definiendo TSL_NO_EXCEPTIONS ). std::terminate se usa en reemplazo de la instrucción throw cuando las excepciones están deshabilitadas.

• API muy similar a std::unordered_map y std::unordered_set .

Diferencias en comparación con std::unordered_map

tsl::robin_map intenta tener una interfaz similar a std::unordered_map , pero existen algunas diferencias.

• La garantía de excepción fuerte solo se cumple si la siguiente declaración es verdadera std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (donde value_type es Key para tsl::robin_set y std::pair<Key, T> para tsl::robin_map ). De lo contrario, si se produce una excepción durante el intercambio o el movimiento, la estructura puede terminar en un estado indefinido. Tenga en cuenta que, según el estándar, un value_type con un constructor de copia noexcept y un constructor sin movimiento también satisface esta condición y, por lo tanto, garantizará una fuerte garantía de excepción para la estructura (consulte la API para obtener más detalles).

• El tipo Key y también T en el caso de map, deben ser intercambiables. También deben ser construibles para copiar y/o mover.

• La invalidación de iteradores no se comporta de la misma manera, cualquier operación que modifique la tabla hash los invalida (consulte la API para obtener más detalles).

• Las referencias y punteros a claves o valores en el mapa se invalidan de la misma manera que los iteradores a estas claves-valor.

• Para iteradores de tsl::robin_map , operator*() y operator->() devuelven una referencia y un puntero a const std::pair<Key, T> en lugar de std::pair<const Key, T> creando el valor T modificable. Para modificar el valor, debe llamar al método value() del iterador para obtener una referencia mutable. Ejemplo:

 tsl::robin_map<int, int> mapa = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ; ++it) {//it->segundo = 2; // Ilegalit.value() = 2; // De acuerdo}

• No hay soporte para algunos métodos relacionados con depósitos (como bucket_size , bucket , ...).

Estas diferencias también se aplican entre std::unordered_set y tsl::robin_set .

Las garantías de seguridad de subprocesos son las mismas que std::unordered_map/set (es decir, es posible tener varios lectores sin escritor).

Política de crecimiento

La biblioteca admite múltiples políticas de crecimiento a través del parámetro de plantilla GrowthPolicy . La biblioteca proporciona tres políticas, pero usted puede implementar fácilmente las suyas propias si es necesario.

• tsl::rh::poder_de_dos_políticas_de_crecimiento. Política predeterminada utilizada por tsl::robin_map/set . Esta política mantiene el tamaño de la matriz de depósitos de la tabla hash en una potencia de dos. Esta restricción permite que la política evite el uso de la operación de módulo lento para asignar un hash a un depósito; en lugar de hash % 2 n , utiliza hash & (2 n - 1) (consulte módulo rápido). Rápido, pero esto puede causar muchas colisiones con una función hash deficiente, ya que el módulo con una potencia de dos solo enmascara los bits más significativos al final.

• tsl::rh::prime_growth_policy. Política predeterminada utilizada por tsl::robin_pg_map/set . La política mantiene el tamaño de la matriz de depósitos de la tabla hash en un número primo. Al asignar un hash a un depósito, el uso de un número primo como módulo dará como resultado una mejor distribución del hash entre los depósitos, incluso con una función hash deficiente. Para permitir que el compilador optimice la operación del módulo, la política utiliza una tabla de búsqueda con módulos primos constantes (consulte la API para obtener más detalles). Más lento que tsl::rh::power_of_two_growth_policy pero más seguro.

• tsl::rh::mod_growth_policy. La política hace crecer el mapa mediante un factor de crecimiento personalizable pasado en el parámetro. Luego simplemente usa el operador de módulo para asignar un hash a un depósito. Más lento pero más flexible.

Para implementar su propia política, debe implementar la siguiente interfaz.

 struct custom_policy {// Se llama en la construcción y repetición de la tabla hash, min_bucket_count_in_out son los depósitos mínimos// que necesita la tabla hash. La política puede cambiarlo a una cantidad mayor de depósitos si es necesario // y la tabla hash usará este valor como recuento de depósitos. Si se solicita 0 depósito, entonces el valor // debe permanecer en 0.explicit custom_policy(std::size_t& min_bucket_count_in_out);    // Devuelve el depósito [0, bucket_count()) al que pertenece el hash. // Si bucket_count() es 0, siempre debe devolver 0.std::size_t bucket_for_hash(std::size_t hash) const noexcept;    // Devuelve el número de depósitos que se deben utilizar en el siguiente crecimientostd::size_t next_bucket_count() const;    // Número máximo de depósitos admitidos por la políticastd::size_t max_bucket_count() const;    // Restablece la política de crecimiento como si la política se hubiera creado con un recuento de depósitos de 0.// Después de borrar, la política siempre debe devolver 0 cuando se llama a bucket_for_hash().void clear() noexcept;
}

Instalación

Para usar robin-map, simplemente agregue el directorio de inclusión a su ruta de inclusión. Es una biblioteca de solo encabezados .

Si usa CMake, también puede usar el destino exportado tsl::robin_map desde CMakeLists.txt con target_link_libraries .

 # Ejemplo donde el proyecto robin-map se almacena en un directorio de terceros add_subdirectory(terceros/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)

Si el proyecto se instaló mediante make install , también puede usar find_package(tsl-robin-map REQUIRED) en lugar de add_subdirectory .

La biblioteca está disponible en vcpkg y conan. También está presente en los repositorios de paquetes de Debian, Ubuntu y Fedora.

El código debería funcionar con cualquier compilador compatible con el estándar C++17.

Para ejecutar las pruebas necesitará la biblioteca Boost Test y CMake.

 clon de git https://github.com/Tessil/robin-map.gitcd robin-map/tests
mkdir buildcd construir
cmake..
cmake --build ../tsl_robin_map_tests

Uso

La API se puede encontrar aquí.

Todos los métodos aún no están documentados, pero replican el comportamiento de los de std::unordered_map y std::unordered_set , excepto si se especifica lo contrario.

Ejemplo

 #include <cstdint>#include <iostream>#include <string>#include <tsl/robin_map.h>#include <tsl/robin_set.h>int main() {
    tsl::robin_map<std::string, int> mapa = {{"a", 1}, {"b", 2}};
    mapa["c"] = 3;
    mapa["d"] = 4;

        mapa.insert({"e", 5});
    mapa.erase("b");    for(auto it = map.begin(); it != map.end(); ++it) {//it->segundo += 2; // No válido.it.value() += 2;
    } // {d, 6} {a, 3} {e, 7} {c, 5}for(const auto& key_value: mapa) {
        std::cout << "{" << valor_clave.primero << ", " << valor_clave.segundo << "}" << std::endl;
    }
            if(mapa.find("a") != mapa.end()) {
        std::cout << "Encontrado "a"." << std::endl;
    } const std::size_t precalculated_hash = std::hash<std::string>()("a");// Si ya conocemos el hash de antemano, podemos pasarlo como parámetro para acelerar las búsquedas.if( map.find("a", precalculated_hash) != map.end()) {
        std::cout << "Encontré "a" con hash " << precalculated_hash << "." << std::endl;
    }
        /* * Calcular el hash y comparar dos std::string puede ser lento.      * Podemos almacenar el hash de cada std::string en el mapa hash para hacer * las inserciones y búsquedas más rápidas configurando StoreHash en verdadero.     */
     tsl::robin_map<std::string, int, std::hash<std::string>,
                    std::equal_to<std::cadena>,
                   std::allocator<std::pair<std::string, int>>, true> map2;

                           mapa2["a"] = 1;
    mapa2["b"] = 2;    // {a, 1} {b, 2}for(const auto& valor_clave: mapa2) {
        std::cout << "{" << valor_clave.primero << ", " << valor_clave.segundo << "}" << std::endl;
    }




                    tsl::robin_set<int> conjunto;
    set.insert({1, 9, 0});
    set.insert({2, -1, 9});    // {0} {1} {2} {9} {-1}for(const auto& clave: establecer) {
        std::cout << "{" << clave << "}" << std::endl;
    }
}

Búsquedas heterogéneas

Las sobrecargas heterogéneas permiten el uso de otros tipos además de Key para operaciones de búsqueda y borrado, siempre que los tipos utilizados sean hash y comparables a Key .

Para activar las sobrecargas heterogéneas en tsl::robin_map/set , el ID calificado KeyEqual::is_transparent debe ser válido. Funciona de la misma manera que para std::map::find . Puede usar std::equal_to<> o definir su propio objeto de función.

Tanto KeyEqual como Hash deberán poder manejar los diferentes tipos.

 #include <funcional>#include <iostream>#include <cadena>#include <tsl/robin_map.h>estructura empleado {empleado(int id, std::nombre de cadena): m_id(id), m_name(std::move (nombre)) {
    } // O incluimos los comparadores en la clase y usamos `std::equal_to<>`...friend bool operator==(const empleado& empl, int empl_id) {return empl.m_id == empl_id;
    } amigo operador bool==(int empl_id, const empleado& empl) {return empl_id == empl.m_id;
    } amigo operador bool==(empleado constante& empl1, empleado const& empl2) {return empl1.m_id == empl2.m_id;
    }
        intm_id;
    std::string m_name;
};// ... o implementamos una clase separada para comparar empleados.struct equal_employee {using is_transparent = void;    operador bool()(const empleado& empl, int empl_id) const {return empl.m_id == empl_id;
    } bool operador()(int empl_id, const empleado& empl) const {return empl_id == empl.m_id;
    } bool operador()(const empleado& empl1, const empleado& empl2) const {return empl1.m_id == empl2.m_id;
    }
};struct hash_employee {
    std::size_t operator()(const empleado& empl) const {return std::hash<int>()(empl.m_id);
    }

        std::size_t operador()(int id) const {return std::hash<int>()(id);
    }
};int main() {// Utilice std::equal_to<> que deducirá y reenviará automáticamente los parámetrostsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
     map.insert({empleado(1, "John Doe"), 2001});
    map.insert({empleado(2, "Jane Doe"), 2002});
    map.insert({empleado(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it!= map.end()) {
        std::cout << it->primero.m_name << " " << it->segundo << std::endl;
    }

    map.erase(1);// Utilice un KeyEqual personalizado que tenga un miembro is_transparent typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
    map2.insert({empleado(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}

Publicación por entregas

La biblioteca proporciona una forma eficaz de serializar y deserializar un mapa o un conjunto para poder guardarlo en un archivo o enviarlo a través de la red. Para hacerlo, requiere que el usuario proporcione un objeto de función tanto para la serialización como para la deserialización.

 serializador de estructuras {// Debe admitir los siguientes tipos para U: std::int16_t, std::uint32_t, // std::uint64_t, float y std::pair<Key, T> si se usa un mapa o Key para / / a set.template<typename U>void operator()(const U& valor);
};

 struct deserializer {// Debe admitir los siguientes tipos para U: std::int16_t, std::uint32_t, // std::uint64_t, float y std::pair<Key, T> si se usa un mapa o Key para / /a set.template<tiponombre U>
    Operador U()();
};

Tenga en cuenta que la implementación deja la compatibilidad binaria (endianidad, representación binaria flotante, tamaño de int, ...) de los tipos que serializa/deserializa en manos de los objetos de función proporcionados si se requiere compatibilidad.

Se pueden encontrar más detalles sobre los métodos serialize y deserialize en la API.

 #include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h>serializador de clases {público:serializador(const char* nombre_archivo) {
        m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
        m_ostream.open(nombre_archivo, std::ios::binary);
    } plantilla<clase T, nombre de tipo std::enable_if<std::is_arithmetic<T>::valor>::tipo* = nullptr>void operator()(const T& valor) {
        m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
    } operador vacío()(const std::pair<std::int64_t, std::int64_t>& valor) {
        (*este)(valor.primero);
        (*este)(valor.segundo);
    }privado:std::ofstream m_ostream;
};clase deserializador {público:deserializador(const char* nombre_archivo) {
        m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
        m_istream.open(nombre_archivo, std::ios::binary);
    } plantilla<clase T>
    operador T()() {
        Valor T; deserializar (valor);        valor de retorno;
    }
    privado:plantilla<clase T, nombre de tipo std::enable_if<std::is_arithmetic<T>::valor>::tipo* = nullptr>void deserialize(T& valor) {
        m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
    } void deserialize(std::pair<std::int64_t, std::int64_t>& valor) {deserialize(value.first);deserialize(value.segundo);
    }privado:std::ifstream m_istream;
};int main() {const tsl::robin_map<std::int64_t, std::int64_t> mapa = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
        const char* nombre_archivo = "robin_map.data";
    {
        serializador serial(nombre_archivo);
        map.serialize(serie);
    }

        {
        deserializador dserial(nombre_archivo);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial);        afirmar (mapa == map_deserialized);
    }

        {
        deserializador dserial(nombre_archivo);        /** * Si el mapa serializado y deserializado son compatibles con hash (consulte las condiciones en API), * establecer el argumento en verdadero acelera el proceso de deserialización ya que no tenemos * que recalcular el hash de cada clave. También sabemos cuánto espacio necesita cada cubo.         */const bool hash_compatible = verdadero;auto map_deserialized =
             tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_compatible);        afirmar (mapa == map_deserialized);
    }
}

Serialización con Boost Serialización y compresión con zlib

Es posible utilizar una biblioteca de serialización para evitar el texto repetitivo.

El siguiente ejemplo utiliza Boost Serialization con el flujo de compresión Boost zlib para reducir el tamaño del archivo serializado resultante. El ejemplo requiere C++20 debido al uso de la sintaxis de la lista de parámetros de plantilla en lambdas, pero se puede adaptar a versiones menos recientes.

 #include <boost/archive/binary_iarchive.hpp>#include <boost/archive/binary_oarchive.hpp>#include <boost/iostreams/filter/zlib.hpp>#include <boost/iostreams/filtering_stream.hpp>#include <boost /serialización/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>impulso del espacio de nombres { serialización del espacio de nombres {plantilla<archivo de clase, clave de clase, clase T> void serialize(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int version) {split_free(ar, mapa, versión);
     }plantilla<archivo de clase, clave de clase, clase T>void save(Archive & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto serializer = [&ar](const auto&v) { ar&v; };
        map.serialize(serializador);
    }plantilla<archivo de clase, clave de clase, clase T>void load(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { U u; ar & u; devolverte; };
        map = tsl::robin_map<Clave, T>::deserialize(deserializador);
    }
}}int principal() {
    tsl::robin_map<std::int64_t, std::int64_t> mapa = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
        const char* nombre_archivo = "robin_map.data";
    {
        std::ofstream des;
        ofs.exceptions(ofs.badbit | ofs.failbit);
        ofs.open(nombre_archivo, std::ios::binary);

                impulso::iostreams::filtering_ostream fo;
        fo.push(boost::iostreams::zlib_compressor());
        fo.push(ofs);

                impulso::archivo::binary_oarchive oa(fo);

                oa << mapa;
    }

        {
        std::ifstream si;
        ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
        ifs.open(nombre_archivo, std::ios::binary);

                impulso::iostreams::filtrado_istream fi;
        fi.push(boost::iostreams::zlib_decompressor());
        fi.push(si);

                impulso::archivo::binary_iarchive ia(fi);

             tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
           ia >> map_deserialized;        afirmar (mapa == map_deserialized);
    }
}

Errores de rendimiento

Son dignos de mención dos posibles problemas de rendimiento relacionados con tsl::robin_map y tsl::robin_set :

1. Malos hashes . Las funciones hash que producen muchas colisiones pueden provocar el siguiente comportamiento sorprendente: cuando el número de colisiones excede un cierto umbral, la tabla hash se expandirá automáticamente para solucionar el problema. Sin embargo, en casos degenerados, esta expansión podría no tener ningún efecto en el recuento de colisiones, provocando un modo de falla en el que una secuencia lineal de inserción conduce a un crecimiento exponencial del almacenamiento.

   Este caso se ha observado principalmente cuando se utiliza la estrategia de crecimiento predeterminada de potencia de dos con el STL predeterminado std::hash<T> para tipos aritméticos T , que a menudo es una identidad. Consulte el número 39 para ver un ejemplo. La solución es simple: use una mejor función hash y/o tsl::robin_pg_set / tsl::robin_pg_map .

2. Borrado de elementos y factores de carga bajos . tsl::robin_map y tsl::robin_set reflejan la API STL map/set, que expone un método iterator erase(iterator) que elimina un elemento en una posición determinada, devolviendo un iterador válido que apunta al siguiente elemento.

   La construcción de este nuevo objeto iterador requiere caminar hasta el siguiente depósito no vacío de la tabla, lo que puede ser una operación costosa cuando la tabla hash tiene un factor de carga bajo (es decir, cuando capacity() es mucho mayor que size() ).

   Además, el método erase() nunca reduce ni vuelve a aplicar hash a la tabla, ya que la especificación de esta función no lo permite. Una secuencia lineal de eliminaciones aleatorias sin inserciones intermedias puede conducir a un caso degenerado con un coste de tiempo de ejecución cuadrático.

   En tales casos, a menudo ni siquiera se necesita un valor de retorno del iterador, por lo que el costo es completamente innecesario. Por lo tanto, tanto tsl::robin_set como tsl::robin_map proporcionan un método de borrado alternativo void erase_fast(iterator) que no devuelve un iterador para evitar tener que encontrar el siguiente elemento.

Licencia

El código tiene la licencia MIT; consulte el archivo LICENCIA para obtener más detalles.