在C++中实现跨段的异构查找

Question

异构查找意味着我们可以使用另一种有意义的兼容类型(如absl::string_view(索引到包含类型为std::string的键的哈希映射中。例如，以下代码有效(出于某些兼容性原因，我在代码中使用Abseil库而不是C++20(：

std::string word = "bird";
absl::flat_hash_map<std::string, int> word_map;
word_map[word] = 1;
std::cout << word_map[absl::string_view(word)] << std::endl;

这是有道理的，因为我们所需要的只是计算哈希函数的能力，以及比较等式的能力。因此，使用这种方法读取哈希表应该很简单，写表也很有意义，因为哈希表可以创建一个新的std::string来保存字符串视图的内容。

std::vector<T>还具有字符串视图的轻量级类似物absl::Span<T>类型。但是，相应的查找不起作用：

std::vector<int> nums = {1, 2, 3, 4};
absl::flat_hash_map<std::vector<int>, int> int_map;
int_map[nums] = 1;
std::cout << int_map[absl::Span<int>(nums)] << std::endl;

编译器在最后一行抱怨operator[]没有匹配项。

问题：如何实现这种异构查找，使其以与字符串和字符串视图相同的方式适用于向量和跨度？

我可以看到absl::Hash<std::vector<int>>和absl::Hash<absl::Span<int>>产生了相同的结果，所以不应该有太多的障碍来实现这一点。

Answer 1

您可以通过定义类型来覆盖哈希和比较来实现Abseil的异构查找功能。根据文档，它们必须标记有is_transparent特征以支持转换。

struct VectorHash {
using is_transparent = void;
size_t operator()(absl::Span<int> v) const {
return absl::Hash<absl::Span<const int>>{}(v);
}
size_t operator()(const std::vector<int>& v) const {
return absl::Hash<absl::Span<const int>>{}(absl::Span<const int>{ v.data(), v.size() });
}
};
struct VectorEq {
using is_transparent = void;
bool operator()(const std::vector<int>& a, absl::Span<int> b) const {
return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
bool operator()(absl::Span<int> b, const std::vector<int>& a) const {
return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
bool operator()(const std::vector<int>& a, const std::vector<int>& b) const {
return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
bool operator()(absl::Span<int> b, absl::Span<int> a) const {
return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
};
using int_map_t = absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq>;

这将使用at或find进行查找。但是[]仍然会失败。为什么？因为[]操作符是一个追加程序——如果密钥不存在，它就会创建密钥。absl::string_view有一个到std::string的显式转换运算符，因此，从一个密钥创建一个新的std::string密钥是可行的。absl::Span<int>没有到std::vector<int>的转换运算符，因此操作失败。

如果不能选择使用at而不是[]，您仍然可以扩展类型：

struct int_map_t : absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq> {
using absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq>::flat_hash_map;
using absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq>::operator [];
int& operator [](absl::Span<int> v) {
return operator [](std::vector<int> { v.begin(), v.end() });
}
};

演示：https://godbolt.org/z/dW4av7

---

在评论中，您询问是否可以实现operator []覆盖，该覆盖在映射条目存在的情况下不复制向量，同时仍然只执行一个哈希。这有点麻烦，仍然可能会进行额外的比较，但我认为您可以使用一个既存储密钥又存储已计算哈希的助手类型来实现这一点：

struct VectorHashMemo {
size_t hash;
absl::Span<int> key;
explicit operator std::vector<int>() const {
return { key.begin(), key.end() };
}
};
struct VectorHash {
/* ...existing overloads... */
size_t operator()(VectorHashMemo v) const {
return v.hash;
}
};
struct VectorEq {
/* ...existing overloads... */
bool operator()(const std::vector<int>& a, VectorHashMemo b) const {
return operator()(a, b.key);
}
bool operator()(VectorHashMemo a, const std::vector<int>& b) const {
return operator()(a.key, b);
}
bool operator()(VectorHashMemo b, VectorHashMemo a) const {
return operator()(a.key, b.key);
}
};

然后，您可以只显式计算一次散列，同时访问两次映射：

struct int_map_t : absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq> {
using absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq>::flat_hash_map;
using absl::flat_hash_map<std::vector<int>, int, VectorHash, VectorEq>::operator [];
int& operator [](absl::Span<int> v) {
VectorHashMemo hash = { absl::Hash<absl::Span<int>>{}(v), v };
auto it = find(hash);
if (it != end()) {
return it->second;
} else {
// calls the explicit conversion operator
return operator [](hash);
}
return operator [](std::vector<int> { v.begin(), v.end() });
}
};

演示：https://godbolt.org/z/fecevE