robin map

Uma implementação C++ de um mapa de hash rápido e um conjunto de hash usando hashing Robin Hood

A biblioteca robin-map é uma implementação C++ de um mapa hash rápido e um conjunto de hash usando endereçamento aberto e hashing Robin Hood linear com exclusão de deslocamento para trás para resolver colisões.

Quatro classes são fornecidas: tsl::robin_map , tsl::robin_set , tsl::robin_pg_map e tsl::robin_pg_set . Os dois primeiros são mais rápidos e usam uma política de crescimento de potência de dois, os dois últimos usam uma política de crescimento principal e são capazes de lidar melhor com uma função hash pobre. Use a versão principal se houver uma chance de repetição de padrões nos bits inferiores do seu hash (por exemplo, você está armazenando ponteiros com uma função hash de identidade). Consulte GrowthPolicy para obter detalhes.

Uma referência de tsl::robin_map em relação a outros mapas hash pode ser encontrada aqui. Esta página também fornece alguns conselhos sobre qual estrutura de tabela hash você deve tentar para seu caso de uso (útil se você estiver um pouco perdido com as múltiplas implementações de tabelas hash no namespace tsl ).

Principais recursos

• Biblioteca somente de cabeçalho, basta adicionar o diretório include ao seu caminho de inclusão e você estará pronto para começar. Se você usar o CMake, também poderá usar o destino exportado tsl::robin_map do CMakeLists.txt.

• Tabela de hash rápida, verifique o benchmark para alguns números.

• Suporte para chave/valor construtível somente de movimentação e não padrão.

• Suporte para pesquisas heterogêneas permitindo o uso de find com um tipo diferente de Key (por exemplo, se você tiver um mapa que usa std::unique_ptr<foo> como chave, você pode usar um foo* ou um std::uintptr_t como parâmetro key para find sem construir um std::unique_ptr<foo> , veja o exemplo).

• Não há necessidade de reservar nenhum valor sentinela das chaves.

• Possibilidade de armazenar o valor de hash junto com o valor-chave armazenado para rehash e pesquisa mais rápida se o hash ou as funções de igualdade de chave forem caros para calcular. Observe que o hash pode ser armazenado mesmo que não seja solicitado explicitamente quando a biblioteca puder detectar que não terá impacto no tamanho da estrutura na memória devido ao alinhamento. Consulte o parâmetro do modelo StoreHash para obter detalhes.

• Se o hash for conhecido antes da consulta, é possível passá-lo como parâmetro para agilizar a consulta (ver parâmetro precalculated_hash na API).

• Suporte para serialização e desserialização eficientes (veja o exemplo e os métodos serialize/deserialize na API para obter detalhes).

• A biblioteca pode ser usada com exceções desabilitadas (através da opção -fno-exceptions no Clang e GCC, sem uma opção /EH no MSVC ou simplesmente definindo TSL_NO_EXCEPTIONS ). std::terminate é usado em substituição à instrução throw quando as exceções são desativadas.

• API muito semelhante a std::unordered_map e std::unordered_set .

Diferenças em comparação com std::unordered_map

tsl::robin_map tenta ter uma interface semelhante a std::unordered_map , mas existem algumas diferenças.

• A garantia de exceção forte só é válida se a seguinte instrução for verdadeira std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (onde value_type é Key para tsl::robin_set e std::pair<Key, T> para tsl::robin_map ). Caso contrário, se uma exceção for lançada durante a troca ou movimentação, a estrutura poderá acabar em um estado indefinido. Observe que, de acordo com o padrão, um value_type com um construtor noexcept copy e nenhum construtor move também satisfaz essa condição e, portanto, garantirá a forte garantia de exceção para a estrutura (consulte a API para obter detalhes).

• O tipo Key , e também T no caso de map, deve ser trocável. Eles também devem ser passíveis de cópia e/ou movimentação.

• A invalidação do iterador não se comporta da mesma maneira, qualquer operação que modifique a tabela hash os invalida (consulte a API para obter detalhes).

• Referências e ponteiros para chaves ou valores no mapa são invalidados da mesma forma que iteradores para essas chaves-valores.

• Para iteradores de tsl::robin_map , operator*() e operator->() retornam uma referência e um ponteiro para const std::pair<Key, T> em vez de std::pair<const Key, T> tornando o valor T não modificável. Para modificar o valor você deve chamar o método value() do iterador para obter uma referência mutável. Exemplo:

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

• Não há suporte para alguns métodos relacionados a buckets (como bucket_size , bucket , ...).

Essas diferenças também se aplicam entre std::unordered_set e tsl::robin_set .

