unordered_dense
v4.5.0
Um hashmap e hashset rápido e densamente armazenados com base na exclusão de mudança para trás de Robin-Hood para C ++ 17 e posteriormente.
As classes ankerl::unordered_dense::map e ankerl::unordered_dense::set são (quase) substituições de std::unordered_map e std::unordered_set . Embora eles não tenham garantias tão fortes de estabilidade / referência, elas geralmente são muito mais rápidas.
Além disso, existem ankerl::unordered_dense::segmented_map e ankerl::unordered_dense::segmented_set com uso de memória de pico mais baixo. e iterador/referências estáveis no inserto.
ankerl::unordered_dense::hashis_transparentstd::hashauto extract() && -> value_container_typeextract() elementos únicos[[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 e segmented_set O design escolhido tem algumas vantagens sobre std::unordered_map :
std::vector , todos os dados são contíguos!absl::flat_hash_mapstd::allocators e alocadores polimórficos. Existem ankerl::unordered_dense::pmr typedefsstd::vector para boost::interprocess::vector ou qualquer outro contêiner de acesso aleatório compatível.std::vector .Não há almoço grátis, então existem algumas desvantagens:
const Key em std::pair<Key, Value> O local de instalação padrão é /usr/local .
Clone o repositório e execute esses comandos na pasta clonada:
mkdir build && cd build
cmake ..
cmake --build . --target install Considere definir um prefixo de instalação se você não quiser instalar o sistema unordered_dense em grande parte, assim:
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target installPara usar a biblioteca instalada, adicione isso ao seu projeto:
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense) ankerl::unordered_dense suporta módulos C ++ 20. Basta compilar src/ankerl.unordered_dense.cpp e usar o módulo resultante, por exemplo, assim:
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 o módulo com EG em module_test.cpp , use
import ankerl.unordered_dense;e compilar com por exemplo
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main Um script de demonstração simples pode ser encontrado em test/modules .
ankerl::unordered_dense::hash é um hash rápido e de alta qualidade, baseado em Wyhash. O mapa/conjunto ankerl::unordered_dense diferencia entre hashes de alta qualidade (bom efeito de avalanching) e má qualidade. Hashes com boa qualidade contêm um marcador especial:
using is_avalanching = void ; This is the cases for the specializations 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> , e std::basic_string_view<C> .
Os hashes que não contêm esse marcador são considerados de má qualidade e recebem uma etapa de mistura adicional dentro da implementação do mapa/conjunto.
Considere um tipo simples de chave personalizado:
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};A implementação mais simples de um hash é a seguinte:
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};Isso pode ser usado, por exemplo, com
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); Como custom_hash_simple não possui um using is_avalanching = void; Marcador é considerado de má qualidade e a mistura adicional de x.value é automaticamente fornecida dentro do conjunto.
De volta ao exemplo id , podemos implementar facilmente um hash de alta qualidade:
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 que wyhash::hash é de alta qualidade, para que possamos adicionar using is_avalanching = void; O que faz com que o mapa/conjunto use diretamente o valor retornado.
ankerl::unordered_dense::hash Em vez de criar uma nova classe, você também pode 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 suporta sobrecargas heterogêneas, conforme descrito em P2363, estendendo recipientes associativos com as sobrecargas heterogêneas restantes que são direcionadas para C ++ 26. Isso possui sobrecargas para find , count , contains , equal_range (consulte P0919R3), erase (consulte P2077R2) e try_emplace , insert_or_assign , operator[] , at e insert & emplace para conjuntos (consulte P2363r3).
Para sobrecargas heterogêneas afetarem, hasher e key_equal precisam ter o atributo is_transparent Set.
Here is an example implementation that's usable with any string types that is convertible to std::string_view (eg char const* and 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 fazer uso deste hash, você precisará especificá -lo como um tipo e também um key_equal com is_transparent como std :: igual_to <>:
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); Para obter mais informações, consulte os exemplos em test/unit/transparent.cpp .
std::hash Quando uma implementação para std::hash of um tipo personalizada está disponível, isso é usado automaticamente e supõe -se que seja de má qualidade (assim std::hash é usado, mas uma etapa de mistura adicional é executada).
Quando o tipo possui uma representação de objeto exclusiva (sem preenchimento, copiável trivialmente), pode -se apenas hash a memória do objeto. Considere uma aula simples
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};Um hash rápido e de alta qualidade pode ser facilmente fornecido assim:
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));
}
}; Além da API std::unordered_map (consulte https://en.cppreference.com/w/cpp/container/unordered_map), temos API adicional que é um pouco semelhante à API do nó, mas aproveita o fato de que estamos usando um recipiente de acesso aleatório internamente:
auto extract() && -> value_container_type Extrai o recipiente usado internamente. *this é esvaziado.
extract() elementos únicos Semelhante ao erase() tenho um extract() . Ele se comporta exatamente o mesmo que erase , exceto que o valor de retorno é o elemento movido que é removido do contêiner:
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> Observe que a API extract(key) retorna uma std::optional<value_type> que está vazia quando a tecla não é encontrada.
[[nodiscard]] auto values() const noexcept -> value_container_type const&Expõe o contêiner de valores subjacentes.
auto replace(value_container_type&& container)Descarta o contêiner de capital internamente e substitui -o por um aprovado. Os elementos não únicos são removidos e o contêiner será parcialmente reordenado quando os elementos não únicos forem encontrados.
unordered_dense aceita um alocador personalizado, mas você também pode especificar um contêiner personalizado para esse argumento de modelo. Dessa forma, é possível substituir o std::vector por EG std::deque ou qualquer outro contêiner como boost::interprocess::vector . Isso suporta ponteiros sofisticados (por exemplo, offset_ptr), para que o contêiner possa ser usado com a memória compartilhada por exemplo, fornecida pelo boost::interprocess .
O mapa/conjunto suporta dois tipos de balde diferentes. O padrão deve ser bom para praticamente todo mundo.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map e segmented_set ankerl::unordered_dense fornece uma implementação de contêiner personalizada que possui requisitos de memória mais baixos do que o std::vector padrão. A memória não é contígua, mas pode alocar segmentos sem precisar realocar e mover todos os elementos. Em resumo, isso leva a
std::vector porque é necessária uma indireção adicional. Aqui está uma comparação com absl::flat_hash_map E O ankerl::unordered_dense::map ao inserir 10 milhões de entradas 
Abseil é mais rápido para este teste de inserção simples, levando um pouco mais de 0,8 segundos. Seu pico de uso de memória é de cerca de 430 MB. Observe como o uso da memória diminui após o último pico; Quando desce para ~ 290 MB, terminou de reformular e pode liberar o bloco de memória usado anteriormente.
ankerl::unordered_dense::segmented_map não possui esses picos e, em vez disso, tem um aumento suave do uso da memória. Observe que ainda há quedas repentinas e aumentos na memória, porque a estrutura de dados de indexação ainda precisa aumentar em um fator fixo. Mas, devido à manutenção dos dados em um contêiner separado, somos capazes de libertar primeiro a estrutura de dados antigos e, em seguida, alocar uma nova e maior estrutura de indexação; Assim, não temos picos.
O mapa/conjunto possui duas estruturas de dados:
std::vector<value_type> , que contém todos os dados. Iteradores de mapa/set são apenas std::vector<value_type>::iterator ! Sempre que um elemento é adicionado, ele é emplace_back ao vetor. A chave é hashed e uma entrada (bucket) é adicionada no local correspondente na matriz do balde. O balde tem essa estrutura:
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};Cada balde armazena 3 coisas:
dist_and_fingerprint )dist_and_fingerprint )Essa estrutura é especialmente projetada para a estratégia de resolução de colisão Robin-Hood Hashing com exclusão de mudança para trás.
A chave é hashed e a matriz do balde é pesquisada se tiver uma entrada nesse local com essa impressão digital. Quando encontrado, a chave no vetor de dados é comparada e, quando igual, o valor é retornado.
Como todos os dados são armazenados em um vetor, as remoções são um pouco mais complicadas:
value_idx do elemento movido. Isso requer outra pesquisa. Em 2023-09-10, fiz uma pesquisa rápida no Github para ver se este mapa é usado em qualquer projeto popular de código aberto. Aqui estão alguns dos projetos que encontrei. Envie -me uma nota se quiser nessa lista!
