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 的模板化查找函数,通常这些东西应该可以工作容器:
- 知道如何对异构类型进行哈希处理,并且
- 知道将异构类型作为右侧的相等运算符。
即使我这样做:
auto equal_to = [](auto& lhs, auto& rhs) { return lhs == rhs; };
并将这个相等类传递给容器我仍然收到错误:
boost::unordered::unordered_flat_map<std::string, int, decltype(equal_to)> my_map;
我该如何让它发挥作用?
从 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*/>
:
#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 等等。但是,它不支持可配置的字符特征。
还有一个解决方案,但我需要更多空间 =]
您可以将查找包装在函数中(例如):
int lookup(std::string_view k) {
static std::string backing;
backing = k;
return my_map.find(backing);
}
由于
std::string
是静态的,因此它不会不断地分配和取消分配每个函数调用。