Início / coding / Perguntas / 79182184
Accepted
Zebrafish
Asked: 2024-11-13 01:45:53 +0800 CST

Como posso usar tipos de chaves heterogêneos com boost::unordered_flat_map

  • 772

Boost unordered_flat_mapé muito bom, é bem mais rápido que std::unordered_map. Estou tentando usá-lo com tipos de chave heterogêneos:

boost::unordered::unordered_flat_map<std::string, int> my_map;
my_map.emplace(std::string("Hello"), 1);
my_map.find(std::string_view("Hello")); 
// no instance of overloaded function matches the argument list
            argument types are: (std::string_view)

Agora, como criei um mapa que tem o tipo de chave std::string, há uma função find que aceita um std::string, mas também há uma função find modelo que aceita um K, e normalmente essas coisas devem funcionar desde que o contêiner:

  1. Sabe como fazer hash do tipo heterogêneo e
  2. Conhece um operador de igualdade que considera o tipo heterogêneo como o lado direito.

Mesmo que eu faça:

auto equal_to = [](auto& lhs, auto& rhs) { return lhs == rhs; };

E passo essa classe de igualdade para o contêiner, ainda recebo o erro:

boost::unordered::unordered_flat_map<std::string, int, decltype(equal_to)> my_map;

Como faço para fazer isso funcionar?

c++

2 respostas

  1. Best Answer

    Do cppreference aprendemos que hash/igualdade transparentes permitem pesquisa de chaves heterogêneas :

    3,4) Encontra um elemento com chave que compara equivalente ao valor x. Esta sobrecarga participa da resolução de sobrecarga somente se Hash::is_transparent e KeyEqual::is_transparent forem válidos e cada um denotar um tipo. Isto pressupõe que tal Hash é chamável com ambos os tipos K e Key, e que KeyEqual é transparente, o que, juntos, permite chamar esta função sem construir uma instância de Key.

    Então, você pode fazer isso:

    struct MyHash : std::hash<std::string_view> {
    using is_transparent = std::true_type; // actual type doesn't matter
};

    Agora, para o que equal_topodemos ser preguiçosos e usar std::equal_to</*void*/>o que já é transparente:

    Ao Vivo Em Coliru

    #include <boost/unordered/unordered_flat_map.hpp>
using namespace std::literals;

struct MyHash : std::hash<std::string_view> {
    using is_transparent = std::true_type; // actual type doesn't matter
};

int main() {
    boost::unordered::unordered_flat_map<std::string, int, MyHash, std::equal_to<>> my_map;
    auto [where,ok] = my_map.emplace("Hello", 1);
    assert(ok);

    auto found = my_map.find("Hello"sv);
    assert(found != my_map.end());
    assert(found == where);
}

    Passando todas as assertivas. No meu código, eu provavelmente não confiaria em equal_to<void>para evitar surpresas. Você poderia substituir a "Rosetta Stone" do Boost core::string_view¹. Você também poderia tornar o hash ainda mais tolerante (por exemplo, expressando-o em termos de Boost ContainerHash).

    ¹ que é interoperável entre muitos, como boost::beast::string_view e std::string_view e muitos outros. No entanto, ele não suporta char-traits configuráveis.

    • 3

  2. Mais uma solução alternativa, mas preciso de mais espaço =]

    Você pode encapsular a pesquisa em uma função (como):

    int lookup(std::string_view k) {
    static std::string backing;
    backing = k;
    return my_map.find(backing);
}

    Como o std::stringé estático, ele não ficará alocando e desalocando continuamente cada chamada de função.

    • -1

relate perguntas