如何将异构键类型与 boost::unordered_flat_map 一起使用

Question

Boost

unordered_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 的查找函数，但也有一个采用 K 的模板化查找函数，通常这些东西应该可以工作容器：

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;

我该如何让它发挥作用？

Answer 1

从 cppreference 中我们了解到透明哈希/相等启用异构键查找:

3,4) 查找键与值比较相等的元素 x。仅当以下情况时，此重载才参与重载决策： Hash::is_transparent 和 KeyEqual::is_transparent 均有效 表示一种类型。这假设这样的哈希可以用 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 等等。但是，它不支持可配置的字符特征。

Answer 2

还有一个解决方案，但我需要更多空间 =]

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

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

由于

std::string

是静态的，因此它不会不断地分配和取消分配每个函数调用。