As garantias de segurança de thread são as mesmas de std::unordered_map/set (ou seja, é possível ter vários leitores sem gravador).

Política de crescimento

A biblioteca oferece suporte a diversas políticas de crescimento por meio do parâmetro de modelo GrowthPolicy . Três políticas são fornecidas pela biblioteca, mas você pode implementar facilmente as suas próprias, se necessário.

• tsl::rh::power_of_two_growth_policy. Política padrão usada por tsl::robin_map/set . Esta política mantém o tamanho da matriz de buckets da tabela hash em uma potência de dois. Essa restrição permite que a política evite o uso da operação de módulo lento para mapear um hash para um bucket, em vez de hash % 2 n , ela usa hash & (2 n - 1) (consulte módulo rápido). Rápido, mas isso pode causar muitas colisões com uma função hash ruim, pois o módulo com potência de dois apenas mascara os bits mais significativos no final.

• tsl::rh::prime_growth_policy. Política padrão usada por tsl::robin_pg_map/set . A política mantém o tamanho da matriz de buckets da tabela hash em um número primo. Ao mapear um hash para um bucket, usar um número primo como módulo resultará em uma melhor distribuição do hash entre os buckets, mesmo com uma função de hash ruim. Para permitir que o compilador otimize a operação do módulo, a política usa uma tabela de consulta com módulos primos constantes (consulte a API para obter detalhes). Mais lento que tsl::rh::power_of_two_growth_policy , mas mais seguro.

• tsl::rh::mod_growth_policy. A política aumenta o mapa por meio de um fator de crescimento personalizável passado no parâmetro. Em seguida, basta usar o operador módulo para mapear um hash para um balde. Mais lento, mas mais flexível.

Para implementar sua própria política, você deve implementar a interface a seguir.

 struct custom_policy {// Chamado na construção e rehash da tabela hash, min_bucket_count_in_out são os buckets mínimos// que a tabela hash precisa. A política pode alterá-lo para um número maior de buckets, se necessário // e a tabela hash usará esse valor como contagem de buckets. Se 0 bucket for solicitado, o valor // deverá permanecer em 0.explicit custom_policy(std::size_t& min_bucket_count_in_out);    // Retorna o bucket [0, bucket_count()) ao qual o hash pertence. // Se bucket_count() for 0, ele deve sempre retornar 0.std::size_t bucket_for_hash(std::size_t hash) const noexcept;    // Retorna o número de buckets que devem ser usados ​​no próximo growthstd::size_t next_bucket_count() const;    // Número máximo de buckets suportados pela políticastd::size_t max_bucket_count() const;    // Redefina a política de crescimento como se a política tivesse sido criada com uma contagem de buckets de 0.// Após uma limpeza, a política deve sempre retornar 0 quando bucket_for_hash() for chamado.void clear() noexcept;
}

Instalação

Para usar o robin-map, basta adicionar o diretório include ao seu caminho de inclusão. É uma biblioteca somente de cabeçalho .

Se você usar o CMake, também poderá usar o destino exportado tsl::robin_map do CMakeLists.txt com target_link_libraries .

 # Exemplo onde o projeto robin-map é armazenado em um diretório de terceirosadd_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)

Se o projeto foi instalado por meio de make install , você também pode usar find_package(tsl-robin-map REQUIRED) em vez de add_subdirectory .

A biblioteca está disponível em vcpkg e conan. Também está presente nos repositórios de pacotes Debian, Ubuntu e Fedora.

O código deve funcionar com qualquer compilador compatível com o padrão C++17.

Para executar os testes você precisará da biblioteca Boost Test e do CMake.

 clone do git https://github.com/Tessil/robin-map.gitcd robin-map/tests
compilação mkdir buildcd
cm fazer..
cmake --build ../tsl_robin_map_tests

Uso

A API pode ser encontrada aqui.

Todos os métodos ainda não estão documentados, mas replicam o comportamento daqueles em std::unordered_map e std::unordered_set , exceto se especificado de outra forma.

Exemplo

 #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;

        map.insert({"e", 5});
    map.erase("b");    for(auto it = map.begin(); it != map.end(); ++it) {//it->second += 2; // Não é válido.it.value() += 2;
    } // {d, 6} {a, 3} {e, 7} {c, 5}for(const auto& key_value : map) {
        std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
    }
            if(map.find("a") != map.end()) {
        std::cout << "Encontrado "a"." << std::endl;
    } const std::size_t precalculated_hash = std::hash<std::string>()("a");// Se já sabemos o hash de antemão, podemos passá-lo no parâmetro para acelerar as pesquisas.if( map.find("a", precalculated_hash) != map.end()) {
        std::cout << "Encontrado "a" com hash " << precalculated_hash << "." << std::endl;
    }
        /* * Calcular o hash e comparar dois std::string pode ser lento.      * Podemos armazenar o hash de cada std::string no mapa hash para tornar * as inserções e pesquisas mais rápidas, definindo StoreHash como true.     */
     tsl::robin_map<std::string, int, std::hash<std::string>,
                    std::equal_to<std::string>,
                   std::allocator<std::pair<std::string, int>>, true> map2;

                           mapa2["a"] = 1;
    mapa2["b"] = 2;    // {a, 1} {b, 2}for(const auto& key_value : map2) {
        std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
    }




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

