Download de robin hood hashing - Download de código -fonte robin hood hashing

robin hood hashing

C/C++

3.11.5

Baixar

➵ Robin_hood Mapa não ordenado e conjunto

Nota: Infelizmente, não tenho tempo para continuar o desenvolvimento deste hashmap. Eu tenho um sucessor digno, por favor, vá até: ankerl::unordered_dense::{map, set}

Passei muito tempo desenvolvendo e aprimorando -o robin_hood , e funciona muito bem para a maioria dos casos de uso. Não farei mais atualizações para este código, a menos que sejam PRs para correções críticas de bugs.

robin_hood::unordered_map e robin_hood::unordered_set é um substituto independente da plataforma para std::unordered_map / std::unordered_set , que é mais rápido e mais eficiente na memória para casos de uso do mundo real.

Instalação e uso

Inclusão direta

Adicione robin_hood.h ao seu projeto C ++.
Use robin_hood::unordered_map em vez de std::unordered_map
Use robin_hood::unordered_set em vez de std::unordered_set

Conan, o gerenciador de pacotes C/C ++

Configure seus CMakeLists.txt (consulte a documentação de Conan sobre como usar o msbuild, meson e outros) assim:

 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)

Crie conanfile.txt em seu diretor de origem (não se esqueça de atualizar a versão)
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
Instale e execute Conan, depois construa seu projeto como sempre:
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
O pacote robin-hood-hashing em Conan é mantido atualizado pelos colaboradores de Conan. Se a versão estiver desatualizada, crie uma solicitação de problema ou puxe no repositório conan-center-index .

Benchmarks

Por favor, consulte os benchmarks extensos nos benchmarks Hashmaps. Em resumo: robin_hood está sempre entre os mapas mais rápidos e usa muito menos memória que std::unordered_map .

Escolhas de design

Dois layouts de memória . Os dados são armazenados em uma matriz plana ou com indireção do nó. O acesso para unordered_flat_map é extremamente rápido devido a nenhuma indiretiva, mas as referências a elementos não são estáveis. Ele também causa picos de alocação quando o mapa redimensionar e precisará de muita memória para objetos grandes. O mapa baseado no nó possui referências e ponteiros estáveis (não iteradores! Semelhante a std :: unorded_map) e usa const Key no par. É um pouco mais lento devido à indireção. A escolha é sua; Você pode usar robin_hood::unordered_flat_map ou robin_hood::unordered_node_map diretamente. Se você usar robin_hood::unordered_map ele tentará escolher o layout que parece apropriado para seus dados.
Alocador personalizado . A representação baseada em nó possui um alocador em massa personalizado que tenta fazer poucas alocações de memória. Toda a memória alocada é reutilizada, para que não haja picos de alocação. É muito rápido também.
Hash otimizado . robin_hood::hash possui implementações personalizadas para tipos inteiros e para std::string que são muito rápidos e volta a std::hash para todo o resto.
Depende do bom hash . Para um hash muito ruim, o desempenho não apenas se degradará como em std::unordered_map , o mapa simplesmente falhará com um std::overflow_error . Na prática, ao usar o padrão robin_hood::hash , nunca vi isso acontecendo.