c++ - 在 C++ 中实现跨度的异构查找

Question

异构查找意味着我们可以索引到持有 std::string 类型键的哈希映射。使用另一种有意义的兼容类型，例如 absl::string_view .例如，以下代码有效(出于某些兼容性原因，我在代码中使用 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保存字符串 View 的内容。
一个 std::vector<T>还有一个轻量级的字符串 View 模拟， 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[] 不匹配。 .

Question: How can I implement this heterogeneous lookup so that it works for vectors and spans in the same way as for strings and string views?

我可以看到 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工作。但是 []仍然会失败。为什么？因为 []运算符是一个 upsert - 如果它不存在，它会创建 key 。 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 []如果映射条目存在，则覆盖不会复制 vector ，同时仍然只做一个哈希。这有点 hacky 并且仍然可能进行额外的比较，但我认为您可以使用存储 key 和已计算哈希的辅助类型来完成此操作:

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