Pesquisas heterogêneas

Sobrecargas heterogêneas permitem o uso de outros tipos além de Key para operações de pesquisa e apagamento, desde que os tipos usados ​​sejam hasháveis ​​e comparáveis ​​a Key .

Para ativar as sobrecargas heterogêneas em tsl::robin_map/set , o ID qualificado KeyEqual::is_transparent deve ser válido. Funciona da mesma maneira que std::map::find . Você pode usar std::equal_to<> ou definir seu próprio objeto de função.

Tanto KeyEqual quanto Hash precisarão ser capazes de lidar com os diferentes tipos.

 #include <funcional>#include <iostream>#include <string>#include <tsl/robin_map.h>struct funcionário {funcionário(int id, std::string nome) : m_id(id), m_name(std::move (nome)) {
    } // Incluímos os comparadores na classe e usamos `std::equal_to<>`...friend bool operator==(const Employee& empl, int empl_id) {return empl.m_id == empl_id;
    } amigo bool operador==(int empl_id, const funcionário& empl) {return empl_id == empl.m_id;
    } amigo operador bool ==(const funcionário& empl1, const funcionário& empl2) {return empl1.m_id == empl2.m_id;
    }
        int m_id;
    std::string nome_m;
};// ... ou implementamos uma classe separada para comparar funcionários.struct equal_employee {using is_transparent = void;    operador bool() (const funcionário& empl, int empl_id) const {return empl.m_id == empl_id;
    } operador bool () (int empl_id, const funcionário& empl) const {return empl_id == empl.m_id;
    } operador bool() (const funcionário& empl1, const funcionário& empl2) const {return empl1.m_id == empl2.m_id;
    }
};struct hash_employee {
    std::size_t operador()(const funcionário& empl) const {return std::hash<int>()(empl.m_id);
    }

        std::size_t operador()(int id) const {return std::hash<int>()(id);
    }
};int main() {// Use std::equal_to<> que deduzirá e encaminhará automaticamente os parâmetrostsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
     map.insert({funcionário(1, "John Doe"), 2001});
    map.insert({funcionário(2, "Jane Doe"), 2002});
    map.insert({employee(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it != map.end()) {
        std::cout << it->first.m_name << " " << it->second << std::endl;
    }

    map.erase(1);// Use um KeyEqual personalizado que possui um membro is_transparent typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
    map2.insert({funcionário(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}

Serialização

A biblioteca fornece uma maneira eficiente de serializar e desserializar um mapa ou conjunto para que ele possa ser salvo em um arquivo ou enviado pela rede. Para fazer isso, é necessário que o usuário forneça um objeto de função para serialização e desserialização.

 struct serializer {// Deve suportar os seguintes tipos para U: std::int16_t, std::uint32_t, // std::uint64_t, float e std::pair<Key, T> se um mapa for usado ou Key para / / a set.template<typename U>void operador()(const U& valor);
};

 struct desserializer {// Deve suportar os seguintes tipos para U: std::int16_t, std::uint32_t, // std::uint64_t, float e std::pair<Key, T> se um mapa for usado ou Key para / /a set.template<nome do tipo U>
    Você operador()();
};

Observe que a implementação deixa a compatibilidade binária (endianness, representação binária flutuante, tamanho de int, ...) dos tipos que ela serializa/desserializa nas mãos dos objetos de função fornecidos, se a compatibilidade for necessária.

Mais detalhes sobre os métodos serialize e deserialize podem ser encontrados na API.

 #include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h>class serializer {public:serializer(const char* file_name) {
        m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
        m_ostream.open(nome_do_arquivo, std::ios::binary);
    } template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void operator()(const T& valor) {
        m_ostream.write(reinterpret_cast<const char*>(&valor), sizeof(T));
    } operador void()(const std::pair<std::int64_t, std::int64_t>& valor) {
        (*este)(valor.primeiro);
        (*este)(valor.segundo);
    }private:std::ofstream m_ostream;
};desserializador de classe {public:deserializer(const char* file_name) {
        m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
        m_istream.open(nome_do_arquivo, std::ios::binary);
    } modelo<classe T>
    Operador T()() {
        Valor T; desserializar (valor);        valor de retorno;
    }
    private:template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void deserialize(T& value) {
        m_istream.read(reinterpret_cast<char*>(&valor), sizeof(T));
    } void deserialize(std::pair<std::int64_t, std::int64_t>& valor) {deserialize(valor.primeiro);deserialize(valor.segundo);
    }private: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* nome_arquivo = "robin_map.data";
    {
        serializador serial(nome_arquivo);
        mapa.serialize(serial);
    }

        {
        desserializador dserial(nome_do_arquivo);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial);        assert(mapa == map_deserializado);
    }

        {
        desserializador dserial(nome_arquivo);        /** * Se o mapa serializado e desserializado forem compatíveis com hash (veja as condições na API), * definir o argumento como true acelera o processo de desserialização, pois não precisamos * recalcular o hash de cada chave. Também sabemos quanto espaço cada balde precisa.         */const bool hash_compatível = true;auto map_deserialized =
             tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_compatível);        assert(mapa == map_deserializado);
    }
}

Serialização com Boost Serialização e compactação com zlib

É possível usar uma biblioteca de serialização para evitar o clichê.

O exemplo a seguir usa Boost Serialization com o fluxo de compactação Boost zlib para reduzir o tamanho do arquivo serializado resultante. O exemplo requer C++20 devido ao uso da sintaxe da lista de parâmetros do modelo em lambdas, mas pode ser adaptado para versões menos recentes.

 #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 /serialization/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>namespace boost { serialização de namespace {template<class Archive, class Key, class T> void serialize(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int version) {split_free(ar, mapa, versão);
     }template<class Archive, class Key, class 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);
    }template<class Archive, class Key, class T>void load(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { você você; você está & você; devolva você; };
        map = tsl::robin_map<Key, T>::deserialize(deserializer);
    }
}}int principal() {
    tsl::robin_map<std::int64_t, std::int64_t> mapa = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
        const char* nome_arquivo = "robin_map.data";
    {
        std::ofstream des;
        ofs.exceptions(ofs.badbit | ofs.failbit);
        ofs.open(nome_arquivo, std::ios::binary);

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

                boost::archive::binary_oarchive oa(fo);

                oa << mapa;
    }

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

                boost::iostreams::filtering_istream fi;
        fi.push(boost::iostreams::zlib_decompressor());
        fi.push(ifs);

                boost::archive::binary_iarchive ia(fi);

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

Armadilhas de desempenho

Duas possíveis armadilhas de desempenho envolvendo tsl::robin_map e tsl::robin_set são dignas de nota:

1. Hashes ruins . Funções hash que produzem muitas colisões podem levar ao seguinte comportamento surpreendente: quando o número de colisões excede um determinado limite, a tabela hash se expande automaticamente para corrigir o problema. No entanto, em casos degenerados, esta expansão pode não ter efeito na contagem de colisões, causando um modo de falha onde uma sequência linear de inserção leva a um crescimento exponencial do armazenamento.

   Este caso foi observado principalmente ao usar a estratégia de crescimento padrão de potência de dois com o STL padrão std::hash<T> para tipos aritméticos T , que geralmente é uma identidade! Veja a edição nº 39 para ver um exemplo. A solução é simples: use uma função hash melhor e/ou tsl::robin_pg_set / tsl::robin_pg_map .

2. Apagamento de elementos e baixos fatores de carga . tsl::robin_map e tsl::robin_set espelham a API STL map/set, que expõe um método iterator erase(iterator) que remove um elemento em uma determinada posição, retornando um iterador válido que aponta para o próximo elemento.

   Construir esse novo objeto iterador requer caminhar até o próximo bucket não vazio na tabela, o que pode ser uma operação cara quando a tabela hash tem um fator de carga baixo (ou seja, quando capacity() é muito maior que size() ).

   Além disso, o método erase() nunca reduz e refaz o hash da tabela, pois isso não é permitido pela especificação desta função. Uma sequência linear de remoções aleatórias sem inserções intermediárias pode então levar a um caso degenerado com custo quadrático de tempo de execução.

   Nesses casos, muitas vezes nem é necessário um valor de retorno do iterador, portanto o custo é totalmente desnecessário. Portanto, tsl::robin_set e tsl::robin_map fornecem um método de apagamento alternativo void erase_fast(iterator) que não retorna um iterador para evitar ter que encontrar o próximo elemento.

Licença

O código está licenciado sob a licença MIT, consulte o arquivo LICENSE para obter detalhes.