unordered_dense
v4.5.0
Un hashmap y un hashset rápido y densamente almacenado basado en la eliminación de cambio hacia atrás de Robin-Hood para C ++ 17 y posterior.
Las clases ankerl::unordered_dense::map y ankerl::unordered_dense::set son (casi) reemplazos de std::unordered_map y std::unordered_set . Si bien no tienen garantías iterador / estabilidad de referencia tan fuertes, generalmente son mucho más rápidas.
Además, hay ankerl::unordered_dense::segmented_map y ankerl::unordered_dense::segmented_set con un uso de memoria máxima más baja. y iterador estable/referencias en insertar.
ankerl::unordered_dense::hashis_transparentstd::hashauto extract() && -> value_container_typeextract() elementos individuales[[nodiscard]] auto values() const noexcept -> value_container_type const&auto replace(value_container_type&& container)ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map y segmented_set El diseño elegido tiene algunas ventajas sobre std::unordered_map :
std::vector , ¡todos los datos son contiguos!absl::flat_hash_mapstd::allocators y asignadores polimórficos. Hay ankerl::unordered_dense::pmr typedefs disponiblesstd::vector para boost::interprocess::vector o cualquier otro contenedor de acceso aleatorio compatible.std::vector .No hay almuerzo gratis, por lo que hay algunas desventajas:
const Key en std::pair<Key, Value> La ubicación de instalación predeterminada es /usr/local .
Clone el repositorio y ejecute estos comandos en la carpeta clonada:
mkdir build && cd build
cmake ..
cmake --build . --target install Considere configurar un prefijo de instalación si no desea instalar el sistema unordered_dense de ancho, como así:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target installPara hacer uso de la biblioteca instalada, agregue esto a su proyecto:
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense) ankerl::unordered_dense admite módulos C ++ 20. Simplemente compile src/ankerl.unordered_dense.cpp y use el módulo resultante, por ejemplo, así:
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm Para usar el módulo con EG en module_test.cpp , use
import ankerl.unordered_dense;y compilar con EG
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main Se puede encontrar un script de demostración simple en test/modules .
ankerl::unordered_dense::hash es un hash rápida y de alta calidad, basado en Wyhash. El mapa ankerl::unordered_dense /set diferencia entre hashes de alta calidad (buen efecto de avalanchería) y mala calidad. Las hashes con buena calidad contienen un marcador especial:
using is_avalanching = void ; Estos son los casos para las especializaciones bool , char , signed char , unsigned char , char8_t , char16_t , char32_t , wchar_t , short , unsigned short , int , unsigned int , long , long long , unsigned long , unsigned long long , T* , std::unique_ptr<T> , std::shared_ptr<T> , enum , std::basic_string<C> :: std::basic_string_view<C> .
Se supone que los hash que no contienen dicho marcador son de mala calidad y reciben un paso de mezcla adicional dentro de la implementación de mapa/conjunto.
Considere un tipo de tecla personalizado simple:
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};La implementación más simple de un hash es esta:
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};Esto se puede usar, por ejemplo, con
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); Dado que custom_hash_simple no tiene un using is_avalanching = void; Marcador Se considera de mala calidad y la mezcla adicional de x.value se proporciona automáticamente dentro del conjunto.
Volver al ejemplo id , podemos implementar fácilmente un hash de mayor calidad:
struct custom_hash_avalanching {
using is_avalanching = void ;
auto operator ()(id const & x) const noexcept -> uint64_t {
return ankerl::unordered_dense::detail::wyhash::hash (x. value );
}
}; Sabemos wyhash::hash es de alta calidad, por lo que podemos agregar using is_avalanching = void; lo que hace que el mapa/set use directamente el valor devuelto.
ankerl::unordered_dense::hash En lugar de crear una nueva clase, también puede especializar ankerl::unordered_dense::hash :
template <>
struct ankerl ::unordered_dense::hash<id> {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(id const & x) const noexcept -> uint64_t {
return detail::wyhash::hash (x. value );
}
};is_transparent Este mapa/conjunto admite sobrecargas heterogéneas como se describe en P2363 que extiende contenedores asociativos con las sobrecargas heterogéneas restantes que está dirigida a C ++ 26. Esto tiene sobrecargas para find , count , contains , equal_range (ver p0919r3), erase (ver p2077R2) e try_emplace , insert_or_assign , operator[] , at y insert & emplace para conjuntos (ver P2363R3).
Para que las sobrecargas heterogéneas tengan efecto, tanto hasher como key_equal necesitan tener el atributo is_transparent SET.
Aquí hay una implementación de ejemplo que se puede utilizar con cualquier tipo de cadena que sea convertible en std::string_view (por ejemplo, char const* y std::string ):
struct string_hash {
using is_transparent = void ; // enable heterogeneous overloads
using is_avalanching = void ; // mark class as high quality avalanching hash
[[nodiscard]] auto operator ()(std::string_view str) const noexcept -> uint64_t {
return ankerl::unordered_dense::hash<std::string_view>{}(str);
}
}; Para hacer uso de este hash, deberá especificarlo como un tipo, y también como un key_equal con is_transparent como std :: igual_to <>:
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); Para obtener más información, consulte los ejemplos en test/unit/transparent.cpp .
std::hash Cuando hay disponible una implementación para std::hash de un tipo personalizado, esto se usa automáticamente y se supone que es de mala calidad (por lo tanto, se usa std::hash , pero se realiza un paso de mezcla adicional).
Cuando el tipo tiene una representación de objeto única (sin relleno, trivialmente copiado), se puede poner la memoria del objeto. Considere una clase simple
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};Se puede proporcionar fácilmente un hash rápido y de alta calidad:
struct custom_hash_unique_object_representation {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(point const & f) const noexcept -> uint64_t {
static_assert (std::has_unique_object_representations_v<point>);
return ankerl::unordered_dense::detail::wyhash::hash (&f, sizeof (f));
}
}; In addition to the standard std::unordered_map API (see https://en.cppreference.com/w/cpp/container/unordered_map) we have additional API that is somewhat similar to the node API, but leverages the fact that we're using a random access container internally:
auto extract() && -> value_container_type Extrae el contenedor usado internamente. *this se vacía.
extract() elementos individuales Similar a erase() Tengo un extract() . Se comporta exactamente lo mismo que erase , excepto que el valor de retorno es el elemento movido que se elimina del contenedor:
auto extract(const_iterator it) -> value_typeauto extract(Key const& key) -> std::optional<value_type>template <class K> auto extract(K&& key) -> std::optional<value_type> Tenga en cuenta que la API extract(key) devuelve un std::optional<value_type> que está vacío cuando no se encuentra la clave.
[[nodiscard]] auto values() const noexcept -> value_container_type const&Expone el contenedor de valores subyacentes.
auto replace(value_container_type&& container)Descarga el contenedor de retención internamente y lo reemplaza con el pasado. Se eliminan elementos no únicos, y el contenedor se reordenará en parte cuando se encuentren elementos no únicos.
unordered_dense acepta un asignador personalizado, pero también puede especificar un contenedor personalizado para ese argumento de plantilla. De esa manera, es posible reemplazar el std::vector con EG std::deque o cualquier otro contenedor como boost::interprocess::vector . Esto admite punteros elegantes (por ejemplo, offset_ptr), por lo que el contenedor se puede usar con la memoria compartida de EG proporcionada por boost::interprocess .
El mapa/set admite dos tipos de deseos diferentes. El valor predeterminado debería ser bueno para casi todos.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map y segmented_set ankerl::unordered_dense proporciona una implementación de contenedores personalizado que tiene requisitos de memoria más bajos que el std::vector . La memoria no es contigua, pero puede asignar segmentos sin tener que reasignar y mover todos los elementos. En resumen, esto lleva a
std::vector porque se necesita una indirección adicional. Aquí hay una comparación contra absl::flat_hash_map y el ankerl::unordered_dense::map al insertar 10 millones de entradas 
Abseil es más rápido para esta simple prueba de inserción, tomando un poco más de 0.8 segundos. Su uso de memoria máxima es de aproximadamente 430 MB. Tenga en cuenta cómo disminuye el uso de la memoria después del último pico; Cuando se reduce a ~ 290 MB, ha terminado de volver a modificar y podría liberar el bloque de memoria utilizado anteriormente.
ankerl::unordered_dense::segmented_map no tiene estos picos, y en su lugar tiene un aumento suave del uso de la memoria. Tenga en cuenta que todavía hay caídas y aumentos repentinos en la memoria porque la estructura de datos de indexación aún debe aumentar en un factor fijo. Pero debido a que mantiene los datos en un contenedor separado, primero podemos liberar la estructura de datos anterior y luego asignar una nueva estructura de indexación más grande; Por lo tanto, no tenemos picos.
El mapa/conjunto tiene dos estructuras de datos:
std::vector<value_type> que contiene todos los datos. map/set iterators son solo std::vector<value_type>::iterator ! Cada vez que se agrega un elemento, es emplace_back al vector. La llave está hash y se agrega una entrada (cubo) en la ubicación correspondiente en la matriz de cubo. El cubo tiene esta estructura:
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};Cada cubo almacena 3 cosas:
dist_and_fingerprint )dist_and_fingerprint )Esta estructura está especialmente diseñada para la estrategia de resolución de colisión Robin-Hood hashing con eliminación de cambio hacia atrás.
La llave está hash y la matriz de cubos se busca si tiene una entrada en esa ubicación con esa huella digital. Cuando se encuentra, se compara la clave en el vector de datos y, cuando es igual, se devuelve el valor.
Dado que todos los datos se almacenan en un vector, las eliminaciones son un poco más complicadas:
value_idx del elemento movido. Esto requiere otra búsqueda. El 2023-09-10 hice una búsqueda rápida en GitHub para ver si este mapa se usa en algún proyecto de código abierto populares. Estos son algunos de los proyectos que encontré. ¡Por favor envíeme una nota si lo desea en esa lista!
