Descargar robin hood hashing - Descargar código fuente robin hood hashing Descarga

robin hood hashing

C/C++

3.11.5

Descargar

➵ Robin_hood mapa y establecimiento

Nota: Desafortunadamente, no tengo tiempo para continuar el desarrollo de este hashmap. Sin embargo, tengo un digno sucesor, por favor diríjase a: ankerl::unordered_dense::{map, set}

He pasado mucho tiempo desarrollándolo y mejorándolo robin_hood , y funciona bastante bien para la mayoría de los casos de uso. Ya no realizaré ninguna actualización de este código, a menos que sean PR para correcciones críticas de errores.

robin_hood::unordered_map y robin_hood::unordered_set es un reemplazo independiente de la plataforma para std::unordered_map / std::unordered_set que es más rápido y más eficiente en la memoria para los casos de uso del mundo real.

Instalación y uso

Inclusión directa

Agregue robin_hood.h a su proyecto C ++.
Use robin_hood::unordered_map en lugar de std::unordered_map
Usar robin_hood::unordered_set en lugar de std::unordered_set

Conan, el administrador de paquetes C/C ++

Configurar su CMakeLists.txt (consulte la documentación de Conan sobre cómo usar MSBuild, Meson y otros) como esta:

 project (myproject CXX)

add_executable ( ${PROJECT_NAME} main.cpp)

include ( ${CMAKE_BINARY_DIR} /conanbuildinfo.cmake) # Include Conan-generated file
conan_basic_setup(TARGETS) # Introduce Conan-generated targets

target_link_libraries ( ${PROJECT_NAME} CONAN_PKG::robin-hood-hashing)

Cree conanfile.txt en su Dir de origen (no olvide actualizar la versión)
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
Instale y ejecute Conan, luego construya su proyecto como siempre:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
El paquete robin-hood-hashing en Conan se mantiene actualizado por los contribuyentes de Conan. Si la versión está desactualizada, cree un problema o extraiga la solicitud en el repositorio conan-center-index .

Puntos de referencia

Consulte los puntos de referencia extensos en los puntos de referencia de Hashmaps. En resumen: robin_hood siempre se encuentra entre los mapas más rápidos y usa mucha menos memoria que std::unordered_map .

Opciones de diseño

Dos diseños de memoria . Los datos se almacenan en una matriz plana o con indirección del nodo. El acceso para unordered_flat_map es extremadamente rápido debido a que no hay indirección, pero las referencias a los elementos no son estables. También causa picos de asignación cuando el mapa cambia de tamaño, y necesitará mucha memoria para objetos grandes. El mapa basado en el nodo tiene referencias y punteros estables (¡no iteradores! Similar a std :: unordered_map) y usa const Key en el par. Es un poco más lento debido a la indirección. La elección es tuya; Puede usar robin_hood::unordered_flat_map o robin_hood::unordered_node_map directamente. Si usa robin_hood::unordered_map intenta elegir el diseño que parece apropiado para sus datos.
Asignador personalizado . La representación basada en el nodo tiene un asignador a granel personalizado que intenta hacer pocas asignaciones de memoria. Toda la memoria asignada se reutiliza, por lo que no habrá ningún pico de asignación. También es muy rápido.
Hash optimizado . robin_hood::hash tiene implementaciones personalizadas para tipos enteros y para std::string que son muy rápidas y vuelven a std::hash para todo lo demás.
Depende del buen hash . Para un hash realmente malo, el rendimiento no solo se degradará como en std::unordered_map , el mapa simplemente fallará con un std::overflow_error . En la práctica, al usar el estándar robin_hood::hash , nunca he visto que esto suceda.