主页 / coding / 问题 / 79182184
Accepted
Zebrafish
Asked: 2024-11-13 01:45:53 +0800 CST

如何使用异构键类型和 boost::unordered_flat_map

  • 772

Boostunordered_flat_map非常好，比 快得多std::unordered_map。我尝试将它与异构键类型一起使用：

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)

现在，因为我创建了一个具有键类型 std::string 的映射，所以有一个接受 std::string 的 find 函数，但也有一个接受 K 的模板化 find 函数，并且通常这些东西应该在容器下工作：

  1. 知道如何对异构类型进行哈希处理，并且
  2. 知道一个将异构类型作为右侧的相等运算符。

即使我这样做：

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

并将这个相等类传递给容器我仍然收到错误：

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

我该如何让它工作呢？

c++

2 个回答

  1. Best Answer

    从 cppreference 中我们了解到透明哈希/相等性可以实现异构键查找：

    3,4) 查找具有与值 x 相等的键的元素。仅当 Hash::is_transparent 和 KeyEqual::is_transparent 有效且各自表示一种类型时，此重载才会参与重载解析。这假设此类 Hash 可使用 K 和 Key 类型调用，并且 KeyEqual 是透明的，两者结合起来，允许在不构造 Key 实例的情况下调用此函数。

    因此，你可以这样做：

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

    现在，equal_to我们可以偷懒并使用std::equal_to</*void*/>已经透明的：

    在 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);
}

    通过所有断言。在我的代码中，我可能不会依赖它equal_to<void>来防止意外。您可以替换 Boost 的“Rosetta Stone” core::string_view¹。您还可以使哈希更具容忍度（例如，用 Boost ContainerHash 来表达它）。

    ¹ 可与许多语言互操作，例如 boost::beast::string_view 和 std::string_view 等。但是，它不支持可配置的字符特征。

    • 3

  2. 又一个解决方法，但我需要更多空间=]

    您可以将查找包装在一个函数中（例如）：

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

    由于std::string是静态的，因此它不会在每个函数调用时不断地分配和取消分配。

    • -1

相关问题